GNUnet 0.21.0
container_multipeermap.c
Go to the documentation of this file.
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 */
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
39#define NEXT_CACHE_SIZE 16
40
44struct BigMapEntry
45{
49 void *value;
50
54 struct BigMapEntry *next;
55
60};
61
62
66struct SmallMapEntry
67{
71 void *value;
72
76 struct SmallMapEntry *next;
77
81 const struct GNUNET_PeerIdentity *key;
82};
83
84
88union MapEntry
89{
93 struct SmallMapEntry *sme;
94
98 struct BigMapEntry *bme;
99};
100
101
106{
110 union MapEntry *map;
111
115 unsigned int size;
116
120 unsigned int map_length;
121
127
133
140
145 unsigned int next_cache_off;
146};
147
148
154{
159
163 unsigned int idx;
164
170
175};
176
177
180 int do_not_copy_keys)
181{
183
184 GNUNET_assert (len > 0);
186 map->map = GNUNET_malloc_large (len * sizeof(union MapEntry));
187 if (NULL == map->map)
188 {
190 return NULL;
191 }
192 map->map_length = len;
193 map->use_small_entries = do_not_copy_keys;
194 return map;
195}
196
197
198void
201{
203 for (unsigned int i = 0; i < map->map_length; i++)
204 {
205 union MapEntry me;
206
207 me = map->map[i];
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 }
237}
238
239
247static unsigned int
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
259unsigned int
262{
263 return map->size;
264}
265
266
267void *
270 const struct GNUNET_PeerIdentity *key)
271{
272 union MapEntry me;
273
274 me = map->map[idx_of (map, key)];
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
291int
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);
306 for (unsigned int i = 0; i < map->map_length; i++)
307 {
308 me = map->map[i];
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 {
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 {
342 return GNUNET_SYSERR;
343 }
344 }
345 count++;
346 }
347 }
348 }
350 return count;
351}
352
353
361static void
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
378static void
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
390 const struct GNUNET_PeerIdentity *key,
391 const void *value)
392{
393 union MapEntry me;
394 unsigned int i;
395
397 i = idx_of (map, key);
398 me = map->map[i];
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;
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;
432 GNUNET_free (bme);
433 map->size--;
434 return GNUNET_YES;
435 }
436 p = bme;
437 }
438 }
439 return GNUNET_NO;
440}
441
442
443int
446 const struct GNUNET_PeerIdentity *key)
447{
448 union MapEntry me;
449 unsigned int i;
450 int ret;
451
453
454 ret = 0;
455 i = idx_of (map, key);
456 me = map->map[i];
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;
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;
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
526 const struct GNUNET_PeerIdentity *key)
527{
528 union MapEntry me;
529
530 me = map->map[idx_of (map, key)];
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
550 const struct GNUNET_PeerIdentity *key,
551 const void *value)
552{
553 union MapEntry me;
554
555 me = map->map[idx_of (map, key)];
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
577static void
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 */
598 map->map_length = new_len;
599 map->map = new_map;
600 for (unsigned int i = 0; i < old_len; i++)
601 {
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
631int
633 const struct GNUNET_PeerIdentity *key,
634 void *value,
636{
637 union MapEntry me;
638 unsigned int i;
639
640 i = idx_of (map, key);
643 {
644 me = map->map[i];
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 {
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 {
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 }
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
702int
705 const struct GNUNET_PeerIdentity *key,
707 void *it_cls)
708{
709 int count;
710 union MapEntry me;
711 union MapEntry *ce;
712
715 count = 0;
716 me = map->map[idx_of (map, key)];
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 {
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 {
748 return GNUNET_SYSERR;
749 }
750 count++;
751 }
752 }
754 return count;
755}
756
757
769unsigned int
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;
783 for (unsigned int idx = 0; idx < map->map_length; idx++)
784 {
785 me = map->map[idx];
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
831{
833
835 iter->map = map;
837 iter->me = map->map[0];
838 return iter;
839}
840
841
845 struct GNUNET_PeerIdentity *key,
846 const void **value)
847{
848 /* make sure the map has not been modified */
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
887void
890{
891 GNUNET_free (iter);
892}
893
894
895/* end of container_multipeermap.c */
#define NEXT_CACHE_SIZE
Maximum recursion depth for callbacks of GNUNET_CONTAINER_multihashmap_get_multiple() themselves s ag...
static void grow(struct GNUNET_CONTAINER_MultiPeerMap *map)
Grow the given map to a more appropriate size.
static void update_next_cache_sme(struct GNUNET_CONTAINER_MultiPeerMap *map, const struct SmallMapEntry *sme)
We are about to free() the sme, make sure it is not in the list of next values for any iterator in th...
static unsigned int idx_of(const struct GNUNET_CONTAINER_MultiPeerMap *map, const struct GNUNET_PeerIdentity *key)
Compute the index of the bucket for the given key.
static void update_next_cache_bme(struct GNUNET_CONTAINER_MultiPeerMap *map, const struct BigMapEntry *bme)
We are about to free() the bme, make sure it is not in the list of next values for any iterator in th...
static int ret
Final status code.
Definition: gnunet-arm.c:94
static GNUNET_NETWORK_STRUCT_END struct GNUNET_PeerIdentity me
Our own peer identity.
struct GNUNET_HashCode key
The key used in the DHT.
static char * value
Value of the record to add/remove.
static struct GNUNET_OS_Process * p
Helper process we started.
Definition: gnunet-uri.c:38
uint32_t GNUNET_CRYPTO_random_u32(enum GNUNET_CRYPTO_Quality mode, uint32_t i)
Produce a random value.
@ GNUNET_CRYPTO_QUALITY_NONCE
Randomness for IVs etc.
void * GNUNET_CONTAINER_multipeermap_get(const struct GNUNET_CONTAINER_MultiPeerMap *map, const struct GNUNET_PeerIdentity *key)
Given a key find a value in the map matching the key.
struct GNUNET_CONTAINER_MultiPeerMapIterator * GNUNET_CONTAINER_multipeermap_iterator_create(const struct GNUNET_CONTAINER_MultiPeerMap *map)
Create an iterator for a multihashmap.
enum GNUNET_GenericReturnValue GNUNET_CONTAINER_multipeermap_contains(const struct GNUNET_CONTAINER_MultiPeerMap *map, const struct GNUNET_PeerIdentity *key)
Check if the map contains any value under the given key (including values that are NULL).
enum GNUNET_GenericReturnValue(* GNUNET_CONTAINER_PeerMapIterator)(void *cls, const struct GNUNET_PeerIdentity *key, void *value)
Iterator over hash map entries.
void GNUNET_CONTAINER_multipeermap_destroy(struct GNUNET_CONTAINER_MultiPeerMap *map)
Destroy a hash map.
enum GNUNET_GenericReturnValue GNUNET_CONTAINER_multipeermap_contains_value(const struct GNUNET_CONTAINER_MultiPeerMap *map, const struct GNUNET_PeerIdentity *key, const void *value)
Check if the map contains the given value under the given key.
int GNUNET_CONTAINER_multipeermap_iterate(struct GNUNET_CONTAINER_MultiPeerMap *map, GNUNET_CONTAINER_PeerMapIterator it, void *it_cls)
Iterate over all entries in the map.
unsigned int GNUNET_CONTAINER_multipeermap_get_random(const struct GNUNET_CONTAINER_MultiPeerMap *map, GNUNET_CONTAINER_PeerMapIterator it, void *it_cls)
Call it on a random value from the map, or not at all if the map is empty.
void GNUNET_CONTAINER_multipeermap_iterator_destroy(struct GNUNET_CONTAINER_MultiPeerMapIterator *iter)
Destroy a multipeermap iterator.
int GNUNET_CONTAINER_multipeermap_remove_all(struct GNUNET_CONTAINER_MultiPeerMap *map, const struct GNUNET_PeerIdentity *key)
Remove all entries for the given key from the map.
GNUNET_CONTAINER_MultiHashMapOption
Options for storing values in the HashMap.
struct GNUNET_CONTAINER_MultiPeerMap * GNUNET_CONTAINER_multipeermap_create(unsigned int len, int do_not_copy_keys)
Create a multi peer map (hash map for public keys of peers).
int GNUNET_CONTAINER_multipeermap_get_multiple(struct GNUNET_CONTAINER_MultiPeerMap *map, const struct GNUNET_PeerIdentity *key, GNUNET_CONTAINER_PeerMapIterator it, void *it_cls)
Iterate over all entries in the map that match a particular key.
unsigned int GNUNET_CONTAINER_multipeermap_size(const struct GNUNET_CONTAINER_MultiPeerMap *map)
Get the number of key-value pairs in the map.
int GNUNET_CONTAINER_multipeermap_put(struct GNUNET_CONTAINER_MultiPeerMap *map, const struct GNUNET_PeerIdentity *key, void *value, enum GNUNET_CONTAINER_MultiHashMapOption opt)
Store a key-value pair in the map.
enum GNUNET_GenericReturnValue GNUNET_CONTAINER_multipeermap_iterator_next(struct GNUNET_CONTAINER_MultiPeerMapIterator *iter, struct GNUNET_PeerIdentity *key, const void **value)
Retrieve the next element from the hash map at the iterator's position.
enum GNUNET_GenericReturnValue GNUNET_CONTAINER_multipeermap_remove(struct GNUNET_CONTAINER_MultiPeerMap *map, const struct GNUNET_PeerIdentity *key, const void *value)
Remove the given key-value pair from the map.
@ GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_FAST
, ' bother checking if a value already exists (faster than GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE...
@ GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE
Allow multiple values with the same key.
@ GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY
There must only be one value per key; storing a value should fail if a value under the same key alrea...
#define GNUNET_memcmp(a, b)
Compare memory in a and b, where both must be of the same pointer type.
#define GNUNET_memcpy(dst, src, n)
Call memcpy() but check for n being 0 first.
GNUNET_GenericReturnValue
Named constants for return values.
@ GNUNET_OK
@ GNUNET_YES
@ GNUNET_NO
@ GNUNET_SYSERR
#define GNUNET_assert(cond)
Use this for fatal errors that cannot be handled.
#define GNUNET_break(cond)
Use this for internal assertion violations that are not fatal (can be handled) but should not occur.
#define GNUNET_malloc_large(size)
Wrapper around malloc.
#define GNUNET_new(type)
Allocate a struct or union of the given type.
#define GNUNET_free(ptr)
Wrapper around free.
static struct GNUNET_CONTAINER_MultiPeerMap * map
Peermap of PeerIdentities to "struct PeerEntry" (for fast lookup).
Definition: peer.c:63
An entry in the hash map with the full key.
struct BigMapEntry * next
If there is a hash collision, we create a linked list.
void * value
Value of the entry.
struct GNUNET_HashCode key
Key for the entry.
unsigned int idx
Current bucket index.
union MapEntry me
Position in the bucket 'idx'.
unsigned int modification_counter
Modification counter as observed on the map when the iterator was created.
const struct GNUNET_CONTAINER_MultiPeerMap * map
Map that we are iterating over.
Internal representation of the hash map.
unsigned int next_cache_off
Offset of next_cache entries in use, must be smaller than NEXT_CACHE_SIZE.
unsigned int map_length
Length of the "map" array.
unsigned int modification_counter
Counts the destructive modifications (grow, remove) to the map, so that iterators can check if they a...
union MapEntry * map
All of our buckets.
int use_small_entries
GNUNET_NO if the map entries are of type 'struct BigMapEntry', GNUNET_YES if the map entries are of t...
unsigned int size
Number of entries in the map.
union MapEntry next_cache[16]
Map entries indicating iteration positions currently in use by GNUNET_CONTAINER_multihashmap_get_mult...
The identity of the host (wraps the signing key of the peer).
An entry in the hash map with just a pointer to the key.
struct SmallMapEntry * next
If there is a hash collision, we create a linked list.
const struct GNUNET_PeerIdentity * key
Key for the entry.
void * value
Value of the entry.
const struct GNUNET_HashCode * key
Key for the entry.
Entry in the map.
struct SmallMapEntry * sme
Variant used if map entries only contain a pointer to the key.
struct BigMapEntry * bme
Variant used if map entries contain the full key.