hash map for fixed-size keys where the same key may be present multiple times; the implementation behind all the maps in gnunet_hashmap_lib.h More...
Go to the source code of this file.
Data Structures | |
| struct | MapEntry |
| An entry in a map. More... | |
| struct | GNUNET_CONTAINER_MultiMap |
| Internal representation of a map. More... | |
| struct | GNUNET_CONTAINER_MultiMapIterator |
| Cursor into a map. More... | |
Macros | |
| #define | LOG(kind, ...) GNUNET_log_from (kind, "util-container-multimap", __VA_ARGS__) |
| #define | NEXT_CACHE_SIZE 16 |
| Maximum recursion depth for callbacks of GNUNET_CONTAINER_multimap_get_multiple_() themselves again calling GNUNET_CONTAINER_multimap_get_multiple_(). | |
| #define | MIN_MAP_LENGTH 2 |
| Smallest number of buckets of a map. | |
| #define | MAX_MAP_LENGTH (1U << 31) |
| Largest number of buckets of a map (a power of two). | |
| #define | FIBONACCI_MULTIPLIER UINT64_C (0x9E3779B97F4A7C15) |
| 2^64 divided by the golden ratio, rounded to an odd number; the multiplier for Fibonacci hashing, which unprotected maps use. | |
| #define | KEY_SHIFT(n) (64 - 8 * (n)) |
| How far to shift a key of n bytes, loaded as an integer, to put it into the first n bytes (in memory) of a 64-bit word. | |
| #define | KEY_WORDS(n) (((n) + sizeof (uint64_t) - 1) / sizeof (uint64_t)) |
| Number of 64-bit words needed to hold a key of n bytes. | |
Enumerations | |
| enum | KeyStorage { KS_INLINE_VALUE , KS_INLINE_COPY , KS_BORROWED } |
| How the keys of a map are stored. More... | |
Functions | |
| GNUNET_static_assert (0==offsetof(struct MapEntry, key_copy) % 8) | |
| Copied keys must be aligned at least as well as the keys that applications use (see GNUNET_CONTAINER_MULTIMAP_DEFINE_PTRKEY). | |
| static uint64_t | rotl64 (uint64_t x, unsigned int b) |
| Rotate a 64-bit word left. | |
| static void | sip_round (uint64_t v[4]) |
| One SipRound. | |
| 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 use, as it is still a strong pseudo-random function for that purpose. | |
| 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 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 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. | |
| static const void * | entry_key (const struct GNUNET_CONTAINER_MultiMap *map, const struct MapEntry *e) |
| Get where the key of an entry is. | |
| 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 struct MapEntry ** | allocate_buckets (unsigned int len) |
| Allocate a bucket array. | |
| struct GNUNET_CONTAINER_MultiMap * | GNUNET_CONTAINER_multimap_create_ (unsigned int len, size_t key_size, enum GNUNET_CONTAINER_MultiMapFlags flags) |
| Create a map. | |
| static void | free_entries (struct GNUNET_CONTAINER_MultiMap *map) |
| Free all entries of a map, leaving its buckets empty. | |
| void | GNUNET_CONTAINER_multimap_destroy_ (struct GNUNET_CONTAINER_MultiMap *map) |
| Destroy 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_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_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. | |
| 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. | |
| 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's next_cache. | |
| 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. | |
| int | GNUNET_CONTAINER_multimap_remove_all_ (struct GNUNET_CONTAINER_MultiMap *map, const void *key) |
| Remove all values stored under a key from a map. | |
| unsigned int | GNUNET_CONTAINER_multimap_clear_ (struct GNUNET_CONTAINER_MultiMap *map) |
| Remove all key-value pairs from a map. | |
| static void | grow (struct GNUNET_CONTAINER_MultiMap *map) |
| Grow the given map to a more appropriate size. | |
| 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. | |
| 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. | |
| struct GNUNET_CONTAINER_MultiMapIterator * | GNUNET_CONTAINER_multimap_iterator_create_ (const struct GNUNET_CONTAINER_MultiMap *map) |
| Create an iterator over a map. | |
| 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. | |
| void | GNUNET_CONTAINER_multimap_iterator_destroy_ (struct GNUNET_CONTAINER_MultiMapIterator *iter) |
| Destroy an iterator. | |
hash map for fixed-size keys where the same key may be present multiple times; the implementation behind all the maps in gnunet_hashmap_lib.h
Definition in file container_multimap.c.
| #define LOG | ( | kind, | |
| ... | |||
| ) | GNUNET_log_from (kind, "util-container-multimap", __VA_ARGS__) |
Definition at line 31 of file container_multimap.c.
| #define NEXT_CACHE_SIZE 16 |
Maximum recursion depth for callbacks of GNUNET_CONTAINER_multimap_get_multiple_() themselves again calling GNUNET_CONTAINER_multimap_get_multiple_().
Should be totally excessive, but if violated we die.
Definition at line 40 of file container_multimap.c.
| #define MIN_MAP_LENGTH 2 |
Smallest number of buckets of a map.
Must be a power of two, and at least two so that the shift for Fibonacci hashing stays below 64.
Definition at line 46 of file container_multimap.c.
| #define MAX_MAP_LENGTH (1U << 31) |
Largest number of buckets of a map (a power of two).
Definition at line 51 of file container_multimap.c.
| #define FIBONACCI_MULTIPLIER UINT64_C (0x9E3779B97F4A7C15) |
2^64 divided by the golden ratio, rounded to an odd number; the multiplier for Fibonacci hashing, which unprotected maps use.
Definition at line 57 of file container_multimap.c.
| #define KEY_SHIFT | ( | n | ) | (64 - 8 * (n)) |
How far to shift a key of n bytes, loaded as an integer, to put it into the first n bytes (in memory) of a 64-bit word.
Definition at line 64 of file container_multimap.c.
| #define KEY_WORDS | ( | n | ) | (((n) + sizeof (uint64_t) - 1) / sizeof (uint64_t)) |
Number of 64-bit words needed to hold a key of n bytes.
Definition at line 72 of file container_multimap.c.
| enum KeyStorage |
How the keys of a map are stored.
Fixed when the map is created.
Definition at line 78 of file container_multimap.c.
| GNUNET_static_assert | ( | 0 | = =offsetof(struct MapEntry, key_copy) % 8 | ) |
Copied keys must be aligned at least as well as the keys that applications use (see GNUNET_CONTAINER_MULTIMAP_DEFINE_PTRKEY).
|
inlinestatic |
Rotate a 64-bit word left.
| x | the word |
| b | number of bits to rotate by, 1 to 63 |
Definition at line 262 of file container_multimap.c.
Referenced by sip_round().
|
inlinestatic |
One SipRound.
| [in,out] | v | the SipHash state |
Definition at line 275 of file container_multimap.c.
References rotl64().
Referenced by siphash13().
|
inlinestatic |
SipHash-1-3 (one compression and three finalization rounds), the variant hash tables such as Rust's use, as it is still a strong pseudo-random function for that purpose.
| key | the 128-bit key |
| data | what to hash |
| len | number of bytes in data |
Definition at line 305 of file container_multimap.c.
References data, end, GNUNET_le64toh, key, m, and sip_round().
Referenced by bucket_of().
|
inlinestatic |
Convert a key of at most 8 bytes to the form it is stored in.
| map | the map, which must use KS_INLINE_VALUE |
| key | the key |
Definition at line 352 of file container_multimap.c.
References key, KEY_SHIFT, and map.
Referenced by lookup_word().
|
inlinestatic |
Prepare a key for looking it up in a map.
| map | the map |
| key | the key |
Definition at line 399 of file container_multimap.c.
References key, key_to_word(), KS_INLINE_VALUE, and map.
Referenced by GNUNET_CONTAINER_multimap_contains_(), GNUNET_CONTAINER_multimap_contains_value_(), GNUNET_CONTAINER_multimap_get_(), GNUNET_CONTAINER_multimap_get_multiple_(), GNUNET_CONTAINER_multimap_put_(), GNUNET_CONTAINER_multimap_remove_(), and GNUNET_CONTAINER_multimap_remove_all_().
|
inlinestatic |
Compute the bucket for a key.
| map | the map |
| key | the key |
| kw | the result of lookup_word() for key |
Definition at line 418 of file container_multimap.c.
References FIBONACCI_MULTIPLIER, key, KS_INLINE_VALUE, map, and siphash13().
Referenced by GNUNET_CONTAINER_multimap_contains_(), GNUNET_CONTAINER_multimap_contains_value_(), GNUNET_CONTAINER_multimap_get_(), GNUNET_CONTAINER_multimap_get_multiple_(), GNUNET_CONTAINER_multimap_put_(), GNUNET_CONTAINER_multimap_remove_(), GNUNET_CONTAINER_multimap_remove_all_(), and grow().
|
inlinestatic |
Check if an entry has a key.
| map | the map |
| e | the entry |
| key | the key to compare to |
| kw | the result of lookup_word() for key |
Definition at line 452 of file container_multimap.c.
References MapEntry::k, key, KS_INLINE_VALUE, map, MapEntry::ptr, and MapEntry::u64.
Referenced by GNUNET_CONTAINER_multimap_contains_(), GNUNET_CONTAINER_multimap_contains_value_(), GNUNET_CONTAINER_multimap_get_(), GNUNET_CONTAINER_multimap_get_multiple_(), GNUNET_CONTAINER_multimap_put_(), GNUNET_CONTAINER_multimap_remove_(), and GNUNET_CONTAINER_multimap_remove_all_().
|
inlinestatic |
Get where the key of an entry is.
| map | the map |
| e | the entry |
Definition at line 483 of file container_multimap.c.
References MapEntry::bytes, MapEntry::k, KS_INLINE_VALUE, map, and MapEntry::ptr.
Referenced by callback_key(), GNUNET_CONTAINER_multimap_iterator_next_(), and grow().
|
inlinestatic |
Get the key of an entry to give to a callback.
Copied and inline keys are copied to buf, so that the callback may free the entry (and then still use the key, for example to remove more entries).
| map | the map | |
| e | the entry | |
| [out] | buf | at least KEY_WORDS (key_size) words |
Definition at line 503 of file container_multimap.c.
References entry_key(), MapEntry::k, KS_BORROWED, map, and MapEntry::ptr.
Referenced by GNUNET_CONTAINER_multimap_iterate_().
|
static |
Allocate a bucket array.
| len | number of buckets |
Definition at line 523 of file container_multimap.c.
References GNUNET_malloc_large, GNUNET_MAX_MALLOC_CHECKED, and GNUNET_new_array.
Referenced by GNUNET_CONTAINER_multimap_create_(), and grow().
|
static |
Free all entries of a map, leaving its buckets empty.
| map | the map |
Definition at line 592 of file container_multimap.c.
References GNUNET_free, map, and MapEntry::next.
Referenced by GNUNET_CONTAINER_multimap_clear_(), and GNUNET_CONTAINER_multimap_destroy_().
|
static |
We are about to free() e, make sure it is not in the list of next values for any iteration in the map's next_cache.
| map | the map to check |
| e | the entry that is about to be free'd |
Definition at line 721 of file container_multimap.c.
References map, and MapEntry::next.
Referenced by GNUNET_CONTAINER_multimap_remove_(), and GNUNET_CONTAINER_multimap_remove_all_().
|
static |
Grow the given map to a more appropriate size.
| map | the hash map to grow |
Definition at line 809 of file container_multimap.c.
References allocate_buckets(), bucket_of(), entry_key(), GNUNET_free, MapEntry::k, KS_INLINE_VALUE, map, MAX_MAP_LENGTH, MapEntry::next, and MapEntry::u64.
Referenced by GNUNET_CONTAINER_multimap_put_().