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