1 /* Sequential list data type implemented by a binary tree.
2 Copyright (C) 2006-2008 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_avltree_list.c, gl_rbtree_list.c,
19 gl_avltreehash_list.c, gl_rbtreehash_list.c. */
22 gl_tree_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)
28 struct gl_list_impl *list = XMALLOC (struct gl_list_impl);
30 list->base.vtable = implementation;
31 list->base.equals_fn = equals_fn;
32 list->base.hashcode_fn = hashcode_fn;
33 list->base.dispose_fn = dispose_fn;
34 list->base.allow_duplicates = allow_duplicates;
36 list->table_size = 11;
37 list->table = XCALLOC (list->table_size, gl_hash_entry_t);
45 gl_tree_size (gl_list_t list)
47 return (list->root != NULL ? list->root->branch_size : 0);
51 gl_tree_node_value (gl_list_t list, gl_list_node_t node)
57 gl_tree_node_set_value (gl_list_t list, gl_list_node_t node, const void *elt)
60 if (elt != node->value)
63 (list->base.hashcode_fn != NULL
64 ? list->base.hashcode_fn (elt)
65 : (size_t)(uintptr_t) elt);
67 if (new_hashcode != node->h.hashcode)
69 remove_from_bucket (list, node);
71 node->h.hashcode = new_hashcode;
72 add_to_bucket (list, node);
83 gl_tree_next_node (gl_list_t list, gl_list_node_t node)
85 if (node->right != NULL)
88 while (node->left != NULL)
93 while (node->parent != NULL && node->parent->right == node)
100 static gl_list_node_t
101 gl_tree_previous_node (gl_list_t list, gl_list_node_t node)
103 if (node->left != NULL)
106 while (node->right != NULL)
111 while (node->parent != NULL && node->parent->left == node)
118 /* Return the node at the given position < gl_tree_size (list). */
119 static inline gl_list_node_t
120 node_at (gl_list_node_t root, size_t position)
122 /* Here we know that root != NULL. */
123 gl_list_node_t node = root;
127 if (node->left != NULL)
129 if (position < node->left->branch_size)
134 position -= node->left->branch_size;
145 gl_tree_get_at (gl_list_t list, size_t position)
147 gl_list_node_t node = list->root;
149 if (!(node != NULL && position < node->branch_size))
150 /* Invalid argument. */
152 node = node_at (node, position);
156 static gl_list_node_t
157 gl_tree_set_at (gl_list_t list, size_t position, const void *elt)
159 gl_list_node_t node = list->root;
161 if (!(node != NULL && position < node->branch_size))
162 /* Invalid argument. */
164 node = node_at (node, position);
166 if (elt != node->value)
168 size_t new_hashcode =
169 (list->base.hashcode_fn != NULL
170 ? list->base.hashcode_fn (elt)
171 : (size_t)(uintptr_t) elt);
173 if (new_hashcode != node->h.hashcode)
175 remove_from_bucket (list, node);
177 node->h.hashcode = new_hashcode;
178 add_to_bucket (list, node);
191 static gl_list_node_t
192 gl_tree_search_from_to (gl_list_t list, size_t start_index, size_t end_index,
195 if (!(start_index <= end_index
196 && end_index <= (list->root != NULL ? list->root->branch_size : 0)))
197 /* Invalid arguments. */
200 gl_listelement_equals_fn equals = list->base.equals_fn;
201 /* Iterate across all elements. */
202 gl_list_node_t node = list->root;
204 iterstack_item_t *stack_ptr = &stack[0];
207 if (start_index == 0)
209 /* Consider all elements. */
212 /* Descend on left branch. */
217 stack_ptr->node = node;
218 stack_ptr->rightp = 0;
222 /* Climb up again. */
225 if (stack_ptr == &stack[0])
228 if (!stack_ptr->rightp)
231 node = stack_ptr->node;
232 /* Test against current element. */
233 if (equals != NULL ? equals (elt, node->value) : elt == node->value)
236 if (index >= end_index)
238 /* Descend on right branch. */
239 stack_ptr->rightp = 1;
246 /* Consider only elements at indices >= start_index.
247 In this case, rightp contains the difference between the start_index
248 for the parent node and the one for the child node (0 when the child
249 node is the parent's left child, > 0 when the child is the parent's
253 /* Descend on left branch. */
258 if (node->branch_size <= start_index)
260 stack_ptr->node = node;
261 stack_ptr->rightp = 0;
265 /* Climb up again. */
268 if (stack_ptr == &stack[0])
271 if (!stack_ptr->rightp)
273 start_index += stack_ptr->rightp;
275 node = stack_ptr->node;
277 size_t left_branch_size1 =
278 (node->left != NULL ? node->left->branch_size : 0) + 1;
279 if (start_index < left_branch_size1)
281 /* Test against current element. */
282 if (equals != NULL ? equals (elt, node->value) : elt == node->value)
284 /* Now that we have considered all indices < left_branch_size1,
285 we can increment start_index. */
286 start_index = left_branch_size1;
289 if (index >= end_index)
291 /* Descend on right branch. */
292 start_index -= left_branch_size1;
293 stack_ptr->rightp = left_branch_size1;
303 gl_tree_indexof_from_to (gl_list_t list, size_t start_index, size_t end_index,
306 if (!(start_index <= end_index
307 && end_index <= (list->root != NULL ? list->root->branch_size : 0)))
308 /* Invalid arguments. */
311 gl_listelement_equals_fn equals = list->base.equals_fn;
312 /* Iterate across all elements. */
313 gl_list_node_t node = list->root;
315 iterstack_item_t *stack_ptr = &stack[0];
318 if (start_index == 0)
320 /* Consider all elements. */
323 /* Descend on left branch. */
328 stack_ptr->node = node;
329 stack_ptr->rightp = 0;
333 /* Climb up again. */
336 if (stack_ptr == &stack[0])
339 if (!stack_ptr->rightp)
342 node = stack_ptr->node;
343 /* Test against current element. */
344 if (equals != NULL ? equals (elt, node->value) : elt == node->value)
347 if (index >= end_index)
349 /* Descend on right branch. */
350 stack_ptr->rightp = 1;
357 /* Consider only elements at indices >= start_index.
358 In this case, rightp contains the difference between the start_index
359 for the parent node and the one for the child node (0 when the child
360 node is the parent's left child, > 0 when the child is the parent's
364 /* Descend on left branch. */
369 if (node->branch_size <= start_index)
371 stack_ptr->node = node;
372 stack_ptr->rightp = 0;
376 /* Climb up again. */
379 if (stack_ptr == &stack[0])
382 if (!stack_ptr->rightp)
384 start_index += stack_ptr->rightp;
386 node = stack_ptr->node;
388 size_t left_branch_size1 =
389 (node->left != NULL ? node->left->branch_size : 0) + 1;
390 if (start_index < left_branch_size1)
392 /* Test against current element. */
393 if (equals != NULL ? equals (elt, node->value) : elt == node->value)
395 /* Now that we have considered all indices < left_branch_size1,
396 we can increment start_index. */
397 start_index = left_branch_size1;
400 if (index >= end_index)
402 /* Descend on right branch. */
403 start_index -= left_branch_size1;
404 stack_ptr->rightp = left_branch_size1;
415 static gl_list_node_t
416 gl_tree_add_at (gl_list_t list, size_t position, const void *elt)
418 size_t count = (list->root != NULL ? list->root->branch_size : 0);
420 if (!(position <= count))
421 /* Invalid argument. */
423 if (position == count)
424 return gl_tree_add_last (list, elt);
426 return gl_tree_add_before (list, node_at (list->root, position), elt);
430 gl_tree_remove_at (gl_list_t list, size_t position)
432 gl_list_node_t node = list->root;
434 if (!(node != NULL && position < node->branch_size))
435 /* Invalid argument. */
437 node = node_at (node, position);
438 return gl_tree_remove_node (list, node);
442 gl_tree_remove (gl_list_t list, const void *elt)
444 if (list->root != NULL)
446 gl_list_node_t node =
447 gl_tree_search_from_to (list, 0, list->root->branch_size, elt);
450 return gl_tree_remove_node (list, node);
458 gl_tree_list_free (gl_list_t list)
460 /* Iterate across all elements in post-order. */
461 gl_list_node_t node = list->root;
463 iterstack_item_t *stack_ptr = &stack[0];
467 /* Descend on left branch. */
472 stack_ptr->node = node;
473 stack_ptr->rightp = false;
477 /* Climb up again. */
480 if (stack_ptr == &stack[0])
483 node = stack_ptr->node;
484 if (!stack_ptr->rightp)
486 /* Free the current node. */
487 if (list->base.dispose_fn != NULL)
488 list->base.dispose_fn (node->value);
491 /* Descend on right branch. */
492 stack_ptr->rightp = true;
502 /* --------------------- gl_list_iterator_t Data Type --------------------- */
504 static gl_list_iterator_t
505 gl_tree_iterator (gl_list_t list)
507 gl_list_iterator_t result;
510 result.vtable = list->base.vtable;
512 /* Start node is the leftmost node. */
515 while (node->left != NULL)
518 /* End point is past the rightmost node. */
529 static gl_list_iterator_t
530 gl_tree_iterator_from_to (gl_list_t list, size_t start_index, size_t end_index)
532 size_t count = (list->root != NULL ? list->root->branch_size : 0);
533 gl_list_iterator_t result;
535 if (!(start_index <= end_index && end_index <= count))
536 /* Invalid arguments. */
538 result.vtable = list->base.vtable;
540 /* Start node is the node at position start_index. */
541 result.p = (start_index < count ? node_at (list->root, start_index) : NULL);
542 /* End point is the node at position end_index. */
543 result.q = (end_index < count ? node_at (list->root, end_index) : NULL);
554 gl_tree_iterator_next (gl_list_iterator_t *iterator,
555 const void **eltp, gl_list_node_t *nodep)
557 if (iterator->p != iterator->q)
559 gl_list_node_t node = (gl_list_node_t) iterator->p;
563 /* Advance to the next node. */
564 if (node->right != NULL)
567 while (node->left != NULL)
572 while (node->parent != NULL && node->parent->right == node)
584 gl_tree_iterator_free (gl_list_iterator_t *iterator)
588 /* ---------------------- Sorted gl_list_t Data Type ---------------------- */
590 static gl_list_node_t
591 gl_tree_sortedlist_search (gl_list_t list, gl_listelement_compar_fn compar,
596 for (node = list->root; node != NULL; )
598 int cmp = compar (node->value, elt);
606 /* We have an element equal to ELT. But we need the leftmost such
608 gl_list_node_t found = node;
610 for (; node != NULL; )
612 int cmp2 = compar (node->value, elt);
617 /* The list was not sorted. */
631 static gl_list_node_t
632 gl_tree_sortedlist_search_from_to (gl_list_t list,
633 gl_listelement_compar_fn compar,
634 size_t low, size_t high,
640 && high <= (list->root != NULL ? list->root->branch_size : 0)))
641 /* Invalid arguments. */
644 for (node = list->root; node != NULL; )
646 size_t left_branch_size =
647 (node->left != NULL ? node->left->branch_size : 0);
649 if (low > left_branch_size)
651 low -= left_branch_size + 1;
652 high -= left_branch_size + 1;
655 else if (high <= left_branch_size)
659 /* Here low <= left_branch_size < high. */
660 int cmp = compar (node->value, elt);
665 high -= left_branch_size + 1;
672 /* We have an element equal to ELT. But we need the leftmost
674 gl_list_node_t found = node;
676 for (; node != NULL; )
678 size_t left_branch_size2 =
679 (node->left != NULL ? node->left->branch_size : 0);
681 if (low > left_branch_size2)
683 low -= left_branch_size2 + 1;
688 /* Here low <= left_branch_size2. */
689 int cmp2 = compar (node->value, elt);
697 /* The list was not sorted. */
714 gl_tree_sortedlist_indexof (gl_list_t list, gl_listelement_compar_fn compar,
720 for (node = list->root, position = 0; node != NULL; )
722 int cmp = compar (node->value, elt);
726 if (node->left != NULL)
727 position += node->left->branch_size;
735 /* We have an element equal to ELT. But we need the leftmost such
737 size_t found_position =
738 position + (node->left != NULL ? node->left->branch_size : 0);
740 for (; node != NULL; )
742 int cmp2 = compar (node->value, elt);
746 if (node->left != NULL)
747 position += node->left->branch_size;
752 /* The list was not sorted. */
758 + (node->left != NULL ? node->left->branch_size : 0);
762 return found_position;
769 gl_tree_sortedlist_indexof_from_to (gl_list_t list,
770 gl_listelement_compar_fn compar,
771 size_t low, size_t high,
778 && high <= (list->root != NULL ? list->root->branch_size : 0)))
779 /* Invalid arguments. */
782 for (node = list->root, position = 0; node != NULL; )
784 size_t left_branch_size =
785 (node->left != NULL ? node->left->branch_size : 0);
787 if (low > left_branch_size)
789 low -= left_branch_size + 1;
790 high -= left_branch_size + 1;
791 position += left_branch_size + 1;
794 else if (high <= left_branch_size)
798 /* Here low <= left_branch_size < high. */
799 int cmp = compar (node->value, elt);
804 high -= left_branch_size + 1;
805 position += left_branch_size + 1;
812 /* We have an element equal to ELT. But we need the leftmost
814 size_t found_position =
815 position + (node->left != NULL ? node->left->branch_size : 0);
817 for (; node != NULL; )
819 size_t left_branch_size2 =
820 (node->left != NULL ? node->left->branch_size : 0);
822 if (low > left_branch_size2)
824 low -= left_branch_size2 + 1;
829 /* Here low <= left_branch_size2. */
830 int cmp2 = compar (node->value, elt);
834 position += left_branch_size2 + 1;
838 /* The list was not sorted. */
842 found_position = position + left_branch_size2;
847 return found_position;
854 static gl_list_node_t
855 gl_tree_sortedlist_add (gl_list_t list, gl_listelement_compar_fn compar,
858 gl_list_node_t node = list->root;
861 return gl_tree_add_first (list, elt);
865 int cmp = compar (node->value, elt);
869 if (node->right == NULL)
870 return gl_tree_add_after (list, node, elt);
875 if (node->left == NULL)
876 return gl_tree_add_before (list, node, elt);
880 return gl_tree_add_before (list, node, elt);
885 gl_tree_sortedlist_remove (gl_list_t list, gl_listelement_compar_fn compar,
888 gl_list_node_t node = gl_tree_sortedlist_search (list, compar, elt);
890 return gl_tree_remove_node (list, node);