diff options
Diffstat (limited to 'src/util')
-rw-r--r-- | src/util/Makefile.am | 1 | ||||
-rw-r--r-- | src/util/container_multishortmap.c | 964 |
2 files changed, 965 insertions, 0 deletions
diff --git a/src/util/Makefile.am b/src/util/Makefile.am index c7f069206..f49aee17f 100644 --- a/src/util/Makefile.am +++ b/src/util/Makefile.am | |||
@@ -70,6 +70,7 @@ libgnunetutil_la_SOURCES = \ | |||
70 | container_heap.c \ | 70 | container_heap.c \ |
71 | container_meta_data.c \ | 71 | container_meta_data.c \ |
72 | container_multihashmap.c \ | 72 | container_multihashmap.c \ |
73 | container_multishortmap.c \ | ||
73 | container_multipeermap.c \ | 74 | container_multipeermap.c \ |
74 | container_multihashmap32.c \ | 75 | container_multihashmap32.c \ |
75 | crypto_symmetric.c \ | 76 | crypto_symmetric.c \ |
diff --git a/src/util/container_multishortmap.c b/src/util/container_multishortmap.c new file mode 100644 index 000000000..71d1073b0 --- /dev/null +++ b/src/util/container_multishortmap.c | |||
@@ -0,0 +1,964 @@ | |||
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 | ||
6 | it under the terms of the GNU General Public License as published | ||
7 | by the Free Software Foundation; either version 3, or (at your | ||
8 | 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 | General Public License for more details. | ||
14 | |||
15 | You should have received a copy of the GNU General Public License | ||
16 | along with GNUnet; see the file COPYING. If not, write to the | ||
17 | Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, | ||
18 | Boston, MA 02110-1301, USA. | ||
19 | */ | ||
20 | /** | ||
21 | * @file util/container_multishortmap.c | ||
22 | * @brief hash map where the same key may be present multiple times | ||
23 | * @author Christian Grothoff | ||
24 | */ | ||
25 | |||
26 | #include "platform.h" | ||
27 | #include "gnunet_util_lib.h" | ||
28 | |||
29 | #define LOG(kind,...) GNUNET_log_from (kind, "util", __VA_ARGS__) | ||
30 | |||
31 | /** | ||
32 | * An entry in the hash map with the full key. | ||
33 | */ | ||
34 | struct BigMapEntry | ||
35 | { | ||
36 | |||
37 | /** | ||
38 | * Value of the entry. | ||
39 | */ | ||
40 | void *value; | ||
41 | |||
42 | /** | ||
43 | * If there is a hash collision, we create a linked list. | ||
44 | */ | ||
45 | struct BigMapEntry *next; | ||
46 | |||
47 | /** | ||
48 | * Key for the entry. | ||
49 | */ | ||
50 | struct GNUNET_PeerIdentity key; | ||
51 | |||
52 | }; | ||
53 | |||
54 | |||
55 | /** | ||
56 | * An entry in the hash map with just a pointer to the key. | ||
57 | */ | ||
58 | struct SmallMapEntry | ||
59 | { | ||
60 | |||
61 | /** | ||
62 | * Value of the entry. | ||
63 | */ | ||
64 | void *value; | ||
65 | |||
66 | /** | ||
67 | * If there is a hash collision, we create a linked list. | ||
68 | */ | ||
69 | struct SmallMapEntry *next; | ||
70 | |||
71 | /** | ||
72 | * Key for the entry. | ||
73 | */ | ||
74 | const struct GNUNET_PeerIdentity *key; | ||
75 | |||
76 | }; | ||
77 | |||
78 | |||
79 | /** | ||
80 | * Entry in the map. | ||
81 | */ | ||
82 | union MapEntry | ||
83 | { | ||
84 | /** | ||
85 | * Variant used if map entries only contain a pointer to the key. | ||
86 | */ | ||
87 | struct SmallMapEntry *sme; | ||
88 | |||
89 | /** | ||
90 | * Variant used if map entries contain the full key. | ||
91 | */ | ||
92 | struct BigMapEntry *bme; | ||
93 | }; | ||
94 | |||
95 | |||
96 | /** | ||
97 | * Internal representation of the hash map. | ||
98 | */ | ||
99 | struct GNUNET_CONTAINER_MultiShortmap | ||
100 | { | ||
101 | /** | ||
102 | * All of our buckets. | ||
103 | */ | ||
104 | union MapEntry *map; | ||
105 | |||
106 | /** | ||
107 | * Number of entries in the map. | ||
108 | */ | ||
109 | unsigned int size; | ||
110 | |||
111 | /** | ||
112 | * Length of the "map" array. | ||
113 | */ | ||
114 | unsigned int map_length; | ||
115 | |||
116 | /** | ||
117 | * GNUNET_NO if the map entries are of type 'struct BigMapEntry', | ||
118 | * GNUNET_YES if the map entries are of type 'struct SmallMapEntry'. | ||
119 | */ | ||
120 | int use_small_entries; | ||
121 | |||
122 | /** | ||
123 | * Counts the destructive modifications (grow, remove) | ||
124 | * to the map, so that iterators can check if they are still valid. | ||
125 | */ | ||
126 | unsigned int modification_counter; | ||
127 | }; | ||
128 | |||
129 | |||
130 | /** | ||
131 | * Cursor into a multishortmap. | ||
132 | * Allows to enumerate elements asynchronously. | ||
133 | */ | ||
134 | struct GNUNET_CONTAINER_MultiShortmapIterator | ||
135 | { | ||
136 | /** | ||
137 | * Position in the bucket 'idx' | ||
138 | */ | ||
139 | union MapEntry me; | ||
140 | |||
141 | /** | ||
142 | * Current bucket index. | ||
143 | */ | ||
144 | unsigned int idx; | ||
145 | |||
146 | /** | ||
147 | * Modification counter as observed on the map when the iterator | ||
148 | * was created. | ||
149 | */ | ||
150 | unsigned int modification_counter; | ||
151 | |||
152 | /** | ||
153 | * Map that we are iterating over. | ||
154 | */ | ||
155 | const struct GNUNET_CONTAINER_MultiShortmap *map; | ||
156 | }; | ||
157 | |||
158 | |||
159 | /** | ||
160 | * Create a multi hash map. | ||
161 | * | ||
162 | * @param len initial size (map will grow as needed) | ||
163 | * @param do_not_copy_keys GNUNET_NO is always safe and should be used by default; | ||
164 | * GNUNET_YES means that on 'put', the 'key' does not have | ||
165 | * to be copied as the destination of the pointer is | ||
166 | * guaranteed to be life as long as the value is stored in | ||
167 | * the hashmap. This can significantly reduce memory | ||
168 | * consumption, but of course is also a recipie for | ||
169 | * heap corruption if the assumption is not true. Only | ||
170 | * use this if (1) memory use is important in this case and | ||
171 | * (2) you have triple-checked that the invariant holds | ||
172 | * @return NULL on error | ||
173 | */ | ||
174 | struct GNUNET_CONTAINER_MultiShortmap * | ||
175 | GNUNET_CONTAINER_multishortmap_create (unsigned int len, | ||
176 | int do_not_copy_keys) | ||
177 | { | ||
178 | struct GNUNET_CONTAINER_MultiShortmap *map; | ||
179 | |||
180 | GNUNET_assert (len > 0); | ||
181 | map = GNUNET_new (struct GNUNET_CONTAINER_MultiShortmap); | ||
182 | map->map = GNUNET_malloc (len * sizeof (union MapEntry)); | ||
183 | map->map_length = len; | ||
184 | map->use_small_entries = do_not_copy_keys; | ||
185 | return map; | ||
186 | } | ||
187 | |||
188 | |||
189 | /** | ||
190 | * Destroy a hash map. Will not free any values | ||
191 | * stored in the hash map! | ||
192 | * | ||
193 | * @param map the map | ||
194 | */ | ||
195 | void | ||
196 | GNUNET_CONTAINER_multishortmap_destroy (struct GNUNET_CONTAINER_MultiShortmap | ||
197 | *map) | ||
198 | { | ||
199 | unsigned int i; | ||
200 | union MapEntry me; | ||
201 | |||
202 | for (i = 0; i < map->map_length; i++) | ||
203 | { | ||
204 | me = map->map[i]; | ||
205 | if (map->use_small_entries) | ||
206 | { | ||
207 | struct SmallMapEntry *sme; | ||
208 | struct SmallMapEntry *nxt; | ||
209 | |||
210 | nxt = me.sme; | ||
211 | while (NULL != (sme = nxt)) | ||
212 | { | ||
213 | nxt = sme->next; | ||
214 | GNUNET_free (sme); | ||
215 | } | ||
216 | me.sme = NULL; | ||
217 | } | ||
218 | else | ||
219 | { | ||
220 | struct BigMapEntry *bme; | ||
221 | struct BigMapEntry *nxt; | ||
222 | |||
223 | nxt = me.bme; | ||
224 | while (NULL != (bme = nxt)) | ||
225 | { | ||
226 | nxt = bme->next; | ||
227 | GNUNET_free (bme); | ||
228 | } | ||
229 | me.bme = NULL; | ||
230 | } | ||
231 | } | ||
232 | GNUNET_free (map->map); | ||
233 | GNUNET_free (map); | ||
234 | } | ||
235 | |||
236 | |||
237 | /** | ||
238 | * Compute the index of the bucket for the given key. | ||
239 | * | ||
240 | * @param map hash map for which to compute the index | ||
241 | * @param key what key should the index be computed for | ||
242 | * @return offset into the "map" array of "map" | ||
243 | */ | ||
244 | static unsigned int | ||
245 | idx_of (const struct GNUNET_CONTAINER_MultiShortmap *map, | ||
246 | const struct GNUNET_PeerIdentity *key) | ||
247 | { | ||
248 | unsigned int kx; | ||
249 | |||
250 | GNUNET_assert (NULL != map); | ||
251 | GNUNET_memcpy (&kx, key, sizeof (kx)); | ||
252 | return kx % map->map_length; | ||
253 | } | ||
254 | |||
255 | |||
256 | /** | ||
257 | * Get the number of key-value pairs in the map. | ||
258 | * | ||
259 | * @param map the map | ||
260 | * @return the number of key value pairs | ||
261 | */ | ||
262 | unsigned int | ||
263 | GNUNET_CONTAINER_multishortmap_size (const struct GNUNET_CONTAINER_MultiShortmap *map) | ||
264 | { | ||
265 | return map->size; | ||
266 | } | ||
267 | |||
268 | |||
269 | /** | ||
270 | * Given a key find a value in the map matching the key. | ||
271 | * | ||
272 | * @param map the map | ||
273 | * @param key what to look for | ||
274 | * @return NULL if no value was found; note that | ||
275 | * this is indistinguishable from values that just | ||
276 | * happen to be NULL; use "contains" to test for | ||
277 | * key-value pairs with value NULL | ||
278 | */ | ||
279 | void * | ||
280 | GNUNET_CONTAINER_multishortmap_get (const struct GNUNET_CONTAINER_MultiShortmap *map, | ||
281 | const struct GNUNET_PeerIdentity *key) | ||
282 | { | ||
283 | union MapEntry me; | ||
284 | |||
285 | me = map->map[idx_of (map, key)]; | ||
286 | if (map->use_small_entries) | ||
287 | { | ||
288 | struct SmallMapEntry *sme; | ||
289 | |||
290 | for (sme = me.sme; NULL != sme; sme = sme->next) | ||
291 | if (0 == memcmp (key, sme->key, sizeof (struct GNUNET_PeerIdentity))) | ||
292 | return sme->value; | ||
293 | } | ||
294 | else | ||
295 | { | ||
296 | struct BigMapEntry *bme; | ||
297 | |||
298 | for (bme = me.bme; NULL != bme; bme = bme->next) | ||
299 | if (0 == memcmp (key, &bme->key, sizeof (struct GNUNET_PeerIdentity))) | ||
300 | return bme->value; | ||
301 | } | ||
302 | return NULL; | ||
303 | } | ||
304 | |||
305 | |||
306 | /** | ||
307 | * Iterate over all entries in the map. | ||
308 | * | ||
309 | * @param map the map | ||
310 | * @param it function to call on each entry | ||
311 | * @param it_cls extra argument to @a it | ||
312 | * @return the number of key value pairs processed, | ||
313 | * #GNUNET_SYSERR if it aborted iteration | ||
314 | */ | ||
315 | int | ||
316 | GNUNET_CONTAINER_multishortmap_iterate (const struct GNUNET_CONTAINER_MultiShortmap *map, | ||
317 | GNUNET_CONTAINER_ShortmapIterator it, | ||
318 | void *it_cls) | ||
319 | { | ||
320 | int count; | ||
321 | unsigned int i; | ||
322 | union MapEntry me; | ||
323 | struct GNUNET_PeerIdentity kc; | ||
324 | |||
325 | count = 0; | ||
326 | GNUNET_assert (NULL != map); | ||
327 | for (i = 0; i < map->map_length; i++) | ||
328 | { | ||
329 | me = map->map[i]; | ||
330 | if (map->use_small_entries) | ||
331 | { | ||
332 | struct SmallMapEntry *sme; | ||
333 | struct SmallMapEntry *nxt; | ||
334 | |||
335 | nxt = me.sme; | ||
336 | while (NULL != (sme = nxt)) | ||
337 | { | ||
338 | nxt = sme->next; | ||
339 | if (NULL != it) | ||
340 | { | ||
341 | if (GNUNET_OK != it (it_cls, sme->key, sme->value)) | ||
342 | return GNUNET_SYSERR; | ||
343 | } | ||
344 | count++; | ||
345 | } | ||
346 | } | ||
347 | else | ||
348 | { | ||
349 | struct BigMapEntry *bme; | ||
350 | struct BigMapEntry *nxt; | ||
351 | |||
352 | nxt = me.bme; | ||
353 | while (NULL != (bme = nxt)) | ||
354 | { | ||
355 | nxt = bme->next; | ||
356 | if (NULL != it) | ||
357 | { | ||
358 | kc = bme->key; | ||
359 | if (GNUNET_OK != it (it_cls, &kc, bme->value)) | ||
360 | return GNUNET_SYSERR; | ||
361 | } | ||
362 | count++; | ||
363 | } | ||
364 | } | ||
365 | } | ||
366 | return count; | ||
367 | } | ||
368 | |||
369 | |||
370 | /** | ||
371 | * 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 | ||
373 | * will be removed. | ||
374 | * | ||
375 | * @param map the map | ||
376 | * @param key key of the key-value pair | ||
377 | * @param value value of the key-value pair | ||
378 | * @return #GNUNET_YES on success, #GNUNET_NO if the key-value pair | ||
379 | * is not in the map | ||
380 | */ | ||
381 | int | ||
382 | GNUNET_CONTAINER_multishortmap_remove (struct GNUNET_CONTAINER_MultiShortmap *map, | ||
383 | const struct GNUNET_PeerIdentity *key, | ||
384 | const void *value) | ||
385 | { | ||
386 | union MapEntry me; | ||
387 | unsigned int i; | ||
388 | |||
389 | map->modification_counter++; | ||
390 | |||
391 | i = idx_of (map, key); | ||
392 | me = map->map[i]; | ||
393 | if (map->use_small_entries) | ||
394 | { | ||
395 | struct SmallMapEntry *sme; | ||
396 | struct SmallMapEntry *p; | ||
397 | |||
398 | p = NULL; | ||
399 | for (sme = me.sme; NULL != sme; sme = sme->next) | ||
400 | { | ||
401 | if ((0 == memcmp (key, sme->key, sizeof (struct GNUNET_PeerIdentity))) && | ||
402 | (value == sme->value)) | ||
403 | { | ||
404 | if (NULL == p) | ||
405 | map->map[i].sme = sme->next; | ||
406 | else | ||
407 | p->next = sme->next; | ||
408 | GNUNET_free (sme); | ||
409 | map->size--; | ||
410 | return GNUNET_YES; | ||
411 | } | ||
412 | p = sme; | ||
413 | } | ||
414 | } | ||
415 | else | ||
416 | { | ||
417 | struct BigMapEntry *bme; | ||
418 | struct BigMapEntry *p; | ||
419 | |||
420 | p = NULL; | ||
421 | for (bme = me.bme; NULL != bme; bme = bme->next) | ||
422 | { | ||
423 | if ((0 == memcmp (key, &bme->key, sizeof (struct GNUNET_PeerIdentity))) && | ||
424 | (value == bme->value)) | ||
425 | { | ||
426 | if (NULL == p) | ||
427 | map->map[i].bme = bme->next; | ||
428 | else | ||
429 | p->next = bme->next; | ||
430 | GNUNET_free (bme); | ||
431 | map->size--; | ||
432 | return GNUNET_YES; | ||
433 | } | ||
434 | p = bme; | ||
435 | } | ||
436 | } | ||
437 | return GNUNET_NO; | ||
438 | } | ||
439 | |||
440 | |||
441 | /** | ||
442 | * Remove all entries for the given key from the map. | ||
443 | * Note that the values would not be "freed". | ||
444 | * | ||
445 | * @param map the map | ||
446 | * @param key identifies values to be removed | ||
447 | * @return number of values removed | ||
448 | */ | ||
449 | int | ||
450 | GNUNET_CONTAINER_multishortmap_remove_all (struct GNUNET_CONTAINER_MultiShortmap *map, | ||
451 | const struct GNUNET_PeerIdentity *key) | ||
452 | { | ||
453 | union MapEntry me; | ||
454 | unsigned int i; | ||
455 | int ret; | ||
456 | |||
457 | map->modification_counter++; | ||
458 | |||
459 | ret = 0; | ||
460 | i = idx_of (map, key); | ||
461 | me = map->map[i]; | ||
462 | if (map->use_small_entries) | ||
463 | { | ||
464 | struct SmallMapEntry *sme; | ||
465 | struct SmallMapEntry *p; | ||
466 | |||
467 | p = NULL; | ||
468 | sme = me.sme; | ||
469 | while (NULL != sme) | ||
470 | { | ||
471 | if (0 == memcmp (key, sme->key, sizeof (struct GNUNET_PeerIdentity))) | ||
472 | { | ||
473 | if (NULL == p) | ||
474 | map->map[i].sme = sme->next; | ||
475 | else | ||
476 | p->next = sme->next; | ||
477 | GNUNET_free (sme); | ||
478 | map->size--; | ||
479 | if (NULL == p) | ||
480 | sme = map->map[i].sme; | ||
481 | else | ||
482 | sme = p->next; | ||
483 | ret++; | ||
484 | } | ||
485 | else | ||
486 | { | ||
487 | p = sme; | ||
488 | sme = sme->next; | ||
489 | } | ||
490 | } | ||
491 | } | ||
492 | else | ||
493 | { | ||
494 | struct BigMapEntry *bme; | ||
495 | struct BigMapEntry *p; | ||
496 | |||
497 | p = NULL; | ||
498 | bme = me.bme; | ||
499 | while (NULL != bme) | ||
500 | { | ||
501 | if (0 == memcmp (key, &bme->key, sizeof (struct GNUNET_PeerIdentity))) | ||
502 | { | ||
503 | if (NULL == p) | ||
504 | map->map[i].bme = bme->next; | ||
505 | else | ||
506 | p->next = bme->next; | ||
507 | GNUNET_free (bme); | ||
508 | map->size--; | ||
509 | if (NULL == p) | ||
510 | bme = map->map[i].bme; | ||
511 | else | ||
512 | bme = p->next; | ||
513 | ret++; | ||
514 | } | ||
515 | else | ||
516 | { | ||
517 | p = bme; | ||
518 | bme = bme->next; | ||
519 | } | ||
520 | } | ||
521 | } | ||
522 | return ret; | ||
523 | } | ||
524 | |||
525 | |||
526 | /** | ||
527 | * Check if the map contains any value under the given | ||
528 | * key (including values that are NULL). | ||
529 | * | ||
530 | * @param map the map | ||
531 | * @param key the key to test if a value exists for it | ||
532 | * @return #GNUNET_YES if such a value exists, | ||
533 | * #GNUNET_NO if not | ||
534 | */ | ||
535 | int | ||
536 | GNUNET_CONTAINER_multishortmap_contains (const struct GNUNET_CONTAINER_MultiShortmap *map, | ||
537 | const struct GNUNET_PeerIdentity *key) | ||
538 | { | ||
539 | union MapEntry me; | ||
540 | |||
541 | me = map->map[idx_of (map, key)]; | ||
542 | if (map->use_small_entries) | ||
543 | { | ||
544 | struct SmallMapEntry *sme; | ||
545 | |||
546 | for (sme = me.sme; NULL != sme; sme = sme->next) | ||
547 | if (0 == memcmp (key, sme->key, sizeof (struct GNUNET_PeerIdentity))) | ||
548 | return GNUNET_YES; | ||
549 | } | ||
550 | else | ||
551 | { | ||
552 | struct BigMapEntry *bme; | ||
553 | |||
554 | for (bme = me.bme; NULL != bme; bme = bme->next) | ||
555 | if (0 == memcmp (key, &bme->key, sizeof (struct GNUNET_PeerIdentity))) | ||
556 | return GNUNET_YES; | ||
557 | } | ||
558 | return GNUNET_NO; | ||
559 | } | ||
560 | |||
561 | |||
562 | /** | ||
563 | * Check if the map contains the given value under the given | ||
564 | * key. | ||
565 | * | ||
566 | * @param map the map | ||
567 | * @param key the key to test if a value exists for it | ||
568 | * @param value value to test for | ||
569 | * @return #GNUNET_YES if such a value exists, | ||
570 | * #GNUNET_NO if not | ||
571 | */ | ||
572 | int | ||
573 | GNUNET_CONTAINER_multishortmap_contains_value (const struct GNUNET_CONTAINER_MultiShortmap *map, | ||
574 | const struct GNUNET_PeerIdentity *key, | ||
575 | const void *value) | ||
576 | { | ||
577 | union MapEntry me; | ||
578 | |||
579 | me = map->map[idx_of (map, key)]; | ||
580 | if (map->use_small_entries) | ||
581 | { | ||
582 | struct SmallMapEntry *sme; | ||
583 | |||
584 | for (sme = me.sme; NULL != sme; sme = sme->next) | ||
585 | if ( (0 == memcmp (key, sme->key, sizeof (struct GNUNET_PeerIdentity))) && | ||
586 | (sme->value == value) ) | ||
587 | return GNUNET_YES; | ||
588 | } | ||
589 | else | ||
590 | { | ||
591 | struct BigMapEntry *bme; | ||
592 | |||
593 | for (bme = me.bme; NULL != bme; bme = bme->next) | ||
594 | if ( (0 == memcmp (key, &bme->key, sizeof (struct GNUNET_PeerIdentity))) && | ||
595 | (bme->value == value) ) | ||
596 | return GNUNET_YES; | ||
597 | } | ||
598 | return GNUNET_NO; | ||
599 | } | ||
600 | |||
601 | |||
602 | /** | ||
603 | * Grow the given map to a more appropriate size. | ||
604 | * | ||
605 | * @param map the hash map to grow | ||
606 | */ | ||
607 | static void | ||
608 | grow (struct GNUNET_CONTAINER_MultiShortmap *map) | ||
609 | { | ||
610 | union MapEntry *old_map; | ||
611 | union MapEntry *new_map; | ||
612 | unsigned int old_len; | ||
613 | unsigned int new_len; | ||
614 | unsigned int idx; | ||
615 | unsigned int i; | ||
616 | |||
617 | map->modification_counter++; | ||
618 | |||
619 | old_map = map->map; | ||
620 | old_len = map->map_length; | ||
621 | new_len = old_len * 2; | ||
622 | new_map = GNUNET_malloc (sizeof (union MapEntry) * new_len); | ||
623 | map->map_length = new_len; | ||
624 | map->map = new_map; | ||
625 | for (i = 0; i < old_len; i++) | ||
626 | { | ||
627 | if (map->use_small_entries) | ||
628 | { | ||
629 | struct SmallMapEntry *sme; | ||
630 | |||
631 | while (NULL != (sme = old_map[i].sme)) | ||
632 | { | ||
633 | old_map[i].sme = sme->next; | ||
634 | idx = idx_of (map, sme->key); | ||
635 | sme->next = new_map[idx].sme; | ||
636 | new_map[idx].sme = sme; | ||
637 | } | ||
638 | } | ||
639 | else | ||
640 | { | ||
641 | struct BigMapEntry *bme; | ||
642 | |||
643 | while (NULL != (bme = old_map[i].bme)) | ||
644 | { | ||
645 | old_map[i].bme = bme->next; | ||
646 | idx = idx_of (map, &bme->key); | ||
647 | bme->next = new_map[idx].bme; | ||
648 | new_map[idx].bme = bme; | ||
649 | } | ||
650 | } | ||
651 | } | ||
652 | GNUNET_free (old_map); | ||
653 | } | ||
654 | |||
655 | |||
656 | /** | ||
657 | * Store a key-value pair in the map. | ||
658 | * | ||
659 | * @param map the map | ||
660 | * @param key key to use | ||
661 | * @param value value to use | ||
662 | * @param opt options for put | ||
663 | * @return #GNUNET_OK on success, | ||
664 | * #GNUNET_NO if a value was replaced (with REPLACE) | ||
665 | * #GNUNET_SYSERR if GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY was the option and the | ||
666 | * value already exists | ||
667 | */ | ||
668 | int | ||
669 | GNUNET_CONTAINER_multishortmap_put (struct GNUNET_CONTAINER_MultiShortmap *map, | ||
670 | const struct GNUNET_PeerIdentity *key, | ||
671 | void *value, | ||
672 | enum GNUNET_CONTAINER_MultiHashMapOption opt) | ||
673 | { | ||
674 | union MapEntry me; | ||
675 | unsigned int i; | ||
676 | |||
677 | i = idx_of (map, key); | ||
678 | if ((opt != GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE) && | ||
679 | (opt != GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_FAST)) | ||
680 | { | ||
681 | me = map->map[i]; | ||
682 | if (map->use_small_entries) | ||
683 | { | ||
684 | struct SmallMapEntry *sme; | ||
685 | |||
686 | for (sme = me.sme; NULL != sme; sme = sme->next) | ||
687 | if (0 == memcmp (key, sme->key, sizeof (struct GNUNET_PeerIdentity))) | ||
688 | { | ||
689 | if (opt == GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY) | ||
690 | return GNUNET_SYSERR; | ||
691 | sme->value = value; | ||
692 | return GNUNET_NO; | ||
693 | } | ||
694 | } | ||
695 | else | ||
696 | { | ||
697 | struct BigMapEntry *bme; | ||
698 | |||
699 | for (bme = me.bme; NULL != bme; bme = bme->next) | ||
700 | if (0 == memcmp (key, &bme->key, sizeof (struct GNUNET_PeerIdentity))) | ||
701 | { | ||
702 | if (opt == GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY) | ||
703 | return GNUNET_SYSERR; | ||
704 | bme->value = value; | ||
705 | return GNUNET_NO; | ||
706 | } | ||
707 | } | ||
708 | } | ||
709 | if (map->size / 3 >= map->map_length / 4) | ||
710 | { | ||
711 | grow (map); | ||
712 | i = idx_of (map, key); | ||
713 | } | ||
714 | if (map->use_small_entries) | ||
715 | { | ||
716 | struct SmallMapEntry *sme; | ||
717 | |||
718 | sme = GNUNET_new (struct SmallMapEntry); | ||
719 | sme->key = key; | ||
720 | sme->value = value; | ||
721 | sme->next = map->map[i].sme; | ||
722 | map->map[i].sme = sme; | ||
723 | } | ||
724 | else | ||
725 | { | ||
726 | struct BigMapEntry *bme; | ||
727 | |||
728 | bme = GNUNET_new (struct BigMapEntry); | ||
729 | bme->key = *key; | ||
730 | bme->value = value; | ||
731 | bme->next = map->map[i].bme; | ||
732 | map->map[i].bme = bme; | ||
733 | } | ||
734 | map->size++; | ||
735 | return GNUNET_OK; | ||
736 | } | ||
737 | |||
738 | |||
739 | /** | ||
740 | * Iterate over all entries in the map that match a particular key. | ||
741 | * | ||
742 | * @param map the map | ||
743 | * @param key key that the entries must correspond to | ||
744 | * @param it function to call on each entry | ||
745 | * @param it_cls extra argument to @a it | ||
746 | * @return the number of key value pairs processed, | ||
747 | * #GNUNET_SYSERR if it aborted iteration | ||
748 | */ | ||
749 | int | ||
750 | GNUNET_CONTAINER_multishortmap_get_multiple (const struct GNUNET_CONTAINER_MultiShortmap *map, | ||
751 | const struct GNUNET_PeerIdentity *key, | ||
752 | GNUNET_CONTAINER_ShortmapIterator it, | ||
753 | void *it_cls) | ||
754 | { | ||
755 | int count; | ||
756 | union MapEntry me; | ||
757 | |||
758 | count = 0; | ||
759 | me = map->map[idx_of (map, key)]; | ||
760 | if (map->use_small_entries) | ||
761 | { | ||
762 | struct SmallMapEntry *sme; | ||
763 | struct SmallMapEntry *nxt; | ||
764 | |||
765 | nxt = me.sme; | ||
766 | while (NULL != (sme = nxt)) | ||
767 | { | ||
768 | nxt = sme->next; | ||
769 | if (0 != memcmp (key, sme->key, sizeof (struct GNUNET_PeerIdentity))) | ||
770 | continue; | ||
771 | if ((it != NULL) && (GNUNET_OK != it (it_cls, key, sme->value))) | ||
772 | return GNUNET_SYSERR; | ||
773 | count++; | ||
774 | } | ||
775 | } | ||
776 | else | ||
777 | { | ||
778 | struct BigMapEntry *bme; | ||
779 | struct BigMapEntry *nxt; | ||
780 | |||
781 | nxt = me.bme; | ||
782 | while (NULL != (bme = nxt)) | ||
783 | { | ||
784 | nxt = bme->next; | ||
785 | if (0 != memcmp (key, &bme->key, sizeof (struct GNUNET_PeerIdentity))) | ||
786 | continue; | ||
787 | if ((it != NULL) && (GNUNET_OK != it (it_cls, key, bme->value))) | ||
788 | return GNUNET_SYSERR; | ||
789 | count++; | ||
790 | } | ||
791 | } | ||
792 | return count; | ||
793 | } | ||
794 | |||
795 | |||
796 | /** | ||
797 | * @ingroup hashmap | ||
798 | * Call @a it on a random value from the map, or not at all | ||
799 | * if the map is empty. Note that this function has linear | ||
800 | * complexity (in the size of the map). | ||
801 | * | ||
802 | * @param map the map | ||
803 | * @param it function to call on a random entry | ||
804 | * @param it_cls extra argument to @a it | ||
805 | * @return the number of key value pairs processed, zero or one. | ||
806 | */ | ||
807 | unsigned int | ||
808 | GNUNET_CONTAINER_multishortmap_get_random (const struct GNUNET_CONTAINER_MultiShortmap *map, | ||
809 | GNUNET_CONTAINER_ShortmapIterator it, | ||
810 | void *it_cls) | ||
811 | { | ||
812 | unsigned int off; | ||
813 | unsigned int idx; | ||
814 | union MapEntry me; | ||
815 | |||
816 | if (0 == map->size) | ||
817 | return 0; | ||
818 | if (NULL == it) | ||
819 | return 1; | ||
820 | off = GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_NONCE, | ||
821 | map->size); | ||
822 | for (idx = 0; idx < map->map_length; idx++) | ||
823 | { | ||
824 | me = map->map[idx]; | ||
825 | if (map->use_small_entries) | ||
826 | { | ||
827 | struct SmallMapEntry *sme; | ||
828 | struct SmallMapEntry *nxt; | ||
829 | |||
830 | nxt = me.sme; | ||
831 | while (NULL != (sme = nxt)) | ||
832 | { | ||
833 | nxt = sme->next; | ||
834 | if (0 == off) | ||
835 | { | ||
836 | if (GNUNET_OK != it (it_cls, | ||
837 | sme->key, | ||
838 | sme->value)) | ||
839 | return GNUNET_SYSERR; | ||
840 | return 1; | ||
841 | } | ||
842 | off--; | ||
843 | } | ||
844 | } | ||
845 | else | ||
846 | { | ||
847 | struct BigMapEntry *bme; | ||
848 | struct BigMapEntry *nxt; | ||
849 | |||
850 | nxt = me.bme; | ||
851 | while (NULL != (bme = nxt)) | ||
852 | { | ||
853 | nxt = bme->next; | ||
854 | if (0 == off) | ||
855 | { | ||
856 | if (GNUNET_OK != it (it_cls, | ||
857 | &bme->key, bme->value)) | ||
858 | return GNUNET_SYSERR; | ||
859 | return 1; | ||
860 | } | ||
861 | off--; | ||
862 | } | ||
863 | } | ||
864 | } | ||
865 | GNUNET_break (0); | ||
866 | return GNUNET_SYSERR; | ||
867 | } | ||
868 | |||
869 | |||
870 | /** | ||
871 | * Create an iterator for a multishortmap. | ||
872 | * The iterator can be used to retrieve all the elements in the multishortmap | ||
873 | * one by one, without having to handle all elements at once (in contrast to | ||
874 | * #GNUNET_CONTAINER_multishortmap_iterate). Note that the iterator can not be | ||
875 | * used anymore if elements have been removed from 'map' after the creation of | ||
876 | * the iterator, or 'map' has been destroyed. Adding elements to 'map' may | ||
877 | * result in skipped or repeated elements. | ||
878 | * | ||
879 | * @param map the map to create an iterator for | ||
880 | * @return an iterator over the given multishortmap 'map' | ||
881 | */ | ||
882 | struct GNUNET_CONTAINER_MultiShortmapIterator * | ||
883 | GNUNET_CONTAINER_multishortmap_iterator_create (const struct GNUNET_CONTAINER_MultiShortmap *map) | ||
884 | { | ||
885 | struct GNUNET_CONTAINER_MultiShortmapIterator *iter; | ||
886 | |||
887 | iter = GNUNET_new (struct GNUNET_CONTAINER_MultiShortmapIterator); | ||
888 | iter->map = map; | ||
889 | iter->modification_counter = map->modification_counter; | ||
890 | iter->me = map->map[0]; | ||
891 | return iter; | ||
892 | } | ||
893 | |||
894 | |||
895 | /** | ||
896 | * Retrieve the next element from the hash map at the iterator's position. | ||
897 | * If there are no elements left, GNUNET_NO is returned, and 'key' and 'value' | ||
898 | * are not modified. | ||
899 | * This operation is only allowed if no elements have been removed from the | ||
900 | * multishortmap since the creation of 'iter', and the map has not been destroyed. | ||
901 | * Adding elements may result in repeating or skipping elements. | ||
902 | * | ||
903 | * @param iter the iterator to get the next element from | ||
904 | * @param key pointer to store the key in, can be NULL | ||
905 | * @param value pointer to store the value in, can be NULL | ||
906 | * @return #GNUNET_YES we returned an element, | ||
907 | * #GNUNET_NO if we are out of elements | ||
908 | */ | ||
909 | int | ||
910 | GNUNET_CONTAINER_multishortmap_iterator_next (struct GNUNET_CONTAINER_MultiShortmapIterator *iter, | ||
911 | struct GNUNET_PeerIdentity *key, const void **value) | ||
912 | { | ||
913 | /* make sure the map has not been modified */ | ||
914 | GNUNET_assert (iter->modification_counter == iter->map->modification_counter); | ||
915 | |||
916 | /* look for the next entry, skipping empty buckets */ | ||
917 | while (1) | ||
918 | { | ||
919 | if (iter->idx >= iter->map->map_length) | ||
920 | return GNUNET_NO; | ||
921 | if (GNUNET_YES == iter->map->use_small_entries) | ||
922 | { | ||
923 | if (NULL != iter->me.sme) | ||
924 | { | ||
925 | if (NULL != key) | ||
926 | *key = *iter->me.sme->key; | ||
927 | if (NULL != value) | ||
928 | *value = iter->me.sme->value; | ||
929 | iter->me.sme = iter->me.sme->next; | ||
930 | return GNUNET_YES; | ||
931 | } | ||
932 | } | ||
933 | else | ||
934 | { | ||
935 | if (NULL != iter->me.bme) | ||
936 | { | ||
937 | if (NULL != key) | ||
938 | *key = iter->me.bme->key; | ||
939 | if (NULL != value) | ||
940 | *value = iter->me.bme->value; | ||
941 | iter->me.bme = iter->me.bme->next; | ||
942 | return GNUNET_YES; | ||
943 | } | ||
944 | } | ||
945 | iter->idx += 1; | ||
946 | if (iter->idx < iter->map->map_length) | ||
947 | iter->me = iter->map->map[iter->idx]; | ||
948 | } | ||
949 | } | ||
950 | |||
951 | |||
952 | /** | ||
953 | * Destroy a multishortmap iterator. | ||
954 | * | ||
955 | * @param iter the iterator to destroy | ||
956 | */ | ||
957 | void | ||
958 | GNUNET_CONTAINER_multishortmap_iterator_destroy (struct GNUNET_CONTAINER_MultiShortmapIterator *iter) | ||
959 | { | ||
960 | GNUNET_free (iter); | ||
961 | } | ||
962 | |||
963 | |||
964 | /* end of container_multishortmap.c */ | ||