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
 18static void hashmap_add_entry(struct hashmap_entry **pprev,
 19			      struct hashmap_entry *entry)
 20{
 21	entry->next = *pprev;
 22	*pprev = entry;
 23}
 24
 25static void hashmap_del_entry(struct hashmap_entry **pprev,
 26			      struct hashmap_entry *entry)
 27{
 28	*pprev = entry->next;
 29	entry->next = NULL;
 30}
 31
 32void 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
 45struct 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
 57void hashmap__clear(struct hashmap *map)
 58{
 59	free(map->buckets);
 60	map->cap = map->cap_bits = map->sz = 0;
 61}
 62
 63void hashmap__free(struct hashmap *map)
 64{
 65	if (!map)
 66		return;
 67
 68	hashmap__clear(map);
 69	free(map);
 70}
 71
 72size_t hashmap__size(const struct hashmap *map)
 73{
 74	return map->sz;
 75}
 76
 77size_t hashmap__capacity(const struct hashmap *map)
 78{
 79	return map->cap;
 80}
 81
 82static 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
 88static 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
118static 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
142int 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
194bool 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
208bool 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