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 
hashmap_add_entry(struct hashmap_entry ** pprev,struct hashmap_entry * entry)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 
hashmap_del_entry(struct hashmap_entry ** pprev,struct hashmap_entry * entry)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 
hashmap__init(struct hashmap * map,hashmap_hash_fn hash_fn,hashmap_equal_fn equal_fn,void * ctx)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 
hashmap__new(hashmap_hash_fn hash_fn,hashmap_equal_fn equal_fn,void * ctx)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 
hashmap__clear(struct hashmap * map)57 void hashmap__clear(struct hashmap *map)
58 {
59 	free(map->buckets);
60 	map->cap = map->cap_bits = map->sz = 0;
61 }
62 
hashmap__free(struct hashmap * map)63 void hashmap__free(struct hashmap *map)
64 {
65 	if (!map)
66 		return;
67 
68 	hashmap__clear(map);
69 	free(map);
70 }
71 
hashmap__size(const struct hashmap * map)72 size_t hashmap__size(const struct hashmap *map)
73 {
74 	return map->sz;
75 }
76 
hashmap__capacity(const struct hashmap * map)77 size_t hashmap__capacity(const struct hashmap *map)
78 {
79 	return map->cap;
80 }
81 
hashmap_needs_to_grow(struct hashmap * map)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 
hashmap_grow(struct hashmap * map)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 
hashmap_find_entry(const struct hashmap * map,const void * key,size_t hash,struct hashmap_entry *** pprev,struct hashmap_entry ** entry)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 
hashmap__insert(struct hashmap * map,const void * key,void * value,enum hashmap_insert_strategy strategy,const void ** old_key,void ** old_value)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 
hashmap__find(const struct hashmap * map,const void * key,void ** value)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 
hashmap__delete(struct hashmap * map,const void * key,const void ** old_key,void ** old_value)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