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