diff options
Diffstat (limited to 'src')
-rw-r--r-- | src/include/gnunet_container_lib.h | 17 | ||||
-rw-r--r-- | src/util/container_multihashmap.c | 210 | ||||
-rw-r--r-- | src/util/container_multihashmap32.c | 159 | ||||
-rw-r--r-- | src/util/container_multipeermap.c | 282 | ||||
-rw-r--r-- | src/util/container_multishortmap.c | 286 |
5 files changed, 634 insertions, 320 deletions
diff --git a/src/include/gnunet_container_lib.h b/src/include/gnunet_container_lib.h index 2de65b2f1..bd9ce7bb2 100644 --- a/src/include/gnunet_container_lib.h +++ b/src/include/gnunet_container_lib.h | |||
@@ -928,7 +928,7 @@ GNUNET_CONTAINER_multihashmap_size (const struct GNUNET_CONTAINER_MultiHashMap * | |||
928 | * #GNUNET_SYSERR if it aborted iteration | 928 | * #GNUNET_SYSERR if it aborted iteration |
929 | */ | 929 | */ |
930 | int | 930 | int |
931 | GNUNET_CONTAINER_multihashmap_iterate (const struct GNUNET_CONTAINER_MultiHashMap *map, | 931 | GNUNET_CONTAINER_multihashmap_iterate (struct GNUNET_CONTAINER_MultiHashMap *map, |
932 | GNUNET_CONTAINER_HashMapIterator it, | 932 | GNUNET_CONTAINER_HashMapIterator it, |
933 | void *it_cls); | 933 | void *it_cls); |
934 | 934 | ||
@@ -993,7 +993,7 @@ GNUNET_CONTAINER_multihashmap_iterator_destroy (struct GNUNET_CONTAINER_MultiHas | |||
993 | * #GNUNET_SYSERR if it aborted iteration | 993 | * #GNUNET_SYSERR if it aborted iteration |
994 | */ | 994 | */ |
995 | int | 995 | int |
996 | GNUNET_CONTAINER_multihashmap_get_multiple (const struct GNUNET_CONTAINER_MultiHashMap *map, | 996 | GNUNET_CONTAINER_multihashmap_get_multiple (struct GNUNET_CONTAINER_MultiHashMap *map, |
997 | const struct GNUNET_HashCode *key, | 997 | const struct GNUNET_HashCode *key, |
998 | GNUNET_CONTAINER_HashMapIterator it, | 998 | GNUNET_CONTAINER_HashMapIterator it, |
999 | void *it_cls); | 999 | void *it_cls); |
@@ -1194,7 +1194,7 @@ GNUNET_CONTAINER_multipeermap_size (const struct GNUNET_CONTAINER_MultiPeerMap * | |||
1194 | * #GNUNET_SYSERR if it aborted iteration | 1194 | * #GNUNET_SYSERR if it aborted iteration |
1195 | */ | 1195 | */ |
1196 | int | 1196 | int |
1197 | GNUNET_CONTAINER_multipeermap_iterate (const struct GNUNET_CONTAINER_MultiPeerMap *map, | 1197 | GNUNET_CONTAINER_multipeermap_iterate (struct GNUNET_CONTAINER_MultiPeerMap *map, |
1198 | GNUNET_CONTAINER_PeerMapIterator it, | 1198 | GNUNET_CONTAINER_PeerMapIterator it, |
1199 | void *it_cls); | 1199 | void *it_cls); |
1200 | 1200 | ||
@@ -1260,7 +1260,7 @@ GNUNET_CONTAINER_multipeermap_iterator_destroy (struct GNUNET_CONTAINER_MultiPee | |||
1260 | * #GNUNET_SYSERR if it aborted iteration | 1260 | * #GNUNET_SYSERR if it aborted iteration |
1261 | */ | 1261 | */ |
1262 | int | 1262 | int |
1263 | GNUNET_CONTAINER_multipeermap_get_multiple (const struct GNUNET_CONTAINER_MultiPeerMap *map, | 1263 | GNUNET_CONTAINER_multipeermap_get_multiple (struct GNUNET_CONTAINER_MultiPeerMap *map, |
1264 | const struct GNUNET_PeerIdentity *key, | 1264 | const struct GNUNET_PeerIdentity *key, |
1265 | GNUNET_CONTAINER_PeerMapIterator it, | 1265 | GNUNET_CONTAINER_PeerMapIterator it, |
1266 | void *it_cls); | 1266 | void *it_cls); |
@@ -1461,7 +1461,7 @@ GNUNET_CONTAINER_multishortmap_size (const struct GNUNET_CONTAINER_MultiShortmap | |||
1461 | * #GNUNET_SYSERR if it aborted iteration | 1461 | * #GNUNET_SYSERR if it aborted iteration |
1462 | */ | 1462 | */ |
1463 | int | 1463 | int |
1464 | GNUNET_CONTAINER_multishortmap_iterate (const struct GNUNET_CONTAINER_MultiShortmap *map, | 1464 | GNUNET_CONTAINER_multishortmap_iterate (struct GNUNET_CONTAINER_MultiShortmap *map, |
1465 | GNUNET_CONTAINER_ShortmapIterator it, | 1465 | GNUNET_CONTAINER_ShortmapIterator it, |
1466 | void *it_cls); | 1466 | void *it_cls); |
1467 | 1467 | ||
@@ -1529,7 +1529,7 @@ GNUNET_CONTAINER_multishortmap_iterator_destroy (struct GNUNET_CONTAINER_MultiSh | |||
1529 | * #GNUNET_SYSERR if it aborted iteration | 1529 | * #GNUNET_SYSERR if it aborted iteration |
1530 | */ | 1530 | */ |
1531 | int | 1531 | int |
1532 | GNUNET_CONTAINER_multishortmap_get_multiple (const struct GNUNET_CONTAINER_MultiShortmap *map, | 1532 | GNUNET_CONTAINER_multishortmap_get_multiple (struct GNUNET_CONTAINER_MultiShortmap *map, |
1533 | const struct GNUNET_ShortHashCode *key, | 1533 | const struct GNUNET_ShortHashCode *key, |
1534 | GNUNET_CONTAINER_ShortmapIterator it, | 1534 | GNUNET_CONTAINER_ShortmapIterator it, |
1535 | void *it_cls); | 1535 | void *it_cls); |
@@ -1648,8 +1648,7 @@ GNUNET_CONTAINER_multihashmap32_get (const struct | |||
1648 | * #GNUNET_SYSERR if it aborted iteration | 1648 | * #GNUNET_SYSERR if it aborted iteration |
1649 | */ | 1649 | */ |
1650 | int | 1650 | int |
1651 | GNUNET_CONTAINER_multihashmap32_iterate (const struct | 1651 | GNUNET_CONTAINER_multihashmap32_iterate (struct GNUNET_CONTAINER_MultiHashMap32 *map, |
1652 | GNUNET_CONTAINER_MultiHashMap32 *map, | ||
1653 | GNUNET_CONTAINER_HashMapIterator32 it, | 1652 | GNUNET_CONTAINER_HashMapIterator32 it, |
1654 | void *it_cls); | 1653 | void *it_cls); |
1655 | 1654 | ||
@@ -1750,7 +1749,7 @@ GNUNET_CONTAINER_multihashmap32_put (struct GNUNET_CONTAINER_MultiHashMap32 *map | |||
1750 | * #GNUNET_SYSERR if it aborted iteration | 1749 | * #GNUNET_SYSERR if it aborted iteration |
1751 | */ | 1750 | */ |
1752 | int | 1751 | int |
1753 | GNUNET_CONTAINER_multihashmap32_get_multiple (const struct GNUNET_CONTAINER_MultiHashMap32 *map, | 1752 | GNUNET_CONTAINER_multihashmap32_get_multiple (struct GNUNET_CONTAINER_MultiHashMap32 *map, |
1754 | uint32_t key, | 1753 | uint32_t key, |
1755 | GNUNET_CONTAINER_HashMapIterator32 it, | 1754 | GNUNET_CONTAINER_HashMapIterator32 it, |
1756 | void *it_cls); | 1755 | void *it_cls); |
diff --git a/src/util/container_multihashmap.c b/src/util/container_multihashmap.c index 1811f861f..e344c2aec 100644 --- a/src/util/container_multihashmap.c +++ b/src/util/container_multihashmap.c | |||
@@ -27,6 +27,15 @@ | |||
27 | #define LOG(kind,...) GNUNET_log_from (kind, "util-container-multihashmap", __VA_ARGS__) | 27 | #define LOG(kind,...) GNUNET_log_from (kind, "util-container-multihashmap", __VA_ARGS__) |
28 | 28 | ||
29 | /** | 29 | /** |
30 | * Maximum recursion depth for callbacks of | ||
31 | * #GNUNET_CONTAINER_multihashmap_get_multiple() themselve s | ||
32 | * again calling #GNUNET_CONTAINER_multihashmap_get_multiple(). | ||
33 | * Should be totally excessive, but if violated we die. | ||
34 | */ | ||
35 | #define NEXT_CACHE_SIZE 16 | ||
36 | |||
37 | |||
38 | /** | ||
30 | * An entry in the hash map with the full key. | 39 | * An entry in the hash map with the full key. |
31 | */ | 40 | */ |
32 | struct BigMapEntry | 41 | struct BigMapEntry |
@@ -122,6 +131,19 @@ struct GNUNET_CONTAINER_MultiHashMap | |||
122 | * to the map, so that iterators can check if they are still valid. | 131 | * to the map, so that iterators can check if they are still valid. |
123 | */ | 132 | */ |
124 | unsigned int modification_counter; | 133 | unsigned int modification_counter; |
134 | |||
135 | /** | ||
136 | * Map entries indicating iteration positions currently | ||
137 | * in use by #GNUNET_CONTAINER_multihashmap_get_multiple(). | ||
138 | * Only used up to @e next_cache_off. | ||
139 | */ | ||
140 | union MapEntry next_cache[NEXT_CACHE_SIZE]; | ||
141 | |||
142 | /** | ||
143 | * Offset of @e next_cache entries in use, must be smaller | ||
144 | * than #NEXT_CACHE_SIZE. | ||
145 | */ | ||
146 | unsigned int next_cache_off; | ||
125 | }; | 147 | }; |
126 | 148 | ||
127 | 149 | ||
@@ -132,7 +154,7 @@ struct GNUNET_CONTAINER_MultiHashMap | |||
132 | struct GNUNET_CONTAINER_MultiHashMapIterator | 154 | struct GNUNET_CONTAINER_MultiHashMapIterator |
133 | { | 155 | { |
134 | /** | 156 | /** |
135 | * Position in the bucket 'idx' | 157 | * Position in the bucket @e idx |
136 | */ | 158 | */ |
137 | union MapEntry me; | 159 | union MapEntry me; |
138 | 160 | ||
@@ -207,15 +229,15 @@ GNUNET_CONTAINER_multihashmap_create (unsigned int len, | |||
207 | 229 | ||
208 | 230 | ||
209 | /** | 231 | /** |
210 | * Destroy a hash map. Will not free any values | 232 | * Destroy a hash map. Will not free any values stored in the hash |
211 | * stored in the hash map! | 233 | * map! |
212 | * | 234 | * |
213 | * @param map the map | 235 | * @param map the map |
214 | */ | 236 | */ |
215 | void | 237 | void |
216 | GNUNET_CONTAINER_multihashmap_destroy (struct GNUNET_CONTAINER_MultiHashMap | 238 | GNUNET_CONTAINER_multihashmap_destroy (struct GNUNET_CONTAINER_MultiHashMap *map) |
217 | *map) | ||
218 | { | 239 | { |
240 | GNUNET_assert (0 == map->next_cache_off); | ||
219 | for (unsigned int i = 0; i < map->map_length; i++) | 241 | for (unsigned int i = 0; i < map->map_length; i++) |
220 | { | 242 | { |
221 | union MapEntry me; | 243 | union MapEntry me; |
@@ -304,7 +326,9 @@ GNUNET_CONTAINER_multihashmap_get (const struct GNUNET_CONTAINER_MultiHashMap *m | |||
304 | struct SmallMapEntry *sme; | 326 | struct SmallMapEntry *sme; |
305 | 327 | ||
306 | for (sme = me.sme; NULL != sme; sme = sme->next) | 328 | for (sme = me.sme; NULL != sme; sme = sme->next) |
307 | if (0 == memcmp (key, sme->key, sizeof (struct GNUNET_HashCode))) | 329 | if (0 == memcmp (key, |
330 | sme->key, | ||
331 | sizeof (struct GNUNET_HashCode))) | ||
308 | return sme->value; | 332 | return sme->value; |
309 | } | 333 | } |
310 | else | 334 | else |
@@ -312,7 +336,9 @@ GNUNET_CONTAINER_multihashmap_get (const struct GNUNET_CONTAINER_MultiHashMap *m | |||
312 | struct BigMapEntry *bme; | 336 | struct BigMapEntry *bme; |
313 | 337 | ||
314 | for (bme = me.bme; NULL != bme; bme = bme->next) | 338 | for (bme = me.bme; NULL != bme; bme = bme->next) |
315 | if (0 == memcmp (key, &bme->key, sizeof (struct GNUNET_HashCode))) | 339 | if (0 == memcmp (key, |
340 | &bme->key, | ||
341 | sizeof (struct GNUNET_HashCode))) | ||
316 | return bme->value; | 342 | return bme->value; |
317 | } | 343 | } |
318 | return NULL; | 344 | return NULL; |
@@ -329,34 +355,39 @@ GNUNET_CONTAINER_multihashmap_get (const struct GNUNET_CONTAINER_MultiHashMap *m | |||
329 | * #GNUNET_SYSERR if it aborted iteration | 355 | * #GNUNET_SYSERR if it aborted iteration |
330 | */ | 356 | */ |
331 | int | 357 | int |
332 | GNUNET_CONTAINER_multihashmap_iterate (const struct | 358 | GNUNET_CONTAINER_multihashmap_iterate (struct GNUNET_CONTAINER_MultiHashMap *map, |
333 | GNUNET_CONTAINER_MultiHashMap *map, | ||
334 | GNUNET_CONTAINER_HashMapIterator it, | 359 | GNUNET_CONTAINER_HashMapIterator it, |
335 | void *it_cls) | 360 | void *it_cls) |
336 | { | 361 | { |
337 | int count; | 362 | int count; |
338 | unsigned int i; | ||
339 | union MapEntry me; | 363 | union MapEntry me; |
364 | union MapEntry *ce; | ||
340 | struct GNUNET_HashCode kc; | 365 | struct GNUNET_HashCode kc; |
341 | 366 | ||
342 | count = 0; | ||
343 | GNUNET_assert (NULL != map); | 367 | GNUNET_assert (NULL != map); |
344 | for (i = 0; i < map->map_length; i++) | 368 | ce = &map->next_cache[map->next_cache_off]; |
369 | GNUNET_assert (++map->next_cache_off < NEXT_CACHE_SIZE); | ||
370 | count = 0; | ||
371 | for (unsigned i = 0; i < map->map_length; i++) | ||
345 | { | 372 | { |
346 | me = map->map[i]; | 373 | me = map->map[i]; |
347 | if (map->use_small_entries) | 374 | if (map->use_small_entries) |
348 | { | 375 | { |
349 | struct SmallMapEntry *sme; | 376 | struct SmallMapEntry *sme; |
350 | struct SmallMapEntry *nxt; | ||
351 | 377 | ||
352 | nxt = me.sme; | 378 | ce->sme = me.sme; |
353 | while (NULL != (sme = nxt)) | 379 | while (NULL != (sme = ce->sme)) |
354 | { | 380 | { |
355 | nxt = sme->next; | 381 | ce->sme = sme->next; |
356 | if (NULL != it) | 382 | if (NULL != it) |
357 | { | 383 | { |
358 | if (GNUNET_OK != it (it_cls, sme->key, sme->value)) | 384 | if (GNUNET_OK != it (it_cls, |
385 | sme->key, | ||
386 | sme->value)) | ||
387 | { | ||
388 | GNUNET_assert (--map->next_cache_off < NEXT_CACHE_SIZE); | ||
359 | return GNUNET_SYSERR; | 389 | return GNUNET_SYSERR; |
390 | } | ||
360 | } | 391 | } |
361 | count++; | 392 | count++; |
362 | } | 393 | } |
@@ -364,27 +395,66 @@ GNUNET_CONTAINER_multihashmap_iterate (const struct | |||
364 | else | 395 | else |
365 | { | 396 | { |
366 | struct BigMapEntry *bme; | 397 | struct BigMapEntry *bme; |
367 | struct BigMapEntry *nxt; | ||
368 | 398 | ||
369 | nxt = me.bme; | 399 | ce->bme = me.bme; |
370 | while (NULL != (bme = nxt)) | 400 | while (NULL != (bme = ce->bme)) |
371 | { | 401 | { |
372 | nxt = bme->next; | 402 | ce->bme = bme->next; |
373 | if (NULL != it) | 403 | if (NULL != it) |
374 | { | 404 | { |
375 | kc = bme->key; | 405 | kc = bme->key; |
376 | if (GNUNET_OK != it (it_cls, &kc, bme->value)) | 406 | if (GNUNET_OK != it (it_cls, |
407 | &kc, | ||
408 | bme->value)) | ||
409 | { | ||
410 | GNUNET_assert (--map->next_cache_off < NEXT_CACHE_SIZE); | ||
377 | return GNUNET_SYSERR; | 411 | return GNUNET_SYSERR; |
412 | } | ||
378 | } | 413 | } |
379 | count++; | 414 | count++; |
380 | } | 415 | } |
381 | } | 416 | } |
382 | } | 417 | } |
418 | GNUNET_assert (--map->next_cache_off < NEXT_CACHE_SIZE); | ||
383 | return count; | 419 | return count; |
384 | } | 420 | } |
385 | 421 | ||
386 | 422 | ||
387 | /** | 423 | /** |
424 | * We are about to free() the @a bme, make sure it is not in | ||
425 | * the list of next values for any iterator in the @a map's next_cache. | ||
426 | * | ||
427 | * @param map the map to check | ||
428 | * @param bme the entry that is about to be free'd | ||
429 | */ | ||
430 | static void | ||
431 | update_next_cache_bme (struct GNUNET_CONTAINER_MultiHashMap *map, | ||
432 | const struct BigMapEntry *bme) | ||
433 | { | ||
434 | for (unsigned int i=0;i<map->next_cache_off;i++) | ||
435 | if (map->next_cache[i].bme == bme) | ||
436 | map->next_cache[i].bme = bme->next; | ||
437 | } | ||
438 | |||
439 | |||
440 | /** | ||
441 | * We are about to free() the @a sme, make sure it is not in | ||
442 | * the list of next values for any iterator in the @a map's next_cache. | ||
443 | * | ||
444 | * @param map the map to check | ||
445 | * @param sme the entry that is about to be free'd | ||
446 | */ | ||
447 | static void | ||
448 | update_next_cache_sme (struct GNUNET_CONTAINER_MultiHashMap *map, | ||
449 | const struct SmallMapEntry *sme) | ||
450 | { | ||
451 | for (unsigned int i=0;i<map->next_cache_off;i++) | ||
452 | if (map->next_cache[i].sme == sme) | ||
453 | map->next_cache[i].sme = sme->next; | ||
454 | } | ||
455 | |||
456 | |||
457 | /** | ||
388 | * Remove the given key-value pair from the map. Note that if the | 458 | * Remove the given key-value pair from the map. Note that if the |
389 | * key-value pair is in the map multiple times, only one of the pairs | 459 | * key-value pair is in the map multiple times, only one of the pairs |
390 | * will be removed. | 460 | * will be removed. |
@@ -409,19 +479,22 @@ GNUNET_CONTAINER_multihashmap_remove (struct GNUNET_CONTAINER_MultiHashMap *map, | |||
409 | me = map->map[i]; | 479 | me = map->map[i]; |
410 | if (map->use_small_entries) | 480 | if (map->use_small_entries) |
411 | { | 481 | { |
412 | struct SmallMapEntry *sme; | ||
413 | struct SmallMapEntry *p; | 482 | struct SmallMapEntry *p; |
414 | 483 | ||
415 | p = NULL; | 484 | p = NULL; |
416 | for (sme = me.sme; NULL != sme; sme = sme->next) | 485 | for (struct SmallMapEntry *sme = me.sme; NULL != sme; sme = sme->next) |
417 | { | 486 | { |
418 | if ((0 == memcmp (key, sme->key, sizeof (struct GNUNET_HashCode))) && | 487 | if ( (0 == memcmp (key, |
419 | (value == sme->value)) | 488 | sme->key, |
489 | sizeof (struct GNUNET_HashCode))) && | ||
490 | (value == sme->value) ) | ||
420 | { | 491 | { |
421 | if (NULL == p) | 492 | if (NULL == p) |
422 | map->map[i].sme = sme->next; | 493 | map->map[i].sme = sme->next; |
423 | else | 494 | else |
424 | p->next = sme->next; | 495 | p->next = sme->next; |
496 | update_next_cache_sme (map, | ||
497 | sme); | ||
425 | GNUNET_free (sme); | 498 | GNUNET_free (sme); |
426 | map->size--; | 499 | map->size--; |
427 | return GNUNET_YES; | 500 | return GNUNET_YES; |
@@ -431,19 +504,22 @@ GNUNET_CONTAINER_multihashmap_remove (struct GNUNET_CONTAINER_MultiHashMap *map, | |||
431 | } | 504 | } |
432 | else | 505 | else |
433 | { | 506 | { |
434 | struct BigMapEntry *bme; | ||
435 | struct BigMapEntry *p; | 507 | struct BigMapEntry *p; |
436 | 508 | ||
437 | p = NULL; | 509 | p = NULL; |
438 | for (bme = me.bme; NULL != bme; bme = bme->next) | 510 | for (struct BigMapEntry *bme = me.bme; NULL != bme; bme = bme->next) |
439 | { | 511 | { |
440 | if ((0 == memcmp (key, &bme->key, sizeof (struct GNUNET_HashCode))) && | 512 | if ( (0 == memcmp (key, |
441 | (value == bme->value)) | 513 | &bme->key, |
514 | sizeof (struct GNUNET_HashCode))) && | ||
515 | (value == bme->value) ) | ||
442 | { | 516 | { |
443 | if (NULL == p) | 517 | if (NULL == p) |
444 | map->map[i].bme = bme->next; | 518 | map->map[i].bme = bme->next; |
445 | else | 519 | else |
446 | p->next = bme->next; | 520 | p->next = bme->next; |
521 | update_next_cache_bme (map, | ||
522 | bme); | ||
447 | GNUNET_free (bme); | 523 | GNUNET_free (bme); |
448 | map->size--; | 524 | map->size--; |
449 | return GNUNET_YES; | 525 | return GNUNET_YES; |
@@ -485,12 +561,16 @@ GNUNET_CONTAINER_multihashmap_remove_all (struct GNUNET_CONTAINER_MultiHashMap * | |||
485 | sme = me.sme; | 561 | sme = me.sme; |
486 | while (NULL != sme) | 562 | while (NULL != sme) |
487 | { | 563 | { |
488 | if (0 == memcmp (key, sme->key, sizeof (struct GNUNET_HashCode))) | 564 | if (0 == memcmp (key, |
565 | sme->key, | ||
566 | sizeof (struct GNUNET_HashCode))) | ||
489 | { | 567 | { |
490 | if (NULL == p) | 568 | if (NULL == p) |
491 | map->map[i].sme = sme->next; | 569 | map->map[i].sme = sme->next; |
492 | else | 570 | else |
493 | p->next = sme->next; | 571 | p->next = sme->next; |
572 | update_next_cache_sme (map, | ||
573 | sme); | ||
494 | GNUNET_free (sme); | 574 | GNUNET_free (sme); |
495 | map->size--; | 575 | map->size--; |
496 | if (NULL == p) | 576 | if (NULL == p) |
@@ -515,12 +595,16 @@ GNUNET_CONTAINER_multihashmap_remove_all (struct GNUNET_CONTAINER_MultiHashMap * | |||
515 | bme = me.bme; | 595 | bme = me.bme; |
516 | while (NULL != bme) | 596 | while (NULL != bme) |
517 | { | 597 | { |
518 | if (0 == memcmp (key, &bme->key, sizeof (struct GNUNET_HashCode))) | 598 | if (0 == memcmp (key, |
599 | &bme->key, | ||
600 | sizeof (struct GNUNET_HashCode))) | ||
519 | { | 601 | { |
520 | if (NULL == p) | 602 | if (NULL == p) |
521 | map->map[i].bme = bme->next; | 603 | map->map[i].bme = bme->next; |
522 | else | 604 | else |
523 | p->next = bme->next; | 605 | p->next = bme->next; |
606 | update_next_cache_bme (map, | ||
607 | bme); | ||
524 | GNUNET_free (bme); | 608 | GNUNET_free (bme); |
525 | map->size--; | 609 | map->size--; |
526 | if (NULL == p) | 610 | if (NULL == p) |
@@ -631,9 +715,8 @@ GNUNET_CONTAINER_multihashmap_contains (const struct | |||
631 | * #GNUNET_NO if not | 715 | * #GNUNET_NO if not |
632 | */ | 716 | */ |
633 | int | 717 | int |
634 | GNUNET_CONTAINER_multihashmap_contains_value (const struct | 718 | GNUNET_CONTAINER_multihashmap_contains_value (const struct GNUNET_CONTAINER_MultiHashMap *map, |
635 | GNUNET_CONTAINER_MultiHashMap | 719 | const struct GNUNET_HashCode *key, |
636 | *map, const struct GNUNET_HashCode *key, | ||
637 | const void *value) | 720 | const void *value) |
638 | { | 721 | { |
639 | union MapEntry me; | 722 | union MapEntry me; |
@@ -644,7 +727,9 @@ GNUNET_CONTAINER_multihashmap_contains_value (const struct | |||
644 | struct SmallMapEntry *sme; | 727 | struct SmallMapEntry *sme; |
645 | 728 | ||
646 | for (sme = me.sme; NULL != sme; sme = sme->next) | 729 | for (sme = me.sme; NULL != sme; sme = sme->next) |
647 | if ( (0 == memcmp (key, sme->key, sizeof (struct GNUNET_HashCode))) && | 730 | if ( (0 == memcmp (key, |
731 | sme->key, | ||
732 | sizeof (struct GNUNET_HashCode))) && | ||
648 | (sme->value == value) ) | 733 | (sme->value == value) ) |
649 | return GNUNET_YES; | 734 | return GNUNET_YES; |
650 | } | 735 | } |
@@ -653,7 +738,9 @@ GNUNET_CONTAINER_multihashmap_contains_value (const struct | |||
653 | struct BigMapEntry *bme; | 738 | struct BigMapEntry *bme; |
654 | 739 | ||
655 | for (bme = me.bme; NULL != bme; bme = bme->next) | 740 | for (bme = me.bme; NULL != bme; bme = bme->next) |
656 | if ( (0 == memcmp (key, &bme->key, sizeof (struct GNUNET_HashCode))) && | 741 | if ( (0 == memcmp (key, |
742 | &bme->key, | ||
743 | sizeof (struct GNUNET_HashCode))) && | ||
657 | (bme->value == value) ) | 744 | (bme->value == value) ) |
658 | return GNUNET_YES; | 745 | return GNUNET_YES; |
659 | } | 746 | } |
@@ -814,49 +901,66 @@ GNUNET_CONTAINER_multihashmap_put (struct GNUNET_CONTAINER_MultiHashMap *map, | |||
814 | * #GNUNET_SYSERR if it aborted iteration | 901 | * #GNUNET_SYSERR if it aborted iteration |
815 | */ | 902 | */ |
816 | int | 903 | int |
817 | GNUNET_CONTAINER_multihashmap_get_multiple (const struct | 904 | GNUNET_CONTAINER_multihashmap_get_multiple (struct GNUNET_CONTAINER_MultiHashMap *map, |
818 | GNUNET_CONTAINER_MultiHashMap *map, | ||
819 | const struct GNUNET_HashCode *key, | 905 | const struct GNUNET_HashCode *key, |
820 | GNUNET_CONTAINER_HashMapIterator it, | 906 | GNUNET_CONTAINER_HashMapIterator it, |
821 | void *it_cls) | 907 | void *it_cls) |
822 | { | 908 | { |
823 | int count; | 909 | int count; |
824 | union MapEntry me; | 910 | union MapEntry *me; |
911 | union MapEntry *ce; | ||
825 | 912 | ||
913 | ce = &map->next_cache[map->next_cache_off]; | ||
914 | GNUNET_assert (++map->next_cache_off < NEXT_CACHE_SIZE); | ||
826 | count = 0; | 915 | count = 0; |
827 | me = map->map[idx_of (map, key)]; | 916 | me = &map->map[idx_of (map, key)]; |
828 | if (map->use_small_entries) | 917 | if (map->use_small_entries) |
829 | { | 918 | { |
830 | struct SmallMapEntry *sme; | 919 | struct SmallMapEntry *sme; |
831 | struct SmallMapEntry *nxt; | ||
832 | 920 | ||
833 | nxt = me.sme; | 921 | ce->sme = me->sme; |
834 | while (NULL != (sme = nxt)) | 922 | while (NULL != (sme = ce->sme)) |
835 | { | 923 | { |
836 | nxt = sme->next; | 924 | ce->sme = sme->next; |
837 | if (0 != memcmp (key, sme->key, sizeof (struct GNUNET_HashCode))) | 925 | if (0 != memcmp (key, |
926 | sme->key, | ||
927 | sizeof (struct GNUNET_HashCode))) | ||
838 | continue; | 928 | continue; |
839 | if ((it != NULL) && (GNUNET_OK != it (it_cls, key, sme->value))) | 929 | if ( (NULL != it) && |
930 | (GNUNET_OK != it (it_cls, | ||
931 | key, | ||
932 | sme->value))) | ||
933 | { | ||
934 | GNUNET_assert (--map->next_cache_off < NEXT_CACHE_SIZE); | ||
840 | return GNUNET_SYSERR; | 935 | return GNUNET_SYSERR; |
936 | } | ||
841 | count++; | 937 | count++; |
842 | } | 938 | } |
843 | } | 939 | } |
844 | else | 940 | else |
845 | { | 941 | { |
846 | struct BigMapEntry *bme; | 942 | struct BigMapEntry *bme; |
847 | struct BigMapEntry *nxt; | ||
848 | 943 | ||
849 | nxt = me.bme; | 944 | ce->bme = me->bme; |
850 | while (NULL != (bme = nxt)) | 945 | while (NULL != (bme = ce->bme)) |
851 | { | 946 | { |
852 | nxt = bme->next; | 947 | ce->bme = bme->next; |
853 | if (0 != memcmp (key, &bme->key, sizeof (struct GNUNET_HashCode))) | 948 | if (0 != memcmp (key, |
949 | &bme->key, | ||
950 | sizeof (struct GNUNET_HashCode))) | ||
854 | continue; | 951 | continue; |
855 | if ((it != NULL) && (GNUNET_OK != it (it_cls, key, bme->value))) | 952 | if ( (NULL != it) && |
953 | (GNUNET_OK != it (it_cls, | ||
954 | key, | ||
955 | bme->value))) | ||
956 | { | ||
957 | GNUNET_assert (--map->next_cache_off < NEXT_CACHE_SIZE); | ||
856 | return GNUNET_SYSERR; | 958 | return GNUNET_SYSERR; |
959 | } | ||
857 | count++; | 960 | count++; |
858 | } | 961 | } |
859 | } | 962 | } |
963 | GNUNET_assert (--map->next_cache_off < NEXT_CACHE_SIZE); | ||
860 | return count; | 964 | return count; |
861 | } | 965 | } |
862 | 966 | ||
diff --git a/src/util/container_multihashmap32.c b/src/util/container_multihashmap32.c index daf5059b6..016dbabcc 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,27 +241,30 @@ 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)) | ||
246 | return GNUNET_SYSERR; | 268 | return GNUNET_SYSERR; |
247 | } | 269 | } |
248 | count++; | 270 | count++; |
@@ -253,6 +275,23 @@ GNUNET_CONTAINER_multihashmap32_iterate (const struct | |||
253 | 275 | ||
254 | 276 | ||
255 | /** | 277 | /** |
278 | * We are about to free() the @a bme, make sure it is not in | ||
279 | * the list of next values for any iterator in the @a map's next_cache. | ||
280 | * | ||
281 | * @param map the map to check | ||
282 | * @param bme the entry that is about to be free'd | ||
283 | */ | ||
284 | static void | ||
285 | update_next_cache (struct GNUNET_CONTAINER_MultiHashMap32 *map, | ||
286 | const struct MapEntry *me) | ||
287 | { | ||
288 | for (unsigned int i=0;i<map->next_cache_off;i++) | ||
289 | if (map->next_cache[i] == me) | ||
290 | map->next_cache[i] = me->next; | ||
291 | } | ||
292 | |||
293 | |||
294 | /** | ||
256 | * Remove the given key-value pair from the map. Note that if the | 295 | * 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 | 296 | * key-value pair is in the map multiple times, only one of the pairs |
258 | * will be removed. | 297 | * will be removed. |
@@ -260,13 +299,13 @@ GNUNET_CONTAINER_multihashmap32_iterate (const struct | |||
260 | * @param map the map | 299 | * @param map the map |
261 | * @param key key of the key-value pair | 300 | * @param key key of the key-value pair |
262 | * @param value value of the key-value pair | 301 | * @param value value of the key-value pair |
263 | * @return GNUNET_YES on success, GNUNET_NO if the key-value pair | 302 | * @return #GNUNET_YES on success, #GNUNET_NO if the key-value pair |
264 | * is not in the map | 303 | * is not in the map |
265 | */ | 304 | */ |
266 | int | 305 | int |
267 | GNUNET_CONTAINER_multihashmap32_remove (struct GNUNET_CONTAINER_MultiHashMap32 | 306 | GNUNET_CONTAINER_multihashmap32_remove (struct GNUNET_CONTAINER_MultiHashMap32 *map, |
268 | *map, | 307 | uint32_t key, |
269 | uint32_t key, const void *value) | 308 | const void *value) |
270 | { | 309 | { |
271 | struct MapEntry *e; | 310 | struct MapEntry *e; |
272 | struct MapEntry *p; | 311 | struct MapEntry *p; |
@@ -285,6 +324,8 @@ GNUNET_CONTAINER_multihashmap32_remove (struct GNUNET_CONTAINER_MultiHashMap32 | |||
285 | map->map[i] = e->next; | 324 | map->map[i] = e->next; |
286 | else | 325 | else |
287 | p->next = e->next; | 326 | p->next = e->next; |
327 | update_next_cache (map, | ||
328 | e); | ||
288 | GNUNET_free (e); | 329 | GNUNET_free (e); |
289 | map->size--; | 330 | map->size--; |
290 | return GNUNET_YES; | 331 | return GNUNET_YES; |
@@ -305,9 +346,7 @@ GNUNET_CONTAINER_multihashmap32_remove (struct GNUNET_CONTAINER_MultiHashMap32 | |||
305 | * @return number of values removed | 346 | * @return number of values removed |
306 | */ | 347 | */ |
307 | int | 348 | int |
308 | GNUNET_CONTAINER_multihashmap32_remove_all (struct | 349 | GNUNET_CONTAINER_multihashmap32_remove_all (struct GNUNET_CONTAINER_MultiHashMap32 *map, |
309 | GNUNET_CONTAINER_MultiHashMap32 | ||
310 | *map, | ||
311 | uint32_t key) | 350 | uint32_t key) |
312 | { | 351 | { |
313 | struct MapEntry *e; | 352 | struct MapEntry *e; |
@@ -329,6 +368,8 @@ GNUNET_CONTAINER_multihashmap32_remove_all (struct | |||
329 | map->map[i] = e->next; | 368 | map->map[i] = e->next; |
330 | else | 369 | else |
331 | p->next = e->next; | 370 | p->next = e->next; |
371 | update_next_cache (map, | ||
372 | e); | ||
332 | GNUNET_free (e); | 373 | GNUNET_free (e); |
333 | map->size--; | 374 | map->size--; |
334 | if (p == NULL) | 375 | if (p == NULL) |
@@ -353,12 +394,11 @@ GNUNET_CONTAINER_multihashmap32_remove_all (struct | |||
353 | * | 394 | * |
354 | * @param map the map | 395 | * @param map the map |
355 | * @param key the key to test if a value exists for it | 396 | * @param key the key to test if a value exists for it |
356 | * @return GNUNET_YES if such a value exists, | 397 | * @return #GNUNET_YES if such a value exists, |
357 | * GNUNET_NO if not | 398 | * #GNUNET_NO if not |
358 | */ | 399 | */ |
359 | int | 400 | int |
360 | GNUNET_CONTAINER_multihashmap32_contains (const struct | 401 | GNUNET_CONTAINER_multihashmap32_contains (const struct GNUNET_CONTAINER_MultiHashMap32 *map, |
361 | GNUNET_CONTAINER_MultiHashMap32 *map, | ||
362 | uint32_t key) | 402 | uint32_t key) |
363 | { | 403 | { |
364 | struct MapEntry *e; | 404 | struct MapEntry *e; |
@@ -381,13 +421,11 @@ GNUNET_CONTAINER_multihashmap32_contains (const struct | |||
381 | * @param map the map | 421 | * @param map the map |
382 | * @param key the key to test if a value exists for it | 422 | * @param key the key to test if a value exists for it |
383 | * @param value value to test for | 423 | * @param value value to test for |
384 | * @return GNUNET_YES if such a value exists, | 424 | * @return #GNUNET_YES if such a value exists, |
385 | * GNUNET_NO if not | 425 | * #GNUNET_NO if not |
386 | */ | 426 | */ |
387 | int | 427 | int |
388 | GNUNET_CONTAINER_multihashmap32_contains_value (const struct | 428 | GNUNET_CONTAINER_multihashmap32_contains_value (const struct GNUNET_CONTAINER_MultiHashMap32 *map, |
389 | GNUNET_CONTAINER_MultiHashMap32 | ||
390 | *map, | ||
391 | uint32_t key, | 429 | uint32_t key, |
392 | const void *value) | 430 | const void *value) |
393 | { | 431 | { |
@@ -418,17 +456,17 @@ grow (struct GNUNET_CONTAINER_MultiHashMap32 *map) | |||
418 | unsigned int old_len; | 456 | unsigned int old_len; |
419 | unsigned int new_len; | 457 | unsigned int new_len; |
420 | unsigned int idx; | 458 | unsigned int idx; |
421 | unsigned int i; | ||
422 | 459 | ||
423 | map->modification_counter++; | 460 | map->modification_counter++; |
424 | 461 | ||
425 | old_map = map->map; | 462 | old_map = map->map; |
426 | old_len = map->map_length; | 463 | old_len = map->map_length; |
427 | new_len = old_len * 2; | 464 | new_len = old_len * 2; |
428 | new_map = GNUNET_malloc (sizeof (struct MapEntry *) * new_len); | 465 | new_map = GNUNET_new_array (new_len, |
466 | struct MapEntry *); | ||
429 | map->map_length = new_len; | 467 | map->map_length = new_len; |
430 | map->map = new_map; | 468 | map->map = new_map; |
431 | for (i = 0; i < old_len; i++) | 469 | for (unsigned int i = 0; i < old_len; i++) |
432 | { | 470 | { |
433 | while (NULL != (e = old_map[i])) | 471 | while (NULL != (e = old_map[i])) |
434 | { | 472 | { |
@@ -449,9 +487,9 @@ grow (struct GNUNET_CONTAINER_MultiHashMap32 *map) | |||
449 | * @param key key to use | 487 | * @param key key to use |
450 | * @param value value to use | 488 | * @param value value to use |
451 | * @param opt options for put | 489 | * @param opt options for put |
452 | * @return GNUNET_OK on success, | 490 | * @return #GNUNET_OK on success, |
453 | * GNUNET_NO if a value was replaced (with REPLACE) | 491 | * #GNUNET_NO if a value was replaced (with REPLACE) |
454 | * GNUNET_SYSERR if UNIQUE_ONLY was the option and the | 492 | * #GNUNET_SYSERR if UNIQUE_ONLY was the option and the |
455 | * value already exists | 493 | * value already exists |
456 | */ | 494 | */ |
457 | int | 495 | int |
@@ -501,29 +539,34 @@ GNUNET_CONTAINER_multihashmap32_put (struct GNUNET_CONTAINER_MultiHashMap32 | |||
501 | * @param map the map | 539 | * @param map the map |
502 | * @param key key that the entries must correspond to | 540 | * @param key key that the entries must correspond to |
503 | * @param it function to call on each entry | 541 | * @param it function to call on each entry |
504 | * @param it_cls extra argument to it | 542 | * @param it_cls extra argument to @a it |
505 | * @return the number of key value pairs processed, | 543 | * @return the number of key value pairs processed, |
506 | * GNUNET_SYSERR if it aborted iteration | 544 | * GNUNET_SYSERR if it aborted iteration |
507 | */ | 545 | */ |
508 | int | 546 | int |
509 | GNUNET_CONTAINER_multihashmap32_get_multiple (const struct | 547 | GNUNET_CONTAINER_multihashmap32_get_multiple (struct GNUNET_CONTAINER_MultiHashMap32 *map, |
510 | GNUNET_CONTAINER_MultiHashMap32 | 548 | uint32_t key, |
511 | *map, uint32_t key, | 549 | GNUNET_CONTAINER_HashMapIterator32 it, |
512 | GNUNET_CONTAINER_HashMapIterator32 | 550 | void *it_cls) |
513 | it, void *it_cls) | ||
514 | { | 551 | { |
515 | int count; | 552 | int count; |
516 | struct MapEntry *e; | 553 | struct MapEntry *e; |
517 | struct MapEntry *n; | 554 | struct MapEntry **ce; |
518 | 555 | ||
519 | count = 0; | 556 | count = 0; |
520 | n = map->map[idx_of (map, key)]; | 557 | ce = &map->next_cache[map->next_cache_off]; |
521 | while (NULL != (e = n)) | 558 | GNUNET_assert (++map->next_cache_off < NEXT_CACHE_SIZE); |
559 | |||
560 | *ce = map->map[idx_of (map, key)]; | ||
561 | while (NULL != (e = *ce)) | ||
522 | { | 562 | { |
523 | n = e->next; | 563 | *ce = e->next; |
524 | if (key != e->key) | 564 | if (key != e->key) |
525 | continue; | 565 | continue; |
526 | if ((it != NULL) && (GNUNET_OK != it (it_cls, key, e->value))) | 566 | if ( (NULL != it) && |
567 | (GNUNET_OK != it (it_cls, | ||
568 | key, | ||
569 | e->value)) ) | ||
527 | return GNUNET_SYSERR; | 570 | return GNUNET_SYSERR; |
528 | count++; | 571 | count++; |
529 | } | 572 | } |
@@ -541,7 +584,7 @@ GNUNET_CONTAINER_multihashmap32_get_multiple (const struct | |||
541 | * result in skipped or repeated elements. | 584 | * result in skipped or repeated elements. |
542 | * | 585 | * |
543 | * @param map the map to create an iterator for | 586 | * @param map the map to create an iterator for |
544 | * @return an iterator over the given multihashmap 'map' | 587 | * @return an iterator over the given multihashmap @a map |
545 | */ | 588 | */ |
546 | struct GNUNET_CONTAINER_MultiHashMap32Iterator * | 589 | struct GNUNET_CONTAINER_MultiHashMap32Iterator * |
547 | GNUNET_CONTAINER_multihashmap32_iterator_create (const struct GNUNET_CONTAINER_MultiHashMap32 *map) | 590 | GNUNET_CONTAINER_multihashmap32_iterator_create (const struct GNUNET_CONTAINER_MultiHashMap32 *map) |
diff --git a/src/util/container_multipeermap.c b/src/util/container_multipeermap.c index ede2fd8b7..67d6e1684 100644 --- a/src/util/container_multipeermap.c +++ b/src/util/container_multipeermap.c | |||
@@ -27,6 +27,14 @@ | |||
27 | #define LOG(kind,...) GNUNET_log_from (kind, "util-container-multipeermap", __VA_ARGS__) | 27 | #define LOG(kind,...) GNUNET_log_from (kind, "util-container-multipeermap", __VA_ARGS__) |
28 | 28 | ||
29 | /** | 29 | /** |
30 | * Maximum recursion depth for callbacks of | ||
31 | * #GNUNET_CONTAINER_multihashmap_get_multiple() themselve s | ||
32 | * again calling #GNUNET_CONTAINER_multihashmap_get_multiple(). | ||
33 | * Should be totally excessive, but if violated we die. | ||
34 | */ | ||
35 | #define NEXT_CACHE_SIZE 16 | ||
36 | |||
37 | /** | ||
30 | * An entry in the hash map with the full key. | 38 | * An entry in the hash map with the full key. |
31 | */ | 39 | */ |
32 | struct BigMapEntry | 40 | struct BigMapEntry |
@@ -112,8 +120,8 @@ struct GNUNET_CONTAINER_MultiPeerMap | |||
112 | unsigned int map_length; | 120 | unsigned int map_length; |
113 | 121 | ||
114 | /** | 122 | /** |
115 | * GNUNET_NO if the map entries are of type 'struct BigMapEntry', | 123 | * #GNUNET_NO if the map entries are of type 'struct BigMapEntry', |
116 | * GNUNET_YES if the map entries are of type 'struct SmallMapEntry'. | 124 | * #GNUNET_YES if the map entries are of type 'struct SmallMapEntry'. |
117 | */ | 125 | */ |
118 | int use_small_entries; | 126 | int use_small_entries; |
119 | 127 | ||
@@ -122,6 +130,19 @@ struct GNUNET_CONTAINER_MultiPeerMap | |||
122 | * to the map, so that iterators can check if they are still valid. | 130 | * to the map, so that iterators can check if they are still valid. |
123 | */ | 131 | */ |
124 | unsigned int modification_counter; | 132 | unsigned int modification_counter; |
133 | |||
134 | /** | ||
135 | * Map entries indicating iteration positions currently | ||
136 | * in use by #GNUNET_CONTAINER_multihashmap_get_multiple(). | ||
137 | * Only used up to @e next_cache_off. | ||
138 | */ | ||
139 | union MapEntry next_cache[NEXT_CACHE_SIZE]; | ||
140 | |||
141 | /** | ||
142 | * Offset of @e next_cache entries in use, must be smaller | ||
143 | * than #NEXT_CACHE_SIZE. | ||
144 | */ | ||
145 | unsigned int next_cache_off; | ||
125 | }; | 146 | }; |
126 | 147 | ||
127 | 148 | ||
@@ -177,7 +198,8 @@ GNUNET_CONTAINER_multipeermap_create (unsigned int len, | |||
177 | 198 | ||
178 | GNUNET_assert (len > 0); | 199 | GNUNET_assert (len > 0); |
179 | map = GNUNET_new (struct GNUNET_CONTAINER_MultiPeerMap); | 200 | map = GNUNET_new (struct GNUNET_CONTAINER_MultiPeerMap); |
180 | map->map = GNUNET_malloc (len * sizeof (union MapEntry)); | 201 | map->map = GNUNET_new_array (len, |
202 | union MapEntry); | ||
181 | map->map_length = len; | 203 | map->map_length = len; |
182 | map->use_small_entries = do_not_copy_keys; | 204 | map->use_small_entries = do_not_copy_keys; |
183 | return map; | 205 | return map; |
@@ -191,14 +213,13 @@ GNUNET_CONTAINER_multipeermap_create (unsigned int len, | |||
191 | * @param map the map | 213 | * @param map the map |
192 | */ | 214 | */ |
193 | void | 215 | void |
194 | GNUNET_CONTAINER_multipeermap_destroy (struct GNUNET_CONTAINER_MultiPeerMap | 216 | GNUNET_CONTAINER_multipeermap_destroy (struct GNUNET_CONTAINER_MultiPeerMap *map) |
195 | *map) | ||
196 | { | 217 | { |
197 | unsigned int i; | 218 | GNUNET_assert (0 == map->next_cache_off); |
198 | union MapEntry me; | 219 | for (unsigned int i = 0; i < map->map_length; i++) |
199 | |||
200 | for (i = 0; i < map->map_length; i++) | ||
201 | { | 220 | { |
221 | union MapEntry me; | ||
222 | |||
202 | me = map->map[i]; | 223 | me = map->map[i]; |
203 | if (map->use_small_entries) | 224 | if (map->use_small_entries) |
204 | { | 225 | { |
@@ -246,7 +267,9 @@ idx_of (const struct GNUNET_CONTAINER_MultiPeerMap *map, | |||
246 | unsigned int kx; | 267 | unsigned int kx; |
247 | 268 | ||
248 | GNUNET_assert (NULL != map); | 269 | GNUNET_assert (NULL != map); |
249 | GNUNET_memcpy (&kx, key, sizeof (kx)); | 270 | GNUNET_memcpy (&kx, |
271 | key, | ||
272 | sizeof (kx)); | ||
250 | return kx % map->map_length; | 273 | return kx % map->map_length; |
251 | } | 274 | } |
252 | 275 | ||
@@ -258,8 +281,7 @@ idx_of (const struct GNUNET_CONTAINER_MultiPeerMap *map, | |||
258 | * @return the number of key value pairs | 281 | * @return the number of key value pairs |
259 | */ | 282 | */ |
260 | unsigned int | 283 | unsigned int |
261 | GNUNET_CONTAINER_multipeermap_size (const struct GNUNET_CONTAINER_MultiPeerMap | 284 | GNUNET_CONTAINER_multipeermap_size (const struct GNUNET_CONTAINER_MultiPeerMap *map) |
262 | *map) | ||
263 | { | 285 | { |
264 | return map->size; | 286 | return map->size; |
265 | } | 287 | } |
@@ -276,26 +298,26 @@ GNUNET_CONTAINER_multipeermap_size (const struct GNUNET_CONTAINER_MultiPeerMap | |||
276 | * key-value pairs with value NULL | 298 | * key-value pairs with value NULL |
277 | */ | 299 | */ |
278 | void * | 300 | void * |
279 | GNUNET_CONTAINER_multipeermap_get (const struct GNUNET_CONTAINER_MultiPeerMap | 301 | GNUNET_CONTAINER_multipeermap_get (const struct GNUNET_CONTAINER_MultiPeerMap *map, |
280 | *map, const struct GNUNET_PeerIdentity *key) | 302 | const struct GNUNET_PeerIdentity *key) |
281 | { | 303 | { |
282 | union MapEntry me; | 304 | union MapEntry me; |
283 | 305 | ||
284 | me = map->map[idx_of (map, key)]; | 306 | me = map->map[idx_of (map, key)]; |
285 | if (map->use_small_entries) | 307 | if (map->use_small_entries) |
286 | { | 308 | { |
287 | struct SmallMapEntry *sme; | 309 | for (struct SmallMapEntry *sme = me.sme; NULL != sme; sme = sme->next) |
288 | 310 | if (0 == memcmp (key, | |
289 | for (sme = me.sme; NULL != sme; sme = sme->next) | 311 | sme->key, |
290 | if (0 == memcmp (key, sme->key, sizeof (struct GNUNET_PeerIdentity))) | 312 | sizeof (struct GNUNET_PeerIdentity))) |
291 | return sme->value; | 313 | return sme->value; |
292 | } | 314 | } |
293 | else | 315 | else |
294 | { | 316 | { |
295 | struct BigMapEntry *bme; | 317 | for (struct BigMapEntry *bme = me.bme; NULL != bme; bme = bme->next) |
296 | 318 | if (0 == memcmp (key, | |
297 | for (bme = me.bme; NULL != bme; bme = bme->next) | 319 | &bme->key, |
298 | if (0 == memcmp (key, &bme->key, sizeof (struct GNUNET_PeerIdentity))) | 320 | sizeof (struct GNUNET_PeerIdentity))) |
299 | return bme->value; | 321 | return bme->value; |
300 | } | 322 | } |
301 | return NULL; | 323 | return NULL; |
@@ -312,34 +334,39 @@ GNUNET_CONTAINER_multipeermap_get (const struct GNUNET_CONTAINER_MultiPeerMap | |||
312 | * #GNUNET_SYSERR if it aborted iteration | 334 | * #GNUNET_SYSERR if it aborted iteration |
313 | */ | 335 | */ |
314 | int | 336 | int |
315 | GNUNET_CONTAINER_multipeermap_iterate (const struct | 337 | GNUNET_CONTAINER_multipeermap_iterate (struct GNUNET_CONTAINER_MultiPeerMap *map, |
316 | GNUNET_CONTAINER_MultiPeerMap *map, | ||
317 | GNUNET_CONTAINER_PeerMapIterator it, | 338 | GNUNET_CONTAINER_PeerMapIterator it, |
318 | void *it_cls) | 339 | void *it_cls) |
319 | { | 340 | { |
320 | int count; | 341 | int count; |
321 | unsigned int i; | ||
322 | union MapEntry me; | 342 | union MapEntry me; |
343 | union MapEntry *ce; | ||
323 | struct GNUNET_PeerIdentity kc; | 344 | struct GNUNET_PeerIdentity kc; |
324 | 345 | ||
325 | count = 0; | 346 | count = 0; |
326 | GNUNET_assert (NULL != map); | 347 | GNUNET_assert (NULL != map); |
327 | for (i = 0; i < map->map_length; i++) | 348 | ce = &map->next_cache[map->next_cache_off]; |
349 | GNUNET_assert (++map->next_cache_off < NEXT_CACHE_SIZE); | ||
350 | for (unsigned int i = 0; i < map->map_length; i++) | ||
328 | { | 351 | { |
329 | me = map->map[i]; | 352 | me = map->map[i]; |
330 | if (map->use_small_entries) | 353 | if (map->use_small_entries) |
331 | { | 354 | { |
332 | struct SmallMapEntry *sme; | 355 | struct SmallMapEntry *sme; |
333 | struct SmallMapEntry *nxt; | ||
334 | 356 | ||
335 | nxt = me.sme; | 357 | ce->sme = me.sme; |
336 | while (NULL != (sme = nxt)) | 358 | while (NULL != (sme = ce->sme)) |
337 | { | 359 | { |
338 | nxt = sme->next; | 360 | ce->sme = sme->next; |
339 | if (NULL != it) | 361 | if (NULL != it) |
340 | { | 362 | { |
341 | if (GNUNET_OK != it (it_cls, sme->key, sme->value)) | 363 | if (GNUNET_OK != it (it_cls, |
364 | sme->key, | ||
365 | sme->value)) | ||
366 | { | ||
367 | GNUNET_assert (--map->next_cache_off < NEXT_CACHE_SIZE); | ||
342 | return GNUNET_SYSERR; | 368 | return GNUNET_SYSERR; |
369 | } | ||
343 | } | 370 | } |
344 | count++; | 371 | count++; |
345 | } | 372 | } |
@@ -347,27 +374,66 @@ GNUNET_CONTAINER_multipeermap_iterate (const struct | |||
347 | else | 374 | else |
348 | { | 375 | { |
349 | struct BigMapEntry *bme; | 376 | struct BigMapEntry *bme; |
350 | struct BigMapEntry *nxt; | ||
351 | 377 | ||
352 | nxt = me.bme; | 378 | ce->bme = me.bme; |
353 | while (NULL != (bme = nxt)) | 379 | while (NULL != (bme = ce->bme)) |
354 | { | 380 | { |
355 | nxt = bme->next; | 381 | ce->bme = bme->next; |
356 | if (NULL != it) | 382 | if (NULL != it) |
357 | { | 383 | { |
358 | kc = bme->key; | 384 | kc = bme->key; |
359 | if (GNUNET_OK != it (it_cls, &kc, bme->value)) | 385 | if (GNUNET_OK != it (it_cls, |
386 | &kc, | ||
387 | bme->value)) | ||
388 | { | ||
389 | GNUNET_assert (--map->next_cache_off < NEXT_CACHE_SIZE); | ||
360 | return GNUNET_SYSERR; | 390 | return GNUNET_SYSERR; |
391 | } | ||
361 | } | 392 | } |
362 | count++; | 393 | count++; |
363 | } | 394 | } |
364 | } | 395 | } |
365 | } | 396 | } |
397 | GNUNET_assert (--map->next_cache_off < NEXT_CACHE_SIZE); | ||
366 | return count; | 398 | return count; |
367 | } | 399 | } |
368 | 400 | ||
369 | 401 | ||
370 | /** | 402 | /** |
403 | * We are about to free() the @a bme, make sure it is not in | ||
404 | * the list of next values for any iterator in the @a map's next_cache. | ||
405 | * | ||
406 | * @param map the map to check | ||
407 | * @param bme the entry that is about to be free'd | ||
408 | */ | ||
409 | static void | ||
410 | update_next_cache_bme (struct GNUNET_CONTAINER_MultiPeerMap *map, | ||
411 | const struct BigMapEntry *bme) | ||
412 | { | ||
413 | for (unsigned int i=0;i<map->next_cache_off;i++) | ||
414 | if (map->next_cache[i].bme == bme) | ||
415 | map->next_cache[i].bme = bme->next; | ||
416 | } | ||
417 | |||
418 | |||
419 | /** | ||
420 | * We are about to free() the @a sme, make sure it is not in | ||
421 | * the list of next values for any iterator in the @a map's next_cache. | ||
422 | * | ||
423 | * @param map the map to check | ||
424 | * @param sme the entry that is about to be free'd | ||
425 | */ | ||
426 | static void | ||
427 | update_next_cache_sme (struct GNUNET_CONTAINER_MultiPeerMap *map, | ||
428 | const struct SmallMapEntry *sme) | ||
429 | { | ||
430 | for (unsigned int i=0;i<map->next_cache_off;i++) | ||
431 | if (map->next_cache[i].sme == sme) | ||
432 | map->next_cache[i].sme = sme->next; | ||
433 | } | ||
434 | |||
435 | |||
436 | /** | ||
371 | * Remove the given key-value pair from the map. Note that if the | 437 | * Remove the given key-value pair from the map. Note that if the |
372 | * key-value pair is in the map multiple times, only one of the pairs | 438 | * key-value pair is in the map multiple times, only one of the pairs |
373 | * will be removed. | 439 | * will be removed. |
@@ -375,7 +441,7 @@ GNUNET_CONTAINER_multipeermap_iterate (const struct | |||
375 | * @param map the map | 441 | * @param map the map |
376 | * @param key key of the key-value pair | 442 | * @param key key of the key-value pair |
377 | * @param value value of the key-value pair | 443 | * @param value value of the key-value pair |
378 | * @return GNUNET_YES on success, GNUNET_NO if the key-value pair | 444 | * @return #GNUNET_YES on success, #GNUNET_NO if the key-value pair |
379 | * is not in the map | 445 | * is not in the map |
380 | */ | 446 | */ |
381 | int | 447 | int |
@@ -387,16 +453,13 @@ GNUNET_CONTAINER_multipeermap_remove (struct GNUNET_CONTAINER_MultiPeerMap *map, | |||
387 | unsigned int i; | 453 | unsigned int i; |
388 | 454 | ||
389 | map->modification_counter++; | 455 | map->modification_counter++; |
390 | |||
391 | i = idx_of (map, key); | 456 | i = idx_of (map, key); |
392 | me = map->map[i]; | 457 | me = map->map[i]; |
393 | if (map->use_small_entries) | 458 | if (map->use_small_entries) |
394 | { | 459 | { |
395 | struct SmallMapEntry *sme; | 460 | struct SmallMapEntry *p = NULL; |
396 | struct SmallMapEntry *p; | ||
397 | 461 | ||
398 | p = NULL; | 462 | for (struct SmallMapEntry *sme = me.sme; NULL != sme; sme = sme->next) |
399 | for (sme = me.sme; NULL != sme; sme = sme->next) | ||
400 | { | 463 | { |
401 | if ((0 == memcmp (key, sme->key, sizeof (struct GNUNET_PeerIdentity))) && | 464 | if ((0 == memcmp (key, sme->key, sizeof (struct GNUNET_PeerIdentity))) && |
402 | (value == sme->value)) | 465 | (value == sme->value)) |
@@ -405,6 +468,8 @@ GNUNET_CONTAINER_multipeermap_remove (struct GNUNET_CONTAINER_MultiPeerMap *map, | |||
405 | map->map[i].sme = sme->next; | 468 | map->map[i].sme = sme->next; |
406 | else | 469 | else |
407 | p->next = sme->next; | 470 | p->next = sme->next; |
471 | update_next_cache_sme (map, | ||
472 | sme); | ||
408 | GNUNET_free (sme); | 473 | GNUNET_free (sme); |
409 | map->size--; | 474 | map->size--; |
410 | return GNUNET_YES; | 475 | return GNUNET_YES; |
@@ -414,19 +479,21 @@ GNUNET_CONTAINER_multipeermap_remove (struct GNUNET_CONTAINER_MultiPeerMap *map, | |||
414 | } | 479 | } |
415 | else | 480 | else |
416 | { | 481 | { |
417 | struct BigMapEntry *bme; | 482 | struct BigMapEntry *p = NULL; |
418 | struct BigMapEntry *p; | ||
419 | 483 | ||
420 | p = NULL; | 484 | for (struct BigMapEntry *bme = me.bme; NULL != bme; bme = bme->next) |
421 | for (bme = me.bme; NULL != bme; bme = bme->next) | ||
422 | { | 485 | { |
423 | if ((0 == memcmp (key, &bme->key, sizeof (struct GNUNET_PeerIdentity))) && | 486 | if ((0 == memcmp (key, |
487 | &bme->key, | ||
488 | sizeof (struct GNUNET_PeerIdentity))) && | ||
424 | (value == bme->value)) | 489 | (value == bme->value)) |
425 | { | 490 | { |
426 | if (NULL == p) | 491 | if (NULL == p) |
427 | map->map[i].bme = bme->next; | 492 | map->map[i].bme = bme->next; |
428 | else | 493 | else |
429 | p->next = bme->next; | 494 | p->next = bme->next; |
495 | update_next_cache_bme (map, | ||
496 | bme); | ||
430 | GNUNET_free (bme); | 497 | GNUNET_free (bme); |
431 | map->size--; | 498 | map->size--; |
432 | return GNUNET_YES; | 499 | return GNUNET_YES; |
@@ -447,8 +514,8 @@ GNUNET_CONTAINER_multipeermap_remove (struct GNUNET_CONTAINER_MultiPeerMap *map, | |||
447 | * @return number of values removed | 514 | * @return number of values removed |
448 | */ | 515 | */ |
449 | int | 516 | int |
450 | GNUNET_CONTAINER_multipeermap_remove_all (struct GNUNET_CONTAINER_MultiPeerMap | 517 | GNUNET_CONTAINER_multipeermap_remove_all (struct GNUNET_CONTAINER_MultiPeerMap *map, |
451 | *map, const struct GNUNET_PeerIdentity *key) | 518 | const struct GNUNET_PeerIdentity *key) |
452 | { | 519 | { |
453 | union MapEntry me; | 520 | union MapEntry me; |
454 | unsigned int i; | 521 | unsigned int i; |
@@ -468,12 +535,16 @@ GNUNET_CONTAINER_multipeermap_remove_all (struct GNUNET_CONTAINER_MultiPeerMap | |||
468 | sme = me.sme; | 535 | sme = me.sme; |
469 | while (NULL != sme) | 536 | while (NULL != sme) |
470 | { | 537 | { |
471 | if (0 == memcmp (key, sme->key, sizeof (struct GNUNET_PeerIdentity))) | 538 | if (0 == memcmp (key, |
539 | sme->key, | ||
540 | sizeof (struct GNUNET_PeerIdentity))) | ||
472 | { | 541 | { |
473 | if (NULL == p) | 542 | if (NULL == p) |
474 | map->map[i].sme = sme->next; | 543 | map->map[i].sme = sme->next; |
475 | else | 544 | else |
476 | p->next = sme->next; | 545 | p->next = sme->next; |
546 | update_next_cache_sme (map, | ||
547 | sme); | ||
477 | GNUNET_free (sme); | 548 | GNUNET_free (sme); |
478 | map->size--; | 549 | map->size--; |
479 | if (NULL == p) | 550 | if (NULL == p) |
@@ -498,12 +569,16 @@ GNUNET_CONTAINER_multipeermap_remove_all (struct GNUNET_CONTAINER_MultiPeerMap | |||
498 | bme = me.bme; | 569 | bme = me.bme; |
499 | while (NULL != bme) | 570 | while (NULL != bme) |
500 | { | 571 | { |
501 | if (0 == memcmp (key, &bme->key, sizeof (struct GNUNET_PeerIdentity))) | 572 | if (0 == memcmp (key, |
573 | &bme->key, | ||
574 | sizeof (struct GNUNET_PeerIdentity))) | ||
502 | { | 575 | { |
503 | if (NULL == p) | 576 | if (NULL == p) |
504 | map->map[i].bme = bme->next; | 577 | map->map[i].bme = bme->next; |
505 | else | 578 | else |
506 | p->next = bme->next; | 579 | p->next = bme->next; |
580 | update_next_cache_bme (map, | ||
581 | bme); | ||
507 | GNUNET_free (bme); | 582 | GNUNET_free (bme); |
508 | map->size--; | 583 | map->size--; |
509 | if (NULL == p) | 584 | if (NULL == p) |
@@ -529,12 +604,11 @@ GNUNET_CONTAINER_multipeermap_remove_all (struct GNUNET_CONTAINER_MultiPeerMap | |||
529 | * | 604 | * |
530 | * @param map the map | 605 | * @param map the map |
531 | * @param key the key to test if a value exists for it | 606 | * @param key the key to test if a value exists for it |
532 | * @return GNUNET_YES if such a value exists, | 607 | * @return #GNUNET_YES if such a value exists, |
533 | * GNUNET_NO if not | 608 | * #GNUNET_NO if not |
534 | */ | 609 | */ |
535 | int | 610 | int |
536 | GNUNET_CONTAINER_multipeermap_contains (const struct | 611 | GNUNET_CONTAINER_multipeermap_contains (const struct GNUNET_CONTAINER_MultiPeerMap *map, |
537 | GNUNET_CONTAINER_MultiPeerMap *map, | ||
538 | const struct GNUNET_PeerIdentity *key) | 612 | const struct GNUNET_PeerIdentity *key) |
539 | { | 613 | { |
540 | union MapEntry me; | 614 | union MapEntry me; |
@@ -542,17 +616,13 @@ GNUNET_CONTAINER_multipeermap_contains (const struct | |||
542 | me = map->map[idx_of (map, key)]; | 616 | me = map->map[idx_of (map, key)]; |
543 | if (map->use_small_entries) | 617 | if (map->use_small_entries) |
544 | { | 618 | { |
545 | struct SmallMapEntry *sme; | 619 | for (struct SmallMapEntry *sme = me.sme; NULL != sme; sme = sme->next) |
546 | |||
547 | for (sme = me.sme; NULL != sme; sme = sme->next) | ||
548 | if (0 == memcmp (key, sme->key, sizeof (struct GNUNET_PeerIdentity))) | 620 | if (0 == memcmp (key, sme->key, sizeof (struct GNUNET_PeerIdentity))) |
549 | return GNUNET_YES; | 621 | return GNUNET_YES; |
550 | } | 622 | } |
551 | else | 623 | else |
552 | { | 624 | { |
553 | struct BigMapEntry *bme; | 625 | for (struct BigMapEntry *bme = me.bme; NULL != bme; bme = bme->next) |
554 | |||
555 | for (bme = me.bme; NULL != bme; bme = bme->next) | ||
556 | if (0 == memcmp (key, &bme->key, sizeof (struct GNUNET_PeerIdentity))) | 626 | if (0 == memcmp (key, &bme->key, sizeof (struct GNUNET_PeerIdentity))) |
557 | return GNUNET_YES; | 627 | return GNUNET_YES; |
558 | } | 628 | } |
@@ -567,13 +637,12 @@ GNUNET_CONTAINER_multipeermap_contains (const struct | |||
567 | * @param map the map | 637 | * @param map the map |
568 | * @param key the key to test if a value exists for it | 638 | * @param key the key to test if a value exists for it |
569 | * @param value value to test for | 639 | * @param value value to test for |
570 | * @return GNUNET_YES if such a value exists, | 640 | * @return #GNUNET_YES if such a value exists, |
571 | * GNUNET_NO if not | 641 | * #GNUNET_NO if not |
572 | */ | 642 | */ |
573 | int | 643 | int |
574 | GNUNET_CONTAINER_multipeermap_contains_value (const struct | 644 | GNUNET_CONTAINER_multipeermap_contains_value (const struct GNUNET_CONTAINER_MultiPeerMap *map, |
575 | GNUNET_CONTAINER_MultiPeerMap | 645 | const struct GNUNET_PeerIdentity *key, |
576 | *map, const struct GNUNET_PeerIdentity *key, | ||
577 | const void *value) | 646 | const void *value) |
578 | { | 647 | { |
579 | union MapEntry me; | 648 | union MapEntry me; |
@@ -581,19 +650,19 @@ GNUNET_CONTAINER_multipeermap_contains_value (const struct | |||
581 | me = map->map[idx_of (map, key)]; | 650 | me = map->map[idx_of (map, key)]; |
582 | if (map->use_small_entries) | 651 | if (map->use_small_entries) |
583 | { | 652 | { |
584 | struct SmallMapEntry *sme; | 653 | for (struct SmallMapEntry *sme = me.sme; NULL != sme; sme = sme->next) |
585 | 654 | if ( (0 == memcmp (key, | |
586 | for (sme = me.sme; NULL != sme; sme = sme->next) | 655 | sme->key, |
587 | if ( (0 == memcmp (key, sme->key, sizeof (struct GNUNET_PeerIdentity))) && | 656 | sizeof (struct GNUNET_PeerIdentity))) && |
588 | (sme->value == value) ) | 657 | (sme->value == value) ) |
589 | return GNUNET_YES; | 658 | return GNUNET_YES; |
590 | } | 659 | } |
591 | else | 660 | else |
592 | { | 661 | { |
593 | struct BigMapEntry *bme; | 662 | for (struct BigMapEntry *bme = me.bme; NULL != bme; bme = bme->next) |
594 | 663 | if ( (0 == memcmp (key, | |
595 | for (bme = me.bme; NULL != bme; bme = bme->next) | 664 | &bme->key, |
596 | if ( (0 == memcmp (key, &bme->key, sizeof (struct GNUNET_PeerIdentity))) && | 665 | sizeof (struct GNUNET_PeerIdentity))) && |
597 | (bme->value == value) ) | 666 | (bme->value == value) ) |
598 | return GNUNET_YES; | 667 | return GNUNET_YES; |
599 | } | 668 | } |
@@ -621,7 +690,8 @@ grow (struct GNUNET_CONTAINER_MultiPeerMap *map) | |||
621 | old_map = map->map; | 690 | old_map = map->map; |
622 | old_len = map->map_length; | 691 | old_len = map->map_length; |
623 | new_len = old_len * 2; | 692 | new_len = old_len * 2; |
624 | new_map = GNUNET_malloc (sizeof (union MapEntry) * new_len); | 693 | new_map = GNUNET_new_array (new_len, |
694 | union MapEntry); | ||
625 | map->map_length = new_len; | 695 | map->map_length = new_len; |
626 | map->map = new_map; | 696 | map->map = new_map; |
627 | for (i = 0; i < old_len; i++) | 697 | for (i = 0; i < old_len; i++) |
@@ -664,7 +734,7 @@ grow (struct GNUNET_CONTAINER_MultiPeerMap *map) | |||
664 | * @param opt options for put | 734 | * @param opt options for put |
665 | * @return #GNUNET_OK on success, | 735 | * @return #GNUNET_OK on success, |
666 | * #GNUNET_NO if a value was replaced (with REPLACE) | 736 | * #GNUNET_NO if a value was replaced (with REPLACE) |
667 | * #GNUNET_SYSERR if GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY was the option and the | 737 | * #GNUNET_SYSERR if #GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY was the option and the |
668 | * value already exists | 738 | * value already exists |
669 | */ | 739 | */ |
670 | int | 740 | int |
@@ -749,48 +819,66 @@ GNUNET_CONTAINER_multipeermap_put (struct GNUNET_CONTAINER_MultiPeerMap *map, | |||
749 | * #GNUNET_SYSERR if it aborted iteration | 819 | * #GNUNET_SYSERR if it aborted iteration |
750 | */ | 820 | */ |
751 | int | 821 | int |
752 | GNUNET_CONTAINER_multipeermap_get_multiple (const struct GNUNET_CONTAINER_MultiPeerMap *map, | 822 | GNUNET_CONTAINER_multipeermap_get_multiple (struct GNUNET_CONTAINER_MultiPeerMap *map, |
753 | const struct GNUNET_PeerIdentity *key, | 823 | const struct GNUNET_PeerIdentity *key, |
754 | GNUNET_CONTAINER_PeerMapIterator it, | 824 | GNUNET_CONTAINER_PeerMapIterator it, |
755 | void *it_cls) | 825 | void *it_cls) |
756 | { | 826 | { |
757 | int count; | 827 | int count; |
758 | union MapEntry me; | 828 | union MapEntry me; |
759 | 829 | union MapEntry *ce; | |
830 | |||
831 | ce = &map->next_cache[map->next_cache_off]; | ||
832 | GNUNET_assert (++map->next_cache_off < NEXT_CACHE_SIZE); | ||
760 | count = 0; | 833 | count = 0; |
761 | me = map->map[idx_of (map, key)]; | 834 | me = map->map[idx_of (map, key)]; |
762 | if (map->use_small_entries) | 835 | if (map->use_small_entries) |
763 | { | 836 | { |
764 | struct SmallMapEntry *sme; | 837 | struct SmallMapEntry *sme; |
765 | struct SmallMapEntry *nxt; | ||
766 | 838 | ||
767 | nxt = me.sme; | 839 | ce->sme = me.sme; |
768 | while (NULL != (sme = nxt)) | 840 | while (NULL != (sme = ce->sme)) |
769 | { | 841 | { |
770 | nxt = sme->next; | 842 | ce->sme = sme->next; |
771 | if (0 != memcmp (key, sme->key, sizeof (struct GNUNET_PeerIdentity))) | 843 | if (0 != memcmp (key, |
844 | sme->key, | ||
845 | sizeof (struct GNUNET_PeerIdentity))) | ||
772 | continue; | 846 | continue; |
773 | if ((it != NULL) && (GNUNET_OK != it (it_cls, key, sme->value))) | 847 | if ( (NULL != it) && |
848 | (GNUNET_OK != it (it_cls, | ||
849 | key, | ||
850 | sme->value))) | ||
851 | { | ||
852 | GNUNET_assert (--map->next_cache_off < NEXT_CACHE_SIZE); | ||
774 | return GNUNET_SYSERR; | 853 | return GNUNET_SYSERR; |
854 | } | ||
775 | count++; | 855 | count++; |
776 | } | 856 | } |
777 | } | 857 | } |
778 | else | 858 | else |
779 | { | 859 | { |
780 | struct BigMapEntry *bme; | 860 | struct BigMapEntry *bme; |
781 | struct BigMapEntry *nxt; | ||
782 | 861 | ||
783 | nxt = me.bme; | 862 | ce->bme = me.bme; |
784 | while (NULL != (bme = nxt)) | 863 | while (NULL != (bme = ce->bme)) |
785 | { | 864 | { |
786 | nxt = bme->next; | 865 | ce->bme = bme->next; |
787 | if (0 != memcmp (key, &bme->key, sizeof (struct GNUNET_PeerIdentity))) | 866 | if (0 != memcmp (key, |
867 | &bme->key, | ||
868 | sizeof (struct GNUNET_PeerIdentity))) | ||
788 | continue; | 869 | continue; |
789 | if ((it != NULL) && (GNUNET_OK != it (it_cls, key, bme->value))) | 870 | if ( (NULL != it) && |
871 | (GNUNET_OK != it (it_cls, | ||
872 | key, | ||
873 | bme->value))) | ||
874 | { | ||
875 | GNUNET_assert (--map->next_cache_off < NEXT_CACHE_SIZE); | ||
790 | return GNUNET_SYSERR; | 876 | return GNUNET_SYSERR; |
877 | } | ||
791 | count++; | 878 | count++; |
792 | } | 879 | } |
793 | } | 880 | } |
881 | GNUNET_assert (--map->next_cache_off < NEXT_CACHE_SIZE); | ||
794 | return count; | 882 | return count; |
795 | } | 883 | } |
796 | 884 | ||
@@ -812,16 +900,15 @@ GNUNET_CONTAINER_multipeermap_get_random (const struct GNUNET_CONTAINER_MultiPee | |||
812 | void *it_cls) | 900 | void *it_cls) |
813 | { | 901 | { |
814 | unsigned int off; | 902 | unsigned int off; |
815 | unsigned int idx; | ||
816 | union MapEntry me; | 903 | union MapEntry me; |
817 | 904 | ||
818 | if (0 == map->size) | 905 | if (0 == map->size) |
819 | return 0; | 906 | return 0; |
820 | if (NULL == it) | 907 | if (NULL == it) |
821 | return 1; | 908 | return 1; |
822 | off = GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_NONCE, | 909 | off = GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_NONCE, |
823 | map->size); | 910 | map->size); |
824 | for (idx = 0; idx < map->map_length; idx++) | 911 | for (unsigned int idx = 0; idx < map->map_length; idx++) |
825 | { | 912 | { |
826 | me = map->map[idx]; | 913 | me = map->map[idx]; |
827 | if (map->use_small_entries) | 914 | if (map->use_small_entries) |
@@ -856,9 +943,10 @@ GNUNET_CONTAINER_multipeermap_get_random (const struct GNUNET_CONTAINER_MultiPee | |||
856 | if (0 == off) | 943 | if (0 == off) |
857 | { | 944 | { |
858 | if (GNUNET_OK != it (it_cls, | 945 | if (GNUNET_OK != it (it_cls, |
859 | &bme->key, bme->value)) | 946 | &bme->key, |
860 | return GNUNET_SYSERR; | 947 | bme->value)) |
861 | return 1; | 948 | return GNUNET_SYSERR; |
949 | return 1; | ||
862 | } | 950 | } |
863 | off--; | 951 | off--; |
864 | } | 952 | } |
diff --git a/src/util/container_multishortmap.c b/src/util/container_multishortmap.c index f815b6238..050fd21f9 100644 --- a/src/util/container_multishortmap.c +++ b/src/util/container_multishortmap.c | |||
@@ -27,6 +27,15 @@ | |||
27 | #define LOG(kind,...) GNUNET_log_from (kind, "util-container-multishortmap", __VA_ARGS__) | 27 | #define LOG(kind,...) GNUNET_log_from (kind, "util-container-multishortmap", __VA_ARGS__) |
28 | 28 | ||
29 | /** | 29 | /** |
30 | * Maximum recursion depth for callbacks of | ||
31 | * #GNUNET_CONTAINER_multihashmap_get_multiple() themselve s | ||
32 | * again calling #GNUNET_CONTAINER_multihashmap_get_multiple(). | ||
33 | * Should be totally excessive, but if violated we die. | ||
34 | */ | ||
35 | #define NEXT_CACHE_SIZE 16 | ||
36 | |||
37 | |||
38 | /** | ||
30 | * An entry in the hash map with the full key. | 39 | * An entry in the hash map with the full key. |
31 | */ | 40 | */ |
32 | struct BigMapEntry | 41 | struct BigMapEntry |
@@ -112,8 +121,8 @@ struct GNUNET_CONTAINER_MultiShortmap | |||
112 | unsigned int map_length; | 121 | unsigned int map_length; |
113 | 122 | ||
114 | /** | 123 | /** |
115 | * GNUNET_NO if the map entries are of type 'struct BigMapEntry', | 124 | * #GNUNET_NO if the map entries are of type 'struct BigMapEntry', |
116 | * GNUNET_YES if the map entries are of type 'struct SmallMapEntry'. | 125 | * #GNUNET_YES if the map entries are of type 'struct SmallMapEntry'. |
117 | */ | 126 | */ |
118 | int use_small_entries; | 127 | int use_small_entries; |
119 | 128 | ||
@@ -122,6 +131,20 @@ struct GNUNET_CONTAINER_MultiShortmap | |||
122 | * to the map, so that iterators can check if they are still valid. | 131 | * to the map, so that iterators can check if they are still valid. |
123 | */ | 132 | */ |
124 | unsigned int modification_counter; | 133 | unsigned int modification_counter; |
134 | |||
135 | /** | ||
136 | * Map entries indicating iteration positions currently | ||
137 | * in use by #GNUNET_CONTAINER_multihashmap_get_multiple(). | ||
138 | * Only used up to @e next_cache_off. | ||
139 | */ | ||
140 | union MapEntry next_cache[NEXT_CACHE_SIZE]; | ||
141 | |||
142 | /** | ||
143 | * Offset of @e next_cache entries in use, must be smaller | ||
144 | * than #NEXT_CACHE_SIZE. | ||
145 | */ | ||
146 | unsigned int next_cache_off; | ||
147 | |||
125 | }; | 148 | }; |
126 | 149 | ||
127 | 150 | ||
@@ -177,7 +200,8 @@ GNUNET_CONTAINER_multishortmap_create (unsigned int len, | |||
177 | 200 | ||
178 | GNUNET_assert (len > 0); | 201 | GNUNET_assert (len > 0); |
179 | map = GNUNET_new (struct GNUNET_CONTAINER_MultiShortmap); | 202 | map = GNUNET_new (struct GNUNET_CONTAINER_MultiShortmap); |
180 | map->map = GNUNET_malloc (len * sizeof (union MapEntry)); | 203 | map->map = GNUNET_new_array (len, |
204 | union MapEntry); | ||
181 | map->map_length = len; | 205 | map->map_length = len; |
182 | map->use_small_entries = do_not_copy_keys; | 206 | map->use_small_entries = do_not_copy_keys; |
183 | return map; | 207 | return map; |
@@ -191,14 +215,13 @@ GNUNET_CONTAINER_multishortmap_create (unsigned int len, | |||
191 | * @param map the map | 215 | * @param map the map |
192 | */ | 216 | */ |
193 | void | 217 | void |
194 | GNUNET_CONTAINER_multishortmap_destroy (struct GNUNET_CONTAINER_MultiShortmap | 218 | GNUNET_CONTAINER_multishortmap_destroy (struct GNUNET_CONTAINER_MultiShortmap *map) |
195 | *map) | ||
196 | { | 219 | { |
197 | unsigned int i; | 220 | GNUNET_assert (0 == map->next_cache_off); |
198 | union MapEntry me; | 221 | for (unsigned int i = 0; i < map->map_length; i++) |
199 | |||
200 | for (i = 0; i < map->map_length; i++) | ||
201 | { | 222 | { |
223 | union MapEntry me; | ||
224 | |||
202 | me = map->map[i]; | 225 | me = map->map[i]; |
203 | if (map->use_small_entries) | 226 | if (map->use_small_entries) |
204 | { | 227 | { |
@@ -283,18 +306,18 @@ GNUNET_CONTAINER_multishortmap_get (const struct GNUNET_CONTAINER_MultiShortmap | |||
283 | me = map->map[idx_of (map, key)]; | 306 | me = map->map[idx_of (map, key)]; |
284 | if (map->use_small_entries) | 307 | if (map->use_small_entries) |
285 | { | 308 | { |
286 | struct SmallMapEntry *sme; | 309 | for (struct SmallMapEntry *sme = me.sme; NULL != sme; sme = sme->next) |
287 | 310 | if (0 == memcmp (key, | |
288 | for (sme = me.sme; NULL != sme; sme = sme->next) | 311 | sme->key, |
289 | if (0 == memcmp (key, sme->key, sizeof (struct GNUNET_ShortHashCode))) | 312 | sizeof (struct GNUNET_ShortHashCode))) |
290 | return sme->value; | 313 | return sme->value; |
291 | } | 314 | } |
292 | else | 315 | else |
293 | { | 316 | { |
294 | struct BigMapEntry *bme; | 317 | for (struct BigMapEntry *bme = me.bme; NULL != bme; bme = bme->next) |
295 | 318 | if (0 == memcmp (key, | |
296 | for (bme = me.bme; NULL != bme; bme = bme->next) | 319 | &bme->key, |
297 | if (0 == memcmp (key, &bme->key, sizeof (struct GNUNET_ShortHashCode))) | 320 | sizeof (struct GNUNET_ShortHashCode))) |
298 | return bme->value; | 321 | return bme->value; |
299 | } | 322 | } |
300 | return NULL; | 323 | return NULL; |
@@ -311,33 +334,37 @@ GNUNET_CONTAINER_multishortmap_get (const struct GNUNET_CONTAINER_MultiShortmap | |||
311 | * #GNUNET_SYSERR if it aborted iteration | 334 | * #GNUNET_SYSERR if it aborted iteration |
312 | */ | 335 | */ |
313 | int | 336 | int |
314 | GNUNET_CONTAINER_multishortmap_iterate (const struct GNUNET_CONTAINER_MultiShortmap *map, | 337 | GNUNET_CONTAINER_multishortmap_iterate (struct GNUNET_CONTAINER_MultiShortmap *map, |
315 | GNUNET_CONTAINER_ShortmapIterator it, | 338 | GNUNET_CONTAINER_ShortmapIterator it, |
316 | void *it_cls) | 339 | void *it_cls) |
317 | { | 340 | { |
318 | int count; | 341 | int count; |
319 | unsigned int i; | ||
320 | union MapEntry me; | 342 | union MapEntry me; |
343 | union MapEntry *ce; | ||
321 | struct GNUNET_ShortHashCode kc; | 344 | struct GNUNET_ShortHashCode kc; |
322 | 345 | ||
323 | count = 0; | 346 | count = 0; |
324 | GNUNET_assert (NULL != map); | 347 | GNUNET_assert (NULL != map); |
325 | for (i = 0; i < map->map_length; i++) | 348 | ce = &map->next_cache[map->next_cache_off]; |
349 | GNUNET_assert (++map->next_cache_off < NEXT_CACHE_SIZE); | ||
350 | for (unsigned int i = 0; i < map->map_length; i++) | ||
326 | { | 351 | { |
327 | me = map->map[i]; | 352 | me = map->map[i]; |
328 | if (map->use_small_entries) | 353 | if (map->use_small_entries) |
329 | { | 354 | { |
330 | struct SmallMapEntry *sme; | 355 | struct SmallMapEntry *sme; |
331 | struct SmallMapEntry *nxt; | 356 | |
332 | 357 | ce->sme = me.sme; | |
333 | nxt = me.sme; | 358 | while (NULL != (sme = ce->sme)) |
334 | while (NULL != (sme = nxt)) | ||
335 | { | 359 | { |
336 | nxt = sme->next; | 360 | ce->sme = sme->next; |
337 | if (NULL != it) | 361 | if ( (NULL != it) && |
362 | (GNUNET_OK != it (it_cls, | ||
363 | sme->key, | ||
364 | sme->value)) ) | ||
338 | { | 365 | { |
339 | if (GNUNET_OK != it (it_cls, sme->key, sme->value)) | 366 | GNUNET_assert (--map->next_cache_off < NEXT_CACHE_SIZE); |
340 | return GNUNET_SYSERR; | 367 | return GNUNET_SYSERR; |
341 | } | 368 | } |
342 | count++; | 369 | count++; |
343 | } | 370 | } |
@@ -345,27 +372,66 @@ GNUNET_CONTAINER_multishortmap_iterate (const struct GNUNET_CONTAINER_MultiShort | |||
345 | else | 372 | else |
346 | { | 373 | { |
347 | struct BigMapEntry *bme; | 374 | struct BigMapEntry *bme; |
348 | struct BigMapEntry *nxt; | ||
349 | 375 | ||
350 | nxt = me.bme; | 376 | ce->bme = me.bme; |
351 | while (NULL != (bme = nxt)) | 377 | while (NULL != (bme = ce->bme)) |
352 | { | 378 | { |
353 | nxt = bme->next; | 379 | ce->bme = bme->next; |
354 | if (NULL != it) | 380 | if (NULL != it) |
355 | { | 381 | { |
356 | kc = bme->key; | 382 | kc = bme->key; |
357 | if (GNUNET_OK != it (it_cls, &kc, bme->value)) | 383 | if (GNUNET_OK != it (it_cls, |
384 | &kc, | ||
385 | bme->value)) | ||
386 | { | ||
387 | GNUNET_assert (--map->next_cache_off < NEXT_CACHE_SIZE); | ||
358 | return GNUNET_SYSERR; | 388 | return GNUNET_SYSERR; |
389 | } | ||
359 | } | 390 | } |
360 | count++; | 391 | count++; |
361 | } | 392 | } |
362 | } | 393 | } |
363 | } | 394 | } |
395 | GNUNET_assert (--map->next_cache_off < NEXT_CACHE_SIZE); | ||
364 | return count; | 396 | return count; |
365 | } | 397 | } |
366 | 398 | ||
367 | 399 | ||
368 | /** | 400 | /** |
401 | * We are about to free() the @a bme, make sure it is not in | ||
402 | * the list of next values for any iterator in the @a map's next_cache. | ||
403 | * | ||
404 | * @param map the map to check | ||
405 | * @param bme the entry that is about to be free'd | ||
406 | */ | ||
407 | static void | ||
408 | update_next_cache_bme (struct GNUNET_CONTAINER_MultiShortmap *map, | ||
409 | const struct BigMapEntry *bme) | ||
410 | { | ||
411 | for (unsigned int i=0;i<map->next_cache_off;i++) | ||
412 | if (map->next_cache[i].bme == bme) | ||
413 | map->next_cache[i].bme = bme->next; | ||
414 | } | ||
415 | |||
416 | |||
417 | /** | ||
418 | * We are about to free() the @a sme, make sure it is not in | ||
419 | * the list of next values for any iterator in the @a map's next_cache. | ||
420 | * | ||
421 | * @param map the map to check | ||
422 | * @param sme the entry that is about to be free'd | ||
423 | */ | ||
424 | static void | ||
425 | update_next_cache_sme (struct GNUNET_CONTAINER_MultiShortmap *map, | ||
426 | const struct SmallMapEntry *sme) | ||
427 | { | ||
428 | for (unsigned int i=0;i<map->next_cache_off;i++) | ||
429 | if (map->next_cache[i].sme == sme) | ||
430 | map->next_cache[i].sme = sme->next; | ||
431 | } | ||
432 | |||
433 | |||
434 | /** | ||
369 | * Remove the given key-value pair from the map. Note that if the | 435 | * Remove the given key-value pair from the map. Note that if the |
370 | * key-value pair is in the map multiple times, only one of the pairs | 436 | * key-value pair is in the map multiple times, only one of the pairs |
371 | * will be removed. | 437 | * will be removed. |
@@ -385,24 +451,25 @@ GNUNET_CONTAINER_multishortmap_remove (struct GNUNET_CONTAINER_MultiShortmap *ma | |||
385 | unsigned int i; | 451 | unsigned int i; |
386 | 452 | ||
387 | map->modification_counter++; | 453 | map->modification_counter++; |
388 | |||
389 | i = idx_of (map, key); | 454 | i = idx_of (map, key); |
390 | me = map->map[i]; | 455 | me = map->map[i]; |
391 | if (map->use_small_entries) | 456 | if (map->use_small_entries) |
392 | { | 457 | { |
393 | struct SmallMapEntry *sme; | 458 | struct SmallMapEntry *p = NULL; |
394 | struct SmallMapEntry *p; | 459 | |
395 | 460 | for (struct SmallMapEntry *sme = me.sme; NULL != sme; sme = sme->next) | |
396 | p = NULL; | ||
397 | for (sme = me.sme; NULL != sme; sme = sme->next) | ||
398 | { | 461 | { |
399 | if ((0 == memcmp (key, sme->key, sizeof (struct GNUNET_ShortHashCode))) && | 462 | if ((0 == memcmp (key, |
463 | sme->key, | ||
464 | sizeof (struct GNUNET_ShortHashCode))) && | ||
400 | (value == sme->value)) | 465 | (value == sme->value)) |
401 | { | 466 | { |
402 | if (NULL == p) | 467 | if (NULL == p) |
403 | map->map[i].sme = sme->next; | 468 | map->map[i].sme = sme->next; |
404 | else | 469 | else |
405 | p->next = sme->next; | 470 | p->next = sme->next; |
471 | update_next_cache_sme (map, | ||
472 | sme); | ||
406 | GNUNET_free (sme); | 473 | GNUNET_free (sme); |
407 | map->size--; | 474 | map->size--; |
408 | return GNUNET_YES; | 475 | return GNUNET_YES; |
@@ -412,19 +479,21 @@ GNUNET_CONTAINER_multishortmap_remove (struct GNUNET_CONTAINER_MultiShortmap *ma | |||
412 | } | 479 | } |
413 | else | 480 | else |
414 | { | 481 | { |
415 | struct BigMapEntry *bme; | 482 | struct BigMapEntry *p = NULL; |
416 | struct BigMapEntry *p; | 483 | |
417 | 484 | for (struct BigMapEntry *bme = me.bme; NULL != bme; bme = bme->next) | |
418 | p = NULL; | ||
419 | for (bme = me.bme; NULL != bme; bme = bme->next) | ||
420 | { | 485 | { |
421 | if ((0 == memcmp (key, &bme->key, sizeof (struct GNUNET_ShortHashCode))) && | 486 | if ((0 == memcmp (key, |
487 | &bme->key, | ||
488 | sizeof (struct GNUNET_ShortHashCode))) && | ||
422 | (value == bme->value)) | 489 | (value == bme->value)) |
423 | { | 490 | { |
424 | if (NULL == p) | 491 | if (NULL == p) |
425 | map->map[i].bme = bme->next; | 492 | map->map[i].bme = bme->next; |
426 | else | 493 | else |
427 | p->next = bme->next; | 494 | p->next = bme->next; |
495 | update_next_cache_bme (map, | ||
496 | bme); | ||
428 | GNUNET_free (bme); | 497 | GNUNET_free (bme); |
429 | map->size--; | 498 | map->size--; |
430 | return GNUNET_YES; | 499 | return GNUNET_YES; |
@@ -472,6 +541,8 @@ GNUNET_CONTAINER_multishortmap_remove_all (struct GNUNET_CONTAINER_MultiShortmap | |||
472 | map->map[i].sme = sme->next; | 541 | map->map[i].sme = sme->next; |
473 | else | 542 | else |
474 | p->next = sme->next; | 543 | p->next = sme->next; |
544 | update_next_cache_sme (map, | ||
545 | sme); | ||
475 | GNUNET_free (sme); | 546 | GNUNET_free (sme); |
476 | map->size--; | 547 | map->size--; |
477 | if (NULL == p) | 548 | if (NULL == p) |
@@ -502,6 +573,8 @@ GNUNET_CONTAINER_multishortmap_remove_all (struct GNUNET_CONTAINER_MultiShortmap | |||
502 | map->map[i].bme = bme->next; | 573 | map->map[i].bme = bme->next; |
503 | else | 574 | else |
504 | p->next = bme->next; | 575 | p->next = bme->next; |
576 | update_next_cache_bme (map, | ||
577 | bme); | ||
505 | GNUNET_free (bme); | 578 | GNUNET_free (bme); |
506 | map->size--; | 579 | map->size--; |
507 | if (NULL == p) | 580 | if (NULL == p) |
@@ -539,18 +612,18 @@ GNUNET_CONTAINER_multishortmap_contains (const struct GNUNET_CONTAINER_MultiShor | |||
539 | me = map->map[idx_of (map, key)]; | 612 | me = map->map[idx_of (map, key)]; |
540 | if (map->use_small_entries) | 613 | if (map->use_small_entries) |
541 | { | 614 | { |
542 | struct SmallMapEntry *sme; | 615 | for (struct SmallMapEntry *sme = me.sme; NULL != sme; sme = sme->next) |
543 | 616 | if (0 == memcmp (key, | |
544 | for (sme = me.sme; NULL != sme; sme = sme->next) | 617 | sme->key, |
545 | if (0 == memcmp (key, sme->key, sizeof (struct GNUNET_ShortHashCode))) | 618 | sizeof (struct GNUNET_ShortHashCode))) |
546 | return GNUNET_YES; | 619 | return GNUNET_YES; |
547 | } | 620 | } |
548 | else | 621 | else |
549 | { | 622 | { |
550 | struct BigMapEntry *bme; | 623 | for (struct BigMapEntry *bme = me.bme; NULL != bme; bme = bme->next) |
551 | 624 | if (0 == memcmp (key, | |
552 | for (bme = me.bme; NULL != bme; bme = bme->next) | 625 | &bme->key, |
553 | if (0 == memcmp (key, &bme->key, sizeof (struct GNUNET_ShortHashCode))) | 626 | sizeof (struct GNUNET_ShortHashCode))) |
554 | return GNUNET_YES; | 627 | return GNUNET_YES; |
555 | } | 628 | } |
556 | return GNUNET_NO; | 629 | return GNUNET_NO; |
@@ -577,19 +650,19 @@ GNUNET_CONTAINER_multishortmap_contains_value (const struct GNUNET_CONTAINER_Mul | |||
577 | me = map->map[idx_of (map, key)]; | 650 | me = map->map[idx_of (map, key)]; |
578 | if (map->use_small_entries) | 651 | if (map->use_small_entries) |
579 | { | 652 | { |
580 | struct SmallMapEntry *sme; | 653 | for (struct SmallMapEntry *sme = me.sme; NULL != sme; sme = sme->next) |
581 | 654 | if ( (0 == memcmp (key, | |
582 | for (sme = me.sme; NULL != sme; sme = sme->next) | 655 | sme->key, |
583 | if ( (0 == memcmp (key, sme->key, sizeof (struct GNUNET_ShortHashCode))) && | 656 | sizeof (struct GNUNET_ShortHashCode))) && |
584 | (sme->value == value) ) | 657 | (sme->value == value) ) |
585 | return GNUNET_YES; | 658 | return GNUNET_YES; |
586 | } | 659 | } |
587 | else | 660 | else |
588 | { | 661 | { |
589 | struct BigMapEntry *bme; | 662 | for (struct BigMapEntry *bme = me.bme; NULL != bme; bme = bme->next) |
590 | 663 | if ( (0 == memcmp (key, | |
591 | for (bme = me.bme; NULL != bme; bme = bme->next) | 664 | &bme->key, |
592 | if ( (0 == memcmp (key, &bme->key, sizeof (struct GNUNET_ShortHashCode))) && | 665 | sizeof (struct GNUNET_ShortHashCode))) && |
593 | (bme->value == value) ) | 666 | (bme->value == value) ) |
594 | return GNUNET_YES; | 667 | return GNUNET_YES; |
595 | } | 668 | } |
@@ -610,17 +683,17 @@ grow (struct GNUNET_CONTAINER_MultiShortmap *map) | |||
610 | unsigned int old_len; | 683 | unsigned int old_len; |
611 | unsigned int new_len; | 684 | unsigned int new_len; |
612 | unsigned int idx; | 685 | unsigned int idx; |
613 | unsigned int i; | ||
614 | 686 | ||
615 | map->modification_counter++; | 687 | map->modification_counter++; |
616 | 688 | ||
617 | old_map = map->map; | 689 | old_map = map->map; |
618 | old_len = map->map_length; | 690 | old_len = map->map_length; |
619 | new_len = old_len * 2; | 691 | new_len = old_len * 2; |
620 | new_map = GNUNET_malloc (sizeof (union MapEntry) * new_len); | 692 | new_map = GNUNET_new_array (new_len, |
693 | union MapEntry); | ||
621 | map->map_length = new_len; | 694 | map->map_length = new_len; |
622 | map->map = new_map; | 695 | map->map = new_map; |
623 | for (i = 0; i < old_len; i++) | 696 | for (unsigned int i = 0; i < old_len; i++) |
624 | { | 697 | { |
625 | if (map->use_small_entries) | 698 | if (map->use_small_entries) |
626 | { | 699 | { |
@@ -660,7 +733,7 @@ grow (struct GNUNET_CONTAINER_MultiShortmap *map) | |||
660 | * @param opt options for put | 733 | * @param opt options for put |
661 | * @return #GNUNET_OK on success, | 734 | * @return #GNUNET_OK on success, |
662 | * #GNUNET_NO if a value was replaced (with REPLACE) | 735 | * #GNUNET_NO if a value was replaced (with REPLACE) |
663 | * #GNUNET_SYSERR if GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY was the option and the | 736 | * #GNUNET_SYSERR if #GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY was the option and the |
664 | * value already exists | 737 | * value already exists |
665 | */ | 738 | */ |
666 | int | 739 | int |
@@ -679,10 +752,10 @@ GNUNET_CONTAINER_multishortmap_put (struct GNUNET_CONTAINER_MultiShortmap *map, | |||
679 | me = map->map[i]; | 752 | me = map->map[i]; |
680 | if (map->use_small_entries) | 753 | if (map->use_small_entries) |
681 | { | 754 | { |
682 | struct SmallMapEntry *sme; | 755 | for (struct SmallMapEntry *sme = me.sme; NULL != sme; sme = sme->next) |
683 | 756 | if (0 == memcmp (key, | |
684 | for (sme = me.sme; NULL != sme; sme = sme->next) | 757 | sme->key, |
685 | if (0 == memcmp (key, sme->key, sizeof (struct GNUNET_ShortHashCode))) | 758 | sizeof (struct GNUNET_ShortHashCode))) |
686 | { | 759 | { |
687 | if (opt == GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY) | 760 | if (opt == GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY) |
688 | return GNUNET_SYSERR; | 761 | return GNUNET_SYSERR; |
@@ -692,10 +765,10 @@ GNUNET_CONTAINER_multishortmap_put (struct GNUNET_CONTAINER_MultiShortmap *map, | |||
692 | } | 765 | } |
693 | else | 766 | else |
694 | { | 767 | { |
695 | struct BigMapEntry *bme; | 768 | for (struct BigMapEntry *bme = me.bme; NULL != bme; bme = bme->next) |
696 | 769 | if (0 == memcmp (key, | |
697 | for (bme = me.bme; NULL != bme; bme = bme->next) | 770 | &bme->key, |
698 | if (0 == memcmp (key, &bme->key, sizeof (struct GNUNET_ShortHashCode))) | 771 | sizeof (struct GNUNET_ShortHashCode))) |
699 | { | 772 | { |
700 | if (opt == GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY) | 773 | if (opt == GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY) |
701 | return GNUNET_SYSERR; | 774 | return GNUNET_SYSERR; |
@@ -745,48 +818,66 @@ GNUNET_CONTAINER_multishortmap_put (struct GNUNET_CONTAINER_MultiShortmap *map, | |||
745 | * #GNUNET_SYSERR if it aborted iteration | 818 | * #GNUNET_SYSERR if it aborted iteration |
746 | */ | 819 | */ |
747 | int | 820 | int |
748 | GNUNET_CONTAINER_multishortmap_get_multiple (const struct GNUNET_CONTAINER_MultiShortmap *map, | 821 | GNUNET_CONTAINER_multishortmap_get_multiple (struct GNUNET_CONTAINER_MultiShortmap *map, |
749 | const struct GNUNET_ShortHashCode *key, | 822 | const struct GNUNET_ShortHashCode *key, |
750 | GNUNET_CONTAINER_ShortmapIterator it, | 823 | GNUNET_CONTAINER_ShortmapIterator it, |
751 | void *it_cls) | 824 | void *it_cls) |
752 | { | 825 | { |
753 | int count; | 826 | int count; |
754 | union MapEntry me; | 827 | union MapEntry me; |
828 | union MapEntry *ce; | ||
755 | 829 | ||
830 | ce = &map->next_cache[map->next_cache_off]; | ||
831 | GNUNET_assert (++map->next_cache_off < NEXT_CACHE_SIZE); | ||
756 | count = 0; | 832 | count = 0; |
757 | me = map->map[idx_of (map, key)]; | 833 | me = map->map[idx_of (map, key)]; |
758 | if (map->use_small_entries) | 834 | if (map->use_small_entries) |
759 | { | 835 | { |
760 | struct SmallMapEntry *sme; | 836 | struct SmallMapEntry *sme; |
761 | struct SmallMapEntry *nxt; | ||
762 | 837 | ||
763 | nxt = me.sme; | 838 | ce->sme = me.sme; |
764 | while (NULL != (sme = nxt)) | 839 | while (NULL != (sme = ce->sme)) |
765 | { | 840 | { |
766 | nxt = sme->next; | 841 | ce->sme = sme->next; |
767 | if (0 != memcmp (key, sme->key, sizeof (struct GNUNET_ShortHashCode))) | 842 | if (0 != memcmp (key, |
843 | sme->key, | ||
844 | sizeof (struct GNUNET_ShortHashCode))) | ||
768 | continue; | 845 | continue; |
769 | if ((it != NULL) && (GNUNET_OK != it (it_cls, key, sme->value))) | 846 | if ( (NULL != it) && |
847 | (GNUNET_OK != it (it_cls, | ||
848 | key, | ||
849 | sme->value)) ) | ||
850 | { | ||
851 | GNUNET_assert (--map->next_cache_off < NEXT_CACHE_SIZE); | ||
770 | return GNUNET_SYSERR; | 852 | return GNUNET_SYSERR; |
853 | } | ||
771 | count++; | 854 | count++; |
772 | } | 855 | } |
773 | } | 856 | } |
774 | else | 857 | else |
775 | { | 858 | { |
776 | struct BigMapEntry *bme; | 859 | struct BigMapEntry *bme; |
777 | struct BigMapEntry *nxt; | ||
778 | 860 | ||
779 | nxt = me.bme; | 861 | ce->bme = me.bme; |
780 | while (NULL != (bme = nxt)) | 862 | while (NULL != (bme = ce->bme)) |
781 | { | 863 | { |
782 | nxt = bme->next; | 864 | ce->bme = bme->next; |
783 | if (0 != memcmp (key, &bme->key, sizeof (struct GNUNET_ShortHashCode))) | 865 | if (0 != memcmp (key, |
866 | &bme->key, | ||
867 | sizeof (struct GNUNET_ShortHashCode))) | ||
784 | continue; | 868 | continue; |
785 | if ((it != NULL) && (GNUNET_OK != it (it_cls, key, bme->value))) | 869 | if ( (NULL != it) && |
870 | (GNUNET_OK != it (it_cls, | ||
871 | key, | ||
872 | bme->value)) ) | ||
873 | { | ||
874 | GNUNET_assert (--map->next_cache_off < NEXT_CACHE_SIZE); | ||
786 | return GNUNET_SYSERR; | 875 | return GNUNET_SYSERR; |
876 | } | ||
787 | count++; | 877 | count++; |
788 | } | 878 | } |
789 | } | 879 | } |
880 | GNUNET_assert (--map->next_cache_off < NEXT_CACHE_SIZE); | ||
790 | return count; | 881 | return count; |
791 | } | 882 | } |
792 | 883 | ||
@@ -808,7 +899,6 @@ GNUNET_CONTAINER_multishortmap_get_random (const struct GNUNET_CONTAINER_MultiSh | |||
808 | void *it_cls) | 899 | void *it_cls) |
809 | { | 900 | { |
810 | unsigned int off; | 901 | unsigned int off; |
811 | unsigned int idx; | ||
812 | union MapEntry me; | 902 | union MapEntry me; |
813 | 903 | ||
814 | if (0 == map->size) | 904 | if (0 == map->size) |
@@ -817,18 +907,13 @@ GNUNET_CONTAINER_multishortmap_get_random (const struct GNUNET_CONTAINER_MultiSh | |||
817 | return 1; | 907 | return 1; |
818 | off = GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_NONCE, | 908 | off = GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_NONCE, |
819 | map->size); | 909 | map->size); |
820 | for (idx = 0; idx < map->map_length; idx++) | 910 | for (unsigned int idx = 0; idx < map->map_length; idx++) |
821 | { | 911 | { |
822 | me = map->map[idx]; | 912 | me = map->map[idx]; |
823 | if (map->use_small_entries) | 913 | if (map->use_small_entries) |
824 | { | 914 | { |
825 | struct SmallMapEntry *sme; | 915 | for (struct SmallMapEntry *sme = me.sme; NULL != sme; sme = sme->next) |
826 | struct SmallMapEntry *nxt; | ||
827 | |||
828 | nxt = me.sme; | ||
829 | while (NULL != (sme = nxt)) | ||
830 | { | 916 | { |
831 | nxt = sme->next; | ||
832 | if (0 == off) | 917 | if (0 == off) |
833 | { | 918 | { |
834 | if (GNUNET_OK != it (it_cls, | 919 | if (GNUNET_OK != it (it_cls, |
@@ -842,13 +927,8 @@ GNUNET_CONTAINER_multishortmap_get_random (const struct GNUNET_CONTAINER_MultiSh | |||
842 | } | 927 | } |
843 | else | 928 | else |
844 | { | 929 | { |
845 | struct BigMapEntry *bme; | 930 | for (struct BigMapEntry *bme = me.bme; NULL != bme; bme = bme->next) |
846 | struct BigMapEntry *nxt; | ||
847 | |||
848 | nxt = me.bme; | ||
849 | while (NULL != (bme = nxt)) | ||
850 | { | 931 | { |
851 | nxt = bme->next; | ||
852 | if (0 == off) | 932 | if (0 == off) |
853 | { | 933 | { |
854 | if (GNUNET_OK != it (it_cls, | 934 | if (GNUNET_OK != it (it_cls, |