^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1) /* SPDX-License-Identifier: (LGPL-2.1 OR BSD-2-Clause) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 2)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 3) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 4) * Generic non-thread safe hash map implementation.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 5) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 6) * Copyright (c) 2019 Facebook
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 7) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 8) #ifndef __LIBBPF_HASHMAP_H
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 9) #define __LIBBPF_HASHMAP_H
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 10)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 11) #include <stdbool.h>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 12) #include <stddef.h>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 13) #include <limits.h>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 14)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 15) static inline size_t hash_bits(size_t h, int bits)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 16) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 17) /* shuffle bits and return requested number of upper bits */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 18) if (bits == 0)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 19) return 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 20)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 21) #if (__SIZEOF_SIZE_T__ == __SIZEOF_LONG_LONG__)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 22) /* LP64 case */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 23) return (h * 11400714819323198485llu) >> (__SIZEOF_LONG_LONG__ * 8 - bits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 24) #elif (__SIZEOF_SIZE_T__ <= __SIZEOF_LONG__)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 25) return (h * 2654435769lu) >> (__SIZEOF_LONG__ * 8 - bits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 26) #else
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 27) # error "Unsupported size_t size"
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 28) #endif
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 29) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 30)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 31) /* generic C-string hashing function */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 32) static inline size_t str_hash(const char *s)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 33) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 34) size_t h = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 35)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 36) while (*s) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 37) h = h * 31 + *s;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 38) s++;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 39) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 40) return h;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 41) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 42)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 43) typedef size_t (*hashmap_hash_fn)(const void *key, void *ctx);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 44) typedef bool (*hashmap_equal_fn)(const void *key1, const void *key2, void *ctx);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 45)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 46) struct hashmap_entry {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 47) const void *key;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 48) void *value;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 49) struct hashmap_entry *next;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 50) };
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 51)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 52) struct hashmap {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 53) hashmap_hash_fn hash_fn;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 54) hashmap_equal_fn equal_fn;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 55) void *ctx;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 56)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 57) struct hashmap_entry **buckets;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 58) size_t cap;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 59) size_t cap_bits;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 60) size_t sz;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 61) };
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 62)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 63) #define HASHMAP_INIT(hash_fn, equal_fn, ctx) { \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 64) .hash_fn = (hash_fn), \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 65) .equal_fn = (equal_fn), \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 66) .ctx = (ctx), \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 67) .buckets = NULL, \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 68) .cap = 0, \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 69) .cap_bits = 0, \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 70) .sz = 0, \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 71) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 72)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 73) void hashmap__init(struct hashmap *map, hashmap_hash_fn hash_fn,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 74) hashmap_equal_fn equal_fn, void *ctx);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 75) struct hashmap *hashmap__new(hashmap_hash_fn hash_fn,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 76) hashmap_equal_fn equal_fn,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 77) void *ctx);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 78) void hashmap__clear(struct hashmap *map);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 79) void hashmap__free(struct hashmap *map);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 80)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 81) size_t hashmap__size(const struct hashmap *map);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 82) size_t hashmap__capacity(const struct hashmap *map);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 83)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 84) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 85) * Hashmap insertion strategy:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 86) * - HASHMAP_ADD - only add key/value if key doesn't exist yet;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 87) * - HASHMAP_SET - add key/value pair if key doesn't exist yet; otherwise,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 88) * update value;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 89) * - HASHMAP_UPDATE - update value, if key already exists; otherwise, do
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 90) * nothing and return -ENOENT;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 91) * - HASHMAP_APPEND - always add key/value pair, even if key already exists.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 92) * This turns hashmap into a multimap by allowing multiple values to be
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 93) * associated with the same key. Most useful read API for such hashmap is
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 94) * hashmap__for_each_key_entry() iteration. If hashmap__find() is still
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 95) * used, it will return last inserted key/value entry (first in a bucket
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 96) * chain).
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 97) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 98) enum hashmap_insert_strategy {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 99) HASHMAP_ADD,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 100) HASHMAP_SET,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 101) HASHMAP_UPDATE,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 102) HASHMAP_APPEND,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 103) };
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 104)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 105) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 106) * hashmap__insert() adds key/value entry w/ various semantics, depending on
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 107) * provided strategy value. If a given key/value pair replaced already
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 108) * existing key/value pair, both old key and old value will be returned
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 109) * through old_key and old_value to allow calling code do proper memory
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 110) * management.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 111) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 112) int hashmap__insert(struct hashmap *map, const void *key, void *value,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 113) enum hashmap_insert_strategy strategy,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 114) const void **old_key, void **old_value);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 115)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 116) static inline int hashmap__add(struct hashmap *map,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 117) const void *key, void *value)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 118) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 119) return hashmap__insert(map, key, value, HASHMAP_ADD, NULL, NULL);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 120) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 121)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 122) static inline int hashmap__set(struct hashmap *map,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 123) const void *key, void *value,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 124) const void **old_key, void **old_value)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 125) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 126) return hashmap__insert(map, key, value, HASHMAP_SET,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 127) old_key, old_value);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 128) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 129)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 130) static inline int hashmap__update(struct hashmap *map,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 131) const void *key, void *value,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 132) const void **old_key, void **old_value)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 133) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 134) return hashmap__insert(map, key, value, HASHMAP_UPDATE,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 135) old_key, old_value);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 136) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 137)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 138) static inline int hashmap__append(struct hashmap *map,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 139) const void *key, void *value)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 140) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 141) return hashmap__insert(map, key, value, HASHMAP_APPEND, NULL, NULL);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 142) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 143)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 144) bool hashmap__delete(struct hashmap *map, const void *key,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 145) const void **old_key, void **old_value);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 146)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 147) bool hashmap__find(const struct hashmap *map, const void *key, void **value);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 148)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 149) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 150) * hashmap__for_each_entry - iterate over all entries in hashmap
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 151) * @map: hashmap to iterate
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 152) * @cur: struct hashmap_entry * used as a loop cursor
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 153) * @bkt: integer used as a bucket loop cursor
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 154) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 155) #define hashmap__for_each_entry(map, cur, bkt) \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 156) for (bkt = 0; bkt < map->cap; bkt++) \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 157) for (cur = map->buckets[bkt]; cur; cur = cur->next)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 158)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 159) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 160) * hashmap__for_each_entry_safe - iterate over all entries in hashmap, safe
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 161) * against removals
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 162) * @map: hashmap to iterate
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 163) * @cur: struct hashmap_entry * used as a loop cursor
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 164) * @tmp: struct hashmap_entry * used as a temporary next cursor storage
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 165) * @bkt: integer used as a bucket loop cursor
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 166) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 167) #define hashmap__for_each_entry_safe(map, cur, tmp, bkt) \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 168) for (bkt = 0; bkt < map->cap; bkt++) \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 169) for (cur = map->buckets[bkt]; \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 170) cur && ({tmp = cur->next; true; }); \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 171) cur = tmp)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 172)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 173) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 174) * hashmap__for_each_key_entry - iterate over entries associated with given key
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 175) * @map: hashmap to iterate
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 176) * @cur: struct hashmap_entry * used as a loop cursor
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 177) * @key: key to iterate entries for
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 178) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 179) #define hashmap__for_each_key_entry(map, cur, _key) \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 180) for (cur = map->buckets \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 181) ? map->buckets[hash_bits(map->hash_fn((_key), map->ctx), map->cap_bits)] \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 182) : NULL; \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 183) cur; \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 184) cur = cur->next) \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 185) if (map->equal_fn(cur->key, (_key), map->ctx))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 186)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 187) #define hashmap__for_each_key_entry_safe(map, cur, tmp, _key) \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 188) for (cur = map->buckets \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 189) ? map->buckets[hash_bits(map->hash_fn((_key), map->ctx), map->cap_bits)] \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 190) : NULL; \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 191) cur && ({ tmp = cur->next; true; }); \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 192) cur = tmp) \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 193) if (map->equal_fn(cur->key, (_key), map->ctx))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 194)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 195) #endif /* __LIBBPF_HASHMAP_H */
Orange Pi5 kernel
Deprecated Linux kernel 5.10.110 for OrangePi 5/5B/5+ boards
3 Commits
0 Branches
0 Tags