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 int 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; 104 int bkt; 105 106 new_cap_bits = map->cap_bits + 1; 107 if (new_cap_bits < HASHMAP_MIN_CAP_BITS) 108 new_cap_bits = HASHMAP_MIN_CAP_BITS; 109 110 new_cap = 1UL << new_cap_bits; 111 new_buckets = calloc(new_cap, sizeof(new_buckets[0])); 112 if (!new_buckets) 113 return -ENOMEM; 114 115 hashmap__for_each_entry_safe(map, cur, tmp, bkt) { 116 h = hash_bits(map->hash_fn(cur->key, map->ctx), new_cap_bits); 117 hashmap_add_entry(&new_buckets[h], cur); 118 } 119 120 map->cap = new_cap; 121 map->cap_bits = new_cap_bits; 122 free(map->buckets); 123 map->buckets = new_buckets; 124 125 return 0; 126 } 127 128 static bool hashmap_find_entry(const struct hashmap *map, 129 const void *key, size_t hash, 130 struct hashmap_entry ***pprev, 131 struct hashmap_entry **entry) 132 { 133 struct hashmap_entry *cur, **prev_ptr; 134 135 if (!map->buckets) 136 return false; 137 138 for (prev_ptr = &map->buckets[hash], cur = *prev_ptr; 139 cur; 140 prev_ptr = &cur->next, cur = cur->next) { 141 if (map->equal_fn(cur->key, key, map->ctx)) { 142 if (pprev) 143 *pprev = prev_ptr; 144 *entry = cur; 145 return true; 146 } 147 } 148 149 return false; 150 } 151 152 int hashmap__insert(struct hashmap *map, const void *key, void *value, 153 enum hashmap_insert_strategy strategy, 154 const void **old_key, void **old_value) 155 { 156 struct hashmap_entry *entry; 157 size_t h; 158 int err; 159 160 if (old_key) 161 *old_key = NULL; 162 if (old_value) 163 *old_value = NULL; 164 165 h = hash_bits(map->hash_fn(key, map->ctx), map->cap_bits); 166 if (strategy != HASHMAP_APPEND && 167 hashmap_find_entry(map, key, h, NULL, &entry)) { 168 if (old_key) 169 *old_key = entry->key; 170 if (old_value) 171 *old_value = entry->value; 172 173 if (strategy == HASHMAP_SET || strategy == HASHMAP_UPDATE) { 174 entry->key = key; 175 entry->value = value; 176 return 0; 177 } else if (strategy == HASHMAP_ADD) { 178 return -EEXIST; 179 } 180 } 181 182 if (strategy == HASHMAP_UPDATE) 183 return -ENOENT; 184 185 if (hashmap_needs_to_grow(map)) { 186 err = hashmap_grow(map); 187 if (err) 188 return err; 189 h = hash_bits(map->hash_fn(key, map->ctx), map->cap_bits); 190 } 191 192 entry = malloc(sizeof(struct hashmap_entry)); 193 if (!entry) 194 return -ENOMEM; 195 196 entry->key = key; 197 entry->value = value; 198 hashmap_add_entry(&map->buckets[h], entry); 199 map->sz++; 200 201 return 0; 202 } 203 204 bool hashmap__find(const struct hashmap *map, const void *key, void **value) 205 { 206 struct hashmap_entry *entry; 207 size_t h; 208 209 h = hash_bits(map->hash_fn(key, map->ctx), map->cap_bits); 210 if (!hashmap_find_entry(map, key, h, NULL, &entry)) 211 return false; 212 213 if (value) 214 *value = entry->value; 215 return true; 216 } 217 218 bool hashmap__delete(struct hashmap *map, const void *key, 219 const void **old_key, void **old_value) 220 { 221 struct hashmap_entry **pprev, *entry; 222 size_t h; 223 224 h = hash_bits(map->hash_fn(key, map->ctx), map->cap_bits); 225 if (!hashmap_find_entry(map, key, h, &pprev, &entry)) 226 return false; 227 228 if (old_key) 229 *old_key = entry->key; 230 if (old_value) 231 *old_value = entry->value; 232 233 hashmap_del_entry(pprev, entry); 234 free(entry); 235 map->sz--; 236 237 return true; 238 } 239 240