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