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 /* Hash table entry representing the same value at more than one position. */
21 struct gl_multiple_nodes
22 {
23 struct gl_hash_entry h; /* hash table entry fields; must be first */
24 void *magic; /* used to distinguish from single node */
25 gl_oset_t nodes; /* set of nodes, sorted by position */
26 };
27 /* A value that cannot occur at the corresponding field (->left) in
28 gl_list_node_impl. */
29 #define MULTIPLE_NODES_MAGIC (void *) -1
30
31 /* Returns the position of the given node in the tree. */
32 static size_t _GL_ATTRIBUTE_PURE
33 node_position (gl_list_node_t node)
34 {
35 size_t position = 0;
36
37 if (node->left != NULL)
38 position += node->left->branch_size;
39 for (;;)
40 {
41 gl_list_node_t parent = node->parent;
42
43 if (parent == NULL)
44 return position;
45 /* position is now relative to the subtree of node. */
46 if (parent->right == node)
47 {
48 position += 1;
49 if (parent->left != NULL)
50 position += parent->left->branch_size;
51 }
52 /* position is now relative to the subtree of parent. */
53 node = parent;
54 }
55 }
56
57 /* Compares two nodes by their position in the tree. */
58 static int _GL_ATTRIBUTE_PURE
59 compare_by_position (const void *x1, const void *x2)
60 {
61 gl_list_node_t node1 = (gl_list_node_t) x1;
62 gl_list_node_t node2 = (gl_list_node_t) x2;
63 size_t position1 = node_position (node1);
64 size_t position2 = node_position (node2);
65
66 return (position1 > position2 ? 1 :
67 position1 < position2 ? -1 : 0);
68 }
69
70 /* Compares a node's position in the tree with a given threshold. */
71 static bool _GL_ATTRIBUTE_PURE
72 compare_position_threshold (const void *x, const void *threshold)
73 {
74 gl_list_node_t node = (gl_list_node_t) x;
75 size_t position = node_position (node);
76 return (position >= (uintptr_t)threshold);
77 }
78
79 /* Returns the first element of a non-empty ordered set of nodes. */
80 static gl_list_node_t
81 gl_oset_first (gl_oset_t set)
82 {
83 gl_oset_iterator_t iter = gl_oset_iterator (set);
84 const void *first;
85
86 if (!gl_oset_iterator_next (&iter, &first))
87 abort ();
88 gl_oset_iterator_free (&iter);
89 return (gl_list_node_t) first;
90 }
91
92 /* Adds a node to the hash table structure.
93 If duplicates are allowed, this function performs in average time
94 O((log n)^2): gl_oset_nx_add may need to add an element to an ordered set
95 of size O(n), needing O(log n) comparison function calls. The comparison
96 function is compare_by_position, which is O(log n) worst-case.
97 If duplicates are forbidden, this function is O(1).
98 Return 0 upon success, -1 upon out-of-memory. */
99 static int
100 add_to_bucket (gl_list_t list, gl_list_node_t new_node)
101 {
102 size_t bucket = new_node->h.hashcode % list->table_size;
103
104 /* If no duplicates are allowed, multiple nodes are not needed. */
105 if (list->base.allow_duplicates)
106 {
107 size_t hashcode = new_node->h.hashcode;
108 const void *value = new_node->value;
109 gl_listelement_equals_fn equals = list->base.equals_fn;
110 gl_hash_entry_t *entryp;
111
112 for (entryp = &list->table[bucket]; *entryp != NULL; entryp = &(*entryp)->hash_next)
113 {
114 gl_hash_entry_t entry = *entryp;
115
116 if (entry->hashcode == hashcode)
117 {
118 if (((struct gl_multiple_nodes *) entry)->magic == MULTIPLE_NODES_MAGIC)
119 {
120 /* An entry representing multiple nodes. */
121 gl_oset_t nodes = ((struct gl_multiple_nodes *) entry)->nodes;
122 /* Only the first node is interesting. */
123 gl_list_node_t node = gl_oset_first (nodes);
124 if (equals != NULL ? equals (value, node->value) : value == node->value)
125 {
126 /* Found already multiple nodes with the same value.
127 Add the new_node to it. */
128 return gl_oset_nx_add (nodes, new_node);
129 }
130 }
131 else
132 {
133 /* An entry representing a single node. */
134 gl_list_node_t node = (struct gl_list_node_impl *) entry;
135 if (equals != NULL ? equals (value, node->value) : value == node->value)
136 {
137 /* Found already a node with the same value. Turn it
138 into an ordered set, and add new_node to it. */
139 gl_oset_t nodes;
140 struct gl_multiple_nodes *multi_entry;
141
142 nodes =
143 gl_oset_nx_create_empty (OSET_TREE_FLAVOR,
144 compare_by_position, NULL);
145 if (nodes == NULL)
146 return -1;
147
148 if (gl_oset_nx_add (nodes, node) < 0)
149 goto fail;
150 if (gl_oset_nx_add (nodes, new_node) < 0)
151 goto fail;
152
153 multi_entry =
154 (struct gl_multiple_nodes *) malloc (sizeof (struct gl_multiple_nodes));
155 if (multi_entry == NULL)
156 goto fail;
157 multi_entry->h.hash_next = entry->hash_next;
158 multi_entry->h.hashcode = entry->hashcode;
159 multi_entry->magic = MULTIPLE_NODES_MAGIC;
160 multi_entry->nodes = nodes;
161 *entryp = &multi_entry->h;
162 return 0;
163
164 fail:
165 gl_oset_free (nodes);
166 return -1;
167 }
168 }
169 }
170 }
171 }
172 /* If no duplicates are allowed, multiple nodes are not needed. */
173 new_node->h.hash_next = list->table[bucket];
174 list->table[bucket] = &new_node->h;
175 return 0;
176 }
177 /* Tell GCC that the likely return value is 0. */
178 #define add_to_bucket(list,node) \
179 __builtin_expect ((add_to_bucket) (list, node), 0)
180
181 /* Removes a node from the hash table structure.
182 If duplicates are allowed, this function performs in average time
183 O((log n)^2): gl_oset_remove may need to remove an element from an ordered
184 set of size O(n), needing O(log n) comparison function calls. The
185 comparison function is compare_by_position, which is O(log n) worst-case.
186 If duplicates are forbidden, this function is O(1) on average. */
187 static void
188 remove_from_bucket (gl_list_t list, gl_list_node_t old_node)
189 {
190 size_t bucket = old_node->h.hashcode % list->table_size;
191
192 if (list->base.allow_duplicates)
193 {
194 size_t hashcode = old_node->h.hashcode;
195 const void *value = old_node->value;
196 gl_listelement_equals_fn equals = list->base.equals_fn;
197 gl_hash_entry_t *entryp;
198
199 for (entryp = &list->table[bucket]; ; entryp = &(*entryp)->hash_next)
200 {
201 gl_hash_entry_t entry = *entryp;
202
203 if (entry == &old_node->h)
204 {
205 /* Found old_node as a single node in the bucket. Remove it. */
206 *entryp = old_node->h.hash_next;
207 break;
208 }
209 if (entry == NULL)
210 /* node is not in the right bucket. Did the hash codes
211 change inadvertently? */
212 abort ();
213 if (((struct gl_multiple_nodes *) entry)->magic == MULTIPLE_NODES_MAGIC
214 && entry->hashcode == hashcode)
215 {
216 /* An entry representing multiple nodes. */
217 gl_oset_t nodes = ((struct gl_multiple_nodes *) entry)->nodes;
218 /* Only the first node is interesting. */
219 gl_list_node_t node = gl_oset_first (nodes);
220 if (equals != NULL ? equals (value, node->value) : value == node->value)
221 {
222 /* Found multiple nodes with the same value.
223 old_node must be one of them. Remove it. */
224 if (!gl_oset_remove (nodes, old_node))
225 abort ();
226 if (gl_oset_size (nodes) == 1)
227 {
228 /* Replace a one-element set with a single node. */
229 node = gl_oset_first (nodes);
230 node->h.hash_next = entry->hash_next;
231 *entryp = &node->h;
232 gl_oset_free (nodes);
233 free (entry);
234 }
235 break;
236 }
237 }
238 }
239 }
240 else
241 {
242 /* If no duplicates are allowed, multiple nodes are not needed. */
243 gl_hash_entry_t *entryp;
244
245 for (entryp = &list->table[bucket]; ; entryp = &(*entryp)->hash_next)
246 {
247 if (*entryp == &old_node->h)
248 {
249 *entryp = old_node->h.hash_next;
250 break;
251 }
252 if (*entryp == NULL)
253 /* node is not in the right bucket. Did the hash codes
254 change inadvertently? */
255 abort ();
256 }
257 }
258 }
259
260 /* Builds up the hash table during initialization: Stores all the nodes of
261 list->root in the hash table.
262 Returns 0 upon success, -1 upon out-of-memory. */
263 static int
264 add_nodes_to_buckets (gl_list_t list)
265 {
266 /* Iterate across all nodes. */
267 gl_list_node_t node = list->root;
268 iterstack_t stack;
269 iterstack_item_t *stack_ptr = &stack[0];
270
271 for (;;)
272 {
273 /* Descend on left branch. */
274 for (;;)
275 {
276 if (node == NULL)
277 break;
278 stack_ptr->node = node;
279 stack_ptr->rightp = false;
280 node = node->left;
281 stack_ptr++;
282 }
283 /* Climb up again. */
284 for (;;)
285 {
286 if (stack_ptr == &stack[0])
287 goto done;
288 stack_ptr--;
289 if (!stack_ptr->rightp)
290 break;
291 }
292 node = stack_ptr->node;
293 /* Add the current node to the hash table. */
294 node->h.hashcode =
295 (list->base.hashcode_fn != NULL
296 ? list->base.hashcode_fn (node->value)
297 : (size_t)(uintptr_t) node->value);
298 if (add_to_bucket (list, node) < 0)
299 goto fail;
300 /* Descend on right branch. */
301 stack_ptr->rightp = true;
302 node = node->right;
303 stack_ptr++;
304 }
305 done:
306 return 0;
307
308 fail:
309 /* Undo everything. */
310 for (;;)
311 {
312 /* Descend on left branch. */
313 stack_ptr->rightp = false;
314 node = node->left;
315 stack_ptr++;
316 /* Descend on right branch. */
317 for (;;)
318 {
319 if (node == NULL)
320 break;
321 stack_ptr->node = node;
322 stack_ptr->rightp = true;
323 node = node->right;
324 stack_ptr++;
325 }
326 /* Climb up again. */
327 for (;;)
328 {
329 if (stack_ptr == &stack[0])
330 goto fail_done;
331 stack_ptr--;
332 if (stack_ptr->rightp)
333 break;
334 }
335 node = stack_ptr->node;
336 /* Remove the current node from the hash table. */
337 remove_from_bucket (list, node);
338 }
339 fail_done:
340 return -1;
341 }
342 /* Tell GCC that the likely return value is 0. */
343 #if (__GNUC__ >= 3) || (__clang_major__ >= 4)
344 # define add_nodes_to_buckets(list) \
345 __builtin_expect ((add_nodes_to_buckets) (list), 0)
346 #endif