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 : * Fixed size chained hashtable.
30 : *
31 : * This hashtable is a standard implementation of a chained hashtable with a fixed size.
32 : *
33 : * Note that performances starts to degenerate after reaching a load factor greater than 0.75.
34 : * The ::tommy_hashdyn and ::tommy_hashlin hashtables fix this problem growing dynamically.
35 : *
36 : * To initialize the hashtable you have to call tommy_hashtable_init() specifing
37 : * the fixed bucket size.
38 : *
39 : * \code
40 : * tommy_hashslin hashtable;
41 : *
42 : * tommy_hashtable_init(&hashtable, 1024);
43 : * \endcode
44 : *
45 : * To insert elements in the hashtable you have to call tommy_hashtable_insert() for
46 : * each element.
47 : * In the insertion call you have to specify the address of the node, the
48 : * address of the object, and the hash value of the key to use.
49 : * The address of the object is used to initialize the tommy_node::data field
50 : * of the node, and the hash to initialize the tommy_node::key field.
51 : *
52 : * \code
53 : * struct object {
54 : * int value;
55 : * // other fields
56 : * tommy_node node;
57 : * };
58 : *
59 : * struct object* obj = malloc(sizeof(struct object)); // creates the object
60 : *
61 : * obj->value = ...; // initializes the object
62 : *
63 : * tommy_hashtable_insert(&hashtable, &obj->node, obj, tommy_inthash_u32(obj->value)); // inserts the object
64 : * \endcode
65 : *
66 : * To find and element in the hashtable you have to call tommy_hashtable_search()
67 : * providing a comparison function, its argument, and the hash of the key to search.
68 : *
69 : * \code
70 : * int compare(const void* arg, const void* obj)
71 : * {
72 : * return *(const int*)arg != ((const struct object*)obj)->value;
73 : * }
74 : *
75 : * int value_to_find = 1;
76 : * struct object* obj = tommy_hashtable_search(&hashtable, compare, &value_to_find, tommy_inthash_u32(value_to_find));
77 : * if (!obj) {
78 : * // not found
79 : * } else {
80 : * // found
81 : * }
82 : * \endcode
83 : *
84 : * To iterate over all the elements in the hashtable with the same key, you have to
85 : * use tommy_hashtable_bucket() and follow the tommy_node::next pointer until NULL.
86 : * You have also to check explicitely for the key, as the bucket may contains
87 : * different keys.
88 : *
89 : * \code
90 : * tommy_node* i = tommy_hashtable_bucket(&hashtable, tommy_inthash_u32(value_to_find));
91 : * while (i) {
92 : * struct object* obj = i->data; // gets the object pointer
93 : *
94 : * if (obj->value == value_to_find) {
95 : * printf("%d\n", obj->value); // process the object
96 : * }
97 : *
98 : * i = i->next; // goes to the next element
99 : * }
100 : * \endcode
101 : *
102 : * To remove an element from the hashtable you have to call tommy_hashtable_remove()
103 : * providing a comparison function, its argument, and the hash of the key to search
104 : * and remove.
105 : *
106 : * \code
107 : * struct object* obj = tommy_hashtable_remove(&hashtable, compare, &value_to_remove, tommy_inthash_u32(value_to_remove));
108 : * if (obj) {
109 : * free(obj); // frees the object allocated memory
110 : * }
111 : * \endcode
112 : *
113 : * To destroy the hashtable you have to remove all the elements, and deinitialize
114 : * the hashtable calling tommy_hashtable_done().
115 : *
116 : * \code
117 : * tommy_hashtable_done(&hashtable);
118 : * \endcode
119 : *
120 : * If you need to iterate over all the elements in the hashtable, you can use
121 : * tommy_hashtable_foreach() or tommy_hashtable_foreach_arg().
122 : * If you need a more precise control with a real iteration, you have to insert
123 : * all the elements also in a ::tommy_list, and use the list to iterate.
124 : * See the \ref multiindex example for more detail.
125 : */
126 :
127 : #ifndef __TOMMYHASHTBL_H
128 : #define __TOMMYHASHTBL_H
129 :
130 : #include "tommyhash.h"
131 :
132 : /******************************************************************************/
133 : /* hashtable */
134 :
135 : /**
136 : * Hashtable node.
137 : * This is the node that you have to include inside your objects.
138 : */
139 : typedef tommy_node tommy_hashtable_node;
140 :
141 : /**
142 : * Hashtable container type.
143 : * \note Don't use internal fields directly, but access the container only using functions.
144 : */
145 : typedef struct tommy_hashtable_struct {
146 : tommy_hashtable_node** bucket; /**< Hash buckets. One list for each hash modulus. */
147 : tommy_size_t bucket_max; /**< Number of buckets. */
148 : tommy_size_t bucket_mask; /**< Bit mask to access the buckets. */
149 : tommy_size_t count; /**< Number of elements. */
150 : } tommy_hashtable;
151 :
152 : /**
153 : * Initializes the hashtable.
154 : * \param buckets Minimum number of buckets to allocate. The effective number used is the next power of 2.
155 : */
156 : void tommy_hashtable_init(tommy_hashtable* hashtable, tommy_size_t bucket_max);
157 :
158 : /**
159 : * Deinitializes the hashtable.
160 : *
161 : * You can call this function with elements still contained,
162 : * but such elements are not going to be freed by this call.
163 : */
164 : void tommy_hashtable_done(tommy_hashtable* hashtable);
165 :
166 : /**
167 : * Inserts an element in the hashtable.
168 : */
169 : void tommy_hashtable_insert(tommy_hashtable* hashtable, tommy_hashtable_node* node, void* data, tommy_hash_t hash);
170 :
171 : /**
172 : * Searches and removes an element from the hashtable.
173 : * You have to provide a compare function and the hash of the element you want to remove.
174 : * If the element is not found, 0 is returned.
175 : * If more equal elements are present, the first one is removed.
176 : * \param cmp Compare function called with cmp_arg as first argument and with the element to compare as a second one.
177 : * The function should return 0 for equal elements, anything other for different elements.
178 : * \param cmp_arg Compare argument passed as first argument of the compare function.
179 : * \param hash Hash of the element to find and remove.
180 : * \return The removed element, or 0 if not found.
181 : */
182 : void* tommy_hashtable_remove(tommy_hashtable* hashtable, tommy_search_func* cmp, const void* cmp_arg, tommy_hash_t hash);
183 :
184 : /**
185 : * Gets the bucket of the specified hash.
186 : * The bucket is guaranteed to contain ALL the elements with the specified hash,
187 : * but it can contain also others.
188 : * You can access elements in the bucket following the ::next pointer until 0.
189 : * \param hash Hash of the element to find.
190 : * \return The head of the bucket, or 0 if empty.
191 : */
192 : tommy_inline tommy_hashtable_node* tommy_hashtable_bucket(tommy_hashtable* hashtable, tommy_hash_t hash)
193 : {
194 : return hashtable->bucket[hash & hashtable->bucket_mask];
195 : }
196 :
197 : /**
198 : * Searches an element in the hashtable.
199 : * You have to provide a compare function and the hash of the element you want to find.
200 : * If more equal elements are present, the first one is returned.
201 : * \param cmp Compare function called with cmp_arg as first argument and with the element to compare as a second one.
202 : * The function should return 0 for equal elements, anything other for different elements.
203 : * \param cmp_arg Compare argument passed as first argument of the compare function.
204 : * \param hash Hash of the element to find.
205 : * \return The first element found, or 0 if none.
206 : */
207 : tommy_inline void* tommy_hashtable_search(tommy_hashtable* hashtable, tommy_search_func* cmp, const void* cmp_arg, tommy_hash_t hash)
208 : {
209 : tommy_hashtable_node* i = tommy_hashtable_bucket(hashtable, hash);
210 :
211 : while (i) {
212 : /* we first check if the hash matches, as in the same bucket we may have multiples hash values */
213 : if (i->index == hash && cmp(cmp_arg, i->data) == 0)
214 : return i->data;
215 : i = i->next;
216 : }
217 : return 0;
218 : }
219 :
220 : /**
221 : * Removes an element from the hashtable.
222 : * You must already have the address of the element to remove.
223 : * \return The tommy_node::data field of the node removed.
224 : */
225 : void* tommy_hashtable_remove_existing(tommy_hashtable* hashtable, tommy_hashtable_node* node);
226 :
227 : /**
228 : * Calls the specified function for each element in the hashtable.
229 : *
230 : * You cannot add or remove elements from the inside of the callback,
231 : * but can use it to deallocate them.
232 : *
233 : * \code
234 : * tommy_hashtable hashtable;
235 : *
236 : * // initializes the hashtable
237 : * tommy_hashtable_init(&hashtable, ...);
238 : *
239 : * ...
240 : *
241 : * // creates an object
242 : * struct object* obj = malloc(sizeof(struct object));
243 : *
244 : * ...
245 : *
246 : * // insert it in the hashtable
247 : * tommy_hashdyn_insert(&hashtable, &obj->node, obj, tommy_inthash_u32(obj->value));
248 : *
249 : * ...
250 : *
251 : * // deallocates all the objects iterating the hashtable
252 : * tommy_hashtable_foreach(&hashtable, free);
253 : *
254 : * // deallocates the hashtable
255 : * tommy_hashdyn_done(&hashtable);
256 : * \endcode
257 : */
258 : void tommy_hashtable_foreach(tommy_hashtable* hashtable, tommy_foreach_func* func);
259 :
260 : /**
261 : * Calls the specified function with an argument for each element in the hashtable.
262 : */
263 : void tommy_hashtable_foreach_arg(tommy_hashtable* hashtable, tommy_foreach_arg_func* func, void* arg);
264 :
265 : /**
266 : * Gets the number of elements.
267 : */
268 10002 : tommy_inline tommy_size_t tommy_hashtable_count(tommy_hashtable* hashtable)
269 : {
270 10002 : return hashtable->count;
271 : }
272 :
273 : /**
274 : * Gets the size of allocated memory.
275 : * It includes the size of the ::tommy_hashtable_node of the stored elements.
276 : */
277 : tommy_size_t tommy_hashtable_memory_usage(tommy_hashtable* hashtable);
278 :
279 : #endif
280 :
|
