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/* prevent accidental re-addition of reallocarray() */
 19#pragma GCC poison reallocarray
 20
 21/* start with 4 buckets */
 22#define HASHMAP_MIN_CAP_BITS 2
 23
 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}