1 /* Sequential list data type implemented by a hash table with a binary tree.
2 Copyright (C) 2006-2007, 2009-2017 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. */
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. */
188 #define add_to_bucket(list,node) \
189 __builtin_expect ((add_to_bucket) (list, node), 0)
191 /* Remove a node from the hash table structure.
192 If duplicates are allowed, this function performs in average time
193 O((log n)^2): gl_oset_remove may need to remove an element from an ordered
194 set of size O(n), needing O(log n) comparison function calls. The
195 comparison function is compare_by_position, which is O(log n) worst-case.
196 If duplicates are forbidden, this function is O(1) on average. */
198 remove_from_bucket (gl_list_t list
, gl_list_node_t old_node
)
200 size_t bucket
= old_node
->h
.hashcode
% list
->table_size
;
202 if (list
->base
.allow_duplicates
)
204 size_t hashcode
= old_node
->h
.hashcode
;
205 const void *value
= old_node
->value
;
206 gl_listelement_equals_fn equals
= list
->base
.equals_fn
;
207 gl_hash_entry_t
*entryp
;
209 for (entryp
= &list
->table
[bucket
]; ; entryp
= &(*entryp
)->hash_next
)
211 gl_hash_entry_t entry
= *entryp
;
213 if (entry
== &old_node
->h
)
215 /* Found old_node as a single node in the bucket. Remove it. */
216 *entryp
= old_node
->h
.hash_next
;
220 /* node is not in the right bucket. Did the hash codes
221 change inadvertently? */
223 if (((struct gl_multiple_nodes
*) entry
)->magic
== MULTIPLE_NODES_MAGIC
224 && entry
->hashcode
== hashcode
)
226 /* An entry representing multiple nodes. */
227 gl_oset_t nodes
= ((struct gl_multiple_nodes
*) entry
)->nodes
;
228 /* Only the first node is interesting. */
229 gl_list_node_t node
= gl_oset_first (nodes
);
230 if (equals
!= NULL
? equals (value
, node
->value
) : value
== node
->value
)
232 /* Found multiple nodes with the same value.
233 old_node must be one of them. Remove it. */
234 if (!gl_oset_remove (nodes
, old_node
))
236 if (gl_oset_size (nodes
) == 1)
238 /* Replace a one-element set with a single node. */
239 node
= gl_oset_first (nodes
);
240 node
->h
.hash_next
= entry
->hash_next
;
242 gl_oset_free (nodes
);
252 /* If no duplicates are allowed, multiple nodes are not needed. */
253 gl_hash_entry_t
*entryp
;
255 for (entryp
= &list
->table
[bucket
]; ; entryp
= &(*entryp
)->hash_next
)
257 if (*entryp
== &old_node
->h
)
259 *entryp
= old_node
->h
.hash_next
;
263 /* node is not in the right bucket. Did the hash codes
264 change inadvertently? */
270 /* Build up the hash table during initialization: Store all the nodes of
271 list->root in the hash table.
272 Return 0 upon success, -1 upon out-of-memory. */
274 add_nodes_to_buckets (gl_list_t list
)
276 /* Iterate across all nodes. */
277 gl_list_node_t node
= list
->root
;
279 iterstack_item_t
*stack_ptr
= &stack
[0];
283 /* Descend on left branch. */
288 stack_ptr
->node
= node
;
289 stack_ptr
->rightp
= false;
293 /* Climb up again. */
296 if (stack_ptr
== &stack
[0])
299 if (!stack_ptr
->rightp
)
302 node
= stack_ptr
->node
;
303 /* Add the current node to the hash table. */
305 (list
->base
.hashcode_fn
!= NULL
306 ? list
->base
.hashcode_fn (node
->value
)
307 : (size_t)(uintptr_t) node
->value
);
308 if (add_to_bucket (list
, node
) < 0)
310 /* Descend on right branch. */
311 stack_ptr
->rightp
= true;
319 /* Undo everything. */
322 /* Descend on left branch. */
323 stack_ptr
->rightp
= false;
326 /* Descend on right branch. */
331 stack_ptr
->node
= node
;
332 stack_ptr
->rightp
= true;
336 /* Climb up again. */
339 if (stack_ptr
== &stack
[0])
342 if (stack_ptr
->rightp
)
345 node
= stack_ptr
->node
;
346 /* Remove the current node from the hash table. */
347 remove_from_bucket (list
, node
);
352 /* Tell GCC that the likely return value is 0. */
354 # define add_nodes_to_buckets(list) \
355 __builtin_expect ((add_nodes_to_buckets) (list), 0)