GNUnet  0.17.6
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 
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 
198 unsigned int
200  const struct GNUNET_CONTAINER_MultiHashMap32 *map)
201 {
202  return map->size;
203 }
204 
205 
206 void *
208  const struct GNUNET_CONTAINER_MultiHashMap32 *map,
209  uint32_t key)
210 {
211  struct MapEntry *e;
212 
213  e = map->map[idx_of (map, key)];
214  while (NULL != e)
215  {
216  if (key == e->key)
217  return e->value;
218  e = e->next;
219  }
220  return NULL;
221 }
222 
223 
224 int
228  void *it_cls)
229 {
230  int count;
231  struct MapEntry **ce;
232 
233  count = 0;
234  GNUNET_assert (NULL != map);
235  ce = &map->next_cache[map->next_cache_off];
237  for (unsigned int i = 0; i < map->map_length; i++)
238  {
239  struct MapEntry *e;
240 
241  *ce = map->map[i];
242  while (NULL != (e = *ce))
243  {
244  *ce = e->next;
245  if (NULL != it)
246  {
247  if (GNUNET_OK != it (it_cls, e->key, e->value))
248  {
250  return GNUNET_SYSERR;
251  }
252  }
253  count++;
254  }
255  }
257  return count;
258 }
259 
260 
268 static void
270  const struct MapEntry *me)
271 {
272  for (unsigned int i = 0; i < map->next_cache_off; i++)
273  if (map->next_cache[i] == me)
274  map->next_cache[i] = me->next;
275 }
276 
277 
278 int
281  uint32_t key,
282  const void *value)
283 {
284  struct MapEntry *e;
285  struct MapEntry *p;
286  unsigned int i;
287 
289 
290  i = idx_of (map, key);
291  p = NULL;
292  e = map->map[i];
293  while (e != NULL)
294  {
295  if ((key == e->key) && (value == e->value))
296  {
297  if (p == NULL)
298  map->map[i] = e->next;
299  else
300  p->next = e->next;
302  GNUNET_free (e);
303  map->size--;
304  return GNUNET_YES;
305  }
306  p = e;
307  e = e->next;
308  }
309  return GNUNET_NO;
310 }
311 
312 
313 int
316  uint32_t key)
317 {
318  struct MapEntry *e;
319  struct MapEntry *p;
320  unsigned int i;
321  int ret;
322 
324 
325  ret = 0;
326  i = idx_of (map, key);
327  p = NULL;
328  e = map->map[i];
329  while (e != NULL)
330  {
331  if (key == e->key)
332  {
333  if (p == NULL)
334  map->map[i] = e->next;
335  else
336  p->next = e->next;
338  GNUNET_free (e);
339  map->size--;
340  if (p == NULL)
341  e = map->map[i];
342  else
343  e = p->next;
344  ret++;
345  }
346  else
347  {
348  p = e;
349  e = e->next;
350  }
351  }
352  return ret;
353 }
354 
355 
356 int
358  const struct GNUNET_CONTAINER_MultiHashMap32 *map,
359  uint32_t key)
360 {
361  struct MapEntry *e;
362 
363  e = map->map[idx_of (map, key)];
364  while (e != NULL)
365  {
366  if (key == e->key)
367  return GNUNET_YES;
368  e = e->next;
369  }
370  return GNUNET_NO;
371 }
372 
373 
374 int
376  const struct GNUNET_CONTAINER_MultiHashMap32 *map,
377  uint32_t key,
378  const void *value)
379 {
380  struct MapEntry *e;
381 
382  e = map->map[idx_of (map, key)];
383  while (e != NULL)
384  {
385  if ((key == e->key) && (e->value == value))
386  return GNUNET_YES;
387  e = e->next;
388  }
389  return GNUNET_NO;
390 }
391 
392 
398 static void
400 {
401  struct MapEntry **old_map;
402  struct MapEntry **new_map;
403  struct MapEntry *e;
404  unsigned int old_len;
405  unsigned int new_len;
406  unsigned int idx;
407 
408  old_map = map->map;
409  old_len = map->map_length;
410  new_len = old_len * 2;
411  if (0 == new_len) /* 2^31 * 2 == 0 */
412  new_len = old_len; /* never use 0 */
413  if (new_len == old_len)
414  return; /* nothing changed */
415  new_map = GNUNET_malloc_large (new_len * sizeof(struct MapEntry *));
416  if (NULL == new_map)
417  return; /* grow not possible */
419  map->map_length = new_len;
420  map->map = new_map;
421  for (unsigned int i = 0; i < old_len; i++)
422  {
423  while (NULL != (e = old_map[i]))
424  {
425  old_map[i] = e->next;
426  idx = idx_of (map, e->key);
427  e->next = new_map[idx];
428  new_map[idx] = e;
429  }
430  }
431  GNUNET_free (old_map);
432 }
433 
434 
447 int
450  uint32_t key,
451  void *value,
453 {
454  struct MapEntry *e;
455  unsigned int i;
456 
457  i = idx_of (map, key);
460  {
461  e = map->map[i];
462  while (e != NULL)
463  {
464  if (key == e->key)
465  {
467  return GNUNET_SYSERR;
468  e->value = value;
469  return GNUNET_NO;
470  }
471  e = e->next;
472  }
473  }
474  if (map->size / 3 >= map->map_length / 4)
475  {
476  grow (map);
477  i = idx_of (map, key);
478  }
479  e = GNUNET_new (struct MapEntry);
480  e->key = key;
481  e->value = value;
482  e->next = map->map[i];
483  map->map[i] = e;
484  map->size++;
485  return GNUNET_OK;
486 }
487 
488 
489 int
492  uint32_t key,
494  void *it_cls)
495 {
496  int count;
497  struct MapEntry *e;
498  struct MapEntry **ce;
499 
500  count = 0;
501  ce = &map->next_cache[map->next_cache_off];
503 
504  *ce = map->map[idx_of (map, key)];
505  while (NULL != (e = *ce))
506  {
507  *ce = e->next;
508  if (key != e->key)
509  continue;
510  if ((NULL != it) && (GNUNET_OK != it (it_cls, key, e->value)))
511  {
513  return GNUNET_SYSERR;
514  }
515  count++;
516  }
518  return count;
519 }
520 
521 
536  const struct GNUNET_CONTAINER_MultiHashMap32 *map)
537 {
539 
541  iter->map = map;
543  iter->me = map->map[0];
544  return iter;
545 }
546 
547 
562 int
565  uint32_t *key,
566  const void **value)
567 {
568  /* make sure the map has not been modified */
570 
571  /* look for the next entry, skipping empty buckets */
572  while (1)
573  {
574  if (iter->idx >= iter->map->map_length)
575  return GNUNET_NO;
576  if (NULL != iter->me)
577  {
578  if (NULL != key)
579  *key = iter->me->key;
580  if (NULL != value)
581  *value = iter->me->value;
582  iter->me = iter->me->next;
583  return GNUNET_YES;
584  }
585  iter->idx += 1;
586  if (iter->idx < iter->map->map_length)
587  iter->me = iter->map->map[iter->idx];
588  }
589 }
590 
591 
597 void
600 {
601  GNUNET_free (iter);
602 }
603 
604 
605 /* end of container_multihashmap.c */
#define NEXT_CACHE_SIZE
Maximum recursion depth for callbacks of GNUNET_CONTAINER_multihashmap_get_multiple() themselves agai...
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.
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...
static void grow(struct GNUNET_CONTAINER_MultiHashMap32 *map)
Grow the given map to a more appropriate size.
static int ret
Return value of the commandline.
Definition: gnunet-abd.c:81
static struct GNUNET_ARM_MonitorHandle * m
Monitor connection with ARM.
Definition: gnunet-arm.c:104
static struct Experiment * e
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.
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.
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_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).
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.
unsigned int GNUNET_CONTAINER_multihashmap32_size(const struct GNUNET_CONTAINER_MultiHashMap32 *map)
Get the number of key-value pairs in the map.
int GNUNET_CONTAINER_multihashmap32_iterate(struct GNUNET_CONTAINER_MultiHashMap32 *map, GNUNET_CONTAINER_MulitHashMapIterator32Callback it, void *it_cls)
Iterate over all entries in the map.
GNUNET_CONTAINER_MultiHashMapOption
Options for storing values in the HashMap.
struct GNUNET_CONTAINER_MultiHashMap32 * GNUNET_CONTAINER_multihashmap32_create(unsigned int len)
Create a multi hash map.
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.
void GNUNET_CONTAINER_multihashmap32_destroy(struct GNUNET_CONTAINER_MultiHashMap32 *map)
Destroy a hash 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.
enum GNUNET_GenericReturnValue(* GNUNET_CONTAINER_MulitHashMapIterator32Callback)(void *cls, uint32_t key, void *value)
Iterator over hash map entries.
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.
@ 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...
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's position.
void GNUNET_CONTAINER_multihashmap32_iterator_destroy(struct GNUNET_CONTAINER_MultiHashMapIterator *iter)
Destroy a multihashmap iterator.
struct GNUNET_CONTAINER_MultiHashMap32Iterator * GNUNET_CONTAINER_multihashmap32_iterator_create(const struct GNUNET_CONTAINER_MultiHashMap32 *map)
Create an iterator for a multihashmap.
@ 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_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.
struct 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_MultiHashMap32 * map
Map that we are iterating over.
Internal representation of the hash map.
unsigned int modification_counter
Counts the destructive modifications (grow, remove) to the map, so that iterators can check if they a...
struct MapEntry * next_cache[16]
Map entries indicating iteration positions currently in use by GNUNET_CONTAINER_multihashmap_get_mult...
struct 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.
unsigned int map_length
Length of the map array.
unsigned int size
Number of entries in the map.
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.
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...
Entry in the map.
void * value
Value of the entry.
uint32_t key
Key for the entry.
struct MapEntry * next
If there is a hash collision, we create a linked list.