1 /* Sequential list data type implemented by a binary tree.
2 Copyright (C) 2006-2007, 2009-2010 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_rbtree_list.c and gl_rbtreehash_list.c. */
20 /* -------------------------- gl_list_t Data Type -------------------------- */
22 /* Create a subtree for count >= 1 elements.
23 Its black-height bh is passed as argument, with
24 2^bh - 1 <= count <= 2^(bh+1) - 1. bh == 0 implies count == 1.
25 Its height is h where 2^(h-1) <= count <= 2^h - 1.
26 Return NULL upon out-of-memory. */
28 create_subtree_with_contents (unsigned int bh,
29 size_t count, const void **contents)
31 size_t half1 = (count - 1) / 2;
32 size_t half2 = count / 2;
33 /* Note: half1 + half2 = count - 1. */
35 (struct gl_list_node_impl *) malloc (sizeof (struct gl_list_node_impl));
41 /* half1 > 0 implies count > 1, implies bh >= 1, implies
42 2^(bh-1) - 1 <= half1 <= 2^bh - 1. */
44 create_subtree_with_contents (bh - 1, half1, contents);
45 if (node->left == NULL)
47 node->left->parent = node;
52 node->value = contents[half1];
56 /* half2 > 0 implies count > 1, implies bh >= 1, implies
57 2^(bh-1) - 1 <= half2 <= 2^bh - 1. */
59 create_subtree_with_contents (bh - 1, half2, contents + half1 + 1);
60 if (node->right == NULL)
62 node->right->parent = node;
67 node->color = (bh == 0 ? RED : BLACK);
69 node->branch_size = count;
74 if (node->left != NULL)
75 free_subtree (node->left);
82 gl_tree_nx_create (gl_list_implementation_t implementation,
83 gl_listelement_equals_fn equals_fn,
84 gl_listelement_hashcode_fn hashcode_fn,
85 gl_listelement_dispose_fn dispose_fn,
86 bool allow_duplicates,
87 size_t count, const void **contents)
89 struct gl_list_impl *list =
90 (struct gl_list_impl *) malloc (sizeof (struct gl_list_impl));
95 list->base.vtable = implementation;
96 list->base.equals_fn = equals_fn;
97 list->base.hashcode_fn = hashcode_fn;
98 list->base.dispose_fn = dispose_fn;
99 list->base.allow_duplicates = allow_duplicates;
102 size_t estimate = xsum (count, count / 2); /* 1.5 * count */
105 list->table_size = next_prime (estimate);
106 if (size_overflow_p (xtimes (list->table_size, sizeof (gl_hash_entry_t))))
109 (gl_hash_entry_t *) calloc (list->table_size, sizeof (gl_hash_entry_t));
110 if (list->table == NULL)
116 /* Assuming 2^bh - 1 <= count <= 2^(bh+1) - 2, we create a tree whose
117 upper bh levels are black, and only the partially present lowest
122 for (n = count + 1, bh = 0; n > 1; n = n >> 1)
126 list->root = create_subtree_with_contents (bh, count, contents);
127 if (list->root == NULL)
129 list->root->parent = NULL;
132 /* Now that the tree is built, node_position() works. Now we can
133 add the nodes to the hash table. */
134 if (add_nodes_to_buckets (list) < 0)
145 free_subtree (list->root);
156 /* Rotate left a subtree.
164 Change the tree structure, update the branch sizes.
165 The caller must update the colors and register D as child of its parent. */
166 static inline gl_list_node_t
167 rotate_left (gl_list_node_t b_node, gl_list_node_t d_node)
169 gl_list_node_t a_node = b_node->left;
170 gl_list_node_t c_node = d_node->left;
171 gl_list_node_t e_node = d_node->right;
173 b_node->right = c_node;
174 d_node->left = b_node;
176 d_node->parent = b_node->parent;
177 b_node->parent = d_node;
179 c_node->parent = b_node;
181 b_node->branch_size =
182 (a_node != NULL ? a_node->branch_size : 0)
183 + 1 + (c_node != NULL ? c_node->branch_size : 0);
184 d_node->branch_size =
185 b_node->branch_size + 1 + (e_node != NULL ? e_node->branch_size : 0);
190 /* Rotate right a subtree.
198 Change the tree structure, update the branch sizes.
199 The caller must update the colors and register B as child of its parent. */
200 static inline gl_list_node_t
201 rotate_right (gl_list_node_t b_node, gl_list_node_t d_node)
203 gl_list_node_t a_node = b_node->left;
204 gl_list_node_t c_node = b_node->right;
205 gl_list_node_t e_node = d_node->right;
207 d_node->left = c_node;
208 b_node->right = d_node;
210 b_node->parent = d_node->parent;
211 d_node->parent = b_node;
213 c_node->parent = d_node;
215 d_node->branch_size =
216 (c_node != NULL ? c_node->branch_size : 0)
217 + 1 + (e_node != NULL ? e_node->branch_size : 0);
218 b_node->branch_size =
219 (a_node != NULL ? a_node->branch_size : 0) + 1 + d_node->branch_size;
224 /* Ensure the tree is balanced, after an insertion operation.
225 Also assigns node->color.
226 parent is the given node's parent, known to be non-NULL. */
228 rebalance_after_add (gl_list_t list, gl_list_node_t node, gl_list_node_t parent)
232 /* At this point, parent = node->parent != NULL.
233 Think of node->color being RED (although node->color is not yet
235 gl_list_node_t grandparent;
236 gl_list_node_t uncle;
238 if (parent->color == BLACK)
240 /* A RED color for node is acceptable. */
245 grandparent = parent->parent;
246 /* Since parent is RED, we know that
247 grandparent is != NULL and colored BLACK. */
249 if (grandparent->left == parent)
250 uncle = grandparent->right;
251 else if (grandparent->right == parent)
252 uncle = grandparent->left;
256 if (uncle != NULL && uncle->color == RED)
258 /* Change grandparent from BLACK to RED, and
259 change parent and uncle from RED to BLACK.
260 This makes it acceptable for node to be RED. */
262 parent->color = uncle->color = BLACK;
267 /* grandparent and uncle are BLACK. parent is RED. node wants
269 In this case, recoloring is not sufficient. Need to perform
270 one or two rotations. */
271 gl_list_node_t *grandparentp;
273 if (grandparent->parent == NULL)
274 grandparentp = &list->root;
275 else if (grandparent->parent->left == grandparent)
276 grandparentp = &grandparent->parent->left;
277 else if (grandparent->parent->right == grandparent)
278 grandparentp = &grandparent->parent->right;
282 if (grandparent->left == parent)
284 if (parent->right == node)
286 /* Rotation between node and parent. */
287 grandparent->left = rotate_left (parent, node);
289 parent = grandparent->left;
291 /* grandparent and uncle are BLACK. parent and node want to be
292 RED. parent = grandparent->left. node = parent->left.
297 parent uncle --> node grandparent
303 *grandparentp = rotate_right (parent, grandparent);
304 parent->color = BLACK;
305 node->color = grandparent->color = RED;
307 else /* grandparent->right == parent */
309 if (parent->left == node)
311 /* Rotation between node and parent. */
312 grandparent->right = rotate_right (node, parent);
314 parent = grandparent->right;
316 /* grandparent and uncle are BLACK. parent and node want to be
317 RED. parent = grandparent->right. node = parent->right.
322 uncle parent --> grandparent node
328 *grandparentp = rotate_left (grandparent, parent);
329 parent->color = BLACK;
330 node->color = grandparent->color = RED;
335 /* Start again with a new (node, parent) pair. */
336 parent = node->parent;
340 /* Change node's color from RED to BLACK. This increases the
341 tree's black-height. */
348 /* Ensure the tree is balanced, after a deletion operation.
349 CHILD was a grandchild of PARENT and is now its child. Between them,
350 a black node was removed. CHILD is also black, or NULL.
351 (CHILD can also be NULL. But PARENT is non-NULL.) */
353 rebalance_after_remove (gl_list_t list, gl_list_node_t child, gl_list_node_t parent)
357 /* At this point, we reduced the black-height of the CHILD subtree by 1.
358 To make up, either look for a possibility to turn a RED to a BLACK
359 node, or try to reduce the black-height tree of CHILD's sibling
361 gl_list_node_t *parentp;
363 if (parent->parent == NULL)
364 parentp = &list->root;
365 else if (parent->parent->left == parent)
366 parentp = &parent->parent->left;
367 else if (parent->parent->right == parent)
368 parentp = &parent->parent->right;
372 if (parent->left == child)
374 gl_list_node_t sibling = parent->right;
375 /* sibling's black-height is >= 1. In particular,
384 if (sibling->color == RED)
386 /* sibling is RED, hence parent is BLACK and sibling's children
387 are non-NULL and BLACK.
392 child sibling --> parent SR
398 *parentp = rotate_left (parent, sibling);
400 sibling->color = BLACK;
402 /* Concentrate on the subtree of parent. The new sibling is
403 one of the old sibling's children, and known to be BLACK. */
404 parentp = &sibling->left;
405 sibling = parent->right;
407 /* Now we know that sibling is BLACK.
414 if (sibling->right != NULL && sibling->right->color == RED)
420 child sibling --> parent SR
426 *parentp = rotate_left (parent, sibling);
427 sibling->color = parent->color;
428 parent->color = BLACK;
429 sibling->right->color = BLACK;
432 else if (sibling->left != NULL && sibling->left->color == RED)
438 child sibling --> child SL
447 where SLL, SLR, SR are all black.
449 parent->right = rotate_right (sibling->left, sibling);
450 /* Change sibling from BLACK to RED and SL from RED to BLACK. */
451 sibling->color = RED;
452 sibling = parent->right;
453 sibling->color = BLACK;
455 /* Now do as in the previous case. */
456 *parentp = rotate_left (parent, sibling);
457 sibling->color = parent->color;
458 parent->color = BLACK;
459 sibling->right->color = BLACK;
464 if (parent->color == BLACK)
466 /* Change sibling from BLACK to RED. Then the entire
467 subtree at parent has decreased its black-height.
471 child sibling --> child sibling
474 sibling->color = RED;
480 /* Change parent from RED to BLACK, but compensate by
481 changing sibling from BLACK to RED.
485 child sibling --> child sibling
488 parent->color = BLACK;
489 sibling->color = RED;
494 else if (parent->right == child)
496 gl_list_node_t sibling = parent->left;
497 /* sibling's black-height is >= 1. In particular,
506 if (sibling->color == RED)
508 /* sibling is RED, hence parent is BLACK and sibling's children
509 are non-NULL and BLACK.
514 sibling child --> SR parent
520 *parentp = rotate_right (sibling, parent);
522 sibling->color = BLACK;
524 /* Concentrate on the subtree of parent. The new sibling is
525 one of the old sibling's children, and known to be BLACK. */
526 parentp = &sibling->right;
527 sibling = parent->left;
529 /* Now we know that sibling is BLACK.
536 if (sibling->left != NULL && sibling->left->color == RED)
542 sibling child --> SL parent
548 *parentp = rotate_right (sibling, parent);
549 sibling->color = parent->color;
550 parent->color = BLACK;
551 sibling->left->color = BLACK;
554 else if (sibling->right != NULL && sibling->right->color == RED)
560 sibling child --> SR child
569 where SL, SRL, SRR are all black.
571 parent->left = rotate_left (sibling, sibling->right);
572 /* Change sibling from BLACK to RED and SL from RED to BLACK. */
573 sibling->color = RED;
574 sibling = parent->left;
575 sibling->color = BLACK;
577 /* Now do as in the previous case. */
578 *parentp = rotate_right (sibling, parent);
579 sibling->color = parent->color;
580 parent->color = BLACK;
581 sibling->left->color = BLACK;
586 if (parent->color == BLACK)
588 /* Change sibling from BLACK to RED. Then the entire
589 subtree at parent has decreased its black-height.
593 sibling child --> sibling child
596 sibling->color = RED;
602 /* Change parent from RED to BLACK, but compensate by
603 changing sibling from BLACK to RED.
607 sibling child --> sibling child
610 parent->color = BLACK;
611 sibling->color = RED;
619 /* Start again with a new (child, parent) pair. */
620 parent = child->parent;
622 #if 0 /* Already handled. */
623 if (child != NULL && child->color == RED)
625 child->color = BLACK;
636 gl_tree_remove_node_from_tree (gl_list_t list, gl_list_node_t node)
638 gl_list_node_t parent = node->parent;
640 if (node->left == NULL)
642 /* Replace node with node->right. */
643 gl_list_node_t child = node->right;
647 child->parent = parent;
648 /* Since node->left == NULL, child must be RED and of height 1,
649 hence node must have been BLACK. Recolor the child. */
650 child->color = BLACK;
656 if (parent->left == node)
657 parent->left = child;
658 else /* parent->right == node */
659 parent->right = child;
661 /* Update branch_size fields of the parent nodes. */
665 for (p = parent; p != NULL; p = p->parent)
669 if (child == NULL && node->color == BLACK)
670 rebalance_after_remove (list, child, parent);
673 else if (node->right == NULL)
675 /* It is not absolutely necessary to treat this case. But the more
676 general case below is more complicated, hence slower. */
677 /* Replace node with node->left. */
678 gl_list_node_t child = node->left;
680 child->parent = parent;
681 /* Since node->right == NULL, child must be RED and of height 1,
682 hence node must have been BLACK. Recolor the child. */
683 child->color = BLACK;
688 if (parent->left == node)
689 parent->left = child;
690 else /* parent->right == node */
691 parent->right = child;
693 /* Update branch_size fields of the parent nodes. */
697 for (p = parent; p != NULL; p = p->parent)
704 /* Replace node with the rightmost element of the node->left subtree. */
705 gl_list_node_t subst;
706 gl_list_node_t subst_parent;
707 gl_list_node_t child;
708 color_t removed_color;
710 for (subst = node->left; subst->right != NULL; )
711 subst = subst->right;
713 subst_parent = subst->parent;
717 removed_color = subst->color;
719 /* The case subst_parent == node is special: If we do nothing special,
720 we get confusion about node->left, subst->left and child->parent.
722 <==> The 'for' loop above terminated immediately.
723 <==> subst == subst_parent->left
724 [otherwise subst == subst_parent->right]
725 In this case, we would need to first set
726 child->parent = node; node->left = child;
727 and later - when we copy subst into node's position - again
728 child->parent = subst; subst->left = child;
729 Altogether a no-op. */
730 if (subst_parent != node)
733 child->parent = subst_parent;
734 subst_parent->right = child;
737 /* Update branch_size fields of the parent nodes. */
741 for (p = subst_parent; p != NULL; p = p->parent)
745 /* Copy subst into node's position.
746 (This is safer than to copy subst's value into node, keep node in
747 place, and free subst.) */
748 if (subst_parent != node)
750 subst->left = node->left;
751 subst->left->parent = subst;
753 subst->right = node->right;
754 subst->right->parent = subst;
755 subst->color = node->color;
756 subst->branch_size = node->branch_size;
757 subst->parent = parent;
760 else if (parent->left == node)
761 parent->left = subst;
762 else /* parent->right == node */
763 parent->right = subst;
765 if (removed_color == BLACK)
767 if (child != NULL && child->color == RED)
768 /* Recolor the child. */
769 child->color = BLACK;
771 /* Rebalancing starts at child's parent, that is subst_parent -
772 except when subst_parent == node. In this case, we need to use
773 its replacement, subst. */
774 rebalance_after_remove (list, child,
775 subst_parent != node ? subst_parent : subst);
780 static gl_list_node_t
781 gl_tree_nx_add_first (gl_list_t list, const void *elt)
783 /* Create new node. */
784 gl_list_node_t new_node =
785 (struct gl_list_node_impl *) malloc (sizeof (struct gl_list_node_impl));
787 if (new_node == NULL)
790 new_node->left = NULL;
791 new_node->right = NULL;
792 new_node->branch_size = 1;
793 new_node->value = elt;
795 new_node->h.hashcode =
796 (list->base.hashcode_fn != NULL
797 ? list->base.hashcode_fn (new_node->value)
798 : (size_t)(uintptr_t) new_node->value);
801 /* Add it to the tree. */
802 if (list->root == NULL)
804 new_node->color = BLACK;
805 list->root = new_node;
806 new_node->parent = NULL;
812 for (node = list->root; node->left != NULL; )
815 node->left = new_node;
816 new_node->parent = node;
818 /* Update branch_size fields of the parent nodes. */
822 for (p = node; p != NULL; p = p->parent)
826 /* Color and rebalance. */
827 rebalance_after_add (list, new_node, node);
831 /* Add node to the hash table.
832 Note that this is only possible _after_ the node has been added to the
833 tree structure, because add_to_bucket() uses node_position(). */
834 if (add_to_bucket (list, new_node) < 0)
836 gl_tree_remove_node_from_tree (list, new_node);
840 hash_resize_after_add (list);
846 static gl_list_node_t
847 gl_tree_nx_add_last (gl_list_t list, const void *elt)
849 /* Create new node. */
850 gl_list_node_t new_node =
851 (struct gl_list_node_impl *) malloc (sizeof (struct gl_list_node_impl));
853 if (new_node == NULL)
856 new_node->left = NULL;
857 new_node->right = NULL;
858 new_node->branch_size = 1;
859 new_node->value = elt;
861 new_node->h.hashcode =
862 (list->base.hashcode_fn != NULL
863 ? list->base.hashcode_fn (new_node->value)
864 : (size_t)(uintptr_t) new_node->value);
867 /* Add it to the tree. */
868 if (list->root == NULL)
870 new_node->color = BLACK;
871 list->root = new_node;
872 new_node->parent = NULL;
878 for (node = list->root; node->right != NULL; )
881 node->right = new_node;
882 new_node->parent = node;
884 /* Update branch_size fields of the parent nodes. */
888 for (p = node; p != NULL; p = p->parent)
892 /* Color and rebalance. */
893 rebalance_after_add (list, new_node, node);
897 /* Add node to the hash table.
898 Note that this is only possible _after_ the node has been added to the
899 tree structure, because add_to_bucket() uses node_position(). */
900 if (add_to_bucket (list, new_node) < 0)
902 gl_tree_remove_node_from_tree (list, new_node);
906 hash_resize_after_add (list);
912 static gl_list_node_t
913 gl_tree_nx_add_before (gl_list_t list, gl_list_node_t node, const void *elt)
915 /* Create new node. */
916 gl_list_node_t new_node =
917 (struct gl_list_node_impl *) malloc (sizeof (struct gl_list_node_impl));
919 if (new_node == NULL)
922 new_node->left = NULL;
923 new_node->right = NULL;
924 new_node->branch_size = 1;
925 new_node->value = elt;
927 new_node->h.hashcode =
928 (list->base.hashcode_fn != NULL
929 ? list->base.hashcode_fn (new_node->value)
930 : (size_t)(uintptr_t) new_node->value);
933 /* Add it to the tree. */
934 if (node->left == NULL)
935 node->left = new_node;
938 for (node = node->left; node->right != NULL; )
940 node->right = new_node;
942 new_node->parent = node;
944 /* Update branch_size fields of the parent nodes. */
948 for (p = node; p != NULL; p = p->parent)
952 /* Color and rebalance. */
953 rebalance_after_add (list, new_node, node);
956 /* Add node to the hash table.
957 Note that this is only possible _after_ the node has been added to the
958 tree structure, because add_to_bucket() uses node_position(). */
959 if (add_to_bucket (list, new_node) < 0)
961 gl_tree_remove_node_from_tree (list, new_node);
965 hash_resize_after_add (list);
971 static gl_list_node_t
972 gl_tree_nx_add_after (gl_list_t list, gl_list_node_t node, const void *elt)
974 /* Create new node. */
975 gl_list_node_t new_node =
976 (struct gl_list_node_impl *) malloc (sizeof (struct gl_list_node_impl));
978 if (new_node == NULL)
981 new_node->left = NULL;
982 new_node->right = NULL;
983 new_node->branch_size = 1;
984 new_node->value = elt;
986 new_node->h.hashcode =
987 (list->base.hashcode_fn != NULL
988 ? list->base.hashcode_fn (new_node->value)
989 : (size_t)(uintptr_t) new_node->value);
992 /* Add it to the tree. */
993 if (node->right == NULL)
994 node->right = new_node;
997 for (node = node->right; node->left != NULL; )
999 node->left = new_node;
1001 new_node->parent = node;
1003 /* Update branch_size fields of the parent nodes. */
1007 for (p = node; p != NULL; p = p->parent)
1011 /* Color and rebalance. */
1012 rebalance_after_add (list, new_node, node);
1015 /* Add node to the hash table.
1016 Note that this is only possible _after_ the node has been added to the
1017 tree structure, because add_to_bucket() uses node_position(). */
1018 if (add_to_bucket (list, new_node) < 0)
1020 gl_tree_remove_node_from_tree (list, new_node);
1024 hash_resize_after_add (list);