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. */
21 /* Hash table entry representing the same value at more than one position. */
22 struct gl_multiple_nodes
24 struct gl_hash_entry h; /* hash table entry fields; must be first */
25 void *magic; /* used to distinguish from single node */
26 gl_oset_t nodes; /* set of nodes, sorted by position */
28 /* A value that cannot occur at the corresponding field (->left) in
30 #define MULTIPLE_NODES_MAGIC (void *) -1
32 /* Resize the hash table if needed, after list->count was incremented. */
34 hash_resize_after_add (gl_list_t list)
36 size_t count = (list->root != 0 ? list->root->branch_size : 0);
37 size_t estimate = xsum (count, count / 2); /* 1.5 * count */
38 if (estimate > list->table_size)
39 hash_resize (list, estimate);
42 /* Return the position of the given node in the tree. */
44 node_position (gl_list_node_t node)
48 if (node->left != NULL)
49 position += node->left->branch_size;
52 gl_list_node_t parent = node->parent;
56 /* position is now relative to the subtree of node. */
57 if (parent->right == node)
60 if (parent->left != NULL)
61 position += parent->left->branch_size;
63 /* position is now relative to the subtree of parent. */
68 /* Compares two nodes by their position in the tree. */
70 compare_by_position (const void *x1, const void *x2)
72 gl_list_node_t node1 = (gl_list_node_t) x1;
73 gl_list_node_t node2 = (gl_list_node_t) x2;
74 size_t position1 = node_position (node1);
75 size_t position2 = node_position (node2);
77 return (position1 > position2 ? 1 :
78 position1 < position2 ? -1 : 0);
81 /* Return the first element of a non-empty ordered set of nodes. */
82 static inline gl_list_node_t
83 gl_oset_first (gl_oset_t set)
85 gl_oset_iterator_t iter = gl_oset_iterator (set);
88 if (!gl_oset_iterator_next (&iter, &first))
90 gl_oset_iterator_free (&iter);
91 return (gl_list_node_t) first;
94 /* Add a node to the hash table structure.
95 If duplicates are allowed, this function performs in average time
96 O((log n)^2): gl_oset_add may need to add an element to an ordered set of
97 size O(n), needing O(log n) comparison function calls. The comparison
98 function is compare_by_position, which is O(log n) worst-case.
99 If duplicates are forbidden, this function is O(1). */
101 add_to_bucket (gl_list_t list, gl_list_node_t new_node)
103 size_t index = new_node->h.hashcode % list->table_size;
105 /* If no duplicates are allowed, multiple nodes are not needed. */
106 if (list->base.allow_duplicates)
108 size_t hashcode = new_node->h.hashcode;
109 const void *value = new_node->value;
110 gl_listelement_equals_fn equals = list->base.equals_fn;
111 gl_hash_entry_t *entryp;
113 for (entryp = &list->table[index]; *entryp != NULL; entryp = &(*entryp)->hash_next)
115 gl_hash_entry_t entry = *entryp;
117 if (entry->hashcode == hashcode)
119 if (((struct gl_multiple_nodes *) entry)->magic == MULTIPLE_NODES_MAGIC)
121 /* An entry representing multiple nodes. */
122 gl_oset_t nodes = ((struct gl_multiple_nodes *) entry)->nodes;
123 /* Only the first node is interesting. */
124 gl_list_node_t node = gl_oset_first (nodes);
125 if (equals != NULL ? equals (value, node->value) : value == node->value)
127 /* Found already multiple nodes with the same value.
128 Add the new_node to it. */
129 gl_oset_add (nodes, new_node);
135 /* An entry representing a single node. */
136 gl_list_node_t node = (struct gl_list_node_impl *) entry;
137 if (equals != NULL ? equals (value, node->value) : value == node->value)
139 /* Found already a node with the same value. Turn it
140 into an ordered set, and add new_node to it. */
142 struct gl_multiple_nodes *multi_entry;
145 gl_oset_create_empty (OSET_TREE_FLAVOR,
146 compare_by_position);
148 gl_oset_add (nodes, node);
149 gl_oset_add (nodes, new_node);
152 (struct gl_multiple_nodes *) xmalloc (sizeof (struct gl_multiple_nodes));
153 multi_entry->h.hash_next = entry->hash_next;
154 multi_entry->h.hashcode = entry->hashcode;
155 multi_entry->magic = MULTIPLE_NODES_MAGIC;
156 multi_entry->nodes = nodes;
157 *entryp = &multi_entry->h;
164 /* If no duplicates are allowed, multiple nodes are not needed. */
165 new_node->h.hash_next = list->table[index];
166 list->table[index] = &new_node->h;
169 /* Remove a node from the hash table structure.
170 If duplicates are allowed, this function performs in average time
171 O((log n)^2): gl_oset_remove may need to remove an element from an ordered
172 set of size O(n), needing O(log n) comparison function calls. The
173 comparison function is compare_by_position, which is O(log n) worst-case.
174 If duplicates are forbidden, this function is O(1) on average. */
176 remove_from_bucket (gl_list_t list, gl_list_node_t old_node)
178 size_t index = old_node->h.hashcode % list->table_size;
180 if (list->base.allow_duplicates)
182 size_t hashcode = old_node->h.hashcode;
183 const void *value = old_node->value;
184 gl_listelement_equals_fn equals = list->base.equals_fn;
185 gl_hash_entry_t *entryp;
187 for (entryp = &list->table[index]; ; entryp = &(*entryp)->hash_next)
189 gl_hash_entry_t entry = *entryp;
191 if (entry == &old_node->h)
193 /* Found old_node as a single node in the bucket. Remove it. */
194 *entryp = old_node->h.hash_next;
198 /* node is not in the right bucket. Did the hash codes
199 change inadvertently? */
201 if (((struct gl_multiple_nodes *) entry)->magic == MULTIPLE_NODES_MAGIC
202 && entry->hashcode == hashcode)
204 /* An entry representing multiple nodes. */
205 gl_oset_t nodes = ((struct gl_multiple_nodes *) entry)->nodes;
206 /* Only the first node is interesting. */
207 gl_list_node_t node = gl_oset_first (nodes);
208 if (equals != NULL ? equals (value, node->value) : value == node->value)
210 /* Found multiple nodes with the same value.
211 old_node must be one of them. Remove it. */
212 if (!gl_oset_remove (nodes, old_node))
214 if (gl_oset_size (nodes) == 1)
216 /* Replace a one-element set with a single node. */
217 node = gl_oset_first (nodes);
218 node->h.hash_next = entry->hash_next;
220 gl_oset_free (nodes);
230 /* If no duplicates are allowed, multiple nodes are not needed. */
231 gl_hash_entry_t *entryp;
233 for (entryp = &list->table[index]; ; entryp = &(*entryp)->hash_next)
235 if (*entryp == &old_node->h)
237 *entryp = old_node->h.hash_next;
241 /* node is not in the right bucket. Did the hash codes
242 change inadvertently? */
248 /* Build up the hash table during initialization: Store all the nodes of
249 list->root in the hash table. */
251 add_nodes_to_buckets (gl_list_t list)
253 /* Iterate across all nodes. */
254 gl_list_node_t node = list->root;
256 iterstack_item_t *stack_ptr = &stack[0];
260 /* Descend on left branch. */
265 stack_ptr->node = node;
266 stack_ptr->rightp = false;
270 /* Climb up again. */
273 if (stack_ptr == &stack[0])
276 if (!stack_ptr->rightp)
279 node = stack_ptr->node;
280 /* Add the current node to the hash table. */
282 (list->base.hashcode_fn != NULL
283 ? list->base.hashcode_fn (node->value)
284 : (size_t)(uintptr_t) node->value);
285 add_to_bucket (list, node);
286 /* Descend on right branch. */
287 stack_ptr->rightp = true;