1 /* Sequential list data type implemented by a binary tree.
2 Copyright (C) 2006-2007, 2009-2021 Free Software Foundation, Inc.
3 Written by Bruno Haible <bruno@clisp.org>, 2006.
4
5 This file is free software: you can redistribute it and/or modify
6 it under the terms of the GNU Lesser General Public License as
7 published by the Free Software Foundation; either version 2.1 of the
8 License, or (at your option) any later version.
9
10 This file 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 Lesser General Public License for more details.
14
15 You should have received a copy of the GNU Lesser General Public License
16 along with this program. If not, see <https://www.gnu.org/licenses/>. */
17
18 /* Common code of gl_rbtree_list.c and gl_rbtreehash_list.c. */
19
20 /* -------------------------- gl_list_t Data Type -------------------------- */
21
22 /* Creates 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. */
27 static gl_list_node_t
28 create_subtree_with_contents (unsigned int bh,
29 size_t count, const void **contents)
30 {
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 =
35 (struct gl_list_node_impl *) malloc (sizeof (struct gl_list_node_impl));
36 if (node == NULL)
37 return NULL;
38
39 if (half1 > 0)
40 {
41 /* half1 > 0 implies count > 1, implies bh >= 1, implies
42 2^(bh-1) - 1 <= half1 <= 2^bh - 1. */
43 node->left =
44 create_subtree_with_contents (bh - 1, half1, contents);
45 if (node->left == NULL)
46 goto fail1;
47 node->left->parent = node;
48 }
49 else
50 node->left = NULL;
51
52 node->value = contents[half1];
53
54 if (half2 > 0)
55 {
56 /* half2 > 0 implies count > 1, implies bh >= 1, implies
57 2^(bh-1) - 1 <= half2 <= 2^bh - 1. */
58 node->right =
59 create_subtree_with_contents (bh - 1, half2, contents + half1 + 1);
60 if (node->right == NULL)
61 goto fail2;
62 node->right->parent = node;
63 }
64 else
65 node->right = NULL;
66
67 node->color = (bh == 0 ? RED : BLACK);
68
69 node->branch_size = count;
70
71 return node;
72
73 fail2:
74 if (node->left != NULL)
75 free_subtree (node->left);
76 fail1:
77 free (node);
78 return NULL;
79 }
80
81 static gl_list_t
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)
88 {
89 struct gl_list_impl *list =
90 (struct gl_list_impl *) malloc (sizeof (struct gl_list_impl));
91
92 if (list == NULL)
93 return NULL;
94
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;
100 #if WITH_HASHTABLE
101 {
102 size_t estimate = xsum (count, count / 2); /* 1.5 * count */
103 if (estimate < 10)
104 estimate = 10;
105 list->table_size = next_prime (estimate);
106 if (size_overflow_p (xtimes (list->table_size, sizeof (gl_hash_entry_t))))
107 goto fail1;
108 list->table =
109 (gl_hash_entry_t *) calloc (list->table_size, sizeof (gl_hash_entry_t));
110 if (list->table == NULL)
111 goto fail1;
112 }
113 #endif
114 if (count > 0)
115 {
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
118 level is red. */
119 unsigned int bh;
120 {
121 size_t n;
122 for (n = count + 1, bh = 0; n > 1; n = n >> 1)
123 bh++;
124 }
125
126 list->root = create_subtree_with_contents (bh, count, contents);
127 if (list->root == NULL)
128 goto fail2;
129 list->root->parent = NULL;
130
131 #if WITH_HASHTABLE
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)
135 goto fail3;
136 #endif
137 }
138 else
139 list->root = NULL;
140
141 return list;
142
143 #if WITH_HASHTABLE
144 fail3:
145 free_subtree (list->root);
146 #endif
147 fail2:
148 #if WITH_HASHTABLE
149 free (list->table);
150 fail1:
151 #endif
152 free (list);
153 return NULL;
154 }
155
156 /* Rotates left a subtree.
157
158 B D
159 / \ / \
160 A D --> B E
161 / \ / \
162 C E A C
163
164 Changes the tree structure, updates the branch sizes.
165 The caller must update the colors and register D as child of its parent. */
166 static gl_list_node_t
167 rotate_left (gl_list_node_t b_node, gl_list_node_t d_node)
168 {
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;
172
173 b_node->right = c_node;
174 d_node->left = b_node;
175
176 d_node->parent = b_node->parent;
177 b_node->parent = d_node;
178 if (c_node != NULL)
179 c_node->parent = b_node;
180
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);
186
187 return d_node;
188 }
189
190 /* Rotates right a subtree.
191
192 D B
193 / \ / \
194 B E --> A D
195 / \ / \
196 A C C E
197
198 Changes the tree structure, updates the branch sizes.
199 The caller must update the colors and register B as child of its parent. */
200 static gl_list_node_t
201 rotate_right (gl_list_node_t b_node, gl_list_node_t d_node)
202 {
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;
206
207 d_node->left = c_node;
208 b_node->right = d_node;
209
210 b_node->parent = d_node->parent;
211 d_node->parent = b_node;
212 if (c_node != NULL)
213 c_node->parent = d_node;
214
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;
220
221 return b_node;
222 }
223
224 /* Ensures 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. */
227 static void
228 rebalance_after_add (gl_list_t list, gl_list_node_t node, gl_list_node_t parent)
229 {
230 for (;;)
231 {
232 /* At this point, parent = node->parent != NULL.
233 Think of node->color being RED (although node->color is not yet
234 assigned.) */
235 gl_list_node_t grandparent;
236 gl_list_node_t uncle;
237
238 if (parent->color == BLACK)
239 {
240 /* A RED color for node is acceptable. */
241 node->color = RED;
242 return;
243 }
244
245 grandparent = parent->parent;
246 /* Since parent is RED, we know that
247 grandparent is != NULL and colored BLACK. */
248
249 if (grandparent->left == parent)
250 uncle = grandparent->right;
251 else if (grandparent->right == parent)
252 uncle = grandparent->left;
253 else
254 abort ();
255
256 if (uncle != NULL && uncle->color == RED)
257 {
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. */
261 node->color = RED;
262 parent->color = uncle->color = BLACK;
263 node = grandparent;
264 }
265 else
266 {
267 /* grandparent and uncle are BLACK. parent is RED. node wants
268 to be RED too.
269 In this case, recoloring is not sufficient. Need to perform
270 one or two rotations. */
271 gl_list_node_t *grandparentp;
272
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;
279 else
280 abort ();
281
282 if (grandparent->left == parent)
283 {
284 if (parent->right == node)
285 {
286 /* Rotation between node and parent. */
287 grandparent->left = rotate_left (parent, node);
288 node = parent;
289 parent = grandparent->left;
290 }
291 /* grandparent and uncle are BLACK. parent and node want to be
292 RED. parent = grandparent->left. node = parent->left.
293
294 grandparent parent
295 bh+1 bh+1
296 / \ / \
297 parent uncle --> node grandparent
298 bh bh bh bh
299 / \ / \
300 node C C uncle
301 bh bh bh bh
302 */
303 *grandparentp = rotate_right (parent, grandparent);
304 parent->color = BLACK;
305 node->color = grandparent->color = RED;
306 }
307 else /* grandparent->right == parent */
308 {
309 if (parent->left == node)
310 {
311 /* Rotation between node and parent. */
312 grandparent->right = rotate_right (node, parent);
313 node = parent;
314 parent = grandparent->right;
315 }
316 /* grandparent and uncle are BLACK. parent and node want to be
317 RED. parent = grandparent->right. node = parent->right.
318
319 grandparent parent
320 bh+1 bh+1
321 / \ / \
322 uncle parent --> grandparent node
323 bh bh bh bh
324 / \ / \
325 C node uncle C
326 bh bh bh bh
327 */
328 *grandparentp = rotate_left (grandparent, parent);
329 parent->color = BLACK;
330 node->color = grandparent->color = RED;
331 }
332 return;
333 }
334
335 /* Start again with a new (node, parent) pair. */
336 parent = node->parent;
337
338 if (parent == NULL)
339 {
340 /* Change node's color from RED to BLACK. This increases the
341 tree's black-height. */
342 node->color = BLACK;
343 return;
344 }
345 }
346 }
347
348 /* Ensures 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.) */
352 static void
353 rebalance_after_remove (gl_list_t list, gl_list_node_t child, gl_list_node_t parent)
354 {
355 for (;;)
356 {
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
360 subtree as well. */
361 gl_list_node_t *parentp;
362
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;
369 else
370 abort ();
371
372 if (parent->left == child)
373 {
374 gl_list_node_t sibling = parent->right;
375 /* sibling's black-height is >= 1. In particular,
376 sibling != NULL.
377
378 parent
379 / \
380 child sibling
381 bh bh+1
382 */
383
384 if (sibling->color == RED)
385 {
386 /* sibling is RED, hence parent is BLACK and sibling's children
387 are non-NULL and BLACK.
388
389 parent sibling
390 bh+2 bh+2
391 / \ / \
392 child sibling --> parent SR
393 bh bh+1 bh+1 bh+1
394 / \ / \
395 SL SR child SL
396 bh+1 bh+1 bh bh+1
397 */
398 *parentp = rotate_left (parent, sibling);
399 parent->color = RED;
400 sibling->color = BLACK;
401
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;
406 }
407 /* Now we know that sibling is BLACK.
408
409 parent
410 / \
411 child sibling
412 bh bh+1
413 */
414 if (sibling->right != NULL && sibling->right->color == RED)
415 {
416 /*
417 parent sibling
418 bh+1|bh+2 bh+1|bh+2
419 / \ / \
420 child sibling --> parent SR
421 bh bh+1 bh+1 bh+1
422 / \ / \
423 SL SR child SL
424 bh bh bh bh
425 */
426 *parentp = rotate_left (parent, sibling);
427 sibling->color = parent->color;
428 parent->color = BLACK;
429 sibling->right->color = BLACK;
430 return;
431 }
432 else if (sibling->left != NULL && sibling->left->color == RED)
433 {
434 /*
435 parent parent
436 bh+1|bh+2 bh+1|bh+2
437 / \ / \
438 child sibling --> child SL
439 bh bh+1 bh bh+1
440 / \ / \
441 SL SR SLL sibling
442 bh bh bh bh
443 / \ / \
444 SLL SLR SLR SR
445 bh bh bh bh
446
447 where SLL, SLR, SR are all black.
448 */
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;
454
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;
460 return;
461 }
462 else
463 {
464 if (parent->color == BLACK)
465 {
466 /* Change sibling from BLACK to RED. Then the entire
467 subtree at parent has decreased its black-height.
468 parent parent
469 bh+2 bh+1
470 / \ / \
471 child sibling --> child sibling
472 bh bh+1 bh bh
473 */
474 sibling->color = RED;
475
476 child = parent;
477 }
478 else
479 {
480 /* Change parent from RED to BLACK, but compensate by
481 changing sibling from BLACK to RED.
482 parent parent
483 bh+1 bh+1
484 / \ / \
485 child sibling --> child sibling
486 bh bh+1 bh bh
487 */
488 parent->color = BLACK;
489 sibling->color = RED;
490 return;
491 }
492 }
493 }
494 else if (parent->right == child)
495 {
496 gl_list_node_t sibling = parent->left;
497 /* sibling's black-height is >= 1. In particular,
498 sibling != NULL.
499
500 parent
501 / \
502 sibling child
503 bh+1 bh
504 */
505
506 if (sibling->color == RED)
507 {
508 /* sibling is RED, hence parent is BLACK and sibling's children
509 are non-NULL and BLACK.
510
511 parent sibling
512 bh+2 bh+2
513 / \ / \
514 sibling child --> SR parent
515 bh+1 ch bh+1 bh+1
516 / \ / \
517 SL SR SL child
518 bh+1 bh+1 bh+1 bh
519 */
520 *parentp = rotate_right (sibling, parent);
521 parent->color = RED;
522 sibling->color = BLACK;
523
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;
528 }
529 /* Now we know that sibling is BLACK.
530
531 parent
532 / \
533 sibling child
534 bh+1 bh
535 */
536 if (sibling->left != NULL && sibling->left->color == RED)
537 {
538 /*
539 parent sibling
540 bh+1|bh+2 bh+1|bh+2
541 / \ / \
542 sibling child --> SL parent
543 bh+1 bh bh+1 bh+1
544 / \ / \
545 SL SR SR child
546 bh bh bh bh
547 */
548 *parentp = rotate_right (sibling, parent);
549 sibling->color = parent->color;
550 parent->color = BLACK;
551 sibling->left->color = BLACK;
552 return;
553 }
554 else if (sibling->right != NULL && sibling->right->color == RED)
555 {
556 /*
557 parent parent
558 bh+1|bh+2 bh+1|bh+2
559 / \ / \
560 sibling child --> SR child
561 bh+1 bh bh+1 bh
562 / \ / \
563 SL SR sibling SRR
564 bh bh bh bh
565 / \ / \
566 SRL SRR SL SRL
567 bh bh bh bh
568
569 where SL, SRL, SRR are all black.
570 */
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;
576
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;
582 return;
583 }
584 else
585 {
586 if (parent->color == BLACK)
587 {
588 /* Change sibling from BLACK to RED. Then the entire
589 subtree at parent has decreased its black-height.
590 parent parent
591 bh+2 bh+1
592 / \ / \
593 sibling child --> sibling child
594 bh+1 bh bh bh
595 */
596 sibling->color = RED;
597
598 child = parent;
599 }
600 else
601 {
602 /* Change parent from RED to BLACK, but compensate by
603 changing sibling from BLACK to RED.
604 parent parent
605 bh+1 bh+1
606 / \ / \
607 sibling child --> sibling child
608 bh+1 bh bh bh
609 */
610 parent->color = BLACK;
611 sibling->color = RED;
612 return;
613 }
614 }
615 }
616 else
617 abort ();
618
619 /* Start again with a new (child, parent) pair. */
620 parent = child->parent;
621
622 #if 0 /* Already handled. */
623 if (child != NULL && child->color == RED)
624 {
625 child->color = BLACK;
626 return;
627 }
628 #endif
629
630 if (parent == NULL)
631 return;
632 }
633 }
634
635 static void
636 gl_tree_remove_node_from_tree (gl_list_t list, gl_list_node_t node)
637 {
638 gl_list_node_t parent = node->parent;
639
640 if (node->left == NULL)
641 {
642 /* Replace node with node->right. */
643 gl_list_node_t child = node->right;
644
645 if (child != NULL)
646 {
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;
651 }
652 if (parent == NULL)
653 list->root = child;
654 else
655 {
656 if (parent->left == node)
657 parent->left = child;
658 else /* parent->right == node */
659 parent->right = child;
660
661 /* Update branch_size fields of the parent nodes. */
662 {
663 gl_list_node_t p;
664
665 for (p = parent; p != NULL; p = p->parent)
666 p->branch_size--;
667 }
668
669 if (child == NULL && node->color == BLACK)
670 rebalance_after_remove (list, child, parent);
671 }
672 }
673 else if (node->right == NULL)
674 {
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;
679
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;
684 if (parent == NULL)
685 list->root = child;
686 else
687 {
688 if (parent->left == node)
689 parent->left = child;
690 else /* parent->right == node */
691 parent->right = child;
692
693 /* Update branch_size fields of the parent nodes. */
694 {
695 gl_list_node_t p;
696
697 for (p = parent; p != NULL; p = p->parent)
698 p->branch_size--;
699 }
700 }
701 }
702 else
703 {
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;
709
710 for (subst = node->left; subst->right != NULL; )
711 subst = subst->right;
712
713 subst_parent = subst->parent;
714
715 child = subst->left;
716
717 removed_color = subst->color;
718
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.
721 subst_parent == node
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)
731 {
732 if (child != NULL)
733 child->parent = subst_parent;
734 subst_parent->right = child;
735 }
736
737 /* Update branch_size fields of the parent nodes. */
738 {
739 gl_list_node_t p;
740
741 for (p = subst_parent; p != NULL; p = p->parent)
742 p->branch_size--;
743 }
744
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)
749 {
750 subst->left = node->left;
751 subst->left->parent = subst;
752 }
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;
758 if (parent == NULL)
759 list->root = subst;
760 else if (parent->left == node)
761 parent->left = subst;
762 else /* parent->right == node */
763 parent->right = subst;
764
765 if (removed_color == BLACK)
766 {
767 if (child != NULL && child->color == RED)
768 /* Recolor the child. */
769 child->color = BLACK;
770 else
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);
776 }
777 }
778 }
779
780 static gl_list_node_t
781 gl_tree_nx_add_first (gl_list_t list, const void *elt)
782 {
783 /* Create new node. */
784 gl_list_node_t new_node =
785 (struct gl_list_node_impl *) malloc (sizeof (struct gl_list_node_impl));
786
787 if (new_node == NULL)
788 return NULL;
789
790 new_node->left = NULL;
791 new_node->right = NULL;
792 new_node->branch_size = 1;
793 new_node->value = elt;
794 #if WITH_HASHTABLE
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);
799 #endif
800
801 /* Add it to the tree. */
802 if (list->root == NULL)
803 {
804 new_node->color = BLACK;
805 list->root = new_node;
806 new_node->parent = NULL;
807 }
808 else
809 {
810 gl_list_node_t node;
811
812 for (node = list->root; node->left != NULL; )
813 node = node->left;
814
815 node->left = new_node;
816 new_node->parent = node;
817
818 /* Update branch_size fields of the parent nodes. */
819 {
820 gl_list_node_t p;
821
822 for (p = node; p != NULL; p = p->parent)
823 p->branch_size++;
824 }
825
826 /* Color and rebalance. */
827 rebalance_after_add (list, new_node, node);
828 }
829
830 #if WITH_HASHTABLE
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)
835 {
836 gl_tree_remove_node_from_tree (list, new_node);
837 free (new_node);
838 return NULL;
839 }
840 hash_resize_after_add (list);
841 #endif
842
843 return new_node;
844 }
845
846 static gl_list_node_t
847 gl_tree_nx_add_last (gl_list_t list, const void *elt)
848 {
849 /* Create new node. */
850 gl_list_node_t new_node =
851 (struct gl_list_node_impl *) malloc (sizeof (struct gl_list_node_impl));
852
853 if (new_node == NULL)
854 return NULL;
855
856 new_node->left = NULL;
857 new_node->right = NULL;
858 new_node->branch_size = 1;
859 new_node->value = elt;
860 #if WITH_HASHTABLE
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);
865 #endif
866
867 /* Add it to the tree. */
868 if (list->root == NULL)
869 {
870 new_node->color = BLACK;
871 list->root = new_node;
872 new_node->parent = NULL;
873 }
874 else
875 {
876 gl_list_node_t node;
877
878 for (node = list->root; node->right != NULL; )
879 node = node->right;
880
881 node->right = new_node;
882 new_node->parent = node;
883
884 /* Update branch_size fields of the parent nodes. */
885 {
886 gl_list_node_t p;
887
888 for (p = node; p != NULL; p = p->parent)
889 p->branch_size++;
890 }
891
892 /* Color and rebalance. */
893 rebalance_after_add (list, new_node, node);
894 }
895
896 #if WITH_HASHTABLE
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)
901 {
902 gl_tree_remove_node_from_tree (list, new_node);
903 free (new_node);
904 return NULL;
905 }
906 hash_resize_after_add (list);
907 #endif
908
909 return new_node;
910 }
911
912 static gl_list_node_t
913 gl_tree_nx_add_before (gl_list_t list, gl_list_node_t node, const void *elt)
914 {
915 /* Create new node. */
916 gl_list_node_t new_node =
917 (struct gl_list_node_impl *) malloc (sizeof (struct gl_list_node_impl));
918
919 if (new_node == NULL)
920 return NULL;
921
922 new_node->left = NULL;
923 new_node->right = NULL;
924 new_node->branch_size = 1;
925 new_node->value = elt;
926 #if WITH_HASHTABLE
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);
931 #endif
932
933 /* Add it to the tree. */
934 if (node->left == NULL)
935 node->left = new_node;
936 else
937 {
938 for (node = node->left; node->right != NULL; )
939 node = node->right;
940 node->right = new_node;
941 }
942 new_node->parent = node;
943
944 /* Update branch_size fields of the parent nodes. */
945 {
946 gl_list_node_t p;
947
948 for (p = node; p != NULL; p = p->parent)
949 p->branch_size++;
950 }
951
952 /* Color and rebalance. */
953 rebalance_after_add (list, new_node, node);
954
955 #if WITH_HASHTABLE
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)
960 {
961 gl_tree_remove_node_from_tree (list, new_node);
962 free (new_node);
963 return NULL;
964 }
965 hash_resize_after_add (list);
966 #endif
967
968 return new_node;
969 }
970
971 static gl_list_node_t
972 gl_tree_nx_add_after (gl_list_t list, gl_list_node_t node, const void *elt)
973 {
974 /* Create new node. */
975 gl_list_node_t new_node =
976 (struct gl_list_node_impl *) malloc (sizeof (struct gl_list_node_impl));
977
978 if (new_node == NULL)
979 return NULL;
980
981 new_node->left = NULL;
982 new_node->right = NULL;
983 new_node->branch_size = 1;
984 new_node->value = elt;
985 #if WITH_HASHTABLE
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);
990 #endif
991
992 /* Add it to the tree. */
993 if (node->right == NULL)
994 node->right = new_node;
995 else
996 {
997 for (node = node->right; node->left != NULL; )
998 node = node->left;
999 node->left = new_node;
1000 }
1001 new_node->parent = node;
1002
1003 /* Update branch_size fields of the parent nodes. */
1004 {
1005 gl_list_node_t p;
1006
1007 for (p = node; p != NULL; p = p->parent)
1008 p->branch_size++;
1009 }
1010
1011 /* Color and rebalance. */
1012 rebalance_after_add (list, new_node, node);
1013
1014 #if WITH_HASHTABLE
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)
1019 {
1020 gl_tree_remove_node_from_tree (list, new_node);
1021 free (new_node);
1022 return NULL;
1023 }
1024 hash_resize_after_add (list);
1025 #endif
1026
1027 return new_node;
1028 }