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