1 /* Sequential list data type implemented by a binary tree.
2 Copyright (C) 2006 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 2, or (at your option)
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, write to the Free Software Foundation,
17 Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. */
19 /* Common code of gl_rbtree_list.c and gl_rbtreehash_list.c. */
21 /* -------------------------- gl_list_t Data Type -------------------------- */
23 /* Create a subtree for count >= 1 elements.
24 Its black-height bh is passed as argument, with
25 2^bh - 1 <= count <= 2^(bh+1) - 1. bh == 0 implies count == 1.
26 Its height is h where 2^(h-1) <= count <= 2^h - 1. */
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 *) xmalloc (sizeof (struct gl_list_node_impl));
39 /* half1 > 0 implies count > 1, implies bh >= 1, implies
40 2^(bh-1) - 1 <= half1 <= 2^bh - 1. */
42 create_subtree_with_contents (bh - 1, half1, contents);
43 node->left->parent = node;
48 node->value = contents[half1];
52 /* half2 > 0 implies count > 1, implies bh >= 1, implies
53 2^(bh-1) - 1 <= half2 <= 2^bh - 1. */
55 create_subtree_with_contents (bh - 1, half2, contents + half1 + 1);
56 node->right->parent = node;
61 node->color = (bh == 0 ? RED : BLACK);
63 node->branch_size = count;
69 gl_tree_create (gl_list_implementation_t implementation,
70 gl_listelement_equals_fn equals_fn,
71 gl_listelement_hashcode_fn hashcode_fn,
72 bool allow_duplicates,
73 size_t count, const void **contents)
75 struct gl_list_impl *list =
76 (struct gl_list_impl *) xmalloc (sizeof (struct gl_list_impl));
78 list->base.vtable = implementation;
79 list->base.equals_fn = equals_fn;
80 list->base.hashcode_fn = hashcode_fn;
81 list->base.allow_duplicates = allow_duplicates;
84 size_t estimate = xsum (count, count / 2); /* 1.5 * count */
87 list->table_size = next_prime (estimate);
89 (gl_hash_entry_t *) xzalloc (list->table_size * sizeof (gl_hash_entry_t));
94 /* Assuming 2^bh - 1 <= count <= 2^(bh+1) - 2, we create a tree whose
95 upper bh levels are black, and only the partially present lowest
100 for (n = count + 1, bh = 0; n > 1; n = n >> 1)
104 list->root = create_subtree_with_contents (bh, count, contents);
105 list->root->parent = NULL;
108 /* Now that the tree is built, node_position() works. Now we can
109 add the nodes to the hash table. */
110 add_nodes_to_buckets (list);
119 /* Rotate left a subtree.
127 Change the tree structure, update the branch sizes.
128 The caller must update the colors and register D as child of its parent. */
129 static inline gl_list_node_t
130 rotate_left (gl_list_node_t b_node, gl_list_node_t d_node)
132 gl_list_node_t a_node = b_node->left;
133 gl_list_node_t c_node = d_node->left;
134 gl_list_node_t e_node = d_node->right;
136 b_node->right = c_node;
137 d_node->left = b_node;
139 d_node->parent = b_node->parent;
140 b_node->parent = d_node;
142 c_node->parent = b_node;
144 b_node->branch_size =
145 (a_node != NULL ? a_node->branch_size : 0)
146 + 1 + (c_node != NULL ? c_node->branch_size : 0);
147 d_node->branch_size =
148 b_node->branch_size + 1 + (e_node != NULL ? e_node->branch_size : 0);
153 /* Rotate right a subtree.
161 Change the tree structure, update the branch sizes.
162 The caller must update the colors and register B as child of its parent. */
163 static inline gl_list_node_t
164 rotate_right (gl_list_node_t b_node, gl_list_node_t d_node)
166 gl_list_node_t a_node = b_node->left;
167 gl_list_node_t c_node = b_node->right;
168 gl_list_node_t e_node = d_node->right;
170 d_node->left = c_node;
171 b_node->right = d_node;
173 b_node->parent = d_node->parent;
174 d_node->parent = b_node;
176 c_node->parent = d_node;
178 d_node->branch_size =
179 (c_node != NULL ? c_node->branch_size : 0)
180 + 1 + (e_node != NULL ? e_node->branch_size : 0);
181 b_node->branch_size =
182 (a_node != NULL ? a_node->branch_size : 0) + 1 + d_node->branch_size;
187 /* Ensure the tree is balanced, after an insertion operation.
188 Also assigns node->color.
189 parent is the given node's parent, known to be non-NULL. */
191 rebalance_after_add (gl_list_t list, gl_list_node_t node, gl_list_node_t parent)
195 /* At this point, parent = node->parent != NULL.
196 Think of node->color being RED (although node->color is not yet
198 gl_list_node_t grandparent;
199 gl_list_node_t uncle;
201 if (parent->color == BLACK)
203 /* A RED color for node is acceptable. */
208 grandparent = parent->parent;
209 /* Since parent is RED, we know that
210 grandparent is != NULL and colored BLACK. */
212 if (grandparent->left == parent)
213 uncle = grandparent->right;
214 else if (grandparent->right == parent)
215 uncle = grandparent->left;
219 if (uncle != NULL && uncle->color == RED)
221 /* Change grandparent from BLACK to RED, and
222 change parent and uncle from RED to BLACK.
223 This makes it acceptable for node to be RED. */
225 parent->color = uncle->color = BLACK;
230 /* grandparent and uncle are BLACK. parent is RED. node wants
232 In this case, recoloring is not sufficient. Need to perform
233 one or two rotations. */
234 gl_list_node_t *grandparentp;
236 if (grandparent->parent == NULL)
237 grandparentp = &list->root;
238 else if (grandparent->parent->left == grandparent)
239 grandparentp = &grandparent->parent->left;
240 else if (grandparent->parent->right == grandparent)
241 grandparentp = &grandparent->parent->right;
245 if (grandparent->left == parent)
247 if (parent->right == node)
249 /* Rotation between node and parent. */
250 grandparent->left = rotate_left (parent, node);
252 parent = grandparent->left;
254 /* grandparent and uncle are BLACK. parent and node want to be
255 RED. parent = grandparent->left. node = parent->left.
260 parent uncle --> node grandparent
266 *grandparentp = rotate_right (parent, grandparent);
267 parent->color = BLACK;
268 node->color = grandparent->color = RED;
270 else /* grandparent->right == parent */
272 if (parent->left == node)
274 /* Rotation between node and parent. */
275 grandparent->right = rotate_right (node, parent);
277 parent = grandparent->right;
279 /* grandparent and uncle are BLACK. parent and node want to be
280 RED. parent = grandparent->right. node = parent->right.
285 uncle parent --> grandparent node
291 *grandparentp = rotate_left (grandparent, parent);
292 parent->color = BLACK;
293 node->color = grandparent->color = RED;
298 /* Start again with a new (node, parent) pair. */
299 parent = node->parent;
303 /* Change node's color from RED to BLACK. This increases the
304 tree's black-height. */
311 /* Ensure the tree is balanced, after a deletion operation.
312 CHILD was a grandchild of PARENT and is now its child. Between them,
313 a black node was removed. CHILD is also black, or NULL.
314 (CHILD can also be NULL. But PARENT is non-NULL.) */
316 rebalance_after_remove (gl_list_t list, gl_list_node_t child, gl_list_node_t parent)
320 /* At this point, we reduced the black-height of the CHILD subtree by 1.
321 To make up, either look for a possibility to turn a RED to a BLACK
322 node, or try to reduce the black-height tree of CHILD's sibling
324 gl_list_node_t *parentp;
326 if (parent->parent == NULL)
327 parentp = &list->root;
328 else if (parent->parent->left == parent)
329 parentp = &parent->parent->left;
330 else if (parent->parent->right == parent)
331 parentp = &parent->parent->right;
335 if (parent->left == child)
337 gl_list_node_t sibling = parent->right;
338 /* sibling's black-height is >= 1. In particular,
347 if (sibling->color == RED)
349 /* sibling is RED, hence parent is BLACK and sibling's children
350 are non-NULL and BLACK.
355 child sibling --> parent SR
361 *parentp = rotate_left (parent, sibling);
363 sibling->color = BLACK;
365 /* Concentrate on the subtree of parent. The new sibling is
366 one of the old sibling's children, and known to be BLACK. */
367 parentp = &sibling->left;
368 sibling = parent->right;
370 /* Now we know that sibling is BLACK.
377 if (sibling->right != NULL && sibling->right->color == RED)
383 child sibling --> parent SR
389 *parentp = rotate_left (parent, sibling);
390 sibling->color = parent->color;
391 parent->color = BLACK;
392 sibling->right->color = BLACK;
395 else if (sibling->left != NULL && sibling->left->color == RED)
401 child sibling --> child SL
410 where SLL, SLR, SR are all black.
412 parent->right = rotate_right (sibling->left, sibling);
413 /* Change sibling from BLACK to RED and SL from RED to BLACK. */
414 sibling->color = RED;
415 sibling = parent->right;
416 sibling->color = BLACK;
418 /* Now do as in the previous case. */
419 *parentp = rotate_left (parent, sibling);
420 sibling->color = parent->color;
421 parent->color = BLACK;
422 sibling->right->color = BLACK;
427 if (parent->color == BLACK)
429 /* Change sibling from BLACK to RED. Then the entire
430 subtree at parent has decreased its black-height.
434 child sibling --> child sibling
437 sibling->color = RED;
443 /* Change parent from RED to BLACK, but compensate by
444 changing sibling from BLACK to RED.
448 child sibling --> child sibling
451 parent->color = BLACK;
452 sibling->color = RED;
457 else if (parent->right == child)
459 gl_list_node_t sibling = parent->left;
460 /* sibling's black-height is >= 1. In particular,
469 if (sibling->color == RED)
471 /* sibling is RED, hence parent is BLACK and sibling's children
472 are non-NULL and BLACK.
477 sibling child --> SR parent
483 *parentp = rotate_right (sibling, parent);
485 sibling->color = BLACK;
487 /* Concentrate on the subtree of parent. The new sibling is
488 one of the old sibling's children, and known to be BLACK. */
489 parentp = &sibling->right;
490 sibling = parent->left;
492 /* Now we know that sibling is BLACK.
499 if (sibling->left != NULL && sibling->left->color == RED)
505 sibling child --> SL parent
511 *parentp = rotate_right (sibling, parent);
512 sibling->color = parent->color;
513 parent->color = BLACK;
514 sibling->left->color = BLACK;
517 else if (sibling->right != NULL && sibling->right->color == RED)
523 sibling child --> SR child
532 where SL, SRL, SRR are all black.
534 parent->left = rotate_left (sibling, sibling->right);
535 /* Change sibling from BLACK to RED and SL from RED to BLACK. */
536 sibling->color = RED;
537 sibling = parent->left;
538 sibling->color = BLACK;
540 /* Now do as in the previous case. */
541 *parentp = rotate_right (sibling, parent);
542 sibling->color = parent->color;
543 parent->color = BLACK;
544 sibling->left->color = BLACK;
549 if (parent->color == BLACK)
551 /* Change sibling from BLACK to RED. Then the entire
552 subtree at parent has decreased its black-height.
556 sibling child --> sibling child
559 sibling->color = RED;
565 /* Change parent from RED to BLACK, but compensate by
566 changing sibling from BLACK to RED.
570 sibling child --> sibling child
573 parent->color = BLACK;
574 sibling->color = RED;
582 /* Start again with a new (child, parent) pair. */
583 parent = child->parent;
585 #if 0 /* Already handled. */
586 if (child != NULL && child->color == RED)
588 child->color = BLACK;
598 static gl_list_node_t
599 gl_tree_add_first (gl_list_t list, const void *elt)
601 /* Create new node. */
602 gl_list_node_t new_node =
603 (struct gl_list_node_impl *) xmalloc (sizeof (struct gl_list_node_impl));
605 new_node->left = NULL;
606 new_node->right = NULL;
607 new_node->branch_size = 1;
608 new_node->value = elt;
610 new_node->h.hashcode =
611 (list->base.hashcode_fn != NULL
612 ? list->base.hashcode_fn (new_node->value)
613 : (size_t)(uintptr_t) new_node->value);
616 /* Add it to the tree. */
617 if (list->root == NULL)
619 new_node->color = BLACK;
620 list->root = new_node;
621 new_node->parent = NULL;
627 for (node = list->root; node->left != NULL; )
630 node->left = new_node;
631 new_node->parent = node;
633 /* Update branch_size fields of the parent nodes. */
637 for (p = node; p != NULL; p = p->parent)
641 /* Color and rebalance. */
642 rebalance_after_add (list, new_node, node);
646 /* Add node to the hash table.
647 Note that this is only possible _after_ the node has been added to the
648 tree structure, because add_to_bucket() uses node_position(). */
649 add_to_bucket (list, new_node);
650 hash_resize_after_add (list);
656 static gl_list_node_t
657 gl_tree_add_last (gl_list_t list, const void *elt)
659 /* Create new node. */
660 gl_list_node_t new_node =
661 (struct gl_list_node_impl *) xmalloc (sizeof (struct gl_list_node_impl));
663 new_node->left = NULL;
664 new_node->right = NULL;
665 new_node->branch_size = 1;
666 new_node->value = elt;
668 new_node->h.hashcode =
669 (list->base.hashcode_fn != NULL
670 ? list->base.hashcode_fn (new_node->value)
671 : (size_t)(uintptr_t) new_node->value);
674 /* Add it to the tree. */
675 if (list->root == NULL)
677 new_node->color = BLACK;
678 list->root = new_node;
679 new_node->parent = NULL;
685 for (node = list->root; node->right != NULL; )
688 node->right = new_node;
689 new_node->parent = node;
691 /* Update branch_size fields of the parent nodes. */
695 for (p = node; p != NULL; p = p->parent)
699 /* Color and rebalance. */
700 rebalance_after_add (list, new_node, node);
704 /* Add node to the hash table.
705 Note that this is only possible _after_ the node has been added to the
706 tree structure, because add_to_bucket() uses node_position(). */
707 add_to_bucket (list, new_node);
708 hash_resize_after_add (list);
714 static gl_list_node_t
715 gl_tree_add_before (gl_list_t list, gl_list_node_t node, const void *elt)
717 /* Create new node. */
718 gl_list_node_t new_node =
719 (struct gl_list_node_impl *) xmalloc (sizeof (struct gl_list_node_impl));
721 new_node->left = NULL;
722 new_node->right = NULL;
723 new_node->branch_size = 1;
724 new_node->value = elt;
726 new_node->h.hashcode =
727 (list->base.hashcode_fn != NULL
728 ? list->base.hashcode_fn (new_node->value)
729 : (size_t)(uintptr_t) new_node->value);
732 /* Add it to the tree. */
733 if (node->left == NULL)
734 node->left = new_node;
737 for (node = node->left; node->right != NULL; )
739 node->right = new_node;
741 new_node->parent = node;
743 /* Update branch_size fields of the parent nodes. */
747 for (p = node; p != NULL; p = p->parent)
751 /* Color and rebalance. */
752 rebalance_after_add (list, new_node, node);
755 /* Add node to the hash table.
756 Note that this is only possible _after_ the node has been added to the
757 tree structure, because add_to_bucket() uses node_position(). */
758 add_to_bucket (list, new_node);
759 hash_resize_after_add (list);
765 static gl_list_node_t
766 gl_tree_add_after (gl_list_t list, gl_list_node_t node, const void *elt)
768 /* Create new node. */
769 gl_list_node_t new_node =
770 (struct gl_list_node_impl *) xmalloc (sizeof (struct gl_list_node_impl));
772 new_node->left = NULL;
773 new_node->right = NULL;
774 new_node->branch_size = 1;
775 new_node->value = elt;
777 new_node->h.hashcode =
778 (list->base.hashcode_fn != NULL
779 ? list->base.hashcode_fn (new_node->value)
780 : (size_t)(uintptr_t) new_node->value);
783 /* Add it to the tree. */
784 if (node->right == NULL)
785 node->right = new_node;
788 for (node = node->right; node->left != NULL; )
790 node->left = new_node;
792 new_node->parent = node;
794 /* Update branch_size fields of the parent nodes. */
798 for (p = node; p != NULL; p = p->parent)
802 /* Color and rebalance. */
803 rebalance_after_add (list, new_node, node);
806 /* Add node to the hash table.
807 Note that this is only possible _after_ the node has been added to the
808 tree structure, because add_to_bucket() uses node_position(). */
809 add_to_bucket (list, new_node);
810 hash_resize_after_add (list);
817 gl_tree_remove_node (gl_list_t list, gl_list_node_t node)
819 gl_list_node_t parent;
822 /* Remove node from the hash table.
823 Note that this is only possible _before_ the node is removed from the
824 tree structure, because remove_from_bucket() uses node_position(). */
825 remove_from_bucket (list, node);
828 parent = node->parent;
830 if (node->left == NULL)
832 /* Replace node with node->right. */
833 gl_list_node_t child = node->right;
837 child->parent = parent;
838 /* Since node->left == NULL, child must be RED and of height 1,
839 hence node must have been BLACK. Recolor the child. */
840 child->color = BLACK;
846 if (parent->left == node)
847 parent->left = child;
848 else /* parent->right == node */
849 parent->right = child;
851 /* Update branch_size fields of the parent nodes. */
855 for (p = parent; p != NULL; p = p->parent)
859 if (child == NULL && node->color == BLACK)
860 rebalance_after_remove (list, child, parent);
863 else if (node->right == NULL)
865 /* It is not absolutely necessary to treat this case. But the more
866 general case below is more complicated, hence slower. */
867 /* Replace node with node->left. */
868 gl_list_node_t child = node->left;
870 child->parent = parent;
871 /* Since node->right == NULL, child must be RED and of height 1,
872 hence node must have been BLACK. Recolor the child. */
873 child->color = BLACK;
878 if (parent->left == node)
879 parent->left = child;
880 else /* parent->right == node */
881 parent->right = child;
883 /* Update branch_size fields of the parent nodes. */
887 for (p = parent; p != NULL; p = p->parent)
894 /* Replace node with the rightmost element of the node->left subtree. */
895 gl_list_node_t subst;
896 gl_list_node_t subst_parent;
897 gl_list_node_t child;
898 color_t removed_color;
900 for (subst = node->left; subst->right != NULL; )
901 subst = subst->right;
903 subst_parent = subst->parent;
907 removed_color = subst->color;
909 /* The case subst_parent == node is special: If we do nothing special,
910 we get confusion about node->left, subst->left and child->parent.
912 <==> The 'for' loop above terminated immediately.
913 <==> subst == subst_parent->left
914 [otherwise subst == subst_parent->right]
915 In this case, we would need to first set
916 child->parent = node; node->left = child;
917 and later - when we copy subst into node's position - again
918 child->parent = subst; subst->left = child;
919 Altogether a no-op. */
920 if (subst_parent != node)
923 child->parent = subst_parent;
924 subst_parent->right = child;
927 /* Update branch_size fields of the parent nodes. */
931 for (p = subst_parent; p != NULL; p = p->parent)
935 /* Copy subst into node's position.
936 (This is safer than to copy subst's value into node, keep node in
937 place, and free subst.) */
938 if (subst_parent != node)
940 subst->left = node->left;
941 subst->left->parent = subst;
943 subst->right = node->right;
944 subst->right->parent = subst;
945 subst->color = node->color;
946 subst->branch_size = node->branch_size;
947 subst->parent = parent;
950 else if (parent->left == node)
951 parent->left = subst;
952 else /* parent->right == node */
953 parent->right = subst;
955 if (removed_color == BLACK)
957 if (child != NULL && child->color == RED)
958 /* Recolor the child. */
959 child->color = BLACK;
961 /* Rebalancing starts at child's parent, that is subst_parent -
962 except when subst_parent == node. In this case, we need to use
963 its replacement, subst. */
964 rebalance_after_remove (list, child,
965 subst_parent != node ? subst_parent : subst);