1 /* Sequential list data type implemented by a binary tree.
2 Copyright (C) 2006-2007, 2009-2011 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.
24 Return NULL upon out-of-memory. */
26 create_subtree_with_contents (size_t count, const void **contents)
28 size_t half1 = (count - 1) / 2;
29 size_t half2 = count / 2;
30 /* Note: half1 + half2 = count - 1. */
32 (struct gl_list_node_impl *) malloc (sizeof (struct gl_list_node_impl));
38 node->left = create_subtree_with_contents (half1, contents);
39 if (node->left == NULL)
41 node->left->parent = node;
46 node->value = contents[half1];
50 node->right = create_subtree_with_contents (half2, contents + half1 + 1);
51 if (node->right == NULL)
53 node->right->parent = node;
58 /* balance is 0, except when count is a power of two and > 1.
59 Reason: half1 <= half2 <= half1 + 1, and the two branches can have
60 different heights only if half1 = 2^h - 1 and half2 = 2^h; in this
61 case, count = half1 + half2 + 1 = 2^(h+1). */
62 node->balance = (count > 1 && (count & (count - 1)) == 0 ? 1 : 0);
64 node->branch_size = count;
69 if (node->left != NULL)
70 free_subtree (node->left);
77 gl_tree_nx_create (gl_list_implementation_t implementation,
78 gl_listelement_equals_fn equals_fn,
79 gl_listelement_hashcode_fn hashcode_fn,
80 gl_listelement_dispose_fn dispose_fn,
81 bool allow_duplicates,
82 size_t count, const void **contents)
84 struct gl_list_impl *list =
85 (struct gl_list_impl *) malloc (sizeof (struct gl_list_impl));
90 list->base.vtable = implementation;
91 list->base.equals_fn = equals_fn;
92 list->base.hashcode_fn = hashcode_fn;
93 list->base.dispose_fn = dispose_fn;
94 list->base.allow_duplicates = allow_duplicates;
97 size_t estimate = xsum (count, count / 2); /* 1.5 * count */
100 list->table_size = next_prime (estimate);
101 if (size_overflow_p (xtimes (list->table_size, sizeof (gl_hash_entry_t))))
104 (gl_hash_entry_t *) calloc (list->table_size, sizeof (gl_hash_entry_t));
105 if (list->table == NULL)
111 list->root = create_subtree_with_contents (count, contents);
112 if (list->root == NULL)
114 list->root->parent = NULL;
117 /* Now that the tree is built, node_position() works. Now we can
118 add the nodes to the hash table. */
119 if (add_nodes_to_buckets (list) < 0)
130 free_subtree (list->root);
141 /* Ensure the tree is balanced, after an insertion or deletion operation.
142 The height of NODE is incremented by HEIGHT_DIFF (1 or -1).
143 PARENT = NODE->parent. (NODE can also be NULL. But PARENT is non-NULL.)
144 Rotation operations are performed starting at PARENT (not NODE itself!). */
146 rebalance (gl_list_t list,
147 gl_list_node_t node, int height_diff, gl_list_node_t parent)
151 gl_list_node_t child;
152 int previous_balance;
154 gl_list_node_t nodeleft;
155 gl_list_node_t noderight;
160 previous_balance = node->balance;
162 /* The balance of NODE is incremented by BALANCE_DIFF: +1 if the right
163 branch's height has increased by 1 or the left branch's height has
164 decreased by 1, -1 if the right branch's height has decreased by 1 or
165 the left branch's height has increased by 1, 0 if no height change. */
166 if (node->left != NULL || node->right != NULL)
167 balance_diff = (child == node->right ? height_diff : -height_diff);
169 /* Special case where above formula doesn't work, because the caller
170 didn't tell whether node's left or right branch shrunk from height 1
172 balance_diff = - previous_balance;
174 node->balance += balance_diff;
175 if (balance_diff == previous_balance)
177 /* node->balance is outside the range [-1,1]. Must rotate. */
178 gl_list_node_t *nodep;
180 if (node->parent == NULL)
181 /* node == list->root */
183 else if (node->parent->left == node)
184 nodep = &node->parent->left;
185 else if (node->parent->right == node)
186 nodep = &node->parent->right;
190 nodeleft = node->left;
191 noderight = node->right;
193 if (balance_diff < 0)
195 /* node->balance = -2. The subtree is heavier on the left side.
196 Rotate from left to right:
202 gl_list_node_t nodeleftleft = nodeleft->left;
203 gl_list_node_t nodeleftright = nodeleft->right;
204 if (nodeleft->balance <= 0)
211 h+1 h|h+1 h+1 h|h+1 h
213 node->left = nodeleftright;
214 nodeleft->right = node;
216 nodeleft->parent = node->parent;
217 node->parent = nodeleft;
218 if (nodeleftright != NULL)
219 nodeleftright->parent = node;
221 nodeleft->balance += 1;
222 node->balance = - nodeleft->balance;
225 (nodeleftright != NULL ? nodeleftright->branch_size : 0)
226 + 1 + (noderight != NULL ? noderight->branch_size : 0);
227 nodeleft->branch_size =
228 nodeleftleft->branch_size + 1 + node->branch_size;
231 height_diff = (height_diff < 0
232 ? /* noderight's height had been decremented from
233 h+1 to h. The subtree's height changes from
235 nodeleft->balance - 1
236 : /* nodeleft's height had been incremented from
237 h+1 to h+2. The subtree's height changes from
253 gl_list_node_t L = nodeleft->right = nodeleftright->left;
254 gl_list_node_t R = node->left = nodeleftright->right;
255 nodeleftright->left = nodeleft;
256 nodeleftright->right = node;
258 nodeleftright->parent = node->parent;
260 L->parent = nodeleft;
263 nodeleft->parent = nodeleftright;
264 node->parent = nodeleftright;
266 nodeleft->balance = (nodeleftright->balance > 0 ? -1 : 0);
267 node->balance = (nodeleftright->balance < 0 ? 1 : 0);
268 nodeleftright->balance = 0;
270 nodeleft->branch_size =
271 (nodeleft->left != NULL ? nodeleft->left->branch_size : 0)
272 + 1 + (nodeleft->right != NULL ? nodeleft->right->branch_size : 0);
274 (node->left != NULL ? node->left->branch_size : 0)
275 + 1 + (node->right != NULL ? node->right->branch_size : 0);
276 nodeleftright->branch_size =
277 nodeleft->branch_size + 1 + node->branch_size;
279 *nodep = nodeleftright;
280 height_diff = (height_diff < 0
281 ? /* noderight's height had been decremented from
282 h+1 to h. The subtree's height changes from
285 : /* nodeleft's height had been incremented from
286 h+1 to h+2. The subtree's height changes from
293 /* node->balance = 2. The subtree is heavier on the right side.
294 Rotate from right to left:
300 gl_list_node_t noderightleft = noderight->left;
301 gl_list_node_t noderightright = noderight->right;
302 if (noderight->balance >= 0)
309 h|h+1 h+1 h h|h+1 h+1
311 node->right = noderightleft;
312 noderight->left = node;
314 noderight->parent = node->parent;
315 node->parent = noderight;
316 if (noderightleft != NULL)
317 noderightleft->parent = node;
319 noderight->balance -= 1;
320 node->balance = - noderight->balance;
323 (nodeleft != NULL ? nodeleft->branch_size : 0)
324 + 1 + (noderightleft != NULL ? noderightleft->branch_size : 0);
325 noderight->branch_size =
326 node->branch_size + 1 + noderightright->branch_size;
329 height_diff = (height_diff < 0
330 ? /* nodeleft's height had been decremented from
331 h+1 to h. The subtree's height changes from
333 - noderight->balance - 1
334 : /* noderight's height had been incremented from
335 h+1 to h+2. The subtree's height changes from
337 - noderight->balance);
351 gl_list_node_t L = node->right = noderightleft->left;
352 gl_list_node_t R = noderight->left = noderightleft->right;
353 noderightleft->left = node;
354 noderightleft->right = noderight;
356 noderightleft->parent = node->parent;
360 R->parent = noderight;
361 node->parent = noderightleft;
362 noderight->parent = noderightleft;
364 node->balance = (noderightleft->balance > 0 ? -1 : 0);
365 noderight->balance = (noderightleft->balance < 0 ? 1 : 0);
366 noderightleft->balance = 0;
369 (node->left != NULL ? node->left->branch_size : 0)
370 + 1 + (node->right != NULL ? node->right->branch_size : 0);
371 noderight->branch_size =
372 (noderight->left != NULL ? noderight->left->branch_size : 0)
373 + 1 + (noderight->right != NULL ? noderight->right->branch_size : 0);
374 noderightleft->branch_size =
375 node->branch_size + 1 + noderight->branch_size;
377 *nodep = noderightleft;
378 height_diff = (height_diff < 0
379 ? /* nodeleft's height had been decremented from
380 h+1 to h. The subtree's height changes from
383 : /* noderight's height had been incremented from
384 h+1 to h+2. The subtree's height changes from
393 /* No rotation needed. Only propagation of the height change to the
394 next higher level. */
396 height_diff = (previous_balance == 0 ? 0 : -1);
398 height_diff = (node->balance == 0 ? 0 : 1);
401 if (height_diff == 0)
404 parent = node->parent;
411 gl_tree_remove_node_from_tree (gl_list_t list, gl_list_node_t node)
413 gl_list_node_t parent = node->parent;
415 if (node->left == NULL)
417 /* Replace node with node->right. */
418 gl_list_node_t child = node->right;
421 child->parent = parent;
426 if (parent->left == node)
427 parent->left = child;
428 else /* parent->right == node */
429 parent->right = child;
431 /* Update branch_size fields of the parent nodes. */
435 for (p = parent; p != NULL; p = p->parent)
439 rebalance (list, child, -1, parent);
442 else if (node->right == NULL)
444 /* It is not absolutely necessary to treat this case. But the more
445 general case below is more complicated, hence slower. */
446 /* Replace node with node->left. */
447 gl_list_node_t child = node->left;
449 child->parent = parent;
454 if (parent->left == node)
455 parent->left = child;
456 else /* parent->right == node */
457 parent->right = child;
459 /* Update branch_size fields of the parent nodes. */
463 for (p = parent; p != NULL; p = p->parent)
467 rebalance (list, child, -1, parent);
472 /* Replace node with the rightmost element of the node->left subtree. */
473 gl_list_node_t subst;
474 gl_list_node_t subst_parent;
475 gl_list_node_t child;
477 for (subst = node->left; subst->right != NULL; )
478 subst = subst->right;
480 subst_parent = subst->parent;
484 /* The case subst_parent == node is special: If we do nothing special,
485 we get confusion about node->left, subst->left and child->parent.
487 <==> The 'for' loop above terminated immediately.
488 <==> subst == subst_parent->left
489 [otherwise subst == subst_parent->right]
490 In this case, we would need to first set
491 child->parent = node; node->left = child;
492 and later - when we copy subst into node's position - again
493 child->parent = subst; subst->left = child;
494 Altogether a no-op. */
495 if (subst_parent != node)
498 child->parent = subst_parent;
499 subst_parent->right = child;
502 /* Update branch_size fields of the parent nodes. */
506 for (p = subst_parent; p != NULL; p = p->parent)
510 /* Copy subst into node's position.
511 (This is safer than to copy subst's value into node, keep node in
512 place, and free subst.) */
513 if (subst_parent != node)
515 subst->left = node->left;
516 subst->left->parent = subst;
518 subst->right = node->right;
519 subst->right->parent = subst;
520 subst->balance = node->balance;
521 subst->branch_size = node->branch_size;
522 subst->parent = parent;
525 else if (parent->left == node)
526 parent->left = subst;
527 else /* parent->right == node */
528 parent->right = subst;
530 /* Rebalancing starts at child's parent, that is subst_parent -
531 except when subst_parent == node. In this case, we need to use
532 its replacement, subst. */
533 rebalance (list, child, -1, subst_parent != node ? subst_parent : subst);
537 static gl_list_node_t
538 gl_tree_nx_add_first (gl_list_t list, const void *elt)
540 /* Create new node. */
541 gl_list_node_t new_node =
542 (struct gl_list_node_impl *) malloc (sizeof (struct gl_list_node_impl));
544 if (new_node == NULL)
547 new_node->left = NULL;
548 new_node->right = NULL;
549 new_node->balance = 0;
550 new_node->branch_size = 1;
551 new_node->value = elt;
553 new_node->h.hashcode =
554 (list->base.hashcode_fn != NULL
555 ? list->base.hashcode_fn (new_node->value)
556 : (size_t)(uintptr_t) new_node->value);
559 /* Add it to the tree. */
560 if (list->root == NULL)
562 list->root = new_node;
563 new_node->parent = NULL;
569 for (node = list->root; node->left != NULL; )
572 node->left = new_node;
573 new_node->parent = node;
576 /* Update branch_size fields of the parent nodes. */
580 for (p = node; p != NULL; p = p->parent)
585 if (node->right == NULL && node->parent != NULL)
586 rebalance (list, node, 1, node->parent);
590 /* Add node to the hash table.
591 Note that this is only possible _after_ the node has been added to the
592 tree structure, because add_to_bucket() uses node_position(). */
593 if (add_to_bucket (list, new_node) < 0)
595 gl_tree_remove_node_from_tree (list, new_node);
599 hash_resize_after_add (list);
605 static gl_list_node_t
606 gl_tree_nx_add_last (gl_list_t list, const void *elt)
608 /* Create new node. */
609 gl_list_node_t new_node =
610 (struct gl_list_node_impl *) malloc (sizeof (struct gl_list_node_impl));
612 if (new_node == NULL)
615 new_node->left = NULL;
616 new_node->right = NULL;
617 new_node->balance = 0;
618 new_node->branch_size = 1;
619 new_node->value = elt;
621 new_node->h.hashcode =
622 (list->base.hashcode_fn != NULL
623 ? list->base.hashcode_fn (new_node->value)
624 : (size_t)(uintptr_t) new_node->value);
627 /* Add it to the tree. */
628 if (list->root == NULL)
630 list->root = new_node;
631 new_node->parent = NULL;
637 for (node = list->root; node->right != NULL; )
640 node->right = new_node;
641 new_node->parent = node;
644 /* Update branch_size fields of the parent nodes. */
648 for (p = node; p != NULL; p = p->parent)
653 if (node->left == NULL && node->parent != NULL)
654 rebalance (list, node, 1, node->parent);
658 /* Add node to the hash table.
659 Note that this is only possible _after_ the node has been added to the
660 tree structure, because add_to_bucket() uses node_position(). */
661 if (add_to_bucket (list, new_node) < 0)
663 gl_tree_remove_node_from_tree (list, new_node);
667 hash_resize_after_add (list);
673 static gl_list_node_t
674 gl_tree_nx_add_before (gl_list_t list, gl_list_node_t node, const void *elt)
676 /* Create new node. */
677 gl_list_node_t new_node;
681 (struct gl_list_node_impl *) malloc (sizeof (struct gl_list_node_impl));
682 if (new_node == NULL)
685 new_node->left = NULL;
686 new_node->right = NULL;
687 new_node->balance = 0;
688 new_node->branch_size = 1;
689 new_node->value = elt;
691 new_node->h.hashcode =
692 (list->base.hashcode_fn != NULL
693 ? list->base.hashcode_fn (new_node->value)
694 : (size_t)(uintptr_t) new_node->value);
697 /* Add it to the tree. */
698 if (node->left == NULL)
700 node->left = new_node;
702 height_inc = (node->right == NULL);
706 for (node = node->left; node->right != NULL; )
708 node->right = new_node;
710 height_inc = (node->left == NULL);
712 new_node->parent = node;
714 /* Update branch_size fields of the parent nodes. */
718 for (p = node; p != NULL; p = p->parent)
723 if (height_inc && node->parent != NULL)
724 rebalance (list, node, 1, node->parent);
727 /* Add node to the hash table.
728 Note that this is only possible _after_ the node has been added to the
729 tree structure, because add_to_bucket() uses node_position(). */
730 if (add_to_bucket (list, new_node) < 0)
732 gl_tree_remove_node_from_tree (list, new_node);
736 hash_resize_after_add (list);
742 static gl_list_node_t
743 gl_tree_nx_add_after (gl_list_t list, gl_list_node_t node, const void *elt)
745 /* Create new node. */
746 gl_list_node_t new_node;
750 (struct gl_list_node_impl *) malloc (sizeof (struct gl_list_node_impl));
751 if (new_node == NULL)
754 new_node->left = NULL;
755 new_node->right = NULL;
756 new_node->balance = 0;
757 new_node->branch_size = 1;
758 new_node->value = elt;
760 new_node->h.hashcode =
761 (list->base.hashcode_fn != NULL
762 ? list->base.hashcode_fn (new_node->value)
763 : (size_t)(uintptr_t) new_node->value);
766 /* Add it to the tree. */
767 if (node->right == NULL)
769 node->right = new_node;
771 height_inc = (node->left == NULL);
775 for (node = node->right; node->left != NULL; )
777 node->left = new_node;
779 height_inc = (node->right == NULL);
781 new_node->parent = node;
783 /* Update branch_size fields of the parent nodes. */
787 for (p = node; p != NULL; p = p->parent)
792 if (height_inc && node->parent != NULL)
793 rebalance (list, node, 1, node->parent);
796 /* Add node to the hash table.
797 Note that this is only possible _after_ the node has been added to the
798 tree structure, because add_to_bucket() uses node_position(). */
799 if (add_to_bucket (list, new_node) < 0)
801 gl_tree_remove_node_from_tree (list, new_node);
805 hash_resize_after_add (list);