GNUnet  0.17.6
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  */
26 #include "platform.h"
27 #include "gnunet_container_lib.h"
28 
29 #define LOG(kind, ...) \
30  GNUNET_log_from (kind, "util-container-multihashmap", __VA_ARGS__)
31 
38 #define NEXT_CACHE_SIZE 16
39 
40 
45 {
49  void *value;
50 
54  struct BigMapEntry *next;
55 
59  struct GNUNET_HashCode key;
60 };
61 
62 
67 {
71  void *value;
72 
77 
81  const struct GNUNET_HashCode *key;
82 };
83 
84 
88 union 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 
132  unsigned int modification_counter;
133 
140 
145  unsigned int next_cache_off;
146 };
147 
148 
154 {
158  union MapEntry me;
159 
163  unsigned int idx;
164 
169  unsigned int modification_counter;
170 
175 };
176 
177 
179 GNUNET_CONTAINER_multihashmap_create (unsigned int len, int do_not_copy_keys)
180 {
182 
183  GNUNET_assert (len > 0);
185  if (len * sizeof(union MapEntry) > GNUNET_MAX_MALLOC_CHECKED)
186  {
187  size_t s;
188  /* application *explicitly* requested very large map, hopefully
189  it checks the return value... */
190  s = len * sizeof(union MapEntry);
191  if ((s / sizeof(union MapEntry)) != len)
192  return NULL; /* integer overflow on multiplication */
193  if (NULL == (hm->map = GNUNET_malloc_large (s)))
194  {
195  /* out of memory */
197  "Out of memory allocating large hash map (%u entries)\n",
198  len);
199  GNUNET_free (hm);
200  return NULL;
201  }
202  }
203  else
204  {
205  hm->map = GNUNET_new_array (len, union MapEntry);
206  }
207  hm->map_length = len;
208  hm->use_small_entries = do_not_copy_keys;
209  return hm;
210 }
211 
212 
213 void
216 {
218  for (unsigned int i = 0; i < map->map_length; i++)
219  {
220  union MapEntry me;
221 
222  me = map->map[i];
223  if (map->use_small_entries)
224  {
225  struct SmallMapEntry *sme;
226  struct SmallMapEntry *nxt;
227 
228  nxt = me.sme;
229  while (NULL != (sme = nxt))
230  {
231  nxt = sme->next;
232  GNUNET_free (sme);
233  }
234  me.sme = NULL;
235  }
236  else
237  {
238  struct BigMapEntry *bme;
239  struct BigMapEntry *nxt;
240 
241  nxt = me.bme;
242  while (NULL != (bme = nxt))
243  {
244  nxt = bme->next;
245  GNUNET_free (bme);
246  }
247  me.bme = NULL;
248  }
249  }
250  GNUNET_free (map->map);
251  GNUNET_free (map);
252 }
253 
254 
262 static unsigned int
264  const struct GNUNET_HashCode *key)
265 {
266  GNUNET_assert (map != NULL);
267  return (*(unsigned int *) key) % map->map_length;
268 }
269 
270 
271 unsigned int
273  const struct GNUNET_CONTAINER_MultiHashMap *map)
274 {
275  return map->size;
276 }
277 
278 
279 void *
281  const struct GNUNET_CONTAINER_MultiHashMap *map,
282  const struct GNUNET_HashCode *key)
283 {
284  union MapEntry me;
285 
286  me = map->map[idx_of (map, key)];
287  if (map->use_small_entries)
288  {
289  struct SmallMapEntry *sme;
290 
291  for (sme = me.sme; NULL != sme; sme = sme->next)
292  if (0 == GNUNET_memcmp (key, sme->key))
293  return sme->value;
294  }
295  else
296  {
297  struct BigMapEntry *bme;
298 
299  for (bme = me.bme; NULL != bme; bme = bme->next)
300  if (0 == GNUNET_memcmp (key, &bme->key))
301  return bme->value;
302  }
303  return NULL;
304 }
305 
306 
307 int
311  void *it_cls)
312 {
313  int count;
314  union MapEntry me;
315  union MapEntry *ce;
316  struct GNUNET_HashCode kc;
317 
318  GNUNET_assert (NULL != map);
319  ce = &map->next_cache[map->next_cache_off];
321  count = 0;
322  for (unsigned i = 0; i < map->map_length; i++)
323  {
324  me = map->map[i];
325  if (map->use_small_entries)
326  {
327  struct SmallMapEntry *sme;
328 
329  ce->sme = me.sme;
330  while (NULL != (sme = ce->sme))
331  {
332  ce->sme = sme->next;
333  if (NULL != it)
334  {
335  if (GNUNET_OK != it (it_cls, sme->key, sme->value))
336  {
338  return GNUNET_SYSERR;
339  }
340  }
341  count++;
342  }
343  }
344  else
345  {
346  struct BigMapEntry *bme;
347 
348  ce->bme = me.bme;
349  while (NULL != (bme = ce->bme))
350  {
351  ce->bme = bme->next;
352  if (NULL != it)
353  {
354  kc = bme->key;
355  if (GNUNET_OK != it (it_cls, &kc, bme->value))
356  {
358  return GNUNET_SYSERR;
359  }
360  }
361  count++;
362  }
363  }
364  }
366  return count;
367 }
368 
369 
377 static void
379  const struct BigMapEntry *bme)
380 {
381  for (unsigned int i = 0; i < map->next_cache_off; i++)
382  if (map->next_cache[i].bme == bme)
383  map->next_cache[i].bme = bme->next;
384 }
385 
386 
394 static void
396  const struct SmallMapEntry *sme)
397 {
398  for (unsigned int i = 0; i < map->next_cache_off; i++)
399  if (map->next_cache[i].sme == sme)
400  map->next_cache[i].sme = sme->next;
401 }
402 
403 
404 int
406  const struct GNUNET_HashCode *key,
407  const void *value)
408 {
409  union MapEntry me;
410  unsigned int i;
411 
413 
414  i = idx_of (map, key);
415  me = map->map[i];
416  if (map->use_small_entries)
417  {
418  struct SmallMapEntry *p;
419 
420  p = NULL;
421  for (struct SmallMapEntry *sme = me.sme; NULL != sme; sme = sme->next)
422  {
423  if ((0 == GNUNET_memcmp (key, sme->key)) && (value == sme->value))
424  {
425  if (NULL == p)
426  map->map[i].sme = sme->next;
427  else
428  p->next = sme->next;
429  update_next_cache_sme (map, sme);
430  GNUNET_free (sme);
431  map->size--;
432  return GNUNET_YES;
433  }
434  p = sme;
435  }
436  }
437  else
438  {
439  struct BigMapEntry *p;
440 
441  p = NULL;
442  for (struct BigMapEntry *bme = me.bme; NULL != bme; bme = bme->next)
443  {
444  if ((0 == GNUNET_memcmp (key, &bme->key)) && (value == bme->value))
445  {
446  if (NULL == p)
447  map->map[i].bme = bme->next;
448  else
449  p->next = bme->next;
450  update_next_cache_bme (map, bme);
451  GNUNET_free (bme);
452  map->size--;
453  return GNUNET_YES;
454  }
455  p = bme;
456  }
457  }
458  return GNUNET_NO;
459 }
460 
461 
462 int
465  const struct GNUNET_HashCode *key)
466 {
467  union MapEntry me;
468  unsigned int i;
469  int ret;
470 
472 
473  ret = 0;
474  i = idx_of (map, key);
475  me = map->map[i];
476  if (map->use_small_entries)
477  {
478  struct SmallMapEntry *sme;
479  struct SmallMapEntry *p;
480 
481  p = NULL;
482  sme = me.sme;
483  while (NULL != sme)
484  {
485  if (0 == GNUNET_memcmp (key, sme->key))
486  {
487  if (NULL == p)
488  map->map[i].sme = sme->next;
489  else
490  p->next = sme->next;
491  update_next_cache_sme (map, sme);
492  GNUNET_free (sme);
493  map->size--;
494  if (NULL == p)
495  sme = map->map[i].sme;
496  else
497  sme = p->next;
498  ret++;
499  }
500  else
501  {
502  p = sme;
503  sme = sme->next;
504  }
505  }
506  }
507  else
508  {
509  struct BigMapEntry *bme;
510  struct BigMapEntry *p;
511 
512  p = NULL;
513  bme = me.bme;
514  while (NULL != bme)
515  {
516  if (0 == GNUNET_memcmp (key, &bme->key))
517  {
518  if (NULL == p)
519  map->map[i].bme = bme->next;
520  else
521  p->next = bme->next;
522  update_next_cache_bme (map, bme);
523  GNUNET_free (bme);
524  map->size--;
525  if (NULL == p)
526  bme = map->map[i].bme;
527  else
528  bme = p->next;
529  ret++;
530  }
531  else
532  {
533  p = bme;
534  bme = bme->next;
535  }
536  }
537  }
538  return ret;
539 }
540 
541 
550 static int
551 remove_all (void *cls, const struct GNUNET_HashCode *key, void *value)
552 {
553  struct GNUNET_CONTAINER_MultiHashMap *map = cls;
554 
557  return GNUNET_OK;
558 }
559 
560 
569 unsigned int
571 {
572  unsigned int ret;
573 
574  ret = map->size;
576  return ret;
577 }
578 
579 
580 int
582  const struct GNUNET_CONTAINER_MultiHashMap *map,
583  const struct GNUNET_HashCode *key)
584 {
585  union MapEntry me;
586 
587  me = map->map[idx_of (map, key)];
588  if (map->use_small_entries)
589  {
590  struct SmallMapEntry *sme;
591 
592  for (sme = me.sme; NULL != sme; sme = sme->next)
593  if (0 == GNUNET_memcmp (key, sme->key))
594  return GNUNET_YES;
595  }
596  else
597  {
598  struct BigMapEntry *bme;
599 
600  for (bme = me.bme; NULL != bme; bme = bme->next)
601  if (0 == GNUNET_memcmp (key, &bme->key))
602  return GNUNET_YES;
603  }
604  return GNUNET_NO;
605 }
606 
607 
608 int
610  const struct GNUNET_CONTAINER_MultiHashMap *map,
611  const struct GNUNET_HashCode *key,
612  const void *value)
613 {
614  union MapEntry me;
615 
616  me = map->map[idx_of (map, key)];
617  if (map->use_small_entries)
618  {
619  struct SmallMapEntry *sme;
620 
621  for (sme = me.sme; NULL != sme; sme = sme->next)
622  if ((0 == GNUNET_memcmp (key, sme->key)) && (sme->value == value))
623  return GNUNET_YES;
624  }
625  else
626  {
627  struct BigMapEntry *bme;
628 
629  for (bme = me.bme; NULL != bme; bme = bme->next)
630  if ((0 == GNUNET_memcmp (key, &bme->key)) && (bme->value == value))
631  return GNUNET_YES;
632  }
633  return GNUNET_NO;
634 }
635 
636 
642 static void
644 {
645  union MapEntry *old_map;
646  union MapEntry *new_map;
647  unsigned int old_len;
648  unsigned int new_len;
649  unsigned int idx;
650 
651  old_map = map->map;
652  old_len = map->map_length;
653  GNUNET_assert (0 != old_len);
654  new_len = old_len * 2;
655  if (0 == new_len) /* 2^31 * 2 == 0 */
656  new_len = old_len; /* never use 0 */
657  if (new_len == old_len)
658  return; /* nothing changed */
659  new_map = GNUNET_malloc_large (new_len * sizeof(union MapEntry));
660  if (NULL == new_map)
661  return; /* grow not possible */
663  map->map_length = new_len;
664  map->map = new_map;
665  for (unsigned int i = 0; i < old_len; i++)
666  {
667  if (map->use_small_entries)
668  {
669  struct SmallMapEntry *sme;
670 
671  while (NULL != (sme = old_map[i].sme))
672  {
673  old_map[i].sme = sme->next;
674  idx = idx_of (map, sme->key);
675  sme->next = new_map[idx].sme;
676  new_map[idx].sme = sme;
677  }
678  }
679  else
680  {
681  struct BigMapEntry *bme;
682 
683  while (NULL != (bme = old_map[i].bme))
684  {
685  old_map[i].bme = bme->next;
686  idx = idx_of (map, &bme->key);
687  bme->next = new_map[idx].bme;
688  new_map[idx].bme = bme;
689  }
690  }
691  }
692  GNUNET_free (old_map);
693 }
694 
695 
708 int
710  const struct GNUNET_HashCode *key,
711  void *value,
713 {
714  union MapEntry me;
715  unsigned int i;
716 
717  i = idx_of (map, key);
720  {
721  me = map->map[i];
722  if (map->use_small_entries)
723  {
724  struct SmallMapEntry *sme;
725 
726  for (sme = me.sme; NULL != sme; sme = sme->next)
727  if (0 == GNUNET_memcmp (key, sme->key))
728  {
730  return GNUNET_SYSERR;
731  sme->value = value;
732  return GNUNET_NO;
733  }
734  }
735  else
736  {
737  struct BigMapEntry *bme;
738 
739  for (bme = me.bme; NULL != bme; bme = bme->next)
740  if (0 == GNUNET_memcmp (key, &bme->key))
741  {
743  return GNUNET_SYSERR;
744  bme->value = value;
745  return GNUNET_NO;
746  }
747  }
748  }
749  if (map->size / 3 >= map->map_length / 4)
750  {
751  grow (map);
752  i = idx_of (map, key);
753  }
754  if (map->use_small_entries)
755  {
756  struct SmallMapEntry *sme;
757 
758  sme = GNUNET_new (struct SmallMapEntry);
759  sme->key = key;
760  sme->value = value;
761  sme->next = map->map[i].sme;
762  map->map[i].sme = sme;
763  }
764  else
765  {
766  struct BigMapEntry *bme;
767 
768  bme = GNUNET_new (struct BigMapEntry);
769  bme->key = *key;
770  bme->value = value;
771  bme->next = map->map[i].bme;
772  map->map[i].bme = bme;
773  }
774  map->size++;
775  return GNUNET_OK;
776 }
777 
778 
779 int
782  const struct GNUNET_HashCode *key,
784  void *it_cls)
785 {
786  int count;
787  union MapEntry *me;
788  union MapEntry *ce;
789 
790  ce = &map->next_cache[map->next_cache_off];
792  count = 0;
793  me = &map->map[idx_of (map, key)];
794  if (map->use_small_entries)
795  {
796  struct SmallMapEntry *sme;
797 
798  ce->sme = me->sme;
799  while (NULL != (sme = ce->sme))
800  {
801  ce->sme = sme->next;
802  if (0 != GNUNET_memcmp (key, sme->key))
803  continue;
804  if ((NULL != it) && (GNUNET_OK != it (it_cls, key, sme->value)))
805  {
807  return GNUNET_SYSERR;
808  }
809  count++;
810  }
811  }
812  else
813  {
814  struct BigMapEntry *bme;
815 
816  ce->bme = me->bme;
817  while (NULL != (bme = ce->bme))
818  {
819  ce->bme = bme->next;
820  if (0 != GNUNET_memcmp (key, &bme->key))
821  continue;
822  if ((NULL != it) && (GNUNET_OK != it (it_cls, key, bme->value)))
823  {
825  return GNUNET_SYSERR;
826  }
827  count++;
828  }
829  }
831  return count;
832 }
833 
834 
846 unsigned int
848  const struct GNUNET_CONTAINER_MultiHashMap *map,
850  void *it_cls)
851 {
852  unsigned int off;
853  unsigned int idx;
854  union MapEntry me;
855 
856  if (0 == map->size)
857  return 0;
858  if (NULL == it)
859  return 1;
861  for (idx = 0; idx < map->map_length; idx++)
862  {
863  me = map->map[idx];
864  if (map->use_small_entries)
865  {
866  struct SmallMapEntry *sme;
867  struct SmallMapEntry *nxt;
868 
869  nxt = me.sme;
870  while (NULL != (sme = nxt))
871  {
872  nxt = sme->next;
873  if (0 == off)
874  {
875  if (GNUNET_OK != it (it_cls, sme->key, sme->value))
876  return GNUNET_SYSERR;
877  return 1;
878  }
879  off--;
880  }
881  }
882  else
883  {
884  struct BigMapEntry *bme;
885  struct BigMapEntry *nxt;
886 
887  nxt = me.bme;
888  while (NULL != (bme = nxt))
889  {
890  nxt = bme->next;
891  if (0 == off)
892  {
893  if (GNUNET_OK != it (it_cls, &bme->key, bme->value))
894  return GNUNET_SYSERR;
895  return 1;
896  }
897  off--;
898  }
899  }
900  }
901  GNUNET_break (0);
902  return GNUNET_SYSERR;
903 }
904 
905 
908  const struct GNUNET_CONTAINER_MultiHashMap *map)
909 {
911 
913  iter->map = map;
915  iter->me = map->map[0];
916  return iter;
917 }
918 
919 
920 int
923  struct GNUNET_HashCode *key,
924  const void **value)
925 {
926  /* make sure the map has not been modified */
928 
929  /* look for the next entry, skipping empty buckets */
930  while (1)
931  {
932  if (iter->idx >= iter->map->map_length)
933  return GNUNET_NO;
934  if (GNUNET_YES == iter->map->use_small_entries)
935  {
936  if (NULL != iter->me.sme)
937  {
938  if (NULL != key)
939  *key = *iter->me.sme->key;
940  if (NULL != value)
941  *value = iter->me.sme->value;
942  iter->me.sme = iter->me.sme->next;
943  return GNUNET_YES;
944  }
945  }
946  else
947  {
948  if (NULL != iter->me.bme)
949  {
950  if (NULL != key)
951  *key = iter->me.bme->key;
952  if (NULL != value)
953  *value = iter->me.bme->value;
954  iter->me.bme = iter->me.bme->next;
955  return GNUNET_YES;
956  }
957  }
958  iter->idx += 1;
959  if (iter->idx < iter->map->map_length)
960  iter->me = iter->map->map[iter->idx];
961  }
962 }
963 
964 
965 void
968 {
969  GNUNET_free (iter);
970 }
971 
972 
973 /* 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:37
Container classes for GNUnet.
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_get_multiple(struct GNUNET_CONTAINER_MultiHashMap *map, const struct GNUNET_HashCode *key, GNUNET_CONTAINER_MulitHashMapIteratorCallback it, void *it_cls)
Iterate over all entries in the map that match a particular key.
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_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.
int GNUNET_CONTAINER_multihashmap_iterate(struct GNUNET_CONTAINER_MultiHashMap *map, GNUNET_CONTAINER_MulitHashMapIteratorCallback it, void *it_cls)
Iterate over all entries 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.
enum GNUNET_GenericReturnValue(* GNUNET_CONTAINER_MulitHashMapIteratorCallback)(void *cls, const struct GNUNET_HashCode *key, void *value)
Iterator over hash map entries.
unsigned int GNUNET_CONTAINER_multihashmap_clear(struct GNUNET_CONTAINER_MultiHashMap *map)
Remove all entries from the map.
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.
unsigned int GNUNET_CONTAINER_multihashmap_get_random(const struct GNUNET_CONTAINER_MultiHashMap *map, GNUNET_CONTAINER_MulitHashMapIteratorCallback it, void *it_cls)
Call it on a random value from the map, or not at all if the map is empty.
@ 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
Definition: gnunet_common.h:99
@ GNUNET_YES
@ GNUNET_NO
Definition: gnunet_common.h:98
@ GNUNET_SYSERR
Definition: gnunet_common.h:97
#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.