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