1 /* Sequential list data type implemented by a binary tree.
2 Copyright (C) 2006-2011 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_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)
28 struct gl_list_impl *list = (struct gl_list_impl *) malloc (sizeof (struct gl_list_impl));
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;
39 list->table_size = 11;
41 (gl_hash_entry_t *) calloc (list->table_size, sizeof (gl_hash_entry_t));
42 if (list->table == NULL)
57 gl_tree_size (gl_list_t list)
59 return (list->root != NULL ? list->root->branch_size : 0);
63 gl_tree_node_value (gl_list_t list, gl_list_node_t node)
69 gl_tree_node_nx_set_value (gl_list_t list, gl_list_node_t node, const void *elt)
72 if (elt != node->value)
75 (list->base.hashcode_fn != NULL
76 ? list->base.hashcode_fn (elt)
77 : (size_t)(uintptr_t) elt);
79 if (new_hashcode != node->h.hashcode)
81 remove_from_bucket (list, node);
83 node->h.hashcode = new_hashcode;
84 if (add_to_bucket (list, node) < 0)
86 /* Out of memory. We removed node from a bucket but cannot add
87 it to another bucket. In order to avoid inconsistencies, we
88 must remove node entirely from the list. */
89 gl_tree_remove_node_from_tree (list, node);
103 static gl_list_node_t
104 gl_tree_next_node (gl_list_t list, gl_list_node_t node)
106 if (node->right != NULL)
109 while (node->left != NULL)
114 while (node->parent != NULL && node->parent->right == node)
121 static gl_list_node_t
122 gl_tree_previous_node (gl_list_t list, gl_list_node_t node)
124 if (node->left != NULL)
127 while (node->right != NULL)
132 while (node->parent != NULL && node->parent->left == node)
139 /* Return the node at the given position < gl_tree_size (list). */
140 static inline gl_list_node_t
141 node_at (gl_list_node_t root, size_t position)
143 /* Here we know that root != NULL. */
144 gl_list_node_t node = root;
148 if (node->left != NULL)
150 if (position < node->left->branch_size)
155 position -= node->left->branch_size;
166 gl_tree_get_at (gl_list_t list, size_t position)
168 gl_list_node_t node = list->root;
170 if (!(node != NULL && position < node->branch_size))
171 /* Invalid argument. */
173 node = node_at (node, position);
177 static gl_list_node_t
178 gl_tree_nx_set_at (gl_list_t list, size_t position, const void *elt)
180 gl_list_node_t node = list->root;
182 if (!(node != NULL && position < node->branch_size))
183 /* Invalid argument. */
185 node = node_at (node, position);
187 if (elt != node->value)
189 size_t new_hashcode =
190 (list->base.hashcode_fn != NULL
191 ? list->base.hashcode_fn (elt)
192 : (size_t)(uintptr_t) elt);
194 if (new_hashcode != node->h.hashcode)
196 remove_from_bucket (list, node);
198 node->h.hashcode = new_hashcode;
199 if (add_to_bucket (list, node) < 0)
201 /* Out of memory. We removed node from a bucket but cannot add
202 it to another bucket. In order to avoid inconsistencies, we
203 must remove node entirely from the list. */
204 gl_tree_remove_node_from_tree (list, node);
220 static gl_list_node_t
221 gl_tree_search_from_to (gl_list_t list, size_t start_index, size_t end_index,
224 if (!(start_index <= end_index
225 && end_index <= (list->root != NULL ? list->root->branch_size : 0)))
226 /* Invalid arguments. */
229 gl_listelement_equals_fn equals = list->base.equals_fn;
230 /* Iterate across all elements. */
231 gl_list_node_t node = list->root;
233 iterstack_item_t *stack_ptr = &stack[0];
236 if (start_index == 0)
238 /* Consider all elements. */
241 /* Descend on left branch. */
246 stack_ptr->node = node;
247 stack_ptr->rightp = 0;
251 /* Climb up again. */
254 if (stack_ptr == &stack[0])
257 if (!stack_ptr->rightp)
260 node = stack_ptr->node;
261 /* Test against current element. */
262 if (equals != NULL ? equals (elt, node->value) : elt == node->value)
265 if (index >= end_index)
267 /* Descend on right branch. */
268 stack_ptr->rightp = 1;
275 /* Consider only elements at indices >= start_index.
276 In this case, rightp contains the difference between the start_index
277 for the parent node and the one for the child node (0 when the child
278 node is the parent's left child, > 0 when the child is the parent's
282 /* Descend on left branch. */
287 if (node->branch_size <= start_index)
289 stack_ptr->node = node;
290 stack_ptr->rightp = 0;
294 /* Climb up again. */
297 if (stack_ptr == &stack[0])
300 if (!stack_ptr->rightp)
302 start_index += stack_ptr->rightp;
304 node = stack_ptr->node;
306 size_t left_branch_size1 =
307 (node->left != NULL ? node->left->branch_size : 0) + 1;
308 if (start_index < left_branch_size1)
310 /* Test against current element. */
311 if (equals != NULL ? equals (elt, node->value) : elt == node->value)
313 /* Now that we have considered all indices < left_branch_size1,
314 we can increment start_index. */
315 start_index = left_branch_size1;
318 if (index >= end_index)
320 /* Descend on right branch. */
321 start_index -= left_branch_size1;
322 stack_ptr->rightp = left_branch_size1;
332 gl_tree_indexof_from_to (gl_list_t list, size_t start_index, size_t end_index,
335 if (!(start_index <= end_index
336 && end_index <= (list->root != NULL ? list->root->branch_size : 0)))
337 /* Invalid arguments. */
340 gl_listelement_equals_fn equals = list->base.equals_fn;
341 /* Iterate across all elements. */
342 gl_list_node_t node = list->root;
344 iterstack_item_t *stack_ptr = &stack[0];
347 if (start_index == 0)
349 /* Consider all elements. */
352 /* Descend on left branch. */
357 stack_ptr->node = node;
358 stack_ptr->rightp = 0;
362 /* Climb up again. */
365 if (stack_ptr == &stack[0])
368 if (!stack_ptr->rightp)
371 node = stack_ptr->node;
372 /* Test against current element. */
373 if (equals != NULL ? equals (elt, node->value) : elt == node->value)
376 if (index >= end_index)
378 /* Descend on right branch. */
379 stack_ptr->rightp = 1;
386 /* Consider only elements at indices >= start_index.
387 In this case, rightp contains the difference between the start_index
388 for the parent node and the one for the child node (0 when the child
389 node is the parent's left child, > 0 when the child is the parent's
393 /* Descend on left branch. */
398 if (node->branch_size <= start_index)
400 stack_ptr->node = node;
401 stack_ptr->rightp = 0;
405 /* Climb up again. */
408 if (stack_ptr == &stack[0])
411 if (!stack_ptr->rightp)
413 start_index += stack_ptr->rightp;
415 node = stack_ptr->node;
417 size_t left_branch_size1 =
418 (node->left != NULL ? node->left->branch_size : 0) + 1;
419 if (start_index < left_branch_size1)
421 /* Test against current element. */
422 if (equals != NULL ? equals (elt, node->value) : elt == node->value)
424 /* Now that we have considered all indices < left_branch_size1,
425 we can increment start_index. */
426 start_index = left_branch_size1;
429 if (index >= end_index)
431 /* Descend on right branch. */
432 start_index -= left_branch_size1;
433 stack_ptr->rightp = left_branch_size1;
444 static gl_list_node_t
445 gl_tree_nx_add_at (gl_list_t list, size_t position, const void *elt)
447 size_t count = (list->root != NULL ? list->root->branch_size : 0);
449 if (!(position <= count))
450 /* Invalid argument. */
452 if (position == count)
453 return gl_tree_nx_add_last (list, elt);
455 return gl_tree_nx_add_before (list, node_at (list->root, position), elt);
459 gl_tree_remove_node (gl_list_t list, gl_list_node_t node)
462 /* Remove node from the hash table.
463 Note that this is only possible _before_ the node is removed from the
464 tree structure, because remove_from_bucket() uses node_position(). */
465 remove_from_bucket (list, node);
468 gl_tree_remove_node_from_tree (list, node);
470 if (list->base.dispose_fn != NULL)
471 list->base.dispose_fn (node->value);
477 gl_tree_remove_at (gl_list_t list, size_t position)
479 gl_list_node_t node = list->root;
481 if (!(node != NULL && position < node->branch_size))
482 /* Invalid argument. */
484 node = node_at (node, position);
485 return gl_tree_remove_node (list, node);
489 gl_tree_remove (gl_list_t list, const void *elt)
491 if (list->root != NULL)
493 gl_list_node_t node =
494 gl_tree_search_from_to (list, 0, list->root->branch_size, elt);
497 return gl_tree_remove_node (list, node);
505 gl_tree_list_free (gl_list_t list)
507 /* Iterate across all elements in post-order. */
508 gl_list_node_t node = list->root;
510 iterstack_item_t *stack_ptr = &stack[0];
514 /* Descend on left branch. */
519 stack_ptr->node = node;
520 stack_ptr->rightp = false;
524 /* Climb up again. */
527 if (stack_ptr == &stack[0])
530 node = stack_ptr->node;
531 if (!stack_ptr->rightp)
533 /* Free the current node. */
534 if (list->base.dispose_fn != NULL)
535 list->base.dispose_fn (node->value);
538 /* Descend on right branch. */
539 stack_ptr->rightp = true;
549 /* --------------------- gl_list_iterator_t Data Type --------------------- */
551 static gl_list_iterator_t
552 gl_tree_iterator (gl_list_t list)
554 gl_list_iterator_t result;
557 result.vtable = list->base.vtable;
559 /* Start node is the leftmost node. */
562 while (node->left != NULL)
565 /* End point is past the rightmost node. */
576 static gl_list_iterator_t
577 gl_tree_iterator_from_to (gl_list_t list, size_t start_index, size_t end_index)
579 size_t count = (list->root != NULL ? list->root->branch_size : 0);
580 gl_list_iterator_t result;
582 if (!(start_index <= end_index && end_index <= count))
583 /* Invalid arguments. */
585 result.vtable = list->base.vtable;
587 /* Start node is the node at position start_index. */
588 result.p = (start_index < count ? node_at (list->root, start_index) : NULL);
589 /* End point is the node at position end_index. */
590 result.q = (end_index < count ? node_at (list->root, end_index) : NULL);
601 gl_tree_iterator_next (gl_list_iterator_t *iterator,
602 const void **eltp, gl_list_node_t *nodep)
604 if (iterator->p != iterator->q)
606 gl_list_node_t node = (gl_list_node_t) iterator->p;
610 /* Advance to the next node. */
611 if (node->right != NULL)
614 while (node->left != NULL)
619 while (node->parent != NULL && node->parent->right == node)
631 gl_tree_iterator_free (gl_list_iterator_t *iterator)
635 /* ---------------------- Sorted gl_list_t Data Type ---------------------- */
637 static gl_list_node_t
638 gl_tree_sortedlist_search (gl_list_t list, gl_listelement_compar_fn compar,
643 for (node = list->root; node != NULL; )
645 int cmp = compar (node->value, elt);
653 /* We have an element equal to ELT. But we need the leftmost such
655 gl_list_node_t found = node;
657 for (; node != NULL; )
659 int cmp2 = compar (node->value, elt);
664 /* The list was not sorted. */
678 static gl_list_node_t
679 gl_tree_sortedlist_search_from_to (gl_list_t list,
680 gl_listelement_compar_fn compar,
681 size_t low, size_t high,
687 && high <= (list->root != NULL ? list->root->branch_size : 0)))
688 /* Invalid arguments. */
691 for (node = list->root; node != NULL; )
693 size_t left_branch_size =
694 (node->left != NULL ? node->left->branch_size : 0);
696 if (low > left_branch_size)
698 low -= left_branch_size + 1;
699 high -= left_branch_size + 1;
702 else if (high <= left_branch_size)
706 /* Here low <= left_branch_size < high. */
707 int cmp = compar (node->value, elt);
712 high -= left_branch_size + 1;
719 /* We have an element equal to ELT. But we need the leftmost
721 gl_list_node_t found = node;
723 for (; node != NULL; )
725 size_t left_branch_size2 =
726 (node->left != NULL ? node->left->branch_size : 0);
728 if (low > left_branch_size2)
730 low -= left_branch_size2 + 1;
735 /* Here low <= left_branch_size2. */
736 int cmp2 = compar (node->value, elt);
744 /* The list was not sorted. */
761 gl_tree_sortedlist_indexof (gl_list_t list, gl_listelement_compar_fn compar,
767 for (node = list->root, position = 0; node != NULL; )
769 int cmp = compar (node->value, elt);
773 if (node->left != NULL)
774 position += node->left->branch_size;
782 /* We have an element equal to ELT. But we need the leftmost such
784 size_t found_position =
785 position + (node->left != NULL ? node->left->branch_size : 0);
787 for (; node != NULL; )
789 int cmp2 = compar (node->value, elt);
793 if (node->left != NULL)
794 position += node->left->branch_size;
799 /* The list was not sorted. */
805 + (node->left != NULL ? node->left->branch_size : 0);
809 return found_position;
816 gl_tree_sortedlist_indexof_from_to (gl_list_t list,
817 gl_listelement_compar_fn compar,
818 size_t low, size_t high,
825 && high <= (list->root != NULL ? list->root->branch_size : 0)))
826 /* Invalid arguments. */
829 for (node = list->root, position = 0; node != NULL; )
831 size_t left_branch_size =
832 (node->left != NULL ? node->left->branch_size : 0);
834 if (low > left_branch_size)
836 low -= left_branch_size + 1;
837 high -= left_branch_size + 1;
838 position += left_branch_size + 1;
841 else if (high <= left_branch_size)
845 /* Here low <= left_branch_size < high. */
846 int cmp = compar (node->value, elt);
851 high -= left_branch_size + 1;
852 position += left_branch_size + 1;
859 /* We have an element equal to ELT. But we need the leftmost
861 size_t found_position =
862 position + (node->left != NULL ? node->left->branch_size : 0);
864 for (; node != NULL; )
866 size_t left_branch_size2 =
867 (node->left != NULL ? node->left->branch_size : 0);
869 if (low > left_branch_size2)
871 low -= left_branch_size2 + 1;
876 /* Here low <= left_branch_size2. */
877 int cmp2 = compar (node->value, elt);
881 position += left_branch_size2 + 1;
885 /* The list was not sorted. */
889 found_position = position + left_branch_size2;
894 return found_position;
901 static gl_list_node_t
902 gl_tree_sortedlist_nx_add (gl_list_t list, gl_listelement_compar_fn compar,
905 gl_list_node_t node = list->root;
908 return gl_tree_nx_add_first (list, elt);
912 int cmp = compar (node->value, elt);
916 if (node->right == NULL)
917 return gl_tree_nx_add_after (list, node, elt);
922 if (node->left == NULL)
923 return gl_tree_nx_add_before (list, node, elt);
927 return gl_tree_nx_add_before (list, node, elt);
932 gl_tree_sortedlist_remove (gl_list_t list, gl_listelement_compar_fn compar,
935 gl_list_node_t node = gl_tree_sortedlist_search (list, compar, elt);
937 return gl_tree_remove_node (list, node);