1 /* Sequential list data type implemented by a hash table with a binary tree.
2 Copyright (C) 2006-2007, 2009-2021 Free Software Foundation, Inc.
3 Written by Bruno Haible <bruno@clisp.org>, 2006.
4
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.
9
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.
14
15 You should have received a copy of the GNU General Public License
16 along with this program. If not, see <https://www.gnu.org/licenses/>. */
17
18 /* Common code of gl_avltreehash_list.c and gl_rbtreehash_list.c. */
19
20 static gl_list_node_t
21 gl_tree_search_from_to (gl_list_t list, size_t start_index, size_t end_index,
22 const void *elt)
23 {
24 if (!(start_index <= end_index
25 && end_index <= (list->root != NULL ? list->root->branch_size : 0)))
26 /* Invalid arguments. */
27 abort ();
28 {
29 size_t hashcode =
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;
36
37 if (list->base.allow_duplicates)
38 {
39 for (entry = list->table[bucket]; entry != NULL; entry = entry->hash_next)
40 if (entry->hashcode == hashcode)
41 {
42 if (((struct gl_multiple_nodes *) entry)->magic == MULTIPLE_NODES_MAGIC)
43 {
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)
49 {
50 /* All nodes in the entry are equal to the given ELT. */
51 if (start_index == 0)
52 {
53 /* We have to return only the one at the minimal
54 position, and this is the first one in the ordered
55 set. */
56 if (end_index == list->root->branch_size
57 || node_position (node) < end_index)
58 return node;
59 }
60 else
61 {
62 /* We have to return only the one at the minimal
63 position >= start_index. */
64 const void *nodes_elt;
65 if (gl_oset_search_atleast (nodes,
66 compare_position_threshold,
67 (void *)(uintptr_t)start_index,
68 &nodes_elt))
69 {
70 node = (gl_list_node_t) nodes_elt;
71 if (end_index == list->root->branch_size
72 || node_position (node) < end_index)
73 return node;
74 }
75 }
76 break;
77 }
78 }
79 else
80 {
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)
84 {
85 bool position_in_bounds;
86 if (start_index == 0 && end_index == list->root->branch_size)
87 position_in_bounds = true;
88 else
89 {
90 size_t position = node_position (node);
91 position_in_bounds =
92 (position >= start_index && position < end_index);
93 }
94 if (position_in_bounds)
95 return node;
96 break;
97 }
98 }
99 }
100 }
101 else
102 {
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)
106 {
107 gl_list_node_t node = (struct gl_list_node_impl *) entry;
108 if (equals != NULL ? equals (elt, node->value) : elt == node->value)
109 {
110 bool position_in_bounds;
111 if (start_index == 0 && end_index == list->root->branch_size)
112 position_in_bounds = true;
113 else
114 {
115 size_t position = node_position (node);
116 position_in_bounds =
117 (position >= start_index && position < end_index);
118 }
119 if (position_in_bounds)
120 return node;
121 break;
122 }
123 }
124 }
125
126 return NULL;
127 }
128 }
129
130 static size_t
131 gl_tree_indexof_from_to (gl_list_t list, size_t start_index, size_t end_index,
132 const void *elt)
133 {
134 gl_list_node_t node =
135 gl_tree_search_from_to (list, start_index, end_index, elt);
136
137 if (node != NULL)
138 return node_position (node);
139 else
140 return (size_t)(-1);
141 }
142
143 static void
144 gl_tree_list_free (gl_list_t list)
145 {
146 if (list->base.allow_duplicates)
147 {
148 /* Free the ordered sets in the hash buckets. */
149 size_t i;
150
151 for (i = list->table_size; i > 0; )
152 {
153 gl_hash_entry_t entry = list->table[--i];
154
155 while (entry != NULL)
156 {
157 gl_hash_entry_t next = entry->hash_next;
158
159 if (((struct gl_multiple_nodes *) entry)->magic == MULTIPLE_NODES_MAGIC)
160 {
161 gl_oset_t nodes = ((struct gl_multiple_nodes *) entry)->nodes;
162
163 gl_oset_free (nodes);
164 free (entry);
165 }
166
167 entry = next;
168 }
169 }
170 }
171
172 /* Iterate across all elements in post-order. */
173 {
174 gl_list_node_t node = list->root;
175 iterstack_t stack;
176 iterstack_item_t *stack_ptr = &stack[0];
177
178 for (;;)
179 {
180 /* Descend on left branch. */
181 for (;;)
182 {
183 if (node == NULL)
184 break;
185 stack_ptr->node = node;
186 stack_ptr->rightp = false;
187 node = node->left;
188 stack_ptr++;
189 }
190 /* Climb up again. */
191 for (;;)
192 {
193 if (stack_ptr == &stack[0])
194 goto done_iterate;
195 stack_ptr--;
196 node = stack_ptr->node;
197 if (!stack_ptr->rightp)
198 break;
199 /* Free the current node. */
200 if (list->base.dispose_fn != NULL)
201 list->base.dispose_fn (node->value);
202 free (node);
203 }
204 /* Descend on right branch. */
205 stack_ptr->rightp = true;
206 node = node->right;
207 stack_ptr++;
208 }
209 }
210 done_iterate:
211 free (list->table);
212 free (list);
213 }