241 lines · c
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 Facebook7 */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 s6417 18/* prevent accidental re-addition of reallocarray() */19#pragma GCC poison reallocarray20 21/* start with 4 buckets */22#define HASHMAP_MIN_CAP_BITS 223 24static void hashmap_add_entry(struct hashmap_entry **pprev,25 struct hashmap_entry *entry)26{27 entry->next = *pprev;28 *pprev = entry;29}30 31static void hashmap_del_entry(struct hashmap_entry **pprev,32 struct hashmap_entry *entry)33{34 *pprev = entry->next;35 entry->next = NULL;36}37 38void 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 51struct 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 63void hashmap__clear(struct hashmap *map)64{65 struct hashmap_entry *cur, *tmp;66 size_t bkt;67 68 hashmap__for_each_entry_safe(map, cur, tmp, bkt) {69 free(cur);70 }71 free(map->buckets);72 map->buckets = NULL;73 map->cap = map->cap_bits = map->sz = 0;74}75 76void hashmap__free(struct hashmap *map)77{78 if (IS_ERR_OR_NULL(map))79 return;80 81 hashmap__clear(map);82 free(map);83}84 85size_t hashmap__size(const struct hashmap *map)86{87 return map->sz;88}89 90size_t hashmap__capacity(const struct hashmap *map)91{92 return map->cap;93}94 95static 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 101static 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;106 size_t h, bkt;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 130static bool hashmap_find_entry(const struct hashmap *map,131 const long 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 154int hashmap_insert(struct hashmap *map, long key, long value,155 enum hashmap_insert_strategy strategy,156 long *old_key, long *old_value)157{158 struct hashmap_entry *entry;159 size_t h;160 int err;161 162 if (old_key)163 *old_key = 0;164 if (old_value)165 *old_value = 0;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 206bool hashmap_find(const struct hashmap *map, long key, long *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 220bool hashmap_delete(struct hashmap *map, long key,221 long *old_key, long *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