Andrii Nakryiko | e3b9242 | 2019-05-24 11:59:00 -0700 | [diff] [blame] | 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 | |
Andrii Nakryiko | 1d1a3bc | 2020-01-10 10:19:16 -0800 | [diff] [blame] | 15 | /* make sure libbpf doesn't use kernel-only integer typedefs */ |
| 16 | #pragma GCC poison u8 u16 u32 u64 s8 s16 s32 s64 |
| 17 | |
Andrii Nakryiko | 8536703 | 2020-08-18 18:36:06 -0700 | [diff] [blame] | 18 | /* prevent accidental re-addition of reallocarray() */ |
| 19 | #pragma GCC poison reallocarray |
| 20 | |
Andrii Nakryiko | e3b9242 | 2019-05-24 11:59:00 -0700 | [diff] [blame] | 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 | { |
Andrii Nakryiko | 229bf8b | 2020-04-28 18:21:04 -0700 | [diff] [blame] | 65 | struct hashmap_entry *cur, *tmp; |
Ian Rogers | 8d35d74 | 2020-05-15 09:50:03 -0700 | [diff] [blame] | 66 | size_t bkt; |
Andrii Nakryiko | 229bf8b | 2020-04-28 18:21:04 -0700 | [diff] [blame] | 67 | |
| 68 | hashmap__for_each_entry_safe(map, cur, tmp, bkt) { |
| 69 | free(cur); |
| 70 | } |
Andrii Nakryiko | e3b9242 | 2019-05-24 11:59:00 -0700 | [diff] [blame] | 71 | free(map->buckets); |
Andrii Nakryiko | 229bf8b | 2020-04-28 18:21:04 -0700 | [diff] [blame] | 72 | map->buckets = NULL; |
Andrii Nakryiko | e3b9242 | 2019-05-24 11:59:00 -0700 | [diff] [blame] | 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; |
Ian Rogers | 8d35d74 | 2020-05-15 09:50:03 -0700 | [diff] [blame] | 106 | size_t h, bkt; |
Andrii Nakryiko | e3b9242 | 2019-05-24 11:59:00 -0700 | [diff] [blame] | 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 | |