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, ...) \
32  GNUNET_log_from(kind, "util-container-multihashmap32", __VA_ARGS__)
33 
34 
41 #define NEXT_CACHE_SIZE 16
42 
46 struct MapEntry {
50  uint32_t key;
51 
55  void *value;
56 
60  struct MapEntry *next;
61 };
62 
70  struct MapEntry **map;
71 
75  unsigned int size;
76 
80  unsigned int map_length;
81 
86  unsigned int modification_counter;
87 
93  struct MapEntry *next_cache[NEXT_CACHE_SIZE];
94 
99  unsigned int next_cache_off;
100 };
101 
102 
111  struct MapEntry *me;
112 
116  unsigned int idx;
117 
122  unsigned int modification_counter;
123 
128 };
129 
130 
139 {
141 
142  GNUNET_assert(len > 0);
144  ret->map = GNUNET_malloc_large(len * sizeof(struct MapEntry *));
145  if (NULL == ret->map)
146  {
147  GNUNET_free(ret);
148  return NULL;
149  }
150  ret->map_length = len;
151  return ret;
152 }
153 
154 
161 void
164 {
165  struct MapEntry *e;
166 
167  for (unsigned int i = 0; i < map->map_length; i++)
168  {
169  while (NULL != (e = map->map[i]))
170  {
171  map->map[i] = e->next;
172  GNUNET_free(e);
173  }
174  }
175  GNUNET_free(map->map);
176  GNUNET_free(map);
177 }
178 
179 
187 static unsigned int
188 idx_of(const struct GNUNET_CONTAINER_MultiHashMap32 *m, const uint32_t key)
189 {
190  GNUNET_assert(NULL != m);
191  return ((unsigned int)key) % m->map_length;
192 }
193 
194 
201 unsigned int
203  const struct GNUNET_CONTAINER_MultiHashMap32 *map)
204 {
205  return map->size;
206 }
207 
208 
219 void *
221  const struct GNUNET_CONTAINER_MultiHashMap32 *map,
222  uint32_t key)
223 {
224  struct MapEntry *e;
225 
226  e = map->map[idx_of(map, key)];
227  while (NULL != e)
228  {
229  if (key == e->key)
230  return e->value;
231  e = e->next;
232  }
233  return NULL;
234 }
235 
236 
246 int
250  void *it_cls)
251 {
252  int count;
253  struct MapEntry **ce;
254 
255  count = 0;
256  GNUNET_assert(NULL != map);
257  ce = &map->next_cache[map->next_cache_off];
259  for (unsigned int i = 0; i < map->map_length; i++)
260  {
261  struct MapEntry *e;
262 
263  *ce = map->map[i];
264  while (NULL != (e = *ce))
265  {
266  *ce = e->next;
267  if (NULL != it)
268  {
269  if (GNUNET_OK != it(it_cls, e->key, e->value))
270  {
272  return GNUNET_SYSERR;
273  }
274  }
275  count++;
276  }
277  }
279  return count;
280 }
281 
282 
290 static void
292  const struct MapEntry *me)
293 {
294  for (unsigned int i = 0; i < map->next_cache_off; i++)
295  if (map->next_cache[i] == me)
296  map->next_cache[i] = me->next;
297 }
298 
299 
311 int
314  uint32_t key,
315  const void *value)
316 {
317  struct MapEntry *e;
318  struct MapEntry *p;
319  unsigned int i;
320 
321  map->modification_counter++;
322 
323  i = idx_of(map, key);
324  p = NULL;
325  e = map->map[i];
326  while (e != NULL)
327  {
328  if ((key == e->key) && (value == e->value))
329  {
330  if (p == NULL)
331  map->map[i] = e->next;
332  else
333  p->next = e->next;
334  update_next_cache(map, e);
335  GNUNET_free(e);
336  map->size--;
337  return GNUNET_YES;
338  }
339  p = e;
340  e = e->next;
341  }
342  return GNUNET_NO;
343 }
344 
345 
354 int
357  uint32_t key)
358 {
359  struct MapEntry *e;
360  struct MapEntry *p;
361  unsigned int i;
362  int ret;
363 
364  map->modification_counter++;
365 
366  ret = 0;
367  i = idx_of(map, key);
368  p = NULL;
369  e = map->map[i];
370  while (e != NULL)
371  {
372  if (key == e->key)
373  {
374  if (p == NULL)
375  map->map[i] = e->next;
376  else
377  p->next = e->next;
378  update_next_cache(map, e);
379  GNUNET_free(e);
380  map->size--;
381  if (p == NULL)
382  e = map->map[i];
383  else
384  e = p->next;
385  ret++;
386  }
387  else
388  {
389  p = e;
390  e = e->next;
391  }
392  }
393  return ret;
394 }
395 
396 
406 int
408  const struct GNUNET_CONTAINER_MultiHashMap32 *map,
409  uint32_t key)
410 {
411  struct MapEntry *e;
412 
413  e = map->map[idx_of(map, key)];
414  while (e != NULL)
415  {
416  if (key == e->key)
417  return GNUNET_YES;
418  e = e->next;
419  }
420  return GNUNET_NO;
421 }
422 
423 
434 int
436  const struct GNUNET_CONTAINER_MultiHashMap32 *map,
437  uint32_t key,
438  const void *value)
439 {
440  struct MapEntry *e;
441 
442  e = map->map[idx_of(map, key)];
443  while (e != NULL)
444  {
445  if ((key == e->key) && (e->value == value))
446  return GNUNET_YES;
447  e = e->next;
448  }
449  return GNUNET_NO;
450 }
451 
452 
458 static void
460 {
461  struct MapEntry **old_map;
462  struct MapEntry **new_map;
463  struct MapEntry *e;
464  unsigned int old_len;
465  unsigned int new_len;
466  unsigned int idx;
467 
468  old_map = map->map;
469  old_len = map->map_length;
470  new_len = old_len * 2;
471  if (0 == new_len) /* 2^31 * 2 == 0 */
472  new_len = old_len; /* never use 0 */
473  if (new_len == old_len)
474  return; /* nothing changed */
475  new_map = GNUNET_malloc_large(new_len * sizeof(struct MapEntry *));
476  if (NULL == new_map)
477  return; /* grow not possible */
478  map->modification_counter++;
479  map->map_length = new_len;
480  map->map = new_map;
481  for (unsigned int i = 0; i < old_len; i++)
482  {
483  while (NULL != (e = old_map[i]))
484  {
485  old_map[i] = e->next;
486  idx = idx_of(map, e->key);
487  e->next = new_map[idx];
488  new_map[idx] = e;
489  }
490  }
491  GNUNET_free(old_map);
492 }
493 
494 
507 int
510  uint32_t key,
511  void *value,
513 {
514  struct MapEntry *e;
515  unsigned int i;
516 
517  i = idx_of(map, key);
520  {
521  e = map->map[i];
522  while (e != NULL)
523  {
524  if (key == e->key)
525  {
527  return GNUNET_SYSERR;
528  e->value = value;
529  return GNUNET_NO;
530  }
531  e = e->next;
532  }
533  }
534  if (map->size / 3 >= map->map_length / 4)
535  {
536  grow(map);
537  i = idx_of(map, key);
538  }
539  e = GNUNET_new(struct MapEntry);
540  e->key = key;
541  e->value = value;
542  e->next = map->map[i];
543  map->map[i] = e;
544  map->size++;
545  return GNUNET_OK;
546 }
547 
548 
559 int
562  uint32_t key,
564  void *it_cls)
565 {
566  int count;
567  struct MapEntry *e;
568  struct MapEntry **ce;
569 
570  count = 0;
571  ce = &map->next_cache[map->next_cache_off];
573 
574  *ce = map->map[idx_of(map, key)];
575  while (NULL != (e = *ce))
576  {
577  *ce = e->next;
578  if (key != e->key)
579  continue;
580  if ((NULL != it) && (GNUNET_OK != it(it_cls, key, e->value)))
581  {
583  return GNUNET_SYSERR;
584  }
585  count++;
586  }
588  return count;
589 }
590 
591 
606  const struct GNUNET_CONTAINER_MultiHashMap32 *map)
607 {
609 
611  iter->map = map;
613  iter->me = map->map[0];
614  return iter;
615 }
616 
617 
632 int
635  uint32_t *key,
636  const void **value)
637 {
638  /* make sure the map has not been modified */
640 
641  /* look for the next entry, skipping empty buckets */
642  while (1)
643  {
644  if (iter->idx >= iter->map->map_length)
645  return GNUNET_NO;
646  if (NULL != iter->me)
647  {
648  if (NULL != key)
649  *key = iter->me->key;
650  if (NULL != value)
651  *value = iter->me->value;
652  iter->me = iter->me->next;
653  return GNUNET_YES;
654  }
655  iter->idx += 1;
656  if (iter->idx < iter->map->map_length)
657  iter->me = iter->map->map[iter->idx];
658  }
659 }
660 
661 
667 void
670 {
671  GNUNET_free(iter);
672 }
673 
674 
675 /* 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 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.
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: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...