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