aboutsummaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
Diffstat (limited to 'src')
-rw-r--r--src/include/gnunet_container_lib.h17
-rw-r--r--src/util/container_multihashmap.c210
-rw-r--r--src/util/container_multihashmap32.c159
-rw-r--r--src/util/container_multipeermap.c282
-rw-r--r--src/util/container_multishortmap.c286
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 */
930int 930int
931GNUNET_CONTAINER_multihashmap_iterate (const struct GNUNET_CONTAINER_MultiHashMap *map, 931GNUNET_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 */
995int 995int
996GNUNET_CONTAINER_multihashmap_get_multiple (const struct GNUNET_CONTAINER_MultiHashMap *map, 996GNUNET_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 */
1196int 1196int
1197GNUNET_CONTAINER_multipeermap_iterate (const struct GNUNET_CONTAINER_MultiPeerMap *map, 1197GNUNET_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 */
1262int 1262int
1263GNUNET_CONTAINER_multipeermap_get_multiple (const struct GNUNET_CONTAINER_MultiPeerMap *map, 1263GNUNET_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 */
1463int 1463int
1464GNUNET_CONTAINER_multishortmap_iterate (const struct GNUNET_CONTAINER_MultiShortmap *map, 1464GNUNET_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 */
1531int 1531int
1532GNUNET_CONTAINER_multishortmap_get_multiple (const struct GNUNET_CONTAINER_MultiShortmap *map, 1532GNUNET_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 */
1650int 1650int
1651GNUNET_CONTAINER_multihashmap32_iterate (const struct 1651GNUNET_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 */
1752int 1751int
1753GNUNET_CONTAINER_multihashmap32_get_multiple (const struct GNUNET_CONTAINER_MultiHashMap32 *map, 1752GNUNET_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 */
32struct BigMapEntry 41struct 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
132struct GNUNET_CONTAINER_MultiHashMapIterator 154struct 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 */
215void 237void
216GNUNET_CONTAINER_multihashmap_destroy (struct GNUNET_CONTAINER_MultiHashMap 238GNUNET_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 */
331int 357int
332GNUNET_CONTAINER_multihashmap_iterate (const struct 358GNUNET_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 */
430static void
431update_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 */
447static void
448update_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 */
633int 717int
634GNUNET_CONTAINER_multihashmap_contains_value (const struct 718GNUNET_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 */
816int 903int
817GNUNET_CONTAINER_multihashmap_get_multiple (const struct 904GNUNET_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
87struct GNUNET_CONTAINER_MultiHashMap32Iterator 109struct 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 */
137void 160void
138GNUNET_CONTAINER_multihashmap32_destroy (struct GNUNET_CONTAINER_MultiHashMap32 161GNUNET_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
165idx_of (const struct GNUNET_CONTAINER_MultiHashMap32 *m, 186idx_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 */
179unsigned int 200unsigned int
180GNUNET_CONTAINER_multihashmap32_size (const struct 201GNUNET_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 */
197void * 217void *
198GNUNET_CONTAINER_multihashmap32_get (const struct 218GNUNET_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 */
224int 243int
225GNUNET_CONTAINER_multihashmap32_iterate (const struct 244GNUNET_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 */
284static void
285update_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 */
266int 305int
267GNUNET_CONTAINER_multihashmap32_remove (struct GNUNET_CONTAINER_MultiHashMap32 306GNUNET_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 */
307int 348int
308GNUNET_CONTAINER_multihashmap32_remove_all (struct 349GNUNET_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 */
359int 400int
360GNUNET_CONTAINER_multihashmap32_contains (const struct 401GNUNET_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 */
387int 427int
388GNUNET_CONTAINER_multihashmap32_contains_value (const struct 428GNUNET_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 */
457int 495int
@@ -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 */
508int 546int
509GNUNET_CONTAINER_multihashmap32_get_multiple (const struct 547GNUNET_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 */
546struct GNUNET_CONTAINER_MultiHashMap32Iterator * 589struct GNUNET_CONTAINER_MultiHashMap32Iterator *
547GNUNET_CONTAINER_multihashmap32_iterator_create (const struct GNUNET_CONTAINER_MultiHashMap32 *map) 590GNUNET_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 */
32struct BigMapEntry 40struct 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 */
193void 215void
194GNUNET_CONTAINER_multipeermap_destroy (struct GNUNET_CONTAINER_MultiPeerMap 216GNUNET_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 */
260unsigned int 283unsigned int
261GNUNET_CONTAINER_multipeermap_size (const struct GNUNET_CONTAINER_MultiPeerMap 284GNUNET_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 */
278void * 300void *
279GNUNET_CONTAINER_multipeermap_get (const struct GNUNET_CONTAINER_MultiPeerMap 301GNUNET_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 */
314int 336int
315GNUNET_CONTAINER_multipeermap_iterate (const struct 337GNUNET_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 */
409static void
410update_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 */
426static void
427update_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 */
381int 447int
@@ -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 */
449int 516int
450GNUNET_CONTAINER_multipeermap_remove_all (struct GNUNET_CONTAINER_MultiPeerMap 517GNUNET_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 */
535int 610int
536GNUNET_CONTAINER_multipeermap_contains (const struct 611GNUNET_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 */
573int 643int
574GNUNET_CONTAINER_multipeermap_contains_value (const struct 644GNUNET_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 */
670int 740int
@@ -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 */
751int 821int
752GNUNET_CONTAINER_multipeermap_get_multiple (const struct GNUNET_CONTAINER_MultiPeerMap *map, 822GNUNET_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 */
32struct BigMapEntry 41struct 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 */
193void 217void
194GNUNET_CONTAINER_multishortmap_destroy (struct GNUNET_CONTAINER_MultiShortmap 218GNUNET_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 */
313int 336int
314GNUNET_CONTAINER_multishortmap_iterate (const struct GNUNET_CONTAINER_MultiShortmap *map, 337GNUNET_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 */
407static void
408update_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 */
424static void
425update_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 */
666int 739int
@@ -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 */
747int 820int
748GNUNET_CONTAINER_multishortmap_get_multiple (const struct GNUNET_CONTAINER_MultiShortmap *map, 821GNUNET_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,
generated by cgit v1.2.3 (git 2.39.1) at 2024-04-24 02:55:24 +0000