GNUnet  0.10.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,...) GNUNET_log_from (kind, "util-container-multihashmap32", __VA_ARGS__)
32 
33 
40 #define NEXT_CACHE_SIZE 16
41 
45 struct MapEntry
46 {
47 
51  uint32_t key;
52 
56  void *value;
57 
61  struct MapEntry *next;
62 
63 };
64 
69 {
70 
74  struct MapEntry **map;
75 
79  unsigned int size;
80 
84  unsigned int map_length;
85 
90  unsigned int modification_counter;
91 
97  struct MapEntry *next_cache[NEXT_CACHE_SIZE];
98 
103  unsigned int next_cache_off;
104 };
105 
106 
112 {
116  struct MapEntry *me;
117 
121  unsigned int idx;
122 
127  unsigned int modification_counter;
128 
133 };
134 
135 
144 {
146 
147  GNUNET_assert (len > 0);
149  ret->map = GNUNET_malloc_large (len *
150  sizeof (struct MapEntry *));
151  if (NULL == ret->map)
152  {
153  GNUNET_free (ret);
154  return NULL;
155  }
156  ret->map_length = len;
157  return ret;
158 }
159 
160 
167 void
169 {
170  struct MapEntry *e;
171 
172  for (unsigned int i = 0; i < map->map_length; i++)
173  {
174  while (NULL != (e = map->map[i]))
175  {
176  map->map[i] = e->next;
177  GNUNET_free (e);
178  }
179  }
180  GNUNET_free (map->map);
181  GNUNET_free (map);
182 }
183 
184 
192 static unsigned int
194  const uint32_t key)
195 {
196  GNUNET_assert (NULL != m);
197  return ((unsigned int) key) % m->map_length;
198 }
199 
200 
207 unsigned int
209 {
210  return map->size;
211 }
212 
213 
224 void *
226  uint32_t key)
227 {
228  struct MapEntry *e;
229 
230  e = map->map[idx_of (map, key)];
231  while (NULL != e)
232  {
233  if (key == e->key)
234  return e->value;
235  e = e->next;
236  }
237  return NULL;
238 }
239 
240 
250 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,
273  e->key,
274  e->value))
275  {
277  return GNUNET_SYSERR;
278  }
279  }
280  count++;
281  }
282  }
284  return count;
285 }
286 
287 
295 static void
297  const struct MapEntry *me)
298 {
299  for (unsigned int i=0;i<map->next_cache_off;i++)
300  if (map->next_cache[i] == me)
301  map->next_cache[i] = me->next;
302 }
303 
304 
316 int
318  uint32_t key,
319  const void *value)
320 {
321  struct MapEntry *e;
322  struct MapEntry *p;
323  unsigned int i;
324 
325  map->modification_counter++;
326 
327  i = idx_of (map, key);
328  p = NULL;
329  e = map->map[i];
330  while (e != NULL)
331  {
332  if ( (key == e->key) && (value == e->value) )
333  {
334  if (p == NULL)
335  map->map[i] = e->next;
336  else
337  p->next = e->next;
338  update_next_cache (map,
339  e);
340  GNUNET_free (e);
341  map->size--;
342  return GNUNET_YES;
343  }
344  p = e;
345  e = e->next;
346  }
347  return GNUNET_NO;
348 }
349 
350 
359 int
361  uint32_t key)
362 {
363  struct MapEntry *e;
364  struct MapEntry *p;
365  unsigned int i;
366  int ret;
367 
368  map->modification_counter++;
369 
370  ret = 0;
371  i = idx_of (map, key);
372  p = NULL;
373  e = map->map[i];
374  while (e != NULL)
375  {
376  if (key == e->key)
377  {
378  if (p == NULL)
379  map->map[i] = e->next;
380  else
381  p->next = e->next;
382  update_next_cache (map,
383  e);
384  GNUNET_free (e);
385  map->size--;
386  if (p == NULL)
387  e = map->map[i];
388  else
389  e = p->next;
390  ret++;
391  }
392  else
393  {
394  p = e;
395  e = e->next;
396  }
397  }
398  return ret;
399 }
400 
401 
411 int
413  uint32_t key)
414 {
415  struct MapEntry *e;
416 
417  e = map->map[idx_of (map, key)];
418  while (e != NULL)
419  {
420  if (key == e->key)
421  return GNUNET_YES;
422  e = e->next;
423  }
424  return GNUNET_NO;
425 }
426 
427 
438 int
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 *
479  sizeof (struct MapEntry *));
480  if (NULL == new_map)
481  return; /* grow not possible */
482  map->modification_counter++;
483  map->map_length = new_len;
484  map->map = new_map;
485  for (unsigned int i = 0; i < old_len; i++)
486  {
487  while (NULL != (e = old_map[i]))
488  {
489  old_map[i] = e->next;
490  idx = idx_of (map, e->key);
491  e->next = new_map[idx];
492  new_map[idx] = e;
493  }
494  }
495  GNUNET_free (old_map);
496 }
497 
498 
511 int
513  *map, uint32_t key, void *value,
515  opt)
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
564  uint32_t key,
566  void *it_cls)
567 {
568  int count;
569  struct MapEntry *e;
570  struct MapEntry **ce;
571 
572  count = 0;
573  ce = &map->next_cache[map->next_cache_off];
575 
576  *ce = map->map[idx_of (map, key)];
577  while (NULL != (e = *ce))
578  {
579  *ce = e->next;
580  if (key != e->key)
581  continue;
582  if ( (NULL != it) &&
583  (GNUNET_OK != it (it_cls,
584  key,
585  e->value)) )
586  {
588  return GNUNET_SYSERR;
589  }
590  count++;
591  }
593  return count;
594 }
595 
596 
611 {
613 
615  iter->map = map;
617  iter->me = map->map[0];
618  return iter;
619 }
620 
621 
636 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
672 {
673  GNUNET_free (iter);
674 }
675 
676 
677 /* end of container_multihashmap.c */
int(* GNUNET_CONTAINER_HashMapIterator32)(void *cls, uint32_t key, void *value)
Iterator over hash map entries.
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.
#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 struct Experiment * e
#define GNUNET_NO
Definition: gnunet_common.h:81
#define GNUNET_OK
Named constants for return values.
Definition: gnunet_common.h:78
struct MapEntry * me
Position in the bucket idx.
#define GNUNET_new(type)
Allocate a struct or union of the given type.
unsigned int modification_counter
Modification counter as observed on the map when the iterator was created.
static int ret
Final status code.
Definition: gnunet-arm.c:89
#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:99
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:79
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...
int GNUNET_CONTAINER_multihashmap32_iterate(struct GNUNET_CONTAINER_MultiHashMap32 *map, GNUNET_CONTAINER_HashMapIterator32 it, void *it_cls)
Iterate over all entries in the map.
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:80
struct MapEntry * next
If there is a hash collision, we create a linked list.
int GNUNET_CONTAINER_multihashmap32_get_multiple(struct GNUNET_CONTAINER_MultiHashMap32 *map, uint32_t key, GNUNET_CONTAINER_HashMapIterator32 it, void *it_cls)
Iterate over all entries in the map that match a particular key.
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.
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...