1 /* Sequential list data type implemented by a hash table with a binary tree.
2 Copyright (C) 2006-2007, 2009-2012 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. */
20 /* Hash table entry representing the same value at more than one position. */
21 struct gl_multiple_nodes
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 */
27 /* A value that cannot occur at the corresponding field (->left) in
29 #define MULTIPLE_NODES_MAGIC (void *) -1
31 /* Resize the hash table if needed, after list->count was incremented. */
33 hash_resize_after_add (gl_list_t list)
35 size_t count = (list->root != 0 ? list->root->branch_size : 0);
36 size_t estimate = xsum (count, count / 2); /* 1.5 * count */
37 if (estimate > list->table_size)
38 hash_resize (list, estimate);
41 /* Return the position of the given node in the tree. */
43 node_position (gl_list_node_t node)
47 if (node->left != NULL)
48 position += node->left->branch_size;
51 gl_list_node_t parent = node->parent;
55 /* position is now relative to the subtree of node. */
56 if (parent->right == node)
59 if (parent->left != NULL)
60 position += parent->left->branch_size;
62 /* position is now relative to the subtree of parent. */
67 /* Compares two nodes by their position in the tree. */
69 compare_by_position (const void *x1, const void *x2)
71 gl_list_node_t node1 = (gl_list_node_t) x1;
72 gl_list_node_t node2 = (gl_list_node_t) x2;
73 size_t position1 = node_position (node1);
74 size_t position2 = node_position (node2);
76 return (position1 > position2 ? 1 :
77 position1 < position2 ? -1 : 0);
80 /* Compares a node's position in the tree with a given threshold. */
82 compare_position_threshold (const void *x, const void *threshold)
84 gl_list_node_t node = (gl_list_node_t) x;
85 size_t position = node_position (node);
86 return (position >= (uintptr_t)threshold);
89 /* Return the first element of a non-empty ordered set of nodes. */
90 static inline gl_list_node_t
91 gl_oset_first (gl_oset_t set)
93 gl_oset_iterator_t iter = gl_oset_iterator (set);
96 if (!gl_oset_iterator_next (&iter, &first))
98 gl_oset_iterator_free (&iter);
99 return (gl_list_node_t) first;
102 /* Add a node to the hash table structure.
103 If duplicates are allowed, this function performs in average time
104 O((log n)^2): gl_oset_nx_add may need to add an element to an ordered set
105 of size O(n), needing O(log n) comparison function calls. The comparison
106 function is compare_by_position, which is O(log n) worst-case.
107 If duplicates are forbidden, this function is O(1).
108 Return 0 upon success, -1 upon out-of-memory. */
110 add_to_bucket (gl_list_t list, gl_list_node_t new_node)
112 size_t bucket = new_node->h.hashcode % list->table_size;
114 /* If no duplicates are allowed, multiple nodes are not needed. */
115 if (list->base.allow_duplicates)
117 size_t hashcode = new_node->h.hashcode;
118 const void *value = new_node->value;
119 gl_listelement_equals_fn equals = list->base.equals_fn;
120 gl_hash_entry_t *entryp;
122 for (entryp = &list->table[bucket]; *entryp != NULL; entryp = &(*entryp)->hash_next)
124 gl_hash_entry_t entry = *entryp;
126 if (entry->hashcode == hashcode)
128 if (((struct gl_multiple_nodes *) entry)->magic == MULTIPLE_NODES_MAGIC)
130 /* An entry representing multiple nodes. */
131 gl_oset_t nodes = ((struct gl_multiple_nodes *) entry)->nodes;
132 /* Only the first node is interesting. */
133 gl_list_node_t node = gl_oset_first (nodes);
134 if (equals != NULL ? equals (value, node->value) : value == node->value)
136 /* Found already multiple nodes with the same value.
137 Add the new_node to it. */
138 return gl_oset_nx_add (nodes, new_node);
143 /* An entry representing a single node. */
144 gl_list_node_t node = (struct gl_list_node_impl *) entry;
145 if (equals != NULL ? equals (value, node->value) : value == node->value)
147 /* Found already a node with the same value. Turn it
148 into an ordered set, and add new_node to it. */
150 struct gl_multiple_nodes *multi_entry;
153 gl_oset_nx_create_empty (OSET_TREE_FLAVOR,
154 compare_by_position, NULL);
158 if (gl_oset_nx_add (nodes, node) < 0)
160 if (gl_oset_nx_add (nodes, new_node) < 0)
164 (struct gl_multiple_nodes *) malloc (sizeof (struct gl_multiple_nodes));
165 if (multi_entry == NULL)
167 multi_entry->h.hash_next = entry->hash_next;
168 multi_entry->h.hashcode = entry->hashcode;
169 multi_entry->magic = MULTIPLE_NODES_MAGIC;
170 multi_entry->nodes = nodes;
171 *entryp = &multi_entry->h;
175 gl_oset_free (nodes);
182 /* If no duplicates are allowed, multiple nodes are not needed. */
183 new_node->h.hash_next = list->table[bucket];
184 list->table[bucket] = &new_node->h;
187 /* Tell GCC that the likely return value is 0. */
189 # define add_to_bucket(list,node) \
190 __builtin_expect ((add_to_bucket) (list, node), 0)
193 /* Remove a node from the hash table structure.
194 If duplicates are allowed, this function performs in average time
195 O((log n)^2): gl_oset_remove may need to remove an element from an ordered
196 set of size O(n), needing O(log n) comparison function calls. The
197 comparison function is compare_by_position, which is O(log n) worst-case.
198 If duplicates are forbidden, this function is O(1) on average. */
200 remove_from_bucket (gl_list_t list, gl_list_node_t old_node)
202 size_t bucket = old_node->h.hashcode % list->table_size;
204 if (list->base.allow_duplicates)
206 size_t hashcode = old_node->h.hashcode;
207 const void *value = old_node->value;
208 gl_listelement_equals_fn equals = list->base.equals_fn;
209 gl_hash_entry_t *entryp;
211 for (entryp = &list->table[bucket]; ; entryp = &(*entryp)->hash_next)
213 gl_hash_entry_t entry = *entryp;
215 if (entry == &old_node->h)
217 /* Found old_node as a single node in the bucket. Remove it. */
218 *entryp = old_node->h.hash_next;
222 /* node is not in the right bucket. Did the hash codes
223 change inadvertently? */
225 if (((struct gl_multiple_nodes *) entry)->magic == MULTIPLE_NODES_MAGIC
226 && entry->hashcode == hashcode)
228 /* An entry representing multiple nodes. */
229 gl_oset_t nodes = ((struct gl_multiple_nodes *) entry)->nodes;
230 /* Only the first node is interesting. */
231 gl_list_node_t node = gl_oset_first (nodes);
232 if (equals != NULL ? equals (value, node->value) : value == node->value)
234 /* Found multiple nodes with the same value.
235 old_node must be one of them. Remove it. */
236 if (!gl_oset_remove (nodes, old_node))
238 if (gl_oset_size (nodes) == 1)
240 /* Replace a one-element set with a single node. */
241 node = gl_oset_first (nodes);
242 node->h.hash_next = entry->hash_next;
244 gl_oset_free (nodes);
254 /* If no duplicates are allowed, multiple nodes are not needed. */
255 gl_hash_entry_t *entryp;
257 for (entryp = &list->table[bucket]; ; entryp = &(*entryp)->hash_next)
259 if (*entryp == &old_node->h)
261 *entryp = old_node->h.hash_next;
265 /* node is not in the right bucket. Did the hash codes
266 change inadvertently? */
272 /* Build up the hash table during initialization: Store all the nodes of
273 list->root in the hash table.
274 Return 0 upon success, -1 upon out-of-memory. */
276 add_nodes_to_buckets (gl_list_t list)
278 /* Iterate across all nodes. */
279 gl_list_node_t node = list->root;
281 iterstack_item_t *stack_ptr = &stack[0];
285 /* Descend on left branch. */
290 stack_ptr->node = node;
291 stack_ptr->rightp = false;
295 /* Climb up again. */
298 if (stack_ptr == &stack[0])
301 if (!stack_ptr->rightp)
304 node = stack_ptr->node;
305 /* Add the current node to the hash table. */
307 (list->base.hashcode_fn != NULL
308 ? list->base.hashcode_fn (node->value)
309 : (size_t)(uintptr_t) node->value);
310 if (add_to_bucket (list, node) < 0)
312 /* Descend on right branch. */
313 stack_ptr->rightp = true;
321 /* Undo everything. */
324 /* Descend on left branch. */
325 stack_ptr->rightp = false;
328 /* Descend on right branch. */
333 stack_ptr->node = node;
334 stack_ptr->rightp = true;
338 /* Climb up again. */
341 if (stack_ptr == &stack[0])
344 if (stack_ptr->rightp)
347 node = stack_ptr->node;
348 /* Remove the current node from the hash table. */
349 remove_from_bucket (list, node);
354 /* Tell GCC that the likely return value is 0. */
356 # define add_nodes_to_buckets(list) \
357 __builtin_expect ((add_nodes_to_buckets) (list), 0)