diff options
author | Christian Grothoff <christian@grothoff.org> | 2018-11-01 17:59:34 +0100 |
---|---|---|
committer | Christian Grothoff <christian@grothoff.org> | 2018-11-01 17:59:34 +0100 |
commit | 3c7d8978fadc492c68061aea11c18478b30b42b6 (patch) | |
tree | 6263575d450013f450afdb92ee1ccdd6243fa87f /src/util/container_multihashmap32.c | |
parent | a44ac13df59787a77fcdba5e46f3639f8d95460e (diff) | |
download | gnunet-3c7d8978fadc492c68061aea11c18478b30b42b6.tar.gz gnunet-3c7d8978fadc492c68061aea11c18478b30b42b6.zip |
fix #5465
Diffstat (limited to 'src/util/container_multihashmap32.c')
-rw-r--r-- | src/util/container_multihashmap32.c | 159 |
1 files changed, 101 insertions, 58 deletions
diff --git a/src/util/container_multihashmap32.c b/src/util/container_multihashmap32.c index daf5059b6..016dbabcc 100644 --- a/src/util/container_multihashmap32.c +++ b/src/util/container_multihashmap32.c | |||
@@ -28,6 +28,15 @@ | |||
28 | 28 | ||
29 | #define LOG(kind,...) GNUNET_log_from (kind, "util-container-multihashmap32", __VA_ARGS__) | 29 | #define LOG(kind,...) GNUNET_log_from (kind, "util-container-multihashmap32", __VA_ARGS__) |
30 | 30 | ||
31 | |||
32 | /** | ||
33 | * Maximum recursion depth for callbacks of | ||
34 | * #GNUNET_CONTAINER_multihashmap_get_multiple() themselves | ||
35 | * again calling #GNUNET_CONTAINER_multihashmap_get_multiple(). | ||
36 | * Should be totally excessive, but if violated we die. | ||
37 | */ | ||
38 | #define NEXT_CACHE_SIZE 16 | ||
39 | |||
31 | /** | 40 | /** |
32 | * An entry in the hash map. | 41 | * An entry in the hash map. |
33 | */ | 42 | */ |
@@ -68,7 +77,7 @@ struct GNUNET_CONTAINER_MultiHashMap32 | |||
68 | unsigned int size; | 77 | unsigned int size; |
69 | 78 | ||
70 | /** | 79 | /** |
71 | * Length of the "map" array. | 80 | * Length of the @e map array. |
72 | */ | 81 | */ |
73 | unsigned int map_length; | 82 | unsigned int map_length; |
74 | 83 | ||
@@ -77,6 +86,19 @@ struct GNUNET_CONTAINER_MultiHashMap32 | |||
77 | * to the map, so that iterators can check if they are still valid. | 86 | * to the map, so that iterators can check if they are still valid. |
78 | */ | 87 | */ |
79 | unsigned int modification_counter; | 88 | unsigned int modification_counter; |
89 | |||
90 | /** | ||
91 | * Map entries indicating iteration positions currently | ||
92 | * in use by #GNUNET_CONTAINER_multihashmap_get_multiple(). | ||
93 | * Only used up to @e next_cache_off. | ||
94 | */ | ||
95 | struct MapEntry *next_cache[NEXT_CACHE_SIZE]; | ||
96 | |||
97 | /** | ||
98 | * Offset of @e next_cache entries in use, must be smaller | ||
99 | * than #NEXT_CACHE_SIZE. | ||
100 | */ | ||
101 | unsigned int next_cache_off; | ||
80 | }; | 102 | }; |
81 | 103 | ||
82 | 104 | ||
@@ -87,7 +109,7 @@ struct GNUNET_CONTAINER_MultiHashMap32 | |||
87 | struct GNUNET_CONTAINER_MultiHashMap32Iterator | 109 | struct GNUNET_CONTAINER_MultiHashMap32Iterator |
88 | { | 110 | { |
89 | /** | 111 | /** |
90 | * Position in the bucket 'idx' | 112 | * Position in the bucket @e idx |
91 | */ | 113 | */ |
92 | struct MapEntry *me; | 114 | struct MapEntry *me; |
93 | 115 | ||
@@ -122,7 +144,8 @@ GNUNET_CONTAINER_multihashmap32_create (unsigned int len) | |||
122 | 144 | ||
123 | GNUNET_assert (len > 0); | 145 | GNUNET_assert (len > 0); |
124 | ret = GNUNET_new (struct GNUNET_CONTAINER_MultiHashMap32); | 146 | ret = GNUNET_new (struct GNUNET_CONTAINER_MultiHashMap32); |
125 | ret->map = GNUNET_malloc (len * sizeof (struct MapEntry *)); | 147 | ret->map = GNUNET_new_array (len, |
148 | struct MapEntry *); | ||
126 | ret->map_length = len; | 149 | ret->map_length = len; |
127 | return ret; | 150 | return ret; |
128 | } | 151 | } |
@@ -135,13 +158,11 @@ GNUNET_CONTAINER_multihashmap32_create (unsigned int len) | |||
135 | * @param map the map | 158 | * @param map the map |
136 | */ | 159 | */ |
137 | void | 160 | void |
138 | GNUNET_CONTAINER_multihashmap32_destroy (struct GNUNET_CONTAINER_MultiHashMap32 | 161 | GNUNET_CONTAINER_multihashmap32_destroy (struct GNUNET_CONTAINER_MultiHashMap32 *map) |
139 | *map) | ||
140 | { | 162 | { |
141 | unsigned int i; | ||
142 | struct MapEntry *e; | 163 | struct MapEntry *e; |
143 | 164 | ||
144 | for (i = 0; i < map->map_length; i++) | 165 | for (unsigned int i = 0; i < map->map_length; i++) |
145 | { | 166 | { |
146 | while (NULL != (e = map->map[i])) | 167 | while (NULL != (e = map->map[i])) |
147 | { | 168 | { |
@@ -165,7 +186,7 @@ static unsigned int | |||
165 | idx_of (const struct GNUNET_CONTAINER_MultiHashMap32 *m, | 186 | idx_of (const struct GNUNET_CONTAINER_MultiHashMap32 *m, |
166 | const uint32_t key) | 187 | const uint32_t key) |
167 | { | 188 | { |
168 | GNUNET_assert (m != NULL); | 189 | GNUNET_assert (NULL != m); |
169 | return ((unsigned int) key) % m->map_length; | 190 | return ((unsigned int) key) % m->map_length; |
170 | } | 191 | } |
171 | 192 | ||
@@ -177,8 +198,7 @@ idx_of (const struct GNUNET_CONTAINER_MultiHashMap32 *m, | |||
177 | * @return the number of key value pairs | 198 | * @return the number of key value pairs |
178 | */ | 199 | */ |
179 | unsigned int | 200 | unsigned int |
180 | GNUNET_CONTAINER_multihashmap32_size (const struct | 201 | GNUNET_CONTAINER_multihashmap32_size (const struct GNUNET_CONTAINER_MultiHashMap32 *map) |
181 | GNUNET_CONTAINER_MultiHashMap32 *map) | ||
182 | { | 202 | { |
183 | return map->size; | 203 | return map->size; |
184 | } | 204 | } |
@@ -195,14 +215,13 @@ GNUNET_CONTAINER_multihashmap32_size (const struct | |||
195 | * key-value pairs with value NULL | 215 | * key-value pairs with value NULL |
196 | */ | 216 | */ |
197 | void * | 217 | void * |
198 | GNUNET_CONTAINER_multihashmap32_get (const struct | 218 | GNUNET_CONTAINER_multihashmap32_get (const struct GNUNET_CONTAINER_MultiHashMap32 *map, |
199 | GNUNET_CONTAINER_MultiHashMap32 *map, | ||
200 | uint32_t key) | 219 | uint32_t key) |
201 | { | 220 | { |
202 | struct MapEntry *e; | 221 | struct MapEntry *e; |
203 | 222 | ||
204 | e = map->map[idx_of (map, key)]; | 223 | e = map->map[idx_of (map, key)]; |
205 | while (e != NULL) | 224 | while (NULL != e) |
206 | { | 225 | { |
207 | if (key == e->key) | 226 | if (key == e->key) |
208 | return e->value; | 227 | return e->value; |
@@ -222,27 +241,30 @@ GNUNET_CONTAINER_multihashmap32_get (const struct | |||
222 | * #GNUNET_SYSERR if it aborted iteration | 241 | * #GNUNET_SYSERR if it aborted iteration |
223 | */ | 242 | */ |
224 | int | 243 | int |
225 | GNUNET_CONTAINER_multihashmap32_iterate (const struct | 244 | GNUNET_CONTAINER_multihashmap32_iterate (struct GNUNET_CONTAINER_MultiHashMap32 *map, |
226 | GNUNET_CONTAINER_MultiHashMap32 *map, | 245 | GNUNET_CONTAINER_HashMapIterator32 it, |
227 | GNUNET_CONTAINER_HashMapIterator32 it, | ||
228 | void *it_cls) | 246 | void *it_cls) |
229 | { | 247 | { |
230 | int count; | 248 | int count; |
231 | unsigned int i; | 249 | struct MapEntry **ce; |
232 | struct MapEntry *e; | ||
233 | struct MapEntry *n; | ||
234 | 250 | ||
235 | count = 0; | 251 | count = 0; |
236 | GNUNET_assert (NULL != map); | 252 | GNUNET_assert (NULL != map); |
237 | for (i = 0; i < map->map_length; i++) | 253 | ce = &map->next_cache[map->next_cache_off]; |
254 | GNUNET_assert (++map->next_cache_off < NEXT_CACHE_SIZE); | ||
255 | for (unsigned int i = 0; i < map->map_length; i++) | ||
238 | { | 256 | { |
239 | n = map->map[i]; | 257 | struct MapEntry *e; |
240 | while (NULL != (e = n)) | 258 | |
259 | *ce = map->map[i]; | ||
260 | while (NULL != (e = *ce)) | ||
241 | { | 261 | { |
242 | n = e->next; | 262 | *ce = e->next; |
243 | if (NULL != it) | 263 | if (NULL != it) |
244 | { | 264 | { |
245 | if (GNUNET_OK != it (it_cls, e->key, e->value)) | 265 | if (GNUNET_OK != it (it_cls, |
266 | e->key, | ||
267 | e->value)) | ||
246 | return GNUNET_SYSERR; | 268 | return GNUNET_SYSERR; |
247 | } | 269 | } |
248 | count++; | 270 | count++; |
@@ -253,6 +275,23 @@ GNUNET_CONTAINER_multihashmap32_iterate (const struct | |||
253 | 275 | ||
254 | 276 | ||
255 | /** | 277 | /** |
278 | * We are about to free() the @a bme, make sure it is not in | ||
279 | * the list of next values for any iterator in the @a map's next_cache. | ||
280 | * | ||
281 | * @param map the map to check | ||
282 | * @param bme the entry that is about to be free'd | ||
283 | */ | ||
284 | static void | ||
285 | update_next_cache (struct GNUNET_CONTAINER_MultiHashMap32 *map, | ||
286 | const struct MapEntry *me) | ||
287 | { | ||
288 | for (unsigned int i=0;i<map->next_cache_off;i++) | ||
289 | if (map->next_cache[i] == me) | ||
290 | map->next_cache[i] = me->next; | ||
291 | } | ||
292 | |||
293 | |||
294 | /** | ||
256 | * Remove the given key-value pair from the map. Note that if the | 295 | * Remove the given key-value pair from the map. Note that if the |
257 | * key-value pair is in the map multiple times, only one of the pairs | 296 | * key-value pair is in the map multiple times, only one of the pairs |
258 | * will be removed. | 297 | * will be removed. |
@@ -260,13 +299,13 @@ GNUNET_CONTAINER_multihashmap32_iterate (const struct | |||
260 | * @param map the map | 299 | * @param map the map |
261 | * @param key key of the key-value pair | 300 | * @param key key of the key-value pair |
262 | * @param value value of the key-value pair | 301 | * @param value value of the key-value pair |
263 | * @return GNUNET_YES on success, GNUNET_NO if the key-value pair | 302 | * @return #GNUNET_YES on success, #GNUNET_NO if the key-value pair |
264 | * is not in the map | 303 | * is not in the map |
265 | */ | 304 | */ |
266 | int | 305 | int |
267 | GNUNET_CONTAINER_multihashmap32_remove (struct GNUNET_CONTAINER_MultiHashMap32 | 306 | GNUNET_CONTAINER_multihashmap32_remove (struct GNUNET_CONTAINER_MultiHashMap32 *map, |
268 | *map, | 307 | uint32_t key, |
269 | uint32_t key, const void *value) | 308 | const void *value) |
270 | { | 309 | { |
271 | struct MapEntry *e; | 310 | struct MapEntry *e; |
272 | struct MapEntry *p; | 311 | struct MapEntry *p; |
@@ -285,6 +324,8 @@ GNUNET_CONTAINER_multihashmap32_remove (struct GNUNET_CONTAINER_MultiHashMap32 | |||
285 | map->map[i] = e->next; | 324 | map->map[i] = e->next; |
286 | else | 325 | else |
287 | p->next = e->next; | 326 | p->next = e->next; |
327 | update_next_cache (map, | ||
328 | e); | ||
288 | GNUNET_free (e); | 329 | GNUNET_free (e); |
289 | map->size--; | 330 | map->size--; |
290 | return GNUNET_YES; | 331 | return GNUNET_YES; |
@@ -305,9 +346,7 @@ GNUNET_CONTAINER_multihashmap32_remove (struct GNUNET_CONTAINER_MultiHashMap32 | |||
305 | * @return number of values removed | 346 | * @return number of values removed |
306 | */ | 347 | */ |
307 | int | 348 | int |
308 | GNUNET_CONTAINER_multihashmap32_remove_all (struct | 349 | GNUNET_CONTAINER_multihashmap32_remove_all (struct GNUNET_CONTAINER_MultiHashMap32 *map, |
309 | GNUNET_CONTAINER_MultiHashMap32 | ||
310 | *map, | ||
311 | uint32_t key) | 350 | uint32_t key) |
312 | { | 351 | { |
313 | struct MapEntry *e; | 352 | struct MapEntry *e; |
@@ -329,6 +368,8 @@ GNUNET_CONTAINER_multihashmap32_remove_all (struct | |||
329 | map->map[i] = e->next; | 368 | map->map[i] = e->next; |
330 | else | 369 | else |
331 | p->next = e->next; | 370 | p->next = e->next; |
371 | update_next_cache (map, | ||
372 | e); | ||
332 | GNUNET_free (e); | 373 | GNUNET_free (e); |
333 | map->size--; | 374 | map->size--; |
334 | if (p == NULL) | 375 | if (p == NULL) |
@@ -353,12 +394,11 @@ GNUNET_CONTAINER_multihashmap32_remove_all (struct | |||
353 | * | 394 | * |
354 | * @param map the map | 395 | * @param map the map |
355 | * @param key the key to test if a value exists for it | 396 | * @param key the key to test if a value exists for it |
356 | * @return GNUNET_YES if such a value exists, | 397 | * @return #GNUNET_YES if such a value exists, |
357 | * GNUNET_NO if not | 398 | * #GNUNET_NO if not |
358 | */ | 399 | */ |
359 | int | 400 | int |
360 | GNUNET_CONTAINER_multihashmap32_contains (const struct | 401 | GNUNET_CONTAINER_multihashmap32_contains (const struct GNUNET_CONTAINER_MultiHashMap32 *map, |
361 | GNUNET_CONTAINER_MultiHashMap32 *map, | ||
362 | uint32_t key) | 402 | uint32_t key) |
363 | { | 403 | { |
364 | struct MapEntry *e; | 404 | struct MapEntry *e; |
@@ -381,13 +421,11 @@ GNUNET_CONTAINER_multihashmap32_contains (const struct | |||
381 | * @param map the map | 421 | * @param map the map |
382 | * @param key the key to test if a value exists for it | 422 | * @param key the key to test if a value exists for it |
383 | * @param value value to test for | 423 | * @param value value to test for |
384 | * @return GNUNET_YES if such a value exists, | 424 | * @return #GNUNET_YES if such a value exists, |
385 | * GNUNET_NO if not | 425 | * #GNUNET_NO if not |
386 | */ | 426 | */ |
387 | int | 427 | int |
388 | GNUNET_CONTAINER_multihashmap32_contains_value (const struct | 428 | GNUNET_CONTAINER_multihashmap32_contains_value (const struct GNUNET_CONTAINER_MultiHashMap32 *map, |
389 | GNUNET_CONTAINER_MultiHashMap32 | ||
390 | *map, | ||
391 | uint32_t key, | 429 | uint32_t key, |
392 | const void *value) | 430 | const void *value) |
393 | { | 431 | { |
@@ -418,17 +456,17 @@ grow (struct GNUNET_CONTAINER_MultiHashMap32 *map) | |||
418 | unsigned int old_len; | 456 | unsigned int old_len; |
419 | unsigned int new_len; | 457 | unsigned int new_len; |
420 | unsigned int idx; | 458 | unsigned int idx; |
421 | unsigned int i; | ||
422 | 459 | ||
423 | map->modification_counter++; | 460 | map->modification_counter++; |
424 | 461 | ||
425 | old_map = map->map; | 462 | old_map = map->map; |
426 | old_len = map->map_length; | 463 | old_len = map->map_length; |
427 | new_len = old_len * 2; | 464 | new_len = old_len * 2; |
428 | new_map = GNUNET_malloc (sizeof (struct MapEntry *) * new_len); | 465 | new_map = GNUNET_new_array (new_len, |
466 | struct MapEntry *); | ||
429 | map->map_length = new_len; | 467 | map->map_length = new_len; |
430 | map->map = new_map; | 468 | map->map = new_map; |
431 | for (i = 0; i < old_len; i++) | 469 | for (unsigned int i = 0; i < old_len; i++) |
432 | { | 470 | { |
433 | while (NULL != (e = old_map[i])) | 471 | while (NULL != (e = old_map[i])) |
434 | { | 472 | { |
@@ -449,9 +487,9 @@ grow (struct GNUNET_CONTAINER_MultiHashMap32 *map) | |||
449 | * @param key key to use | 487 | * @param key key to use |
450 | * @param value value to use | 488 | * @param value value to use |
451 | * @param opt options for put | 489 | * @param opt options for put |
452 | * @return GNUNET_OK on success, | 490 | * @return #GNUNET_OK on success, |
453 | * GNUNET_NO if a value was replaced (with REPLACE) | 491 | * #GNUNET_NO if a value was replaced (with REPLACE) |
454 | * GNUNET_SYSERR if UNIQUE_ONLY was the option and the | 492 | * #GNUNET_SYSERR if UNIQUE_ONLY was the option and the |
455 | * value already exists | 493 | * value already exists |
456 | */ | 494 | */ |
457 | int | 495 | int |
@@ -501,29 +539,34 @@ GNUNET_CONTAINER_multihashmap32_put (struct GNUNET_CONTAINER_MultiHashMap32 | |||
501 | * @param map the map | 539 | * @param map the map |
502 | * @param key key that the entries must correspond to | 540 | * @param key key that the entries must correspond to |
503 | * @param it function to call on each entry | 541 | * @param it function to call on each entry |
504 | * @param it_cls extra argument to it | 542 | * @param it_cls extra argument to @a it |
505 | * @return the number of key value pairs processed, | 543 | * @return the number of key value pairs processed, |
506 | * GNUNET_SYSERR if it aborted iteration | 544 | * GNUNET_SYSERR if it aborted iteration |
507 | */ | 545 | */ |
508 | int | 546 | int |
509 | GNUNET_CONTAINER_multihashmap32_get_multiple (const struct | 547 | GNUNET_CONTAINER_multihashmap32_get_multiple (struct GNUNET_CONTAINER_MultiHashMap32 *map, |
510 | GNUNET_CONTAINER_MultiHashMap32 | 548 | uint32_t key, |
511 | *map, uint32_t key, | 549 | GNUNET_CONTAINER_HashMapIterator32 it, |
512 | GNUNET_CONTAINER_HashMapIterator32 | 550 | void *it_cls) |
513 | it, void *it_cls) | ||
514 | { | 551 | { |
515 | int count; | 552 | int count; |
516 | struct MapEntry *e; | 553 | struct MapEntry *e; |
517 | struct MapEntry *n; | 554 | struct MapEntry **ce; |
518 | 555 | ||
519 | count = 0; | 556 | count = 0; |
520 | n = map->map[idx_of (map, key)]; | 557 | ce = &map->next_cache[map->next_cache_off]; |
521 | while (NULL != (e = n)) | 558 | GNUNET_assert (++map->next_cache_off < NEXT_CACHE_SIZE); |
559 | |||
560 | *ce = map->map[idx_of (map, key)]; | ||
561 | while (NULL != (e = *ce)) | ||
522 | { | 562 | { |
523 | n = e->next; | 563 | *ce = e->next; |
524 | if (key != e->key) | 564 | if (key != e->key) |
525 | continue; | 565 | continue; |
526 | if ((it != NULL) && (GNUNET_OK != it (it_cls, key, e->value))) | 566 | if ( (NULL != it) && |
567 | (GNUNET_OK != it (it_cls, | ||
568 | key, | ||
569 | e->value)) ) | ||
527 | return GNUNET_SYSERR; | 570 | return GNUNET_SYSERR; |
528 | count++; | 571 | count++; |
529 | } | 572 | } |
@@ -541,7 +584,7 @@ GNUNET_CONTAINER_multihashmap32_get_multiple (const struct | |||
541 | * result in skipped or repeated elements. | 584 | * result in skipped or repeated elements. |
542 | * | 585 | * |
543 | * @param map the map to create an iterator for | 586 | * @param map the map to create an iterator for |
544 | * @return an iterator over the given multihashmap 'map' | 587 | * @return an iterator over the given multihashmap @a map |
545 | */ | 588 | */ |
546 | struct GNUNET_CONTAINER_MultiHashMap32Iterator * | 589 | struct GNUNET_CONTAINER_MultiHashMap32Iterator * |
547 | GNUNET_CONTAINER_multihashmap32_iterator_create (const struct GNUNET_CONTAINER_MultiHashMap32 *map) | 590 | GNUNET_CONTAINER_multihashmap32_iterator_create (const struct GNUNET_CONTAINER_MultiHashMap32 *map) |