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_avltree_list.c, gl_rbtree_list.c,
20 gl_avltreehash_list.c, gl_rbtreehash_list.c. */
23 gl_tree_create_empty (gl_list_implementation_t implementation,
24 gl_listelement_equals_fn equals_fn,
25 gl_listelement_hashcode_fn hashcode_fn,
26 bool allow_duplicates)
28 struct gl_list_impl *list =
29 (struct gl_list_impl *) xmalloc (sizeof (struct gl_list_impl));
31 list->base.vtable = implementation;
32 list->base.equals_fn = equals_fn;
33 list->base.hashcode_fn = hashcode_fn;
34 list->base.allow_duplicates = allow_duplicates;
36 list->table_size = 11;
38 (gl_hash_entry_t *) xzalloc (list->table_size * sizeof (gl_hash_entry_t));
46 gl_tree_size (gl_list_t list)
48 return (list->root != NULL ? list->root->branch_size : 0);
52 gl_tree_node_value (gl_list_t list, gl_list_node_t node)
58 gl_tree_next_node (gl_list_t list, gl_list_node_t node)
60 if (node->right != NULL)
63 while (node->left != NULL)
68 while (node->parent != NULL && node->parent->right == node)
76 gl_tree_previous_node (gl_list_t list, gl_list_node_t node)
78 if (node->left != NULL)
81 while (node->right != NULL)
86 while (node->parent != NULL && node->parent->left == node)
93 /* Return the node at the given position < gl_tree_size (list). */
94 static inline gl_list_node_t
95 node_at (gl_list_node_t root, size_t position)
97 /* Here we know that root != NULL. */
98 gl_list_node_t node = root;
102 if (node->left != NULL)
104 if (position < node->left->branch_size)
109 position -= node->left->branch_size;
120 gl_tree_get_at (gl_list_t list, size_t position)
122 gl_list_node_t node = list->root;
124 if (!(node != NULL && position < node->branch_size))
125 /* Invalid argument. */
127 node = node_at (node, position);
131 static gl_list_node_t
132 gl_tree_set_at (gl_list_t list, size_t position, const void *elt)
134 gl_list_node_t node = list->root;
136 if (!(node != NULL && position < node->branch_size))
137 /* Invalid argument. */
139 node = node_at (node, position);
141 if (elt != node->value)
143 size_t new_hashcode =
144 (list->base.hashcode_fn != NULL
145 ? list->base.hashcode_fn (elt)
146 : (size_t)(uintptr_t) elt);
148 if (new_hashcode != node->h.hashcode)
150 remove_from_bucket (list, node);
152 node->h.hashcode = new_hashcode;
153 add_to_bucket (list, node);
166 static gl_list_node_t
167 gl_tree_search_from_to (gl_list_t list, size_t start_index, size_t end_index,
170 if (!(start_index <= end_index
171 && end_index <= (list->root != NULL ? list->root->branch_size : 0)))
172 /* Invalid arguments. */
175 gl_listelement_equals_fn equals = list->base.equals_fn;
176 /* Iterate across all elements. */
177 gl_list_node_t node = list->root;
179 iterstack_item_t *stack_ptr = &stack[0];
182 if (start_index == 0)
184 /* Consider all elements. */
187 /* Descend on left branch. */
192 stack_ptr->node = node;
193 stack_ptr->rightp = 0;
197 /* Climb up again. */
200 if (stack_ptr == &stack[0])
203 if (!stack_ptr->rightp)
206 node = stack_ptr->node;
207 /* Test against current element. */
208 if (equals != NULL ? equals (elt, node->value) : elt == node->value)
211 if (index >= end_index)
213 /* Descend on right branch. */
214 stack_ptr->rightp = 1;
221 /* Consider only elements at indices >= start_index.
222 In this case, rightp contains the difference between the start_index
223 for the parent node and the one for the child node (0 when the child
224 node is the parent's left child, > 0 when the child is the parent's
228 /* Descend on left branch. */
233 if (node->branch_size <= start_index)
235 stack_ptr->node = node;
236 stack_ptr->rightp = 0;
240 /* Climb up again. */
243 if (stack_ptr == &stack[0])
246 if (!stack_ptr->rightp)
248 start_index += stack_ptr->rightp;
250 node = stack_ptr->node;
252 size_t left_branch_size1 =
253 (node->left != NULL ? node->left->branch_size : 0) + 1;
254 if (start_index < left_branch_size1)
256 /* Test against current element. */
257 if (equals != NULL ? equals (elt, node->value) : elt == node->value)
259 /* Now that we have considered all indices < left_branch_size1,
260 we can increment start_index. */
261 start_index = left_branch_size1;
264 if (index >= end_index)
266 /* Descend on right branch. */
267 start_index -= left_branch_size1;
268 stack_ptr->rightp = left_branch_size1;
278 gl_tree_indexof_from_to (gl_list_t list, size_t start_index, size_t end_index,
281 if (!(start_index <= end_index
282 && end_index <= (list->root != NULL ? list->root->branch_size : 0)))
283 /* Invalid arguments. */
286 gl_listelement_equals_fn equals = list->base.equals_fn;
287 /* Iterate across all elements. */
288 gl_list_node_t node = list->root;
290 iterstack_item_t *stack_ptr = &stack[0];
293 if (start_index == 0)
295 /* Consider all elements. */
298 /* Descend on left branch. */
303 stack_ptr->node = node;
304 stack_ptr->rightp = 0;
308 /* Climb up again. */
311 if (stack_ptr == &stack[0])
314 if (!stack_ptr->rightp)
317 node = stack_ptr->node;
318 /* Test against current element. */
319 if (equals != NULL ? equals (elt, node->value) : elt == node->value)
322 if (index >= end_index)
324 /* Descend on right branch. */
325 stack_ptr->rightp = 1;
332 /* Consider only elements at indices >= start_index.
333 In this case, rightp contains the difference between the start_index
334 for the parent node and the one for the child node (0 when the child
335 node is the parent's left child, > 0 when the child is the parent's
339 /* Descend on left branch. */
344 if (node->branch_size <= start_index)
346 stack_ptr->node = node;
347 stack_ptr->rightp = 0;
351 /* Climb up again. */
354 if (stack_ptr == &stack[0])
357 if (!stack_ptr->rightp)
359 start_index += stack_ptr->rightp;
361 node = stack_ptr->node;
363 size_t left_branch_size1 =
364 (node->left != NULL ? node->left->branch_size : 0) + 1;
365 if (start_index < left_branch_size1)
367 /* Test against current element. */
368 if (equals != NULL ? equals (elt, node->value) : elt == node->value)
370 /* Now that we have considered all indices < left_branch_size1,
371 we can increment start_index. */
372 start_index = left_branch_size1;
375 if (index >= end_index)
377 /* Descend on right branch. */
378 start_index -= left_branch_size1;
379 stack_ptr->rightp = left_branch_size1;
390 static gl_list_node_t
391 gl_tree_add_at (gl_list_t list, size_t position, const void *elt)
393 size_t count = (list->root != NULL ? list->root->branch_size : 0);
395 if (!(position <= count))
396 /* Invalid argument. */
398 if (position == count)
399 return gl_tree_add_last (list, elt);
401 return gl_tree_add_before (list, node_at (list->root, position), elt);
405 gl_tree_remove_at (gl_list_t list, size_t position)
407 gl_list_node_t node = list->root;
409 if (!(node != NULL && position < node->branch_size))
410 /* Invalid argument. */
412 node = node_at (node, position);
413 return gl_tree_remove_node (list, node);
417 gl_tree_remove (gl_list_t list, const void *elt)
419 if (list->root != NULL)
421 gl_list_node_t node =
422 gl_tree_search_from_to (list, 0, list->root->branch_size, elt);
425 return gl_tree_remove_node (list, node);
433 gl_tree_list_free (gl_list_t list)
435 /* Iterate across all elements in post-order. */
436 gl_list_node_t node = list->root;
438 iterstack_item_t *stack_ptr = &stack[0];
442 /* Descend on left branch. */
447 stack_ptr->node = node;
448 stack_ptr->rightp = false;
452 /* Climb up again. */
455 if (stack_ptr == &stack[0])
458 node = stack_ptr->node;
459 if (!stack_ptr->rightp)
461 /* Free the current node. */
464 /* Descend on right branch. */
465 stack_ptr->rightp = true;
475 /* --------------------- gl_list_iterator_t Data Type --------------------- */
477 static gl_list_iterator_t
478 gl_tree_iterator (gl_list_t list)
480 gl_list_iterator_t result;
483 result.vtable = list->base.vtable;
485 /* Start node is the leftmost node. */
488 while (node->left != NULL)
491 /* End point is past the rightmost node. */
502 static gl_list_iterator_t
503 gl_tree_iterator_from_to (gl_list_t list, size_t start_index, size_t end_index)
505 size_t count = (list->root != NULL ? list->root->branch_size : 0);
506 gl_list_iterator_t result;
508 if (!(start_index <= end_index && end_index <= count))
509 /* Invalid arguments. */
511 result.vtable = list->base.vtable;
513 /* Start node is the node at position start_index. */
514 result.p = (start_index < count ? node_at (list->root, start_index) : NULL);
515 /* End point is the node at position end_index. */
516 result.q = (end_index < count ? node_at (list->root, end_index) : NULL);
527 gl_tree_iterator_next (gl_list_iterator_t *iterator,
528 const void **eltp, gl_list_node_t *nodep)
530 if (iterator->p != iterator->q)
532 gl_list_node_t node = (gl_list_node_t) iterator->p;
536 /* Advance to the next node. */
537 if (node->right != NULL)
540 while (node->left != NULL)
545 while (node->parent != NULL && node->parent->right == node)
557 gl_tree_iterator_free (gl_list_iterator_t *iterator)
561 /* ---------------------- Sorted gl_list_t Data Type ---------------------- */
563 static gl_list_node_t
564 gl_tree_sortedlist_search (gl_list_t list, gl_listelement_compar_fn compar,
569 for (node = list->root; node != NULL; )
571 int cmp = compar (node->value, elt);
579 /* We have an element equal to ELT. But we need the leftmost such
581 gl_list_node_t found = node;
583 for (; node != NULL; )
585 int cmp2 = compar (node->value, elt);
590 /* The list was not sorted. */
604 static gl_list_node_t
605 gl_tree_sortedlist_search_from_to (gl_list_t list,
606 gl_listelement_compar_fn compar,
607 size_t low, size_t high,
613 && high <= (list->root != NULL ? list->root->branch_size : 0)))
614 /* Invalid arguments. */
617 for (node = list->root; node != NULL; )
619 size_t left_branch_size =
620 (node->left != NULL ? node->left->branch_size : 0);
622 if (low > left_branch_size)
624 low -= left_branch_size + 1;
625 high -= left_branch_size + 1;
628 else if (high <= left_branch_size)
632 /* Here low <= left_branch_size < high. */
633 int cmp = compar (node->value, elt);
638 high -= left_branch_size + 1;
645 /* We have an element equal to ELT. But we need the leftmost
647 gl_list_node_t found = node;
649 for (; node != NULL; )
651 size_t left_branch_size2 =
652 (node->left != NULL ? node->left->branch_size : 0);
654 if (low > left_branch_size2)
656 low -= left_branch_size2 + 1;
661 /* Here low <= left_branch_size2. */
662 int cmp2 = compar (node->value, elt);
670 /* The list was not sorted. */
687 gl_tree_sortedlist_indexof (gl_list_t list, gl_listelement_compar_fn compar,
693 for (node = list->root, position = 0; node != NULL; )
695 int cmp = compar (node->value, elt);
699 if (node->left != NULL)
700 position += node->left->branch_size;
708 /* We have an element equal to ELT. But we need the leftmost such
710 size_t found_position =
711 position + (node->left != NULL ? node->left->branch_size : 0);
713 for (; node != NULL; )
715 int cmp2 = compar (node->value, elt);
719 if (node->left != NULL)
720 position += node->left->branch_size;
725 /* The list was not sorted. */
731 + (node->left != NULL ? node->left->branch_size : 0);
735 return found_position;
742 gl_tree_sortedlist_indexof_from_to (gl_list_t list,
743 gl_listelement_compar_fn compar,
744 size_t low, size_t high,
751 && high <= (list->root != NULL ? list->root->branch_size : 0)))
752 /* Invalid arguments. */
755 for (node = list->root, position = 0; node != NULL; )
757 size_t left_branch_size =
758 (node->left != NULL ? node->left->branch_size : 0);
760 if (low > left_branch_size)
762 low -= left_branch_size + 1;
763 high -= left_branch_size + 1;
764 position += left_branch_size + 1;
767 else if (high <= left_branch_size)
771 /* Here low <= left_branch_size < high. */
772 int cmp = compar (node->value, elt);
777 high -= left_branch_size + 1;
778 position += left_branch_size + 1;
785 /* We have an element equal to ELT. But we need the leftmost
787 size_t found_position =
788 position + (node->left != NULL ? node->left->branch_size : 0);
790 for (; node != NULL; )
792 size_t left_branch_size2 =
793 (node->left != NULL ? node->left->branch_size : 0);
795 if (low > left_branch_size2)
797 low -= left_branch_size2 + 1;
802 /* Here low <= left_branch_size2. */
803 int cmp2 = compar (node->value, elt);
807 position += left_branch_size2 + 1;
811 /* The list was not sorted. */
815 found_position = position + left_branch_size2;
820 return found_position;
827 static gl_list_node_t
828 gl_tree_sortedlist_add (gl_list_t list, gl_listelement_compar_fn compar,
831 gl_list_node_t node = list->root;
834 return gl_tree_add_first (list, elt);
838 int cmp = compar (node->value, elt);
842 if (node->right == NULL)
843 return gl_tree_add_after (list, node, elt);
848 if (node->left == NULL)
849 return gl_tree_add_before (list, node, elt);
853 return gl_tree_add_before (list, node, elt);
858 gl_tree_sortedlist_remove (gl_list_t list, gl_listelement_compar_fn compar,
861 gl_list_node_t node = gl_tree_sortedlist_search (list, compar, elt);
863 return gl_tree_remove_node (list, node);