lib/bpf/hashmap.h

0001 /* SPDX-License-Identifier: (LGPL-2.1 OR BSD-2-Clause) */
0002
0003 /*
0004  * Generic non-thread safe hash map implementation.
0005  *
0006  * Copyright (c) 2019 Facebook
0007  */
0008 #ifndef __LIBBPF_HASHMAP_H
0009 #define __LIBBPF_HASHMAP_H
0010
0011 #include <stdbool.h>
0012 #include <stddef.h>
0013 #include <limits.h>
0014
0015 static inline size_t hash_bits(size_t h, int bits)
0016 {
0017     /* shuffle bits and return requested number of upper bits */
0018     if (bits == 0)
0019         return 0;
0020
0021 #if (__SIZEOF_SIZE_T__ == __SIZEOF_LONG_LONG__)
0022     /* LP64 case */
0023     return (h * 11400714819323198485llu) >> (__SIZEOF_LONG_LONG__ * 8 - bits);
0024 #elif (__SIZEOF_SIZE_T__ <= __SIZEOF_LONG__)
0025     return (h * 2654435769lu) >> (__SIZEOF_LONG__ * 8 - bits);
0026 #else
0027 #   error "Unsupported size_t size"
0028 #endif
0029 }
0030
0031 /* generic C-string hashing function */
0032 static inline size_t str_hash(const char *s)
0033 {
0034     size_t h = 0;
0035
0036     while (*s) {
0037         h = h * 31 + *s;
0038         s++;
0039     }
0040     return h;
0041 }
0042
0043 typedef size_t (*hashmap_hash_fn)(const void *key, void *ctx);
0044 typedef bool (*hashmap_equal_fn)(const void *key1, const void *key2, void *ctx);
0045
0046 struct hashmap_entry {
0047     const void *key;
0048     void *value;
0049     struct hashmap_entry *next;
0050 };
0051
0052 struct hashmap {
0053     hashmap_hash_fn hash_fn;
0054     hashmap_equal_fn equal_fn;
0055     void *ctx;
0056
0057     struct hashmap_entry **buckets;
0058     size_t cap;
0059     size_t cap_bits;
0060     size_t sz;
0061 };
0062
0063 #define HASHMAP_INIT(hash_fn, equal_fn, ctx) {  \
0064     .hash_fn = (hash_fn),           \
0065     .equal_fn = (equal_fn),         \
0066     .ctx = (ctx),               \
0067     .buckets = NULL,            \
0068     .cap = 0,               \
0069     .cap_bits = 0,              \
0070     .sz = 0,                \
0071 }
0072
0073 void hashmap__init(struct hashmap *map, hashmap_hash_fn hash_fn,
0074            hashmap_equal_fn equal_fn, void *ctx);
0075 struct hashmap *hashmap__new(hashmap_hash_fn hash_fn,
0076                  hashmap_equal_fn equal_fn,
0077                  void *ctx);
0078 void hashmap__clear(struct hashmap *map);
0079 void hashmap__free(struct hashmap *map);
0080
0081 size_t hashmap__size(const struct hashmap *map);
0082 size_t hashmap__capacity(const struct hashmap *map);
0083
0084 /*
0085  * Hashmap insertion strategy:
0086  * - HASHMAP_ADD - only add key/value if key doesn't exist yet;
0087  * - HASHMAP_SET - add key/value pair if key doesn't exist yet; otherwise,
0088  *   update value;
0089  * - HASHMAP_UPDATE - update value, if key already exists; otherwise, do
0090  *   nothing and return -ENOENT;
0091  * - HASHMAP_APPEND - always add key/value pair, even if key already exists.
0092  *   This turns hashmap into a multimap by allowing multiple values to be
0093  *   associated with the same key. Most useful read API for such hashmap is
0094  *   hashmap__for_each_key_entry() iteration. If hashmap__find() is still
0095  *   used, it will return last inserted key/value entry (first in a bucket
0096  *   chain).
0097  */
0098 enum hashmap_insert_strategy {
0099     HASHMAP_ADD,
0100     HASHMAP_SET,
0101     HASHMAP_UPDATE,
0102     HASHMAP_APPEND,
0103 };
0104
0105 /*
0106  * hashmap__insert() adds key/value entry w/ various semantics, depending on
0107  * provided strategy value. If a given key/value pair replaced already
0108  * existing key/value pair, both old key and old value will be returned
0109  * through old_key and old_value to allow calling code do proper memory
0110  * management.
0111  */
0112 int hashmap__insert(struct hashmap *map, const void *key, void *value,
0113             enum hashmap_insert_strategy strategy,
0114             const void **old_key, void **old_value);
0115
0116 static inline int hashmap__add(struct hashmap *map,
0117                    const void *key, void *value)
0118 {
0119     return hashmap__insert(map, key, value, HASHMAP_ADD, NULL, NULL);
0120 }
0121
0122 static inline int hashmap__set(struct hashmap *map,
0123                    const void *key, void *value,
0124                    const void **old_key, void **old_value)
0125 {
0126     return hashmap__insert(map, key, value, HASHMAP_SET,
0127                    old_key, old_value);
0128 }
0129
0130 static inline int hashmap__update(struct hashmap *map,
0131                   const void *key, void *value,
0132                   const void **old_key, void **old_value)
0133 {
0134     return hashmap__insert(map, key, value, HASHMAP_UPDATE,
0135                    old_key, old_value);
0136 }
0137
0138 static inline int hashmap__append(struct hashmap *map,
0139                   const void *key, void *value)
0140 {
0141     return hashmap__insert(map, key, value, HASHMAP_APPEND, NULL, NULL);
0142 }
0143
0144 bool hashmap__delete(struct hashmap *map, const void *key,
0145              const void **old_key, void **old_value);
0146
0147 bool hashmap__find(const struct hashmap *map, const void *key, void **value);
0148
0149 /*
0150  * hashmap__for_each_entry - iterate over all entries in hashmap
0151  * @map: hashmap to iterate
0152  * @cur: struct hashmap_entry * used as a loop cursor
0153  * @bkt: integer used as a bucket loop cursor
0154  */
0155 #define hashmap__for_each_entry(map, cur, bkt)                  \
0156     for (bkt = 0; bkt < map->cap; bkt++)                    \
0157         for (cur = map->buckets[bkt]; cur; cur = cur->next)
0158
0159 /*
0160  * hashmap__for_each_entry_safe - iterate over all entries in hashmap, safe
0161  * against removals
0162  * @map: hashmap to iterate
0163  * @cur: struct hashmap_entry * used as a loop cursor
0164  * @tmp: struct hashmap_entry * used as a temporary next cursor storage
0165  * @bkt: integer used as a bucket loop cursor
0166  */
0167 #define hashmap__for_each_entry_safe(map, cur, tmp, bkt)            \
0168     for (bkt = 0; bkt < map->cap; bkt++)                    \
0169         for (cur = map->buckets[bkt];                   \
0170              cur && ({tmp = cur->next; true; });            \
0171              cur = tmp)
0172
0173 /*
0174  * hashmap__for_each_key_entry - iterate over entries associated with given key
0175  * @map: hashmap to iterate
0176  * @cur: struct hashmap_entry * used as a loop cursor
0177  * @key: key to iterate entries for
0178  */
0179 #define hashmap__for_each_key_entry(map, cur, _key)             \
0180     for (cur = map->buckets                         \
0181              ? map->buckets[hash_bits(map->hash_fn((_key), map->ctx), map->cap_bits)] \
0182              : NULL;                            \
0183          cur;                               \
0184          cur = cur->next)                           \
0185         if (map->equal_fn(cur->key, (_key), map->ctx))
0186
0187 #define hashmap__for_each_key_entry_safe(map, cur, tmp, _key)           \
0188     for (cur = map->buckets                         \
0189              ? map->buckets[hash_bits(map->hash_fn((_key), map->ctx), map->cap_bits)] \
0190              : NULL;                            \
0191          cur && ({ tmp = cur->next; true; });               \
0192          cur = tmp)                             \
0193         if (map->equal_fn(cur->key, (_key), map->ctx))
0194
0195 #endif /* __LIBBPF_HASHMAP_H */