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