diff options
Diffstat (limited to 'src/util/container_multihashmap.c')
-rw-r--r-- | src/util/container_multihashmap.c | 885 |
1 files changed, 439 insertions, 446 deletions
diff --git a/src/util/container_multihashmap.c b/src/util/container_multihashmap.c index bcf6dccf0..62e5311d8 100644 --- a/src/util/container_multihashmap.c +++ b/src/util/container_multihashmap.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_multihashmap.c | 21 | * @file util/container_multihashmap.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_container_lib.h" | 27 | #include "gnunet_container_lib.h" |
28 | 28 | ||
29 | #define LOG(kind, ...) \ | 29 | #define LOG(kind, ...) \ |
30 | GNUNET_log_from (kind, "util-container-multihashmap", __VA_ARGS__) | 30 | GNUNET_log_from(kind, "util-container-multihashmap", __VA_ARGS__) |
31 | 31 | ||
32 | /** | 32 | /** |
33 | * Maximum recursion depth for callbacks of | 33 | * Maximum recursion depth for callbacks of |
@@ -41,9 +41,7 @@ | |||
41 | /** | 41 | /** |
42 | * An entry in the hash map with the full key. | 42 | * An entry in the hash map with the full key. |
43 | */ | 43 | */ |
44 | struct BigMapEntry | 44 | struct BigMapEntry { |
45 | { | ||
46 | |||
47 | /** | 45 | /** |
48 | * Value of the entry. | 46 | * Value of the entry. |
49 | */ | 47 | */ |
@@ -64,9 +62,7 @@ struct BigMapEntry | |||
64 | /** | 62 | /** |
65 | * 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. |
66 | */ | 64 | */ |
67 | struct SmallMapEntry | 65 | struct SmallMapEntry { |
68 | { | ||
69 | |||
70 | /** | 66 | /** |
71 | * Value of the entry. | 67 | * Value of the entry. |
72 | */ | 68 | */ |
@@ -87,8 +83,7 @@ struct SmallMapEntry | |||
87 | /** | 83 | /** |
88 | * Entry in the map. | 84 | * Entry in the map. |
89 | */ | 85 | */ |
90 | union MapEntry | 86 | union MapEntry { |
91 | { | ||
92 | /** | 87 | /** |
93 | * Variant used if map entries only contain a pointer to the key. | 88 | * Variant used if map entries only contain a pointer to the key. |
94 | */ | 89 | */ |
@@ -104,8 +99,7 @@ union MapEntry | |||
104 | /** | 99 | /** |
105 | * Internal representation of the hash map. | 100 | * Internal representation of the hash map. |
106 | */ | 101 | */ |
107 | struct GNUNET_CONTAINER_MultiHashMap | 102 | struct GNUNET_CONTAINER_MultiHashMap { |
108 | { | ||
109 | /** | 103 | /** |
110 | * All of our buckets. | 104 | * All of our buckets. |
111 | */ | 105 | */ |
@@ -152,8 +146,7 @@ struct GNUNET_CONTAINER_MultiHashMap | |||
152 | * Cursor into a multihashmap. | 146 | * Cursor into a multihashmap. |
153 | * Allows to enumerate elements asynchronously. | 147 | * Allows to enumerate elements asynchronously. |
154 | */ | 148 | */ |
155 | struct GNUNET_CONTAINER_MultiHashMapIterator | 149 | struct GNUNET_CONTAINER_MultiHashMapIterator { |
156 | { | ||
157 | /** | 150 | /** |
158 | * Position in the bucket @e idx | 151 | * Position in the bucket @e idx |
159 | */ | 152 | */ |
@@ -193,34 +186,34 @@ struct GNUNET_CONTAINER_MultiHashMapIterator | |||
193 | * @return NULL on error | 186 | * @return NULL on error |
194 | */ | 187 | */ |
195 | struct GNUNET_CONTAINER_MultiHashMap * | 188 | struct GNUNET_CONTAINER_MultiHashMap * |
196 | GNUNET_CONTAINER_multihashmap_create (unsigned int len, int do_not_copy_keys) | 189 | GNUNET_CONTAINER_multihashmap_create(unsigned int len, int do_not_copy_keys) |
197 | { | 190 | { |
198 | struct GNUNET_CONTAINER_MultiHashMap *hm; | 191 | struct GNUNET_CONTAINER_MultiHashMap *hm; |
199 | 192 | ||
200 | GNUNET_assert (len > 0); | 193 | GNUNET_assert(len > 0); |
201 | hm = GNUNET_new (struct GNUNET_CONTAINER_MultiHashMap); | 194 | hm = GNUNET_new(struct GNUNET_CONTAINER_MultiHashMap); |
202 | if (len * sizeof (union MapEntry) > GNUNET_MAX_MALLOC_CHECKED) | 195 | if (len * sizeof(union MapEntry) > GNUNET_MAX_MALLOC_CHECKED) |
203 | { | ||
204 | size_t s; | ||
205 | /* application *explicitly* requested very large map, hopefully | ||
206 | it checks the return value... */ | ||
207 | s = len * sizeof (union MapEntry); | ||
208 | if ((s / sizeof (union MapEntry)) != len) | ||
209 | return NULL; /* integer overflow on multiplication */ | ||
210 | if (NULL == (hm->map = GNUNET_malloc_large (s))) | ||
211 | { | 196 | { |
212 | /* out of memory */ | 197 | size_t s; |
213 | GNUNET_log (GNUNET_ERROR_TYPE_WARNING, | 198 | /* application *explicitly* requested very large map, hopefully |
214 | "Out of memory allocating large hash map (%u entries)\n", | 199 | it checks the return value... */ |
215 | len); | 200 | s = len * sizeof(union MapEntry); |
216 | GNUNET_free (hm); | 201 | if ((s / sizeof(union MapEntry)) != len) |
217 | return NULL; | 202 | return NULL; /* integer overflow on multiplication */ |
203 | if (NULL == (hm->map = GNUNET_malloc_large(s))) | ||
204 | { | ||
205 | /* out of memory */ | ||
206 | GNUNET_log(GNUNET_ERROR_TYPE_WARNING, | ||
207 | "Out of memory allocating large hash map (%u entries)\n", | ||
208 | len); | ||
209 | GNUNET_free(hm); | ||
210 | return NULL; | ||
211 | } | ||
218 | } | 212 | } |
219 | } | ||
220 | else | 213 | else |
221 | { | 214 | { |
222 | hm->map = GNUNET_new_array (len, union MapEntry); | 215 | hm->map = GNUNET_new_array(len, union MapEntry); |
223 | } | 216 | } |
224 | hm->map_length = len; | 217 | hm->map_length = len; |
225 | hm->use_small_entries = do_not_copy_keys; | 218 | hm->use_small_entries = do_not_copy_keys; |
226 | return hm; | 219 | return hm; |
@@ -234,44 +227,44 @@ GNUNET_CONTAINER_multihashmap_create (unsigned int len, int do_not_copy_keys) | |||
234 | * @param map the map | 227 | * @param map the map |
235 | */ | 228 | */ |
236 | void | 229 | void |
237 | GNUNET_CONTAINER_multihashmap_destroy ( | 230 | GNUNET_CONTAINER_multihashmap_destroy( |
238 | struct GNUNET_CONTAINER_MultiHashMap *map) | 231 | struct GNUNET_CONTAINER_MultiHashMap *map) |
239 | { | 232 | { |
240 | GNUNET_assert (0 == map->next_cache_off); | 233 | GNUNET_assert(0 == map->next_cache_off); |
241 | for (unsigned int i = 0; i < map->map_length; i++) | 234 | for (unsigned int i = 0; i < map->map_length; i++) |
242 | { | ||
243 | union MapEntry me; | ||
244 | |||
245 | me = map->map[i]; | ||
246 | if (map->use_small_entries) | ||
247 | { | 235 | { |
248 | struct SmallMapEntry *sme; | 236 | union MapEntry me; |
249 | struct SmallMapEntry *nxt; | 237 | |
250 | 238 | me = map->map[i]; | |
251 | nxt = me.sme; | 239 | if (map->use_small_entries) |
252 | while (NULL != (sme = nxt)) | 240 | { |
253 | { | 241 | struct SmallMapEntry *sme; |
254 | nxt = sme->next; | 242 | struct SmallMapEntry *nxt; |
255 | GNUNET_free (sme); | 243 | |
256 | } | 244 | nxt = me.sme; |
257 | me.sme = NULL; | 245 | while (NULL != (sme = nxt)) |
258 | } | 246 | { |
259 | else | 247 | nxt = sme->next; |
260 | { | 248 | GNUNET_free(sme); |
261 | struct BigMapEntry *bme; | 249 | } |
262 | struct BigMapEntry *nxt; | 250 | me.sme = NULL; |
263 | 251 | } | |
264 | nxt = me.bme; | 252 | else |
265 | while (NULL != (bme = nxt)) | 253 | { |
266 | { | 254 | struct BigMapEntry *bme; |
267 | nxt = bme->next; | 255 | struct BigMapEntry *nxt; |
268 | GNUNET_free (bme); | 256 | |
269 | } | 257 | nxt = me.bme; |
270 | me.bme = NULL; | 258 | while (NULL != (bme = nxt)) |
259 | { | ||
260 | nxt = bme->next; | ||
261 | GNUNET_free(bme); | ||
262 | } | ||
263 | me.bme = NULL; | ||
264 | } | ||
271 | } | 265 | } |
272 | } | 266 | GNUNET_free(map->map); |
273 | GNUNET_free (map->map); | 267 | GNUNET_free(map); |
274 | GNUNET_free (map); | ||
275 | } | 268 | } |
276 | 269 | ||
277 | 270 | ||
@@ -283,11 +276,11 @@ GNUNET_CONTAINER_multihashmap_destroy ( | |||
283 | * @return offset into the "map" array of "map" | 276 | * @return offset into the "map" array of "map" |
284 | */ | 277 | */ |
285 | static unsigned int | 278 | static unsigned int |
286 | idx_of (const struct GNUNET_CONTAINER_MultiHashMap *map, | 279 | idx_of(const struct GNUNET_CONTAINER_MultiHashMap *map, |
287 | const struct GNUNET_HashCode *key) | 280 | const struct GNUNET_HashCode *key) |
288 | { | 281 | { |
289 | GNUNET_assert (map != NULL); | 282 | GNUNET_assert(map != NULL); |
290 | return (*(unsigned int *) key) % map->map_length; | 283 | return (*(unsigned int *)key) % map->map_length; |
291 | } | 284 | } |
292 | 285 | ||
293 | 286 | ||
@@ -298,7 +291,7 @@ idx_of (const struct GNUNET_CONTAINER_MultiHashMap *map, | |||
298 | * @return the number of key value pairs | 291 | * @return the number of key value pairs |
299 | */ | 292 | */ |
300 | unsigned int | 293 | unsigned int |
301 | GNUNET_CONTAINER_multihashmap_size ( | 294 | GNUNET_CONTAINER_multihashmap_size( |
302 | const struct GNUNET_CONTAINER_MultiHashMap *map) | 295 | const struct GNUNET_CONTAINER_MultiHashMap *map) |
303 | { | 296 | { |
304 | return map->size; | 297 | return map->size; |
@@ -316,29 +309,29 @@ GNUNET_CONTAINER_multihashmap_size ( | |||
316 | * key-value pairs with value NULL | 309 | * key-value pairs with value NULL |
317 | */ | 310 | */ |
318 | void * | 311 | void * |
319 | GNUNET_CONTAINER_multihashmap_get ( | 312 | GNUNET_CONTAINER_multihashmap_get( |
320 | const struct GNUNET_CONTAINER_MultiHashMap *map, | 313 | const struct GNUNET_CONTAINER_MultiHashMap *map, |
321 | const struct GNUNET_HashCode *key) | 314 | const struct GNUNET_HashCode *key) |
322 | { | 315 | { |
323 | union MapEntry me; | 316 | union MapEntry me; |
324 | 317 | ||
325 | me = map->map[idx_of (map, key)]; | 318 | me = map->map[idx_of(map, key)]; |
326 | if (map->use_small_entries) | 319 | if (map->use_small_entries) |
327 | { | 320 | { |
328 | struct SmallMapEntry *sme; | 321 | struct SmallMapEntry *sme; |
329 | 322 | ||
330 | for (sme = me.sme; NULL != sme; sme = sme->next) | 323 | for (sme = me.sme; NULL != sme; sme = sme->next) |
331 | if (0 == GNUNET_memcmp (key, sme->key)) | 324 | if (0 == GNUNET_memcmp(key, sme->key)) |
332 | return sme->value; | 325 | return sme->value; |
333 | } | 326 | } |
334 | else | 327 | else |
335 | { | 328 | { |
336 | struct BigMapEntry *bme; | 329 | struct BigMapEntry *bme; |
337 | 330 | ||
338 | for (bme = me.bme; NULL != bme; bme = bme->next) | 331 | for (bme = me.bme; NULL != bme; bme = bme->next) |
339 | if (0 == GNUNET_memcmp (key, &bme->key)) | 332 | if (0 == GNUNET_memcmp(key, &bme->key)) |
340 | return bme->value; | 333 | return bme->value; |
341 | } | 334 | } |
342 | return NULL; | 335 | return NULL; |
343 | } | 336 | } |
344 | 337 | ||
@@ -353,7 +346,7 @@ GNUNET_CONTAINER_multihashmap_get ( | |||
353 | * #GNUNET_SYSERR if it aborted iteration | 346 | * #GNUNET_SYSERR if it aborted iteration |
354 | */ | 347 | */ |
355 | int | 348 | int |
356 | GNUNET_CONTAINER_multihashmap_iterate ( | 349 | GNUNET_CONTAINER_multihashmap_iterate( |
357 | struct GNUNET_CONTAINER_MultiHashMap *map, | 350 | struct GNUNET_CONTAINER_MultiHashMap *map, |
358 | GNUNET_CONTAINER_MulitHashMapIteratorCallback it, | 351 | GNUNET_CONTAINER_MulitHashMapIteratorCallback it, |
359 | void *it_cls) | 352 | void *it_cls) |
@@ -363,54 +356,54 @@ GNUNET_CONTAINER_multihashmap_iterate ( | |||
363 | union MapEntry *ce; | 356 | union MapEntry *ce; |
364 | struct GNUNET_HashCode kc; | 357 | struct GNUNET_HashCode kc; |
365 | 358 | ||
366 | GNUNET_assert (NULL != map); | 359 | GNUNET_assert(NULL != map); |
367 | ce = &map->next_cache[map->next_cache_off]; | 360 | ce = &map->next_cache[map->next_cache_off]; |
368 | GNUNET_assert (++map->next_cache_off < NEXT_CACHE_SIZE); | 361 | GNUNET_assert(++map->next_cache_off < NEXT_CACHE_SIZE); |
369 | count = 0; | 362 | count = 0; |
370 | for (unsigned i = 0; i < map->map_length; i++) | 363 | for (unsigned i = 0; i < map->map_length; i++) |
371 | { | ||
372 | me = map->map[i]; | ||
373 | if (map->use_small_entries) | ||
374 | { | 364 | { |
375 | struct SmallMapEntry *sme; | 365 | me = map->map[i]; |
376 | 366 | if (map->use_small_entries) | |
377 | ce->sme = me.sme; | ||
378 | while (NULL != (sme = ce->sme)) | ||
379 | { | ||
380 | ce->sme = sme->next; | ||
381 | if (NULL != it) | ||
382 | { | 367 | { |
383 | if (GNUNET_OK != it (it_cls, sme->key, sme->value)) | 368 | struct SmallMapEntry *sme; |
384 | { | 369 | |
385 | GNUNET_assert (--map->next_cache_off < NEXT_CACHE_SIZE); | 370 | ce->sme = me.sme; |
386 | return GNUNET_SYSERR; | 371 | while (NULL != (sme = ce->sme)) |
387 | } | 372 | { |
373 | ce->sme = sme->next; | ||
374 | if (NULL != it) | ||
375 | { | ||
376 | if (GNUNET_OK != it(it_cls, sme->key, sme->value)) | ||
377 | { | ||
378 | GNUNET_assert(--map->next_cache_off < NEXT_CACHE_SIZE); | ||
379 | return GNUNET_SYSERR; | ||
380 | } | ||
381 | } | ||
382 | count++; | ||
383 | } | ||
388 | } | 384 | } |
389 | count++; | 385 | else |
390 | } | ||
391 | } | ||
392 | else | ||
393 | { | ||
394 | struct BigMapEntry *bme; | ||
395 | |||
396 | ce->bme = me.bme; | ||
397 | while (NULL != (bme = ce->bme)) | ||
398 | { | ||
399 | ce->bme = bme->next; | ||
400 | if (NULL != it) | ||
401 | { | 386 | { |
402 | kc = bme->key; | 387 | struct BigMapEntry *bme; |
403 | if (GNUNET_OK != it (it_cls, &kc, bme->value)) | 388 | |
404 | { | 389 | ce->bme = me.bme; |
405 | GNUNET_assert (--map->next_cache_off < NEXT_CACHE_SIZE); | 390 | while (NULL != (bme = ce->bme)) |
406 | return GNUNET_SYSERR; | 391 | { |
407 | } | 392 | ce->bme = bme->next; |
393 | if (NULL != it) | ||
394 | { | ||
395 | kc = bme->key; | ||
396 | if (GNUNET_OK != it(it_cls, &kc, bme->value)) | ||
397 | { | ||
398 | GNUNET_assert(--map->next_cache_off < NEXT_CACHE_SIZE); | ||
399 | return GNUNET_SYSERR; | ||
400 | } | ||
401 | } | ||
402 | count++; | ||
403 | } | ||
408 | } | 404 | } |
409 | count++; | ||
410 | } | ||
411 | } | 405 | } |
412 | } | 406 | GNUNET_assert(--map->next_cache_off < NEXT_CACHE_SIZE); |
413 | GNUNET_assert (--map->next_cache_off < NEXT_CACHE_SIZE); | ||
414 | return count; | 407 | return count; |
415 | } | 408 | } |
416 | 409 | ||
@@ -423,8 +416,8 @@ GNUNET_CONTAINER_multihashmap_iterate ( | |||
423 | * @param bme the entry that is about to be free'd | 416 | * @param bme the entry that is about to be free'd |
424 | */ | 417 | */ |
425 | static void | 418 | static void |
426 | update_next_cache_bme (struct GNUNET_CONTAINER_MultiHashMap *map, | 419 | update_next_cache_bme(struct GNUNET_CONTAINER_MultiHashMap *map, |
427 | const struct BigMapEntry *bme) | 420 | const struct BigMapEntry *bme) |
428 | { | 421 | { |
429 | for (unsigned int i = 0; i < map->next_cache_off; i++) | 422 | for (unsigned int i = 0; i < map->next_cache_off; i++) |
430 | if (map->next_cache[i].bme == bme) | 423 | if (map->next_cache[i].bme == bme) |
@@ -440,8 +433,8 @@ update_next_cache_bme (struct GNUNET_CONTAINER_MultiHashMap *map, | |||
440 | * @param sme the entry that is about to be free'd | 433 | * @param sme the entry that is about to be free'd |
441 | */ | 434 | */ |
442 | static void | 435 | static void |
443 | update_next_cache_sme (struct GNUNET_CONTAINER_MultiHashMap *map, | 436 | update_next_cache_sme(struct GNUNET_CONTAINER_MultiHashMap *map, |
444 | const struct SmallMapEntry *sme) | 437 | const struct SmallMapEntry *sme) |
445 | { | 438 | { |
446 | for (unsigned int i = 0; i < map->next_cache_off; i++) | 439 | for (unsigned int i = 0; i < map->next_cache_off; i++) |
447 | if (map->next_cache[i].sme == sme) | 440 | if (map->next_cache[i].sme == sme) |
@@ -461,59 +454,59 @@ update_next_cache_sme (struct GNUNET_CONTAINER_MultiHashMap *map, | |||
461 | * is not in the map | 454 | * is not in the map |
462 | */ | 455 | */ |
463 | int | 456 | int |
464 | GNUNET_CONTAINER_multihashmap_remove (struct GNUNET_CONTAINER_MultiHashMap *map, | 457 | GNUNET_CONTAINER_multihashmap_remove(struct GNUNET_CONTAINER_MultiHashMap *map, |
465 | const struct GNUNET_HashCode *key, | 458 | const struct GNUNET_HashCode *key, |
466 | const void *value) | 459 | const void *value) |
467 | { | 460 | { |
468 | union MapEntry me; | 461 | union MapEntry me; |
469 | unsigned int i; | 462 | unsigned int i; |
470 | 463 | ||
471 | map->modification_counter++; | 464 | map->modification_counter++; |
472 | 465 | ||
473 | i = idx_of (map, key); | 466 | i = idx_of(map, key); |
474 | me = map->map[i]; | 467 | me = map->map[i]; |
475 | if (map->use_small_entries) | 468 | if (map->use_small_entries) |
476 | { | ||
477 | struct SmallMapEntry *p; | ||
478 | |||
479 | p = NULL; | ||
480 | for (struct SmallMapEntry *sme = me.sme; NULL != sme; sme = sme->next) | ||
481 | { | 469 | { |
482 | if ((0 == GNUNET_memcmp (key, sme->key)) && (value == sme->value)) | 470 | struct SmallMapEntry *p; |
483 | { | 471 | |
484 | if (NULL == p) | 472 | p = NULL; |
485 | map->map[i].sme = sme->next; | 473 | for (struct SmallMapEntry *sme = me.sme; NULL != sme; sme = sme->next) |
486 | else | 474 | { |
487 | p->next = sme->next; | 475 | if ((0 == GNUNET_memcmp(key, sme->key)) && (value == sme->value)) |
488 | update_next_cache_sme (map, sme); | 476 | { |
489 | GNUNET_free (sme); | 477 | if (NULL == p) |
490 | map->size--; | 478 | map->map[i].sme = sme->next; |
491 | return GNUNET_YES; | 479 | else |
492 | } | 480 | p->next = sme->next; |
493 | p = sme; | 481 | update_next_cache_sme(map, sme); |
482 | GNUNET_free(sme); | ||
483 | map->size--; | ||
484 | return GNUNET_YES; | ||
485 | } | ||
486 | p = sme; | ||
487 | } | ||
494 | } | 488 | } |
495 | } | ||
496 | else | 489 | else |
497 | { | ||
498 | struct BigMapEntry *p; | ||
499 | |||
500 | p = NULL; | ||
501 | for (struct BigMapEntry *bme = me.bme; NULL != bme; bme = bme->next) | ||
502 | { | 490 | { |
503 | if ((0 == GNUNET_memcmp (key, &bme->key)) && (value == bme->value)) | 491 | struct BigMapEntry *p; |
504 | { | 492 | |
505 | if (NULL == p) | 493 | p = NULL; |
506 | map->map[i].bme = bme->next; | 494 | for (struct BigMapEntry *bme = me.bme; NULL != bme; bme = bme->next) |
507 | else | 495 | { |
508 | p->next = bme->next; | 496 | if ((0 == GNUNET_memcmp(key, &bme->key)) && (value == bme->value)) |
509 | update_next_cache_bme (map, bme); | 497 | { |
510 | GNUNET_free (bme); | 498 | if (NULL == p) |
511 | map->size--; | 499 | map->map[i].bme = bme->next; |
512 | return GNUNET_YES; | 500 | else |
513 | } | 501 | p->next = bme->next; |
514 | p = bme; | 502 | update_next_cache_bme(map, bme); |
503 | GNUNET_free(bme); | ||
504 | map->size--; | ||
505 | return GNUNET_YES; | ||
506 | } | ||
507 | p = bme; | ||
508 | } | ||
515 | } | 509 | } |
516 | } | ||
517 | return GNUNET_NO; | 510 | return GNUNET_NO; |
518 | } | 511 | } |
519 | 512 | ||
@@ -527,7 +520,7 @@ GNUNET_CONTAINER_multihashmap_remove (struct GNUNET_CONTAINER_MultiHashMap *map, | |||
527 | * @return number of values removed | 520 | * @return number of values removed |
528 | */ | 521 | */ |
529 | int | 522 | int |
530 | GNUNET_CONTAINER_multihashmap_remove_all ( | 523 | GNUNET_CONTAINER_multihashmap_remove_all( |
531 | struct GNUNET_CONTAINER_MultiHashMap *map, | 524 | struct GNUNET_CONTAINER_MultiHashMap *map, |
532 | const struct GNUNET_HashCode *key) | 525 | const struct GNUNET_HashCode *key) |
533 | { | 526 | { |
@@ -538,70 +531,70 @@ GNUNET_CONTAINER_multihashmap_remove_all ( | |||
538 | map->modification_counter++; | 531 | map->modification_counter++; |
539 | 532 | ||
540 | ret = 0; | 533 | ret = 0; |
541 | i = idx_of (map, key); | 534 | i = idx_of(map, key); |
542 | me = map->map[i]; | 535 | me = map->map[i]; |
543 | if (map->use_small_entries) | 536 | if (map->use_small_entries) |
544 | { | ||
545 | struct SmallMapEntry *sme; | ||
546 | struct SmallMapEntry *p; | ||
547 | |||
548 | p = NULL; | ||
549 | sme = me.sme; | ||
550 | while (NULL != sme) | ||
551 | { | 537 | { |
552 | if (0 == GNUNET_memcmp (key, sme->key)) | 538 | struct SmallMapEntry *sme; |
553 | { | 539 | struct SmallMapEntry *p; |
554 | if (NULL == p) | 540 | |
555 | map->map[i].sme = sme->next; | 541 | p = NULL; |
556 | else | 542 | sme = me.sme; |
557 | p->next = sme->next; | 543 | while (NULL != sme) |
558 | update_next_cache_sme (map, sme); | 544 | { |
559 | GNUNET_free (sme); | 545 | if (0 == GNUNET_memcmp(key, sme->key)) |
560 | map->size--; | 546 | { |
561 | if (NULL == p) | 547 | if (NULL == p) |
562 | sme = map->map[i].sme; | 548 | map->map[i].sme = sme->next; |
563 | else | 549 | else |
564 | sme = p->next; | 550 | p->next = sme->next; |
565 | ret++; | 551 | update_next_cache_sme(map, sme); |
566 | } | 552 | GNUNET_free(sme); |
567 | else | 553 | map->size--; |
568 | { | 554 | if (NULL == p) |
569 | p = sme; | 555 | sme = map->map[i].sme; |
570 | sme = sme->next; | 556 | else |
571 | } | 557 | sme = p->next; |
558 | ret++; | ||
559 | } | ||
560 | else | ||
561 | { | ||
562 | p = sme; | ||
563 | sme = sme->next; | ||
564 | } | ||
565 | } | ||
572 | } | 566 | } |
573 | } | ||
574 | else | 567 | else |
575 | { | ||
576 | struct BigMapEntry *bme; | ||
577 | struct BigMapEntry *p; | ||
578 | |||
579 | p = NULL; | ||
580 | bme = me.bme; | ||
581 | while (NULL != bme) | ||
582 | { | 568 | { |
583 | if (0 == GNUNET_memcmp (key, &bme->key)) | 569 | struct BigMapEntry *bme; |
584 | { | 570 | struct BigMapEntry *p; |
585 | if (NULL == p) | 571 | |
586 | map->map[i].bme = bme->next; | 572 | p = NULL; |
587 | else | 573 | bme = me.bme; |
588 | p->next = bme->next; | 574 | while (NULL != bme) |
589 | update_next_cache_bme (map, bme); | 575 | { |
590 | GNUNET_free (bme); | 576 | if (0 == GNUNET_memcmp(key, &bme->key)) |
591 | map->size--; | 577 | { |
592 | if (NULL == p) | 578 | if (NULL == p) |
593 | bme = map->map[i].bme; | 579 | map->map[i].bme = bme->next; |
594 | else | 580 | else |
595 | bme = p->next; | 581 | p->next = bme->next; |
596 | ret++; | 582 | update_next_cache_bme(map, bme); |
597 | } | 583 | GNUNET_free(bme); |
598 | else | 584 | map->size--; |
599 | { | 585 | if (NULL == p) |
600 | p = bme; | 586 | bme = map->map[i].bme; |
601 | bme = bme->next; | 587 | else |
602 | } | 588 | bme = p->next; |
589 | ret++; | ||
590 | } | ||
591 | else | ||
592 | { | ||
593 | p = bme; | ||
594 | bme = bme->next; | ||
595 | } | ||
596 | } | ||
603 | } | 597 | } |
604 | } | ||
605 | return ret; | 598 | return ret; |
606 | } | 599 | } |
607 | 600 | ||
@@ -615,12 +608,12 @@ GNUNET_CONTAINER_multihashmap_remove_all ( | |||
615 | * @return #GNUNET_OK (continue to iterate) | 608 | * @return #GNUNET_OK (continue to iterate) |
616 | */ | 609 | */ |
617 | static int | 610 | static int |
618 | remove_all (void *cls, const struct GNUNET_HashCode *key, void *value) | 611 | remove_all(void *cls, const struct GNUNET_HashCode *key, void *value) |
619 | { | 612 | { |
620 | struct GNUNET_CONTAINER_MultiHashMap *map = cls; | 613 | struct GNUNET_CONTAINER_MultiHashMap *map = cls; |
621 | 614 | ||
622 | GNUNET_assert (GNUNET_YES == | 615 | GNUNET_assert(GNUNET_YES == |
623 | GNUNET_CONTAINER_multihashmap_remove (map, key, value)); | 616 | GNUNET_CONTAINER_multihashmap_remove(map, key, value)); |
624 | return GNUNET_OK; | 617 | return GNUNET_OK; |
625 | } | 618 | } |
626 | 619 | ||
@@ -634,12 +627,12 @@ remove_all (void *cls, const struct GNUNET_HashCode *key, void *value) | |||
634 | * @return number of values removed | 627 | * @return number of values removed |
635 | */ | 628 | */ |
636 | unsigned int | 629 | unsigned int |
637 | GNUNET_CONTAINER_multihashmap_clear (struct GNUNET_CONTAINER_MultiHashMap *map) | 630 | GNUNET_CONTAINER_multihashmap_clear(struct GNUNET_CONTAINER_MultiHashMap *map) |
638 | { | 631 | { |
639 | unsigned int ret; | 632 | unsigned int ret; |
640 | 633 | ||
641 | ret = map->size; | 634 | ret = map->size; |
642 | GNUNET_CONTAINER_multihashmap_iterate (map, &remove_all, map); | 635 | GNUNET_CONTAINER_multihashmap_iterate(map, &remove_all, map); |
643 | return ret; | 636 | return ret; |
644 | } | 637 | } |
645 | 638 | ||
@@ -654,29 +647,29 @@ GNUNET_CONTAINER_multihashmap_clear (struct GNUNET_CONTAINER_MultiHashMap *map) | |||
654 | * #GNUNET_NO if not | 647 | * #GNUNET_NO if not |
655 | */ | 648 | */ |
656 | int | 649 | int |
657 | GNUNET_CONTAINER_multihashmap_contains ( | 650 | GNUNET_CONTAINER_multihashmap_contains( |
658 | const struct GNUNET_CONTAINER_MultiHashMap *map, | 651 | const struct GNUNET_CONTAINER_MultiHashMap *map, |
659 | const struct GNUNET_HashCode *key) | 652 | const struct GNUNET_HashCode *key) |
660 | { | 653 | { |
661 | union MapEntry me; | 654 | union MapEntry me; |
662 | 655 | ||
663 | me = map->map[idx_of (map, key)]; | 656 | me = map->map[idx_of(map, key)]; |
664 | if (map->use_small_entries) | 657 | if (map->use_small_entries) |
665 | { | 658 | { |
666 | struct SmallMapEntry *sme; | 659 | struct SmallMapEntry *sme; |
667 | 660 | ||
668 | for (sme = me.sme; NULL != sme; sme = sme->next) | 661 | for (sme = me.sme; NULL != sme; sme = sme->next) |
669 | if (0 == GNUNET_memcmp (key, sme->key)) | 662 | if (0 == GNUNET_memcmp(key, sme->key)) |
670 | return GNUNET_YES; | 663 | return GNUNET_YES; |
671 | } | 664 | } |
672 | else | 665 | else |
673 | { | 666 | { |
674 | struct BigMapEntry *bme; | 667 | struct BigMapEntry *bme; |
675 | 668 | ||
676 | for (bme = me.bme; NULL != bme; bme = bme->next) | 669 | for (bme = me.bme; NULL != bme; bme = bme->next) |
677 | if (0 == GNUNET_memcmp (key, &bme->key)) | 670 | if (0 == GNUNET_memcmp(key, &bme->key)) |
678 | return GNUNET_YES; | 671 | return GNUNET_YES; |
679 | } | 672 | } |
680 | return GNUNET_NO; | 673 | return GNUNET_NO; |
681 | } | 674 | } |
682 | 675 | ||
@@ -692,30 +685,30 @@ GNUNET_CONTAINER_multihashmap_contains ( | |||
692 | * #GNUNET_NO if not | 685 | * #GNUNET_NO if not |
693 | */ | 686 | */ |
694 | int | 687 | int |
695 | GNUNET_CONTAINER_multihashmap_contains_value ( | 688 | GNUNET_CONTAINER_multihashmap_contains_value( |
696 | const struct GNUNET_CONTAINER_MultiHashMap *map, | 689 | const struct GNUNET_CONTAINER_MultiHashMap *map, |
697 | const struct GNUNET_HashCode *key, | 690 | const struct GNUNET_HashCode *key, |
698 | const void *value) | 691 | const void *value) |
699 | { | 692 | { |
700 | union MapEntry me; | 693 | union MapEntry me; |
701 | 694 | ||
702 | me = map->map[idx_of (map, key)]; | 695 | me = map->map[idx_of(map, key)]; |
703 | if (map->use_small_entries) | 696 | if (map->use_small_entries) |
704 | { | 697 | { |
705 | struct SmallMapEntry *sme; | 698 | struct SmallMapEntry *sme; |
706 | 699 | ||
707 | for (sme = me.sme; NULL != sme; sme = sme->next) | 700 | for (sme = me.sme; NULL != sme; sme = sme->next) |
708 | if ((0 == GNUNET_memcmp (key, sme->key)) && (sme->value == value)) | 701 | if ((0 == GNUNET_memcmp(key, sme->key)) && (sme->value == value)) |
709 | return GNUNET_YES; | 702 | return GNUNET_YES; |
710 | } | 703 | } |
711 | else | 704 | else |
712 | { | 705 | { |
713 | struct BigMapEntry *bme; | 706 | struct BigMapEntry *bme; |
714 | 707 | ||
715 | for (bme = me.bme; NULL != bme; bme = bme->next) | 708 | for (bme = me.bme; NULL != bme; bme = bme->next) |
716 | if ((0 == GNUNET_memcmp (key, &bme->key)) && (bme->value == value)) | 709 | if ((0 == GNUNET_memcmp(key, &bme->key)) && (bme->value == value)) |
717 | return GNUNET_YES; | 710 | return GNUNET_YES; |
718 | } | 711 | } |
719 | return GNUNET_NO; | 712 | return GNUNET_NO; |
720 | } | 713 | } |
721 | 714 | ||
@@ -726,7 +719,7 @@ GNUNET_CONTAINER_multihashmap_contains_value ( | |||
726 | * @param map the hash map to grow | 719 | * @param map the hash map to grow |
727 | */ | 720 | */ |
728 | static void | 721 | static void |
729 | grow (struct GNUNET_CONTAINER_MultiHashMap *map) | 722 | grow(struct GNUNET_CONTAINER_MultiHashMap *map) |
730 | { | 723 | { |
731 | union MapEntry *old_map; | 724 | union MapEntry *old_map; |
732 | union MapEntry *new_map; | 725 | union MapEntry *new_map; |
@@ -736,46 +729,46 @@ grow (struct GNUNET_CONTAINER_MultiHashMap *map) | |||
736 | 729 | ||
737 | old_map = map->map; | 730 | old_map = map->map; |
738 | old_len = map->map_length; | 731 | old_len = map->map_length; |
739 | GNUNET_assert (0 != old_len); | 732 | GNUNET_assert(0 != old_len); |
740 | new_len = old_len * 2; | 733 | new_len = old_len * 2; |
741 | if (0 == new_len) /* 2^31 * 2 == 0 */ | 734 | if (0 == new_len) /* 2^31 * 2 == 0 */ |
742 | new_len = old_len; /* never use 0 */ | 735 | new_len = old_len; /* never use 0 */ |
743 | if (new_len == old_len) | 736 | if (new_len == old_len) |
744 | return; /* nothing changed */ | 737 | return; /* nothing changed */ |
745 | new_map = GNUNET_malloc_large (new_len * sizeof (union MapEntry)); | 738 | new_map = GNUNET_malloc_large(new_len * sizeof(union MapEntry)); |
746 | if (NULL == new_map) | 739 | if (NULL == new_map) |
747 | return; /* grow not possible */ | 740 | return; /* grow not possible */ |
748 | map->modification_counter++; | 741 | map->modification_counter++; |
749 | map->map_length = new_len; | 742 | map->map_length = new_len; |
750 | map->map = new_map; | 743 | map->map = new_map; |
751 | for (unsigned int i = 0; i < old_len; i++) | 744 | for (unsigned int i = 0; i < old_len; i++) |
752 | { | ||
753 | if (map->use_small_entries) | ||
754 | { | ||
755 | struct SmallMapEntry *sme; | ||
756 | |||
757 | while (NULL != (sme = old_map[i].sme)) | ||
758 | { | ||
759 | old_map[i].sme = sme->next; | ||
760 | idx = idx_of (map, sme->key); | ||
761 | sme->next = new_map[idx].sme; | ||
762 | new_map[idx].sme = sme; | ||
763 | } | ||
764 | } | ||
765 | else | ||
766 | { | 745 | { |
767 | struct BigMapEntry *bme; | 746 | if (map->use_small_entries) |
768 | 747 | { | |
769 | while (NULL != (bme = old_map[i].bme)) | 748 | struct SmallMapEntry *sme; |
770 | { | 749 | |
771 | old_map[i].bme = bme->next; | 750 | while (NULL != (sme = old_map[i].sme)) |
772 | idx = idx_of (map, &bme->key); | 751 | { |
773 | bme->next = new_map[idx].bme; | 752 | old_map[i].sme = sme->next; |
774 | new_map[idx].bme = bme; | 753 | idx = idx_of(map, sme->key); |
775 | } | 754 | sme->next = new_map[idx].sme; |
755 | new_map[idx].sme = sme; | ||
756 | } | ||
757 | } | ||
758 | else | ||
759 | { | ||
760 | struct BigMapEntry *bme; | ||
761 | |||
762 | while (NULL != (bme = old_map[i].bme)) | ||
763 | { | ||
764 | old_map[i].bme = bme->next; | ||
765 | idx = idx_of(map, &bme->key); | ||
766 | bme->next = new_map[idx].bme; | ||
767 | new_map[idx].bme = bme; | ||
768 | } | ||
769 | } | ||
776 | } | 770 | } |
777 | } | 771 | GNUNET_free(old_map); |
778 | GNUNET_free (old_map); | ||
779 | } | 772 | } |
780 | 773 | ||
781 | 774 | ||
@@ -792,71 +785,71 @@ grow (struct GNUNET_CONTAINER_MultiHashMap *map) | |||
792 | * value already exists | 785 | * value already exists |
793 | */ | 786 | */ |
794 | int | 787 | int |
795 | GNUNET_CONTAINER_multihashmap_put (struct GNUNET_CONTAINER_MultiHashMap *map, | 788 | GNUNET_CONTAINER_multihashmap_put(struct GNUNET_CONTAINER_MultiHashMap *map, |
796 | const struct GNUNET_HashCode *key, | 789 | const struct GNUNET_HashCode *key, |
797 | void *value, | 790 | void *value, |
798 | enum GNUNET_CONTAINER_MultiHashMapOption opt) | 791 | enum GNUNET_CONTAINER_MultiHashMapOption opt) |
799 | { | 792 | { |
800 | union MapEntry me; | 793 | union MapEntry me; |
801 | unsigned int i; | 794 | unsigned int i; |
802 | 795 | ||
803 | i = idx_of (map, key); | 796 | i = idx_of(map, key); |
804 | if ((opt != GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE) && | 797 | if ((opt != GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE) && |
805 | (opt != GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_FAST)) | 798 | (opt != GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_FAST)) |
806 | { | ||
807 | me = map->map[i]; | ||
808 | if (map->use_small_entries) | ||
809 | { | 799 | { |
810 | struct SmallMapEntry *sme; | 800 | me = map->map[i]; |
811 | 801 | if (map->use_small_entries) | |
812 | for (sme = me.sme; NULL != sme; sme = sme->next) | ||
813 | if (0 == GNUNET_memcmp (key, sme->key)) | ||
814 | { | 802 | { |
815 | if (opt == GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY) | 803 | struct SmallMapEntry *sme; |
816 | return GNUNET_SYSERR; | 804 | |
817 | sme->value = value; | 805 | for (sme = me.sme; NULL != sme; sme = sme->next) |
818 | return GNUNET_NO; | 806 | if (0 == GNUNET_memcmp(key, sme->key)) |
807 | { | ||
808 | if (opt == GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY) | ||
809 | return GNUNET_SYSERR; | ||
810 | sme->value = value; | ||
811 | return GNUNET_NO; | ||
812 | } | ||
819 | } | 813 | } |
820 | } | 814 | else |
821 | else | ||
822 | { | ||
823 | struct BigMapEntry *bme; | ||
824 | |||
825 | for (bme = me.bme; NULL != bme; bme = bme->next) | ||
826 | if (0 == GNUNET_memcmp (key, &bme->key)) | ||
827 | { | 815 | { |
828 | if (opt == GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY) | 816 | struct BigMapEntry *bme; |
829 | return GNUNET_SYSERR; | 817 | |
830 | bme->value = value; | 818 | for (bme = me.bme; NULL != bme; bme = bme->next) |
831 | return GNUNET_NO; | 819 | if (0 == GNUNET_memcmp(key, &bme->key)) |
820 | { | ||
821 | if (opt == GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY) | ||
822 | return GNUNET_SYSERR; | ||
823 | bme->value = value; | ||
824 | return GNUNET_NO; | ||
825 | } | ||
832 | } | 826 | } |
833 | } | 827 | } |
834 | } | ||
835 | if (map->size / 3 >= map->map_length / 4) | 828 | if (map->size / 3 >= map->map_length / 4) |
836 | { | 829 | { |
837 | grow (map); | 830 | grow(map); |
838 | i = idx_of (map, key); | 831 | i = idx_of(map, key); |
839 | } | 832 | } |
840 | if (map->use_small_entries) | 833 | if (map->use_small_entries) |
841 | { | 834 | { |
842 | struct SmallMapEntry *sme; | 835 | struct SmallMapEntry *sme; |
843 | 836 | ||
844 | sme = GNUNET_new (struct SmallMapEntry); | 837 | sme = GNUNET_new(struct SmallMapEntry); |
845 | sme->key = key; | 838 | sme->key = key; |
846 | sme->value = value; | 839 | sme->value = value; |
847 | sme->next = map->map[i].sme; | 840 | sme->next = map->map[i].sme; |
848 | map->map[i].sme = sme; | 841 | map->map[i].sme = sme; |
849 | } | 842 | } |
850 | else | 843 | else |
851 | { | 844 | { |
852 | struct BigMapEntry *bme; | 845 | struct BigMapEntry *bme; |
853 | 846 | ||
854 | bme = GNUNET_new (struct BigMapEntry); | 847 | bme = GNUNET_new(struct BigMapEntry); |
855 | bme->key = *key; | 848 | bme->key = *key; |
856 | bme->value = value; | 849 | bme->value = value; |
857 | bme->next = map->map[i].bme; | 850 | bme->next = map->map[i].bme; |
858 | map->map[i].bme = bme; | 851 | map->map[i].bme = bme; |
859 | } | 852 | } |
860 | map->size++; | 853 | map->size++; |
861 | return GNUNET_OK; | 854 | return GNUNET_OK; |
862 | } | 855 | } |
@@ -873,7 +866,7 @@ GNUNET_CONTAINER_multihashmap_put (struct GNUNET_CONTAINER_MultiHashMap *map, | |||
873 | * #GNUNET_SYSERR if it aborted iteration | 866 | * #GNUNET_SYSERR if it aborted iteration |
874 | */ | 867 | */ |
875 | int | 868 | int |
876 | GNUNET_CONTAINER_multihashmap_get_multiple ( | 869 | GNUNET_CONTAINER_multihashmap_get_multiple( |
877 | struct GNUNET_CONTAINER_MultiHashMap *map, | 870 | struct GNUNET_CONTAINER_MultiHashMap *map, |
878 | const struct GNUNET_HashCode *key, | 871 | const struct GNUNET_HashCode *key, |
879 | GNUNET_CONTAINER_MulitHashMapIteratorCallback it, | 872 | GNUNET_CONTAINER_MulitHashMapIteratorCallback it, |
@@ -884,46 +877,46 @@ GNUNET_CONTAINER_multihashmap_get_multiple ( | |||
884 | union MapEntry *ce; | 877 | union MapEntry *ce; |
885 | 878 | ||
886 | ce = &map->next_cache[map->next_cache_off]; | 879 | ce = &map->next_cache[map->next_cache_off]; |
887 | GNUNET_assert (++map->next_cache_off < NEXT_CACHE_SIZE); | 880 | GNUNET_assert(++map->next_cache_off < NEXT_CACHE_SIZE); |
888 | count = 0; | 881 | count = 0; |
889 | me = &map->map[idx_of (map, key)]; | 882 | me = &map->map[idx_of(map, key)]; |
890 | if (map->use_small_entries) | 883 | if (map->use_small_entries) |
891 | { | ||
892 | struct SmallMapEntry *sme; | ||
893 | |||
894 | ce->sme = me->sme; | ||
895 | while (NULL != (sme = ce->sme)) | ||
896 | { | 884 | { |
897 | ce->sme = sme->next; | 885 | struct SmallMapEntry *sme; |
898 | if (0 != GNUNET_memcmp (key, sme->key)) | 886 | |
899 | continue; | 887 | ce->sme = me->sme; |
900 | if ((NULL != it) && (GNUNET_OK != it (it_cls, key, sme->value))) | 888 | while (NULL != (sme = ce->sme)) |
901 | { | 889 | { |
902 | GNUNET_assert (--map->next_cache_off < NEXT_CACHE_SIZE); | 890 | ce->sme = sme->next; |
903 | return GNUNET_SYSERR; | 891 | if (0 != GNUNET_memcmp(key, sme->key)) |
904 | } | 892 | continue; |
905 | count++; | 893 | if ((NULL != it) && (GNUNET_OK != it(it_cls, key, sme->value))) |
894 | { | ||
895 | GNUNET_assert(--map->next_cache_off < NEXT_CACHE_SIZE); | ||
896 | return GNUNET_SYSERR; | ||
897 | } | ||
898 | count++; | ||
899 | } | ||
906 | } | 900 | } |
907 | } | ||
908 | else | 901 | else |
909 | { | ||
910 | struct BigMapEntry *bme; | ||
911 | |||
912 | ce->bme = me->bme; | ||
913 | while (NULL != (bme = ce->bme)) | ||
914 | { | 902 | { |
915 | ce->bme = bme->next; | 903 | struct BigMapEntry *bme; |
916 | if (0 != GNUNET_memcmp (key, &bme->key)) | 904 | |
917 | continue; | 905 | ce->bme = me->bme; |
918 | if ((NULL != it) && (GNUNET_OK != it (it_cls, key, bme->value))) | 906 | while (NULL != (bme = ce->bme)) |
919 | { | 907 | { |
920 | GNUNET_assert (--map->next_cache_off < NEXT_CACHE_SIZE); | 908 | ce->bme = bme->next; |
921 | return GNUNET_SYSERR; | 909 | if (0 != GNUNET_memcmp(key, &bme->key)) |
922 | } | 910 | continue; |
923 | count++; | 911 | if ((NULL != it) && (GNUNET_OK != it(it_cls, key, bme->value))) |
912 | { | ||
913 | GNUNET_assert(--map->next_cache_off < NEXT_CACHE_SIZE); | ||
914 | return GNUNET_SYSERR; | ||
915 | } | ||
916 | count++; | ||
917 | } | ||
924 | } | 918 | } |
925 | } | 919 | GNUNET_assert(--map->next_cache_off < NEXT_CACHE_SIZE); |
926 | GNUNET_assert (--map->next_cache_off < NEXT_CACHE_SIZE); | ||
927 | return count; | 920 | return count; |
928 | } | 921 | } |
929 | 922 | ||
@@ -940,7 +933,7 @@ GNUNET_CONTAINER_multihashmap_get_multiple ( | |||
940 | * @return the number of key value pairs processed, zero or one. | 933 | * @return the number of key value pairs processed, zero or one. |
941 | */ | 934 | */ |
942 | unsigned int | 935 | unsigned int |
943 | GNUNET_CONTAINER_multihashmap_get_random ( | 936 | GNUNET_CONTAINER_multihashmap_get_random( |
944 | const struct GNUNET_CONTAINER_MultiHashMap *map, | 937 | const struct GNUNET_CONTAINER_MultiHashMap *map, |
945 | GNUNET_CONTAINER_MulitHashMapIteratorCallback it, | 938 | GNUNET_CONTAINER_MulitHashMapIteratorCallback it, |
946 | void *it_cls) | 939 | void *it_cls) |
@@ -953,48 +946,48 @@ GNUNET_CONTAINER_multihashmap_get_random ( | |||
953 | return 0; | 946 | return 0; |
954 | if (NULL == it) | 947 | if (NULL == it) |
955 | return 1; | 948 | return 1; |
956 | off = GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_NONCE, map->size); | 949 | off = GNUNET_CRYPTO_random_u32(GNUNET_CRYPTO_QUALITY_NONCE, map->size); |
957 | for (idx = 0; idx < map->map_length; idx++) | 950 | for (idx = 0; idx < map->map_length; idx++) |
958 | { | ||
959 | me = map->map[idx]; | ||
960 | if (map->use_small_entries) | ||
961 | { | 951 | { |
962 | struct SmallMapEntry *sme; | 952 | me = map->map[idx]; |
963 | struct SmallMapEntry *nxt; | 953 | if (map->use_small_entries) |
964 | |||
965 | nxt = me.sme; | ||
966 | while (NULL != (sme = nxt)) | ||
967 | { | ||
968 | nxt = sme->next; | ||
969 | if (0 == off) | ||
970 | { | 954 | { |
971 | if (GNUNET_OK != it (it_cls, sme->key, sme->value)) | 955 | struct SmallMapEntry *sme; |
972 | return GNUNET_SYSERR; | 956 | struct SmallMapEntry *nxt; |
973 | return 1; | 957 | |
958 | nxt = me.sme; | ||
959 | while (NULL != (sme = nxt)) | ||
960 | { | ||
961 | nxt = sme->next; | ||
962 | if (0 == off) | ||
963 | { | ||
964 | if (GNUNET_OK != it(it_cls, sme->key, sme->value)) | ||
965 | return GNUNET_SYSERR; | ||
966 | return 1; | ||
967 | } | ||
968 | off--; | ||
969 | } | ||
974 | } | 970 | } |
975 | off--; | 971 | else |
976 | } | ||
977 | } | ||
978 | else | ||
979 | { | ||
980 | struct BigMapEntry *bme; | ||
981 | struct BigMapEntry *nxt; | ||
982 | |||
983 | nxt = me.bme; | ||
984 | while (NULL != (bme = nxt)) | ||
985 | { | ||
986 | nxt = bme->next; | ||
987 | if (0 == off) | ||
988 | { | 972 | { |
989 | if (GNUNET_OK != it (it_cls, &bme->key, bme->value)) | 973 | struct BigMapEntry *bme; |
990 | return GNUNET_SYSERR; | 974 | struct BigMapEntry *nxt; |
991 | return 1; | 975 | |
976 | nxt = me.bme; | ||
977 | while (NULL != (bme = nxt)) | ||
978 | { | ||
979 | nxt = bme->next; | ||
980 | if (0 == off) | ||
981 | { | ||
982 | if (GNUNET_OK != it(it_cls, &bme->key, bme->value)) | ||
983 | return GNUNET_SYSERR; | ||
984 | return 1; | ||
985 | } | ||
986 | off--; | ||
987 | } | ||
992 | } | 988 | } |
993 | off--; | ||
994 | } | ||
995 | } | 989 | } |
996 | } | 990 | GNUNET_break(0); |
997 | GNUNET_break (0); | ||
998 | return GNUNET_SYSERR; | 991 | return GNUNET_SYSERR; |
999 | } | 992 | } |
1000 | 993 | ||
@@ -1012,12 +1005,12 @@ GNUNET_CONTAINER_multihashmap_get_random ( | |||
1012 | * @return an iterator over the given multihashmap 'map' | 1005 | * @return an iterator over the given multihashmap 'map' |
1013 | */ | 1006 | */ |
1014 | struct GNUNET_CONTAINER_MultiHashMapIterator * | 1007 | struct GNUNET_CONTAINER_MultiHashMapIterator * |
1015 | GNUNET_CONTAINER_multihashmap_iterator_create ( | 1008 | GNUNET_CONTAINER_multihashmap_iterator_create( |
1016 | const struct GNUNET_CONTAINER_MultiHashMap *map) | 1009 | const struct GNUNET_CONTAINER_MultiHashMap *map) |
1017 | { | 1010 | { |
1018 | struct GNUNET_CONTAINER_MultiHashMapIterator *iter; | 1011 | struct GNUNET_CONTAINER_MultiHashMapIterator *iter; |
1019 | 1012 | ||
1020 | iter = GNUNET_new (struct GNUNET_CONTAINER_MultiHashMapIterator); | 1013 | iter = GNUNET_new(struct GNUNET_CONTAINER_MultiHashMapIterator); |
1021 | iter->map = map; | 1014 | iter->map = map; |
1022 | iter->modification_counter = map->modification_counter; | 1015 | iter->modification_counter = map->modification_counter; |
1023 | iter->me = map->map[0]; | 1016 | iter->me = map->map[0]; |
@@ -1040,47 +1033,47 @@ GNUNET_CONTAINER_multihashmap_iterator_create ( | |||
1040 | * #GNUNET_NO if we are out of elements | 1033 | * #GNUNET_NO if we are out of elements |
1041 | */ | 1034 | */ |
1042 | int | 1035 | int |
1043 | GNUNET_CONTAINER_multihashmap_iterator_next ( | 1036 | GNUNET_CONTAINER_multihashmap_iterator_next( |
1044 | struct GNUNET_CONTAINER_MultiHashMapIterator *iter, | 1037 | struct GNUNET_CONTAINER_MultiHashMapIterator *iter, |
1045 | struct GNUNET_HashCode *key, | 1038 | struct GNUNET_HashCode *key, |
1046 | const void **value) | 1039 | const void **value) |
1047 | { | 1040 | { |
1048 | /* make sure the map has not been modified */ | 1041 | /* make sure the map has not been modified */ |
1049 | GNUNET_assert (iter->modification_counter == iter->map->modification_counter); | 1042 | GNUNET_assert(iter->modification_counter == iter->map->modification_counter); |
1050 | 1043 | ||
1051 | /* look for the next entry, skipping empty buckets */ | 1044 | /* look for the next entry, skipping empty buckets */ |
1052 | while (1) | 1045 | while (1) |
1053 | { | ||
1054 | if (iter->idx >= iter->map->map_length) | ||
1055 | return GNUNET_NO; | ||
1056 | if (GNUNET_YES == iter->map->use_small_entries) | ||
1057 | { | ||
1058 | if (NULL != iter->me.sme) | ||
1059 | { | ||
1060 | if (NULL != key) | ||
1061 | *key = *iter->me.sme->key; | ||
1062 | if (NULL != value) | ||
1063 | *value = iter->me.sme->value; | ||
1064 | iter->me.sme = iter->me.sme->next; | ||
1065 | return GNUNET_YES; | ||
1066 | } | ||
1067 | } | ||
1068 | else | ||
1069 | { | 1046 | { |
1070 | if (NULL != iter->me.bme) | 1047 | if (iter->idx >= iter->map->map_length) |
1071 | { | 1048 | return GNUNET_NO; |
1072 | if (NULL != key) | 1049 | if (GNUNET_YES == iter->map->use_small_entries) |
1073 | *key = iter->me.bme->key; | 1050 | { |
1074 | if (NULL != value) | 1051 | if (NULL != iter->me.sme) |
1075 | *value = iter->me.bme->value; | 1052 | { |
1076 | iter->me.bme = iter->me.bme->next; | 1053 | if (NULL != key) |
1077 | return GNUNET_YES; | 1054 | *key = *iter->me.sme->key; |
1078 | } | 1055 | if (NULL != value) |
1056 | *value = iter->me.sme->value; | ||
1057 | iter->me.sme = iter->me.sme->next; | ||
1058 | return GNUNET_YES; | ||
1059 | } | ||
1060 | } | ||
1061 | else | ||
1062 | { | ||
1063 | if (NULL != iter->me.bme) | ||
1064 | { | ||
1065 | if (NULL != key) | ||
1066 | *key = iter->me.bme->key; | ||
1067 | if (NULL != value) | ||
1068 | *value = iter->me.bme->value; | ||
1069 | iter->me.bme = iter->me.bme->next; | ||
1070 | return GNUNET_YES; | ||
1071 | } | ||
1072 | } | ||
1073 | iter->idx += 1; | ||
1074 | if (iter->idx < iter->map->map_length) | ||
1075 | iter->me = iter->map->map[iter->idx]; | ||
1079 | } | 1076 | } |
1080 | iter->idx += 1; | ||
1081 | if (iter->idx < iter->map->map_length) | ||
1082 | iter->me = iter->map->map[iter->idx]; | ||
1083 | } | ||
1084 | } | 1077 | } |
1085 | 1078 | ||
1086 | 1079 | ||
@@ -1090,10 +1083,10 @@ GNUNET_CONTAINER_multihashmap_iterator_next ( | |||
1090 | * @param iter the iterator to destroy | 1083 | * @param iter the iterator to destroy |
1091 | */ | 1084 | */ |
1092 | void | 1085 | void |
1093 | GNUNET_CONTAINER_multihashmap_iterator_destroy ( | 1086 | GNUNET_CONTAINER_multihashmap_iterator_destroy( |
1094 | struct GNUNET_CONTAINER_MultiHashMapIterator *iter) | 1087 | struct GNUNET_CONTAINER_MultiHashMapIterator *iter) |
1095 | { | 1088 | { |
1096 | GNUNET_free (iter); | 1089 | GNUNET_free(iter); |
1097 | } | 1090 | } |
1098 | 1091 | ||
1099 | 1092 | ||