1 /* Sequential list data type implemented by a binary tree.
2 Copyright (C) 2006-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_avltree_list.c, gl_rbtree_list.c,
19 gl_avltreehash_list.c, gl_rbtreehash_list.c. */
20
21 static gl_list_t
22 gl_tree_nx_create_empty (gl_list_implementation_t implementation,
23 gl_listelement_equals_fn equals_fn,
24 gl_listelement_hashcode_fn hashcode_fn,
25 gl_listelement_dispose_fn dispose_fn,
26 bool allow_duplicates)
27 {
28 struct gl_list_impl *list = (struct gl_list_impl *) malloc (sizeof (struct gl_list_impl));
29
30 if (list == NULL)
31 return NULL;
32
33 list->base.vtable = implementation;
34 list->base.equals_fn = equals_fn;
35 list->base.hashcode_fn = hashcode_fn;
36 list->base.dispose_fn = dispose_fn;
37 list->base.allow_duplicates = allow_duplicates;
38 #if WITH_HASHTABLE
39 list->table_size = 11;
40 list->table =
41 (gl_hash_entry_t *) calloc (list->table_size, sizeof (gl_hash_entry_t));
42 if (list->table == NULL)
43 goto fail;
44 #endif
45 list->root = NULL;
46
47 return list;
48
49 #if WITH_HASHTABLE
50 fail:
51 free (list);
52 return NULL;
53 #endif
54 }
55
56 static size_t _GL_ATTRIBUTE_PURE
57 gl_tree_size (gl_list_t list)
58 {
59 return (list->root != NULL ? list->root->branch_size : 0);
60 }
61
62 static const void * _GL_ATTRIBUTE_PURE
63 gl_tree_node_value (_GL_ATTRIBUTE_MAYBE_UNUSED gl_list_t list,
64 gl_list_node_t node)
65 {
66 return node->value;
67 }
68
69 static int
70 gl_tree_node_nx_set_value (_GL_ATTRIBUTE_MAYBE_UNUSED gl_list_t list,
71 gl_list_node_t node, const void *elt)
72 {
73 #if WITH_HASHTABLE
74 if (elt != node->value)
75 {
76 size_t new_hashcode =
77 (list->base.hashcode_fn != NULL
78 ? list->base.hashcode_fn (elt)
79 : (size_t)(uintptr_t) elt);
80
81 if (new_hashcode != node->h.hashcode)
82 {
83 remove_from_bucket (list, node);
84 node->value = elt;
85 node->h.hashcode = new_hashcode;
86 if (add_to_bucket (list, node) < 0)
87 {
88 /* Out of memory. We removed node from a bucket but cannot add
89 it to another bucket. In order to avoid inconsistencies, we
90 must remove node entirely from the list. */
91 gl_tree_remove_node_from_tree (list, node);
92 free (node);
93 return -1;
94 }
95 }
96 else
97 node->value = elt;
98 }
99 #else
100 node->value = elt;
101 #endif
102 return 0;
103 }
104
105 static gl_list_node_t _GL_ATTRIBUTE_PURE
106 gl_tree_next_node (_GL_ATTRIBUTE_MAYBE_UNUSED gl_list_t list,
107 gl_list_node_t node)
108 {
109 if (node->right != NULL)
110 {
111 node = node->right;
112 while (node->left != NULL)
113 node = node->left;
114 }
115 else
116 {
117 while (node->parent != NULL && node->parent->right == node)
118 node = node->parent;
119 node = node->parent;
120 }
121 return node;
122 }
123
124 static gl_list_node_t _GL_ATTRIBUTE_PURE
125 gl_tree_previous_node (_GL_ATTRIBUTE_MAYBE_UNUSED gl_list_t list,
126 gl_list_node_t node)
127 {
128 if (node->left != NULL)
129 {
130 node = node->left;
131 while (node->right != NULL)
132 node = node->right;
133 }
134 else
135 {
136 while (node->parent != NULL && node->parent->left == node)
137 node = node->parent;
138 node = node->parent;
139 }
140 return node;
141 }
142
143 static gl_list_node_t _GL_ATTRIBUTE_PURE
144 gl_tree_first_node (_GL_ATTRIBUTE_MAYBE_UNUSED gl_list_t list)
145 {
146 gl_list_node_t node = list->root;
147
148 if (node != NULL)
149 {
150 while (node->left != NULL)
151 node = node->left;
152 }
153 return node;
154 }
155
156 static gl_list_node_t _GL_ATTRIBUTE_PURE
157 gl_tree_last_node (_GL_ATTRIBUTE_MAYBE_UNUSED gl_list_t list)
158 {
159 gl_list_node_t node = list->root;
160
161 if (node != NULL)
162 {
163 while (node->right != NULL)
164 node = node->right;
165 }
166 return node;
167 }
168
169 /* Returns the node at the given position < gl_tree_size (list). */
170 static gl_list_node_t _GL_ATTRIBUTE_PURE
171 node_at (gl_list_node_t root, size_t position)
172 {
173 /* Here we know that root != NULL. */
174 gl_list_node_t node = root;
175
176 for (;;)
177 {
178 if (node->left != NULL)
179 {
180 if (position < node->left->branch_size)
181 {
182 node = node->left;
183 continue;
184 }
185 position -= node->left->branch_size;
186 }
187 if (position == 0)
188 break;
189 position--;
190 node = node->right;
191 }
192 return node;
193 }
194
195 static const void * _GL_ATTRIBUTE_PURE
196 gl_tree_get_at (gl_list_t list, size_t position)
197 {
198 gl_list_node_t node = list->root;
199
200 if (!(node != NULL && position < node->branch_size))
201 /* Invalid argument. */
202 abort ();
203 node = node_at (node, position);
204 return node->value;
205 }
206
207 static gl_list_node_t
208 gl_tree_nx_set_at (gl_list_t list, size_t position, const void *elt)
209 {
210 gl_list_node_t node = list->root;
211
212 if (!(node != NULL && position < node->branch_size))
213 /* Invalid argument. */
214 abort ();
215 node = node_at (node, position);
216 #if WITH_HASHTABLE
217 if (elt != node->value)
218 {
219 size_t new_hashcode =
220 (list->base.hashcode_fn != NULL
221 ? list->base.hashcode_fn (elt)
222 : (size_t)(uintptr_t) elt);
223
224 if (new_hashcode != node->h.hashcode)
225 {
226 remove_from_bucket (list, node);
227 node->value = elt;
228 node->h.hashcode = new_hashcode;
229 if (add_to_bucket (list, node) < 0)
230 {
231 /* Out of memory. We removed node from a bucket but cannot add
232 it to another bucket. In order to avoid inconsistencies, we
233 must remove node entirely from the list. */
234 gl_tree_remove_node_from_tree (list, node);
235 free (node);
236 return NULL;
237 }
238 }
239 else
240 node->value = elt;
241 }
242 #else
243 node->value = elt;
244 #endif
245 return node;
246 }
247
248 #if !WITH_HASHTABLE
249
250 static gl_list_node_t _GL_ATTRIBUTE_PURE
251 gl_tree_search_from_to (gl_list_t list, size_t start_index, size_t end_index,
252 const void *elt)
253 {
254 if (!(start_index <= end_index
255 && end_index <= (list->root != NULL ? list->root->branch_size : 0)))
256 /* Invalid arguments. */
257 abort ();
258 {
259 gl_listelement_equals_fn equals = list->base.equals_fn;
260 /* Iterate across all elements. */
261 gl_list_node_t node = list->root;
262 iterstack_t stack;
263 iterstack_item_t *stack_ptr = &stack[0];
264 size_t index = 0;
265
266 if (start_index == 0)
267 {
268 /* Consider all elements. */
269 for (;;)
270 {
271 /* Descend on left branch. */
272 for (;;)
273 {
274 if (node == NULL)
275 break;
276 stack_ptr->node = node;
277 stack_ptr->rightp = 0;
278 node = node->left;
279 stack_ptr++;
280 }
281 /* Climb up again. */
282 for (;;)
283 {
284 if (stack_ptr == &stack[0])
285 return NULL;
286 stack_ptr--;
287 if (!stack_ptr->rightp)
288 break;
289 }
290 node = stack_ptr->node;
291 /* Test against current element. */
292 if (equals != NULL ? equals (elt, node->value) : elt == node->value)
293 return node;
294 index++;
295 if (index >= end_index)
296 return NULL;
297 /* Descend on right branch. */
298 stack_ptr->rightp = 1;
299 node = node->right;
300 stack_ptr++;
301 }
302 }
303 else
304 {
305 /* Consider only elements at indices >= start_index.
306 In this case, rightp contains the difference between the start_index
307 for the parent node and the one for the child node (0 when the child
308 node is the parent's left child, > 0 when the child is the parent's
309 right child). */
310 for (;;)
311 {
312 /* Descend on left branch. */
313 for (;;)
314 {
315 if (node == NULL)
316 break;
317 if (node->branch_size <= start_index)
318 break;
319 stack_ptr->node = node;
320 stack_ptr->rightp = 0;
321 node = node->left;
322 stack_ptr++;
323 }
324 /* Climb up again. */
325 for (;;)
326 {
327 if (stack_ptr == &stack[0])
328 return NULL;
329 stack_ptr--;
330 if (!stack_ptr->rightp)
331 break;
332 start_index += stack_ptr->rightp;
333 }
334 node = stack_ptr->node;
335 {
336 size_t left_branch_size1 =
337 (node->left != NULL ? node->left->branch_size : 0) + 1;
338 if (start_index < left_branch_size1)
339 {
340 /* Test against current element. */
341 if (equals != NULL ? equals (elt, node->value) : elt == node->value)
342 return node;
343 /* Now that we have considered all indices < left_branch_size1,
344 we can increment start_index. */
345 start_index = left_branch_size1;
346 }
347 index++;
348 if (index >= end_index)
349 return NULL;
350 /* Descend on right branch. */
351 start_index -= left_branch_size1;
352 stack_ptr->rightp = left_branch_size1;
353 }
354 node = node->right;
355 stack_ptr++;
356 }
357 }
358 }
359 }
360
361 static size_t _GL_ATTRIBUTE_PURE
362 gl_tree_indexof_from_to (gl_list_t list, size_t start_index, size_t end_index,
363 const void *elt)
364 {
365 if (!(start_index <= end_index
366 && end_index <= (list->root != NULL ? list->root->branch_size : 0)))
367 /* Invalid arguments. */
368 abort ();
369 {
370 gl_listelement_equals_fn equals = list->base.equals_fn;
371 /* Iterate across all elements. */
372 gl_list_node_t node = list->root;
373 iterstack_t stack;
374 iterstack_item_t *stack_ptr = &stack[0];
375 size_t index = 0;
376
377 if (start_index == 0)
378 {
379 /* Consider all elements. */
380 for (;;)
381 {
382 /* Descend on left branch. */
383 for (;;)
384 {
385 if (node == NULL)
386 break;
387 stack_ptr->node = node;
388 stack_ptr->rightp = 0;
389 node = node->left;
390 stack_ptr++;
391 }
392 /* Climb up again. */
393 for (;;)
394 {
395 if (stack_ptr == &stack[0])
396 return (size_t)(-1);
397 stack_ptr--;
398 if (!stack_ptr->rightp)
399 break;
400 }
401 node = stack_ptr->node;
402 /* Test against current element. */
403 if (equals != NULL ? equals (elt, node->value) : elt == node->value)
404 return index;
405 index++;
406 if (index >= end_index)
407 return (size_t)(-1);
408 /* Descend on right branch. */
409 stack_ptr->rightp = 1;
410 node = node->right;
411 stack_ptr++;
412 }
413 }
414 else
415 {
416 /* Consider only elements at indices >= start_index.
417 In this case, rightp contains the difference between the start_index
418 for the parent node and the one for the child node (0 when the child
419 node is the parent's left child, > 0 when the child is the parent's
420 right child). */
421 for (;;)
422 {
423 /* Descend on left branch. */
424 for (;;)
425 {
426 if (node == NULL)
427 break;
428 if (node->branch_size <= start_index)
429 break;
430 stack_ptr->node = node;
431 stack_ptr->rightp = 0;
432 node = node->left;
433 stack_ptr++;
434 }
435 /* Climb up again. */
436 for (;;)
437 {
438 if (stack_ptr == &stack[0])
439 return (size_t)(-1);
440 stack_ptr--;
441 if (!stack_ptr->rightp)
442 break;
443 start_index += stack_ptr->rightp;
444 }
445 node = stack_ptr->node;
446 {
447 size_t left_branch_size1 =
448 (node->left != NULL ? node->left->branch_size : 0) + 1;
449 if (start_index < left_branch_size1)
450 {
451 /* Test against current element. */
452 if (equals != NULL ? equals (elt, node->value) : elt == node->value)
453 return index;
454 /* Now that we have considered all indices < left_branch_size1,
455 we can increment start_index. */
456 start_index = left_branch_size1;
457 }
458 index++;
459 if (index >= end_index)
460 return (size_t)(-1);
461 /* Descend on right branch. */
462 start_index -= left_branch_size1;
463 stack_ptr->rightp = left_branch_size1;
464 }
465 node = node->right;
466 stack_ptr++;
467 }
468 }
469 }
470 }
471
472 #endif
473
474 static gl_list_node_t
475 gl_tree_nx_add_at (gl_list_t list, size_t position, const void *elt)
476 {
477 size_t count = (list->root != NULL ? list->root->branch_size : 0);
478
479 if (!(position <= count))
480 /* Invalid argument. */
481 abort ();
482 if (position == count)
483 return gl_tree_nx_add_last (list, elt);
484 else
485 return gl_tree_nx_add_before (list, node_at (list->root, position), elt);
486 }
487
488 static bool
489 gl_tree_remove_node (gl_list_t list, gl_list_node_t node)
490 {
491 #if WITH_HASHTABLE
492 /* Remove node from the hash table.
493 Note that this is only possible _before_ the node is removed from the
494 tree structure, because remove_from_bucket() uses node_position(). */
495 remove_from_bucket (list, node);
496 #endif
497
498 gl_tree_remove_node_from_tree (list, node);
499
500 if (list->base.dispose_fn != NULL)
501 list->base.dispose_fn (node->value);
502 free (node);
503 return true;
504 }
505
506 static bool
507 gl_tree_remove_at (gl_list_t list, size_t position)
508 {
509 gl_list_node_t node = list->root;
510
511 if (!(node != NULL && position < node->branch_size))
512 /* Invalid argument. */
513 abort ();
514 node = node_at (node, position);
515 return gl_tree_remove_node (list, node);
516 }
517
518 static bool
519 gl_tree_remove (gl_list_t list, const void *elt)
520 {
521 if (list->root != NULL)
522 {
523 gl_list_node_t node =
524 gl_tree_search_from_to (list, 0, list->root->branch_size, elt);
525
526 if (node != NULL)
527 return gl_tree_remove_node (list, node);
528 }
529 return false;
530 }
531
532 #if !WITH_HASHTABLE
533
534 static void
535 gl_tree_list_free (gl_list_t list)
536 {
537 /* Iterate across all elements in post-order. */
538 gl_list_node_t node = list->root;
539 iterstack_t stack;
540 iterstack_item_t *stack_ptr = &stack[0];
541
542 for (;;)
543 {
544 /* Descend on left branch. */
545 for (;;)
546 {
547 if (node == NULL)
548 break;
549 stack_ptr->node = node;
550 stack_ptr->rightp = false;
551 node = node->left;
552 stack_ptr++;
553 }
554 /* Climb up again. */
555 for (;;)
556 {
557 if (stack_ptr == &stack[0])
558 goto done_iterate;
559 stack_ptr--;
560 node = stack_ptr->node;
561 if (!stack_ptr->rightp)
562 break;
563 /* Free the current node. */
564 if (list->base.dispose_fn != NULL)
565 list->base.dispose_fn (node->value);
566 free (node);
567 }
568 /* Descend on right branch. */
569 stack_ptr->rightp = true;
570 node = node->right;
571 stack_ptr++;
572 }
573 done_iterate:
574 free (list);
575 }
576
577 #endif
578
579 /* --------------------- gl_list_iterator_t Data Type --------------------- */
580
581 static gl_list_iterator_t _GL_ATTRIBUTE_PURE
582 gl_tree_iterator (gl_list_t list)
583 {
584 gl_list_iterator_t result;
585 gl_list_node_t node;
586
587 result.vtable = list->base.vtable;
588 result.list = list;
589 /* Start node is the leftmost node. */
590 node = list->root;
591 if (node != NULL)
592 while (node->left != NULL)
593 node = node->left;
594 result.p = node;
595 /* End point is past the rightmost node. */
596 result.q = NULL;
597 #if defined GCC_LINT || defined lint
598 result.i = 0;
599 result.j = 0;
600 result.count = 0;
601 #endif
602
603 return result;
604 }
605
606 static gl_list_iterator_t _GL_ATTRIBUTE_PURE
607 gl_tree_iterator_from_to (gl_list_t list, size_t start_index, size_t end_index)
608 {
609 size_t count = (list->root != NULL ? list->root->branch_size : 0);
610 gl_list_iterator_t result;
611
612 if (!(start_index <= end_index && end_index <= count))
613 /* Invalid arguments. */
614 abort ();
615 result.vtable = list->base.vtable;
616 result.list = list;
617 /* Start node is the node at position start_index. */
618 result.p = (start_index < count ? node_at (list->root, start_index) : NULL);
619 /* End point is the node at position end_index. */
620 result.q = (end_index < count ? node_at (list->root, end_index) : NULL);
621 #if defined GCC_LINT || defined lint
622 result.i = 0;
623 result.j = 0;
624 result.count = 0;
625 #endif
626
627 return result;
628 }
629
630 static bool
631 gl_tree_iterator_next (gl_list_iterator_t *iterator,
632 const void **eltp, gl_list_node_t *nodep)
633 {
634 if (iterator->p != iterator->q)
635 {
636 gl_list_node_t node = (gl_list_node_t) iterator->p;
637 *eltp = node->value;
638 if (nodep != NULL)
639 *nodep = node;
640 /* Advance to the next node. */
641 if (node->right != NULL)
642 {
643 node = node->right;
644 while (node->left != NULL)
645 node = node->left;
646 }
647 else
648 {
649 while (node->parent != NULL && node->parent->right == node)
650 node = node->parent;
651 node = node->parent;
652 }
653 iterator->p = node;
654 return true;
655 }
656 else
657 return false;
658 }
659
660 static void
661 gl_tree_iterator_free (_GL_ATTRIBUTE_MAYBE_UNUSED gl_list_iterator_t *iterator)
662 {
663 }
664
665 /* ---------------------- Sorted gl_list_t Data Type ---------------------- */
666
667 static gl_list_node_t _GL_ATTRIBUTE_PURE
668 gl_tree_sortedlist_search (gl_list_t list, gl_listelement_compar_fn compar,
669 const void *elt)
670 {
671 gl_list_node_t node;
672
673 for (node = list->root; node != NULL; )
674 {
675 int cmp = compar (node->value, elt);
676
677 if (cmp < 0)
678 node = node->right;
679 else if (cmp > 0)
680 node = node->left;
681 else /* cmp == 0 */
682 {
683 /* We have an element equal to ELT. But we need the leftmost such
684 element. */
685 gl_list_node_t found = node;
686 node = node->left;
687 for (; node != NULL; )
688 {
689 int cmp2 = compar (node->value, elt);
690
691 if (cmp2 < 0)
692 node = node->right;
693 else if (cmp2 > 0)
694 /* The list was not sorted. */
695 abort ();
696 else /* cmp2 == 0 */
697 {
698 found = node;
699 node = node->left;
700 }
701 }
702 return found;
703 }
704 }
705 return NULL;
706 }
707
708 static gl_list_node_t _GL_ATTRIBUTE_PURE
709 gl_tree_sortedlist_search_from_to (gl_list_t list,
710 gl_listelement_compar_fn compar,
711 size_t low, size_t high,
712 const void *elt)
713 {
714 gl_list_node_t node;
715
716 if (!(low <= high
717 && high <= (list->root != NULL ? list->root->branch_size : 0)))
718 /* Invalid arguments. */
719 abort ();
720
721 for (node = list->root; node != NULL; )
722 {
723 size_t left_branch_size =
724 (node->left != NULL ? node->left->branch_size : 0);
725
726 if (low > left_branch_size)
727 {
728 low -= left_branch_size + 1;
729 high -= left_branch_size + 1;
730 node = node->right;
731 }
732 else if (high <= left_branch_size)
733 node = node->left;
734 else
735 {
736 /* Here low <= left_branch_size < high. */
737 int cmp = compar (node->value, elt);
738
739 if (cmp < 0)
740 {
741 low = 0;
742 high -= left_branch_size + 1;
743 node = node->right;
744 }
745 else if (cmp > 0)
746 node = node->left;
747 else /* cmp == 0 */
748 {
749 /* We have an element equal to ELT. But we need the leftmost
750 such element. */
751 gl_list_node_t found = node;
752 node = node->left;
753 for (; node != NULL; )
754 {
755 size_t left_branch_size2 =
756 (node->left != NULL ? node->left->branch_size : 0);
757
758 if (low > left_branch_size2)
759 {
760 low -= left_branch_size2 + 1;
761 node = node->right;
762 }
763 else
764 {
765 /* Here low <= left_branch_size2. */
766 int cmp2 = compar (node->value, elt);
767
768 if (cmp2 < 0)
769 {
770 low = 0;
771 node = node->right;
772 }
773 else if (cmp2 > 0)
774 /* The list was not sorted. */
775 abort ();
776 else /* cmp2 == 0 */
777 {
778 found = node;
779 node = node->left;
780 }
781 }
782 }
783 return found;
784 }
785 }
786 }
787 return NULL;
788 }
789
790 static size_t _GL_ATTRIBUTE_PURE
791 gl_tree_sortedlist_indexof (gl_list_t list, gl_listelement_compar_fn compar,
792 const void *elt)
793 {
794 gl_list_node_t node;
795 size_t position;
796
797 for (node = list->root, position = 0; node != NULL; )
798 {
799 int cmp = compar (node->value, elt);
800
801 if (cmp < 0)
802 {
803 if (node->left != NULL)
804 position += node->left->branch_size;
805 position++;
806 node = node->right;
807 }
808 else if (cmp > 0)
809 node = node->left;
810 else /* cmp == 0 */
811 {
812 /* We have an element equal to ELT. But we need the leftmost such
813 element. */
814 size_t found_position =
815 position + (node->left != NULL ? node->left->branch_size : 0);
816 node = node->left;
817 for (; node != NULL; )
818 {
819 int cmp2 = compar (node->value, elt);
820
821 if (cmp2 < 0)
822 {
823 if (node->left != NULL)
824 position += node->left->branch_size;
825 position++;
826 node = node->right;
827 }
828 else if (cmp2 > 0)
829 /* The list was not sorted. */
830 abort ();
831 else /* cmp2 == 0 */
832 {
833 found_position =
834 position
835 + (node->left != NULL ? node->left->branch_size : 0);
836 node = node->left;
837 }
838 }
839 return found_position;
840 }
841 }
842 return (size_t)(-1);
843 }
844
845 static size_t _GL_ATTRIBUTE_PURE
846 gl_tree_sortedlist_indexof_from_to (gl_list_t list,
847 gl_listelement_compar_fn compar,
848 size_t low, size_t high,
849 const void *elt)
850 {
851 gl_list_node_t node;
852 size_t position;
853
854 if (!(low <= high
855 && high <= (list->root != NULL ? list->root->branch_size : 0)))
856 /* Invalid arguments. */
857 abort ();
858
859 for (node = list->root, position = 0; node != NULL; )
860 {
861 size_t left_branch_size =
862 (node->left != NULL ? node->left->branch_size : 0);
863
864 if (low > left_branch_size)
865 {
866 low -= left_branch_size + 1;
867 high -= left_branch_size + 1;
868 position += left_branch_size + 1;
869 node = node->right;
870 }
871 else if (high <= left_branch_size)
872 node = node->left;
873 else
874 {
875 /* Here low <= left_branch_size < high. */
876 int cmp = compar (node->value, elt);
877
878 if (cmp < 0)
879 {
880 low = 0;
881 high -= left_branch_size + 1;
882 position += left_branch_size + 1;
883 node = node->right;
884 }
885 else if (cmp > 0)
886 node = node->left;
887 else /* cmp == 0 */
888 {
889 /* We have an element equal to ELT. But we need the leftmost
890 such element. */
891 size_t found_position =
892 position + (node->left != NULL ? node->left->branch_size : 0);
893 node = node->left;
894 for (; node != NULL; )
895 {
896 size_t left_branch_size2 =
897 (node->left != NULL ? node->left->branch_size : 0);
898
899 if (low > left_branch_size2)
900 {
901 low -= left_branch_size2 + 1;
902 node = node->right;
903 }
904 else
905 {
906 /* Here low <= left_branch_size2. */
907 int cmp2 = compar (node->value, elt);
908
909 if (cmp2 < 0)
910 {
911 position += left_branch_size2 + 1;
912 node = node->right;
913 }
914 else if (cmp2 > 0)
915 /* The list was not sorted. */
916 abort ();
917 else /* cmp2 == 0 */
918 {
919 found_position = position + left_branch_size2;
920 node = node->left;
921 }
922 }
923 }
924 return found_position;
925 }
926 }
927 }
928 return (size_t)(-1);
929 }
930
931 static gl_list_node_t
932 gl_tree_sortedlist_nx_add (gl_list_t list, gl_listelement_compar_fn compar,
933 const void *elt)
934 {
935 gl_list_node_t node = list->root;
936
937 if (node == NULL)
938 return gl_tree_nx_add_first (list, elt);
939
940 for (;;)
941 {
942 int cmp = compar (node->value, elt);
943
944 if (cmp < 0)
945 {
946 if (node->right == NULL)
947 return gl_tree_nx_add_after (list, node, elt);
948 node = node->right;
949 }
950 else if (cmp > 0)
951 {
952 if (node->left == NULL)
953 return gl_tree_nx_add_before (list, node, elt);
954 node = node->left;
955 }
956 else /* cmp == 0 */
957 return gl_tree_nx_add_before (list, node, elt);
958 }
959 }
960
961 static bool
962 gl_tree_sortedlist_remove (gl_list_t list, gl_listelement_compar_fn compar,
963 const void *elt)
964 {
965 gl_list_node_t node = gl_tree_sortedlist_search (list, compar, elt);
966 if (node != NULL)
967 return gl_tree_remove_node (list, node);
968 else
969 return false;
970 }