diff options
Diffstat (limited to 'src/lib/util/container_multipeermap.c')
-rw-r--r-- | src/lib/util/container_multipeermap.c | 895 |
1 files changed, 895 insertions, 0 deletions
diff --git a/src/lib/util/container_multipeermap.c b/src/lib/util/container_multipeermap.c new file mode 100644 index 000000000..7ccfb62c8 --- /dev/null +++ b/src/lib/util/container_multipeermap.c | |||
@@ -0,0 +1,895 @@ | |||
1 | /* | ||
2 | This file is part of GNUnet. | ||
3 | Copyright (C) 2008, 2012 GNUnet e.V. | ||
4 | |||
5 | GNUnet is free software: you can redistribute it and/or modify it | ||
6 | under the terms of the GNU Affero General Public License as published | ||
7 | by the Free Software Foundation, either version 3 of the License, | ||
8 | or (at your option) any later version. | ||
9 | |||
10 | GNUnet is distributed in the hope that it will be useful, but | ||
11 | WITHOUT ANY WARRANTY; without even the implied warranty of | ||
12 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU | ||
13 | Affero General Public License for more details. | ||
14 | |||
15 | You should have received a copy of the GNU Affero General Public License | ||
16 | along with this program. If not, see <http://www.gnu.org/licenses/>. | ||
17 | |||
18 | SPDX-License-Identifier: AGPL3.0-or-later | ||
19 | */ | ||
20 | /** | ||
21 | * @file util/container_multipeermap.c | ||
22 | * @brief hash map where the same key may be present multiple times | ||
23 | * @author Christian Grothoff | ||
24 | */ | ||
25 | |||
26 | |||
27 | #include "platform.h" | ||
28 | #include "gnunet_util_lib.h" | ||
29 | |||
30 | #define LOG(kind, ...) \ | ||
31 | GNUNET_log_from (kind, "util-container-multipeermap", __VA_ARGS__) | ||
32 | |||
33 | /** | ||
34 | * Maximum recursion depth for callbacks of | ||
35 | * #GNUNET_CONTAINER_multihashmap_get_multiple() themselves s | ||
36 | * again calling #GNUNET_CONTAINER_multihashmap_get_multiple(). | ||
37 | * Should be totally excessive, but if violated we die. | ||
38 | */ | ||
39 | #define NEXT_CACHE_SIZE 16 | ||
40 | |||
41 | /** | ||
42 | * An entry in the hash map with the full key. | ||
43 | */ | ||
44 | struct BigMapEntry | ||
45 | { | ||
46 | /** | ||
47 | * Value of the entry. | ||
48 | */ | ||
49 | void *value; | ||
50 | |||
51 | /** | ||
52 | * If there is a hash collision, we create a linked list. | ||
53 | */ | ||
54 | struct BigMapEntry *next; | ||
55 | |||
56 | /** | ||
57 | * Key for the entry. | ||
58 | */ | ||
59 | struct GNUNET_PeerIdentity key; | ||
60 | }; | ||
61 | |||
62 | |||
63 | /** | ||
64 | * An entry in the hash map with just a pointer to the key. | ||
65 | */ | ||
66 | struct SmallMapEntry | ||
67 | { | ||
68 | /** | ||
69 | * Value of the entry. | ||
70 | */ | ||
71 | void *value; | ||
72 | |||
73 | /** | ||
74 | * If there is a hash collision, we create a linked list. | ||
75 | */ | ||
76 | struct SmallMapEntry *next; | ||
77 | |||
78 | /** | ||
79 | * Key for the entry. | ||
80 | */ | ||
81 | const struct GNUNET_PeerIdentity *key; | ||
82 | }; | ||
83 | |||
84 | |||
85 | /** | ||
86 | * Entry in the map. | ||
87 | */ | ||
88 | union MapEntry | ||
89 | { | ||
90 | /** | ||
91 | * Variant used if map entries only contain a pointer to the key. | ||
92 | */ | ||
93 | struct SmallMapEntry *sme; | ||
94 | |||
95 | /** | ||
96 | * Variant used if map entries contain the full key. | ||
97 | */ | ||
98 | struct BigMapEntry *bme; | ||
99 | }; | ||
100 | |||
101 | |||
102 | /** | ||
103 | * Internal representation of the hash map. | ||
104 | */ | ||
105 | struct GNUNET_CONTAINER_MultiPeerMap | ||
106 | { | ||
107 | /** | ||
108 | * All of our buckets. | ||
109 | */ | ||
110 | union MapEntry *map; | ||
111 | |||
112 | /** | ||
113 | * Number of entries in the map. | ||
114 | */ | ||
115 | unsigned int size; | ||
116 | |||
117 | /** | ||
118 | * Length of the "map" array. | ||
119 | */ | ||
120 | unsigned int map_length; | ||
121 | |||
122 | /** | ||
123 | * #GNUNET_NO if the map entries are of type 'struct BigMapEntry', | ||
124 | * #GNUNET_YES if the map entries are of type 'struct SmallMapEntry'. | ||
125 | */ | ||
126 | int use_small_entries; | ||
127 | |||
128 | /** | ||
129 | * Counts the destructive modifications (grow, remove) | ||
130 | * to the map, so that iterators can check if they are still valid. | ||
131 | */ | ||
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; | ||
146 | }; | ||
147 | |||
148 | |||
149 | /** | ||
150 | * Cursor into a multipeermap. | ||
151 | * Allows to enumerate elements asynchronously. | ||
152 | */ | ||
153 | struct GNUNET_CONTAINER_MultiPeerMapIterator | ||
154 | { | ||
155 | /** | ||
156 | * Position in the bucket 'idx' | ||
157 | */ | ||
158 | union MapEntry me; | ||
159 | |||
160 | /** | ||
161 | * Current bucket index. | ||
162 | */ | ||
163 | unsigned int idx; | ||
164 | |||
165 | /** | ||
166 | * Modification counter as observed on the map when the iterator | ||
167 | * was created. | ||
168 | */ | ||
169 | unsigned int modification_counter; | ||
170 | |||
171 | /** | ||
172 | * Map that we are iterating over. | ||
173 | */ | ||
174 | const struct GNUNET_CONTAINER_MultiPeerMap *map; | ||
175 | }; | ||
176 | |||
177 | |||
178 | struct GNUNET_CONTAINER_MultiPeerMap * | ||
179 | GNUNET_CONTAINER_multipeermap_create (unsigned int len, | ||
180 | int do_not_copy_keys) | ||
181 | { | ||
182 | struct GNUNET_CONTAINER_MultiPeerMap *map; | ||
183 | |||
184 | GNUNET_assert (len > 0); | ||
185 | map = GNUNET_new (struct GNUNET_CONTAINER_MultiPeerMap); | ||
186 | map->map = GNUNET_malloc_large (len * sizeof(union MapEntry)); | ||
187 | if (NULL == map->map) | ||
188 | { | ||
189 | GNUNET_free (map); | ||
190 | return NULL; | ||
191 | } | ||
192 | map->map_length = len; | ||
193 | map->use_small_entries = do_not_copy_keys; | ||
194 | return map; | ||
195 | } | ||
196 | |||
197 | |||
198 | void | ||
199 | GNUNET_CONTAINER_multipeermap_destroy ( | ||
200 | struct GNUNET_CONTAINER_MultiPeerMap *map) | ||
201 | { | ||
202 | GNUNET_assert (0 == map->next_cache_off); | ||
203 | for (unsigned int i = 0; i < map->map_length; i++) | ||
204 | { | ||
205 | union MapEntry me; | ||
206 | |||
207 | me = map->map[i]; | ||
208 | if (map->use_small_entries) | ||
209 | { | ||
210 | struct SmallMapEntry *sme; | ||
211 | struct SmallMapEntry *nxt; | ||
212 | |||
213 | nxt = me.sme; | ||
214 | while (NULL != (sme = nxt)) | ||
215 | { | ||
216 | nxt = sme->next; | ||
217 | GNUNET_free (sme); | ||
218 | } | ||
219 | me.sme = NULL; | ||
220 | } | ||
221 | else | ||
222 | { | ||
223 | struct BigMapEntry *bme; | ||
224 | struct BigMapEntry *nxt; | ||
225 | |||
226 | nxt = me.bme; | ||
227 | while (NULL != (bme = nxt)) | ||
228 | { | ||
229 | nxt = bme->next; | ||
230 | GNUNET_free (bme); | ||
231 | } | ||
232 | me.bme = NULL; | ||
233 | } | ||
234 | } | ||
235 | GNUNET_free (map->map); | ||
236 | GNUNET_free (map); | ||
237 | } | ||
238 | |||
239 | |||
240 | /** | ||
241 | * Compute the index of the bucket for the given key. | ||
242 | * | ||
243 | * @param map hash map for which to compute the index | ||
244 | * @param key what key should the index be computed for | ||
245 | * @return offset into the "map" array of "map" | ||
246 | */ | ||
247 | static unsigned int | ||
248 | idx_of (const struct GNUNET_CONTAINER_MultiPeerMap *map, | ||
249 | const struct GNUNET_PeerIdentity *key) | ||
250 | { | ||
251 | unsigned int kx; | ||
252 | |||
253 | GNUNET_assert (NULL != map); | ||
254 | GNUNET_memcpy (&kx, key, sizeof(kx)); | ||
255 | return kx % map->map_length; | ||
256 | } | ||
257 | |||
258 | |||
259 | unsigned int | ||
260 | GNUNET_CONTAINER_multipeermap_size ( | ||
261 | const struct GNUNET_CONTAINER_MultiPeerMap *map) | ||
262 | { | ||
263 | return map->size; | ||
264 | } | ||
265 | |||
266 | |||
267 | void * | ||
268 | GNUNET_CONTAINER_multipeermap_get ( | ||
269 | const struct GNUNET_CONTAINER_MultiPeerMap *map, | ||
270 | const struct GNUNET_PeerIdentity *key) | ||
271 | { | ||
272 | union MapEntry me; | ||
273 | |||
274 | me = map->map[idx_of (map, key)]; | ||
275 | if (map->use_small_entries) | ||
276 | { | ||
277 | for (struct SmallMapEntry *sme = me.sme; NULL != sme; sme = sme->next) | ||
278 | if (0 == GNUNET_memcmp (key, sme->key)) | ||
279 | return sme->value; | ||
280 | } | ||
281 | else | ||
282 | { | ||
283 | for (struct BigMapEntry *bme = me.bme; NULL != bme; bme = bme->next) | ||
284 | if (0 == GNUNET_memcmp (key, &bme->key)) | ||
285 | return bme->value; | ||
286 | } | ||
287 | return NULL; | ||
288 | } | ||
289 | |||
290 | |||
291 | int | ||
292 | GNUNET_CONTAINER_multipeermap_iterate ( | ||
293 | struct GNUNET_CONTAINER_MultiPeerMap *map, | ||
294 | GNUNET_CONTAINER_PeerMapIterator it, | ||
295 | void *it_cls) | ||
296 | { | ||
297 | int count; | ||
298 | union MapEntry me; | ||
299 | union MapEntry *ce; | ||
300 | struct GNUNET_PeerIdentity kc; | ||
301 | |||
302 | count = 0; | ||
303 | GNUNET_assert (NULL != map); | ||
304 | ce = &map->next_cache[map->next_cache_off]; | ||
305 | GNUNET_assert (++map->next_cache_off < NEXT_CACHE_SIZE); | ||
306 | for (unsigned int i = 0; i < map->map_length; i++) | ||
307 | { | ||
308 | me = map->map[i]; | ||
309 | if (map->use_small_entries) | ||
310 | { | ||
311 | struct SmallMapEntry *sme; | ||
312 | |||
313 | ce->sme = me.sme; | ||
314 | while (NULL != (sme = ce->sme)) | ||
315 | { | ||
316 | ce->sme = sme->next; | ||
317 | if (NULL != it) | ||
318 | { | ||
319 | if (GNUNET_OK != it (it_cls, sme->key, sme->value)) | ||
320 | { | ||
321 | GNUNET_assert (--map->next_cache_off < NEXT_CACHE_SIZE); | ||
322 | return GNUNET_SYSERR; | ||
323 | } | ||
324 | } | ||
325 | count++; | ||
326 | } | ||
327 | } | ||
328 | else | ||
329 | { | ||
330 | struct BigMapEntry *bme; | ||
331 | |||
332 | ce->bme = me.bme; | ||
333 | while (NULL != (bme = ce->bme)) | ||
334 | { | ||
335 | ce->bme = bme->next; | ||
336 | if (NULL != it) | ||
337 | { | ||
338 | kc = bme->key; | ||
339 | if (GNUNET_OK != it (it_cls, &kc, bme->value)) | ||
340 | { | ||
341 | GNUNET_assert (--map->next_cache_off < NEXT_CACHE_SIZE); | ||
342 | return GNUNET_SYSERR; | ||
343 | } | ||
344 | } | ||
345 | count++; | ||
346 | } | ||
347 | } | ||
348 | } | ||
349 | GNUNET_assert (--map->next_cache_off < NEXT_CACHE_SIZE); | ||
350 | return count; | ||
351 | } | ||
352 | |||
353 | |||
354 | /** | ||
355 | * We are about to free() the @a bme, make sure it is not in | ||
356 | * the list of next values for any iterator in the @a map's next_cache. | ||
357 | * | ||
358 | * @param map the map to check | ||
359 | * @param bme the entry that is about to be free'd | ||
360 | */ | ||
361 | static void | ||
362 | update_next_cache_bme (struct GNUNET_CONTAINER_MultiPeerMap *map, | ||
363 | const struct BigMapEntry *bme) | ||
364 | { | ||
365 | for (unsigned int i = 0; i < map->next_cache_off; i++) | ||
366 | if (map->next_cache[i].bme == bme) | ||
367 | map->next_cache[i].bme = bme->next; | ||
368 | } | ||
369 | |||
370 | |||
371 | /** | ||
372 | * We are about to free() the @a sme, make sure it is not in | ||
373 | * the list of next values for any iterator in the @a map's next_cache. | ||
374 | * | ||
375 | * @param map the map to check | ||
376 | * @param sme the entry that is about to be free'd | ||
377 | */ | ||
378 | static void | ||
379 | update_next_cache_sme (struct GNUNET_CONTAINER_MultiPeerMap *map, | ||
380 | const struct SmallMapEntry *sme) | ||
381 | { | ||
382 | for (unsigned int i = 0; i < map->next_cache_off; i++) | ||
383 | if (map->next_cache[i].sme == sme) | ||
384 | map->next_cache[i].sme = sme->next; | ||
385 | } | ||
386 | |||
387 | |||
388 | enum GNUNET_GenericReturnValue | ||
389 | GNUNET_CONTAINER_multipeermap_remove (struct GNUNET_CONTAINER_MultiPeerMap *map, | ||
390 | const struct GNUNET_PeerIdentity *key, | ||
391 | const void *value) | ||
392 | { | ||
393 | union MapEntry me; | ||
394 | unsigned int i; | ||
395 | |||
396 | map->modification_counter++; | ||
397 | i = idx_of (map, key); | ||
398 | me = map->map[i]; | ||
399 | if (map->use_small_entries) | ||
400 | { | ||
401 | struct SmallMapEntry *p = NULL; | ||
402 | |||
403 | for (struct SmallMapEntry *sme = me.sme; NULL != sme; sme = sme->next) | ||
404 | { | ||
405 | if ((0 == GNUNET_memcmp (key, sme->key)) && (value == sme->value)) | ||
406 | { | ||
407 | if (NULL == p) | ||
408 | map->map[i].sme = sme->next; | ||
409 | else | ||
410 | p->next = sme->next; | ||
411 | update_next_cache_sme (map, sme); | ||
412 | GNUNET_free (sme); | ||
413 | map->size--; | ||
414 | return GNUNET_YES; | ||
415 | } | ||
416 | p = sme; | ||
417 | } | ||
418 | } | ||
419 | else | ||
420 | { | ||
421 | struct BigMapEntry *p = NULL; | ||
422 | |||
423 | for (struct BigMapEntry *bme = me.bme; NULL != bme; bme = bme->next) | ||
424 | { | ||
425 | if ((0 == GNUNET_memcmp (key, &bme->key)) && (value == bme->value)) | ||
426 | { | ||
427 | if (NULL == p) | ||
428 | map->map[i].bme = bme->next; | ||
429 | else | ||
430 | p->next = bme->next; | ||
431 | update_next_cache_bme (map, bme); | ||
432 | GNUNET_free (bme); | ||
433 | map->size--; | ||
434 | return GNUNET_YES; | ||
435 | } | ||
436 | p = bme; | ||
437 | } | ||
438 | } | ||
439 | return GNUNET_NO; | ||
440 | } | ||
441 | |||
442 | |||
443 | int | ||
444 | GNUNET_CONTAINER_multipeermap_remove_all ( | ||
445 | struct GNUNET_CONTAINER_MultiPeerMap *map, | ||
446 | const struct GNUNET_PeerIdentity *key) | ||
447 | { | ||
448 | union MapEntry me; | ||
449 | unsigned int i; | ||
450 | int ret; | ||
451 | |||
452 | map->modification_counter++; | ||
453 | |||
454 | ret = 0; | ||
455 | i = idx_of (map, key); | ||
456 | me = map->map[i]; | ||
457 | if (map->use_small_entries) | ||
458 | { | ||
459 | struct SmallMapEntry *sme; | ||
460 | struct SmallMapEntry *p; | ||
461 | |||
462 | p = NULL; | ||
463 | sme = me.sme; | ||
464 | while (NULL != sme) | ||
465 | { | ||
466 | if (0 == GNUNET_memcmp (key, sme->key)) | ||
467 | { | ||
468 | if (NULL == p) | ||
469 | map->map[i].sme = sme->next; | ||
470 | else | ||
471 | p->next = sme->next; | ||
472 | update_next_cache_sme (map, sme); | ||
473 | GNUNET_free (sme); | ||
474 | map->size--; | ||
475 | if (NULL == p) | ||
476 | sme = map->map[i].sme; | ||
477 | else | ||
478 | sme = p->next; | ||
479 | ret++; | ||
480 | } | ||
481 | else | ||
482 | { | ||
483 | p = sme; | ||
484 | sme = sme->next; | ||
485 | } | ||
486 | } | ||
487 | } | ||
488 | else | ||
489 | { | ||
490 | struct BigMapEntry *bme; | ||
491 | struct BigMapEntry *p; | ||
492 | |||
493 | p = NULL; | ||
494 | bme = me.bme; | ||
495 | while (NULL != bme) | ||
496 | { | ||
497 | if (0 == GNUNET_memcmp (key, &bme->key)) | ||
498 | { | ||
499 | if (NULL == p) | ||
500 | map->map[i].bme = bme->next; | ||
501 | else | ||
502 | p->next = bme->next; | ||
503 | update_next_cache_bme (map, bme); | ||
504 | GNUNET_free (bme); | ||
505 | map->size--; | ||
506 | if (NULL == p) | ||
507 | bme = map->map[i].bme; | ||
508 | else | ||
509 | bme = p->next; | ||
510 | ret++; | ||
511 | } | ||
512 | else | ||
513 | { | ||
514 | p = bme; | ||
515 | bme = bme->next; | ||
516 | } | ||
517 | } | ||
518 | } | ||
519 | return ret; | ||
520 | } | ||
521 | |||
522 | |||
523 | enum GNUNET_GenericReturnValue | ||
524 | GNUNET_CONTAINER_multipeermap_contains ( | ||
525 | const struct GNUNET_CONTAINER_MultiPeerMap *map, | ||
526 | const struct GNUNET_PeerIdentity *key) | ||
527 | { | ||
528 | union MapEntry me; | ||
529 | |||
530 | me = map->map[idx_of (map, key)]; | ||
531 | if (map->use_small_entries) | ||
532 | { | ||
533 | for (struct SmallMapEntry *sme = me.sme; NULL != sme; sme = sme->next) | ||
534 | if (0 == GNUNET_memcmp (key, sme->key)) | ||
535 | return GNUNET_YES; | ||
536 | } | ||
537 | else | ||
538 | { | ||
539 | for (struct BigMapEntry *bme = me.bme; NULL != bme; bme = bme->next) | ||
540 | if (0 == GNUNET_memcmp (key, &bme->key)) | ||
541 | return GNUNET_YES; | ||
542 | } | ||
543 | return GNUNET_NO; | ||
544 | } | ||
545 | |||
546 | |||
547 | enum GNUNET_GenericReturnValue | ||
548 | GNUNET_CONTAINER_multipeermap_contains_value ( | ||
549 | const struct GNUNET_CONTAINER_MultiPeerMap *map, | ||
550 | const struct GNUNET_PeerIdentity *key, | ||
551 | const void *value) | ||
552 | { | ||
553 | union MapEntry me; | ||
554 | |||
555 | me = map->map[idx_of (map, key)]; | ||
556 | if (map->use_small_entries) | ||
557 | { | ||
558 | for (struct SmallMapEntry *sme = me.sme; NULL != sme; sme = sme->next) | ||
559 | if ((0 == GNUNET_memcmp (key, sme->key)) && (sme->value == value)) | ||
560 | return GNUNET_YES; | ||
561 | } | ||
562 | else | ||
563 | { | ||
564 | for (struct BigMapEntry *bme = me.bme; NULL != bme; bme = bme->next) | ||
565 | if ((0 == GNUNET_memcmp (key, &bme->key)) && (bme->value == value)) | ||
566 | return GNUNET_YES; | ||
567 | } | ||
568 | return GNUNET_NO; | ||
569 | } | ||
570 | |||
571 | |||
572 | /** | ||
573 | * Grow the given map to a more appropriate size. | ||
574 | * | ||
575 | * @param map the hash map to grow | ||
576 | */ | ||
577 | static void | ||
578 | grow (struct GNUNET_CONTAINER_MultiPeerMap *map) | ||
579 | { | ||
580 | union MapEntry *old_map; | ||
581 | union MapEntry *new_map; | ||
582 | unsigned int old_len; | ||
583 | unsigned int new_len; | ||
584 | unsigned int idx; | ||
585 | |||
586 | old_map = map->map; | ||
587 | old_len = map->map_length; | ||
588 | GNUNET_assert (0 != old_len); | ||
589 | new_len = old_len * 2; | ||
590 | if (0 == new_len) /* 2^31 * 2 == 0 */ | ||
591 | new_len = old_len; /* never use 0 */ | ||
592 | if (new_len == old_len) | ||
593 | return; /* nothing changed */ | ||
594 | new_map = GNUNET_malloc_large (new_len * sizeof(union MapEntry)); | ||
595 | if (NULL == new_map) | ||
596 | return; /* grow not possible */ | ||
597 | map->modification_counter++; | ||
598 | map->map_length = new_len; | ||
599 | map->map = new_map; | ||
600 | for (unsigned int i = 0; i < old_len; i++) | ||
601 | { | ||
602 | if (map->use_small_entries) | ||
603 | { | ||
604 | struct SmallMapEntry *sme; | ||
605 | |||
606 | while (NULL != (sme = old_map[i].sme)) | ||
607 | { | ||
608 | old_map[i].sme = sme->next; | ||
609 | idx = idx_of (map, sme->key); | ||
610 | sme->next = new_map[idx].sme; | ||
611 | new_map[idx].sme = sme; | ||
612 | } | ||
613 | } | ||
614 | else | ||
615 | { | ||
616 | struct BigMapEntry *bme; | ||
617 | |||
618 | while (NULL != (bme = old_map[i].bme)) | ||
619 | { | ||
620 | old_map[i].bme = bme->next; | ||
621 | idx = idx_of (map, &bme->key); | ||
622 | bme->next = new_map[idx].bme; | ||
623 | new_map[idx].bme = bme; | ||
624 | } | ||
625 | } | ||
626 | } | ||
627 | GNUNET_free (old_map); | ||
628 | } | ||
629 | |||
630 | |||
631 | int | ||
632 | GNUNET_CONTAINER_multipeermap_put (struct GNUNET_CONTAINER_MultiPeerMap *map, | ||
633 | const struct GNUNET_PeerIdentity *key, | ||
634 | void *value, | ||
635 | enum GNUNET_CONTAINER_MultiHashMapOption opt) | ||
636 | { | ||
637 | union MapEntry me; | ||
638 | unsigned int i; | ||
639 | |||
640 | i = idx_of (map, key); | ||
641 | if ((opt != GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE) && | ||
642 | (opt != GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_FAST)) | ||
643 | { | ||
644 | me = map->map[i]; | ||
645 | if (map->use_small_entries) | ||
646 | { | ||
647 | struct SmallMapEntry *sme; | ||
648 | |||
649 | for (sme = me.sme; NULL != sme; sme = sme->next) | ||
650 | if (0 == GNUNET_memcmp (key, sme->key)) | ||
651 | { | ||
652 | if (opt == GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY) | ||
653 | return GNUNET_SYSERR; | ||
654 | sme->value = value; | ||
655 | return GNUNET_NO; | ||
656 | } | ||
657 | } | ||
658 | else | ||
659 | { | ||
660 | struct BigMapEntry *bme; | ||
661 | |||
662 | for (bme = me.bme; NULL != bme; bme = bme->next) | ||
663 | if (0 == GNUNET_memcmp (key, &bme->key)) | ||
664 | { | ||
665 | if (opt == GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY) | ||
666 | return GNUNET_SYSERR; | ||
667 | bme->value = value; | ||
668 | return GNUNET_NO; | ||
669 | } | ||
670 | } | ||
671 | } | ||
672 | if (map->size / 3 >= map->map_length / 4) | ||
673 | { | ||
674 | grow (map); | ||
675 | i = idx_of (map, key); | ||
676 | } | ||
677 | if (map->use_small_entries) | ||
678 | { | ||
679 | struct SmallMapEntry *sme; | ||
680 | |||
681 | sme = GNUNET_new (struct SmallMapEntry); | ||
682 | sme->key = key; | ||
683 | sme->value = value; | ||
684 | sme->next = map->map[i].sme; | ||
685 | map->map[i].sme = sme; | ||
686 | } | ||
687 | else | ||
688 | { | ||
689 | struct BigMapEntry *bme; | ||
690 | |||
691 | bme = GNUNET_new (struct BigMapEntry); | ||
692 | bme->key = *key; | ||
693 | bme->value = value; | ||
694 | bme->next = map->map[i].bme; | ||
695 | map->map[i].bme = bme; | ||
696 | } | ||
697 | map->size++; | ||
698 | return GNUNET_OK; | ||
699 | } | ||
700 | |||
701 | |||
702 | int | ||
703 | GNUNET_CONTAINER_multipeermap_get_multiple ( | ||
704 | struct GNUNET_CONTAINER_MultiPeerMap *map, | ||
705 | const struct GNUNET_PeerIdentity *key, | ||
706 | GNUNET_CONTAINER_PeerMapIterator it, | ||
707 | void *it_cls) | ||
708 | { | ||
709 | int count; | ||
710 | union MapEntry me; | ||
711 | union MapEntry *ce; | ||
712 | |||
713 | ce = &map->next_cache[map->next_cache_off]; | ||
714 | GNUNET_assert (++map->next_cache_off < NEXT_CACHE_SIZE); | ||
715 | count = 0; | ||
716 | me = map->map[idx_of (map, key)]; | ||
717 | if (map->use_small_entries) | ||
718 | { | ||
719 | struct SmallMapEntry *sme; | ||
720 | |||
721 | ce->sme = me.sme; | ||
722 | while (NULL != (sme = ce->sme)) | ||
723 | { | ||
724 | ce->sme = sme->next; | ||
725 | if (0 != GNUNET_memcmp (key, sme->key)) | ||
726 | continue; | ||
727 | if ((NULL != it) && (GNUNET_OK != it (it_cls, key, sme->value))) | ||
728 | { | ||
729 | GNUNET_assert (--map->next_cache_off < NEXT_CACHE_SIZE); | ||
730 | return GNUNET_SYSERR; | ||
731 | } | ||
732 | count++; | ||
733 | } | ||
734 | } | ||
735 | else | ||
736 | { | ||
737 | struct BigMapEntry *bme; | ||
738 | |||
739 | ce->bme = me.bme; | ||
740 | while (NULL != (bme = ce->bme)) | ||
741 | { | ||
742 | ce->bme = bme->next; | ||
743 | if (0 != GNUNET_memcmp (key, &bme->key)) | ||
744 | continue; | ||
745 | if ((NULL != it) && (GNUNET_OK != it (it_cls, key, bme->value))) | ||
746 | { | ||
747 | GNUNET_assert (--map->next_cache_off < NEXT_CACHE_SIZE); | ||
748 | return GNUNET_SYSERR; | ||
749 | } | ||
750 | count++; | ||
751 | } | ||
752 | } | ||
753 | GNUNET_assert (--map->next_cache_off < NEXT_CACHE_SIZE); | ||
754 | return count; | ||
755 | } | ||
756 | |||
757 | |||
758 | /** | ||
759 | * @ingroup hashmap | ||
760 | * Call @a it on a random value from the map, or not at all | ||
761 | * if the map is empty. Note that this function has linear | ||
762 | * complexity (in the size of the map). | ||
763 | * | ||
764 | * @param map the map | ||
765 | * @param it function to call on a random entry | ||
766 | * @param it_cls extra argument to @a it | ||
767 | * @return the number of key value pairs processed, zero or one. | ||
768 | */ | ||
769 | unsigned int | ||
770 | GNUNET_CONTAINER_multipeermap_get_random ( | ||
771 | const struct GNUNET_CONTAINER_MultiPeerMap *map, | ||
772 | GNUNET_CONTAINER_PeerMapIterator it, | ||
773 | void *it_cls) | ||
774 | { | ||
775 | unsigned int off; | ||
776 | union MapEntry me; | ||
777 | |||
778 | if (0 == map->size) | ||
779 | return 0; | ||
780 | if (NULL == it) | ||
781 | return 1; | ||
782 | off = GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_NONCE, map->size); | ||
783 | for (unsigned int idx = 0; idx < map->map_length; idx++) | ||
784 | { | ||
785 | me = map->map[idx]; | ||
786 | if (map->use_small_entries) | ||
787 | { | ||
788 | struct SmallMapEntry *sme; | ||
789 | struct SmallMapEntry *nxt; | ||
790 | |||
791 | nxt = me.sme; | ||
792 | while (NULL != (sme = nxt)) | ||
793 | { | ||
794 | nxt = sme->next; | ||
795 | if (0 == off) | ||
796 | { | ||
797 | if (GNUNET_OK != it (it_cls, sme->key, sme->value)) | ||
798 | return GNUNET_SYSERR; | ||
799 | return 1; | ||
800 | } | ||
801 | off--; | ||
802 | } | ||
803 | } | ||
804 | else | ||
805 | { | ||
806 | struct BigMapEntry *bme; | ||
807 | struct BigMapEntry *nxt; | ||
808 | |||
809 | nxt = me.bme; | ||
810 | while (NULL != (bme = nxt)) | ||
811 | { | ||
812 | nxt = bme->next; | ||
813 | if (0 == off) | ||
814 | { | ||
815 | if (GNUNET_OK != it (it_cls, &bme->key, bme->value)) | ||
816 | return GNUNET_SYSERR; | ||
817 | return 1; | ||
818 | } | ||
819 | off--; | ||
820 | } | ||
821 | } | ||
822 | } | ||
823 | GNUNET_break (0); | ||
824 | return GNUNET_SYSERR; | ||
825 | } | ||
826 | |||
827 | |||
828 | struct GNUNET_CONTAINER_MultiPeerMapIterator * | ||
829 | GNUNET_CONTAINER_multipeermap_iterator_create ( | ||
830 | const struct GNUNET_CONTAINER_MultiPeerMap *map) | ||
831 | { | ||
832 | struct GNUNET_CONTAINER_MultiPeerMapIterator *iter; | ||
833 | |||
834 | iter = GNUNET_new (struct GNUNET_CONTAINER_MultiPeerMapIterator); | ||
835 | iter->map = map; | ||
836 | iter->modification_counter = map->modification_counter; | ||
837 | iter->me = map->map[0]; | ||
838 | return iter; | ||
839 | } | ||
840 | |||
841 | |||
842 | enum GNUNET_GenericReturnValue | ||
843 | GNUNET_CONTAINER_multipeermap_iterator_next ( | ||
844 | struct GNUNET_CONTAINER_MultiPeerMapIterator *iter, | ||
845 | struct GNUNET_PeerIdentity *key, | ||
846 | const void **value) | ||
847 | { | ||
848 | /* make sure the map has not been modified */ | ||
849 | GNUNET_assert (iter->modification_counter == iter->map->modification_counter); | ||
850 | |||
851 | /* look for the next entry, skipping empty buckets */ | ||
852 | while (1) | ||
853 | { | ||
854 | if (iter->idx >= iter->map->map_length) | ||
855 | return GNUNET_NO; | ||
856 | if (GNUNET_YES == iter->map->use_small_entries) | ||
857 | { | ||
858 | if (NULL != iter->me.sme) | ||
859 | { | ||
860 | if (NULL != key) | ||
861 | *key = *iter->me.sme->key; | ||
862 | if (NULL != value) | ||
863 | *value = iter->me.sme->value; | ||
864 | iter->me.sme = iter->me.sme->next; | ||
865 | return GNUNET_YES; | ||
866 | } | ||
867 | } | ||
868 | else | ||
869 | { | ||
870 | if (NULL != iter->me.bme) | ||
871 | { | ||
872 | if (NULL != key) | ||
873 | *key = iter->me.bme->key; | ||
874 | if (NULL != value) | ||
875 | *value = iter->me.bme->value; | ||
876 | iter->me.bme = iter->me.bme->next; | ||
877 | return GNUNET_YES; | ||
878 | } | ||
879 | } | ||
880 | iter->idx += 1; | ||
881 | if (iter->idx < iter->map->map_length) | ||
882 | iter->me = iter->map->map[iter->idx]; | ||
883 | } | ||
884 | } | ||
885 | |||
886 | |||
887 | void | ||
888 | GNUNET_CONTAINER_multipeermap_iterator_destroy ( | ||
889 | struct GNUNET_CONTAINER_MultiPeerMapIterator *iter) | ||
890 | { | ||
891 | GNUNET_free (iter); | ||
892 | } | ||
893 | |||
894 | |||
895 | /* end of container_multipeermap.c */ | ||