1 /* Sequential list data type implemented by a hash table with a binary tree.
2 Copyright (C) 2006-2007, 2009-2010 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_avltreehash_list.c and gl_rbtreehash_list.c. */
21 gl_tree_search_from_to (gl_list_t list, size_t start_index, size_t end_index,
24 if (!(start_index <= end_index
25 && end_index <= (list->root != NULL ? list->root->branch_size : 0)))
26 /* Invalid arguments. */
30 (list->base.hashcode_fn != NULL
31 ? list->base.hashcode_fn (elt)
32 : (size_t)(uintptr_t) elt);
33 size_t bucket = hashcode % list->table_size;
34 gl_listelement_equals_fn equals = list->base.equals_fn;
35 gl_hash_entry_t entry;
37 if (list->base.allow_duplicates)
39 for (entry = list->table[bucket]; entry != NULL; entry = entry->hash_next)
40 if (entry->hashcode == hashcode)
42 if (((struct gl_multiple_nodes *) entry)->magic == MULTIPLE_NODES_MAGIC)
44 /* An entry representing multiple nodes. */
45 gl_oset_t nodes = ((struct gl_multiple_nodes *) entry)->nodes;
46 /* The first node is interesting. */
47 gl_list_node_t node = gl_oset_first (nodes);
48 if (equals != NULL ? equals (elt, node->value) : elt == node->value)
50 /* All nodes in the entry are equal to the given ELT. */
53 /* We have to return only the one at the minimal
54 position, and this is the first one in the ordered
56 if (end_index == list->root->branch_size
57 || node_position (node) < end_index)
62 /* We have to return only the one at the minimal
63 position >= start_index. */
65 if (gl_oset_search_atleast (nodes,
66 compare_position_threshold,
67 (void *)(uintptr_t)start_index,
70 node = (gl_list_node_t) elt;
71 if (end_index == list->root->branch_size
72 || node_position (node) < end_index)
81 /* An entry representing a single node. */
82 gl_list_node_t node = (struct gl_list_node_impl *) entry;
83 if (equals != NULL ? equals (elt, node->value) : elt == node->value)
85 bool position_in_bounds;
86 if (start_index == 0 && end_index == list->root->branch_size)
87 position_in_bounds = true;
90 size_t position = node_position (node);
92 (position >= start_index && position < end_index);
94 if (position_in_bounds)
103 /* If no duplicates are allowed, multiple nodes are not needed. */
104 for (entry = list->table[bucket]; entry != NULL; entry = entry->hash_next)
105 if (entry->hashcode == hashcode)
107 gl_list_node_t node = (struct gl_list_node_impl *) entry;
108 if (equals != NULL ? equals (elt, node->value) : elt == node->value)
110 bool position_in_bounds;
111 if (start_index == 0 && end_index == list->root->branch_size)
112 position_in_bounds = true;
115 size_t position = node_position (node);
117 (position >= start_index && position < end_index);
119 if (position_in_bounds)
131 gl_tree_indexof_from_to (gl_list_t list, size_t start_index, size_t end_index,
134 gl_list_node_t node =
135 gl_tree_search_from_to (list, start_index, end_index, elt);
138 return node_position (node);
144 gl_tree_list_free (gl_list_t list)
146 if (list->base.allow_duplicates)
148 /* Free the ordered sets in the hash buckets. */
151 for (i = list->table_size; i > 0; )
153 gl_hash_entry_t entry = list->table[--i];
155 while (entry != NULL)
157 gl_hash_entry_t next = entry->hash_next;
159 if (((struct gl_multiple_nodes *) entry)->magic == MULTIPLE_NODES_MAGIC)
161 gl_oset_t nodes = ((struct gl_multiple_nodes *) entry)->nodes;
163 gl_oset_free (nodes);
172 /* Iterate across all elements in post-order. */
174 gl_list_node_t node = list->root;
176 iterstack_item_t *stack_ptr = &stack[0];
180 /* Descend on left branch. */
185 stack_ptr->node = node;
186 stack_ptr->rightp = false;
190 /* Climb up again. */
193 if (stack_ptr == &stack[0])
196 node = stack_ptr->node;
197 if (!stack_ptr->rightp)
199 /* Free the current node. */
200 if (list->base.dispose_fn != NULL)
201 list->base.dispose_fn (node->value);
204 /* Descend on right branch. */
205 stack_ptr->rightp = true;