diff options
Diffstat (limited to 'src/util/container_multipeermap.c')
-rw-r--r-- | src/util/container_multipeermap.c | 282 |
1 files changed, 185 insertions, 97 deletions
diff --git a/src/util/container_multipeermap.c b/src/util/container_multipeermap.c index ede2fd8b7..67d6e1684 100644 --- a/src/util/container_multipeermap.c +++ b/src/util/container_multipeermap.c | |||
@@ -27,6 +27,14 @@ | |||
27 | #define LOG(kind,...) GNUNET_log_from (kind, "util-container-multipeermap", __VA_ARGS__) | 27 | #define LOG(kind,...) GNUNET_log_from (kind, "util-container-multipeermap", __VA_ARGS__) |
28 | 28 | ||
29 | /** | 29 | /** |
30 | * Maximum recursion depth for callbacks of | ||
31 | * #GNUNET_CONTAINER_multihashmap_get_multiple() themselve s | ||
32 | * again calling #GNUNET_CONTAINER_multihashmap_get_multiple(). | ||
33 | * Should be totally excessive, but if violated we die. | ||
34 | */ | ||
35 | #define NEXT_CACHE_SIZE 16 | ||
36 | |||
37 | /** | ||
30 | * An entry in the hash map with the full key. | 38 | * An entry in the hash map with the full key. |
31 | */ | 39 | */ |
32 | struct BigMapEntry | 40 | struct BigMapEntry |
@@ -112,8 +120,8 @@ struct GNUNET_CONTAINER_MultiPeerMap | |||
112 | unsigned int map_length; | 120 | unsigned int map_length; |
113 | 121 | ||
114 | /** | 122 | /** |
115 | * GNUNET_NO if the map entries are of type 'struct BigMapEntry', | 123 | * #GNUNET_NO if the map entries are of type 'struct BigMapEntry', |
116 | * GNUNET_YES if the map entries are of type 'struct SmallMapEntry'. | 124 | * #GNUNET_YES if the map entries are of type 'struct SmallMapEntry'. |
117 | */ | 125 | */ |
118 | int use_small_entries; | 126 | int use_small_entries; |
119 | 127 | ||
@@ -122,6 +130,19 @@ struct GNUNET_CONTAINER_MultiPeerMap | |||
122 | * to the map, so that iterators can check if they are still valid. | 130 | * to the map, so that iterators can check if they are still valid. |
123 | */ | 131 | */ |
124 | unsigned int modification_counter; | 132 | unsigned int modification_counter; |
133 | |||
134 | /** | ||
135 | * Map entries indicating iteration positions currently | ||
136 | * in use by #GNUNET_CONTAINER_multihashmap_get_multiple(). | ||
137 | * Only used up to @e next_cache_off. | ||
138 | */ | ||
139 | union MapEntry next_cache[NEXT_CACHE_SIZE]; | ||
140 | |||
141 | /** | ||
142 | * Offset of @e next_cache entries in use, must be smaller | ||
143 | * than #NEXT_CACHE_SIZE. | ||
144 | */ | ||
145 | unsigned int next_cache_off; | ||
125 | }; | 146 | }; |
126 | 147 | ||
127 | 148 | ||
@@ -177,7 +198,8 @@ GNUNET_CONTAINER_multipeermap_create (unsigned int len, | |||
177 | 198 | ||
178 | GNUNET_assert (len > 0); | 199 | GNUNET_assert (len > 0); |
179 | map = GNUNET_new (struct GNUNET_CONTAINER_MultiPeerMap); | 200 | map = GNUNET_new (struct GNUNET_CONTAINER_MultiPeerMap); |
180 | map->map = GNUNET_malloc (len * sizeof (union MapEntry)); | 201 | map->map = GNUNET_new_array (len, |
202 | union MapEntry); | ||
181 | map->map_length = len; | 203 | map->map_length = len; |
182 | map->use_small_entries = do_not_copy_keys; | 204 | map->use_small_entries = do_not_copy_keys; |
183 | return map; | 205 | return map; |
@@ -191,14 +213,13 @@ GNUNET_CONTAINER_multipeermap_create (unsigned int len, | |||
191 | * @param map the map | 213 | * @param map the map |
192 | */ | 214 | */ |
193 | void | 215 | void |
194 | GNUNET_CONTAINER_multipeermap_destroy (struct GNUNET_CONTAINER_MultiPeerMap | 216 | GNUNET_CONTAINER_multipeermap_destroy (struct GNUNET_CONTAINER_MultiPeerMap *map) |
195 | *map) | ||
196 | { | 217 | { |
197 | unsigned int i; | 218 | GNUNET_assert (0 == map->next_cache_off); |
198 | union MapEntry me; | 219 | for (unsigned int i = 0; i < map->map_length; i++) |
199 | |||
200 | for (i = 0; i < map->map_length; i++) | ||
201 | { | 220 | { |
221 | union MapEntry me; | ||
222 | |||
202 | me = map->map[i]; | 223 | me = map->map[i]; |
203 | if (map->use_small_entries) | 224 | if (map->use_small_entries) |
204 | { | 225 | { |
@@ -246,7 +267,9 @@ idx_of (const struct GNUNET_CONTAINER_MultiPeerMap *map, | |||
246 | unsigned int kx; | 267 | unsigned int kx; |
247 | 268 | ||
248 | GNUNET_assert (NULL != map); | 269 | GNUNET_assert (NULL != map); |
249 | GNUNET_memcpy (&kx, key, sizeof (kx)); | 270 | GNUNET_memcpy (&kx, |
271 | key, | ||
272 | sizeof (kx)); | ||
250 | return kx % map->map_length; | 273 | return kx % map->map_length; |
251 | } | 274 | } |
252 | 275 | ||
@@ -258,8 +281,7 @@ idx_of (const struct GNUNET_CONTAINER_MultiPeerMap *map, | |||
258 | * @return the number of key value pairs | 281 | * @return the number of key value pairs |
259 | */ | 282 | */ |
260 | unsigned int | 283 | unsigned int |
261 | GNUNET_CONTAINER_multipeermap_size (const struct GNUNET_CONTAINER_MultiPeerMap | 284 | GNUNET_CONTAINER_multipeermap_size (const struct GNUNET_CONTAINER_MultiPeerMap *map) |
262 | *map) | ||
263 | { | 285 | { |
264 | return map->size; | 286 | return map->size; |
265 | } | 287 | } |
@@ -276,26 +298,26 @@ GNUNET_CONTAINER_multipeermap_size (const struct GNUNET_CONTAINER_MultiPeerMap | |||
276 | * key-value pairs with value NULL | 298 | * key-value pairs with value NULL |
277 | */ | 299 | */ |
278 | void * | 300 | void * |
279 | GNUNET_CONTAINER_multipeermap_get (const struct GNUNET_CONTAINER_MultiPeerMap | 301 | GNUNET_CONTAINER_multipeermap_get (const struct GNUNET_CONTAINER_MultiPeerMap *map, |
280 | *map, const struct GNUNET_PeerIdentity *key) | 302 | const struct GNUNET_PeerIdentity *key) |
281 | { | 303 | { |
282 | union MapEntry me; | 304 | union MapEntry me; |
283 | 305 | ||
284 | me = map->map[idx_of (map, key)]; | 306 | me = map->map[idx_of (map, key)]; |
285 | if (map->use_small_entries) | 307 | if (map->use_small_entries) |
286 | { | 308 | { |
287 | struct SmallMapEntry *sme; | 309 | for (struct SmallMapEntry *sme = me.sme; NULL != sme; sme = sme->next) |
288 | 310 | if (0 == memcmp (key, | |
289 | for (sme = me.sme; NULL != sme; sme = sme->next) | 311 | sme->key, |
290 | if (0 == memcmp (key, sme->key, sizeof (struct GNUNET_PeerIdentity))) | 312 | sizeof (struct GNUNET_PeerIdentity))) |
291 | return sme->value; | 313 | return sme->value; |
292 | } | 314 | } |
293 | else | 315 | else |
294 | { | 316 | { |
295 | struct BigMapEntry *bme; | 317 | for (struct BigMapEntry *bme = me.bme; NULL != bme; bme = bme->next) |
296 | 318 | if (0 == memcmp (key, | |
297 | for (bme = me.bme; NULL != bme; bme = bme->next) | 319 | &bme->key, |
298 | if (0 == memcmp (key, &bme->key, sizeof (struct GNUNET_PeerIdentity))) | 320 | sizeof (struct GNUNET_PeerIdentity))) |
299 | return bme->value; | 321 | return bme->value; |
300 | } | 322 | } |
301 | return NULL; | 323 | return NULL; |
@@ -312,34 +334,39 @@ GNUNET_CONTAINER_multipeermap_get (const struct GNUNET_CONTAINER_MultiPeerMap | |||
312 | * #GNUNET_SYSERR if it aborted iteration | 334 | * #GNUNET_SYSERR if it aborted iteration |
313 | */ | 335 | */ |
314 | int | 336 | int |
315 | GNUNET_CONTAINER_multipeermap_iterate (const struct | 337 | GNUNET_CONTAINER_multipeermap_iterate (struct GNUNET_CONTAINER_MultiPeerMap *map, |
316 | GNUNET_CONTAINER_MultiPeerMap *map, | ||
317 | GNUNET_CONTAINER_PeerMapIterator it, | 338 | GNUNET_CONTAINER_PeerMapIterator it, |
318 | void *it_cls) | 339 | void *it_cls) |
319 | { | 340 | { |
320 | int count; | 341 | int count; |
321 | unsigned int i; | ||
322 | union MapEntry me; | 342 | union MapEntry me; |
343 | union MapEntry *ce; | ||
323 | struct GNUNET_PeerIdentity kc; | 344 | struct GNUNET_PeerIdentity kc; |
324 | 345 | ||
325 | count = 0; | 346 | count = 0; |
326 | GNUNET_assert (NULL != map); | 347 | GNUNET_assert (NULL != map); |
327 | for (i = 0; i < map->map_length; i++) | 348 | ce = &map->next_cache[map->next_cache_off]; |
349 | GNUNET_assert (++map->next_cache_off < NEXT_CACHE_SIZE); | ||
350 | for (unsigned int i = 0; i < map->map_length; i++) | ||
328 | { | 351 | { |
329 | me = map->map[i]; | 352 | me = map->map[i]; |
330 | if (map->use_small_entries) | 353 | if (map->use_small_entries) |
331 | { | 354 | { |
332 | struct SmallMapEntry *sme; | 355 | struct SmallMapEntry *sme; |
333 | struct SmallMapEntry *nxt; | ||
334 | 356 | ||
335 | nxt = me.sme; | 357 | ce->sme = me.sme; |
336 | while (NULL != (sme = nxt)) | 358 | while (NULL != (sme = ce->sme)) |
337 | { | 359 | { |
338 | nxt = sme->next; | 360 | ce->sme = sme->next; |
339 | if (NULL != it) | 361 | if (NULL != it) |
340 | { | 362 | { |
341 | if (GNUNET_OK != it (it_cls, sme->key, sme->value)) | 363 | if (GNUNET_OK != it (it_cls, |
364 | sme->key, | ||
365 | sme->value)) | ||
366 | { | ||
367 | GNUNET_assert (--map->next_cache_off < NEXT_CACHE_SIZE); | ||
342 | return GNUNET_SYSERR; | 368 | return GNUNET_SYSERR; |
369 | } | ||
343 | } | 370 | } |
344 | count++; | 371 | count++; |
345 | } | 372 | } |
@@ -347,27 +374,66 @@ GNUNET_CONTAINER_multipeermap_iterate (const struct | |||
347 | else | 374 | else |
348 | { | 375 | { |
349 | struct BigMapEntry *bme; | 376 | struct BigMapEntry *bme; |
350 | struct BigMapEntry *nxt; | ||
351 | 377 | ||
352 | nxt = me.bme; | 378 | ce->bme = me.bme; |
353 | while (NULL != (bme = nxt)) | 379 | while (NULL != (bme = ce->bme)) |
354 | { | 380 | { |
355 | nxt = bme->next; | 381 | ce->bme = bme->next; |
356 | if (NULL != it) | 382 | if (NULL != it) |
357 | { | 383 | { |
358 | kc = bme->key; | 384 | kc = bme->key; |
359 | if (GNUNET_OK != it (it_cls, &kc, bme->value)) | 385 | if (GNUNET_OK != it (it_cls, |
386 | &kc, | ||
387 | bme->value)) | ||
388 | { | ||
389 | GNUNET_assert (--map->next_cache_off < NEXT_CACHE_SIZE); | ||
360 | return GNUNET_SYSERR; | 390 | return GNUNET_SYSERR; |
391 | } | ||
361 | } | 392 | } |
362 | count++; | 393 | count++; |
363 | } | 394 | } |
364 | } | 395 | } |
365 | } | 396 | } |
397 | GNUNET_assert (--map->next_cache_off < NEXT_CACHE_SIZE); | ||
366 | return count; | 398 | return count; |
367 | } | 399 | } |
368 | 400 | ||
369 | 401 | ||
370 | /** | 402 | /** |
403 | * We are about to free() the @a bme, make sure it is not in | ||
404 | * the list of next values for any iterator in the @a map's next_cache. | ||
405 | * | ||
406 | * @param map the map to check | ||
407 | * @param bme the entry that is about to be free'd | ||
408 | */ | ||
409 | static void | ||
410 | update_next_cache_bme (struct GNUNET_CONTAINER_MultiPeerMap *map, | ||
411 | const struct BigMapEntry *bme) | ||
412 | { | ||
413 | for (unsigned int i=0;i<map->next_cache_off;i++) | ||
414 | if (map->next_cache[i].bme == bme) | ||
415 | map->next_cache[i].bme = bme->next; | ||
416 | } | ||
417 | |||
418 | |||
419 | /** | ||
420 | * We are about to free() the @a sme, make sure it is not in | ||
421 | * the list of next values for any iterator in the @a map's next_cache. | ||
422 | * | ||
423 | * @param map the map to check | ||
424 | * @param sme the entry that is about to be free'd | ||
425 | */ | ||
426 | static void | ||
427 | update_next_cache_sme (struct GNUNET_CONTAINER_MultiPeerMap *map, | ||
428 | const struct SmallMapEntry *sme) | ||
429 | { | ||
430 | for (unsigned int i=0;i<map->next_cache_off;i++) | ||
431 | if (map->next_cache[i].sme == sme) | ||
432 | map->next_cache[i].sme = sme->next; | ||
433 | } | ||
434 | |||
435 | |||
436 | /** | ||
371 | * Remove the given key-value pair from the map. Note that if the | 437 | * Remove the given key-value pair from the map. Note that if the |
372 | * key-value pair is in the map multiple times, only one of the pairs | 438 | * key-value pair is in the map multiple times, only one of the pairs |
373 | * will be removed. | 439 | * will be removed. |
@@ -375,7 +441,7 @@ GNUNET_CONTAINER_multipeermap_iterate (const struct | |||
375 | * @param map the map | 441 | * @param map the map |
376 | * @param key key of the key-value pair | 442 | * @param key key of the key-value pair |
377 | * @param value value of the key-value pair | 443 | * @param value value of the key-value pair |
378 | * @return GNUNET_YES on success, GNUNET_NO if the key-value pair | 444 | * @return #GNUNET_YES on success, #GNUNET_NO if the key-value pair |
379 | * is not in the map | 445 | * is not in the map |
380 | */ | 446 | */ |
381 | int | 447 | int |
@@ -387,16 +453,13 @@ GNUNET_CONTAINER_multipeermap_remove (struct GNUNET_CONTAINER_MultiPeerMap *map, | |||
387 | unsigned int i; | 453 | unsigned int i; |
388 | 454 | ||
389 | map->modification_counter++; | 455 | map->modification_counter++; |
390 | |||
391 | i = idx_of (map, key); | 456 | i = idx_of (map, key); |
392 | me = map->map[i]; | 457 | me = map->map[i]; |
393 | if (map->use_small_entries) | 458 | if (map->use_small_entries) |
394 | { | 459 | { |
395 | struct SmallMapEntry *sme; | 460 | struct SmallMapEntry *p = NULL; |
396 | struct SmallMapEntry *p; | ||
397 | 461 | ||
398 | p = NULL; | 462 | for (struct SmallMapEntry *sme = me.sme; NULL != sme; sme = sme->next) |
399 | for (sme = me.sme; NULL != sme; sme = sme->next) | ||
400 | { | 463 | { |
401 | if ((0 == memcmp (key, sme->key, sizeof (struct GNUNET_PeerIdentity))) && | 464 | if ((0 == memcmp (key, sme->key, sizeof (struct GNUNET_PeerIdentity))) && |
402 | (value == sme->value)) | 465 | (value == sme->value)) |
@@ -405,6 +468,8 @@ GNUNET_CONTAINER_multipeermap_remove (struct GNUNET_CONTAINER_MultiPeerMap *map, | |||
405 | map->map[i].sme = sme->next; | 468 | map->map[i].sme = sme->next; |
406 | else | 469 | else |
407 | p->next = sme->next; | 470 | p->next = sme->next; |
471 | update_next_cache_sme (map, | ||
472 | sme); | ||
408 | GNUNET_free (sme); | 473 | GNUNET_free (sme); |
409 | map->size--; | 474 | map->size--; |
410 | return GNUNET_YES; | 475 | return GNUNET_YES; |
@@ -414,19 +479,21 @@ GNUNET_CONTAINER_multipeermap_remove (struct GNUNET_CONTAINER_MultiPeerMap *map, | |||
414 | } | 479 | } |
415 | else | 480 | else |
416 | { | 481 | { |
417 | struct BigMapEntry *bme; | 482 | struct BigMapEntry *p = NULL; |
418 | struct BigMapEntry *p; | ||
419 | 483 | ||
420 | p = NULL; | 484 | for (struct BigMapEntry *bme = me.bme; NULL != bme; bme = bme->next) |
421 | for (bme = me.bme; NULL != bme; bme = bme->next) | ||
422 | { | 485 | { |
423 | if ((0 == memcmp (key, &bme->key, sizeof (struct GNUNET_PeerIdentity))) && | 486 | if ((0 == memcmp (key, |
487 | &bme->key, | ||
488 | sizeof (struct GNUNET_PeerIdentity))) && | ||
424 | (value == bme->value)) | 489 | (value == bme->value)) |
425 | { | 490 | { |
426 | if (NULL == p) | 491 | if (NULL == p) |
427 | map->map[i].bme = bme->next; | 492 | map->map[i].bme = bme->next; |
428 | else | 493 | else |
429 | p->next = bme->next; | 494 | p->next = bme->next; |
495 | update_next_cache_bme (map, | ||
496 | bme); | ||
430 | GNUNET_free (bme); | 497 | GNUNET_free (bme); |
431 | map->size--; | 498 | map->size--; |
432 | return GNUNET_YES; | 499 | return GNUNET_YES; |
@@ -447,8 +514,8 @@ GNUNET_CONTAINER_multipeermap_remove (struct GNUNET_CONTAINER_MultiPeerMap *map, | |||
447 | * @return number of values removed | 514 | * @return number of values removed |
448 | */ | 515 | */ |
449 | int | 516 | int |
450 | GNUNET_CONTAINER_multipeermap_remove_all (struct GNUNET_CONTAINER_MultiPeerMap | 517 | GNUNET_CONTAINER_multipeermap_remove_all (struct GNUNET_CONTAINER_MultiPeerMap *map, |
451 | *map, const struct GNUNET_PeerIdentity *key) | 518 | const struct GNUNET_PeerIdentity *key) |
452 | { | 519 | { |
453 | union MapEntry me; | 520 | union MapEntry me; |
454 | unsigned int i; | 521 | unsigned int i; |
@@ -468,12 +535,16 @@ GNUNET_CONTAINER_multipeermap_remove_all (struct GNUNET_CONTAINER_MultiPeerMap | |||
468 | sme = me.sme; | 535 | sme = me.sme; |
469 | while (NULL != sme) | 536 | while (NULL != sme) |
470 | { | 537 | { |
471 | if (0 == memcmp (key, sme->key, sizeof (struct GNUNET_PeerIdentity))) | 538 | if (0 == memcmp (key, |
539 | sme->key, | ||
540 | sizeof (struct GNUNET_PeerIdentity))) | ||
472 | { | 541 | { |
473 | if (NULL == p) | 542 | if (NULL == p) |
474 | map->map[i].sme = sme->next; | 543 | map->map[i].sme = sme->next; |
475 | else | 544 | else |
476 | p->next = sme->next; | 545 | p->next = sme->next; |
546 | update_next_cache_sme (map, | ||
547 | sme); | ||
477 | GNUNET_free (sme); | 548 | GNUNET_free (sme); |
478 | map->size--; | 549 | map->size--; |
479 | if (NULL == p) | 550 | if (NULL == p) |
@@ -498,12 +569,16 @@ GNUNET_CONTAINER_multipeermap_remove_all (struct GNUNET_CONTAINER_MultiPeerMap | |||
498 | bme = me.bme; | 569 | bme = me.bme; |
499 | while (NULL != bme) | 570 | while (NULL != bme) |
500 | { | 571 | { |
501 | if (0 == memcmp (key, &bme->key, sizeof (struct GNUNET_PeerIdentity))) | 572 | if (0 == memcmp (key, |
573 | &bme->key, | ||
574 | sizeof (struct GNUNET_PeerIdentity))) | ||
502 | { | 575 | { |
503 | if (NULL == p) | 576 | if (NULL == p) |
504 | map->map[i].bme = bme->next; | 577 | map->map[i].bme = bme->next; |
505 | else | 578 | else |
506 | p->next = bme->next; | 579 | p->next = bme->next; |
580 | update_next_cache_bme (map, | ||
581 | bme); | ||
507 | GNUNET_free (bme); | 582 | GNUNET_free (bme); |
508 | map->size--; | 583 | map->size--; |
509 | if (NULL == p) | 584 | if (NULL == p) |
@@ -529,12 +604,11 @@ GNUNET_CONTAINER_multipeermap_remove_all (struct GNUNET_CONTAINER_MultiPeerMap | |||
529 | * | 604 | * |
530 | * @param map the map | 605 | * @param map the map |
531 | * @param key the key to test if a value exists for it | 606 | * @param key the key to test if a value exists for it |
532 | * @return GNUNET_YES if such a value exists, | 607 | * @return #GNUNET_YES if such a value exists, |
533 | * GNUNET_NO if not | 608 | * #GNUNET_NO if not |
534 | */ | 609 | */ |
535 | int | 610 | int |
536 | GNUNET_CONTAINER_multipeermap_contains (const struct | 611 | GNUNET_CONTAINER_multipeermap_contains (const struct GNUNET_CONTAINER_MultiPeerMap *map, |
537 | GNUNET_CONTAINER_MultiPeerMap *map, | ||
538 | const struct GNUNET_PeerIdentity *key) | 612 | const struct GNUNET_PeerIdentity *key) |
539 | { | 613 | { |
540 | union MapEntry me; | 614 | union MapEntry me; |
@@ -542,17 +616,13 @@ GNUNET_CONTAINER_multipeermap_contains (const struct | |||
542 | me = map->map[idx_of (map, key)]; | 616 | me = map->map[idx_of (map, key)]; |
543 | if (map->use_small_entries) | 617 | if (map->use_small_entries) |
544 | { | 618 | { |
545 | struct SmallMapEntry *sme; | 619 | for (struct SmallMapEntry *sme = me.sme; NULL != sme; sme = sme->next) |
546 | |||
547 | for (sme = me.sme; NULL != sme; sme = sme->next) | ||
548 | if (0 == memcmp (key, sme->key, sizeof (struct GNUNET_PeerIdentity))) | 620 | if (0 == memcmp (key, sme->key, sizeof (struct GNUNET_PeerIdentity))) |
549 | return GNUNET_YES; | 621 | return GNUNET_YES; |
550 | } | 622 | } |
551 | else | 623 | else |
552 | { | 624 | { |
553 | struct BigMapEntry *bme; | 625 | for (struct BigMapEntry *bme = me.bme; NULL != bme; bme = bme->next) |
554 | |||
555 | for (bme = me.bme; NULL != bme; bme = bme->next) | ||
556 | if (0 == memcmp (key, &bme->key, sizeof (struct GNUNET_PeerIdentity))) | 626 | if (0 == memcmp (key, &bme->key, sizeof (struct GNUNET_PeerIdentity))) |
557 | return GNUNET_YES; | 627 | return GNUNET_YES; |
558 | } | 628 | } |
@@ -567,13 +637,12 @@ GNUNET_CONTAINER_multipeermap_contains (const struct | |||
567 | * @param map the map | 637 | * @param map the map |
568 | * @param key the key to test if a value exists for it | 638 | * @param key the key to test if a value exists for it |
569 | * @param value value to test for | 639 | * @param value value to test for |
570 | * @return GNUNET_YES if such a value exists, | 640 | * @return #GNUNET_YES if such a value exists, |
571 | * GNUNET_NO if not | 641 | * #GNUNET_NO if not |
572 | */ | 642 | */ |
573 | int | 643 | int |
574 | GNUNET_CONTAINER_multipeermap_contains_value (const struct | 644 | GNUNET_CONTAINER_multipeermap_contains_value (const struct GNUNET_CONTAINER_MultiPeerMap *map, |
575 | GNUNET_CONTAINER_MultiPeerMap | 645 | const struct GNUNET_PeerIdentity *key, |
576 | *map, const struct GNUNET_PeerIdentity *key, | ||
577 | const void *value) | 646 | const void *value) |
578 | { | 647 | { |
579 | union MapEntry me; | 648 | union MapEntry me; |
@@ -581,19 +650,19 @@ GNUNET_CONTAINER_multipeermap_contains_value (const struct | |||
581 | me = map->map[idx_of (map, key)]; | 650 | me = map->map[idx_of (map, key)]; |
582 | if (map->use_small_entries) | 651 | if (map->use_small_entries) |
583 | { | 652 | { |
584 | struct SmallMapEntry *sme; | 653 | for (struct SmallMapEntry *sme = me.sme; NULL != sme; sme = sme->next) |
585 | 654 | if ( (0 == memcmp (key, | |
586 | for (sme = me.sme; NULL != sme; sme = sme->next) | 655 | sme->key, |
587 | if ( (0 == memcmp (key, sme->key, sizeof (struct GNUNET_PeerIdentity))) && | 656 | sizeof (struct GNUNET_PeerIdentity))) && |
588 | (sme->value == value) ) | 657 | (sme->value == value) ) |
589 | return GNUNET_YES; | 658 | return GNUNET_YES; |
590 | } | 659 | } |
591 | else | 660 | else |
592 | { | 661 | { |
593 | struct BigMapEntry *bme; | 662 | for (struct BigMapEntry *bme = me.bme; NULL != bme; bme = bme->next) |
594 | 663 | if ( (0 == memcmp (key, | |
595 | for (bme = me.bme; NULL != bme; bme = bme->next) | 664 | &bme->key, |
596 | if ( (0 == memcmp (key, &bme->key, sizeof (struct GNUNET_PeerIdentity))) && | 665 | sizeof (struct GNUNET_PeerIdentity))) && |
597 | (bme->value == value) ) | 666 | (bme->value == value) ) |
598 | return GNUNET_YES; | 667 | return GNUNET_YES; |
599 | } | 668 | } |
@@ -621,7 +690,8 @@ grow (struct GNUNET_CONTAINER_MultiPeerMap *map) | |||
621 | old_map = map->map; | 690 | old_map = map->map; |
622 | old_len = map->map_length; | 691 | old_len = map->map_length; |
623 | new_len = old_len * 2; | 692 | new_len = old_len * 2; |
624 | new_map = GNUNET_malloc (sizeof (union MapEntry) * new_len); | 693 | new_map = GNUNET_new_array (new_len, |
694 | union MapEntry); | ||
625 | map->map_length = new_len; | 695 | map->map_length = new_len; |
626 | map->map = new_map; | 696 | map->map = new_map; |
627 | for (i = 0; i < old_len; i++) | 697 | for (i = 0; i < old_len; i++) |
@@ -664,7 +734,7 @@ grow (struct GNUNET_CONTAINER_MultiPeerMap *map) | |||
664 | * @param opt options for put | 734 | * @param opt options for put |
665 | * @return #GNUNET_OK on success, | 735 | * @return #GNUNET_OK on success, |
666 | * #GNUNET_NO if a value was replaced (with REPLACE) | 736 | * #GNUNET_NO if a value was replaced (with REPLACE) |
667 | * #GNUNET_SYSERR if GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY was the option and the | 737 | * #GNUNET_SYSERR if #GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY was the option and the |
668 | * value already exists | 738 | * value already exists |
669 | */ | 739 | */ |
670 | int | 740 | int |
@@ -749,48 +819,66 @@ GNUNET_CONTAINER_multipeermap_put (struct GNUNET_CONTAINER_MultiPeerMap *map, | |||
749 | * #GNUNET_SYSERR if it aborted iteration | 819 | * #GNUNET_SYSERR if it aborted iteration |
750 | */ | 820 | */ |
751 | int | 821 | int |
752 | GNUNET_CONTAINER_multipeermap_get_multiple (const struct GNUNET_CONTAINER_MultiPeerMap *map, | 822 | GNUNET_CONTAINER_multipeermap_get_multiple (struct GNUNET_CONTAINER_MultiPeerMap *map, |
753 | const struct GNUNET_PeerIdentity *key, | 823 | const struct GNUNET_PeerIdentity *key, |
754 | GNUNET_CONTAINER_PeerMapIterator it, | 824 | GNUNET_CONTAINER_PeerMapIterator it, |
755 | void *it_cls) | 825 | void *it_cls) |
756 | { | 826 | { |
757 | int count; | 827 | int count; |
758 | union MapEntry me; | 828 | union MapEntry me; |
759 | 829 | union MapEntry *ce; | |
830 | |||
831 | ce = &map->next_cache[map->next_cache_off]; | ||
832 | GNUNET_assert (++map->next_cache_off < NEXT_CACHE_SIZE); | ||
760 | count = 0; | 833 | count = 0; |
761 | me = map->map[idx_of (map, key)]; | 834 | me = map->map[idx_of (map, key)]; |
762 | if (map->use_small_entries) | 835 | if (map->use_small_entries) |
763 | { | 836 | { |
764 | struct SmallMapEntry *sme; | 837 | struct SmallMapEntry *sme; |
765 | struct SmallMapEntry *nxt; | ||
766 | 838 | ||
767 | nxt = me.sme; | 839 | ce->sme = me.sme; |
768 | while (NULL != (sme = nxt)) | 840 | while (NULL != (sme = ce->sme)) |
769 | { | 841 | { |
770 | nxt = sme->next; | 842 | ce->sme = sme->next; |
771 | if (0 != memcmp (key, sme->key, sizeof (struct GNUNET_PeerIdentity))) | 843 | if (0 != memcmp (key, |
844 | sme->key, | ||
845 | sizeof (struct GNUNET_PeerIdentity))) | ||
772 | continue; | 846 | continue; |
773 | if ((it != NULL) && (GNUNET_OK != it (it_cls, key, sme->value))) | 847 | if ( (NULL != it) && |
848 | (GNUNET_OK != it (it_cls, | ||
849 | key, | ||
850 | sme->value))) | ||
851 | { | ||
852 | GNUNET_assert (--map->next_cache_off < NEXT_CACHE_SIZE); | ||
774 | return GNUNET_SYSERR; | 853 | return GNUNET_SYSERR; |
854 | } | ||
775 | count++; | 855 | count++; |
776 | } | 856 | } |
777 | } | 857 | } |
778 | else | 858 | else |
779 | { | 859 | { |
780 | struct BigMapEntry *bme; | 860 | struct BigMapEntry *bme; |
781 | struct BigMapEntry *nxt; | ||
782 | 861 | ||
783 | nxt = me.bme; | 862 | ce->bme = me.bme; |
784 | while (NULL != (bme = nxt)) | 863 | while (NULL != (bme = ce->bme)) |
785 | { | 864 | { |
786 | nxt = bme->next; | 865 | ce->bme = bme->next; |
787 | if (0 != memcmp (key, &bme->key, sizeof (struct GNUNET_PeerIdentity))) | 866 | if (0 != memcmp (key, |
867 | &bme->key, | ||
868 | sizeof (struct GNUNET_PeerIdentity))) | ||
788 | continue; | 869 | continue; |
789 | if ((it != NULL) && (GNUNET_OK != it (it_cls, key, bme->value))) | 870 | if ( (NULL != it) && |
871 | (GNUNET_OK != it (it_cls, | ||
872 | key, | ||
873 | bme->value))) | ||
874 | { | ||
875 | GNUNET_assert (--map->next_cache_off < NEXT_CACHE_SIZE); | ||
790 | return GNUNET_SYSERR; | 876 | return GNUNET_SYSERR; |
877 | } | ||
791 | count++; | 878 | count++; |
792 | } | 879 | } |
793 | } | 880 | } |
881 | GNUNET_assert (--map->next_cache_off < NEXT_CACHE_SIZE); | ||
794 | return count; | 882 | return count; |
795 | } | 883 | } |
796 | 884 | ||
@@ -812,16 +900,15 @@ GNUNET_CONTAINER_multipeermap_get_random (const struct GNUNET_CONTAINER_MultiPee | |||
812 | void *it_cls) | 900 | void *it_cls) |
813 | { | 901 | { |
814 | unsigned int off; | 902 | unsigned int off; |
815 | unsigned int idx; | ||
816 | union MapEntry me; | 903 | union MapEntry me; |
817 | 904 | ||
818 | if (0 == map->size) | 905 | if (0 == map->size) |
819 | return 0; | 906 | return 0; |
820 | if (NULL == it) | 907 | if (NULL == it) |
821 | return 1; | 908 | return 1; |
822 | off = GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_NONCE, | 909 | off = GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_NONCE, |
823 | map->size); | 910 | map->size); |
824 | for (idx = 0; idx < map->map_length; idx++) | 911 | for (unsigned int idx = 0; idx < map->map_length; idx++) |
825 | { | 912 | { |
826 | me = map->map[idx]; | 913 | me = map->map[idx]; |
827 | if (map->use_small_entries) | 914 | if (map->use_small_entries) |
@@ -856,9 +943,10 @@ GNUNET_CONTAINER_multipeermap_get_random (const struct GNUNET_CONTAINER_MultiPee | |||
856 | if (0 == off) | 943 | if (0 == off) |
857 | { | 944 | { |
858 | if (GNUNET_OK != it (it_cls, | 945 | if (GNUNET_OK != it (it_cls, |
859 | &bme->key, bme->value)) | 946 | &bme->key, |
860 | return GNUNET_SYSERR; | 947 | bme->value)) |
861 | return 1; | 948 | return GNUNET_SYSERR; |
949 | return 1; | ||
862 | } | 950 | } |
863 | off--; | 951 | off--; |
864 | } | 952 | } |