1 /* Sequential list data type implemented by a binary tree.
2 Copyright (C) 2006-2007 Free Software Foundation, Inc.
3 Written by Bruno Haible <bruno@clisp.org>, 2006.
5 This program is free software: you can redistribute it and/or modify
6 it under the terms of the GNU General Public License as published by
7 the Free Software Foundation; either version 3 of the License, or
8 (at your option) any later version.
10 This program is distributed in the hope that it will be useful,
11 but WITHOUT ANY WARRANTY; without even the implied warranty of
12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 GNU General Public License for more details.
15 You should have received a copy of the GNU General Public License
16 along with this program. If not, see <http://www.gnu.org/licenses/>. */
18 /* Common code of gl_avltree_list.c and gl_avltreehash_list.c. */
20 /* -------------------------- gl_list_t Data Type -------------------------- */
22 /* Create a subtree for count >= 1 elements.
23 Its height is h where 2^(h-1) <= count <= 2^h - 1. */
25 create_subtree_with_contents (size_t count, const void **contents)
27 size_t half1 = (count - 1) / 2;
28 size_t half2 = count / 2;
29 /* Note: half1 + half2 = count - 1. */
30 gl_list_node_t node = XMALLOC (struct gl_list_node_impl);
34 node->left = create_subtree_with_contents (half1, contents);
35 node->left->parent = node;
40 node->value = contents[half1];
44 node->right = create_subtree_with_contents (half2, contents + half1 + 1);
45 node->right->parent = node;
50 /* balance is 0, except when count is a power of two and > 1.
51 Reason: half1 <= half2 <= half1 + 1, and the two branches can have
52 different heights only if half1 = 2^h - 1 and half2 = 2^h; in this
53 case, count = half1 + half2 + 1 = 2^(h+1). */
54 node->balance = (count > 1 && (count & (count - 1)) == 0 ? 1 : 0);
56 node->branch_size = count;
62 gl_tree_create (gl_list_implementation_t implementation,
63 gl_listelement_equals_fn equals_fn,
64 gl_listelement_hashcode_fn hashcode_fn,
65 gl_listelement_dispose_fn dispose_fn,
66 bool allow_duplicates,
67 size_t count, const void **contents)
69 struct gl_list_impl *list = XMALLOC (struct gl_list_impl);
71 list->base.vtable = implementation;
72 list->base.equals_fn = equals_fn;
73 list->base.hashcode_fn = hashcode_fn;
74 list->base.dispose_fn = dispose_fn;
75 list->base.allow_duplicates = allow_duplicates;
78 size_t estimate = xsum (count, count / 2); /* 1.5 * count */
81 list->table_size = next_prime (estimate);
82 list->table = XCALLOC (list->table_size, gl_hash_entry_t);
87 list->root = create_subtree_with_contents (count, contents);
88 list->root->parent = NULL;
91 /* Now that the tree is built, node_position() works. Now we can
92 add the nodes to the hash table. */
93 add_nodes_to_buckets (list);
102 /* Ensure the tree is balanced, after an insertion or deletion operation.
103 The height of NODE is incremented by HEIGHT_DIFF (1 or -1).
104 PARENT = NODE->parent. (NODE can also be NULL. But PARENT is non-NULL.)
105 Rotation operations are performed starting at PARENT (not NODE itself!). */
107 rebalance (gl_list_t list,
108 gl_list_node_t node, int height_diff, gl_list_node_t parent)
112 gl_list_node_t child;
113 int previous_balance;
115 gl_list_node_t nodeleft;
116 gl_list_node_t noderight;
121 previous_balance = node->balance;
123 /* The balance of NODE is incremented by BALANCE_DIFF: +1 if the right
124 branch's height has increased by 1 or the left branch's height has
125 decreased by 1, -1 if the right branch's height has decreased by 1 or
126 the left branch's height has increased by 1, 0 if no height change. */
127 if (node->left != NULL || node->right != NULL)
128 balance_diff = (child == node->right ? height_diff : -height_diff);
130 /* Special case where above formula doesn't work, because the caller
131 didn't tell whether node's left or right branch shrunk from height 1
133 balance_diff = - previous_balance;
135 node->balance += balance_diff;
136 if (balance_diff == previous_balance)
138 /* node->balance is outside the range [-1,1]. Must rotate. */
139 gl_list_node_t *nodep;
141 if (node->parent == NULL)
142 /* node == list->root */
144 else if (node->parent->left == node)
145 nodep = &node->parent->left;
146 else if (node->parent->right == node)
147 nodep = &node->parent->right;
151 nodeleft = node->left;
152 noderight = node->right;
154 if (balance_diff < 0)
156 /* node->balance = -2. The subtree is heavier on the left side.
157 Rotate from left to right:
163 gl_list_node_t nodeleftleft = nodeleft->left;
164 gl_list_node_t nodeleftright = nodeleft->right;
165 if (nodeleft->balance <= 0)
172 h+1 h|h+1 h+1 h|h+1 h
174 node->left = nodeleftright;
175 nodeleft->right = node;
177 nodeleft->parent = node->parent;
178 node->parent = nodeleft;
179 if (nodeleftright != NULL)
180 nodeleftright->parent = node;
182 nodeleft->balance += 1;
183 node->balance = - nodeleft->balance;
186 (nodeleftright != NULL ? nodeleftright->branch_size : 0)
187 + 1 + (noderight != NULL ? noderight->branch_size : 0);
188 nodeleft->branch_size =
189 nodeleftleft->branch_size + 1 + node->branch_size;
192 height_diff = (height_diff < 0
193 ? /* noderight's height had been decremented from
194 h+1 to h. The subtree's height changes from
196 nodeleft->balance - 1
197 : /* nodeleft's height had been incremented from
198 h+1 to h+2. The subtree's height changes from
214 gl_list_node_t L = nodeleft->right = nodeleftright->left;
215 gl_list_node_t R = node->left = nodeleftright->right;
216 nodeleftright->left = nodeleft;
217 nodeleftright->right = node;
219 nodeleftright->parent = node->parent;
221 L->parent = nodeleft;
224 nodeleft->parent = nodeleftright;
225 node->parent = nodeleftright;
227 nodeleft->balance = (nodeleftright->balance > 0 ? -1 : 0);
228 node->balance = (nodeleftright->balance < 0 ? 1 : 0);
229 nodeleftright->balance = 0;
231 nodeleft->branch_size =
232 (nodeleft->left != NULL ? nodeleft->left->branch_size : 0)
233 + 1 + (nodeleft->right != NULL ? nodeleft->right->branch_size : 0);
235 (node->left != NULL ? node->left->branch_size : 0)
236 + 1 + (node->right != NULL ? node->right->branch_size : 0);
237 nodeleftright->branch_size =
238 nodeleft->branch_size + 1 + node->branch_size;
240 *nodep = nodeleftright;
241 height_diff = (height_diff < 0
242 ? /* noderight's height had been decremented from
243 h+1 to h. The subtree's height changes from
246 : /* nodeleft's height had been incremented from
247 h+1 to h+2. The subtree's height changes from
254 /* node->balance = 2. The subtree is heavier on the right side.
255 Rotate from right to left:
261 gl_list_node_t noderightleft = noderight->left;
262 gl_list_node_t noderightright = noderight->right;
263 if (noderight->balance >= 0)
270 h|h+1 h+1 h h|h+1 h+1
272 node->right = noderightleft;
273 noderight->left = node;
275 noderight->parent = node->parent;
276 node->parent = noderight;
277 if (noderightleft != NULL)
278 noderightleft->parent = node;
280 noderight->balance -= 1;
281 node->balance = - noderight->balance;
284 (nodeleft != NULL ? nodeleft->branch_size : 0)
285 + 1 + (noderightleft != NULL ? noderightleft->branch_size : 0);
286 noderight->branch_size =
287 node->branch_size + 1 + noderightright->branch_size;
290 height_diff = (height_diff < 0
291 ? /* nodeleft's height had been decremented from
292 h+1 to h. The subtree's height changes from
294 - noderight->balance - 1
295 : /* noderight's height had been incremented from
296 h+1 to h+2. The subtree's height changes from
298 - noderight->balance);
312 gl_list_node_t L = node->right = noderightleft->left;
313 gl_list_node_t R = noderight->left = noderightleft->right;
314 noderightleft->left = node;
315 noderightleft->right = noderight;
317 noderightleft->parent = node->parent;
321 R->parent = noderight;
322 node->parent = noderightleft;
323 noderight->parent = noderightleft;
325 node->balance = (noderightleft->balance > 0 ? -1 : 0);
326 noderight->balance = (noderightleft->balance < 0 ? 1 : 0);
327 noderightleft->balance = 0;
330 (node->left != NULL ? node->left->branch_size : 0)
331 + 1 + (node->right != NULL ? node->right->branch_size : 0);
332 noderight->branch_size =
333 (noderight->left != NULL ? noderight->left->branch_size : 0)
334 + 1 + (noderight->right != NULL ? noderight->right->branch_size : 0);
335 noderightleft->branch_size =
336 node->branch_size + 1 + noderight->branch_size;
338 *nodep = noderightleft;
339 height_diff = (height_diff < 0
340 ? /* nodeleft's height had been decremented from
341 h+1 to h. The subtree's height changes from
344 : /* noderight's height had been incremented from
345 h+1 to h+2. The subtree's height changes from
354 /* No rotation needed. Only propagation of the height change to the
355 next higher level. */
357 height_diff = (previous_balance == 0 ? 0 : -1);
359 height_diff = (node->balance == 0 ? 0 : 1);
362 if (height_diff == 0)
365 parent = node->parent;
371 static gl_list_node_t
372 gl_tree_add_first (gl_list_t list, const void *elt)
374 /* Create new node. */
375 gl_list_node_t new_node = XMALLOC (struct gl_list_node_impl);
377 new_node->left = NULL;
378 new_node->right = NULL;
379 new_node->balance = 0;
380 new_node->branch_size = 1;
381 new_node->value = elt;
383 new_node->h.hashcode =
384 (list->base.hashcode_fn != NULL
385 ? list->base.hashcode_fn (new_node->value)
386 : (size_t)(uintptr_t) new_node->value);
389 /* Add it to the tree. */
390 if (list->root == NULL)
392 list->root = new_node;
393 new_node->parent = NULL;
399 for (node = list->root; node->left != NULL; )
402 node->left = new_node;
403 new_node->parent = node;
406 /* Update branch_size fields of the parent nodes. */
410 for (p = node; p != NULL; p = p->parent)
415 if (node->right == NULL && node->parent != NULL)
416 rebalance (list, node, 1, node->parent);
420 /* Add node to the hash table.
421 Note that this is only possible _after_ the node has been added to the
422 tree structure, because add_to_bucket() uses node_position(). */
423 add_to_bucket (list, new_node);
424 hash_resize_after_add (list);
430 static gl_list_node_t
431 gl_tree_add_last (gl_list_t list, const void *elt)
433 /* Create new node. */
434 gl_list_node_t new_node = XMALLOC (struct gl_list_node_impl);
436 new_node->left = NULL;
437 new_node->right = NULL;
438 new_node->balance = 0;
439 new_node->branch_size = 1;
440 new_node->value = elt;
442 new_node->h.hashcode =
443 (list->base.hashcode_fn != NULL
444 ? list->base.hashcode_fn (new_node->value)
445 : (size_t)(uintptr_t) new_node->value);
448 /* Add it to the tree. */
449 if (list->root == NULL)
451 list->root = new_node;
452 new_node->parent = NULL;
458 for (node = list->root; node->right != NULL; )
461 node->right = new_node;
462 new_node->parent = node;
465 /* Update branch_size fields of the parent nodes. */
469 for (p = node; p != NULL; p = p->parent)
474 if (node->left == NULL && node->parent != NULL)
475 rebalance (list, node, 1, node->parent);
479 /* Add node to the hash table.
480 Note that this is only possible _after_ the node has been added to the
481 tree structure, because add_to_bucket() uses node_position(). */
482 add_to_bucket (list, new_node);
483 hash_resize_after_add (list);
489 static gl_list_node_t
490 gl_tree_add_before (gl_list_t list, gl_list_node_t node, const void *elt)
492 /* Create new node. */
493 gl_list_node_t new_node = XMALLOC (struct gl_list_node_impl);
496 new_node->left = NULL;
497 new_node->right = NULL;
498 new_node->balance = 0;
499 new_node->branch_size = 1;
500 new_node->value = elt;
502 new_node->h.hashcode =
503 (list->base.hashcode_fn != NULL
504 ? list->base.hashcode_fn (new_node->value)
505 : (size_t)(uintptr_t) new_node->value);
508 /* Add it to the tree. */
509 if (node->left == NULL)
511 node->left = new_node;
513 height_inc = (node->right == NULL);
517 for (node = node->left; node->right != NULL; )
519 node->right = new_node;
521 height_inc = (node->left == NULL);
523 new_node->parent = node;
525 /* Update branch_size fields of the parent nodes. */
529 for (p = node; p != NULL; p = p->parent)
534 if (height_inc && node->parent != NULL)
535 rebalance (list, node, 1, node->parent);
538 /* Add node to the hash table.
539 Note that this is only possible _after_ the node has been added to the
540 tree structure, because add_to_bucket() uses node_position(). */
541 add_to_bucket (list, new_node);
542 hash_resize_after_add (list);
548 static gl_list_node_t
549 gl_tree_add_after (gl_list_t list, gl_list_node_t node, const void *elt)
551 /* Create new node. */
552 gl_list_node_t new_node = XMALLOC (struct gl_list_node_impl);
555 new_node->left = NULL;
556 new_node->right = NULL;
557 new_node->balance = 0;
558 new_node->branch_size = 1;
559 new_node->value = elt;
561 new_node->h.hashcode =
562 (list->base.hashcode_fn != NULL
563 ? list->base.hashcode_fn (new_node->value)
564 : (size_t)(uintptr_t) new_node->value);
567 /* Add it to the tree. */
568 if (node->right == NULL)
570 node->right = new_node;
572 height_inc = (node->left == NULL);
576 for (node = node->right; node->left != NULL; )
578 node->left = new_node;
580 height_inc = (node->right == NULL);
582 new_node->parent = node;
584 /* Update branch_size fields of the parent nodes. */
588 for (p = node; p != NULL; p = p->parent)
593 if (height_inc && node->parent != NULL)
594 rebalance (list, node, 1, node->parent);
597 /* Add node to the hash table.
598 Note that this is only possible _after_ the node has been added to the
599 tree structure, because add_to_bucket() uses node_position(). */
600 add_to_bucket (list, new_node);
601 hash_resize_after_add (list);
608 gl_tree_remove_node (gl_list_t list, gl_list_node_t node)
610 gl_list_node_t parent;
613 /* Remove node from the hash table.
614 Note that this is only possible _before_ the node is removed from the
615 tree structure, because remove_from_bucket() uses node_position(). */
616 remove_from_bucket (list, node);
619 parent = node->parent;
621 if (node->left == NULL)
623 /* Replace node with node->right. */
624 gl_list_node_t child = node->right;
627 child->parent = parent;
632 if (parent->left == node)
633 parent->left = child;
634 else /* parent->right == node */
635 parent->right = child;
637 /* Update branch_size fields of the parent nodes. */
641 for (p = parent; p != NULL; p = p->parent)
645 rebalance (list, child, -1, parent);
648 else if (node->right == NULL)
650 /* It is not absolutely necessary to treat this case. But the more
651 general case below is more complicated, hence slower. */
652 /* Replace node with node->left. */
653 gl_list_node_t child = node->left;
655 child->parent = parent;
660 if (parent->left == node)
661 parent->left = child;
662 else /* parent->right == node */
663 parent->right = child;
665 /* Update branch_size fields of the parent nodes. */
669 for (p = parent; p != NULL; p = p->parent)
673 rebalance (list, child, -1, parent);
678 /* Replace node with the rightmost element of the node->left subtree. */
679 gl_list_node_t subst;
680 gl_list_node_t subst_parent;
681 gl_list_node_t child;
683 for (subst = node->left; subst->right != NULL; )
684 subst = subst->right;
686 subst_parent = subst->parent;
690 /* The case subst_parent == node is special: If we do nothing special,
691 we get confusion about node->left, subst->left and child->parent.
693 <==> The 'for' loop above terminated immediately.
694 <==> subst == subst_parent->left
695 [otherwise subst == subst_parent->right]
696 In this case, we would need to first set
697 child->parent = node; node->left = child;
698 and later - when we copy subst into node's position - again
699 child->parent = subst; subst->left = child;
700 Altogether a no-op. */
701 if (subst_parent != node)
704 child->parent = subst_parent;
705 subst_parent->right = child;
708 /* Update branch_size fields of the parent nodes. */
712 for (p = subst_parent; p != NULL; p = p->parent)
716 /* Copy subst into node's position.
717 (This is safer than to copy subst's value into node, keep node in
718 place, and free subst.) */
719 if (subst_parent != node)
721 subst->left = node->left;
722 subst->left->parent = subst;
724 subst->right = node->right;
725 subst->right->parent = subst;
726 subst->balance = node->balance;
727 subst->branch_size = node->branch_size;
728 subst->parent = parent;
731 else if (parent->left == node)
732 parent->left = subst;
733 else /* parent->right == node */
734 parent->right = subst;
736 /* Rebalancing starts at child's parent, that is subst_parent -
737 except when subst_parent == node. In this case, we need to use
738 its replacement, subst. */
739 rebalance (list, child, -1, subst_parent != node ? subst_parent : subst);
742 if (list->base.dispose_fn != NULL)
743 list->base.dispose_fn (node->value);