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 #include <stdint.h> 9 #include <stdlib.h> 10 #include <stdio.h> 11 #include <errno.h> 12 #include <linux/err.h> 13 #include "hashmap.h" 14 15 /* make sure libbpf doesn't use kernel-only integer typedefs */ 16 #pragma GCC poison u8 u16 u32 u64 s8 s16 s32 s64 17 18 /* prevent accidental re-addition of reallocarray() */ 19 #pragma GCC poison reallocarray 20 21 /* start with 4 buckets */ 22 #define HASHMAP_MIN_CAP_BITS 2 23 24 static void hashmap_add_entry(struct hashmap_entry **pprev, 25 struct hashmap_entry *entry) 26 { 27 entry->next = *pprev; 28 *pprev = entry; 29 } 30 31 static void hashmap_del_entry(struct hashmap_entry **pprev, 32 struct hashmap_entry *entry) 33 { 34 *pprev = entry->next; 35 entry->next = NULL; 36 } 37 38 void hashmap__init(struct hashmap *map, hashmap_hash_fn hash_fn, 39 hashmap_equal_fn equal_fn, void *ctx) 40 { 41 map->hash_fn = hash_fn; 42 map->equal_fn = equal_fn; 43 map->ctx = ctx; 44 45 map->buckets = NULL; 46 map->cap = 0; 47 map->cap_bits = 0; 48 map->sz = 0; 49 } 50 51 struct hashmap *hashmap__new(hashmap_hash_fn hash_fn, 52 hashmap_equal_fn equal_fn, 53 void *ctx) 54 { 55 struct hashmap *map = malloc(sizeof(struct hashmap)); 56 57 if (!map) 58 return ERR_PTR(-ENOMEM); 59 hashmap__init(map, hash_fn, equal_fn, ctx); 60 return map; 61 } 62 63 void hashmap__clear(struct hashmap *map) 64 { 65 struct hashmap_entry *cur, *tmp; 66 size_t bkt; 67 68 hashmap__for_each_entry_safe(map, cur, tmp, bkt) { 69 free(cur); 70 } 71 free(map->buckets); 72 map->buckets = NULL; 73 map->cap = map->cap_bits = map->sz = 0; 74 } 75 76 void hashmap__free(struct hashmap *map) 77 { 78 if (!map) 79 return; 80 81 hashmap__clear(map); 82 free(map); 83 } 84 85 size_t hashmap__size(const struct hashmap *map) 86 { 87 return map->sz; 88 } 89 90 size_t hashmap__capacity(const struct hashmap *map) 91 { 92 return map->cap; 93 } 94 95 static bool hashmap_needs_to_grow(struct hashmap *map) 96 { 97 /* grow if empty or more than 75% filled */ 98 return (map->cap == 0) || ((map->sz + 1) * 4 / 3 > map->cap); 99 } 100 101 static int hashmap_grow(struct hashmap *map) 102 { 103 struct hashmap_entry **new_buckets; 104 struct hashmap_entry *cur, *tmp; 105 size_t new_cap_bits, new_cap; 106 size_t h, bkt; 107 108 new_cap_bits = map->cap_bits + 1; 109 if (new_cap_bits < HASHMAP_MIN_CAP_BITS) 110 new_cap_bits = HASHMAP_MIN_CAP_BITS; 111 112 new_cap = 1UL << new_cap_bits; 113 new_buckets = calloc(new_cap, sizeof(new_buckets[0])); 114 if (!new_buckets) 115 return -ENOMEM; 116 117 hashmap__for_each_entry_safe(map, cur, tmp, bkt) { 118 h = hash_bits(map->hash_fn(cur->key, map->ctx), new_cap_bits); 119 hashmap_add_entry(&new_buckets[h], cur); 120 } 121 122 map->cap = new_cap; 123 map->cap_bits = new_cap_bits; 124 free(map->buckets); 125 map->buckets = new_buckets; 126 127 return 0; 128 } 129 130 static bool hashmap_find_entry(const struct hashmap *map, 131 const void *key, size_t hash, 132 struct hashmap_entry ***pprev, 133 struct hashmap_entry **entry) 134 { 135 struct hashmap_entry *cur, **prev_ptr; 136 137 if (!map->buckets) 138 return false; 139 140 for (prev_ptr = &map->buckets[hash], cur = *prev_ptr; 141 cur; 142 prev_ptr = &cur->next, cur = cur->next) { 143 if (map->equal_fn(cur->key, key, map->ctx)) { 144 if (pprev) 145 *pprev = prev_ptr; 146 *entry = cur; 147 return true; 148 } 149 } 150 151 return false; 152 } 153 154 int hashmap__insert(struct hashmap *map, const void *key, void *value, 155 enum hashmap_insert_strategy strategy, 156 const void **old_key, void **old_value) 157 { 158 struct hashmap_entry *entry; 159 size_t h; 160 int err; 161 162 if (old_key) 163 *old_key = NULL; 164 if (old_value) 165 *old_value = NULL; 166 167 h = hash_bits(map->hash_fn(key, map->ctx), map->cap_bits); 168 if (strategy != HASHMAP_APPEND && 169 hashmap_find_entry(map, key, h, NULL, &entry)) { 170 if (old_key) 171 *old_key = entry->key; 172 if (old_value) 173 *old_value = entry->value; 174 175 if (strategy == HASHMAP_SET || strategy == HASHMAP_UPDATE) { 176 entry->key = key; 177 entry->value = value; 178 return 0; 179 } else if (strategy == HASHMAP_ADD) { 180 return -EEXIST; 181 } 182 } 183 184 if (strategy == HASHMAP_UPDATE) 185 return -ENOENT; 186 187 if (hashmap_needs_to_grow(map)) { 188 err = hashmap_grow(map); 189 if (err) 190 return err; 191 h = hash_bits(map->hash_fn(key, map->ctx), map->cap_bits); 192 } 193 194 entry = malloc(sizeof(struct hashmap_entry)); 195 if (!entry) 196 return -ENOMEM; 197 198 entry->key = key; 199 entry->value = value; 200 hashmap_add_entry(&map->buckets[h], entry); 201 map->sz++; 202 203 return 0; 204 } 205 206 bool hashmap__find(const struct hashmap *map, const void *key, void **value) 207 { 208 struct hashmap_entry *entry; 209 size_t h; 210 211 h = hash_bits(map->hash_fn(key, map->ctx), map->cap_bits); 212 if (!hashmap_find_entry(map, key, h, NULL, &entry)) 213 return false; 214 215 if (value) 216 *value = entry->value; 217 return true; 218 } 219 220 bool hashmap__delete(struct hashmap *map, const void *key, 221 const void **old_key, void **old_value) 222 { 223 struct hashmap_entry **pprev, *entry; 224 size_t h; 225 226 h = hash_bits(map->hash_fn(key, map->ctx), map->cap_bits); 227 if (!hashmap_find_entry(map, key, h, &pprev, &entry)) 228 return false; 229 230 if (old_key) 231 *old_key = entry->key; 232 if (old_value) 233 *old_value = entry->value; 234 235 hashmap_del_entry(pprev, entry); 236 free(entry); 237 map->sz--; 238 239 return true; 240 } 241 242