diff options
author | Christian Grothoff <christian@grothoff.org> | 2009-10-20 07:21:23 +0000 |
---|---|---|
committer | Christian Grothoff <christian@grothoff.org> | 2009-10-20 07:21:23 +0000 |
commit | 7e7e68018805b6566060d063d81f7ae5e5bb03e4 (patch) | |
tree | 715d2cb0f8eb86c6d141e742beee8e178bb02c25 /src/util/container_multihashmap.c | |
parent | 3d0d16299831c5a3a30f26c7a384fbfbed4e0486 (diff) | |
download | gnunet-7e7e68018805b6566060d063d81f7ae5e5bb03e4.tar.gz gnunet-7e7e68018805b6566060d063d81f7ae5e5bb03e4.zip |
fix bugs and add comments
Diffstat (limited to 'src/util/container_multihashmap.c')
-rw-r--r-- | src/util/container_multihashmap.c | 206 |
1 files changed, 169 insertions, 37 deletions
diff --git a/src/util/container_multihashmap.c b/src/util/container_multihashmap.c index 41c11bf1b..ac1905201 100644 --- a/src/util/container_multihashmap.c +++ b/src/util/container_multihashmap.c | |||
@@ -29,43 +29,75 @@ | |||
29 | #include "gnunet_crypto_lib.h" | 29 | #include "gnunet_crypto_lib.h" |
30 | 30 | ||
31 | /** | 31 | /** |
32 | * | 32 | * An entry in the hash map. |
33 | */ | 33 | */ |
34 | struct MapEntry | 34 | struct MapEntry |
35 | { | 35 | { |
36 | |||
37 | /** | ||
38 | * Key for the entry. | ||
39 | */ | ||
36 | GNUNET_HashCode key; | 40 | GNUNET_HashCode key; |
41 | |||
42 | /** | ||
43 | * Value of the entry. | ||
44 | */ | ||
37 | void *value; | 45 | void *value; |
46 | |||
47 | /** | ||
48 | * If there is a hash collision, we create a linked list. | ||
49 | */ | ||
38 | struct MapEntry *next; | 50 | struct MapEntry *next; |
51 | |||
39 | }; | 52 | }; |
40 | 53 | ||
41 | /** | 54 | /** |
42 | * | 55 | * Internal representation of the hash map. |
43 | */ | 56 | */ |
44 | struct GNUNET_CONTAINER_MultiHashMap | 57 | struct GNUNET_CONTAINER_MultiHashMap |
45 | { | 58 | { |
46 | 59 | ||
60 | /** | ||
61 | * All of our buckets. | ||
62 | */ | ||
47 | struct MapEntry **map; | 63 | struct MapEntry **map; |
48 | 64 | ||
65 | /** | ||
66 | * Number of entries in the map. | ||
67 | */ | ||
49 | unsigned int size; | 68 | unsigned int size; |
50 | 69 | ||
70 | /** | ||
71 | * Length of the "map" array. | ||
72 | */ | ||
51 | unsigned int map_length; | 73 | unsigned int map_length; |
52 | }; | 74 | }; |
53 | 75 | ||
54 | 76 | ||
77 | /** | ||
78 | * Create a multi hash map. | ||
79 | * | ||
80 | * @param len initial size (map will grow as needed) | ||
81 | * @return NULL on error | ||
82 | */ | ||
55 | struct GNUNET_CONTAINER_MultiHashMap * | 83 | struct GNUNET_CONTAINER_MultiHashMap * |
56 | GNUNET_CONTAINER_multihashmap_create (unsigned int len) | 84 | GNUNET_CONTAINER_multihashmap_create (unsigned int len) |
57 | { | 85 | { |
58 | struct GNUNET_CONTAINER_MultiHashMap *ret; | 86 | struct GNUNET_CONTAINER_MultiHashMap *ret; |
59 | 87 | ||
60 | ret = GNUNET_malloc (sizeof (struct GNUNET_CONTAINER_MultiHashMap)); | 88 | ret = GNUNET_malloc (sizeof (struct GNUNET_CONTAINER_MultiHashMap)); |
61 | ret->size = 0; | ||
62 | ret->map = GNUNET_malloc (len * sizeof (struct MapEntry *)); | 89 | ret->map = GNUNET_malloc (len * sizeof (struct MapEntry *)); |
63 | memset (ret->map, 0, len * sizeof (struct MapEntry *)); | ||
64 | ret->map_length = len; | 90 | ret->map_length = len; |
65 | return ret; | 91 | return ret; |
66 | } | 92 | } |
67 | 93 | ||
68 | 94 | ||
95 | /** | ||
96 | * Destroy a hash map. Will not free any values | ||
97 | * stored in the hash map! | ||
98 | * | ||
99 | * @param map the map | ||
100 | */ | ||
69 | void | 101 | void |
70 | GNUNET_CONTAINER_multihashmap_destroy (struct GNUNET_CONTAINER_MultiHashMap | 102 | GNUNET_CONTAINER_multihashmap_destroy (struct GNUNET_CONTAINER_MultiHashMap |
71 | *map) | 103 | *map) |
@@ -85,6 +117,14 @@ GNUNET_CONTAINER_multihashmap_destroy (struct GNUNET_CONTAINER_MultiHashMap | |||
85 | GNUNET_free (map); | 117 | GNUNET_free (map); |
86 | } | 118 | } |
87 | 119 | ||
120 | |||
121 | /** | ||
122 | * Compute the index of the bucket for the given key. | ||
123 | * | ||
124 | * @param m hash map for which to compute the index | ||
125 | * @param key what key should the index be computed for | ||
126 | * @return offset into the "map" array of "m" | ||
127 | */ | ||
88 | static unsigned int | 128 | static unsigned int |
89 | idx_of (const struct GNUNET_CONTAINER_MultiHashMap *m, | 129 | idx_of (const struct GNUNET_CONTAINER_MultiHashMap *m, |
90 | const GNUNET_HashCode * key) | 130 | const GNUNET_HashCode * key) |
@@ -93,6 +133,12 @@ idx_of (const struct GNUNET_CONTAINER_MultiHashMap *m, | |||
93 | } | 133 | } |
94 | 134 | ||
95 | 135 | ||
136 | /** | ||
137 | * Get the number of key-value pairs in the map. | ||
138 | * | ||
139 | * @param map the map | ||
140 | * @return the number of key value pairs | ||
141 | */ | ||
96 | unsigned int | 142 | unsigned int |
97 | GNUNET_CONTAINER_multihashmap_size (const struct GNUNET_CONTAINER_MultiHashMap | 143 | GNUNET_CONTAINER_multihashmap_size (const struct GNUNET_CONTAINER_MultiHashMap |
98 | *map) | 144 | *map) |
@@ -101,6 +147,16 @@ GNUNET_CONTAINER_multihashmap_size (const struct GNUNET_CONTAINER_MultiHashMap | |||
101 | } | 147 | } |
102 | 148 | ||
103 | 149 | ||
150 | /** | ||
151 | * Given a key find a value in the map matching the key. | ||
152 | * | ||
153 | * @param map the map | ||
154 | * @param key what to look for | ||
155 | * @return NULL if no value was found; note that | ||
156 | * this is indistinguishable from values that just | ||
157 | * happen to be NULL; use "contains" to test for | ||
158 | * key-value pairs with value NULL | ||
159 | */ | ||
104 | void * | 160 | void * |
105 | GNUNET_CONTAINER_multihashmap_get (const struct GNUNET_CONTAINER_MultiHashMap | 161 | GNUNET_CONTAINER_multihashmap_get (const struct GNUNET_CONTAINER_MultiHashMap |
106 | *map, const GNUNET_HashCode * key) | 162 | *map, const GNUNET_HashCode * key) |
@@ -118,11 +174,20 @@ GNUNET_CONTAINER_multihashmap_get (const struct GNUNET_CONTAINER_MultiHashMap | |||
118 | } | 174 | } |
119 | 175 | ||
120 | 176 | ||
177 | /** | ||
178 | * Iterate over all entries in the map. | ||
179 | * | ||
180 | * @param map the map | ||
181 | * @param it function to call on each entry | ||
182 | * @param it_cls extra argument to it | ||
183 | * @return the number of key value pairs processed, | ||
184 | * GNUNET_SYSERR if it aborted iteration | ||
185 | */ | ||
121 | int | 186 | int |
122 | GNUNET_CONTAINER_multihashmap_iterate (const struct | 187 | GNUNET_CONTAINER_multihashmap_iterate (const struct |
123 | GNUNET_CONTAINER_MultiHashMap *map, | 188 | GNUNET_CONTAINER_MultiHashMap *map, |
124 | GNUNET_CONTAINER_HashMapIterator it, | 189 | GNUNET_CONTAINER_HashMapIterator it, |
125 | void *cls) | 190 | void *it_cls) |
126 | { | 191 | { |
127 | int count; | 192 | int count; |
128 | unsigned int i; | 193 | unsigned int i; |
@@ -134,7 +199,8 @@ GNUNET_CONTAINER_multihashmap_iterate (const struct | |||
134 | e = map->map[i]; | 199 | e = map->map[i]; |
135 | while (e != NULL) | 200 | while (e != NULL) |
136 | { | 201 | { |
137 | if ((NULL != it) && (GNUNET_OK != it (cls, &e->key, e->value))) | 202 | if ( (NULL != it) && |
203 | (GNUNET_OK != it (it_cls, &e->key, e->value)) ) | ||
138 | return GNUNET_SYSERR; | 204 | return GNUNET_SYSERR; |
139 | count++; | 205 | count++; |
140 | e = e->next; | 206 | e = e->next; |
@@ -144,6 +210,17 @@ GNUNET_CONTAINER_multihashmap_iterate (const struct | |||
144 | } | 210 | } |
145 | 211 | ||
146 | 212 | ||
213 | /** | ||
214 | * Remove the given key-value pair from the map. Note that if the | ||
215 | * key-value pair is in the map multiple times, only one of the pairs | ||
216 | * will be removed. | ||
217 | * | ||
218 | * @param map the map | ||
219 | * @param key key of the key-value pair | ||
220 | * @param value value of the key-value pair | ||
221 | * @return GNUNET_YES on success, GNUNET_NO if the key-value pair | ||
222 | * is not in the map | ||
223 | */ | ||
147 | int | 224 | int |
148 | GNUNET_CONTAINER_multihashmap_remove (struct GNUNET_CONTAINER_MultiHashMap | 225 | GNUNET_CONTAINER_multihashmap_remove (struct GNUNET_CONTAINER_MultiHashMap |
149 | *map, const GNUNET_HashCode * key, | 226 | *map, const GNUNET_HashCode * key, |
@@ -158,8 +235,8 @@ GNUNET_CONTAINER_multihashmap_remove (struct GNUNET_CONTAINER_MultiHashMap | |||
158 | e = map->map[i]; | 235 | e = map->map[i]; |
159 | while (e != NULL) | 236 | while (e != NULL) |
160 | { | 237 | { |
161 | if ((0 == memcmp (key, &e->key, sizeof (GNUNET_HashCode))) && | 238 | if ( (0 == memcmp (key, &e->key, sizeof (GNUNET_HashCode))) && |
162 | (value == e->value)) | 239 | (value == e->value)) |
163 | { | 240 | { |
164 | if (p == NULL) | 241 | if (p == NULL) |
165 | map->map[i] = e->next; | 242 | map->map[i] = e->next; |
@@ -176,6 +253,14 @@ GNUNET_CONTAINER_multihashmap_remove (struct GNUNET_CONTAINER_MultiHashMap | |||
176 | } | 253 | } |
177 | 254 | ||
178 | 255 | ||
256 | /** | ||
257 | * Remove all entries for the given key from the map. | ||
258 | * Note that the values would not be "freed". | ||
259 | * | ||
260 | * @param map the map | ||
261 | * @param key identifies values to be removed | ||
262 | * @return number of values removed | ||
263 | */ | ||
179 | int | 264 | int |
180 | GNUNET_CONTAINER_multihashmap_remove_all (struct GNUNET_CONTAINER_MultiHashMap | 265 | GNUNET_CONTAINER_multihashmap_remove_all (struct GNUNET_CONTAINER_MultiHashMap |
181 | *map, const GNUNET_HashCode * key) | 266 | *map, const GNUNET_HashCode * key) |
@@ -215,16 +300,23 @@ GNUNET_CONTAINER_multihashmap_remove_all (struct GNUNET_CONTAINER_MultiHashMap | |||
215 | } | 300 | } |
216 | 301 | ||
217 | 302 | ||
303 | /** | ||
304 | * Check if the map contains any value under the given | ||
305 | * key (including values that are NULL). | ||
306 | * | ||
307 | * @param map the map | ||
308 | * @param key the key to test if a value exists for it | ||
309 | * @return GNUNET_YES if such a value exists, | ||
310 | * GNUNET_NO if not | ||
311 | */ | ||
218 | int | 312 | int |
219 | GNUNET_CONTAINER_multihashmap_contains (const struct | 313 | GNUNET_CONTAINER_multihashmap_contains (const struct |
220 | GNUNET_CONTAINER_MultiHashMap *map, | 314 | GNUNET_CONTAINER_MultiHashMap *map, |
221 | const GNUNET_HashCode * key) | 315 | const GNUNET_HashCode * key) |
222 | { | 316 | { |
223 | struct MapEntry *e; | 317 | struct MapEntry *e; |
224 | unsigned int i; | ||
225 | 318 | ||
226 | i = idx_of (map, key); | 319 | e = map->map[idx_of (map, key)]; |
227 | e = map->map[i]; | ||
228 | while (e != NULL) | 320 | while (e != NULL) |
229 | { | 321 | { |
230 | if (0 == memcmp (key, &e->key, sizeof (GNUNET_HashCode))) | 322 | if (0 == memcmp (key, &e->key, sizeof (GNUNET_HashCode))) |
@@ -235,32 +327,54 @@ GNUNET_CONTAINER_multihashmap_contains (const struct | |||
235 | } | 327 | } |
236 | 328 | ||
237 | 329 | ||
330 | /** | ||
331 | * Grow the given map to a more appropriate size. | ||
332 | * | ||
333 | * @param map the hash map to grow | ||
334 | */ | ||
238 | static void | 335 | static void |
239 | grow (struct GNUNET_CONTAINER_MultiHashMap *map) | 336 | grow (struct GNUNET_CONTAINER_MultiHashMap *map) |
240 | { | 337 | { |
241 | struct MapEntry **old; | 338 | struct MapEntry **old_map; |
339 | struct MapEntry **new_map; | ||
242 | struct MapEntry *e; | 340 | struct MapEntry *e; |
341 | unsigned int old_len; | ||
342 | unsigned int new_len; | ||
343 | unsigned int idx; | ||
243 | unsigned int i; | 344 | unsigned int i; |
244 | unsigned int l; | 345 | |
245 | 346 | old_map = map->map; | |
246 | old = map->map; | 347 | old_len = map->map_length; |
247 | l = map->map_length; | 348 | new_len = old_len * 2; |
248 | map->map_length *= 2; | 349 | new_map = GNUNET_malloc (sizeof (struct MapEntry *) * new_len); |
249 | map->map = GNUNET_malloc (sizeof (struct MapEntry *) * map->map_length); | 350 | map->map_length = new_len; |
250 | memset (map->map, 0, sizeof (struct MapEntry *) * map->map_length); | 351 | map->map = new_map; |
251 | for (i = 0; i < l; i++) | 352 | for (i = 0; i < old_len; i++) |
252 | { | 353 | { |
253 | while (NULL != (e = old[i])) | 354 | while (NULL != (e = old_map[i])) |
254 | { | 355 | { |
255 | old[i] = e->next; | 356 | old_map[i] = e->next; |
256 | e->next = map->map[idx_of (map, &e->key)]; | 357 | idx = idx_of (map, &e->key); |
257 | map->map[idx_of (map, &e->key)] = e; | 358 | e->next = new_map[idx]; |
359 | new_map[idx] = e; | ||
258 | } | 360 | } |
259 | } | 361 | } |
260 | GNUNET_free (old); | 362 | GNUNET_free (old_map); |
261 | } | 363 | } |
262 | 364 | ||
263 | 365 | ||
366 | /** | ||
367 | * Store a key-value pair in the map. | ||
368 | * | ||
369 | * @param map the map | ||
370 | * @param key key to use | ||
371 | * @param value value to use | ||
372 | * @param opt options for put | ||
373 | * @return GNUNET_OK on success, | ||
374 | * GNUNET_NO if a value was replaced (with REPLACE) | ||
375 | * GNUNET_SYSERR if UNIQUE_ONLY was the option and the | ||
376 | * value already exists | ||
377 | */ | ||
264 | int | 378 | int |
265 | GNUNET_CONTAINER_multihashmap_put (struct GNUNET_CONTAINER_MultiHashMap *map, | 379 | GNUNET_CONTAINER_multihashmap_put (struct GNUNET_CONTAINER_MultiHashMap *map, |
266 | const GNUNET_HashCode * key, | 380 | const GNUNET_HashCode * key, |
@@ -272,14 +386,13 @@ GNUNET_CONTAINER_multihashmap_put (struct GNUNET_CONTAINER_MultiHashMap *map, | |||
272 | unsigned int i; | 386 | unsigned int i; |
273 | 387 | ||
274 | i = idx_of (map, key); | 388 | i = idx_of (map, key); |
275 | if ((opt != GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE) && | 389 | if ( (opt != GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE) && |
276 | (opt != GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_FAST)) | 390 | (opt != GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_FAST) ) |
277 | { | 391 | { |
278 | e = map->map[i]; | 392 | e = map->map[i]; |
279 | while (e != NULL) | 393 | while (e != NULL) |
280 | { | 394 | { |
281 | if ((0 == memcmp (key, &e->key, sizeof (GNUNET_HashCode))) && | 395 | if (0 == memcmp (key, &e->key, sizeof (GNUNET_HashCode))) |
282 | (value == e->value)) | ||
283 | { | 396 | { |
284 | if (opt == GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY) | 397 | if (opt == GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY) |
285 | return GNUNET_SYSERR; | 398 | return GNUNET_SYSERR; |
@@ -289,7 +402,7 @@ GNUNET_CONTAINER_multihashmap_put (struct GNUNET_CONTAINER_MultiHashMap *map, | |||
289 | e = e->next; | 402 | e = e->next; |
290 | } | 403 | } |
291 | } | 404 | } |
292 | if (map->size / 3 > map->map_length / 4) | 405 | if (map->size / 3 >= map->map_length / 4) |
293 | grow (map); | 406 | grow (map); |
294 | e = GNUNET_malloc (sizeof (struct MapEntry)); | 407 | e = GNUNET_malloc (sizeof (struct MapEntry)); |
295 | e->key = *key; | 408 | e->key = *key; |
@@ -301,12 +414,22 @@ GNUNET_CONTAINER_multihashmap_put (struct GNUNET_CONTAINER_MultiHashMap *map, | |||
301 | } | 414 | } |
302 | 415 | ||
303 | 416 | ||
417 | /** | ||
418 | * Iterate over all entries in the map that match a particular key. | ||
419 | * | ||
420 | * @param map the map | ||
421 | * @param key key that the entries must correspond to | ||
422 | * @param it function to call on each entry | ||
423 | * @param it_cls extra argument to it | ||
424 | * @return the number of key value pairs processed, | ||
425 | * GNUNET_SYSERR if it aborted iteration | ||
426 | */ | ||
304 | int | 427 | int |
305 | GNUNET_CONTAINER_multihashmap_get_multiple (const struct | 428 | GNUNET_CONTAINER_multihashmap_get_multiple (const struct |
306 | GNUNET_CONTAINER_MultiHashMap | 429 | GNUNET_CONTAINER_MultiHashMap |
307 | *map, const GNUNET_HashCode * key, | 430 | *map, const GNUNET_HashCode * key, |
308 | GNUNET_CONTAINER_HashMapIterator | 431 | GNUNET_CONTAINER_HashMapIterator |
309 | it, void *cls) | 432 | it, void *it_cls) |
310 | { | 433 | { |
311 | int count; | 434 | int count; |
312 | struct MapEntry *e; | 435 | struct MapEntry *e; |
@@ -317,7 +440,8 @@ GNUNET_CONTAINER_multihashmap_get_multiple (const struct | |||
317 | { | 440 | { |
318 | if (0 == memcmp (key, &e->key, sizeof (GNUNET_HashCode))) | 441 | if (0 == memcmp (key, &e->key, sizeof (GNUNET_HashCode))) |
319 | { | 442 | { |
320 | if ((it != NULL) && (GNUNET_OK != it (&e->key, e->value, cls))) | 443 | if ( (it != NULL) && |
444 | (GNUNET_OK != it (it_cls, &e->key, e->value)) ) | ||
321 | return GNUNET_SYSERR; | 445 | return GNUNET_SYSERR; |
322 | count++; | 446 | count++; |
323 | } | 447 | } |
@@ -327,26 +451,34 @@ GNUNET_CONTAINER_multihashmap_get_multiple (const struct | |||
327 | } | 451 | } |
328 | 452 | ||
329 | 453 | ||
454 | /** | ||
455 | * Returns the stored value of a random non-null entry in the hash | ||
456 | * table. Returns only the first value, does not go inside bucket | ||
457 | * linked list (yet). Runs with a worst case time of N, so it's not | ||
458 | * efficient in any way shape or form!!!!. | ||
459 | * | ||
460 | * @param map the map | ||
461 | * @return value associated with a random key | ||
462 | */ | ||
330 | void * | 463 | void * |
331 | GNUNET_CONTAINER_multihashmap_get_random (const struct | 464 | GNUNET_CONTAINER_multihashmap_get_random (const struct |
332 | GNUNET_CONTAINER_MultiHashMap *map) | 465 | GNUNET_CONTAINER_MultiHashMap *map) |
333 | { | 466 | { |
334 | unsigned int rand; | 467 | unsigned int rand; |
335 | struct MapEntry *e; | 468 | struct MapEntry *e; |
336 | e = NULL; | ||
337 | 469 | ||
338 | if (map->size == 0) | 470 | if (map->size == 0) |
339 | return NULL; | 471 | return NULL; |
340 | 472 | while (1) | |
341 | while (e == NULL) | ||
342 | { | 473 | { |
343 | rand = | 474 | rand = |
344 | GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_WEAK, | 475 | GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_WEAK, |
345 | map->map_length); | 476 | map->map_length); |
346 | e = map->map[rand]; | 477 | if (NULL != (e = map->map[rand])) |
478 | return e->value; | ||
347 | } | 479 | } |
348 | |||
349 | return e->value; | 480 | return e->value; |
350 | } | 481 | } |
351 | 482 | ||
483 | |||
352 | /* end of container_multihashmap.c */ | 484 | /* end of container_multihashmap.c */ |