diff options
Diffstat (limited to 'src/util/container_multihashmap.c')
-rw-r--r-- | src/util/container_multihashmap.c | 210 |
1 files changed, 157 insertions, 53 deletions
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 | ||