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. */
34 gl_list_node_t node = XMALLOC (struct gl_list_node_impl);
38 /* half1 > 0 implies count > 1, implies bh >= 1, implies
39 2^(bh-1) - 1 <= half1 <= 2^bh - 1. */
41 create_subtree_with_contents (bh - 1, half1, contents);
42 node->left->parent = node;
47 node->value = contents[half1];
51 /* half2 > 0 implies count > 1, implies bh >= 1, implies
52 2^(bh-1) - 1 <= half2 <= 2^bh - 1. */
54 create_subtree_with_contents (bh - 1, half2, contents + half1 + 1);
55 node->right->parent = node;
60 node->color = (bh == 0 ? RED : BLACK);
62 node->branch_size = count;
68 gl_tree_create (gl_list_implementation_t implementation,
69 gl_listelement_equals_fn equals_fn,
70 gl_listelement_hashcode_fn hashcode_fn,
71 bool allow_duplicates,
72 size_t count, const void **contents)
74 struct gl_list_impl *list = XMALLOC (struct gl_list_impl);
76 list->base.vtable = implementation;
77 list->base.equals_fn = equals_fn;
78 list->base.hashcode_fn = hashcode_fn;
79 list->base.allow_duplicates = allow_duplicates;
82 size_t estimate = xsum (count, count / 2); /* 1.5 * count */
85 list->table_size = next_prime (estimate);
86 list->table = XCALLOC (list->table_size, gl_hash_entry_t);
91 /* Assuming 2^bh - 1 <= count <= 2^(bh+1) - 2, we create a tree whose
92 upper bh levels are black, and only the partially present lowest
97 for (n = count + 1, bh = 0; n > 1; n = n >> 1)
101 list->root = create_subtree_with_contents (bh, count, contents);
102 list->root->parent = NULL;
105 /* Now that the tree is built, node_position() works. Now we can
106 add the nodes to the hash table. */
107 add_nodes_to_buckets (list);
116 /* Rotate left a subtree.
124 Change the tree structure, update the branch sizes.
125 The caller must update the colors and register D as child of its parent. */
126 static inline gl_list_node_t
127 rotate_left (gl_list_node_t b_node, gl_list_node_t d_node)
129 gl_list_node_t a_node = b_node->left;
130 gl_list_node_t c_node = d_node->left;
131 gl_list_node_t e_node = d_node->right;
133 b_node->right = c_node;
134 d_node->left = b_node;
136 d_node->parent = b_node->parent;
137 b_node->parent = d_node;
139 c_node->parent = b_node;
141 b_node->branch_size =
142 (a_node != NULL ? a_node->branch_size : 0)
143 + 1 + (c_node != NULL ? c_node->branch_size : 0);
144 d_node->branch_size =
145 b_node->branch_size + 1 + (e_node != NULL ? e_node->branch_size : 0);
150 /* Rotate right a subtree.
158 Change the tree structure, update the branch sizes.
159 The caller must update the colors and register B as child of its parent. */
160 static inline gl_list_node_t
161 rotate_right (gl_list_node_t b_node, gl_list_node_t d_node)
163 gl_list_node_t a_node = b_node->left;
164 gl_list_node_t c_node = b_node->right;
165 gl_list_node_t e_node = d_node->right;
167 d_node->left = c_node;
168 b_node->right = d_node;
170 b_node->parent = d_node->parent;
171 d_node->parent = b_node;
173 c_node->parent = d_node;
175 d_node->branch_size =
176 (c_node != NULL ? c_node->branch_size : 0)
177 + 1 + (e_node != NULL ? e_node->branch_size : 0);
178 b_node->branch_size =
179 (a_node != NULL ? a_node->branch_size : 0) + 1 + d_node->branch_size;
184 /* Ensure the tree is balanced, after an insertion operation.
185 Also assigns node->color.
186 parent is the given node's parent, known to be non-NULL. */
188 rebalance_after_add (gl_list_t list, gl_list_node_t node, gl_list_node_t parent)
192 /* At this point, parent = node->parent != NULL.
193 Think of node->color being RED (although node->color is not yet
195 gl_list_node_t grandparent;
196 gl_list_node_t uncle;
198 if (parent->color == BLACK)
200 /* A RED color for node is acceptable. */
205 grandparent = parent->parent;
206 /* Since parent is RED, we know that
207 grandparent is != NULL and colored BLACK. */
209 if (grandparent->left == parent)
210 uncle = grandparent->right;
211 else if (grandparent->right == parent)
212 uncle = grandparent->left;
216 if (uncle != NULL && uncle->color == RED)
218 /* Change grandparent from BLACK to RED, and
219 change parent and uncle from RED to BLACK.
220 This makes it acceptable for node to be RED. */
222 parent->color = uncle->color = BLACK;
227 /* grandparent and uncle are BLACK. parent is RED. node wants
229 In this case, recoloring is not sufficient. Need to perform
230 one or two rotations. */
231 gl_list_node_t *grandparentp;
233 if (grandparent->parent == NULL)
234 grandparentp = &list->root;
235 else if (grandparent->parent->left == grandparent)
236 grandparentp = &grandparent->parent->left;
237 else if (grandparent->parent->right == grandparent)
238 grandparentp = &grandparent->parent->right;
242 if (grandparent->left == parent)
244 if (parent->right == node)
246 /* Rotation between node and parent. */
247 grandparent->left = rotate_left (parent, node);
249 parent = grandparent->left;
251 /* grandparent and uncle are BLACK. parent and node want to be
252 RED. parent = grandparent->left. node = parent->left.
257 parent uncle --> node grandparent
263 *grandparentp = rotate_right (parent, grandparent);
264 parent->color = BLACK;
265 node->color = grandparent->color = RED;
267 else /* grandparent->right == parent */
269 if (parent->left == node)
271 /* Rotation between node and parent. */
272 grandparent->right = rotate_right (node, parent);
274 parent = grandparent->right;
276 /* grandparent and uncle are BLACK. parent and node want to be
277 RED. parent = grandparent->right. node = parent->right.
282 uncle parent --> grandparent node
288 *grandparentp = rotate_left (grandparent, parent);
289 parent->color = BLACK;
290 node->color = grandparent->color = RED;
295 /* Start again with a new (node, parent) pair. */
296 parent = node->parent;
300 /* Change node's color from RED to BLACK. This increases the
301 tree's black-height. */
308 /* Ensure the tree is balanced, after a deletion operation.
309 CHILD was a grandchild of PARENT and is now its child. Between them,
310 a black node was removed. CHILD is also black, or NULL.
311 (CHILD can also be NULL. But PARENT is non-NULL.) */
313 rebalance_after_remove (gl_list_t list, gl_list_node_t child, gl_list_node_t parent)
317 /* At this point, we reduced the black-height of the CHILD subtree by 1.
318 To make up, either look for a possibility to turn a RED to a BLACK
319 node, or try to reduce the black-height tree of CHILD's sibling
321 gl_list_node_t *parentp;
323 if (parent->parent == NULL)
324 parentp = &list->root;
325 else if (parent->parent->left == parent)
326 parentp = &parent->parent->left;
327 else if (parent->parent->right == parent)
328 parentp = &parent->parent->right;
332 if (parent->left == child)
334 gl_list_node_t sibling = parent->right;
335 /* sibling's black-height is >= 1. In particular,
344 if (sibling->color == RED)
346 /* sibling is RED, hence parent is BLACK and sibling's children
347 are non-NULL and BLACK.
352 child sibling --> parent SR
358 *parentp = rotate_left (parent, sibling);
360 sibling->color = BLACK;
362 /* Concentrate on the subtree of parent. The new sibling is
363 one of the old sibling's children, and known to be BLACK. */
364 parentp = &sibling->left;
365 sibling = parent->right;
367 /* Now we know that sibling is BLACK.
374 if (sibling->right != NULL && sibling->right->color == RED)
380 child sibling --> parent SR
386 *parentp = rotate_left (parent, sibling);
387 sibling->color = parent->color;
388 parent->color = BLACK;
389 sibling->right->color = BLACK;
392 else if (sibling->left != NULL && sibling->left->color == RED)
398 child sibling --> child SL
407 where SLL, SLR, SR are all black.
409 parent->right = rotate_right (sibling->left, sibling);
410 /* Change sibling from BLACK to RED and SL from RED to BLACK. */
411 sibling->color = RED;
412 sibling = parent->right;
413 sibling->color = BLACK;
415 /* Now do as in the previous case. */
416 *parentp = rotate_left (parent, sibling);
417 sibling->color = parent->color;
418 parent->color = BLACK;
419 sibling->right->color = BLACK;
424 if (parent->color == BLACK)
426 /* Change sibling from BLACK to RED. Then the entire
427 subtree at parent has decreased its black-height.
431 child sibling --> child sibling
434 sibling->color = RED;
440 /* Change parent from RED to BLACK, but compensate by
441 changing sibling from BLACK to RED.
445 child sibling --> child sibling
448 parent->color = BLACK;
449 sibling->color = RED;
454 else if (parent->right == child)
456 gl_list_node_t sibling = parent->left;
457 /* sibling's black-height is >= 1. In particular,
466 if (sibling->color == RED)
468 /* sibling is RED, hence parent is BLACK and sibling's children
469 are non-NULL and BLACK.
474 sibling child --> SR parent
480 *parentp = rotate_right (sibling, parent);
482 sibling->color = BLACK;
484 /* Concentrate on the subtree of parent. The new sibling is
485 one of the old sibling's children, and known to be BLACK. */
486 parentp = &sibling->right;
487 sibling = parent->left;
489 /* Now we know that sibling is BLACK.
496 if (sibling->left != NULL && sibling->left->color == RED)
502 sibling child --> SL parent
508 *parentp = rotate_right (sibling, parent);
509 sibling->color = parent->color;
510 parent->color = BLACK;
511 sibling->left->color = BLACK;
514 else if (sibling->right != NULL && sibling->right->color == RED)
520 sibling child --> SR child
529 where SL, SRL, SRR are all black.
531 parent->left = rotate_left (sibling, sibling->right);
532 /* Change sibling from BLACK to RED and SL from RED to BLACK. */
533 sibling->color = RED;
534 sibling = parent->left;
535 sibling->color = BLACK;
537 /* Now do as in the previous case. */
538 *parentp = rotate_right (sibling, parent);
539 sibling->color = parent->color;
540 parent->color = BLACK;
541 sibling->left->color = BLACK;
546 if (parent->color == BLACK)
548 /* Change sibling from BLACK to RED. Then the entire
549 subtree at parent has decreased its black-height.
553 sibling child --> sibling child
556 sibling->color = RED;
562 /* Change parent from RED to BLACK, but compensate by
563 changing sibling from BLACK to RED.
567 sibling child --> sibling child
570 parent->color = BLACK;
571 sibling->color = RED;
579 /* Start again with a new (child, parent) pair. */
580 parent = child->parent;
582 #if 0 /* Already handled. */
583 if (child != NULL && child->color == RED)
585 child->color = BLACK;
595 static gl_list_node_t
596 gl_tree_add_first (gl_list_t list, const void *elt)
598 /* Create new node. */
599 gl_list_node_t new_node = XMALLOC (struct gl_list_node_impl);
601 new_node->left = NULL;
602 new_node->right = NULL;
603 new_node->branch_size = 1;
604 new_node->value = elt;
606 new_node->h.hashcode =
607 (list->base.hashcode_fn != NULL
608 ? list->base.hashcode_fn (new_node->value)
609 : (size_t)(uintptr_t) new_node->value);
612 /* Add it to the tree. */
613 if (list->root == NULL)
615 new_node->color = BLACK;
616 list->root = new_node;
617 new_node->parent = NULL;
623 for (node = list->root; node->left != NULL; )
626 node->left = new_node;
627 new_node->parent = node;
629 /* Update branch_size fields of the parent nodes. */
633 for (p = node; p != NULL; p = p->parent)
637 /* Color and rebalance. */
638 rebalance_after_add (list, new_node, node);
642 /* Add node to the hash table.
643 Note that this is only possible _after_ the node has been added to the
644 tree structure, because add_to_bucket() uses node_position(). */
645 add_to_bucket (list, new_node);
646 hash_resize_after_add (list);
652 static gl_list_node_t
653 gl_tree_add_last (gl_list_t list, const void *elt)
655 /* Create new node. */
656 gl_list_node_t new_node = XMALLOC (struct gl_list_node_impl);
658 new_node->left = NULL;
659 new_node->right = NULL;
660 new_node->branch_size = 1;
661 new_node->value = elt;
663 new_node->h.hashcode =
664 (list->base.hashcode_fn != NULL
665 ? list->base.hashcode_fn (new_node->value)
666 : (size_t)(uintptr_t) new_node->value);
669 /* Add it to the tree. */
670 if (list->root == NULL)
672 new_node->color = BLACK;
673 list->root = new_node;
674 new_node->parent = NULL;
680 for (node = list->root; node->right != NULL; )
683 node->right = new_node;
684 new_node->parent = node;
686 /* Update branch_size fields of the parent nodes. */
690 for (p = node; p != NULL; p = p->parent)
694 /* Color and rebalance. */
695 rebalance_after_add (list, new_node, node);
699 /* Add node to the hash table.
700 Note that this is only possible _after_ the node has been added to the
701 tree structure, because add_to_bucket() uses node_position(). */
702 add_to_bucket (list, new_node);
703 hash_resize_after_add (list);
709 static gl_list_node_t
710 gl_tree_add_before (gl_list_t list, gl_list_node_t node, const void *elt)
712 /* Create new node. */
713 gl_list_node_t new_node = XMALLOC (struct gl_list_node_impl);
715 new_node->left = NULL;
716 new_node->right = NULL;
717 new_node->branch_size = 1;
718 new_node->value = elt;
720 new_node->h.hashcode =
721 (list->base.hashcode_fn != NULL
722 ? list->base.hashcode_fn (new_node->value)
723 : (size_t)(uintptr_t) new_node->value);
726 /* Add it to the tree. */
727 if (node->left == NULL)
728 node->left = new_node;
731 for (node = node->left; node->right != NULL; )
733 node->right = new_node;
735 new_node->parent = node;
737 /* Update branch_size fields of the parent nodes. */
741 for (p = node; p != NULL; p = p->parent)
745 /* Color and rebalance. */
746 rebalance_after_add (list, new_node, node);
749 /* Add node to the hash table.
750 Note that this is only possible _after_ the node has been added to the
751 tree structure, because add_to_bucket() uses node_position(). */
752 add_to_bucket (list, new_node);
753 hash_resize_after_add (list);
759 static gl_list_node_t
760 gl_tree_add_after (gl_list_t list, gl_list_node_t node, const void *elt)
762 /* Create new node. */
763 gl_list_node_t new_node = XMALLOC (struct gl_list_node_impl);
765 new_node->left = NULL;
766 new_node->right = NULL;
767 new_node->branch_size = 1;
768 new_node->value = elt;
770 new_node->h.hashcode =
771 (list->base.hashcode_fn != NULL
772 ? list->base.hashcode_fn (new_node->value)
773 : (size_t)(uintptr_t) new_node->value);
776 /* Add it to the tree. */
777 if (node->right == NULL)
778 node->right = new_node;
781 for (node = node->right; node->left != NULL; )
783 node->left = new_node;
785 new_node->parent = node;
787 /* Update branch_size fields of the parent nodes. */
791 for (p = node; p != NULL; p = p->parent)
795 /* Color and rebalance. */
796 rebalance_after_add (list, new_node, node);
799 /* Add node to the hash table.
800 Note that this is only possible _after_ the node has been added to the
801 tree structure, because add_to_bucket() uses node_position(). */
802 add_to_bucket (list, new_node);
803 hash_resize_after_add (list);
810 gl_tree_remove_node (gl_list_t list, gl_list_node_t node)
812 gl_list_node_t parent;
815 /* Remove node from the hash table.
816 Note that this is only possible _before_ the node is removed from the
817 tree structure, because remove_from_bucket() uses node_position(). */
818 remove_from_bucket (list, node);
821 parent = node->parent;
823 if (node->left == NULL)
825 /* Replace node with node->right. */
826 gl_list_node_t child = node->right;
830 child->parent = parent;
831 /* Since node->left == NULL, child must be RED and of height 1,
832 hence node must have been BLACK. Recolor the child. */
833 child->color = BLACK;
839 if (parent->left == node)
840 parent->left = child;
841 else /* parent->right == node */
842 parent->right = child;
844 /* Update branch_size fields of the parent nodes. */
848 for (p = parent; p != NULL; p = p->parent)
852 if (child == NULL && node->color == BLACK)
853 rebalance_after_remove (list, child, parent);
856 else if (node->right == NULL)
858 /* It is not absolutely necessary to treat this case. But the more
859 general case below is more complicated, hence slower. */
860 /* Replace node with node->left. */
861 gl_list_node_t child = node->left;
863 child->parent = parent;
864 /* Since node->right == NULL, child must be RED and of height 1,
865 hence node must have been BLACK. Recolor the child. */
866 child->color = BLACK;
871 if (parent->left == node)
872 parent->left = child;
873 else /* parent->right == node */
874 parent->right = child;
876 /* Update branch_size fields of the parent nodes. */
880 for (p = parent; p != NULL; p = p->parent)
887 /* Replace node with the rightmost element of the node->left subtree. */
888 gl_list_node_t subst;
889 gl_list_node_t subst_parent;
890 gl_list_node_t child;
891 color_t removed_color;
893 for (subst = node->left; subst->right != NULL; )
894 subst = subst->right;
896 subst_parent = subst->parent;
900 removed_color = subst->color;
902 /* The case subst_parent == node is special: If we do nothing special,
903 we get confusion about node->left, subst->left and child->parent.
905 <==> The 'for' loop above terminated immediately.
906 <==> subst == subst_parent->left
907 [otherwise subst == subst_parent->right]
908 In this case, we would need to first set
909 child->parent = node; node->left = child;
910 and later - when we copy subst into node's position - again
911 child->parent = subst; subst->left = child;
912 Altogether a no-op. */
913 if (subst_parent != node)
916 child->parent = subst_parent;
917 subst_parent->right = child;
920 /* Update branch_size fields of the parent nodes. */
924 for (p = subst_parent; p != NULL; p = p->parent)
928 /* Copy subst into node's position.
929 (This is safer than to copy subst's value into node, keep node in
930 place, and free subst.) */
931 if (subst_parent != node)
933 subst->left = node->left;
934 subst->left->parent = subst;
936 subst->right = node->right;
937 subst->right->parent = subst;
938 subst->color = node->color;
939 subst->branch_size = node->branch_size;
940 subst->parent = parent;
943 else if (parent->left == node)
944 parent->left = subst;
945 else /* parent->right == node */
946 parent->right = subst;
948 if (removed_color == BLACK)
950 if (child != NULL && child->color == RED)
951 /* Recolor the child. */
952 child->color = BLACK;
954 /* Rebalancing starts at child's parent, that is subst_parent -
955 except when subst_parent == node. In this case, we need to use
956 its replacement, subst. */
957 rebalance_after_remove (list, child,
958 subst_parent != node ? subst_parent : subst);