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