31#define LOG(kind, ...) \
32 GNUNET_log_from (kind, "util-container-multimap", __VA_ARGS__)
40#define NEXT_CACHE_SIZE 16
46#define MIN_MAP_LENGTH 2
51#define MAX_MAP_LENGTH (1U << 31)
57#define FIBONACCI_MULTIPLIER UINT64_C (0x9E3779B97F4A7C15)
63#if __BYTE_ORDER == __BIG_ENDIAN
64#define KEY_SHIFT(n) (64 - 8 * (n))
72#define KEY_WORDS(n) (((n) + sizeof (uint64_t) - 1) / sizeof (uint64_t))
132 unsigned char bytes[
sizeof (uint64_t)];
261static inline uint64_t
265 return (x << b) | (x >> (64 - b));
304static inline uint64_t
309 const unsigned char *in =
data;
310 const unsigned char *
end = in + (len - len % 8);
312 key[0] ^ UINT64_C (0x736f6d6570736575),
313 key[1] ^ UINT64_C (0x646f72616e646f6d),
314 key[0] ^ UINT64_C (0x6c7967656e657261),
315 key[1] ^ UINT64_C (0x7465646279746573)
317 uint64_t b = ((uint64_t) len) << 56;
319 for (; in !=
end; in += 8)
331 for (
size_t i = 0; i < len % 8; i++)
332 b |= ((uint64_t) in[i]) << (8 * i);
340 return v[0] ^ v[1] ^ v[2] ^ v[3];
351static inline uint64_t
358 unsigned char bytes[
sizeof (uint64_t)];
364 switch (
map->key_size)
370 memcpy (&v,
key,
sizeof (v));
377 memcpy (&v,
key,
sizeof (v));
381 memcpy (&w.u64,
key, sizeof (w.u64));
385 memcpy (w.bytes,
key,
map->key_size);
398static inline uint64_t
417static inline unsigned int
422 if (
map->unprotected)
435 sizeof (kw)) & (
map->map_length - 1);
438 map->key_size) & (
map->map_length - 1);
458 return kw == e->
k.
u64;
461 switch (
map->key_size)
464 return 0 == memcmp (
key, e->
k.
ptr, 16);
466 return 0 == memcmp (
key, e->
k.
ptr, 32);
468 return 0 == memcmp (
key, e->
k.
ptr, 64);
470 return 0 == memcmp (
key, e->
k.
ptr,
map->key_size);
482static inline const void *
502static inline const void *
527 s = (size_t) len *
sizeof (
struct MapEntry *);
528 if (s /
sizeof (
struct MapEntry *) != len)
560 if (NULL ==
map->buckets)
563 "Out of memory allocating large hash map (%u entries)\n",
569 map->shift = 64 - bits;
572 map->unprotected =
true;
575 sizeof (
map->sip_key));
594 for (
unsigned int i = 0; i <
map->map_length; i++)
598 while (NULL != (e =
map->buckets[i]))
667 if ( (
value == e->value) &&
684 ce = &
map->next_cache[
map->next_cache_off];
687 for (
unsigned int i = 0; i <
map->map_length; i++)
691 *ce =
map->buckets[i];
692 while (NULL != (e = *ce))
724 for (
unsigned int i = 0; i <
map->next_cache_off; i++)
725 if (
map->next_cache[i] == e)
738 map->modification_counter++;
768 map->modification_counter++;
771 while (NULL != (e = *pp))
794 map->modification_counter++;
797 for (
unsigned int i = 0; i <
map->next_cache_off; i++)
798 map->next_cache[i] = NULL;
813 unsigned int old_len;
815 old_buckets =
map->buckets;
816 old_len =
map->map_length;
820 if (NULL == new_buckets)
822 map->modification_counter++;
823 map->map_length = old_len * 2;
825 map->buckets = new_buckets;
826 for (
unsigned int i = 0; i < old_len; i++)
830 while (NULL != (e = old_buckets[i]))
834 old_buckets[i] = e->
next;
838 e->
next = new_buckets[idx];
839 new_buckets[idx] = e;
860 for (e =
map->buckets[i]; NULL != e; e = e->
next)
870 if (
map->size / 3 >=
map->map_length / 4)
875 switch (
map->storage)
915 ce = &
map->next_cache[
map->next_cache_off];
919 while (NULL != (e = *ce))
948 iter->
me =
map->buckets[0];
967 if (iter->
idx >=
map->map_length)
969 if (NULL != iter->
me)
981 if (iter->
idx <
map->map_length)
#define NEXT_CACHE_SIZE
Maximum recursion depth for callbacks of GNUNET_CONTAINER_multimap_get_multiple_() themselves again c...
#define KEY_WORDS(n)
Number of 64-bit words needed to hold a key of n bytes.
#define MIN_MAP_LENGTH
Smallest number of buckets of a map.
static const void * entry_key(const struct GNUNET_CONTAINER_MultiMap *map, const struct MapEntry *e)
Get where the key of an entry is.
static uint64_t siphash13(const uint64_t key[2], const void *data, size_t len)
SipHash-1-3 (one compression and three finalization rounds), the variant hash tables such as Rust's u...
static uint64_t key_to_word(const struct GNUNET_CONTAINER_MultiMap *map, const void *key)
Convert a key of at most 8 bytes to the form it is stored in.
static void free_entries(struct GNUNET_CONTAINER_MultiMap *map)
Free all entries of a map, leaving its buckets empty.
#define MAX_MAP_LENGTH
Largest number of buckets of a map (a power of two).
KeyStorage
How the keys of a map are stored.
@ KS_INLINE_VALUE
The key has at most 8 bytes.
@ KS_BORROWED
The key is longer than 8 bytes and was not copied: k.ptr points to memory that the application keeps ...
@ KS_INLINE_COPY
The key is longer than 8 bytes and was copied: the entry was allocated with key_size extra bytes for ...
static struct MapEntry ** allocate_buckets(unsigned int len)
Allocate a bucket array.
static uint64_t rotl64(uint64_t x, unsigned int b)
Rotate a 64-bit word left.
#define KEY_SHIFT(n)
How far to shift a key of n bytes, loaded as an integer, to put it into the first n bytes (in memory)...
static const void * callback_key(const struct GNUNET_CONTAINER_MultiMap *map, const struct MapEntry *e, uint64_t *buf)
Get the key of an entry to give to a callback.
static bool keys_equal(const struct GNUNET_CONTAINER_MultiMap *map, const struct MapEntry *e, const void *key, uint64_t kw)
Check if an entry has a key.
#define FIBONACCI_MULTIPLIER
2^64 divided by the golden ratio, rounded to an odd number; the multiplier for Fibonacci hashing,...
static void update_next_cache(struct GNUNET_CONTAINER_MultiMap *map, const struct MapEntry *e)
We are about to free() e, make sure it is not in the list of next values for any iteration in the map...
static uint64_t lookup_word(const struct GNUNET_CONTAINER_MultiMap *map, const void *key)
Prepare a key for looking it up in a map.
static unsigned int bucket_of(const struct GNUNET_CONTAINER_MultiMap *map, const void *key, uint64_t kw)
Compute the bucket for a key.
static void grow(struct GNUNET_CONTAINER_MultiMap *map)
Grow the given map to a more appropriate size.
static void sip_round(uint64_t v[4])
One SipRound.
static struct GNUNET_ARM_MonitorHandle * m
Monitor connection with ARM.
static int ret
Final status code.
static int end
Set if we are to shutdown all services (including ARM).
static char * data
The data to insert into the dht.
struct GNUNET_HashCode key
The key used in the DHT.
static char * value
Value of the record to add/remove.
void GNUNET_CRYPTO_random_block(void *buffer, size_t length)
Fill block with a random values.
int GNUNET_CONTAINER_multimap_iterate_(struct GNUNET_CONTAINER_MultiMap *map, GNUNET_CONTAINER_MultiMapIteratorCallback it, void *it_cls)
Call a function on every key-value pair of a map.
unsigned int GNUNET_CONTAINER_multimap_clear_(struct GNUNET_CONTAINER_MultiMap *map)
Remove all key-value pairs from a map.
struct GNUNET_CONTAINER_MultiMapIterator * GNUNET_CONTAINER_multimap_iterator_create_(const struct GNUNET_CONTAINER_MultiMap *map)
Create an iterator over a map.
void GNUNET_CONTAINER_multimap_iterator_destroy_(struct GNUNET_CONTAINER_MultiMapIterator *iter)
Destroy an iterator.
enum GNUNET_GenericReturnValue GNUNET_CONTAINER_multimap_contains_(const struct GNUNET_CONTAINER_MultiMap *map, const void *key)
Check if the map has any value stored under a key.
enum GNUNET_GenericReturnValue(* GNUNET_CONTAINER_MultiMapIteratorCallback)(void *cls, const void *key, void *value)
Iterator over the entries of a map with untyped keys and values.
GNUNET_CONTAINER_MultiHashMapOption
Options for storing values in the HashMap.
enum GNUNET_GenericReturnValue GNUNET_CONTAINER_multimap_remove_(struct GNUNET_CONTAINER_MultiMap *map, const void *key, const void *value)
Remove a key-value pair from a map.
void GNUNET_CONTAINER_multimap_destroy_(struct GNUNET_CONTAINER_MultiMap *map)
Destroy a map.
#define GNUNET_CONTAINER_MULTIMAP_MAX_KEY_SIZE
Largest key size (in bytes) a map supports.
enum GNUNET_GenericReturnValue GNUNET_CONTAINER_multimap_put_(struct GNUNET_CONTAINER_MultiMap *map, const void *key, void *value, enum GNUNET_CONTAINER_MultiHashMapOption opt)
Store a key-value pair in a map.
unsigned int GNUNET_CONTAINER_multimap_size_(const struct GNUNET_CONTAINER_MultiMap *map)
Get the number of key-value pairs in a map.
void * GNUNET_CONTAINER_multimap_get_(const struct GNUNET_CONTAINER_MultiMap *map, const void *key)
Get a value stored under a key.
enum GNUNET_GenericReturnValue GNUNET_CONTAINER_multimap_iterator_next_(struct GNUNET_CONTAINER_MultiMapIterator *iter, void *key, const void **value)
Get the next key-value pair from an iterator.
struct GNUNET_CONTAINER_MultiMap * GNUNET_CONTAINER_multimap_create_(unsigned int len, size_t key_size, enum GNUNET_CONTAINER_MultiMapFlags flags)
Create a map.
int GNUNET_CONTAINER_multimap_remove_all_(struct GNUNET_CONTAINER_MultiMap *map, const void *key)
Remove all values stored under a key from a map.
int GNUNET_CONTAINER_multimap_get_multiple_(struct GNUNET_CONTAINER_MultiMap *map, const void *key, GNUNET_CONTAINER_MultiMapIteratorCallback it, void *it_cls)
Call a function on every value stored under a key.
GNUNET_CONTAINER_MultiMapFlags
Flags for GNUNET_CONTAINER_multimap_create_().
enum GNUNET_GenericReturnValue GNUNET_CONTAINER_multimap_contains_value_(const struct GNUNET_CONTAINER_MultiMap *map, const void *key, const void *value)
Check if the map has a particular key-value pair.
@ 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...
@ GNUNET_CONTAINER_MULTIMAP_FLAG_UNPROTECTED
Do not protect the map against hash flooding.
@ GNUNET_CONTAINER_MULTIMAP_FLAG_DO_NOT_COPY_KEYS
Do not copy keys longer than 8 bytes into the map, only keep a pointer to them.
#define GNUNET_le64toh(x)
GNUNET_GenericReturnValue
Named constants for return values.
#define GNUNET_static_assert(cond)
#define GNUNET_assert(cond)
Use this for fatal errors that cannot be handled.
@ GNUNET_ERROR_TYPE_WARNING
#define GNUNET_MAX_MALLOC_CHECKED
Maximum allocation with GNUNET_malloc macro.
#define GNUNET_malloc_large(size)
Wrapper around malloc.
#define GNUNET_new(type)
Allocate a struct or union of the given type.
#define GNUNET_malloc(size)
Wrapper around malloc.
#define GNUNET_new_array(n, type)
Allocate a size n array with structs or unions 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).
unsigned int idx
Current bucket index.
const struct GNUNET_CONTAINER_MultiMap * map
Map that we are iterating over.
struct MapEntry * me
Position in the bucket idx.
unsigned int modification_counter
Modification counter as observed on the map when the iterator was created.
Internal representation of a map.
uint64_t sip_key[2]
Random SipHash key of this map, unless it is unprotected.
enum KeyStorage storage
How keys are stored.
struct MapEntry ** buckets
All of our buckets, map_length many.
struct MapEntry * next_cache[16]
Map entries indicating iteration positions currently in use by GNUNET_CONTAINER_multimap_iterate_() a...
bool unprotected
True if the map was created with GNUNET_CONTAINER_MULTIMAP_FLAG_UNPROTECTED: buckets are then chosen ...
size_t key_size
Size of the keys in bytes.
unsigned int size
Number of entries in the map.
unsigned int modification_counter
Counts the destructive modifications (grow, remove) to the map, so that iterators can check if they a...
unsigned int map_length
Length of the buckets array, always a power of two.
unsigned int next_cache_off
Offset of next_cache entries in use, must be smaller than NEXT_CACHE_SIZE.
unsigned int shift
64 minus the binary logarithm of map_length, for Fibonacci hashing.
const void * ptr
KS_INLINE_COPY and KS_BORROWED: the key_size bytes of the key.
unsigned char key_copy[]
KS_INLINE_COPY only: the key; allocated with the entry.
union MapEntry::@43 k
The key itself (KS_INLINE_VALUE), or where to find it (the other kinds of storage).
void * value
The application's value.
uint64_t u64
KS_INLINE_VALUE: the key, zero-extended, for comparing.
struct MapEntry * next
Next entry in the same bucket.
unsigned char bytes[sizeof(uint64_t)]
KS_INLINE_VALUE: the key, as the first key_size bytes.