Line data Source code
1 : /*
2 : * Copyright (c) 2010, Andrea Mazzoleni. All rights reserved.
3 : *
4 : * Redistribution and use in source and binary forms, with or without
5 : * modification, are permitted provided that the following conditions
6 : * are met:
7 : *
8 : * 1. Redistributions of source code must retain the above copyright
9 : * notice, this list of conditions and the following disclaimer.
10 : *
11 : * 2. Redistributions in binary form must reproduce the above copyright
12 : * notice, this list of conditions and the following disclaimer in the
13 : * documentation and/or other materials provided with the distribution.
14 : *
15 : * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
16 : * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
17 : * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
18 : * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
19 : * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
20 : * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
21 : * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
22 : * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
23 : * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
24 : * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
25 : * POSSIBILITY OF SUCH DAMAGE.
26 : */
27 :
28 : #include "tommyhashdyn.h"
29 : #include "tommylist.h"
30 :
31 : /******************************************************************************/
32 : /* hashdyn */
33 :
34 10070 : TOMMY_API void tommy_hashdyn_init(tommy_hashdyn* hashdyn)
35 : {
36 : /* fixed initial size */
37 10070 : hashdyn->bucket_bit = TOMMY_HASHDYN_BIT;
38 10070 : hashdyn->bucket_max = (tommy_size_t)1 << hashdyn->bucket_bit;
39 10070 : hashdyn->bucket_mask = hashdyn->bucket_max - 1;
40 10070 : hashdyn->bucket = tommy_cast(tommy_hashdyn_node**, tommy_calloc(hashdyn->bucket_max, sizeof(tommy_hashdyn_node*)));
41 :
42 10070 : hashdyn->count = 0;
43 10070 : }
44 :
45 9736 : TOMMY_API void tommy_hashdyn_done(tommy_hashdyn* hashdyn)
46 : {
47 9736 : tommy_free(hashdyn->bucket);
48 9736 : }
49 :
50 : /**
51 : * Resize the bucket vector.
52 : */
53 44738 : static void tommy_hashdyn_resize(tommy_hashdyn* hashdyn, tommy_uint_t new_bucket_bit)
54 : {
55 : tommy_size_t bucket_bit;
56 : tommy_size_t bucket_max;
57 : tommy_size_t new_bucket_max;
58 : tommy_size_t new_bucket_mask;
59 : tommy_hashdyn_node** new_bucket;
60 :
61 44738 : bucket_bit = hashdyn->bucket_bit;
62 44738 : bucket_max = hashdyn->bucket_max;
63 :
64 44738 : new_bucket_max = (tommy_size_t)1 << new_bucket_bit;
65 44738 : new_bucket_mask = new_bucket_max - 1;
66 :
67 : /* allocate the new vector using malloc() and not calloc() */
68 : /* because data is fully initialized in the update process */
69 44738 : new_bucket = tommy_cast(tommy_hashdyn_node**, tommy_malloc(new_bucket_max * sizeof(tommy_hashdyn_node*)));
70 :
71 : /* reinsert all the elements */
72 44738 : if (new_bucket_bit > bucket_bit) {
73 : tommy_size_t i;
74 :
75 : /* grow */
76 34211515 : for (i = 0; i < bucket_max; ++i) {
77 : tommy_hashdyn_node* j;
78 :
79 : /* setup the new two buckets */
80 34166832 : new_bucket[i] = 0;
81 34166832 : new_bucket[i + bucket_max] = 0;
82 :
83 : /* reinsert the bucket */
84 34166832 : j = hashdyn->bucket[i];
85 51250248 : while (j) {
86 17083416 : tommy_hashdyn_node* j_next = j->next;
87 17083416 : tommy_size_t pos = j->index & new_bucket_mask;
88 17083416 : if (new_bucket[pos])
89 2009700 : tommy_list_insert_tail_not_empty(new_bucket[pos], j);
90 : else
91 15073716 : tommy_list_insert_first(&new_bucket[pos], j);
92 17083416 : j = j_next;
93 : }
94 : }
95 : } else {
96 : tommy_size_t i;
97 :
98 : /* shrink */
99 79335 : for (i = 0; i < new_bucket_max; ++i) {
100 : /* setup the new bucket with the lower bucket*/
101 79280 : new_bucket[i] = hashdyn->bucket[i];
102 :
103 : /* concat the upper bucket */
104 79280 : tommy_list_concat(&new_bucket[i], &hashdyn->bucket[i + new_bucket_max]);
105 : }
106 : }
107 :
108 44738 : tommy_free(hashdyn->bucket);
109 :
110 : /* setup */
111 44738 : hashdyn->bucket_bit = new_bucket_bit;
112 44738 : hashdyn->bucket_max = new_bucket_max;
113 44738 : hashdyn->bucket_mask = new_bucket_mask;
114 44738 : hashdyn->bucket = new_bucket;
115 44738 : }
116 :
117 : /**
118 : * Grow.
119 : */
120 14008562 : tommy_inline void hashdyn_grow_step(tommy_hashdyn* hashdyn)
121 : {
122 : /* grow if more than 50% full */
123 14008562 : if (hashdyn->count >= hashdyn->bucket_max / 2)
124 44683 : tommy_hashdyn_resize(hashdyn, hashdyn->bucket_bit + 1);
125 14008562 : }
126 :
127 : /**
128 : * Shrink.
129 : */
130 293846 : tommy_inline void hashdyn_shrink_step(tommy_hashdyn* hashdyn)
131 : {
132 : /* shrink if less than 12.5% full */
133 293846 : if (hashdyn->count <= hashdyn->bucket_max / 8 && hashdyn->bucket_bit > TOMMY_HASHDYN_BIT)
134 55 : tommy_hashdyn_resize(hashdyn, hashdyn->bucket_bit - 1);
135 293846 : }
136 :
137 14008562 : TOMMY_API void tommy_hashdyn_insert(tommy_hashdyn* hashdyn, tommy_hashdyn_node* node, void* data, tommy_hash_t hash)
138 : {
139 14008562 : tommy_size_t pos = hash & hashdyn->bucket_mask;
140 :
141 14008562 : tommy_list_insert_tail(&hashdyn->bucket[pos], node, data);
142 :
143 14008562 : node->index = hash;
144 :
145 14008562 : ++hashdyn->count;
146 :
147 14008562 : hashdyn_grow_step(hashdyn);
148 14008562 : }
149 :
150 293718 : TOMMY_API void* tommy_hashdyn_remove_existing(tommy_hashdyn* hashdyn, tommy_hashdyn_node* node)
151 : {
152 293718 : tommy_size_t pos = node->index & hashdyn->bucket_mask;
153 :
154 293718 : tommy_list_remove_existing(&hashdyn->bucket[pos], node);
155 :
156 293718 : --hashdyn->count;
157 :
158 293718 : hashdyn_shrink_step(hashdyn);
159 :
160 293718 : return node->data;
161 : }
162 :
163 256 : TOMMY_API void* tommy_hashdyn_remove(tommy_hashdyn* hashdyn, tommy_search_func* cmp, const void* cmp_arg, tommy_hash_t hash)
164 : {
165 256 : tommy_size_t pos = hash & hashdyn->bucket_mask;
166 256 : tommy_hashdyn_node* node = hashdyn->bucket[pos];
167 :
168 512 : while (node) {
169 : /* we first check if the hash matches, as in the same bucket we may have multiples hash values */
170 384 : if (node->index == hash && cmp(cmp_arg, node->data) == 0) {
171 128 : tommy_list_remove_existing(&hashdyn->bucket[pos], node);
172 :
173 128 : --hashdyn->count;
174 :
175 128 : hashdyn_shrink_step(hashdyn);
176 :
177 128 : return node->data;
178 : }
179 256 : node = node->next;
180 : }
181 :
182 128 : return 0;
183 : }
184 :
185 287 : TOMMY_API void tommy_hashdyn_foreach(tommy_hashdyn* hashdyn, tommy_foreach_func* func)
186 : {
187 287 : tommy_size_t bucket_max = hashdyn->bucket_max;
188 287 : tommy_hashdyn_node** bucket = hashdyn->bucket;
189 : tommy_size_t pos;
190 :
191 6011023 : for (pos = 0; pos < bucket_max; ++pos) {
192 6010736 : tommy_hashdyn_node* node = bucket[pos];
193 :
194 7918995 : while (node) {
195 1908259 : void* data = node->data;
196 1908259 : node = node->next;
197 1908259 : func(data);
198 : }
199 : }
200 287 : }
201 :
202 4 : TOMMY_API void tommy_hashdyn_foreach_arg(tommy_hashdyn* hashdyn, tommy_foreach_arg_func* func, void* arg)
203 : {
204 4 : tommy_size_t bucket_max = hashdyn->bucket_max;
205 4 : tommy_hashdyn_node** bucket = hashdyn->bucket;
206 : tommy_size_t pos;
207 :
208 1316 : for (pos = 0; pos < bucket_max; ++pos) {
209 1312 : tommy_hashdyn_node* node = bucket[pos];
210 :
211 1629 : while (node) {
212 317 : void* data = node->data;
213 317 : node = node->next;
214 317 : func(arg, data);
215 : }
216 : }
217 4 : }
218 :
219 1 : TOMMY_API tommy_size_t tommy_hashdyn_memory_usage(tommy_hashdyn* hashdyn)
220 : {
221 1 : return hashdyn->bucket_max * (tommy_size_t)sizeof(hashdyn->bucket[0])
222 1 : + tommy_hashdyn_count(hashdyn) * (tommy_size_t)sizeof(tommy_hashdyn_node);
223 : }
224 :
225 : /**
226 : * \brief Transfers all elements from the dynamic hashtable into a tommy_list.
227 : *
228 : * Removes every element from the \p hashdyn hashtable and inserts them
229 : * into the provided \p list (at the tail), preserving the per-bucket order
230 : * but not guaranteeing any particular global order.
231 : *
232 : * After the call:
233 : * - the hashtable is left completely empty (\c count = 0, all buckets = NULL)
234 : * - the target list contains all the elements that were previously in the hashtable
235 : *
236 : * This function is useful when you need to:
237 : * - extract all elements to process/sort them outside the hash table
238 : * - convert the hashtable into a list for sequential iteration
239 : * - prepare for a full clear + re-insertion with different hash/ordering
240 : * - move ownership of the nodes to a list-based container
241 : *
242 : * \note The operation is O(n) where n is the number of elements.
243 : * \note No memory allocation is performed.
244 : * \note The relative order of elements that were in the same bucket is preserved,
245 : * but the order among different buckets is bucket-order dependent.
246 : *
247 : * Typical usage pattern:
248 : * \code
249 : * tommy_list all_elements;
250 : * tommy_list_init(&all_elements);
251 : *
252 : * // move everything out of the hashtable into the list
253 : * tommy_hashdyn_to_list(&hashdyn, &all_elements);
254 : *
255 : * // now you can sort, filter, process sequentially, etc.
256 : * tommy_list_sort(&all_elements, compare_by_value);
257 : * \endcode
258 : *
259 : * \param hashdyn The dynamic hashtable to drain
260 : * \param list The list that will receive all the elements
261 : */
262 434 : TOMMY_API void tommy_hashdyn_to_list(tommy_hashdyn* hashdyn, tommy_list* list)
263 : {
264 434 : tommy_size_t bucket_max = hashdyn->bucket_max;
265 434 : tommy_hashdyn_node** bucket = hashdyn->bucket;
266 : tommy_size_t pos;
267 :
268 : /* move everything to the list */
269 7378 : for (pos = 0; pos < bucket_max; ++pos) {
270 6944 : tommy_hashdyn_node* node = bucket[pos];
271 :
272 7748 : while (node) {
273 804 : tommy_node* node_next = node->next;
274 804 : tommy_list_insert_tail(list, node, node->data);
275 804 : node = node_next;
276 : }
277 : }
278 :
279 : /* clear all */
280 434 : memset(hashdyn->bucket, 0, hashdyn->bucket_max * sizeof(tommy_hashdyn_node*));
281 434 : hashdyn->count = 0;
282 434 : }
|
