GNUnet  0.17.6
container_multishortmap.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_util_lib.h"
28 
29 #define LOG(kind, ...) \
30  GNUNET_log_from (kind, "util-container-multishortmap", __VA_ARGS__)
31 
38 #define NEXT_CACHE_SIZE 16
39 
40 
44 struct BigMapEntry
45 {
49  void *value;
50 
54  struct BigMapEntry *next;
55 
60 };
61 
62 
66 struct SmallMapEntry
67 {
71  void *value;
72 
76  struct SmallMapEntry *next;
77 
81  const struct GNUNET_ShortHashCode *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 
194 GNUNET_CONTAINER_multishortmap_create (unsigned int len, int do_not_copy_keys)
195 {
197 
198  GNUNET_assert (len > 0);
200  map->map = GNUNET_malloc_large (len * sizeof(union MapEntry));
201  if (NULL == map->map)
202  {
203  GNUNET_free (map);
204  return NULL;
205  }
206  map->map_length = len;
207  map->use_small_entries = do_not_copy_keys;
208  return map;
209 }
210 
211 
212 void
215 {
217  for (unsigned int i = 0; i < map->map_length; i++)
218  {
219  union MapEntry me;
220 
221  me = map->map[i];
222  if (map->use_small_entries)
223  {
224  struct SmallMapEntry *sme;
225  struct SmallMapEntry *nxt;
226 
227  nxt = me.sme;
228  while (NULL != (sme = nxt))
229  {
230  nxt = sme->next;
231  GNUNET_free (sme);
232  }
233  me.sme = NULL;
234  }
235  else
236  {
237  struct BigMapEntry *bme;
238  struct BigMapEntry *nxt;
239 
240  nxt = me.bme;
241  while (NULL != (bme = nxt))
242  {
243  nxt = bme->next;
244  GNUNET_free (bme);
245  }
246  me.bme = NULL;
247  }
248  }
249  GNUNET_free (map->map);
250  GNUNET_free (map);
251 }
252 
253 
261 static unsigned int
263  const struct GNUNET_ShortHashCode *key)
264 {
265  unsigned int kx;
266 
267  GNUNET_assert (NULL != map);
268  GNUNET_memcpy (&kx, key, sizeof(kx));
269  return kx % map->map_length;
270 }
271 
272 
273 unsigned int
275  const struct GNUNET_CONTAINER_MultiShortmap *map)
276 {
277  return map->size;
278 }
279 
280 
281 void *
283  const struct GNUNET_CONTAINER_MultiShortmap *map,
284  const struct GNUNET_ShortHashCode *key)
285 {
286  union MapEntry me;
287 
288  me = map->map[idx_of (map, key)];
289  if (map->use_small_entries)
290  {
291  for (struct SmallMapEntry *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  for (struct BigMapEntry *bme = me.bme; NULL != bme; bme = bme->next)
298  if (0 == GNUNET_memcmp (key, &bme->key))
299  return bme->value;
300  }
301  return NULL;
302 }
303 
304 
305 int
309  void *it_cls)
310 {
311  int count;
312  union MapEntry me;
313  union MapEntry *ce;
314  struct GNUNET_ShortHashCode kc;
315 
316  count = 0;
317  GNUNET_assert (NULL != map);
318  ce = &map->next_cache[map->next_cache_off];
320  for (unsigned int i = 0; i < map->map_length; i++)
321  {
322  me = map->map[i];
323  if (map->use_small_entries)
324  {
325  struct SmallMapEntry *sme;
326 
327  ce->sme = me.sme;
328  while (NULL != (sme = ce->sme))
329  {
330  ce->sme = sme->next;
331  if ((NULL != it) && (GNUNET_OK != it (it_cls, sme->key, sme->value)))
332  {
334  return GNUNET_SYSERR;
335  }
336  count++;
337  }
338  }
339  else
340  {
341  struct BigMapEntry *bme;
342 
343  ce->bme = me.bme;
344  while (NULL != (bme = ce->bme))
345  {
346  ce->bme = bme->next;
347  if (NULL != it)
348  {
349  kc = bme->key;
350  if (GNUNET_OK != it (it_cls, &kc, bme->value))
351  {
353  return GNUNET_SYSERR;
354  }
355  }
356  count++;
357  }
358  }
359  }
361  return count;
362 }
363 
364 
372 static void
374  const struct BigMapEntry *bme)
375 {
376  for (unsigned int i = 0; i < map->next_cache_off; i++)
377  if (map->next_cache[i].bme == bme)
378  map->next_cache[i].bme = bme->next;
379 }
380 
381 
389 static void
391  const struct SmallMapEntry *sme)
392 {
393  for (unsigned int i = 0; i < map->next_cache_off; i++)
394  if (map->next_cache[i].sme == sme)
395  map->next_cache[i].sme = sme->next;
396 }
397 
398 
399 int
402  const struct GNUNET_ShortHashCode *key,
403  const void *value)
404 {
405  union MapEntry me;
406  unsigned int i;
407 
409  i = idx_of (map, key);
410  me = map->map[i];
411  if (map->use_small_entries)
412  {
413  struct SmallMapEntry *p = NULL;
414 
415  for (struct SmallMapEntry *sme = me.sme; NULL != sme; sme = sme->next)
416  {
417  if ((0 == GNUNET_memcmp (key, sme->key)) && (value == sme->value))
418  {
419  if (NULL == p)
420  map->map[i].sme = sme->next;
421  else
422  p->next = sme->next;
423  update_next_cache_sme (map, sme);
424  GNUNET_free (sme);
425  map->size--;
426  return GNUNET_YES;
427  }
428  p = sme;
429  }
430  }
431  else
432  {
433  struct BigMapEntry *p = NULL;
434 
435  for (struct BigMapEntry *bme = me.bme; NULL != bme; bme = bme->next)
436  {
437  if ((0 == GNUNET_memcmp (key, &bme->key)) && (value == bme->value))
438  {
439  if (NULL == p)
440  map->map[i].bme = bme->next;
441  else
442  p->next = bme->next;
443  update_next_cache_bme (map, bme);
444  GNUNET_free (bme);
445  map->size--;
446  return GNUNET_YES;
447  }
448  p = bme;
449  }
450  }
451  return GNUNET_NO;
452 }
453 
454 
455 int
458  const struct GNUNET_ShortHashCode *key)
459 {
460  union MapEntry me;
461  unsigned int i;
462  int ret;
463 
465 
466  ret = 0;
467  i = idx_of (map, key);
468  me = map->map[i];
469  if (map->use_small_entries)
470  {
471  struct SmallMapEntry *sme;
472  struct SmallMapEntry *p;
473 
474  p = NULL;
475  sme = me.sme;
476  while (NULL != sme)
477  {
478  if (0 == GNUNET_memcmp (key, sme->key))
479  {
480  if (NULL == p)
481  map->map[i].sme = sme->next;
482  else
483  p->next = sme->next;
484  update_next_cache_sme (map, sme);
485  GNUNET_free (sme);
486  map->size--;
487  if (NULL == p)
488  sme = map->map[i].sme;
489  else
490  sme = p->next;
491  ret++;
492  }
493  else
494  {
495  p = sme;
496  sme = sme->next;
497  }
498  }
499  }
500  else
501  {
502  struct BigMapEntry *bme;
503  struct BigMapEntry *p;
504 
505  p = NULL;
506  bme = me.bme;
507  while (NULL != bme)
508  {
509  if (0 == GNUNET_memcmp (key, &bme->key))
510  {
511  if (NULL == p)
512  map->map[i].bme = bme->next;
513  else
514  p->next = bme->next;
515  update_next_cache_bme (map, bme);
516  GNUNET_free (bme);
517  map->size--;
518  if (NULL == p)
519  bme = map->map[i].bme;
520  else
521  bme = p->next;
522  ret++;
523  }
524  else
525  {
526  p = bme;
527  bme = bme->next;
528  }
529  }
530  }
531  return ret;
532 }
533 
534 
535 int
537  const struct GNUNET_CONTAINER_MultiShortmap *map,
538  const struct GNUNET_ShortHashCode *key)
539 {
540  union MapEntry me;
541 
542  me = map->map[idx_of (map, key)];
543  if (map->use_small_entries)
544  {
545  for (struct SmallMapEntry *sme = me.sme; NULL != sme; sme = sme->next)
546  if (0 == GNUNET_memcmp (key, sme->key))
547  return GNUNET_YES;
548  }
549  else
550  {
551  for (struct BigMapEntry *bme = me.bme; NULL != bme; bme = bme->next)
552  if (0 == GNUNET_memcmp (key, &bme->key))
553  return GNUNET_YES;
554  }
555  return GNUNET_NO;
556 }
557 
558 
559 int
561  const struct GNUNET_CONTAINER_MultiShortmap *map,
562  const struct GNUNET_ShortHashCode *key,
563  const void *value)
564 {
565  union MapEntry me;
566 
567  me = map->map[idx_of (map, key)];
568  if (map->use_small_entries)
569  {
570  for (struct SmallMapEntry *sme = me.sme; NULL != sme; sme = sme->next)
571  if ((0 == GNUNET_memcmp (key, sme->key)) && (sme->value == value))
572  return GNUNET_YES;
573  }
574  else
575  {
576  for (struct BigMapEntry *bme = me.bme; NULL != bme; bme = bme->next)
577  if ((0 == GNUNET_memcmp (key, &bme->key)) && (bme->value == value))
578  return GNUNET_YES;
579  }
580  return GNUNET_NO;
581 }
582 
583 
589 static void
591 {
592  union MapEntry *old_map;
593  union MapEntry *new_map;
594  unsigned int old_len;
595  unsigned int new_len;
596  unsigned int idx;
597 
598  old_map = map->map;
599  old_len = map->map_length;
600  new_len = old_len * 2;
601  if (0 == new_len) /* 2^31 * 2 == 0 */
602  new_len = old_len; /* never use 0 */
603  if (new_len == old_len)
604  return; /* nothing changed */
605  new_map = GNUNET_malloc_large (new_len * sizeof(union MapEntry));
606  if (NULL == new_map)
607  return; /* grow not possible */
609  map->map_length = new_len;
610  map->map = new_map;
611  for (unsigned int i = 0; i < old_len; i++)
612  {
613  if (map->use_small_entries)
614  {
615  struct SmallMapEntry *sme;
616 
617  while (NULL != (sme = old_map[i].sme))
618  {
619  old_map[i].sme = sme->next;
620  idx = idx_of (map, sme->key);
621  sme->next = new_map[idx].sme;
622  new_map[idx].sme = sme;
623  }
624  }
625  else
626  {
627  struct BigMapEntry *bme;
628 
629  while (NULL != (bme = old_map[i].bme))
630  {
631  old_map[i].bme = bme->next;
632  idx = idx_of (map, &bme->key);
633  bme->next = new_map[idx].bme;
634  new_map[idx].bme = bme;
635  }
636  }
637  }
638  GNUNET_free (old_map);
639 }
640 
641 
642 int
645  const struct GNUNET_ShortHashCode *key,
646  void *value,
648 {
649  union MapEntry me;
650  unsigned int i;
651 
652  i = idx_of (map, key);
655  {
656  me = map->map[i];
657  if (map->use_small_entries)
658  {
659  for (struct SmallMapEntry *sme = me.sme; NULL != sme; sme = sme->next)
660  if (0 == GNUNET_memcmp (key, sme->key))
661  {
663  return GNUNET_SYSERR;
664  sme->value = value;
665  return GNUNET_NO;
666  }
667  }
668  else
669  {
670  for (struct BigMapEntry *bme = me.bme; NULL != bme; bme = bme->next)
671  if (0 == GNUNET_memcmp (key, &bme->key))
672  {
674  return GNUNET_SYSERR;
675  bme->value = value;
676  return GNUNET_NO;
677  }
678  }
679  }
680  if (map->size / 3 >= map->map_length / 4)
681  {
682  grow (map);
683  i = idx_of (map, key);
684  }
685  if (map->use_small_entries)
686  {
687  struct SmallMapEntry *sme;
688 
689  sme = GNUNET_new (struct SmallMapEntry);
690  sme->key = key;
691  sme->value = value;
692  sme->next = map->map[i].sme;
693  map->map[i].sme = sme;
694  }
695  else
696  {
697  struct BigMapEntry *bme;
698 
699  bme = GNUNET_new (struct BigMapEntry);
700  bme->key = *key;
701  bme->value = value;
702  bme->next = map->map[i].bme;
703  map->map[i].bme = bme;
704  }
705  map->size++;
706  return GNUNET_OK;
707 }
708 
709 
720 int
723  const struct GNUNET_ShortHashCode *key,
725  void *it_cls)
726 {
727  int count;
728  union MapEntry me;
729  union MapEntry *ce;
730 
731  ce = &map->next_cache[map->next_cache_off];
733  count = 0;
734  me = map->map[idx_of (map, key)];
735  if (map->use_small_entries)
736  {
737  struct SmallMapEntry *sme;
738 
739  ce->sme = me.sme;
740  while (NULL != (sme = ce->sme))
741  {
742  ce->sme = sme->next;
743  if (0 != GNUNET_memcmp (key, sme->key))
744  continue;
745  if ((NULL != it) && (GNUNET_OK != it (it_cls, key, sme->value)))
746  {
748  return GNUNET_SYSERR;
749  }
750  count++;
751  }
752  }
753  else
754  {
755  struct BigMapEntry *bme;
756 
757  ce->bme = me.bme;
758  while (NULL != (bme = ce->bme))
759  {
760  ce->bme = bme->next;
761  if (0 != GNUNET_memcmp (key, &bme->key))
762  continue;
763  if ((NULL != it) && (GNUNET_OK != it (it_cls, key, bme->value)))
764  {
766  return GNUNET_SYSERR;
767  }
768  count++;
769  }
770  }
772  return count;
773 }
774 
775 
787 unsigned int
789  const struct GNUNET_CONTAINER_MultiShortmap *map,
791  void *it_cls)
792 {
793  unsigned int off;
794  union MapEntry me;
795 
796  if (0 == map->size)
797  return 0;
798  if (NULL == it)
799  return 1;
801  for (unsigned int idx = 0; idx < map->map_length; idx++)
802  {
803  me = map->map[idx];
804  if (map->use_small_entries)
805  {
806  for (struct SmallMapEntry *sme = me.sme; NULL != sme; sme = sme->next)
807  {
808  if (0 == off)
809  {
810  if (GNUNET_OK != it (it_cls, sme->key, sme->value))
811  return GNUNET_SYSERR;
812  return 1;
813  }
814  off--;
815  }
816  }
817  else
818  {
819  for (struct BigMapEntry *bme = me.bme; NULL != bme; bme = bme->next)
820  {
821  if (0 == off)
822  {
823  if (GNUNET_OK != it (it_cls, &bme->key, bme->value))
824  return GNUNET_SYSERR;
825  return 1;
826  }
827  off--;
828  }
829  }
830  }
831  GNUNET_break (0);
832  return GNUNET_SYSERR;
833 }
834 
835 
838  const struct GNUNET_CONTAINER_MultiShortmap *map)
839 {
841 
843  iter->map = map;
845  iter->me = map->map[0];
846  return iter;
847 }
848 
849 
850 int
853  struct GNUNET_ShortHashCode *key,
854  const void **value)
855 {
856  /* make sure the map has not been modified */
858 
859  /* look for the next entry, skipping empty buckets */
860  while (1)
861  {
862  if (iter->idx >= iter->map->map_length)
863  return GNUNET_NO;
864  if (GNUNET_YES == iter->map->use_small_entries)
865  {
866  if (NULL != iter->me.sme)
867  {
868  if (NULL != key)
869  *key = *iter->me.sme->key;
870  if (NULL != value)
871  *value = iter->me.sme->value;
872  iter->me.sme = iter->me.sme->next;
873  return GNUNET_YES;
874  }
875  }
876  else
877  {
878  if (NULL != iter->me.bme)
879  {
880  if (NULL != key)
881  *key = iter->me.bme->key;
882  if (NULL != value)
883  *value = iter->me.bme->value;
884  iter->me.bme = iter->me.bme->next;
885  return GNUNET_YES;
886  }
887  }
888  iter->idx += 1;
889  if (iter->idx < iter->map->map_length)
890  iter->me = iter->map->map[iter->idx];
891  }
892 }
893 
894 
895 void
898 {
899  GNUNET_free (iter);
900 }
901 
902 
903 /* end of container_multishortmap.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_MultiShortmap *map)
Grow the given map to a more appropriate size.
static void update_next_cache_sme(struct GNUNET_CONTAINER_MultiShortmap *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 void update_next_cache_bme(struct GNUNET_CONTAINER_MultiShortmap *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 unsigned int idx_of(const struct GNUNET_CONTAINER_MultiShortmap *map, const struct GNUNET_ShortHashCode *key)
Compute the index of the bucket for the given key.
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
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.
unsigned int GNUNET_CONTAINER_multishortmap_get_random(const struct GNUNET_CONTAINER_MultiShortmap *map, GNUNET_CONTAINER_ShortmapIterator it, void *it_cls)
Call it on a random value from the map, or not at all if the map is empty.
enum GNUNET_GenericReturnValue(* GNUNET_CONTAINER_ShortmapIterator)(void *cls, const struct GNUNET_ShortHashCode *key, void *value)
Iterator over hash map entries.
void GNUNET_CONTAINER_multishortmap_iterator_destroy(struct GNUNET_CONTAINER_MultiShortmapIterator *iter)
Destroy a multishortmap iterator.
int GNUNET_CONTAINER_multishortmap_put(struct GNUNET_CONTAINER_MultiShortmap *map, const struct GNUNET_ShortHashCode *key, void *value, enum GNUNET_CONTAINER_MultiHashMapOption opt)
Store a key-value pair in the map.
struct GNUNET_CONTAINER_MultiShortmapIterator * GNUNET_CONTAINER_multishortmap_iterator_create(const struct GNUNET_CONTAINER_MultiShortmap *map)
Create an iterator for a multihashmap.
int GNUNET_CONTAINER_multishortmap_iterator_next(struct GNUNET_CONTAINER_MultiShortmapIterator *iter, struct GNUNET_ShortHashCode *key, const void **value)
Retrieve the next element from the hash map at the iterator's position.
int GNUNET_CONTAINER_multishortmap_iterate(struct GNUNET_CONTAINER_MultiShortmap *map, GNUNET_CONTAINER_ShortmapIterator it, void *it_cls)
Iterate over all entries in the map.
int GNUNET_CONTAINER_multishortmap_contains_value(const struct GNUNET_CONTAINER_MultiShortmap *map, const struct GNUNET_ShortHashCode *key, const void *value)
Check if the map contains the given value under the given key.
GNUNET_CONTAINER_MultiHashMapOption
Options for storing values in the HashMap.
struct GNUNET_CONTAINER_MultiShortmap * GNUNET_CONTAINER_multishortmap_create(unsigned int len, int do_not_copy_keys)
Create a multi hash map.
void GNUNET_CONTAINER_multishortmap_destroy(struct GNUNET_CONTAINER_MultiShortmap *map)
Destroy a hash map.
int GNUNET_CONTAINER_multishortmap_remove_all(struct GNUNET_CONTAINER_MultiShortmap *map, const struct GNUNET_ShortHashCode *key)
Remove all entries for the given key from the map.
int GNUNET_CONTAINER_multishortmap_get_multiple(struct GNUNET_CONTAINER_MultiShortmap *map, const struct GNUNET_ShortHashCode *key, GNUNET_CONTAINER_ShortmapIterator it, void *it_cls)
Iterate over all entries in the map that match a particular key.
void * GNUNET_CONTAINER_multishortmap_get(const struct GNUNET_CONTAINER_MultiShortmap *map, const struct GNUNET_ShortHashCode *key)
Given a key find a value in the map matching the key.
unsigned int GNUNET_CONTAINER_multishortmap_size(const struct GNUNET_CONTAINER_MultiShortmap *map)
Get the number of key-value pairs in the map.
int GNUNET_CONTAINER_multishortmap_remove(struct GNUNET_CONTAINER_MultiShortmap *map, const struct GNUNET_ShortHashCode *key, const void *value)
Remove the given key-value pair from the map.
int GNUNET_CONTAINER_multishortmap_contains(const struct GNUNET_CONTAINER_MultiShortmap *map, const struct GNUNET_ShortHashCode *key)
Check if the map contains any value under the given key (including values that are NULL).
@ 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_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.
#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.
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 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...
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_MultiShortmap * map
Map that we are iterating over.
Internal representation of the hash map.
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 map_length
Length of the "map" array.
union MapEntry next_cache[16]
Map entries indicating iteration positions currently in use by GNUNET_CONTAINER_multihashmap_get_mult...
unsigned int size
Number of entries in the map.
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.
unsigned int next_cache_off
Offset of next_cache entries in use, must be smaller than NEXT_CACHE_SIZE.
A 256-bit hashcode.
An entry in the hash map with just a pointer to the key.
const struct GNUNET_ShortHashCode * key
Key for the entry.
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.