GNUnet 0.21.0
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
47struct 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
90
97
102 unsigned int next_cache_off;
103};
104
105
111{
115 struct MapEntry *me;
116
120 unsigned int idx;
121
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 {
152 return NULL;
153 }
154 ret->map_length = len;
155 return ret;
156}
157
158
165void
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 }
181}
182
183
191static unsigned int
192idx_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
199unsigned int
202{
203 return map->size;
204}
205
206
207void *
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
225int
229 void *it_cls)
230{
231 int count;
232 struct MapEntry **ce;
233
234 count = 0;
235 GNUNET_assert (NULL != map);
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
269static 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
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
314int
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
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
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
399static 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
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
490int
493 uint32_t key,
495 void *it_cls)
496{
497 int count;
498 struct MapEntry *e;
499 struct MapEntry **ce;
500
501 count = 0;
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
538{
540
542 iter->map = map;
544 iter->me = map->map[0];
545 return iter;
546}
547
548
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
598void
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 struct GNUNET_ARM_MonitorHandle * m
Monitor connection with ARM.
Definition: gnunet-arm.c:104
static int ret
Final status code.
Definition: gnunet-arm.c:94
static GNUNET_NETWORK_STRUCT_END struct GNUNET_PeerIdentity me
Our own peer identity.
struct GNUNET_HashCode key
The key used in the DHT.
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.
enum GNUNET_GenericReturnValue 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.
enum GNUNET_GenericReturnValue 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).
struct GNUNET_CONTAINER_MultiHashMap32 * GNUNET_CONTAINER_multihashmap32_create(unsigned int len)
Create a multi hash map.
enum GNUNET_GenericReturnValue 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.
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.
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.
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_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...
struct GNUNET_CONTAINER_MultiHashMap32Iterator * GNUNET_CONTAINER_multihashmap32_iterator_create(const struct GNUNET_CONTAINER_MultiHashMap32 *map)
Create an iterator for a multihashmap.
enum GNUNET_GenericReturnValue 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.
GNUNET_GenericReturnValue
Named constants for return values.
@ 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.
static struct GNUNET_CONTAINER_MultiPeerMap * map
Peermap of PeerIdentities to "struct PeerEntry" (for fast lookup).
Definition: peer.c:63
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.