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