summaryrefslogtreecommitdiff
path: root/src/util/container_multiuuidmap.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/util/container_multiuuidmap.c')
-rw-r--r--src/util/container_multiuuidmap.c791
1 files changed, 398 insertions, 393 deletions
diff --git a/src/util/container_multiuuidmap.c b/src/util/container_multiuuidmap.c
index 78ed7f2b7..5e896aec2 100644
--- a/src/util/container_multiuuidmap.c
+++ b/src/util/container_multiuuidmap.c
@@ -27,7 +27,7 @@
27#include "gnunet_util_lib.h" 27#include "gnunet_util_lib.h"
28 28
29#define LOG(kind, ...) \ 29#define LOG(kind, ...) \
30 GNUNET_log_from(kind, "util-container-multiuuidmap", __VA_ARGS__) 30 GNUNET_log_from (kind, "util-container-multiuuidmap", __VA_ARGS__)
31 31
32/** 32/**
33 * Maximum recursion depth for callbacks of 33 * Maximum recursion depth for callbacks of
@@ -41,7 +41,8 @@
41/** 41/**
42 * An entry in the hash map with the full key. 42 * An entry in the hash map with the full key.
43 */ 43 */
44struct BigMapEntry { 44struct BigMapEntry
45{
45 /** 46 /**
46 * Value of the entry. 47 * Value of the entry.
47 */ 48 */
@@ -62,7 +63,8 @@ struct BigMapEntry {
62/** 63/**
63 * An entry in the hash map with just a pointer to the key. 64 * An entry in the hash map with just a pointer to the key.
64 */ 65 */
65struct SmallMapEntry { 66struct SmallMapEntry
67{
66 /** 68 /**
67 * Value of the entry. 69 * Value of the entry.
68 */ 70 */
@@ -83,7 +85,8 @@ struct SmallMapEntry {
83/** 85/**
84 * Entry in the map. 86 * Entry in the map.
85 */ 87 */
86union MapEntry { 88union MapEntry
89{
87 /** 90 /**
88 * Variant used if map entries only contain a pointer to the key. 91 * Variant used if map entries only contain a pointer to the key.
89 */ 92 */
@@ -99,7 +102,8 @@ union MapEntry {
99/** 102/**
100 * Internal representation of the hash map. 103 * Internal representation of the hash map.
101 */ 104 */
102struct GNUNET_CONTAINER_MultiUuidmap { 105struct GNUNET_CONTAINER_MultiUuidmap
106{
103 /** 107 /**
104 * All of our buckets. 108 * All of our buckets.
105 */ 109 */
@@ -146,7 +150,8 @@ struct GNUNET_CONTAINER_MultiUuidmap {
146 * Cursor into a multiuuidmap. 150 * Cursor into a multiuuidmap.
147 * Allows to enumerate elements asynchronously. 151 * Allows to enumerate elements asynchronously.
148 */ 152 */
149struct GNUNET_CONTAINER_MultiUuidmapIterator { 153struct GNUNET_CONTAINER_MultiUuidmapIterator
154{
150 /** 155 /**
151 * Position in the bucket 'idx' 156 * Position in the bucket 'idx'
152 */ 157 */
@@ -186,18 +191,18 @@ struct GNUNET_CONTAINER_MultiUuidmapIterator {
186 * @return NULL on error 191 * @return NULL on error
187 */ 192 */
188struct GNUNET_CONTAINER_MultiUuidmap * 193struct GNUNET_CONTAINER_MultiUuidmap *
189GNUNET_CONTAINER_multiuuidmap_create(unsigned int len, int do_not_copy_keys) 194GNUNET_CONTAINER_multiuuidmap_create (unsigned int len, int do_not_copy_keys)
190{ 195{
191 struct GNUNET_CONTAINER_MultiUuidmap *map; 196 struct GNUNET_CONTAINER_MultiUuidmap *map;
192 197
193 GNUNET_assert(len > 0); 198 GNUNET_assert (len > 0);
194 map = GNUNET_new(struct GNUNET_CONTAINER_MultiUuidmap); 199 map = GNUNET_new (struct GNUNET_CONTAINER_MultiUuidmap);
195 map->map = GNUNET_malloc_large(len * sizeof(union MapEntry)); 200 map->map = GNUNET_malloc_large (len * sizeof(union MapEntry));
196 if (NULL == map->map) 201 if (NULL == map->map)
197 { 202 {
198 GNUNET_free(map); 203 GNUNET_free (map);
199 return NULL; 204 return NULL;
200 } 205 }
201 map->map_length = len; 206 map->map_length = len;
202 map->use_small_entries = do_not_copy_keys; 207 map->use_small_entries = do_not_copy_keys;
203 return map; 208 return map;
@@ -211,44 +216,44 @@ GNUNET_CONTAINER_multiuuidmap_create(unsigned int len, int do_not_copy_keys)
211 * @param map the map 216 * @param map the map
212 */ 217 */
213void 218void
214GNUNET_CONTAINER_multiuuidmap_destroy( 219GNUNET_CONTAINER_multiuuidmap_destroy (
215 struct GNUNET_CONTAINER_MultiUuidmap *map) 220 struct GNUNET_CONTAINER_MultiUuidmap *map)
216{ 221{
217 GNUNET_assert(0 == map->next_cache_off); 222 GNUNET_assert (0 == map->next_cache_off);
218 for (unsigned int i = 0; i < map->map_length; i++) 223 for (unsigned int i = 0; i < map->map_length; i++)
219 { 224 {
220 union MapEntry me; 225 union MapEntry me;
221 226
222 me = map->map[i]; 227 me = map->map[i];
223 if (map->use_small_entries) 228 if (map->use_small_entries)
224 { 229 {
225 struct SmallMapEntry *sme; 230 struct SmallMapEntry *sme;
226 struct SmallMapEntry *nxt; 231 struct SmallMapEntry *nxt;
227 232
228 nxt = me.sme; 233 nxt = me.sme;
229 while (NULL != (sme = nxt)) 234 while (NULL != (sme = nxt))
230 { 235 {
231 nxt = sme->next; 236 nxt = sme->next;
232 GNUNET_free(sme); 237 GNUNET_free (sme);
233 } 238 }
234 me.sme = NULL; 239 me.sme = NULL;
235 }
236 else
237 {
238 struct BigMapEntry *bme;
239 struct BigMapEntry *nxt;
240
241 nxt = me.bme;
242 while (NULL != (bme = nxt))
243 {
244 nxt = bme->next;
245 GNUNET_free(bme);
246 }
247 me.bme = NULL;
248 }
249 } 240 }
250 GNUNET_free(map->map); 241 else
251 GNUNET_free(map); 242 {
243 struct BigMapEntry *bme;
244 struct BigMapEntry *nxt;
245
246 nxt = me.bme;
247 while (NULL != (bme = nxt))
248 {
249 nxt = bme->next;
250 GNUNET_free (bme);
251 }
252 me.bme = NULL;
253 }
254 }
255 GNUNET_free (map->map);
256 GNUNET_free (map);
252} 257}
253 258
254 259
@@ -260,13 +265,13 @@ GNUNET_CONTAINER_multiuuidmap_destroy(
260 * @return offset into the "map" array of "map" 265 * @return offset into the "map" array of "map"
261 */ 266 */
262static unsigned int 267static unsigned int
263idx_of(const struct GNUNET_CONTAINER_MultiUuidmap *map, 268idx_of (const struct GNUNET_CONTAINER_MultiUuidmap *map,
264 const struct GNUNET_Uuid *key) 269 const struct GNUNET_Uuid *key)
265{ 270{
266 unsigned int kx; 271 unsigned int kx;
267 272
268 GNUNET_assert(NULL != map); 273 GNUNET_assert (NULL != map);
269 GNUNET_memcpy(&kx, key, sizeof(kx)); 274 GNUNET_memcpy (&kx, key, sizeof(kx));
270 return kx % map->map_length; 275 return kx % map->map_length;
271} 276}
272 277
@@ -278,7 +283,7 @@ idx_of(const struct GNUNET_CONTAINER_MultiUuidmap *map,
278 * @return the number of key value pairs 283 * @return the number of key value pairs
279 */ 284 */
280unsigned int 285unsigned int
281GNUNET_CONTAINER_multiuuidmap_size( 286GNUNET_CONTAINER_multiuuidmap_size (
282 const struct GNUNET_CONTAINER_MultiUuidmap *map) 287 const struct GNUNET_CONTAINER_MultiUuidmap *map)
283{ 288{
284 return map->size; 289 return map->size;
@@ -296,25 +301,25 @@ GNUNET_CONTAINER_multiuuidmap_size(
296 * key-value pairs with value NULL 301 * key-value pairs with value NULL
297 */ 302 */
298void * 303void *
299GNUNET_CONTAINER_multiuuidmap_get( 304GNUNET_CONTAINER_multiuuidmap_get (
300 const struct GNUNET_CONTAINER_MultiUuidmap *map, 305 const struct GNUNET_CONTAINER_MultiUuidmap *map,
301 const struct GNUNET_Uuid *key) 306 const struct GNUNET_Uuid *key)
302{ 307{
303 union MapEntry me; 308 union MapEntry me;
304 309
305 me = map->map[idx_of(map, key)]; 310 me = map->map[idx_of (map, key)];
306 if (map->use_small_entries) 311 if (map->use_small_entries)
307 { 312 {
308 for (struct SmallMapEntry *sme = me.sme; NULL != sme; sme = sme->next) 313 for (struct SmallMapEntry *sme = me.sme; NULL != sme; sme = sme->next)
309 if (0 == GNUNET_memcmp(key, sme->key)) 314 if (0 == GNUNET_memcmp (key, sme->key))
310 return sme->value; 315 return sme->value;
311 } 316 }
312 else 317 else
313 { 318 {
314 for (struct BigMapEntry *bme = me.bme; NULL != bme; bme = bme->next) 319 for (struct BigMapEntry *bme = me.bme; NULL != bme; bme = bme->next)
315 if (0 == GNUNET_memcmp(key, &bme->key)) 320 if (0 == GNUNET_memcmp (key, &bme->key))
316 return bme->value; 321 return bme->value;
317 } 322 }
318 return NULL; 323 return NULL;
319} 324}
320 325
@@ -329,7 +334,7 @@ GNUNET_CONTAINER_multiuuidmap_get(
329 * #GNUNET_SYSERR if it aborted iteration 334 * #GNUNET_SYSERR if it aborted iteration
330 */ 335 */
331int 336int
332GNUNET_CONTAINER_multiuuidmap_iterate( 337GNUNET_CONTAINER_multiuuidmap_iterate (
333 struct GNUNET_CONTAINER_MultiUuidmap *map, 338 struct GNUNET_CONTAINER_MultiUuidmap *map,
334 GNUNET_CONTAINER_MultiUuidmapIteratorCallback it, 339 GNUNET_CONTAINER_MultiUuidmapIteratorCallback it,
335 void *it_cls) 340 void *it_cls)
@@ -340,50 +345,50 @@ GNUNET_CONTAINER_multiuuidmap_iterate(
340 struct GNUNET_Uuid kc; 345 struct GNUNET_Uuid kc;
341 346
342 count = 0; 347 count = 0;
343 GNUNET_assert(NULL != map); 348 GNUNET_assert (NULL != map);
344 ce = &map->next_cache[map->next_cache_off]; 349 ce = &map->next_cache[map->next_cache_off];
345 GNUNET_assert(++map->next_cache_off < NEXT_CACHE_SIZE); 350 GNUNET_assert (++map->next_cache_off < NEXT_CACHE_SIZE);
346 for (unsigned int i = 0; i < map->map_length; i++) 351 for (unsigned int i = 0; i < map->map_length; i++)
352 {
353 me = map->map[i];
354 if (map->use_small_entries)
347 { 355 {
348 me = map->map[i]; 356 struct SmallMapEntry *sme;
349 if (map->use_small_entries) 357
358 ce->sme = me.sme;
359 while (NULL != (sme = ce->sme))
360 {
361 ce->sme = sme->next;
362 if ((NULL != it) && (GNUNET_OK != it (it_cls, sme->key, sme->value)))
350 { 363 {
351 struct SmallMapEntry *sme; 364 GNUNET_assert (--map->next_cache_off < NEXT_CACHE_SIZE);
352 365 return GNUNET_SYSERR;
353 ce->sme = me.sme;
354 while (NULL != (sme = ce->sme))
355 {
356 ce->sme = sme->next;
357 if ((NULL != it) && (GNUNET_OK != it(it_cls, sme->key, sme->value)))
358 {
359 GNUNET_assert(--map->next_cache_off < NEXT_CACHE_SIZE);
360 return GNUNET_SYSERR;
361 }
362 count++;
363 }
364 } 366 }
365 else 367 count++;
368 }
369 }
370 else
371 {
372 struct BigMapEntry *bme;
373
374 ce->bme = me.bme;
375 while (NULL != (bme = ce->bme))
376 {
377 ce->bme = bme->next;
378 if (NULL != it)
366 { 379 {
367 struct BigMapEntry *bme; 380 kc = bme->key;
368 381 if (GNUNET_OK != it (it_cls, &kc, bme->value))
369 ce->bme = me.bme; 382 {
370 while (NULL != (bme = ce->bme)) 383 GNUNET_assert (--map->next_cache_off < NEXT_CACHE_SIZE);
371 { 384 return GNUNET_SYSERR;
372 ce->bme = bme->next; 385 }
373 if (NULL != it)
374 {
375 kc = bme->key;
376 if (GNUNET_OK != it(it_cls, &kc, bme->value))
377 {
378 GNUNET_assert(--map->next_cache_off < NEXT_CACHE_SIZE);
379 return GNUNET_SYSERR;
380 }
381 }
382 count++;
383 }
384 } 386 }
387 count++;
388 }
385 } 389 }
386 GNUNET_assert(--map->next_cache_off < NEXT_CACHE_SIZE); 390 }
391 GNUNET_assert (--map->next_cache_off < NEXT_CACHE_SIZE);
387 return count; 392 return count;
388} 393}
389 394
@@ -396,8 +401,8 @@ GNUNET_CONTAINER_multiuuidmap_iterate(
396 * @param bme the entry that is about to be free'd 401 * @param bme the entry that is about to be free'd
397 */ 402 */
398static void 403static void
399update_next_cache_bme(struct GNUNET_CONTAINER_MultiUuidmap *map, 404update_next_cache_bme (struct GNUNET_CONTAINER_MultiUuidmap *map,
400 const struct BigMapEntry *bme) 405 const struct BigMapEntry *bme)
401{ 406{
402 for (unsigned int i = 0; i < map->next_cache_off; i++) 407 for (unsigned int i = 0; i < map->next_cache_off; i++)
403 if (map->next_cache[i].bme == bme) 408 if (map->next_cache[i].bme == bme)
@@ -413,8 +418,8 @@ update_next_cache_bme(struct GNUNET_CONTAINER_MultiUuidmap *map,
413 * @param sme the entry that is about to be free'd 418 * @param sme the entry that is about to be free'd
414 */ 419 */
415static void 420static void
416update_next_cache_sme(struct GNUNET_CONTAINER_MultiUuidmap *map, 421update_next_cache_sme (struct GNUNET_CONTAINER_MultiUuidmap *map,
417 const struct SmallMapEntry *sme) 422 const struct SmallMapEntry *sme)
418{ 423{
419 for (unsigned int i = 0; i < map->next_cache_off; i++) 424 for (unsigned int i = 0; i < map->next_cache_off; i++)
420 if (map->next_cache[i].sme == sme) 425 if (map->next_cache[i].sme == sme)
@@ -434,56 +439,56 @@ update_next_cache_sme(struct GNUNET_CONTAINER_MultiUuidmap *map,
434 * is not in the map 439 * is not in the map
435 */ 440 */
436int 441int
437GNUNET_CONTAINER_multiuuidmap_remove(struct GNUNET_CONTAINER_MultiUuidmap *map, 442GNUNET_CONTAINER_multiuuidmap_remove (struct GNUNET_CONTAINER_MultiUuidmap *map,
438 const struct GNUNET_Uuid *key, 443 const struct GNUNET_Uuid *key,
439 const void *value) 444 const void *value)
440{ 445{
441 union MapEntry me; 446 union MapEntry me;
442 unsigned int i; 447 unsigned int i;
443 448
444 map->modification_counter++; 449 map->modification_counter++;
445 i = idx_of(map, key); 450 i = idx_of (map, key);
446 me = map->map[i]; 451 me = map->map[i];
447 if (map->use_small_entries) 452 if (map->use_small_entries)
448 { 453 {
449 struct SmallMapEntry *p = NULL; 454 struct SmallMapEntry *p = NULL;
450 455
451 for (struct SmallMapEntry *sme = me.sme; NULL != sme; sme = sme->next) 456 for (struct SmallMapEntry *sme = me.sme; NULL != sme; sme = sme->next)
452 { 457 {
453 if ((0 == GNUNET_memcmp(key, sme->key)) && (value == sme->value)) 458 if ((0 == GNUNET_memcmp (key, sme->key)) && (value == sme->value))
454 { 459 {
455 if (NULL == p) 460 if (NULL == p)
456 map->map[i].sme = sme->next; 461 map->map[i].sme = sme->next;
457 else 462 else
458 p->next = sme->next; 463 p->next = sme->next;
459 update_next_cache_sme(map, sme); 464 update_next_cache_sme (map, sme);
460 GNUNET_free(sme); 465 GNUNET_free (sme);
461 map->size--; 466 map->size--;
462 return GNUNET_YES; 467 return GNUNET_YES;
463 } 468 }
464 p = sme; 469 p = sme;
465 }
466 } 470 }
471 }
467 else 472 else
468 { 473 {
469 struct BigMapEntry *p = NULL; 474 struct BigMapEntry *p = NULL;
470 475
471 for (struct BigMapEntry *bme = me.bme; NULL != bme; bme = bme->next) 476 for (struct BigMapEntry *bme = me.bme; NULL != bme; bme = bme->next)
472 { 477 {
473 if ((0 == GNUNET_memcmp(key, &bme->key)) && (value == bme->value)) 478 if ((0 == GNUNET_memcmp (key, &bme->key)) && (value == bme->value))
474 { 479 {
475 if (NULL == p) 480 if (NULL == p)
476 map->map[i].bme = bme->next; 481 map->map[i].bme = bme->next;
477 else 482 else
478 p->next = bme->next; 483 p->next = bme->next;
479 update_next_cache_bme(map, bme); 484 update_next_cache_bme (map, bme);
480 GNUNET_free(bme); 485 GNUNET_free (bme);
481 map->size--; 486 map->size--;
482 return GNUNET_YES; 487 return GNUNET_YES;
483 } 488 }
484 p = bme; 489 p = bme;
485 }
486 } 490 }
491 }
487 return GNUNET_NO; 492 return GNUNET_NO;
488} 493}
489 494
@@ -497,7 +502,7 @@ GNUNET_CONTAINER_multiuuidmap_remove(struct GNUNET_CONTAINER_MultiUuidmap *map,
497 * @return number of values removed 502 * @return number of values removed
498 */ 503 */
499int 504int
500GNUNET_CONTAINER_multiuuidmap_remove_all( 505GNUNET_CONTAINER_multiuuidmap_remove_all (
501 struct GNUNET_CONTAINER_MultiUuidmap *map, 506 struct GNUNET_CONTAINER_MultiUuidmap *map,
502 const struct GNUNET_Uuid *key) 507 const struct GNUNET_Uuid *key)
503{ 508{
@@ -508,70 +513,70 @@ GNUNET_CONTAINER_multiuuidmap_remove_all(
508 map->modification_counter++; 513 map->modification_counter++;
509 514
510 ret = 0; 515 ret = 0;
511 i = idx_of(map, key); 516 i = idx_of (map, key);
512 me = map->map[i]; 517 me = map->map[i];
513 if (map->use_small_entries) 518 if (map->use_small_entries)
514 { 519 {
515 struct SmallMapEntry *sme; 520 struct SmallMapEntry *sme;
516 struct SmallMapEntry *p; 521 struct SmallMapEntry *p;
517 522
518 p = NULL; 523 p = NULL;
519 sme = me.sme; 524 sme = me.sme;
520 while (NULL != sme) 525 while (NULL != sme)
521 { 526 {
522 if (0 == GNUNET_memcmp(key, sme->key)) 527 if (0 == GNUNET_memcmp (key, sme->key))
523 { 528 {
524 if (NULL == p) 529 if (NULL == p)
525 map->map[i].sme = sme->next; 530 map->map[i].sme = sme->next;
526 else 531 else
527 p->next = sme->next; 532 p->next = sme->next;
528 update_next_cache_sme(map, sme); 533 update_next_cache_sme (map, sme);
529 GNUNET_free(sme); 534 GNUNET_free (sme);
530 map->size--; 535 map->size--;
531 if (NULL == p) 536 if (NULL == p)
532 sme = map->map[i].sme; 537 sme = map->map[i].sme;
533 else 538 else
534 sme = p->next; 539 sme = p->next;
535 ret++; 540 ret++;
536 } 541 }
537 else 542 else
538 { 543 {
539 p = sme; 544 p = sme;
540 sme = sme->next; 545 sme = sme->next;
541 } 546 }
542 }
543 } 547 }
548 }
544 else 549 else
545 { 550 {
546 struct BigMapEntry *bme; 551 struct BigMapEntry *bme;
547 struct BigMapEntry *p; 552 struct BigMapEntry *p;
548 553
549 p = NULL; 554 p = NULL;
550 bme = me.bme; 555 bme = me.bme;
551 while (NULL != bme) 556 while (NULL != bme)
552 { 557 {
553 if (0 == GNUNET_memcmp(key, &bme->key)) 558 if (0 == GNUNET_memcmp (key, &bme->key))
554 { 559 {
555 if (NULL == p) 560 if (NULL == p)
556 map->map[i].bme = bme->next; 561 map->map[i].bme = bme->next;
557 else 562 else
558 p->next = bme->next; 563 p->next = bme->next;
559 update_next_cache_bme(map, bme); 564 update_next_cache_bme (map, bme);
560 GNUNET_free(bme); 565 GNUNET_free (bme);
561 map->size--; 566 map->size--;
562 if (NULL == p) 567 if (NULL == p)
563 bme = map->map[i].bme; 568 bme = map->map[i].bme;
564 else 569 else
565 bme = p->next; 570 bme = p->next;
566 ret++; 571 ret++;
567 } 572 }
568 else 573 else
569 { 574 {
570 p = bme; 575 p = bme;
571 bme = bme->next; 576 bme = bme->next;
572 } 577 }
573 }
574 } 578 }
579 }
575 return ret; 580 return ret;
576} 581}
577 582
@@ -586,25 +591,25 @@ GNUNET_CONTAINER_multiuuidmap_remove_all(
586 * #GNUNET_NO if not 591 * #GNUNET_NO if not
587 */ 592 */
588int 593int
589GNUNET_CONTAINER_multiuuidmap_contains( 594GNUNET_CONTAINER_multiuuidmap_contains (
590 const struct GNUNET_CONTAINER_MultiUuidmap *map, 595 const struct GNUNET_CONTAINER_MultiUuidmap *map,
591 const struct GNUNET_Uuid *key) 596 const struct GNUNET_Uuid *key)
592{ 597{
593 union MapEntry me; 598 union MapEntry me;
594 599
595 me = map->map[idx_of(map, key)]; 600 me = map->map[idx_of (map, key)];
596 if (map->use_small_entries) 601 if (map->use_small_entries)
597 { 602 {
598 for (struct SmallMapEntry *sme = me.sme; NULL != sme; sme = sme->next) 603 for (struct SmallMapEntry *sme = me.sme; NULL != sme; sme = sme->next)
599 if (0 == GNUNET_memcmp(key, sme->key)) 604 if (0 == GNUNET_memcmp (key, sme->key))
600 return GNUNET_YES; 605 return GNUNET_YES;
601 } 606 }
602 else 607 else
603 { 608 {
604 for (struct BigMapEntry *bme = me.bme; NULL != bme; bme = bme->next) 609 for (struct BigMapEntry *bme = me.bme; NULL != bme; bme = bme->next)
605 if (0 == GNUNET_memcmp(key, &bme->key)) 610 if (0 == GNUNET_memcmp (key, &bme->key))
606 return GNUNET_YES; 611 return GNUNET_YES;
607 } 612 }
608 return GNUNET_NO; 613 return GNUNET_NO;
609} 614}
610 615
@@ -620,26 +625,26 @@ GNUNET_CONTAINER_multiuuidmap_contains(
620 * #GNUNET_NO if not 625 * #GNUNET_NO if not
621 */ 626 */
622int 627int
623GNUNET_CONTAINER_multiuuidmap_contains_value( 628GNUNET_CONTAINER_multiuuidmap_contains_value (
624 const struct GNUNET_CONTAINER_MultiUuidmap *map, 629 const struct GNUNET_CONTAINER_MultiUuidmap *map,
625 const struct GNUNET_Uuid *key, 630 const struct GNUNET_Uuid *key,
626 const void *value) 631 const void *value)
627{ 632{
628 union MapEntry me; 633 union MapEntry me;
629 634
630 me = map->map[idx_of(map, key)]; 635 me = map->map[idx_of (map, key)];
631 if (map->use_small_entries) 636 if (map->use_small_entries)
632 { 637 {
633 for (struct SmallMapEntry *sme = me.sme; NULL != sme; sme = sme->next) 638 for (struct SmallMapEntry *sme = me.sme; NULL != sme; sme = sme->next)
634 if ((0 == GNUNET_memcmp(key, sme->key)) && (sme->value == value)) 639 if ((0 == GNUNET_memcmp (key, sme->key)) && (sme->value == value))
635 return GNUNET_YES; 640 return GNUNET_YES;
636 } 641 }
637 else 642 else
638 { 643 {
639 for (struct BigMapEntry *bme = me.bme; NULL != bme; bme = bme->next) 644 for (struct BigMapEntry *bme = me.bme; NULL != bme; bme = bme->next)
640 if ((0 == GNUNET_memcmp(key, &bme->key)) && (bme->value == value)) 645 if ((0 == GNUNET_memcmp (key, &bme->key)) && (bme->value == value))
641 return GNUNET_YES; 646 return GNUNET_YES;
642 } 647 }
643 return GNUNET_NO; 648 return GNUNET_NO;
644} 649}
645 650
@@ -650,7 +655,7 @@ GNUNET_CONTAINER_multiuuidmap_contains_value(
650 * @param map the hash map to grow 655 * @param map the hash map to grow
651 */ 656 */
652static void 657static void
653grow(struct GNUNET_CONTAINER_MultiUuidmap *map) 658grow (struct GNUNET_CONTAINER_MultiUuidmap *map)
654{ 659{
655 union MapEntry *old_map; 660 union MapEntry *old_map;
656 union MapEntry *new_map; 661 union MapEntry *new_map;
@@ -665,40 +670,40 @@ grow(struct GNUNET_CONTAINER_MultiUuidmap *map)
665 new_len = old_len; /* never use 0 */ 670 new_len = old_len; /* never use 0 */
666 if (new_len == old_len) 671 if (new_len == old_len)
667 return; /* nothing changed */ 672 return; /* nothing changed */
668 new_map = GNUNET_malloc_large(new_len * sizeof(union MapEntry)); 673 new_map = GNUNET_malloc_large (new_len * sizeof(union MapEntry));
669 if (NULL == new_map) 674 if (NULL == new_map)
670 return; /* grow not possible */ 675 return; /* grow not possible */
671 map->modification_counter++; 676 map->modification_counter++;
672 map->map_length = new_len; 677 map->map_length = new_len;
673 map->map = new_map; 678 map->map = new_map;
674 for (unsigned int i = 0; i < old_len; i++) 679 for (unsigned int i = 0; i < old_len; i++)
680 {
681 if (map->use_small_entries)
675 { 682 {
676 if (map->use_small_entries) 683 struct SmallMapEntry *sme;
677 { 684
678 struct SmallMapEntry *sme; 685 while (NULL != (sme = old_map[i].sme))
679 686 {
680 while (NULL != (sme = old_map[i].sme)) 687 old_map[i].sme = sme->next;
681 { 688 idx = idx_of (map, sme->key);
682 old_map[i].sme = sme->next; 689 sme->next = new_map[idx].sme;
683 idx = idx_of(map, sme->key); 690 new_map[idx].sme = sme;
684 sme->next = new_map[idx].sme; 691 }
685 new_map[idx].sme = sme;
686 }
687 }
688 else
689 {
690 struct BigMapEntry *bme;
691
692 while (NULL != (bme = old_map[i].bme))
693 {
694 old_map[i].bme = bme->next;
695 idx = idx_of(map, &bme->key);
696 bme->next = new_map[idx].bme;
697 new_map[idx].bme = bme;
698 }
699 }
700 } 692 }
701 GNUNET_free(old_map); 693 else
694 {
695 struct BigMapEntry *bme;
696
697 while (NULL != (bme = old_map[i].bme))
698 {
699 old_map[i].bme = bme->next;
700 idx = idx_of (map, &bme->key);
701 bme->next = new_map[idx].bme;
702 new_map[idx].bme = bme;
703 }
704 }
705 }
706 GNUNET_free (old_map);
702} 707}
703 708
704 709
@@ -715,67 +720,67 @@ grow(struct GNUNET_CONTAINER_MultiUuidmap *map)
715 * value already exists 720 * value already exists
716 */ 721 */
717int 722int
718GNUNET_CONTAINER_multiuuidmap_put(struct GNUNET_CONTAINER_MultiUuidmap *map, 723GNUNET_CONTAINER_multiuuidmap_put (struct GNUNET_CONTAINER_MultiUuidmap *map,
719 const struct GNUNET_Uuid *key, 724 const struct GNUNET_Uuid *key,
720 void *value, 725 void *value,
721 enum GNUNET_CONTAINER_MultiHashMapOption opt) 726 enum GNUNET_CONTAINER_MultiHashMapOption opt)
722{ 727{
723 union MapEntry me; 728 union MapEntry me;
724 unsigned int i; 729 unsigned int i;
725 730
726 i = idx_of(map, key); 731 i = idx_of (map, key);
727 if ((opt != GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE) && 732 if ((opt != GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE) &&
728 (opt != GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_FAST)) 733 (opt != GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_FAST))
734 {
735 me = map->map[i];
736 if (map->use_small_entries)
729 { 737 {
730 me = map->map[i]; 738 for (struct SmallMapEntry *sme = me.sme; NULL != sme; sme = sme->next)
731 if (map->use_small_entries) 739 if (0 == GNUNET_memcmp (key, sme->key))
732 { 740 {
733 for (struct SmallMapEntry *sme = me.sme; NULL != sme; sme = sme->next) 741 if (opt == GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY)
734 if (0 == GNUNET_memcmp(key, sme->key)) 742 return GNUNET_SYSERR;
735 { 743 sme->value = value;
736 if (opt == GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY) 744 return GNUNET_NO;
737 return GNUNET_SYSERR;
738 sme->value = value;
739 return GNUNET_NO;
740 }
741 } 745 }
742 else 746 }
747 else
748 {
749 for (struct BigMapEntry *bme = me.bme; NULL != bme; bme = bme->next)
750 if (0 == GNUNET_memcmp (key, &bme->key))
743 { 751 {
744 for (struct BigMapEntry *bme = me.bme; NULL != bme; bme = bme->next) 752 if (opt == GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY)
745 if (0 == GNUNET_memcmp(key, &bme->key)) 753 return GNUNET_SYSERR;
746 { 754 bme->value = value;
747 if (opt == GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY) 755 return GNUNET_NO;
748 return GNUNET_SYSERR;
749 bme->value = value;
750 return GNUNET_NO;
751 }
752 } 756 }
753 } 757 }
758 }
754 if (map->size / 3 >= map->map_length / 4) 759 if (map->size / 3 >= map->map_length / 4)
755 { 760 {
756 grow(map); 761 grow (map);
757 i = idx_of(map, key); 762 i = idx_of (map, key);
758 } 763 }
759 if (map->use_small_entries) 764 if (map->use_small_entries)
760 { 765 {
761 struct SmallMapEntry *sme; 766 struct SmallMapEntry *sme;
762 767
763 sme = GNUNET_new(struct SmallMapEntry); 768 sme = GNUNET_new (struct SmallMapEntry);
764 sme->key = key; 769 sme->key = key;
765 sme->value = value; 770 sme->value = value;
766 sme->next = map->map[i].sme; 771 sme->next = map->map[i].sme;
767 map->map[i].sme = sme; 772 map->map[i].sme = sme;
768 } 773 }
769 else 774 else
770 { 775 {
771 struct BigMapEntry *bme; 776 struct BigMapEntry *bme;
772 777
773 bme = GNUNET_new(struct BigMapEntry); 778 bme = GNUNET_new (struct BigMapEntry);
774 bme->key = *key; 779 bme->key = *key;
775 bme->value = value; 780 bme->value = value;
776 bme->next = map->map[i].bme; 781 bme->next = map->map[i].bme;
777 map->map[i].bme = bme; 782 map->map[i].bme = bme;
778 } 783 }
779 map->size++; 784 map->size++;
780 return GNUNET_OK; 785 return GNUNET_OK;
781} 786}
@@ -792,7 +797,7 @@ GNUNET_CONTAINER_multiuuidmap_put(struct GNUNET_CONTAINER_MultiUuidmap *map,
792 * #GNUNET_SYSERR if it aborted iteration 797 * #GNUNET_SYSERR if it aborted iteration
793 */ 798 */
794int 799int
795GNUNET_CONTAINER_multiuuidmap_get_multiple( 800GNUNET_CONTAINER_multiuuidmap_get_multiple (
796 struct GNUNET_CONTAINER_MultiUuidmap *map, 801 struct GNUNET_CONTAINER_MultiUuidmap *map,
797 const struct GNUNET_Uuid *key, 802 const struct GNUNET_Uuid *key,
798 GNUNET_CONTAINER_MultiUuidmapIteratorCallback it, 803 GNUNET_CONTAINER_MultiUuidmapIteratorCallback it,
@@ -803,46 +808,46 @@ GNUNET_CONTAINER_multiuuidmap_get_multiple(
803 union MapEntry *ce; 808 union MapEntry *ce;
804 809
805 ce = &map->next_cache[map->next_cache_off]; 810 ce = &map->next_cache[map->next_cache_off];
806 GNUNET_assert(++map->next_cache_off < NEXT_CACHE_SIZE); 811 GNUNET_assert (++map->next_cache_off < NEXT_CACHE_SIZE);
807 count = 0; 812 count = 0;
808 me = map->map[idx_of(map, key)]; 813 me = map->map[idx_of (map, key)];
809 if (map->use_small_entries) 814 if (map->use_small_entries)
810 { 815 {
811 struct SmallMapEntry *sme; 816 struct SmallMapEntry *sme;
812 817
813 ce->sme = me.sme; 818 ce->sme = me.sme;
814 while (NULL != (sme = ce->sme)) 819 while (NULL != (sme = ce->sme))
815 { 820 {
816 ce->sme = sme->next; 821 ce->sme = sme->next;
817 if (0 != GNUNET_memcmp(key, sme->key)) 822 if (0 != GNUNET_memcmp (key, sme->key))
818 continue; 823 continue;
819 if ((NULL != it) && (GNUNET_OK != it(it_cls, key, sme->value))) 824 if ((NULL != it) && (GNUNET_OK != it (it_cls, key, sme->value)))
820 { 825 {
821 GNUNET_assert(--map->next_cache_off < NEXT_CACHE_SIZE); 826 GNUNET_assert (--map->next_cache_off < NEXT_CACHE_SIZE);
822 return GNUNET_SYSERR; 827 return GNUNET_SYSERR;
823 } 828 }
824 count++; 829 count++;
825 }
826 } 830 }
831 }
827 else 832 else
828 { 833 {
829 struct BigMapEntry *bme; 834 struct BigMapEntry *bme;
830 835
831 ce->bme = me.bme; 836 ce->bme = me.bme;
832 while (NULL != (bme = ce->bme)) 837 while (NULL != (bme = ce->bme))
833 { 838 {
834 ce->bme = bme->next; 839 ce->bme = bme->next;
835 if (0 != GNUNET_memcmp(key, &bme->key)) 840 if (0 != GNUNET_memcmp (key, &bme->key))
836 continue; 841 continue;
837 if ((NULL != it) && (GNUNET_OK != it(it_cls, key, bme->value))) 842 if ((NULL != it) && (GNUNET_OK != it (it_cls, key, bme->value)))
838 { 843 {
839 GNUNET_assert(--map->next_cache_off < NEXT_CACHE_SIZE); 844 GNUNET_assert (--map->next_cache_off < NEXT_CACHE_SIZE);
840 return GNUNET_SYSERR; 845 return GNUNET_SYSERR;
841 } 846 }
842 count++; 847 count++;
843 }
844 } 848 }
845 GNUNET_assert(--map->next_cache_off < NEXT_CACHE_SIZE); 849 }
850 GNUNET_assert (--map->next_cache_off < NEXT_CACHE_SIZE);
846 return count; 851 return count;
847} 852}
848 853
@@ -859,7 +864,7 @@ GNUNET_CONTAINER_multiuuidmap_get_multiple(
859 * @return the number of key value pairs processed, zero or one. 864 * @return the number of key value pairs processed, zero or one.
860 */ 865 */
861unsigned int 866unsigned int
862GNUNET_CONTAINER_multiuuidmap_get_random( 867GNUNET_CONTAINER_multiuuidmap_get_random (
863 const struct GNUNET_CONTAINER_MultiUuidmap *map, 868 const struct GNUNET_CONTAINER_MultiUuidmap *map,
864 GNUNET_CONTAINER_MultiUuidmapIteratorCallback it, 869 GNUNET_CONTAINER_MultiUuidmapIteratorCallback it,
865 void *it_cls) 870 void *it_cls)
@@ -871,38 +876,38 @@ GNUNET_CONTAINER_multiuuidmap_get_random(
871 return 0; 876 return 0;
872 if (NULL == it) 877 if (NULL == it)
873 return 1; 878 return 1;
874 off = GNUNET_CRYPTO_random_u32(GNUNET_CRYPTO_QUALITY_NONCE, map->size); 879 off = GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_NONCE, map->size);
875 for (unsigned int idx = 0; idx < map->map_length; idx++) 880 for (unsigned int idx = 0; idx < map->map_length; idx++)
881 {
882 me = map->map[idx];
883 if (map->use_small_entries)
876 { 884 {
877 me = map->map[idx]; 885 for (struct SmallMapEntry *sme = me.sme; NULL != sme; sme = sme->next)
878 if (map->use_small_entries) 886 {
887 if (0 == off)
879 { 888 {
880 for (struct SmallMapEntry *sme = me.sme; NULL != sme; sme = sme->next) 889 if (GNUNET_OK != it (it_cls, sme->key, sme->value))
881 { 890 return GNUNET_SYSERR;
882 if (0 == off) 891 return 1;
883 {
884 if (GNUNET_OK != it(it_cls, sme->key, sme->value))
885 return GNUNET_SYSERR;
886 return 1;
887 }
888 off--;
889 }
890 } 892 }
891 else 893 off--;
894 }
895 }
896 else
897 {
898 for (struct BigMapEntry *bme = me.bme; NULL != bme; bme = bme->next)
899 {
900 if (0 == off)
892 { 901 {
893 for (struct BigMapEntry *bme = me.bme; NULL != bme; bme = bme->next) 902 if (GNUNET_OK != it (it_cls, &bme->key, bme->value))
894 { 903 return GNUNET_SYSERR;
895 if (0 == off) 904 return 1;
896 {
897 if (GNUNET_OK != it(it_cls, &bme->key, bme->value))
898 return GNUNET_SYSERR;
899 return 1;
900 }
901 off--;
902 }
903 } 905 }
906 off--;
907 }
904 } 908 }
905 GNUNET_break(0); 909 }
910 GNUNET_break (0);
906 return GNUNET_SYSERR; 911 return GNUNET_SYSERR;
907} 912}
908 913
@@ -920,12 +925,12 @@ GNUNET_CONTAINER_multiuuidmap_get_random(
920 * @return an iterator over the given multiuuidmap 'map' 925 * @return an iterator over the given multiuuidmap 'map'
921 */ 926 */
922struct GNUNET_CONTAINER_MultiUuidmapIterator * 927struct GNUNET_CONTAINER_MultiUuidmapIterator *
923GNUNET_CONTAINER_multiuuidmap_iterator_create( 928GNUNET_CONTAINER_multiuuidmap_iterator_create (
924 const struct GNUNET_CONTAINER_MultiUuidmap *map) 929 const struct GNUNET_CONTAINER_MultiUuidmap *map)
925{ 930{
926 struct GNUNET_CONTAINER_MultiUuidmapIterator *iter; 931 struct GNUNET_CONTAINER_MultiUuidmapIterator *iter;
927 932
928 iter = GNUNET_new(struct GNUNET_CONTAINER_MultiUuidmapIterator); 933 iter = GNUNET_new (struct GNUNET_CONTAINER_MultiUuidmapIterator);
929 iter->map = map; 934 iter->map = map;
930 iter->modification_counter = map->modification_counter; 935 iter->modification_counter = map->modification_counter;
931 iter->me = map->map[0]; 936 iter->me = map->map[0];
@@ -948,47 +953,47 @@ GNUNET_CONTAINER_multiuuidmap_iterator_create(
948 * #GNUNET_NO if we are out of elements 953 * #GNUNET_NO if we are out of elements
949 */ 954 */
950int 955int
951GNUNET_CONTAINER_multiuuidmap_iterator_next( 956GNUNET_CONTAINER_multiuuidmap_iterator_next (
952 struct GNUNET_CONTAINER_MultiUuidmapIterator *iter, 957 struct GNUNET_CONTAINER_MultiUuidmapIterator *iter,
953 struct GNUNET_Uuid *key, 958 struct GNUNET_Uuid *key,
954 const void **value) 959 const void **value)
955{ 960{
956 /* make sure the map has not been modified */ 961 /* make sure the map has not been modified */
957 GNUNET_assert(iter->modification_counter == iter->map->modification_counter); 962 GNUNET_assert (iter->modification_counter == iter->map->modification_counter);
958 963
959 /* look for the next entry, skipping empty buckets */ 964 /* look for the next entry, skipping empty buckets */
960 while (1) 965 while (1)
966 {
967 if (iter->idx >= iter->map->map_length)
968 return GNUNET_NO;
969 if (GNUNET_YES == iter->map->use_small_entries)
961 { 970 {
962 if (iter->idx >= iter->map->map_length) 971 if (NULL != iter->me.sme)
963 return GNUNET_NO; 972 {
964 if (GNUNET_YES == iter->map->use_small_entries) 973 if (NULL != key)
965 { 974 *key = *iter->me.sme->key;
966 if (NULL != iter->me.sme) 975 if (NULL != value)
967 { 976 *value = iter->me.sme->value;
968 if (NULL != key) 977 iter->me.sme = iter->me.sme->next;
969 *key = *iter->me.sme->key; 978 return GNUNET_YES;
970 if (NULL != value) 979 }
971 *value = iter->me.sme->value; 980 }
972 iter->me.sme = iter->me.sme->next; 981 else
973 return GNUNET_YES; 982 {
974 } 983 if (NULL != iter->me.bme)
975 } 984 {
976 else 985 if (NULL != key)
977 { 986 *key = iter->me.bme->key;
978 if (NULL != iter->me.bme) 987 if (NULL != value)
979 { 988 *value = iter->me.bme->value;
980 if (NULL != key) 989 iter->me.bme = iter->me.bme->next;
981 *key = iter->me.bme->key; 990 return GNUNET_YES;
982 if (NULL != value) 991 }
983 *value = iter->me.bme->value;
984 iter->me.bme = iter->me.bme->next;
985 return GNUNET_YES;
986 }
987 }
988 iter->idx += 1;
989 if (iter->idx < iter->map->map_length)
990 iter->me = iter->map->map[iter->idx];
991 } 992 }
993 iter->idx += 1;
994 if (iter->idx < iter->map->map_length)
995 iter->me = iter->map->map[iter->idx];
996 }
992} 997}
993 998
994 999
@@ -998,10 +1003,10 @@ GNUNET_CONTAINER_multiuuidmap_iterator_next(
998 * @param iter the iterator to destroy 1003 * @param iter the iterator to destroy
999 */ 1004 */
1000void 1005void
1001GNUNET_CONTAINER_multiuuidmap_iterator_destroy( 1006GNUNET_CONTAINER_multiuuidmap_iterator_destroy (
1002 struct GNUNET_CONTAINER_MultiUuidmapIterator *iter) 1007 struct GNUNET_CONTAINER_MultiUuidmapIterator *iter)
1003{ 1008{
1004 GNUNET_free(iter); 1009 GNUNET_free (iter);
1005} 1010}
1006 1011
1007 1012