1 /* Sequential list data type implemented by a hash table with 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_avltreehash_list.c and gl_rbtreehash_list.c. */
22 gl_tree_search_from_to (gl_list_t list, size_t start_index, size_t end_index,
25 if (!(start_index <= end_index
26 && end_index <= (list->root != NULL ? list->root->branch_size : 0)))
27 /* Invalid arguments. */
31 (list->base.hashcode_fn != NULL
32 ? list->base.hashcode_fn (elt)
33 : (size_t)(uintptr_t) elt);
34 size_t bucket = hashcode % list->table_size;
35 gl_listelement_equals_fn equals = list->base.equals_fn;
36 gl_hash_entry_t entry;
38 if (list->base.allow_duplicates)
40 for (entry = list->table[bucket]; entry != NULL; entry = entry->hash_next)
41 if (entry->hashcode == hashcode)
43 if (((struct gl_multiple_nodes *) entry)->magic == MULTIPLE_NODES_MAGIC)
45 /* An entry representing multiple nodes. */
46 gl_oset_t nodes = ((struct gl_multiple_nodes *) entry)->nodes;
47 /* The first node is interesting. */
48 gl_list_node_t node = gl_oset_first (nodes);
49 if (equals != NULL ? equals (elt, node->value) : elt == node->value)
51 /* All nodes in the entry are equal to the given ELT. */
54 /* We have to return only the one at the minimal
55 position, and this is the first one in the ordered
57 if (end_index == list->root->branch_size
58 || node_position (node) < end_index)
63 /* We have to return only the one at the minimal
64 position >= start_index. */
66 if (gl_oset_search_atleast (nodes,
67 compare_position_threshold,
68 (void *)(uintptr_t)start_index,
71 node = (gl_list_node_t) elt;
72 if (end_index == list->root->branch_size
73 || node_position (node) < end_index)
82 /* An entry representing a single node. */
83 gl_list_node_t node = (struct gl_list_node_impl *) entry;
84 if (equals != NULL ? equals (elt, node->value) : elt == node->value)
86 bool position_in_bounds;
87 if (start_index == 0 && end_index == list->root->branch_size)
88 position_in_bounds = true;
91 size_t position = node_position (node);
93 (position >= start_index && position < end_index);
95 if (position_in_bounds)
104 /* If no duplicates are allowed, multiple nodes are not needed. */
105 for (entry = list->table[bucket]; entry != NULL; entry = entry->hash_next)
106 if (entry->hashcode == hashcode)
108 gl_list_node_t node = (struct gl_list_node_impl *) entry;
109 if (equals != NULL ? equals (elt, node->value) : elt == node->value)
111 bool position_in_bounds;
112 if (start_index == 0 && end_index == list->root->branch_size)
113 position_in_bounds = true;
116 size_t position = node_position (node);
118 (position >= start_index && position < end_index);
120 if (position_in_bounds)
132 gl_tree_indexof_from_to (gl_list_t list, size_t start_index, size_t end_index,
135 gl_list_node_t node =
136 gl_tree_search_from_to (list, start_index, end_index, elt);
139 return node_position (node);
145 gl_tree_list_free (gl_list_t list)
147 if (list->base.allow_duplicates)
149 /* Free the ordered sets in the hash buckets. */
152 for (i = list->table_size; i > 0; )
154 gl_hash_entry_t entry = list->table[--i];
156 while (entry != NULL)
158 gl_hash_entry_t next = entry->hash_next;
160 if (((struct gl_multiple_nodes *) entry)->magic == MULTIPLE_NODES_MAGIC)
162 gl_oset_t nodes = ((struct gl_multiple_nodes *) entry)->nodes;
164 gl_oset_free (nodes);
173 /* Iterate across all elements in post-order. */
175 gl_list_node_t node = list->root;
177 iterstack_item_t *stack_ptr = &stack[0];
181 /* Descend on left branch. */
186 stack_ptr->node = node;
187 stack_ptr->rightp = false;
191 /* Climb up again. */
194 if (stack_ptr == &stack[0])
197 node = stack_ptr->node;
198 if (!stack_ptr->rightp)
200 /* Free the current node. */
203 /* Descend on right branch. */
204 stack_ptr->rightp = true;