diff options
author | Sree Harsha Totakura <totakura@in.tum.de> | 2013-04-17 09:41:59 +0000 |
---|---|---|
committer | Sree Harsha Totakura <totakura@in.tum.de> | 2013-04-17 09:41:59 +0000 |
commit | 7e53c7855a15eb7049d391f1a1b32aff822c5c5b (patch) | |
tree | ed7e3decb1f79a7721675f4b532e8a684bf104a8 /src/util/container_multihashmap32.c | |
parent | 0555e4e107db9c0c1f0caa6c947881c32bf426f4 (diff) | |
download | gnunet-7e53c7855a15eb7049d391f1a1b32aff822c5c5b.tar.gz gnunet-7e53c7855a15eb7049d391f1a1b32aff822c5c5b.zip |
- 32-bit key hashmap
Diffstat (limited to 'src/util/container_multihashmap32.c')
-rw-r--r-- | src/util/container_multihashmap32.c | 497 |
1 files changed, 497 insertions, 0 deletions
diff --git a/src/util/container_multihashmap32.c b/src/util/container_multihashmap32.c new file mode 100644 index 000000000..da727d710 --- /dev/null +++ b/src/util/container_multihashmap32.c | |||
@@ -0,0 +1,497 @@ | |||
1 | /* | ||
2 | This file is part of GNUnet. | ||
3 | (C) 2008 Christian Grothoff (and other contributing authors) | ||
4 | |||
5 | GNUnet is free software; you can redistribute it and/or modify | ||
6 | it under the terms of the GNU General Public License as published | ||
7 | by the Free Software Foundation; either version 2, or (at your | ||
8 | option) any later version. | ||
9 | |||
10 | GNUnet is distributed in the hope that it will be useful, but | ||
11 | WITHOUT ANY WARRANTY; without even the implied warranty of | ||
12 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU | ||
13 | General Public License for more details. | ||
14 | |||
15 | You should have received a copy of the GNU General Public License | ||
16 | along with GNUnet; see the file COPYING. If not, write to the | ||
17 | Free Software Foundation, Inc., 59 Temple Place - Suite 330, | ||
18 | Boston, MA 02111-1307, USA. | ||
19 | */ | ||
20 | /** | ||
21 | * @file util/container_multihashmap32.c | ||
22 | * @brief a version of hash map implemented in container_multihashmap.c but with | ||
23 | * uint32_t as keys | ||
24 | * @author Christian Grothoff | ||
25 | * @author Sree Harsha Totakura | ||
26 | */ | ||
27 | |||
28 | #include "platform.h" | ||
29 | #include "gnunet_common.h" | ||
30 | #include "gnunet_container_lib.h" | ||
31 | #include "gnunet_crypto_lib.h" | ||
32 | |||
33 | #define LOG(kind,...) GNUNET_log_from (kind, "util", __VA_ARGS__) | ||
34 | |||
35 | /** | ||
36 | * An entry in the hash map. | ||
37 | */ | ||
38 | struct MapEntry | ||
39 | { | ||
40 | |||
41 | /** | ||
42 | * Key for the entry. | ||
43 | */ | ||
44 | uint32_t key; | ||
45 | |||
46 | /** | ||
47 | * Value of the entry. | ||
48 | */ | ||
49 | void *value; | ||
50 | |||
51 | /** | ||
52 | * If there is a hash collision, we create a linked list. | ||
53 | */ | ||
54 | struct MapEntry *next; | ||
55 | |||
56 | }; | ||
57 | |||
58 | /** | ||
59 | * Internal representation of the hash map. | ||
60 | */ | ||
61 | struct GNUNET_CONTAINER_MultiHashMap32 | ||
62 | { | ||
63 | |||
64 | /** | ||
65 | * All of our buckets. | ||
66 | */ | ||
67 | struct MapEntry **map; | ||
68 | |||
69 | /** | ||
70 | * Number of entries in the map. | ||
71 | */ | ||
72 | unsigned int size; | ||
73 | |||
74 | /** | ||
75 | * Length of the "map" array. | ||
76 | */ | ||
77 | unsigned int map_length; | ||
78 | }; | ||
79 | |||
80 | |||
81 | /** | ||
82 | * Create a multi hash map. | ||
83 | * | ||
84 | * @param len initial size (map will grow as needed) | ||
85 | * @return NULL on error | ||
86 | */ | ||
87 | struct GNUNET_CONTAINER_MultiHashMap32 * | ||
88 | GNUNET_CONTAINER_multihashmap32_create (unsigned int len) | ||
89 | { | ||
90 | struct GNUNET_CONTAINER_MultiHashMap32 *ret; | ||
91 | |||
92 | GNUNET_assert (len > 0); | ||
93 | ret = GNUNET_malloc (sizeof (struct GNUNET_CONTAINER_MultiHashMap32)); | ||
94 | ret->map = GNUNET_malloc (len * sizeof (struct MapEntry *)); | ||
95 | ret->map_length = len; | ||
96 | return ret; | ||
97 | } | ||
98 | |||
99 | |||
100 | /** | ||
101 | * Destroy a hash map. Will not free any values | ||
102 | * stored in the hash map! | ||
103 | * | ||
104 | * @param map the map | ||
105 | */ | ||
106 | void | ||
107 | GNUNET_CONTAINER_multihashmap32_destroy (struct GNUNET_CONTAINER_MultiHashMap32 | ||
108 | *map) | ||
109 | { | ||
110 | unsigned int i; | ||
111 | struct MapEntry *e; | ||
112 | |||
113 | for (i = 0; i < map->map_length; i++) | ||
114 | { | ||
115 | while (NULL != (e = map->map[i])) | ||
116 | { | ||
117 | map->map[i] = e->next; | ||
118 | GNUNET_free (e); | ||
119 | } | ||
120 | } | ||
121 | GNUNET_free (map->map); | ||
122 | GNUNET_free (map); | ||
123 | } | ||
124 | |||
125 | |||
126 | /** | ||
127 | * Compute the index of the bucket for the given key. | ||
128 | * | ||
129 | * @param m hash map for which to compute the index | ||
130 | * @param key what key should the index be computed for | ||
131 | * @return offset into the "map" array of "m" | ||
132 | */ | ||
133 | static unsigned int | ||
134 | idx_of (const struct GNUNET_CONTAINER_MultiHashMap32 *m, | ||
135 | const uint32_t key) | ||
136 | { | ||
137 | GNUNET_assert (m != NULL); | ||
138 | return ((unsigned int) key) % m->map_length; | ||
139 | } | ||
140 | |||
141 | |||
142 | /** | ||
143 | * Get the number of key-value pairs in the map. | ||
144 | * | ||
145 | * @param map the map | ||
146 | * @return the number of key value pairs | ||
147 | */ | ||
148 | unsigned int | ||
149 | GNUNET_CONTAINER_multihashmap32_size (const struct | ||
150 | GNUNET_CONTAINER_MultiHashMap32 *map) | ||
151 | { | ||
152 | return map->size; | ||
153 | } | ||
154 | |||
155 | |||
156 | /** | ||
157 | * Given a key find a value in the map matching the key. | ||
158 | * | ||
159 | * @param map the map | ||
160 | * @param key what to look for | ||
161 | * @return NULL if no value was found; note that | ||
162 | * this is indistinguishable from values that just | ||
163 | * happen to be NULL; use "contains" to test for | ||
164 | * key-value pairs with value NULL | ||
165 | */ | ||
166 | void * | ||
167 | GNUNET_CONTAINER_multihashmap32_get (const struct | ||
168 | GNUNET_CONTAINER_MultiHashMap32 *map, | ||
169 | uint32_t key) | ||
170 | { | ||
171 | struct MapEntry *e; | ||
172 | |||
173 | e = map->map[idx_of (map, key)]; | ||
174 | while (e != NULL) | ||
175 | { | ||
176 | if (key == e->key) | ||
177 | return e->value; | ||
178 | e = e->next; | ||
179 | } | ||
180 | return NULL; | ||
181 | } | ||
182 | |||
183 | |||
184 | /** | ||
185 | * Iterate over all entries in the map. | ||
186 | * | ||
187 | * @param map the map | ||
188 | * @param it function to call on each entry | ||
189 | * @param it_cls extra argument to it | ||
190 | * @return the number of key value pairs processed, | ||
191 | * GNUNET_SYSERR if it aborted iteration | ||
192 | */ | ||
193 | int | ||
194 | GNUNET_CONTAINER_multihashmap32_iterate (const struct | ||
195 | GNUNET_CONTAINER_MultiHashMap32 *map, | ||
196 | GNUNET_CONTAINER_HashMapIterator32 it, | ||
197 | void *it_cls) | ||
198 | { | ||
199 | int count; | ||
200 | unsigned int i; | ||
201 | struct MapEntry *e; | ||
202 | struct MapEntry *n; | ||
203 | |||
204 | count = 0; | ||
205 | GNUNET_assert (map != NULL); | ||
206 | for (i = 0; i < map->map_length; i++) | ||
207 | { | ||
208 | n = map->map[i]; | ||
209 | while (NULL != (e = n)) | ||
210 | { | ||
211 | n = e->next; | ||
212 | if (NULL != it) | ||
213 | { | ||
214 | if (GNUNET_OK != it (it_cls, e->key, e->value)) | ||
215 | return GNUNET_SYSERR; | ||
216 | } | ||
217 | count++; | ||
218 | } | ||
219 | } | ||
220 | return count; | ||
221 | } | ||
222 | |||
223 | |||
224 | /** | ||
225 | * Remove the given key-value pair from the map. Note that if the | ||
226 | * key-value pair is in the map multiple times, only one of the pairs | ||
227 | * will be removed. | ||
228 | * | ||
229 | * @param map the map | ||
230 | * @param key key of the key-value pair | ||
231 | * @param value value of the key-value pair | ||
232 | * @return GNUNET_YES on success, GNUNET_NO if the key-value pair | ||
233 | * is not in the map | ||
234 | */ | ||
235 | int | ||
236 | GNUNET_CONTAINER_multihashmap32_remove (struct GNUNET_CONTAINER_MultiHashMap32 | ||
237 | *map, | ||
238 | uint32_t key, void *value) | ||
239 | { | ||
240 | struct MapEntry *e; | ||
241 | struct MapEntry *p; | ||
242 | unsigned int i; | ||
243 | |||
244 | i = idx_of (map, key); | ||
245 | p = NULL; | ||
246 | e = map->map[i]; | ||
247 | while (e != NULL) | ||
248 | { | ||
249 | if ( (key == e->key) && (value == e->value) ) | ||
250 | { | ||
251 | if (p == NULL) | ||
252 | map->map[i] = e->next; | ||
253 | else | ||
254 | p->next = e->next; | ||
255 | GNUNET_free (e); | ||
256 | map->size--; | ||
257 | return GNUNET_YES; | ||
258 | } | ||
259 | p = e; | ||
260 | e = e->next; | ||
261 | } | ||
262 | return GNUNET_NO; | ||
263 | } | ||
264 | |||
265 | |||
266 | /** | ||
267 | * Remove all entries for the given key from the map. | ||
268 | * Note that the values would not be "freed". | ||
269 | * | ||
270 | * @param map the map | ||
271 | * @param key identifies values to be removed | ||
272 | * @return number of values removed | ||
273 | */ | ||
274 | int | ||
275 | GNUNET_CONTAINER_multihashmap32_remove_all (struct | ||
276 | GNUNET_CONTAINER_MultiHashMap32 | ||
277 | *map, | ||
278 | uint32_t key) | ||
279 | { | ||
280 | struct MapEntry *e; | ||
281 | struct MapEntry *p; | ||
282 | unsigned int i; | ||
283 | int ret; | ||
284 | |||
285 | ret = 0; | ||
286 | i = idx_of (map, key); | ||
287 | p = NULL; | ||
288 | e = map->map[i]; | ||
289 | while (e != NULL) | ||
290 | { | ||
291 | if (key == e->key) | ||
292 | { | ||
293 | if (p == NULL) | ||
294 | map->map[i] = e->next; | ||
295 | else | ||
296 | p->next = e->next; | ||
297 | GNUNET_free (e); | ||
298 | map->size--; | ||
299 | if (p == NULL) | ||
300 | e = map->map[i]; | ||
301 | else | ||
302 | e = p->next; | ||
303 | ret++; | ||
304 | } | ||
305 | else | ||
306 | { | ||
307 | p = e; | ||
308 | e = e->next; | ||
309 | } | ||
310 | } | ||
311 | return ret; | ||
312 | } | ||
313 | |||
314 | |||
315 | /** | ||
316 | * Check if the map contains any value under the given | ||
317 | * key (including values that are NULL). | ||
318 | * | ||
319 | * @param map the map | ||
320 | * @param key the key to test if a value exists for it | ||
321 | * @return GNUNET_YES if such a value exists, | ||
322 | * GNUNET_NO if not | ||
323 | */ | ||
324 | int | ||
325 | GNUNET_CONTAINER_multihashmap32_contains (const struct | ||
326 | GNUNET_CONTAINER_MultiHashMap32 *map, | ||
327 | uint32_t key) | ||
328 | { | ||
329 | struct MapEntry *e; | ||
330 | |||
331 | e = map->map[idx_of (map, key)]; | ||
332 | while (e != NULL) | ||
333 | { | ||
334 | if (key == e->key) | ||
335 | return GNUNET_YES; | ||
336 | e = e->next; | ||
337 | } | ||
338 | return GNUNET_NO; | ||
339 | } | ||
340 | |||
341 | |||
342 | /** | ||
343 | * Check if the map contains the given value under the given | ||
344 | * key. | ||
345 | * | ||
346 | * @param map the map | ||
347 | * @param key the key to test if a value exists for it | ||
348 | * @param value value to test for | ||
349 | * @return GNUNET_YES if such a value exists, | ||
350 | * GNUNET_NO if not | ||
351 | */ | ||
352 | int | ||
353 | GNUNET_CONTAINER_multihashmap32_contains_value (const struct | ||
354 | GNUNET_CONTAINER_MultiHashMap32 | ||
355 | *map, | ||
356 | uint32_t key, | ||
357 | const void *value) | ||
358 | { | ||
359 | struct MapEntry *e; | ||
360 | |||
361 | e = map->map[idx_of (map, key)]; | ||
362 | while (e != NULL) | ||
363 | { | ||
364 | if ( (key == e->key) && (e->value == value) ) | ||
365 | return GNUNET_YES; | ||
366 | e = e->next; | ||
367 | } | ||
368 | return GNUNET_NO; | ||
369 | } | ||
370 | |||
371 | |||
372 | /** | ||
373 | * Grow the given map to a more appropriate size. | ||
374 | * | ||
375 | * @param map the hash map to grow | ||
376 | */ | ||
377 | static void | ||
378 | grow (struct GNUNET_CONTAINER_MultiHashMap32 *map) | ||
379 | { | ||
380 | struct MapEntry **old_map; | ||
381 | struct MapEntry **new_map; | ||
382 | struct MapEntry *e; | ||
383 | unsigned int old_len; | ||
384 | unsigned int new_len; | ||
385 | unsigned int idx; | ||
386 | unsigned int i; | ||
387 | |||
388 | old_map = map->map; | ||
389 | old_len = map->map_length; | ||
390 | new_len = old_len * 2; | ||
391 | new_map = GNUNET_malloc (sizeof (struct MapEntry *) * new_len); | ||
392 | map->map_length = new_len; | ||
393 | map->map = new_map; | ||
394 | for (i = 0; i < old_len; i++) | ||
395 | { | ||
396 | while (NULL != (e = old_map[i])) | ||
397 | { | ||
398 | old_map[i] = e->next; | ||
399 | idx = idx_of (map, e->key); | ||
400 | e->next = new_map[idx]; | ||
401 | new_map[idx] = e; | ||
402 | } | ||
403 | } | ||
404 | GNUNET_free (old_map); | ||
405 | } | ||
406 | |||
407 | |||
408 | /** | ||
409 | * Store a key-value pair in the map. | ||
410 | * | ||
411 | * @param map the map | ||
412 | * @param key key to use | ||
413 | * @param value value to use | ||
414 | * @param opt options for put | ||
415 | * @return GNUNET_OK on success, | ||
416 | * GNUNET_NO if a value was replaced (with REPLACE) | ||
417 | * GNUNET_SYSERR if UNIQUE_ONLY was the option and the | ||
418 | * value already exists | ||
419 | */ | ||
420 | int | ||
421 | GNUNET_CONTAINER_multihashmap32_put (struct GNUNET_CONTAINER_MultiHashMap32 | ||
422 | *map, uint32_t key, void *value, | ||
423 | enum GNUNET_CONTAINER_MultiHashMapOption | ||
424 | opt) | ||
425 | { | ||
426 | struct MapEntry *e; | ||
427 | unsigned int i; | ||
428 | |||
429 | i = idx_of (map, key); | ||
430 | if ((opt != GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE) && | ||
431 | (opt != GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_FAST)) | ||
432 | { | ||
433 | e = map->map[i]; | ||
434 | while (e != NULL) | ||
435 | { | ||
436 | if (key == e->key) | ||
437 | { | ||
438 | if (opt == GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY) | ||
439 | return GNUNET_SYSERR; | ||
440 | e->value = value; | ||
441 | return GNUNET_NO; | ||
442 | } | ||
443 | e = e->next; | ||
444 | } | ||
445 | } | ||
446 | if (map->size / 3 >= map->map_length / 4) | ||
447 | { | ||
448 | grow (map); | ||
449 | i = idx_of (map, key); | ||
450 | } | ||
451 | e = GNUNET_malloc (sizeof (struct MapEntry)); | ||
452 | e->key = key; | ||
453 | e->value = value; | ||
454 | e->next = map->map[i]; | ||
455 | map->map[i] = e; | ||
456 | map->size++; | ||
457 | return GNUNET_OK; | ||
458 | } | ||
459 | |||
460 | |||
461 | /** | ||
462 | * Iterate over all entries in the map that match a particular key. | ||
463 | * | ||
464 | * @param map the map | ||
465 | * @param key key that the entries must correspond to | ||
466 | * @param it function to call on each entry | ||
467 | * @param it_cls extra argument to it | ||
468 | * @return the number of key value pairs processed, | ||
469 | * GNUNET_SYSERR if it aborted iteration | ||
470 | */ | ||
471 | int | ||
472 | GNUNET_CONTAINER_multihashmap32_get_multiple (const struct | ||
473 | GNUNET_CONTAINER_MultiHashMap32 | ||
474 | *map, uint32_t key, | ||
475 | GNUNET_CONTAINER_HashMapIterator32 | ||
476 | it, void *it_cls) | ||
477 | { | ||
478 | int count; | ||
479 | struct MapEntry *e; | ||
480 | struct MapEntry *n; | ||
481 | |||
482 | count = 0; | ||
483 | n = map->map[idx_of (map, key)]; | ||
484 | while (NULL != (e = n)) | ||
485 | { | ||
486 | n = e->next; | ||
487 | if (key != e->key) | ||
488 | continue; | ||
489 | if ((it != NULL) && (GNUNET_OK != it (it_cls, key, e->value))) | ||
490 | return GNUNET_SYSERR; | ||
491 | count++; | ||
492 | } | ||
493 | return count; | ||
494 | } | ||
495 | |||
496 | |||
497 | /* end of container_multihashmap.c */ | ||