GNUnet  0.19.4
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  */
29 #include "platform.h"
30 #include "gnunet_util_lib.h"
31 
32 #define LOG(kind, ...) \
33  GNUNET_log_from (kind, "util-container-multihashmap32", __VA_ARGS__)
34 
35 
42 #define NEXT_CACHE_SIZE 16
43 
47 struct MapEntry
48 {
52  uint32_t key;
53 
57  void *value;
58 
62  struct MapEntry *next;
63 };
64 
69 {
73  struct MapEntry **map;
74 
78  unsigned int size;
79 
83  unsigned int map_length;
84 
89  unsigned int modification_counter;
90 
97 
102  unsigned int next_cache_off;
103 };
104 
105 
111 {
115  struct MapEntry *me;
116 
120  unsigned int idx;
121 
126  unsigned int modification_counter;
127 
132 };
133 
134 
143 {
145 
146  GNUNET_assert (len > 0);
148  ret->map = GNUNET_malloc_large (len * sizeof(struct MapEntry *));
149  if (NULL == ret->map)
150  {
151  GNUNET_free (ret);
152  return NULL;
153  }
154  ret->map_length = len;
155  return ret;
156 }
157 
158 
165 void
168 {
169  struct MapEntry *e;
170 
171  for (unsigned int i = 0; i < map->map_length; i++)
172  {
173  while (NULL != (e = map->map[i]))
174  {
175  map->map[i] = e->next;
176  GNUNET_free (e);
177  }
178  }
179  GNUNET_free (map->map);
180  GNUNET_free (map);
181 }
182 
183 
191 static unsigned int
192 idx_of (const struct GNUNET_CONTAINER_MultiHashMap32 *m, const uint32_t key)
193 {
194  GNUNET_assert (NULL != m);
195  return ((unsigned int) key) % m->map_length;
196 }
197 
198 
199 unsigned int
201  const struct GNUNET_CONTAINER_MultiHashMap32 *map)
202 {
203  return map->size;
204 }
205 
206 
207 void *
209  const struct GNUNET_CONTAINER_MultiHashMap32 *map,
210  uint32_t key)
211 {
212  struct MapEntry *e;
213 
214  e = map->map[idx_of (map, key)];
215  while (NULL != e)
216  {
217  if (key == e->key)
218  return e->value;
219  e = e->next;
220  }
221  return NULL;
222 }
223 
224 
225 int
229  void *it_cls)
230 {
231  int count;
232  struct MapEntry **ce;
233 
234  count = 0;
235  GNUNET_assert (NULL != map);
236  ce = &map->next_cache[map->next_cache_off];
238  for (unsigned int i = 0; i < map->map_length; i++)
239  {
240  struct MapEntry *e;
241 
242  *ce = map->map[i];
243  while (NULL != (e = *ce))
244  {
245  *ce = e->next;
246  if (NULL != it)
247  {
248  if (GNUNET_OK != it (it_cls, e->key, e->value))
249  {
251  return GNUNET_SYSERR;
252  }
253  }
254  count++;
255  }
256  }
258  return count;
259 }
260 
261 
269 static void
271  const struct MapEntry *me)
272 {
273  for (unsigned int i = 0; i < map->next_cache_off; i++)
274  if (map->next_cache[i] == me)
275  map->next_cache[i] = me->next;
276 }
277 
278 
279 int
282  uint32_t key,
283  const void *value)
284 {
285  struct MapEntry *e;
286  struct MapEntry *p;
287  unsigned int i;
288 
290 
291  i = idx_of (map, key);
292  p = NULL;
293  e = map->map[i];
294  while (e != NULL)
295  {
296  if ((key == e->key) && (value == e->value))
297  {
298  if (p == NULL)
299  map->map[i] = e->next;
300  else
301  p->next = e->next;
303  GNUNET_free (e);
304  map->size--;
305  return GNUNET_YES;
306  }
307  p = e;
308  e = e->next;
309  }
310  return GNUNET_NO;
311 }
312 
313 
314 int
317  uint32_t key)
318 {
319  struct MapEntry *e;
320  struct MapEntry *p;
321  unsigned int i;
322  int ret;
323 
325 
326  ret = 0;
327  i = idx_of (map, key);
328  p = NULL;
329  e = map->map[i];
330  while (e != NULL)
331  {
332  if (key == e->key)
333  {
334  if (p == NULL)
335  map->map[i] = e->next;
336  else
337  p->next = e->next;
339  GNUNET_free (e);
340  map->size--;
341  if (p == NULL)
342  e = map->map[i];
343  else
344  e = p->next;
345  ret++;
346  }
347  else
348  {
349  p = e;
350  e = e->next;
351  }
352  }
353  return ret;
354 }
355 
356 
357 int
359  const struct GNUNET_CONTAINER_MultiHashMap32 *map,
360  uint32_t key)
361 {
362  struct MapEntry *e;
363 
364  e = map->map[idx_of (map, key)];
365  while (e != NULL)
366  {
367  if (key == e->key)
368  return GNUNET_YES;
369  e = e->next;
370  }
371  return GNUNET_NO;
372 }
373 
374 
375 int
377  const struct GNUNET_CONTAINER_MultiHashMap32 *map,
378  uint32_t key,
379  const void *value)
380 {
381  struct MapEntry *e;
382 
383  e = map->map[idx_of (map, key)];
384  while (e != NULL)
385  {
386  if ((key == e->key) && (e->value == value))
387  return GNUNET_YES;
388  e = e->next;
389  }
390  return GNUNET_NO;
391 }
392 
393 
399 static void
401 {
402  struct MapEntry **old_map;
403  struct MapEntry **new_map;
404  struct MapEntry *e;
405  unsigned int old_len;
406  unsigned int new_len;
407  unsigned int idx;
408 
409  old_map = map->map;
410  old_len = map->map_length;
411  new_len = old_len * 2;
412  if (0 == new_len) /* 2^31 * 2 == 0 */
413  new_len = old_len; /* never use 0 */
414  if (new_len == old_len)
415  return; /* nothing changed */
416  new_map = GNUNET_malloc_large (new_len * sizeof(struct MapEntry *));
417  if (NULL == new_map)
418  return; /* grow not possible */
420  map->map_length = new_len;
421  map->map = new_map;
422  for (unsigned int i = 0; i < old_len; i++)
423  {
424  while (NULL != (e = old_map[i]))
425  {
426  old_map[i] = e->next;
427  idx = idx_of (map, e->key);
428  e->next = new_map[idx];
429  new_map[idx] = e;
430  }
431  }
432  GNUNET_free (old_map);
433 }
434 
435 
448 int
451  uint32_t key,
452  void *value,
454 {
455  struct MapEntry *e;
456  unsigned int i;
457 
458  i = idx_of (map, key);
461  {
462  e = map->map[i];
463  while (e != NULL)
464  {
465  if (key == e->key)
466  {
468  return GNUNET_SYSERR;
469  e->value = value;
470  return GNUNET_NO;
471  }
472  e = e->next;
473  }
474  }
475  if (map->size / 3 >= map->map_length / 4)
476  {
477  grow (map);
478  i = idx_of (map, key);
479  }
480  e = GNUNET_new (struct MapEntry);
481  e->key = key;
482  e->value = value;
483  e->next = map->map[i];
484  map->map[i] = e;
485  map->size++;
486  return GNUNET_OK;
487 }
488 
489 
490 int
493  uint32_t key,
495  void *it_cls)
496 {
497  int count;
498  struct MapEntry *e;
499  struct MapEntry **ce;
500 
501  count = 0;
502  ce = &map->next_cache[map->next_cache_off];
504 
505  *ce = map->map[idx_of (map, key)];
506  while (NULL != (e = *ce))
507  {
508  *ce = e->next;
509  if (key != e->key)
510  continue;
511  if ((NULL != it) && (GNUNET_OK != it (it_cls, key, e->value)))
512  {
514  return GNUNET_SYSERR;
515  }
516  count++;
517  }
519  return count;
520 }
521 
522 
537  const struct GNUNET_CONTAINER_MultiHashMap32 *map)
538 {
540 
542  iter->map = map;
544  iter->me = map->map[0];
545  return iter;
546 }
547 
548 
563 int
566  uint32_t *key,
567  const void **value)
568 {
569  /* make sure the map has not been modified */
571 
572  /* look for the next entry, skipping empty buckets */
573  while (1)
574  {
575  if (iter->idx >= iter->map->map_length)
576  return GNUNET_NO;
577  if (NULL != iter->me)
578  {
579  if (NULL != key)
580  *key = iter->me->key;
581  if (NULL != value)
582  *value = iter->me->value;
583  iter->me = iter->me->next;
584  return GNUNET_YES;
585  }
586  iter->idx += 1;
587  if (iter->idx < iter->map->map_length)
588  iter->me = iter->map->map[iter->idx];
589  }
590 }
591 
592 
598 void
601 {
602  GNUNET_free (iter);
603 }
604 
605 
606 /* 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 me, make sure it is not in the list of next values for any iterator in the...
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:38
int GNUNET_CONTAINER_multihashmap32_get_multiple(struct GNUNET_CONTAINER_MultiHashMap32 *map, uint32_t key, GNUNET_CONTAINER_MultiHashMapIterator32Callback 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.
enum GNUNET_GenericReturnValue(* GNUNET_CONTAINER_MultiHashMapIterator32Callback)(void *cls, uint32_t key, void *value)
Iterator over hash map entries.
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.
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_multihashmap32_iterate(struct GNUNET_CONTAINER_MultiHashMap32 *map, GNUNET_CONTAINER_MultiHashMapIterator32Callback it, void *it_cls)
Iterate over all entries in the map.
@ 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
@ GNUNET_YES
@ GNUNET_NO
@ GNUNET_SYSERR
#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.