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 (gl_list_t list, const void *elt)
169 gl_listelement_equals_fn equals = list->base.equals_fn;
170 /* Iterate across all elements. */
171 gl_list_node_t node = list->root;
173 iterstack_item_t *stack_ptr = &stack[0];
177 /* Descend on left branch. */
182 stack_ptr->node = node;
183 stack_ptr->rightp = false;
187 /* Climb up again. */
190 if (stack_ptr == &stack[0])
193 if (!stack_ptr->rightp)
196 node = stack_ptr->node;
197 /* Test against current element. */
198 if (equals != NULL ? equals (elt, node->value) : elt == node->value)
200 /* Descend on right branch. */
201 stack_ptr->rightp = true;
208 gl_tree_indexof (gl_list_t list, const void *elt)
210 gl_listelement_equals_fn equals = list->base.equals_fn;
211 /* Iterate across all elements. */
212 gl_list_node_t node = list->root;
214 iterstack_item_t *stack_ptr = &stack[0];
219 /* Descend on left branch. */
224 stack_ptr->node = node;
225 stack_ptr->rightp = false;
229 /* Climb up again. */
232 if (stack_ptr == &stack[0])
235 if (!stack_ptr->rightp)
238 node = stack_ptr->node;
239 /* Test against current element. */
240 if (equals != NULL ? equals (elt, node->value) : elt == node->value)
243 /* Descend on right branch. */
244 stack_ptr->rightp = true;
252 static gl_list_node_t
253 gl_tree_add_at (gl_list_t list, size_t position, const void *elt)
255 size_t count = (list->root != NULL ? list->root->branch_size : 0);
257 if (!(position <= count))
258 /* Invalid argument. */
260 if (position == count)
261 return gl_tree_add_last (list, elt);
263 return gl_tree_add_before (list, node_at (list->root, position), elt);
267 gl_tree_remove_at (gl_list_t list, size_t position)
269 gl_list_node_t node = list->root;
271 if (!(node != NULL && position < node->branch_size))
272 /* Invalid argument. */
274 node = node_at (node, position);
275 return gl_tree_remove_node (list, node);
279 gl_tree_remove (gl_list_t list, const void *elt)
281 gl_list_node_t node = gl_tree_search (list, elt);
284 return gl_tree_remove_node (list, node);
292 gl_tree_list_free (gl_list_t list)
294 /* Iterate across all elements in post-order. */
295 gl_list_node_t node = list->root;
297 iterstack_item_t *stack_ptr = &stack[0];
301 /* Descend on left branch. */
306 stack_ptr->node = node;
307 stack_ptr->rightp = false;
311 /* Climb up again. */
314 if (stack_ptr == &stack[0])
317 node = stack_ptr->node;
318 if (!stack_ptr->rightp)
320 /* Free the current node. */
323 /* Descend on right branch. */
324 stack_ptr->rightp = true;
334 /* --------------------- gl_list_iterator_t Data Type --------------------- */
336 static gl_list_iterator_t
337 gl_tree_iterator (gl_list_t list)
339 gl_list_iterator_t result;
342 result.vtable = list->base.vtable;
344 /* Start node is the leftmost node. */
347 while (node->left != NULL)
350 /* End point is past the rightmost node. */
356 static gl_list_iterator_t
357 gl_tree_iterator_from_to (gl_list_t list, size_t start_index, size_t end_index)
359 size_t count = (list->root != NULL ? list->root->branch_size : 0);
360 gl_list_iterator_t result;
362 if (!(start_index <= end_index && end_index <= count))
363 /* Invalid arguments. */
365 result.vtable = list->base.vtable;
367 /* Start node is the node at position start_index. */
368 result.p = (start_index < count ? node_at (list->root, start_index) : NULL);
369 /* End point is the node at position end_index. */
370 result.q = (end_index < count ? node_at (list->root, end_index) : NULL);
376 gl_tree_iterator_next (gl_list_iterator_t *iterator,
377 const void **eltp, gl_list_node_t *nodep)
379 if (iterator->p != iterator->q)
381 gl_list_node_t node = (gl_list_node_t) iterator->p;
385 /* Advance to the next node. */
386 if (node->right != NULL)
389 while (node->left != NULL)
394 while (node->parent != NULL && node->parent->right == node)
406 gl_tree_iterator_free (gl_list_iterator_t *iterator)
410 /* ---------------------- Sorted gl_list_t Data Type ---------------------- */
412 static gl_list_node_t
413 gl_tree_sortedlist_search (gl_list_t list, gl_listelement_compar_fn compar,
418 for (node = list->root; node != NULL; )
420 int cmp = compar (node->value, elt);
428 /* We have an element equal to ELT. But we need the leftmost such
430 gl_list_node_t found = node;
432 for (; node != NULL; )
434 int cmp2 = compar (node->value, elt);
439 /* The list was not sorted. */
454 gl_tree_sortedlist_indexof (gl_list_t list, gl_listelement_compar_fn compar,
460 for (node = list->root, position = 0; node != NULL; )
462 int cmp = compar (node->value, elt);
466 if (node->left != NULL)
467 position += node->left->branch_size;
475 /* We have an element equal to ELT. But we need the leftmost such
477 size_t found_position =
478 position + (node->left != NULL ? node->left->branch_size : 0);
480 for (; node != NULL; )
482 int cmp2 = compar (node->value, elt);
486 if (node->left != NULL)
487 position += node->left->branch_size;
492 /* The list was not sorted. */
498 + (node->left != NULL ? node->left->branch_size : 0);
502 return found_position;
508 static gl_list_node_t
509 gl_tree_sortedlist_add (gl_list_t list, gl_listelement_compar_fn compar,
512 gl_list_node_t node = list->root;
515 return gl_tree_add_first (list, elt);
519 int cmp = compar (node->value, elt);
523 if (node->right == NULL)
524 return gl_tree_add_after (list, node, elt);
529 if (node->left == NULL)
530 return gl_tree_add_before (list, node, elt);
534 return gl_tree_add_before (list, node, elt);
539 gl_tree_sortedlist_remove (gl_list_t list, gl_listelement_compar_fn compar,
542 gl_list_node_t node = gl_tree_sortedlist_search (list, compar, elt);
544 return gl_tree_remove_node (list, node);