GNUnet  0.19.4
container_multihashmap.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-multihashmap", __VA_ARGS__)
32 
39 #define NEXT_CACHE_SIZE 16
40 
41 
46 {
50  void *value;
51 
55  struct BigMapEntry *next;
56 
60  struct GNUNET_HashCode key;
61 };
62 
63 
68 {
72  void *value;
73 
78 
82  const struct GNUNET_HashCode *key;
83 };
84 
85 
89 union MapEntry
90 {
94  struct SmallMapEntry *sme;
95 
99  struct BigMapEntry *bme;
100 };
101 
102 
107 {
111  union MapEntry *map;
112 
116  unsigned int size;
117 
121  unsigned int map_length;
122 
128 
133  unsigned int modification_counter;
134 
141 
146  unsigned int next_cache_off;
147 };
148 
149 
155 {
159  union MapEntry me;
160 
164  unsigned int idx;
165 
170  unsigned int modification_counter;
171 
176 };
177 
178 
180 GNUNET_CONTAINER_multihashmap_create (unsigned int len, int do_not_copy_keys)
181 {
183 
184  GNUNET_assert (len > 0);
186  if (len * sizeof(union MapEntry) > GNUNET_MAX_MALLOC_CHECKED)
187  {
188  size_t s;
189  /* application *explicitly* requested very large map, hopefully
190  it checks the return value... */
191  s = len * sizeof(union MapEntry);
192  if ((s / sizeof(union MapEntry)) != len)
193  return NULL; /* integer overflow on multiplication */
194  if (NULL == (hm->map = GNUNET_malloc_large (s)))
195  {
196  /* out of memory */
198  "Out of memory allocating large hash map (%u entries)\n",
199  len);
200  GNUNET_free (hm);
201  return NULL;
202  }
203  }
204  else
205  {
206  hm->map = GNUNET_new_array (len, union MapEntry);
207  }
208  hm->map_length = len;
209  hm->use_small_entries = do_not_copy_keys;
210  return hm;
211 }
212 
213 
214 void
217 {
219  for (unsigned int i = 0; i < map->map_length; i++)
220  {
221  union MapEntry me;
222 
223  me = map->map[i];
224  if (map->use_small_entries)
225  {
226  struct SmallMapEntry *sme;
227  struct SmallMapEntry *nxt;
228 
229  nxt = me.sme;
230  while (NULL != (sme = nxt))
231  {
232  nxt = sme->next;
233  GNUNET_free (sme);
234  }
235  me.sme = NULL;
236  }
237  else
238  {
239  struct BigMapEntry *bme;
240  struct BigMapEntry *nxt;
241 
242  nxt = me.bme;
243  while (NULL != (bme = nxt))
244  {
245  nxt = bme->next;
246  GNUNET_free (bme);
247  }
248  me.bme = NULL;
249  }
250  }
251  GNUNET_free (map->map);
252  GNUNET_free (map);
253 }
254 
255 
263 static unsigned int
265  const struct GNUNET_HashCode *key)
266 {
267  GNUNET_assert (map != NULL);
268  return (*(unsigned int *) key) % map->map_length;
269 }
270 
271 
272 unsigned int
274  const struct GNUNET_CONTAINER_MultiHashMap *map)
275 {
276  return map->size;
277 }
278 
279 
280 void *
282  const struct GNUNET_CONTAINER_MultiHashMap *map,
283  const struct GNUNET_HashCode *key)
284 {
285  union MapEntry me;
286 
287  me = map->map[idx_of (map, key)];
288  if (map->use_small_entries)
289  {
290  struct SmallMapEntry *sme;
291 
292  for (sme = me.sme; NULL != sme; sme = sme->next)
293  if (0 == GNUNET_memcmp (key, sme->key))
294  return sme->value;
295  }
296  else
297  {
298  struct BigMapEntry *bme;
299 
300  for (bme = me.bme; NULL != bme; bme = bme->next)
301  if (0 == GNUNET_memcmp (key, &bme->key))
302  return bme->value;
303  }
304  return NULL;
305 }
306 
307 
308 int
312  void *it_cls)
313 {
314  int count;
315  union MapEntry me;
316  union MapEntry *ce;
317  struct GNUNET_HashCode kc;
318 
319  GNUNET_assert (NULL != map);
320  ce = &map->next_cache[map->next_cache_off];
322  count = 0;
323  for (unsigned i = 0; i < map->map_length; i++)
324  {
325  me = map->map[i];
326  if (map->use_small_entries)
327  {
328  struct SmallMapEntry *sme;
329 
330  ce->sme = me.sme;
331  while (NULL != (sme = ce->sme))
332  {
333  ce->sme = sme->next;
334  if (NULL != it)
335  {
336  if (GNUNET_OK != it (it_cls, sme->key, sme->value))
337  {
339  return GNUNET_SYSERR;
340  }
341  }
342  count++;
343  }
344  }
345  else
346  {
347  struct BigMapEntry *bme;
348 
349  ce->bme = me.bme;
350  while (NULL != (bme = ce->bme))
351  {
352  ce->bme = bme->next;
353  if (NULL != it)
354  {
355  kc = bme->key;
356  if (GNUNET_OK != it (it_cls, &kc, bme->value))
357  {
359  return GNUNET_SYSERR;
360  }
361  }
362  count++;
363  }
364  }
365  }
367  return count;
368 }
369 
370 
378 static void
380  const struct BigMapEntry *bme)
381 {
382  for (unsigned int i = 0; i < map->next_cache_off; i++)
383  if (map->next_cache[i].bme == bme)
384  map->next_cache[i].bme = bme->next;
385 }
386 
387 
395 static void
397  const struct SmallMapEntry *sme)
398 {
399  for (unsigned int i = 0; i < map->next_cache_off; i++)
400  if (map->next_cache[i].sme == sme)
401  map->next_cache[i].sme = sme->next;
402 }
403 
404 
405 int
407  const struct GNUNET_HashCode *key,
408  const void *value)
409 {
410  union MapEntry me;
411  unsigned int i;
412 
414 
415  i = idx_of (map, key);
416  me = map->map[i];
417  if (map->use_small_entries)
418  {
419  struct SmallMapEntry *p;
420 
421  p = NULL;
422  for (struct SmallMapEntry *sme = me.sme; NULL != sme; sme = sme->next)
423  {
424  if ((0 == GNUNET_memcmp (key, sme->key)) && (value == sme->value))
425  {
426  if (NULL == p)
427  map->map[i].sme = sme->next;
428  else
429  p->next = sme->next;
430  update_next_cache_sme (map, sme);
431  GNUNET_free (sme);
432  map->size--;
433  return GNUNET_YES;
434  }
435  p = sme;
436  }
437  }
438  else
439  {
440  struct BigMapEntry *p;
441 
442  p = NULL;
443  for (struct BigMapEntry *bme = me.bme; NULL != bme; bme = bme->next)
444  {
445  if ((0 == GNUNET_memcmp (key, &bme->key)) && (value == bme->value))
446  {
447  if (NULL == p)
448  map->map[i].bme = bme->next;
449  else
450  p->next = bme->next;
451  update_next_cache_bme (map, bme);
452  GNUNET_free (bme);
453  map->size--;
454  return GNUNET_YES;
455  }
456  p = bme;
457  }
458  }
459  return GNUNET_NO;
460 }
461 
462 
463 int
466  const struct GNUNET_HashCode *key)
467 {
468  union MapEntry me;
469  unsigned int i;
470  int ret;
471 
473 
474  ret = 0;
475  i = idx_of (map, key);
476  me = map->map[i];
477  if (map->use_small_entries)
478  {
479  struct SmallMapEntry *sme;
480  struct SmallMapEntry *p;
481 
482  p = NULL;
483  sme = me.sme;
484  while (NULL != sme)
485  {
486  if (0 == GNUNET_memcmp (key, sme->key))
487  {
488  if (NULL == p)
489  map->map[i].sme = sme->next;
490  else
491  p->next = sme->next;
492  update_next_cache_sme (map, sme);
493  GNUNET_free (sme);
494  map->size--;
495  if (NULL == p)
496  sme = map->map[i].sme;
497  else
498  sme = p->next;
499  ret++;
500  }
501  else
502  {
503  p = sme;
504  sme = sme->next;
505  }
506  }
507  }
508  else
509  {
510  struct BigMapEntry *bme;
511  struct BigMapEntry *p;
512 
513  p = NULL;
514  bme = me.bme;
515  while (NULL != bme)
516  {
517  if (0 == GNUNET_memcmp (key, &bme->key))
518  {
519  if (NULL == p)
520  map->map[i].bme = bme->next;
521  else
522  p->next = bme->next;
523  update_next_cache_bme (map, bme);
524  GNUNET_free (bme);
525  map->size--;
526  if (NULL == p)
527  bme = map->map[i].bme;
528  else
529  bme = p->next;
530  ret++;
531  }
532  else
533  {
534  p = bme;
535  bme = bme->next;
536  }
537  }
538  }
539  return ret;
540 }
541 
542 
551 static int
552 remove_all (void *cls, const struct GNUNET_HashCode *key, void *value)
553 {
554  struct GNUNET_CONTAINER_MultiHashMap *map = cls;
555 
558  return GNUNET_OK;
559 }
560 
561 
570 unsigned int
572 {
573  unsigned int ret;
574 
575  ret = map->size;
577  return ret;
578 }
579 
580 
581 int
583  const struct GNUNET_CONTAINER_MultiHashMap *map,
584  const struct GNUNET_HashCode *key)
585 {
586  union MapEntry me;
587 
588  me = map->map[idx_of (map, key)];
589  if (map->use_small_entries)
590  {
591  struct SmallMapEntry *sme;
592 
593  for (sme = me.sme; NULL != sme; sme = sme->next)
594  if (0 == GNUNET_memcmp (key, sme->key))
595  return GNUNET_YES;
596  }
597  else
598  {
599  struct BigMapEntry *bme;
600 
601  for (bme = me.bme; NULL != bme; bme = bme->next)
602  if (0 == GNUNET_memcmp (key, &bme->key))
603  return GNUNET_YES;
604  }
605  return GNUNET_NO;
606 }
607 
608 
609 int
611  const struct GNUNET_CONTAINER_MultiHashMap *map,
612  const struct GNUNET_HashCode *key,
613  const void *value)
614 {
615  union MapEntry me;
616 
617  me = map->map[idx_of (map, key)];
618  if (map->use_small_entries)
619  {
620  struct SmallMapEntry *sme;
621 
622  for (sme = me.sme; NULL != sme; sme = sme->next)
623  if ((0 == GNUNET_memcmp (key, sme->key)) && (sme->value == value))
624  return GNUNET_YES;
625  }
626  else
627  {
628  struct BigMapEntry *bme;
629 
630  for (bme = me.bme; NULL != bme; bme = bme->next)
631  if ((0 == GNUNET_memcmp (key, &bme->key)) && (bme->value == value))
632  return GNUNET_YES;
633  }
634  return GNUNET_NO;
635 }
636 
637 
643 static void
645 {
646  union MapEntry *old_map;
647  union MapEntry *new_map;
648  unsigned int old_len;
649  unsigned int new_len;
650  unsigned int idx;
651 
652  old_map = map->map;
653  old_len = map->map_length;
654  GNUNET_assert (0 != old_len);
655  new_len = old_len * 2;
656  if (0 == new_len) /* 2^31 * 2 == 0 */
657  new_len = old_len; /* never use 0 */
658  if (new_len == old_len)
659  return; /* nothing changed */
660  new_map = GNUNET_malloc_large (new_len * sizeof(union MapEntry));
661  if (NULL == new_map)
662  return; /* grow not possible */
664  map->map_length = new_len;
665  map->map = new_map;
666  for (unsigned int i = 0; i < old_len; i++)
667  {
668  if (map->use_small_entries)
669  {
670  struct SmallMapEntry *sme;
671 
672  while (NULL != (sme = old_map[i].sme))
673  {
674  old_map[i].sme = sme->next;
675  idx = idx_of (map, sme->key);
676  sme->next = new_map[idx].sme;
677  new_map[idx].sme = sme;
678  }
679  }
680  else
681  {
682  struct BigMapEntry *bme;
683 
684  while (NULL != (bme = old_map[i].bme))
685  {
686  old_map[i].bme = bme->next;
687  idx = idx_of (map, &bme->key);
688  bme->next = new_map[idx].bme;
689  new_map[idx].bme = bme;
690  }
691  }
692  }
693  GNUNET_free (old_map);
694 }
695 
696 
709 int
711  const struct GNUNET_HashCode *key,
712  void *value,
714 {
715  union MapEntry me;
716  unsigned int i;
717 
718  i = idx_of (map, key);
721  {
722  me = map->map[i];
723  if (map->use_small_entries)
724  {
725  struct SmallMapEntry *sme;
726 
727  for (sme = me.sme; NULL != sme; sme = sme->next)
728  if (0 == GNUNET_memcmp (key, sme->key))
729  {
731  return GNUNET_SYSERR;
732  sme->value = value;
733  return GNUNET_NO;
734  }
735  }
736  else
737  {
738  struct BigMapEntry *bme;
739 
740  for (bme = me.bme; NULL != bme; bme = bme->next)
741  if (0 == GNUNET_memcmp (key, &bme->key))
742  {
744  return GNUNET_SYSERR;
745  bme->value = value;
746  return GNUNET_NO;
747  }
748  }
749  }
750  if (map->size / 3 >= map->map_length / 4)
751  {
752  grow (map);
753  i = idx_of (map, key);
754  }
755  if (map->use_small_entries)
756  {
757  struct SmallMapEntry *sme;
758 
759  sme = GNUNET_new (struct SmallMapEntry);
760  sme->key = key;
761  sme->value = value;
762  sme->next = map->map[i].sme;
763  map->map[i].sme = sme;
764  }
765  else
766  {
767  struct BigMapEntry *bme;
768 
769  bme = GNUNET_new (struct BigMapEntry);
770  bme->key = *key;
771  bme->value = value;
772  bme->next = map->map[i].bme;
773  map->map[i].bme = bme;
774  }
775  map->size++;
776  return GNUNET_OK;
777 }
778 
779 
780 int
783  const struct GNUNET_HashCode *key,
785  void *it_cls)
786 {
787  int count;
788  union MapEntry *me;
789  union MapEntry *ce;
790 
791  ce = &map->next_cache[map->next_cache_off];
793  count = 0;
794  me = &map->map[idx_of (map, key)];
795  if (map->use_small_entries)
796  {
797  struct SmallMapEntry *sme;
798 
799  ce->sme = me->sme;
800  while (NULL != (sme = ce->sme))
801  {
802  ce->sme = sme->next;
803  if (0 != GNUNET_memcmp (key, sme->key))
804  continue;
805  if ((NULL != it) && (GNUNET_OK != it (it_cls, key, sme->value)))
806  {
808  return GNUNET_SYSERR;
809  }
810  count++;
811  }
812  }
813  else
814  {
815  struct BigMapEntry *bme;
816 
817  ce->bme = me->bme;
818  while (NULL != (bme = ce->bme))
819  {
820  ce->bme = bme->next;
821  if (0 != GNUNET_memcmp (key, &bme->key))
822  continue;
823  if ((NULL != it) && (GNUNET_OK != it (it_cls, key, bme->value)))
824  {
826  return GNUNET_SYSERR;
827  }
828  count++;
829  }
830  }
832  return count;
833 }
834 
835 
847 unsigned int
849  const struct GNUNET_CONTAINER_MultiHashMap *map,
851  void *it_cls)
852 {
853  unsigned int off;
854  unsigned int idx;
855  union MapEntry me;
856 
857  if (0 == map->size)
858  return 0;
859  if (NULL == it)
860  return 1;
862  for (idx = 0; idx < map->map_length; idx++)
863  {
864  me = map->map[idx];
865  if (map->use_small_entries)
866  {
867  struct SmallMapEntry *sme;
868  struct SmallMapEntry *nxt;
869 
870  nxt = me.sme;
871  while (NULL != (sme = nxt))
872  {
873  nxt = sme->next;
874  if (0 == off)
875  {
876  if (GNUNET_OK != it (it_cls, sme->key, sme->value))
877  return GNUNET_SYSERR;
878  return 1;
879  }
880  off--;
881  }
882  }
883  else
884  {
885  struct BigMapEntry *bme;
886  struct BigMapEntry *nxt;
887 
888  nxt = me.bme;
889  while (NULL != (bme = nxt))
890  {
891  nxt = bme->next;
892  if (0 == off)
893  {
894  if (GNUNET_OK != it (it_cls, &bme->key, bme->value))
895  return GNUNET_SYSERR;
896  return 1;
897  }
898  off--;
899  }
900  }
901  }
902  GNUNET_break (0);
903  return GNUNET_SYSERR;
904 }
905 
906 
909  const struct GNUNET_CONTAINER_MultiHashMap *map)
910 {
912 
914  iter->map = map;
916  iter->me = map->map[0];
917  return iter;
918 }
919 
920 
921 int
924  struct GNUNET_HashCode *key,
925  const void **value)
926 {
927  /* make sure the map has not been modified */
929 
930  /* look for the next entry, skipping empty buckets */
931  while (1)
932  {
933  if (iter->idx >= iter->map->map_length)
934  return GNUNET_NO;
935  if (GNUNET_YES == iter->map->use_small_entries)
936  {
937  if (NULL != iter->me.sme)
938  {
939  if (NULL != key)
940  *key = *iter->me.sme->key;
941  if (NULL != value)
942  *value = iter->me.sme->value;
943  iter->me.sme = iter->me.sme->next;
944  return GNUNET_YES;
945  }
946  }
947  else
948  {
949  if (NULL != iter->me.bme)
950  {
951  if (NULL != key)
952  *key = iter->me.bme->key;
953  if (NULL != value)
954  *value = iter->me.bme->value;
955  iter->me.bme = iter->me.bme->next;
956  return GNUNET_YES;
957  }
958  }
959  iter->idx += 1;
960  if (iter->idx < iter->map->map_length)
961  iter->me = iter->map->map[iter->idx];
962  }
963 }
964 
965 
966 void
969 {
970  GNUNET_free (iter);
971 }
972 
973 
974 /* end of container_multihashmap.c */
#define NEXT_CACHE_SIZE
Maximum recursion depth for callbacks of GNUNET_CONTAINER_multihashmap_get_multiple() themselves s ag...
static unsigned int idx_of(const struct GNUNET_CONTAINER_MultiHashMap *map, const struct GNUNET_HashCode *key)
Compute the index of the bucket for the given key.
static void update_next_cache_bme(struct GNUNET_CONTAINER_MultiHashMap *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 void grow(struct GNUNET_CONTAINER_MultiHashMap *map)
Grow the given map to a more appropriate size.
static void update_next_cache_sme(struct GNUNET_CONTAINER_MultiHashMap *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 int remove_all(void *cls, const struct GNUNET_HashCode *key, void *value)
Callback used to remove all entries from the map.
static int ret
Return value of the commandline.
Definition: gnunet-abd.c:81
static GNUNET_NETWORK_STRUCT_END struct GNUNET_PeerIdentity me
Our own peer identity.
static struct GNUNET_CONTAINER_MultiPeerMap * map
Handle to the map used to store old latency values for peers.
struct GNUNET_HashCode key
The key used in the DHT.
uint16_t len
length of data (which is always a uint32_t, but presumably this can be used to specify that fewer byt...
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.
int GNUNET_CONTAINER_multihashmap_contains(const struct GNUNET_CONTAINER_MultiHashMap *map, const struct GNUNET_HashCode *key)
Check if the map contains any value under the given key (including values that are NULL).
int GNUNET_CONTAINER_multihashmap_remove_all(struct GNUNET_CONTAINER_MultiHashMap *map, const struct GNUNET_HashCode *key)
Remove all entries for the given key from the map.
int GNUNET_CONTAINER_multihashmap_iterate(struct GNUNET_CONTAINER_MultiHashMap *map, GNUNET_CONTAINER_MultiHashMapIteratorCallback it, void *it_cls)
Iterate over all entries in the map.
int GNUNET_CONTAINER_multihashmap_contains_value(const struct GNUNET_CONTAINER_MultiHashMap *map, const struct GNUNET_HashCode *key, const void *value)
Check if the map contains the given value under the given key.
int GNUNET_CONTAINER_multihashmap_iterator_next(struct GNUNET_CONTAINER_MultiHashMapIterator *iter, struct GNUNET_HashCode *key, const void **value)
Retrieve the next element from the hash map at the iterator's position.
int GNUNET_CONTAINER_multihashmap_remove(struct GNUNET_CONTAINER_MultiHashMap *map, const struct GNUNET_HashCode *key, const void *value)
Remove the given key-value pair from the map.
int GNUNET_CONTAINER_multihashmap_put(struct GNUNET_CONTAINER_MultiHashMap *map, const struct GNUNET_HashCode *key, void *value, enum GNUNET_CONTAINER_MultiHashMapOption opt)
Store a key-value pair in the map.
struct GNUNET_CONTAINER_MultiHashMap * GNUNET_CONTAINER_multihashmap_create(unsigned int len, int do_not_copy_keys)
Create a multi hash map.
unsigned int GNUNET_CONTAINER_multihashmap_size(const struct GNUNET_CONTAINER_MultiHashMap *map)
Get the number of key-value pairs in the map.
void GNUNET_CONTAINER_multihashmap_destroy(struct GNUNET_CONTAINER_MultiHashMap *map)
Destroy a hash map.
struct GNUNET_CONTAINER_MultiHashMapIterator * GNUNET_CONTAINER_multihashmap_iterator_create(const struct GNUNET_CONTAINER_MultiHashMap *map)
Create an iterator for a multihashmap.
GNUNET_CONTAINER_MultiHashMapOption
Options for storing values in the HashMap.
unsigned int GNUNET_CONTAINER_multihashmap_clear(struct GNUNET_CONTAINER_MultiHashMap *map)
Remove all entries from the map.
int GNUNET_CONTAINER_multihashmap_get_multiple(struct GNUNET_CONTAINER_MultiHashMap *map, const struct GNUNET_HashCode *key, GNUNET_CONTAINER_MultiHashMapIteratorCallback it, void *it_cls)
Iterate over all entries in the map that match a particular key.
unsigned int GNUNET_CONTAINER_multihashmap_get_random(const struct GNUNET_CONTAINER_MultiHashMap *map, GNUNET_CONTAINER_MultiHashMapIteratorCallback 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_multihashmap_iterator_destroy(struct GNUNET_CONTAINER_MultiHashMapIterator *iter)
Destroy a multihashmap iterator.
void * GNUNET_CONTAINER_multihashmap_get(const struct GNUNET_CONTAINER_MultiHashMap *map, const struct GNUNET_HashCode *key)
Given a key find a value in the map matching the key.
enum GNUNET_GenericReturnValue(* GNUNET_CONTAINER_MultiHashMapIteratorCallback)(void *cls, const struct GNUNET_HashCode *key, void *value)
Iterator over hash map entries.
@ 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_log(kind,...)
#define GNUNET_memcmp(a, b)
Compare memory in a and b, where both must be of the same pointer type.
@ 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.
@ GNUNET_ERROR_TYPE_WARNING
#define GNUNET_MAX_MALLOC_CHECKED
Maximum allocation with GNUNET_malloc macro.
#define GNUNET_malloc_large(size)
Wrapper around malloc.
#define GNUNET_new(type)
Allocate a struct or union of the given type.
#define GNUNET_new_array(n, type)
Allocate a size n array with structs or unions of the given type.
#define GNUNET_free(ptr)
Wrapper around free.
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.
const struct GNUNET_CONTAINER_MultiHashMap * map
Map that we are iterating over.
unsigned int idx
Current bucket index.
unsigned int modification_counter
Modification counter as observed on the map when the iterator was created.
union MapEntry me
Position in the bucket idx.
Internal representation of the hash map.
unsigned int size
Number of entries in the map.
union MapEntry * map
All of our buckets.
unsigned int modification_counter
Counts the destructive modifications (grow, remove) to the map, so that iterators can check if they a...
unsigned int map_length
Length of the "map" array.
int use_small_entries
GNUNET_NO if the map entries are of type 'struct BigMapEntry', GNUNET_YES if the map entries are of t...
union MapEntry next_cache[16]
Map entries indicating iteration positions currently in use by GNUNET_CONTAINER_multihashmap_get_mult...
unsigned int next_cache_off
Offset of next_cache entries in use, must be smaller than NEXT_CACHE_SIZE.
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...
A 512-bit hashcode.
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.
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.