diff options
Diffstat (limited to 'src/util/container_multihashmap32.c')
-rw-r--r-- | src/util/container_multihashmap32.c | 169 |
1 files changed, 110 insertions, 59 deletions
diff --git a/src/util/container_multihashmap32.c b/src/util/container_multihashmap32.c index daf5059b6..72940489e 100644 --- a/src/util/container_multihashmap32.c +++ b/src/util/container_multihashmap32.c | |||
@@ -28,6 +28,15 @@ | |||
28 | 28 | ||
29 | #define LOG(kind,...) GNUNET_log_from (kind, "util-container-multihashmap32", __VA_ARGS__) | 29 | #define LOG(kind,...) GNUNET_log_from (kind, "util-container-multihashmap32", __VA_ARGS__) |
30 | 30 | ||
31 | |||
32 | /** | ||
33 | * Maximum recursion depth for callbacks of | ||
34 | * #GNUNET_CONTAINER_multihashmap_get_multiple() themselves | ||
35 | * again calling #GNUNET_CONTAINER_multihashmap_get_multiple(). | ||
36 | * Should be totally excessive, but if violated we die. | ||
37 | */ | ||
38 | #define NEXT_CACHE_SIZE 16 | ||
39 | |||
31 | /** | 40 | /** |
32 | * An entry in the hash map. | 41 | * An entry in the hash map. |
33 | */ | 42 | */ |
@@ -68,7 +77,7 @@ struct GNUNET_CONTAINER_MultiHashMap32 | |||
68 | unsigned int size; | 77 | unsigned int size; |
69 | 78 | ||
70 | /** | 79 | /** |
71 | * Length of the "map" array. | 80 | * Length of the @e map array. |
72 | */ | 81 | */ |
73 | unsigned int map_length; | 82 | unsigned int map_length; |
74 | 83 | ||
@@ -77,6 +86,19 @@ struct GNUNET_CONTAINER_MultiHashMap32 | |||
77 | * to the map, so that iterators can check if they are still valid. | 86 | * to the map, so that iterators can check if they are still valid. |
78 | */ | 87 | */ |
79 | unsigned int modification_counter; | 88 | unsigned int modification_counter; |
89 | |||
90 | /** | ||
91 | * Map entries indicating iteration positions currently | ||
92 | * in use by #GNUNET_CONTAINER_multihashmap_get_multiple(). | ||
93 | * Only used up to @e next_cache_off. | ||
94 | */ | ||
95 | struct MapEntry *next_cache[NEXT_CACHE_SIZE]; | ||
96 | |||
97 | /** | ||
98 | * Offset of @e next_cache entries in use, must be smaller | ||
99 | * than #NEXT_CACHE_SIZE. | ||
100 | */ | ||
101 | unsigned int next_cache_off; | ||
80 | }; | 102 | }; |
81 | 103 | ||
82 | 104 | ||
@@ -87,7 +109,7 @@ struct GNUNET_CONTAINER_MultiHashMap32 | |||
87 | struct GNUNET_CONTAINER_MultiHashMap32Iterator | 109 | struct GNUNET_CONTAINER_MultiHashMap32Iterator |
88 | { | 110 | { |
89 | /** | 111 | /** |
90 | * Position in the bucket 'idx' | 112 | * Position in the bucket @e idx |
91 | */ | 113 | */ |
92 | struct MapEntry *me; | 114 | struct MapEntry *me; |
93 | 115 | ||
@@ -122,7 +144,8 @@ GNUNET_CONTAINER_multihashmap32_create (unsigned int len) | |||
122 | 144 | ||
123 | GNUNET_assert (len > 0); | 145 | GNUNET_assert (len > 0); |
124 | ret = GNUNET_new (struct GNUNET_CONTAINER_MultiHashMap32); | 146 | ret = GNUNET_new (struct GNUNET_CONTAINER_MultiHashMap32); |
125 | ret->map = GNUNET_malloc (len * sizeof (struct MapEntry *)); | 147 | ret->map = GNUNET_new_array (len, |
148 | struct MapEntry *); | ||
126 | ret->map_length = len; | 149 | ret->map_length = len; |
127 | return ret; | 150 | return ret; |
128 | } | 151 | } |
@@ -135,13 +158,11 @@ GNUNET_CONTAINER_multihashmap32_create (unsigned int len) | |||
135 | * @param map the map | 158 | * @param map the map |
136 | */ | 159 | */ |
137 | void | 160 | void |
138 | GNUNET_CONTAINER_multihashmap32_destroy (struct GNUNET_CONTAINER_MultiHashMap32 | 161 | GNUNET_CONTAINER_multihashmap32_destroy (struct GNUNET_CONTAINER_MultiHashMap32 *map) |
139 | *map) | ||
140 | { | 162 | { |
141 | unsigned int i; | ||
142 | struct MapEntry *e; | 163 | struct MapEntry *e; |
143 | 164 | ||
144 | for (i = 0; i < map->map_length; i++) | 165 | for (unsigned int i = 0; i < map->map_length; i++) |
145 | { | 166 | { |
146 | while (NULL != (e = map->map[i])) | 167 | while (NULL != (e = map->map[i])) |
147 | { | 168 | { |
@@ -165,7 +186,7 @@ static unsigned int | |||
165 | idx_of (const struct GNUNET_CONTAINER_MultiHashMap32 *m, | 186 | idx_of (const struct GNUNET_CONTAINER_MultiHashMap32 *m, |
166 | const uint32_t key) | 187 | const uint32_t key) |
167 | { | 188 | { |
168 | GNUNET_assert (m != NULL); | 189 | GNUNET_assert (NULL != m); |
169 | return ((unsigned int) key) % m->map_length; | 190 | return ((unsigned int) key) % m->map_length; |
170 | } | 191 | } |
171 | 192 | ||
@@ -177,8 +198,7 @@ idx_of (const struct GNUNET_CONTAINER_MultiHashMap32 *m, | |||
177 | * @return the number of key value pairs | 198 | * @return the number of key value pairs |
178 | */ | 199 | */ |
179 | unsigned int | 200 | unsigned int |
180 | GNUNET_CONTAINER_multihashmap32_size (const struct | 201 | GNUNET_CONTAINER_multihashmap32_size (const struct GNUNET_CONTAINER_MultiHashMap32 *map) |
181 | GNUNET_CONTAINER_MultiHashMap32 *map) | ||
182 | { | 202 | { |
183 | return map->size; | 203 | return map->size; |
184 | } | 204 | } |
@@ -195,14 +215,13 @@ GNUNET_CONTAINER_multihashmap32_size (const struct | |||
195 | * key-value pairs with value NULL | 215 | * key-value pairs with value NULL |
196 | */ | 216 | */ |
197 | void * | 217 | void * |
198 | GNUNET_CONTAINER_multihashmap32_get (const struct | 218 | GNUNET_CONTAINER_multihashmap32_get (const struct GNUNET_CONTAINER_MultiHashMap32 *map, |
199 | GNUNET_CONTAINER_MultiHashMap32 *map, | ||
200 | uint32_t key) | 219 | uint32_t key) |
201 | { | 220 | { |
202 | struct MapEntry *e; | 221 | struct MapEntry *e; |
203 | 222 | ||
204 | e = map->map[idx_of (map, key)]; | 223 | e = map->map[idx_of (map, key)]; |
205 | while (e != NULL) | 224 | while (NULL != e) |
206 | { | 225 | { |
207 | if (key == e->key) | 226 | if (key == e->key) |
208 | return e->value; | 227 | return e->value; |
@@ -222,37 +241,61 @@ GNUNET_CONTAINER_multihashmap32_get (const struct | |||
222 | * #GNUNET_SYSERR if it aborted iteration | 241 | * #GNUNET_SYSERR if it aborted iteration |
223 | */ | 242 | */ |
224 | int | 243 | int |
225 | GNUNET_CONTAINER_multihashmap32_iterate (const struct | 244 | GNUNET_CONTAINER_multihashmap32_iterate (struct GNUNET_CONTAINER_MultiHashMap32 *map, |
226 | GNUNET_CONTAINER_MultiHashMap32 *map, | 245 | GNUNET_CONTAINER_HashMapIterator32 it, |
227 | GNUNET_CONTAINER_HashMapIterator32 it, | ||
228 | void *it_cls) | 246 | void *it_cls) |
229 | { | 247 | { |
230 | int count; | 248 | int count; |
231 | unsigned int i; | 249 | struct MapEntry **ce; |
232 | struct MapEntry *e; | ||
233 | struct MapEntry *n; | ||
234 | 250 | ||
235 | count = 0; | 251 | count = 0; |
236 | GNUNET_assert (NULL != map); | 252 | GNUNET_assert (NULL != map); |
237 | for (i = 0; i < map->map_length; i++) | 253 | ce = &map->next_cache[map->next_cache_off]; |
254 | GNUNET_assert (++map->next_cache_off < NEXT_CACHE_SIZE); | ||
255 | for (unsigned int i = 0; i < map->map_length; i++) | ||
238 | { | 256 | { |
239 | n = map->map[i]; | 257 | struct MapEntry *e; |
240 | while (NULL != (e = n)) | 258 | |
259 | *ce = map->map[i]; | ||
260 | while (NULL != (e = *ce)) | ||
241 | { | 261 | { |
242 | n = e->next; | 262 | *ce = e->next; |
243 | if (NULL != it) | 263 | if (NULL != it) |
244 | { | 264 | { |
245 | if (GNUNET_OK != it (it_cls, e->key, e->value)) | 265 | if (GNUNET_OK != it (it_cls, |
266 | e->key, | ||
267 | e->value)) | ||
268 | { | ||
269 | GNUNET_assert (--map->next_cache_off < NEXT_CACHE_SIZE); | ||
246 | return GNUNET_SYSERR; | 270 | return GNUNET_SYSERR; |
271 | } | ||
247 | } | 272 | } |
248 | count++; | 273 | count++; |
249 | } | 274 | } |
250 | } | 275 | } |
276 | GNUNET_assert (--map->next_cache_off < NEXT_CACHE_SIZE); | ||
251 | return count; | 277 | return count; |
252 | } | 278 | } |
253 | 279 | ||
254 | 280 | ||
255 | /** | 281 | /** |
282 | * We are about to free() the @a bme, make sure it is not in | ||
283 | * the list of next values for any iterator in the @a map's next_cache. | ||
284 | * | ||
285 | * @param map the map to check | ||
286 | * @param bme the entry that is about to be free'd | ||
287 | */ | ||
288 | static void | ||
289 | update_next_cache (struct GNUNET_CONTAINER_MultiHashMap32 *map, | ||
290 | const struct MapEntry *me) | ||
291 | { | ||
292 | for (unsigned int i=0;i<map->next_cache_off;i++) | ||
293 | if (map->next_cache[i] == me) | ||
294 | map->next_cache[i] = me->next; | ||
295 | } | ||
296 | |||
297 | |||
298 | /** | ||
256 | * Remove the given key-value pair from the map. Note that if the | 299 | * Remove the given key-value pair from the map. Note that if the |
257 | * key-value pair is in the map multiple times, only one of the pairs | 300 | * key-value pair is in the map multiple times, only one of the pairs |
258 | * will be removed. | 301 | * will be removed. |
@@ -260,13 +303,13 @@ GNUNET_CONTAINER_multihashmap32_iterate (const struct | |||
260 | * @param map the map | 303 | * @param map the map |
261 | * @param key key of the key-value pair | 304 | * @param key key of the key-value pair |
262 | * @param value value of the key-value pair | 305 | * @param value value of the key-value pair |
263 | * @return GNUNET_YES on success, GNUNET_NO if the key-value pair | 306 | * @return #GNUNET_YES on success, #GNUNET_NO if the key-value pair |
264 | * is not in the map | 307 | * is not in the map |
265 | */ | 308 | */ |
266 | int | 309 | int |
267 | GNUNET_CONTAINER_multihashmap32_remove (struct GNUNET_CONTAINER_MultiHashMap32 | 310 | GNUNET_CONTAINER_multihashmap32_remove (struct GNUNET_CONTAINER_MultiHashMap32 *map, |
268 | *map, | 311 | uint32_t key, |
269 | uint32_t key, const void *value) | 312 | const void *value) |
270 | { | 313 | { |
271 | struct MapEntry *e; | 314 | struct MapEntry *e; |
272 | struct MapEntry *p; | 315 | struct MapEntry *p; |
@@ -285,6 +328,8 @@ GNUNET_CONTAINER_multihashmap32_remove (struct GNUNET_CONTAINER_MultiHashMap32 | |||
285 | map->map[i] = e->next; | 328 | map->map[i] = e->next; |
286 | else | 329 | else |
287 | p->next = e->next; | 330 | p->next = e->next; |
331 | update_next_cache (map, | ||
332 | e); | ||
288 | GNUNET_free (e); | 333 | GNUNET_free (e); |
289 | map->size--; | 334 | map->size--; |
290 | return GNUNET_YES; | 335 | return GNUNET_YES; |
@@ -305,9 +350,7 @@ GNUNET_CONTAINER_multihashmap32_remove (struct GNUNET_CONTAINER_MultiHashMap32 | |||
305 | * @return number of values removed | 350 | * @return number of values removed |
306 | */ | 351 | */ |
307 | int | 352 | int |
308 | GNUNET_CONTAINER_multihashmap32_remove_all (struct | 353 | GNUNET_CONTAINER_multihashmap32_remove_all (struct GNUNET_CONTAINER_MultiHashMap32 *map, |
309 | GNUNET_CONTAINER_MultiHashMap32 | ||
310 | *map, | ||
311 | uint32_t key) | 354 | uint32_t key) |
312 | { | 355 | { |
313 | struct MapEntry *e; | 356 | struct MapEntry *e; |
@@ -329,6 +372,8 @@ GNUNET_CONTAINER_multihashmap32_remove_all (struct | |||
329 | map->map[i] = e->next; | 372 | map->map[i] = e->next; |
330 | else | 373 | else |
331 | p->next = e->next; | 374 | p->next = e->next; |
375 | update_next_cache (map, | ||
376 | e); | ||
332 | GNUNET_free (e); | 377 | GNUNET_free (e); |
333 | map->size--; | 378 | map->size--; |
334 | if (p == NULL) | 379 | if (p == NULL) |
@@ -353,12 +398,11 @@ GNUNET_CONTAINER_multihashmap32_remove_all (struct | |||
353 | * | 398 | * |
354 | * @param map the map | 399 | * @param map the map |
355 | * @param key the key to test if a value exists for it | 400 | * @param key the key to test if a value exists for it |
356 | * @return GNUNET_YES if such a value exists, | 401 | * @return #GNUNET_YES if such a value exists, |
357 | * GNUNET_NO if not | 402 | * #GNUNET_NO if not |
358 | */ | 403 | */ |
359 | int | 404 | int |
360 | GNUNET_CONTAINER_multihashmap32_contains (const struct | 405 | GNUNET_CONTAINER_multihashmap32_contains (const struct GNUNET_CONTAINER_MultiHashMap32 *map, |
361 | GNUNET_CONTAINER_MultiHashMap32 *map, | ||
362 | uint32_t key) | 406 | uint32_t key) |
363 | { | 407 | { |
364 | struct MapEntry *e; | 408 | struct MapEntry *e; |
@@ -381,13 +425,11 @@ GNUNET_CONTAINER_multihashmap32_contains (const struct | |||
381 | * @param map the map | 425 | * @param map the map |
382 | * @param key the key to test if a value exists for it | 426 | * @param key the key to test if a value exists for it |
383 | * @param value value to test for | 427 | * @param value value to test for |
384 | * @return GNUNET_YES if such a value exists, | 428 | * @return #GNUNET_YES if such a value exists, |
385 | * GNUNET_NO if not | 429 | * #GNUNET_NO if not |
386 | */ | 430 | */ |
387 | int | 431 | int |
388 | GNUNET_CONTAINER_multihashmap32_contains_value (const struct | 432 | GNUNET_CONTAINER_multihashmap32_contains_value (const struct GNUNET_CONTAINER_MultiHashMap32 *map, |
389 | GNUNET_CONTAINER_MultiHashMap32 | ||
390 | *map, | ||
391 | uint32_t key, | 433 | uint32_t key, |
392 | const void *value) | 434 | const void *value) |
393 | { | 435 | { |
@@ -418,17 +460,17 @@ grow (struct GNUNET_CONTAINER_MultiHashMap32 *map) | |||
418 | unsigned int old_len; | 460 | unsigned int old_len; |
419 | unsigned int new_len; | 461 | unsigned int new_len; |
420 | unsigned int idx; | 462 | unsigned int idx; |
421 | unsigned int i; | ||
422 | 463 | ||
423 | map->modification_counter++; | 464 | map->modification_counter++; |
424 | 465 | ||
425 | old_map = map->map; | 466 | old_map = map->map; |
426 | old_len = map->map_length; | 467 | old_len = map->map_length; |
427 | new_len = old_len * 2; | 468 | new_len = old_len * 2; |
428 | new_map = GNUNET_malloc (sizeof (struct MapEntry *) * new_len); | 469 | new_map = GNUNET_new_array (new_len, |
470 | struct MapEntry *); | ||
429 | map->map_length = new_len; | 471 | map->map_length = new_len; |
430 | map->map = new_map; | 472 | map->map = new_map; |
431 | for (i = 0; i < old_len; i++) | 473 | for (unsigned int i = 0; i < old_len; i++) |
432 | { | 474 | { |
433 | while (NULL != (e = old_map[i])) | 475 | while (NULL != (e = old_map[i])) |
434 | { | 476 | { |
@@ -449,9 +491,9 @@ grow (struct GNUNET_CONTAINER_MultiHashMap32 *map) | |||
449 | * @param key key to use | 491 | * @param key key to use |
450 | * @param value value to use | 492 | * @param value value to use |
451 | * @param opt options for put | 493 | * @param opt options for put |
452 | * @return GNUNET_OK on success, | 494 | * @return #GNUNET_OK on success, |
453 | * GNUNET_NO if a value was replaced (with REPLACE) | 495 | * #GNUNET_NO if a value was replaced (with REPLACE) |
454 | * GNUNET_SYSERR if UNIQUE_ONLY was the option and the | 496 | * #GNUNET_SYSERR if UNIQUE_ONLY was the option and the |
455 | * value already exists | 497 | * value already exists |
456 | */ | 498 | */ |
457 | int | 499 | int |
@@ -501,32 +543,41 @@ GNUNET_CONTAINER_multihashmap32_put (struct GNUNET_CONTAINER_MultiHashMap32 | |||
501 | * @param map the map | 543 | * @param map the map |
502 | * @param key key that the entries must correspond to | 544 | * @param key key that the entries must correspond to |
503 | * @param it function to call on each entry | 545 | * @param it function to call on each entry |
504 | * @param it_cls extra argument to it | 546 | * @param it_cls extra argument to @a it |
505 | * @return the number of key value pairs processed, | 547 | * @return the number of key value pairs processed, |
506 | * GNUNET_SYSERR if it aborted iteration | 548 | * GNUNET_SYSERR if it aborted iteration |
507 | */ | 549 | */ |
508 | int | 550 | int |
509 | GNUNET_CONTAINER_multihashmap32_get_multiple (const struct | 551 | GNUNET_CONTAINER_multihashmap32_get_multiple (struct GNUNET_CONTAINER_MultiHashMap32 *map, |
510 | GNUNET_CONTAINER_MultiHashMap32 | 552 | uint32_t key, |
511 | *map, uint32_t key, | 553 | GNUNET_CONTAINER_HashMapIterator32 it, |
512 | GNUNET_CONTAINER_HashMapIterator32 | 554 | void *it_cls) |
513 | it, void *it_cls) | ||
514 | { | 555 | { |
515 | int count; | 556 | int count; |
516 | struct MapEntry *e; | 557 | struct MapEntry *e; |
517 | struct MapEntry *n; | 558 | struct MapEntry **ce; |
518 | 559 | ||
519 | count = 0; | 560 | count = 0; |
520 | n = map->map[idx_of (map, key)]; | 561 | ce = &map->next_cache[map->next_cache_off]; |
521 | while (NULL != (e = n)) | 562 | GNUNET_assert (++map->next_cache_off < NEXT_CACHE_SIZE); |
563 | |||
564 | *ce = map->map[idx_of (map, key)]; | ||
565 | while (NULL != (e = *ce)) | ||
522 | { | 566 | { |
523 | n = e->next; | 567 | *ce = e->next; |
524 | if (key != e->key) | 568 | if (key != e->key) |
525 | continue; | 569 | continue; |
526 | if ((it != NULL) && (GNUNET_OK != it (it_cls, key, e->value))) | 570 | if ( (NULL != it) && |
527 | return GNUNET_SYSERR; | 571 | (GNUNET_OK != it (it_cls, |
572 | key, | ||
573 | e->value)) ) | ||
574 | { | ||
575 | GNUNET_assert (--map->next_cache_off < NEXT_CACHE_SIZE); | ||
576 | return GNUNET_SYSERR; | ||
577 | } | ||
528 | count++; | 578 | count++; |
529 | } | 579 | } |
580 | GNUNET_assert (--map->next_cache_off < NEXT_CACHE_SIZE); | ||
530 | return count; | 581 | return count; |
531 | } | 582 | } |
532 | 583 | ||
@@ -541,7 +592,7 @@ GNUNET_CONTAINER_multihashmap32_get_multiple (const struct | |||
541 | * result in skipped or repeated elements. | 592 | * result in skipped or repeated elements. |
542 | * | 593 | * |
543 | * @param map the map to create an iterator for | 594 | * @param map the map to create an iterator for |
544 | * @return an iterator over the given multihashmap 'map' | 595 | * @return an iterator over the given multihashmap @a map |
545 | */ | 596 | */ |
546 | struct GNUNET_CONTAINER_MultiHashMap32Iterator * | 597 | struct GNUNET_CONTAINER_MultiHashMap32Iterator * |
547 | GNUNET_CONTAINER_multihashmap32_iterator_create (const struct GNUNET_CONTAINER_MultiHashMap32 *map) | 598 | GNUNET_CONTAINER_multihashmap32_iterator_create (const struct GNUNET_CONTAINER_MultiHashMap32 *map) |