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 : /** \file
29 : * Dynamic chained hashtable.
30 : *
31 : * This hashtable resizes dynamically. It starts with the minimal size of 16 buckets, it doubles
32 : * the size when it reaches a load factor greater than 0.5 and it halves the size when the load
33 : * factor is lower than 0.125.
34 : *
35 : * All the elements are reallocated in a single resize operation done inside
36 : * tommy_hashdyn_insert() or tommy_hashdyn_remove().
37 : *
38 : * Note that the resize operation takes approximately 100 [ms] with 1 million of elements,
39 : * and 1 [second] with 10 millions. This could be a problem in real-time applications.
40 : *
41 : * The resize also **fragments** the heap, as it involves allocating a double-sized table, **copying** elements,
42 : * and deallocating the older table, **leaving** a big hole in the heap.
43 : *
44 : * The ::tommy_hashlin hashtable fixes both problems.
45 : *
46 : * To initialize the hashtable you have to call tommy_hashdyn_init().
47 : *
48 : * \code
49 : * tommy_hashdyn hashdyn;
50 : *
51 : * tommy_hashdyn_init(&hashdyn);
52 : * \endcode
53 : *
54 : * To insert elements in the hashtable you have to call tommy_hashdyn_insert() for
55 : * each element.
56 : * In the insertion call you have to specify the address of the node, the
57 : * address of the object, and the hash value of the key to use.
58 : * The address of the object is used to initialize the tommy_node::data field
59 : * of the node, and the hash to initialize the tommy_node::key field.
60 : *
61 : * \code
62 : * struct object {
63 : * int value;
64 : * // other fields
65 : * tommy_node node;
66 : * };
67 : *
68 : * struct object* obj = malloc(sizeof(struct object)); // creates the object
69 : *
70 : * obj->value = ...; // initializes the object
71 : *
72 : * tommy_hashdyn_insert(&hashdyn, &obj->node, obj, tommy_inthash_u32(obj->value)); // inserts the object
73 : * \endcode
74 : *
75 : * To find an element in the hashtable you have to call tommy_hashtable_search()
76 : * providing a comparison function, its argument, and the hash of the key to search.
77 : *
78 : * \code
79 : * int compare(const void* arg, const void* obj)
80 : * {
81 : * return *(const int*)arg != ((const struct object*)obj)->value;
82 : * }
83 : *
84 : * int value_to_find = 1;
85 : * struct object* obj = tommy_hashdyn_search(&hashdyn, compare, &value_to_find, tommy_inthash_u32(value_to_find));
86 : * if (!obj) {
87 : * // not found
88 : * } else {
89 : * // found
90 : * }
91 : * \endcode
92 : *
93 : * To iterate over all the elements in the hashtable with the same key, you have to
94 : * use tommy_hashdyn_bucket() and follow the tommy_node::next pointer until NULL.
95 : * You have also to check explicitly for the key, as the bucket may contain
96 : * different keys.
97 : *
98 : * \code
99 : * int value_to_find = 1;
100 : * tommy_node* i = tommy_hashdyn_bucket(&hashdyn, tommy_inthash_u32(value_to_find));
101 : * while (i) {
102 : * struct object* obj = i->data; // gets the object pointer
103 : *
104 : * if (obj->value == value_to_find) {
105 : * printf("%d\n", obj->value); // process the object
106 : * }
107 : *
108 : * i = i->next; // goes to the next element
109 : * }
110 : * \endcode
111 : *
112 : * To remove an element from the hashtable you have to call tommy_hashdyn_remove()
113 : * providing a comparison function, its argument, and the hash of the key to search
114 : * and remove.
115 : *
116 : * \code
117 : * struct object* obj = tommy_hashdyn_remove(&hashdyn, compare, &value_to_remove, tommy_inthash_u32(value_to_remove));
118 : * if (obj) {
119 : * free(obj); // frees the object allocated memory
120 : * }
121 : * \endcode
122 : *
123 : * To destroy the hashtable you have to remove all the elements, and deinitialize
124 : * the hashtable calling tommy_hashdyn_done().
125 : *
126 : * \code
127 : * tommy_hashdyn_done(&hashdyn);
128 : * \endcode
129 : *
130 : * If you need to iterate over all the elements in the hashtable, you can use
131 : * tommy_hashdyn_foreach() or tommy_hashdyn_foreach_arg().
132 : * If you need a more precise control with a real iteration, you have to insert
133 : * all the elements also in a ::tommy_list, and use the list to iterate.
134 : * See the \ref multiindex example for more detail.
135 : */
136 :
137 : #ifndef __TOMMYHASHDYN_H
138 : #define __TOMMYHASHDYN_H
139 :
140 : #include "tommyhash.h"
141 :
142 : /******************************************************************************/
143 : /* hashdyn */
144 :
145 : /** \internal
146 : * Initial and minimal size of the hashtable expressed as a power of 2.
147 : * The initial size is 2^TOMMY_HASHDYN_BIT.
148 : */
149 : #define TOMMY_HASHDYN_BIT 4
150 :
151 : /**
152 : * Hashtable node.
153 : * This is the node that you have to include inside your objects.
154 : */
155 : typedef tommy_node tommy_hashdyn_node;
156 :
157 : /**
158 : * Hashtable container type.
159 : * \note Don't use internal fields directly, but access the container only using functions.
160 : */
161 : typedef struct tommy_hashdyn_struct {
162 : tommy_hashdyn_node** bucket; /**< Hash buckets. One list for each hash modulus. */
163 : tommy_size_t bucket_max; /**< Number of buckets. */
164 : tommy_size_t bucket_mask; /**< Bit mask to access the buckets. */
165 : tommy_size_t count; /**< Number of elements. */
166 : tommy_uint_t bucket_bit; /**< Bits used in the bit mask. */
167 : } tommy_hashdyn;
168 :
169 : /**
170 : * Initializes the hashtable.
171 : */
172 : TOMMY_API void tommy_hashdyn_init(tommy_hashdyn* hashdyn);
173 :
174 : /**
175 : * Deinitializes the hashtable.
176 : *
177 : * You can call this function with elements still contained,
178 : * but such elements are not going to be freed by this call.
179 : */
180 : TOMMY_API void tommy_hashdyn_done(tommy_hashdyn* hashdyn);
181 :
182 : /**
183 : * Inserts an element in the hashtable.
184 : */
185 : TOMMY_API void tommy_hashdyn_insert(tommy_hashdyn* hashdyn, tommy_hashdyn_node* node, void* data, tommy_hash_t hash);
186 :
187 : /**
188 : * Searches and removes an element from the hashtable.
189 : * You have to provide a compare function and the hash of the element you want to remove.
190 : * If the element is not found, 0 is returned.
191 : * If more equal elements are present, the first one is removed.
192 : * \param cmp Compare function called with cmp_arg as first argument and with the element to compare as a second one.
193 : * The function should return 0 for equal elements, anything other for different elements.
194 : * \param cmp_arg Compare argument passed as first argument of the compare function.
195 : * \param hash Hash of the element to find and remove.
196 : * \return The removed element, or 0 if not found.
197 : */
198 : TOMMY_API void* tommy_hashdyn_remove(tommy_hashdyn* hashdyn, tommy_search_func* cmp, const void* cmp_arg, tommy_hash_t hash);
199 :
200 : /**
201 : * Gets the bucket of the specified hash.
202 : * The bucket is guaranteed to contain ALL the elements with the specified hash,
203 : * but it can contain also others.
204 : * You can access elements in the bucket following the ::next pointer until 0.
205 : * \param hash Hash of the element to find.
206 : * \return The head of the bucket, or 0 if empty.
207 : */
208 3382861 : tommy_inline tommy_hashdyn_node* tommy_hashdyn_bucket(tommy_hashdyn* hashdyn, tommy_hash_t hash)
209 : {
210 3382861 : return hashdyn->bucket[hash & hashdyn->bucket_mask];
211 : }
212 :
213 : /**
214 : * Searches an element in the hashtable.
215 : * You have to provide a compare function and the hash of the element you want to find.
216 : * If more equal elements are present, the first one is returned.
217 : * \param cmp Compare function called with cmp_arg as first argument and with the element to compare as a second one.
218 : * The function should return 0 for equal elements, anything other for different elements.
219 : * \param cmp_arg Compare argument passed as first argument of the compare function.
220 : * \param hash Hash of the element to find.
221 : * \return The first element found, or 0 if none.
222 : */
223 3325913 : tommy_inline void* tommy_hashdyn_search(tommy_hashdyn* hashdyn, tommy_search_func* cmp, const void* cmp_arg, tommy_hash_t hash)
224 : {
225 3325913 : tommy_hashdyn_node* i = tommy_hashdyn_bucket(hashdyn, hash);
226 :
227 4041466 : while (i) {
228 : /* we first check if the hash matches, as in the same bucket we may have multiple hash values */
229 2005687 : if (i->index == hash && cmp(cmp_arg, i->data) == 0)
230 1290134 : return i->data;
231 715553 : i = i->next;
232 : }
233 2035779 : return 0;
234 : }
235 :
236 : /**
237 : * Removes an element from the hashtable.
238 : * You must already have the address of the element to remove.
239 : * \return The tommy_node::data field of the node removed.
240 : */
241 : TOMMY_API void* tommy_hashdyn_remove_existing(tommy_hashdyn* hashdyn, tommy_hashdyn_node* node);
242 :
243 : /**
244 : * Calls the specified function for each element in the hashtable.
245 : *
246 : * You cannot add or remove elements from the inside of the callback,
247 : * but can use it to deallocate them.
248 : *
249 : * \code
250 : * tommy_hashdyn hashdyn;
251 : *
252 : * // initializes the hashtable
253 : * tommy_hashdyn_init(&hashdyn);
254 : *
255 : * ...
256 : *
257 : * // creates an object
258 : * struct object* obj = malloc(sizeof(struct object));
259 : *
260 : * ...
261 : *
262 : * // insert it in the hashtable
263 : * tommy_hashdyn_insert(&hashdyn, &obj->node, obj, tommy_inthash_u32(obj->value));
264 : *
265 : * ...
266 : *
267 : * // deallocates all the objects iterating the hashtable
268 : * tommy_hashdyn_foreach(&hashdyn, free);
269 : *
270 : * // deallocates the hashtable
271 : * tommy_hashdyn_done(&hashdyn);
272 : * \endcode
273 : */
274 : TOMMY_API void tommy_hashdyn_foreach(tommy_hashdyn* hashdyn, tommy_foreach_func* func);
275 :
276 : /**
277 : * Calls the specified function with an argument for each element in the hashtable.
278 : */
279 : TOMMY_API void tommy_hashdyn_foreach_arg(tommy_hashdyn* hashdyn, tommy_foreach_arg_func* func, void* arg);
280 :
281 : /**
282 : * Gets the number of elements.
283 : */
284 437 : tommy_inline tommy_size_t tommy_hashdyn_count(tommy_hashdyn* hashdyn)
285 : {
286 437 : return hashdyn->count;
287 : }
288 :
289 : /**
290 : * Gets the size of allocated memory.
291 : * It includes the size of the ::tommy_hashdyn_node of the stored elements.
292 : */
293 : TOMMY_API tommy_size_t tommy_hashdyn_memory_usage(tommy_hashdyn* hashdyn);
294 :
295 : /**
296 : * \brief Transfers all elements from the hashtable into a tommy_list.
297 : *
298 : * Removes every element from the \p hashdyn hashtable and inserts them
299 : * into the provided \p list (at the tail), preserving the per-bucket order
300 : * but not guaranteeing any particular global order.
301 : *
302 : * After the call:
303 : * - the hashtable is left completely empty
304 : * - the target list contains all the elements that were previously in the hashtable
305 : *
306 : * This function is useful when you need to:
307 : * - extract all elements to process/sort them outside the hash table
308 : * - convert the hashtable into a list for sequential iteration
309 : * - prepare for a full clear + re-insertion with different hash/ordering
310 : * - move ownership of the nodes to a list-based container
311 : *
312 : * \note The operation is O(n) where n is the number of elements.
313 : * \note No memory allocation is performed.
314 : * \note The relative order of elements that were in the same bucket is preserved,
315 : * but the order among different buckets is bucket-order dependent.
316 : *
317 : * Typical usage pattern:
318 : * \code
319 : * tommy_list all_elements;
320 : * tommy_list_init(&all_elements);
321 : *
322 : * // move everything out of the hashtable into the list
323 : * tommy_hashdyn_to_list(&hashdyn, &all_elements);
324 : *
325 : * // now you can sort, filter, process sequentially, etc.
326 : * tommy_list_sort(&all_elements, compare_by_value);
327 : * \endcode
328 : *
329 : * \param hashdyn The dynamic hashtable to drain
330 : * \param list The list that will receive all the elements
331 : */
332 : TOMMY_API void tommy_hashdyn_to_list(tommy_hashdyn* hashdyn, tommy_list* list);
333 :
334 : #endif
|
