GNUnet  0.11.x
container_multihashmap32.c
Go to the documentation of this file.
1 /*
2  This file is part of GNUnet.
3  Copyright (C) 2008 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  */
28 #include "platform.h"
29 #include "gnunet_container_lib.h"
30 
31 #define LOG(kind, ...) \
32  GNUNET_log_from (kind, "util-container-multihashmap32", __VA_ARGS__)
33 
34 
41 #define NEXT_CACHE_SIZE 16
42 
46 struct MapEntry
47 {
51  uint32_t key;
52 
56  void *value;
57 
61  struct MapEntry *next;
62 };
63 
68 {
72  struct MapEntry **map;
73 
77  unsigned int size;
78 
82  unsigned int map_length;
83 
88  unsigned int modification_counter;
89 
95  struct MapEntry *next_cache[NEXT_CACHE_SIZE];
96 
101  unsigned int next_cache_off;
102 };
103 
104 
110 {
114  struct MapEntry *me;
115 
119  unsigned int idx;
120 
125  unsigned int modification_counter;
126 
131 };
132 
133 
142 {
144 
145  GNUNET_assert (len > 0);
147  ret->map = GNUNET_malloc_large (len * sizeof(struct MapEntry *));
148  if (NULL == ret->map)
149  {
150  GNUNET_free (ret);
151  return NULL;
152  }
153  ret->map_length = len;
154  return ret;
155 }
156 
157 
164 void
167 {
168  struct MapEntry *e;
169 
170  for (unsigned int i = 0; i < map->map_length; i++)
171  {
172  while (NULL != (e = map->map[i]))
173  {
174  map->map[i] = e->next;
175  GNUNET_free (e);
176  }
177  }
178  GNUNET_free (map->map);
179  GNUNET_free (map);
180 }
181 
182 
190 static unsigned int
191 idx_of (const struct GNUNET_CONTAINER_MultiHashMap32 *m, const uint32_t key)
192 {
193  GNUNET_assert (NULL != m);
194  return ((unsigned int) key) % m->map_length;
195 }
196 
197 
204 unsigned int
206  const struct GNUNET_CONTAINER_MultiHashMap32 *map)
207 {
208  return map->size;
209 }
210 
211 
222 void *
224  const struct GNUNET_CONTAINER_MultiHashMap32 *map,
225  uint32_t key)
226 {
227  struct MapEntry *e;
228 
229  e = map->map[idx_of (map, key)];
230  while (NULL != e)
231  {
232  if (key == e->key)
233  return e->value;
234  e = e->next;
235  }
236  return NULL;
237 }
238 
239 
249 int
253  void *it_cls)
254 {
255  int count;
256  struct MapEntry **ce;
257 
258  count = 0;
259  GNUNET_assert (NULL != map);
260  ce = &map->next_cache[map->next_cache_off];
262  for (unsigned int i = 0; i < map->map_length; i++)
263  {
264  struct MapEntry *e;
265 
266  *ce = map->map[i];
267  while (NULL != (e = *ce))
268  {
269  *ce = e->next;
270  if (NULL != it)
271  {
272  if (GNUNET_OK != it (it_cls, e->key, e->value))
273  {
275  return GNUNET_SYSERR;
276  }
277  }
278  count++;
279  }
280  }
282  return count;
283 }
284 
285 
293 static void
295  const struct MapEntry *me)
296 {
297  for (unsigned int i = 0; i < map->next_cache_off; i++)
298  if (map->next_cache[i] == me)
299  map->next_cache[i] = me->next;
300 }
301 
302 
314 int
317  uint32_t key,
318  const void *value)
319 {
320  struct MapEntry *e;
321  struct MapEntry *p;
322  unsigned int i;
323 
324  map->modification_counter++;
325 
326  i = idx_of (map, key);
327  p = NULL;
328  e = map->map[i];
329  while (e != NULL)
330  {
331  if ((key == e->key) && (value == e->value))
332  {
333  if (p == NULL)
334  map->map[i] = e->next;
335  else
336  p->next = e->next;
337  update_next_cache (map, e);
338  GNUNET_free (e);
339  map->size--;
340  return GNUNET_YES;
341  }
342  p = e;
343  e = e->next;
344  }
345  return GNUNET_NO;
346 }
347 
348 
357 int
360  uint32_t key)
361 {
362  struct MapEntry *e;
363  struct MapEntry *p;
364  unsigned int i;
365  int ret;
366 
367  map->modification_counter++;
368 
369  ret = 0;
370  i = idx_of (map, key);
371  p = NULL;
372  e = map->map[i];
373  while (e != NULL)
374  {
375  if (key == e->key)
376  {
377  if (p == NULL)
378  map->map[i] = e->next;
379  else
380  p->next = e->next;
381  update_next_cache (map, e);
382  GNUNET_free (e);
383  map->size--;
384  if (p == NULL)
385  e = map->map[i];
386  else
387  e = p->next;
388  ret++;
389  }
390  else
391  {
392  p = e;
393  e = e->next;
394  }
395  }
396  return ret;
397 }
398 
399 
409 int
411  const struct GNUNET_CONTAINER_MultiHashMap32 *map,
412  uint32_t key)
413 {
414  struct MapEntry *e;
415 
416  e = map->map[idx_of (map, key)];
417  while (e != NULL)
418  {
419  if (key == e->key)
420  return GNUNET_YES;
421  e = e->next;
422  }
423  return GNUNET_NO;
424 }
425 
426 
437 int
439  const struct GNUNET_CONTAINER_MultiHashMap32 *map,
440  uint32_t key,
441  const void *value)
442 {
443  struct MapEntry *e;
444 
445  e = map->map[idx_of (map, key)];
446  while (e != NULL)
447  {
448  if ((key == e->key) && (e->value == value))
449  return GNUNET_YES;
450  e = e->next;
451  }
452  return GNUNET_NO;
453 }
454 
455 
461 static void
463 {
464  struct MapEntry **old_map;
465  struct MapEntry **new_map;
466  struct MapEntry *e;
467  unsigned int old_len;
468  unsigned int new_len;
469  unsigned int idx;
470 
471  old_map = map->map;
472  old_len = map->map_length;
473  new_len = old_len * 2;
474  if (0 == new_len) /* 2^31 * 2 == 0 */
475  new_len = old_len; /* never use 0 */
476  if (new_len == old_len)
477  return; /* nothing changed */
478  new_map = GNUNET_malloc_large (new_len * sizeof(struct MapEntry *));
479  if (NULL == new_map)
480  return; /* grow not possible */
481  map->modification_counter++;
482  map->map_length = new_len;
483  map->map = new_map;
484  for (unsigned int i = 0; i < old_len; i++)
485  {
486  while (NULL != (e = old_map[i]))
487  {
488  old_map[i] = e->next;
489  idx = idx_of (map, e->key);
490  e->next = new_map[idx];
491  new_map[idx] = e;
492  }
493  }
494  GNUNET_free (old_map);
495 }
496 
497 
510 int
513  uint32_t key,
514  void *value,
516 {
517  struct MapEntry *e;
518  unsigned int i;
519 
520  i = idx_of (map, key);
523  {
524  e = map->map[i];
525  while (e != NULL)
526  {
527  if (key == e->key)
528  {
530  return GNUNET_SYSERR;
531  e->value = value;
532  return GNUNET_NO;
533  }
534  e = e->next;
535  }
536  }
537  if (map->size / 3 >= map->map_length / 4)
538  {
539  grow (map);
540  i = idx_of (map, key);
541  }
542  e = GNUNET_new (struct MapEntry);
543  e->key = key;
544  e->value = value;
545  e->next = map->map[i];
546  map->map[i] = e;
547  map->size++;
548  return GNUNET_OK;
549 }
550 
551 
562 int
565  uint32_t key,
567  void *it_cls)
568 {
569  int count;
570  struct MapEntry *e;
571  struct MapEntry **ce;
572 
573  count = 0;
574  ce = &map->next_cache[map->next_cache_off];
576 
577  *ce = map->map[idx_of (map, key)];
578  while (NULL != (e = *ce))
579  {
580  *ce = e->next;
581  if (key != e->key)
582  continue;
583  if ((NULL != it) && (GNUNET_OK != it (it_cls, key, e->value)))
584  {
586  return GNUNET_SYSERR;
587  }
588  count++;
589  }
591  return count;
592 }
593 
594 
609  const struct GNUNET_CONTAINER_MultiHashMap32 *map)
610 {
612 
614  iter->map = map;
616  iter->me = map->map[0];
617  return iter;
618 }
619 
620 
635 int
638  uint32_t *key,
639  const void **value)
640 {
641  /* make sure the map has not been modified */
643 
644  /* look for the next entry, skipping empty buckets */
645  while (1)
646  {
647  if (iter->idx >= iter->map->map_length)
648  return GNUNET_NO;
649  if (NULL != iter->me)
650  {
651  if (NULL != key)
652  *key = iter->me->key;
653  if (NULL != value)
654  *value = iter->me->value;
655  iter->me = iter->me->next;
656  return GNUNET_YES;
657  }
658  iter->idx += 1;
659  if (iter->idx < iter->map->map_length)
660  iter->me = iter->map->map[iter->idx];
661  }
662 }
663 
664 
670 void
673 {
674  GNUNET_free (iter);
675 }
676 
677 
678 /* end of container_multihashmap.c */
static GNUNET_NETWORK_STRUCT_END struct GNUNET_PeerIdentity me
Our own peer identity.
GNUNET_CONTAINER_MultiHashMapOption
Options for storing values in the HashMap.
void GNUNET_CONTAINER_multihashmap32_iterator_destroy(struct GNUNET_CONTAINER_MultiHashMapIterator *iter)
Destroy a multihashmap iterator.
int GNUNET_CONTAINER_multihashmap32_iterate(struct GNUNET_CONTAINER_MultiHashMap32 *map, GNUNET_CONTAINER_MulitHashMapIterator32Callback it, void *it_cls)
Iterate over all entries in the map.
#define GNUNET_assert(cond)
Use this for fatal errors that cannot be handled.
struct MapEntry ** map
All of our buckets.
uint32_t key
Key for the entry.
static int ret
Return value of the commandline.
Definition: gnunet-abd.c:81
static struct Experiment * e
#define GNUNET_NO
Definition: gnunet_common.h:78
#define GNUNET_OK
Named constants for return values.
Definition: gnunet_common.h:75
struct MapEntry * me
Position in the bucket idx.
#define GNUNET_new(type)
Allocate a struct or union of the given type.
int GNUNET_CONTAINER_multihashmap32_get_multiple(struct GNUNET_CONTAINER_MultiHashMap32 *map, uint32_t key, GNUNET_CONTAINER_MulitHashMapIterator32Callback it, void *it_cls)
Iterate over all entries in the map that match a particular key.
unsigned int modification_counter
Modification counter as observed on the map when the iterator was created.
#define GNUNET_malloc_large(size)
Wrapper around malloc.
int GNUNET_CONTAINER_multihashmap32_put(struct GNUNET_CONTAINER_MultiHashMap32 *map, uint32_t key, void *value, enum GNUNET_CONTAINER_MultiHashMapOption opt)
Store a key-value pair in the map.
int GNUNET_CONTAINER_multihashmap32_remove_all(struct GNUNET_CONTAINER_MultiHashMap32 *map, uint32_t key)
Remove all entries for the given key from the map.
static struct GNUNET_CONTAINER_MultiPeerMap * map
Handle to the map used to store old latency values for peers.
unsigned int size
Number of entries in the map.
static struct GNUNET_ARM_MonitorHandle * m
Monitor connection with ARM.
Definition: gnunet-arm.c:104
static void grow(struct GNUNET_CONTAINER_MultiHashMap32 *map)
Grow the given map to a more appropriate size.
static struct GNUNET_OS_Process * p
Helper process we started.
Definition: gnunet-qr.c:59
int GNUNET_CONTAINER_multihashmap32_remove(struct GNUNET_CONTAINER_MultiHashMap32 *map, uint32_t key, const void *value)
Remove the given key-value pair from the map.
, &#39; bother checking if a value already exists (faster than GNUNET_CONTAINER_MULTIHASHMAPOPTION_...
int GNUNET_CONTAINER_multihashmap32_contains(const struct GNUNET_CONTAINER_MultiHashMap32 *map, uint32_t key)
Check if the map contains any value under the given key (including values that are NULL)...
void * GNUNET_CONTAINER_multihashmap32_get(const struct GNUNET_CONTAINER_MultiHashMap32 *map, uint32_t key)
Given a key find a value in the map matching the key.
Entry in the map.
unsigned int GNUNET_CONTAINER_multihashmap32_size(const struct GNUNET_CONTAINER_MultiHashMap32 *map)
Get the number of key-value pairs in the map.
#define NEXT_CACHE_SIZE
Maximum recursion depth for callbacks of GNUNET_CONTAINER_multihashmap_get_multiple() themselves agai...
Internal representation of the hash map.
void * value
Value of the entry.
struct GNUNET_CONTAINER_MultiHashMap32 * GNUNET_CONTAINER_multihashmap32_create(unsigned int len)
Create a multi hash map.
void GNUNET_CONTAINER_multihashmap32_destroy(struct GNUNET_CONTAINER_MultiHashMap32 *map)
Destroy a hash map.
static void update_next_cache(struct GNUNET_CONTAINER_MultiHashMap32 *map, const struct MapEntry *me)
We are about to free() the bme, make sure it is not in the list of next values for any iterator in th...
There must only be one value per key; storing a value should fail if a value under the same key alrea...
#define GNUNET_SYSERR
Definition: gnunet_common.h:76
struct GNUNET_CONTAINER_MultiHashMap32Iterator * GNUNET_CONTAINER_multihashmap32_iterator_create(const struct GNUNET_CONTAINER_MultiHashMap32 *map)
Create an iterator for a multihashmap.
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...
Allow multiple values with the same key.
int GNUNET_CONTAINER_multihashmap32_iterator_next(struct GNUNET_CONTAINER_MultiHashMap32Iterator *iter, uint32_t *key, const void **value)
Retrieve the next element from the hash map at the iterator&#39;s position.
struct MapEntry * next_cache[16]
Map entries indicating iteration positions currently in use by GNUNET_CONTAINER_multihashmap_get_mult...
#define GNUNET_YES
Definition: gnunet_common.h:77
struct MapEntry * next
If there is a hash collision, we create a linked list.
unsigned int idx
Current bucket index.
const struct GNUNET_CONTAINER_MultiHashMap32 * map
Map that we are iterating over.
int GNUNET_CONTAINER_multihashmap32_contains_value(const struct GNUNET_CONTAINER_MultiHashMap32 *map, uint32_t key, const void *value)
Check if the map contains the given value under the given key.
int(* GNUNET_CONTAINER_MulitHashMapIterator32Callback)(void *cls, uint32_t key, void *value)
Iterator over hash map entries.
static unsigned int idx_of(const struct GNUNET_CONTAINER_MultiHashMap32 *m, const uint32_t key)
Compute the index of the bucket for the given key.
unsigned int next_cache_off
Offset of next_cache entries in use, must be smaller than NEXT_CACHE_SIZE.
#define GNUNET_free(ptr)
Wrapper around free.
uint16_t len
length of data (which is always a uint32_t, but presumably this can be used to specify that fewer byt...