1 /* Sequential list data type implemented by a binary tree.
2 Copyright (C) 2006-2007 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_next_node (gl_list_t list, gl_list_node_t node)
59 if (node->right != NULL)
62 while (node->left != NULL)
67 while (node->parent != NULL && node->parent->right == node)
75 gl_tree_previous_node (gl_list_t list, gl_list_node_t node)
77 if (node->left != NULL)
80 while (node->right != NULL)
85 while (node->parent != NULL && node->parent->left == node)
92 /* Return the node at the given position < gl_tree_size (list). */
93 static inline gl_list_node_t
94 node_at (gl_list_node_t root, size_t position)
96 /* Here we know that root != NULL. */
97 gl_list_node_t node = root;
101 if (node->left != NULL)
103 if (position < node->left->branch_size)
108 position -= node->left->branch_size;
119 gl_tree_get_at (gl_list_t list, size_t position)
121 gl_list_node_t node = list->root;
123 if (!(node != NULL && position < node->branch_size))
124 /* Invalid argument. */
126 node = node_at (node, position);
130 static gl_list_node_t
131 gl_tree_set_at (gl_list_t list, size_t position, const void *elt)
133 gl_list_node_t node = list->root;
135 if (!(node != NULL && position < node->branch_size))
136 /* Invalid argument. */
138 node = node_at (node, position);
140 if (elt != node->value)
142 size_t new_hashcode =
143 (list->base.hashcode_fn != NULL
144 ? list->base.hashcode_fn (elt)
145 : (size_t)(uintptr_t) elt);
147 if (new_hashcode != node->h.hashcode)
149 remove_from_bucket (list, node);
151 node->h.hashcode = new_hashcode;
152 add_to_bucket (list, node);
165 static gl_list_node_t
166 gl_tree_search_from_to (gl_list_t list, size_t start_index, size_t end_index,
169 if (!(start_index <= end_index
170 && end_index <= (list->root != NULL ? list->root->branch_size : 0)))
171 /* Invalid arguments. */
174 gl_listelement_equals_fn equals = list->base.equals_fn;
175 /* Iterate across all elements. */
176 gl_list_node_t node = list->root;
178 iterstack_item_t *stack_ptr = &stack[0];
181 if (start_index == 0)
183 /* Consider all elements. */
186 /* Descend on left branch. */
191 stack_ptr->node = node;
192 stack_ptr->rightp = 0;
196 /* Climb up again. */
199 if (stack_ptr == &stack[0])
202 if (!stack_ptr->rightp)
205 node = stack_ptr->node;
206 /* Test against current element. */
207 if (equals != NULL ? equals (elt, node->value) : elt == node->value)
210 if (index >= end_index)
212 /* Descend on right branch. */
213 stack_ptr->rightp = 1;
220 /* Consider only elements at indices >= start_index.
221 In this case, rightp contains the difference between the start_index
222 for the parent node and the one for the child node (0 when the child
223 node is the parent's left child, > 0 when the child is the parent's
227 /* Descend on left branch. */
232 if (node->branch_size <= start_index)
234 stack_ptr->node = node;
235 stack_ptr->rightp = 0;
239 /* Climb up again. */
242 if (stack_ptr == &stack[0])
245 if (!stack_ptr->rightp)
247 start_index += stack_ptr->rightp;
249 node = stack_ptr->node;
251 size_t left_branch_size1 =
252 (node->left != NULL ? node->left->branch_size : 0) + 1;
253 if (start_index < left_branch_size1)
255 /* Test against current element. */
256 if (equals != NULL ? equals (elt, node->value) : elt == node->value)
258 /* Now that we have considered all indices < left_branch_size1,
259 we can increment start_index. */
260 start_index = left_branch_size1;
263 if (index >= end_index)
265 /* Descend on right branch. */
266 start_index -= left_branch_size1;
267 stack_ptr->rightp = left_branch_size1;
277 gl_tree_indexof_from_to (gl_list_t list, size_t start_index, size_t end_index,
280 if (!(start_index <= end_index
281 && end_index <= (list->root != NULL ? list->root->branch_size : 0)))
282 /* Invalid arguments. */
285 gl_listelement_equals_fn equals = list->base.equals_fn;
286 /* Iterate across all elements. */
287 gl_list_node_t node = list->root;
289 iterstack_item_t *stack_ptr = &stack[0];
292 if (start_index == 0)
294 /* Consider all elements. */
297 /* Descend on left branch. */
302 stack_ptr->node = node;
303 stack_ptr->rightp = 0;
307 /* Climb up again. */
310 if (stack_ptr == &stack[0])
313 if (!stack_ptr->rightp)
316 node = stack_ptr->node;
317 /* Test against current element. */
318 if (equals != NULL ? equals (elt, node->value) : elt == node->value)
321 if (index >= end_index)
323 /* Descend on right branch. */
324 stack_ptr->rightp = 1;
331 /* Consider only elements at indices >= start_index.
332 In this case, rightp contains the difference between the start_index
333 for the parent node and the one for the child node (0 when the child
334 node is the parent's left child, > 0 when the child is the parent's
338 /* Descend on left branch. */
343 if (node->branch_size <= start_index)
345 stack_ptr->node = node;
346 stack_ptr->rightp = 0;
350 /* Climb up again. */
353 if (stack_ptr == &stack[0])
356 if (!stack_ptr->rightp)
358 start_index += stack_ptr->rightp;
360 node = stack_ptr->node;
362 size_t left_branch_size1 =
363 (node->left != NULL ? node->left->branch_size : 0) + 1;
364 if (start_index < left_branch_size1)
366 /* Test against current element. */
367 if (equals != NULL ? equals (elt, node->value) : elt == node->value)
369 /* Now that we have considered all indices < left_branch_size1,
370 we can increment start_index. */
371 start_index = left_branch_size1;
374 if (index >= end_index)
376 /* Descend on right branch. */
377 start_index -= left_branch_size1;
378 stack_ptr->rightp = left_branch_size1;
389 static gl_list_node_t
390 gl_tree_add_at (gl_list_t list, size_t position, const void *elt)
392 size_t count = (list->root != NULL ? list->root->branch_size : 0);
394 if (!(position <= count))
395 /* Invalid argument. */
397 if (position == count)
398 return gl_tree_add_last (list, elt);
400 return gl_tree_add_before (list, node_at (list->root, position), elt);
404 gl_tree_remove_at (gl_list_t list, size_t position)
406 gl_list_node_t node = list->root;
408 if (!(node != NULL && position < node->branch_size))
409 /* Invalid argument. */
411 node = node_at (node, position);
412 return gl_tree_remove_node (list, node);
416 gl_tree_remove (gl_list_t list, const void *elt)
418 if (list->root != NULL)
420 gl_list_node_t node =
421 gl_tree_search_from_to (list, 0, list->root->branch_size, elt);
424 return gl_tree_remove_node (list, node);
432 gl_tree_list_free (gl_list_t list)
434 /* Iterate across all elements in post-order. */
435 gl_list_node_t node = list->root;
437 iterstack_item_t *stack_ptr = &stack[0];
441 /* Descend on left branch. */
446 stack_ptr->node = node;
447 stack_ptr->rightp = false;
451 /* Climb up again. */
454 if (stack_ptr == &stack[0])
457 node = stack_ptr->node;
458 if (!stack_ptr->rightp)
460 /* Free the current node. */
461 if (list->base.dispose_fn != NULL)
462 list->base.dispose_fn (node->value);
465 /* Descend on right branch. */
466 stack_ptr->rightp = true;
476 /* --------------------- gl_list_iterator_t Data Type --------------------- */
478 static gl_list_iterator_t
479 gl_tree_iterator (gl_list_t list)
481 gl_list_iterator_t result;
484 result.vtable = list->base.vtable;
486 /* Start node is the leftmost node. */
489 while (node->left != NULL)
492 /* End point is past the rightmost node. */
503 static gl_list_iterator_t
504 gl_tree_iterator_from_to (gl_list_t list, size_t start_index, size_t end_index)
506 size_t count = (list->root != NULL ? list->root->branch_size : 0);
507 gl_list_iterator_t result;
509 if (!(start_index <= end_index && end_index <= count))
510 /* Invalid arguments. */
512 result.vtable = list->base.vtable;
514 /* Start node is the node at position start_index. */
515 result.p = (start_index < count ? node_at (list->root, start_index) : NULL);
516 /* End point is the node at position end_index. */
517 result.q = (end_index < count ? node_at (list->root, end_index) : NULL);
528 gl_tree_iterator_next (gl_list_iterator_t *iterator,
529 const void **eltp, gl_list_node_t *nodep)
531 if (iterator->p != iterator->q)
533 gl_list_node_t node = (gl_list_node_t) iterator->p;
537 /* Advance to the next node. */
538 if (node->right != NULL)
541 while (node->left != NULL)
546 while (node->parent != NULL && node->parent->right == node)
558 gl_tree_iterator_free (gl_list_iterator_t *iterator)
562 /* ---------------------- Sorted gl_list_t Data Type ---------------------- */
564 static gl_list_node_t
565 gl_tree_sortedlist_search (gl_list_t list, gl_listelement_compar_fn compar,
570 for (node = list->root; node != NULL; )
572 int cmp = compar (node->value, elt);
580 /* We have an element equal to ELT. But we need the leftmost such
582 gl_list_node_t found = node;
584 for (; node != NULL; )
586 int cmp2 = compar (node->value, elt);
591 /* The list was not sorted. */
605 static gl_list_node_t
606 gl_tree_sortedlist_search_from_to (gl_list_t list,
607 gl_listelement_compar_fn compar,
608 size_t low, size_t high,
614 && high <= (list->root != NULL ? list->root->branch_size : 0)))
615 /* Invalid arguments. */
618 for (node = list->root; node != NULL; )
620 size_t left_branch_size =
621 (node->left != NULL ? node->left->branch_size : 0);
623 if (low > left_branch_size)
625 low -= left_branch_size + 1;
626 high -= left_branch_size + 1;
629 else if (high <= left_branch_size)
633 /* Here low <= left_branch_size < high. */
634 int cmp = compar (node->value, elt);
639 high -= left_branch_size + 1;
646 /* We have an element equal to ELT. But we need the leftmost
648 gl_list_node_t found = node;
650 for (; node != NULL; )
652 size_t left_branch_size2 =
653 (node->left != NULL ? node->left->branch_size : 0);
655 if (low > left_branch_size2)
657 low -= left_branch_size2 + 1;
662 /* Here low <= left_branch_size2. */
663 int cmp2 = compar (node->value, elt);
671 /* The list was not sorted. */
688 gl_tree_sortedlist_indexof (gl_list_t list, gl_listelement_compar_fn compar,
694 for (node = list->root, position = 0; node != NULL; )
696 int cmp = compar (node->value, elt);
700 if (node->left != NULL)
701 position += node->left->branch_size;
709 /* We have an element equal to ELT. But we need the leftmost such
711 size_t found_position =
712 position + (node->left != NULL ? node->left->branch_size : 0);
714 for (; node != NULL; )
716 int cmp2 = compar (node->value, elt);
720 if (node->left != NULL)
721 position += node->left->branch_size;
726 /* The list was not sorted. */
732 + (node->left != NULL ? node->left->branch_size : 0);
736 return found_position;
743 gl_tree_sortedlist_indexof_from_to (gl_list_t list,
744 gl_listelement_compar_fn compar,
745 size_t low, size_t high,
752 && high <= (list->root != NULL ? list->root->branch_size : 0)))
753 /* Invalid arguments. */
756 for (node = list->root, position = 0; node != NULL; )
758 size_t left_branch_size =
759 (node->left != NULL ? node->left->branch_size : 0);
761 if (low > left_branch_size)
763 low -= left_branch_size + 1;
764 high -= left_branch_size + 1;
765 position += left_branch_size + 1;
768 else if (high <= left_branch_size)
772 /* Here low <= left_branch_size < high. */
773 int cmp = compar (node->value, elt);
778 high -= left_branch_size + 1;
779 position += left_branch_size + 1;
786 /* We have an element equal to ELT. But we need the leftmost
788 size_t found_position =
789 position + (node->left != NULL ? node->left->branch_size : 0);
791 for (; node != NULL; )
793 size_t left_branch_size2 =
794 (node->left != NULL ? node->left->branch_size : 0);
796 if (low > left_branch_size2)
798 low -= left_branch_size2 + 1;
803 /* Here low <= left_branch_size2. */
804 int cmp2 = compar (node->value, elt);
808 position += left_branch_size2 + 1;
812 /* The list was not sorted. */
816 found_position = position + left_branch_size2;
821 return found_position;
828 static gl_list_node_t
829 gl_tree_sortedlist_add (gl_list_t list, gl_listelement_compar_fn compar,
832 gl_list_node_t node = list->root;
835 return gl_tree_add_first (list, elt);
839 int cmp = compar (node->value, elt);
843 if (node->right == NULL)
844 return gl_tree_add_after (list, node, elt);
849 if (node->left == NULL)
850 return gl_tree_add_before (list, node, elt);
854 return gl_tree_add_before (list, node, elt);
859 gl_tree_sortedlist_remove (gl_list_t list, gl_listelement_compar_fn compar,
862 gl_list_node_t node = gl_tree_sortedlist_search (list, compar, elt);
864 return gl_tree_remove_node (list, node);