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