1 /*
2 * Copyright 2020 Daniel Silverstone <dsilvers@netsurf-browser.org>
3 *
4 * This file is part of NetSurf, http://www.netsurf-browser.org/
5 *
6 * NetSurf is free software; you can redistribute it and/or modify
7 * it under the terms of the GNU General Public License as published by
8 * the Free Software Foundation; version 2 of the License.
9 *
10 * NetSurf is distributed in the hope that it will be useful,
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 * GNU General Public License for more details.
14 *
15 * You should have received a copy of the GNU General Public License
16 * along with this program. If not, see <http://www.gnu.org/licenses/>.
17 */
18
19 #include <stdlib.h>
20 #include <string.h>
21
22 #include "utils/hashmap.h"
23
24 /**
25 * The default number of buckets in the hashmaps we create.
26 */
27 #define DEFAULT_HASHMAP_BUCKETS (4091)
28
29 /**
30 * Hashmaps have chains of entries in buckets.
31 */
32 typedef struct hashmap_entry_s {
33 struct hashmap_entry_s **prevptr;
34 struct hashmap_entry_s *next;
35 void *key;
36 void *value;
37 uint32_t key_hash;
38 } hashmap_entry_t;
39
40 /**
41 * The content of a hashmap
42 */
43 struct hashmap_s {
44 /**
45 * The parameters to be used for this hashmap
46 */
47 hashmap_parameters_t *params;
48
49 /**
50 * The buckets for the hash chains
51 */
52 hashmap_entry_t **buckets;
53
54 /**
55 * The number of buckets in this map
56 */
57 uint32_t bucket_count;
58
59 /**
60 * The number of entries in this map
61 */
62 size_t entry_count;
63 };
64
65 /* Exported function, documented in hashmap.h */
66 hashmap_t *
hashmap_create(hashmap_parameters_t * params)67 hashmap_create(hashmap_parameters_t *params)
68 {
69 hashmap_t *ret = malloc(sizeof(hashmap_t));
70 if (ret == NULL) {
71 return NULL;
72 }
73
74 ret->params = params;
75 ret->bucket_count = DEFAULT_HASHMAP_BUCKETS;
76 ret->entry_count = 0;
77 ret->buckets = malloc(ret->bucket_count * sizeof(hashmap_entry_t *));
78
79 if (ret->buckets == NULL) {
80 free(ret);
81 return NULL;
82 }
83
84 memset(ret->buckets, 0, ret->bucket_count * sizeof(hashmap_entry_t *));
85
86 return ret;
87 }
88
89 /* Exported function, documented in hashmap.h */
90 void
hashmap_destroy(hashmap_t * hashmap)91 hashmap_destroy(hashmap_t *hashmap)
92 {
93 uint32_t bucket;
94 hashmap_entry_t *entry;
95
96 for (bucket = 0; bucket < hashmap->bucket_count; bucket++) {
97 for (entry = hashmap->buckets[bucket];
98 entry != NULL;) {
99 hashmap_entry_t *next = entry->next;
100 hashmap->params->value_destroy(entry->value);
101 hashmap->params->key_destroy(entry->key);
102 free(entry);
103 entry = next;
104 }
105 }
106
107 free(hashmap->buckets);
108 free(hashmap);
109 }
110
111 /* Exported function, documented in hashmap.h */
112 void *
hashmap_lookup(hashmap_t * hashmap,void * key)113 hashmap_lookup(hashmap_t *hashmap, void *key)
114 {
115 uint32_t hash = hashmap->params->key_hash(key);
116 hashmap_entry_t *entry = hashmap->buckets[hash % hashmap->bucket_count];
117
118 for(;entry != NULL; entry = entry->next) {
119 if (entry->key_hash == hash) {
120 if (hashmap->params->key_eq(key, entry->key)) {
121 return entry->value;
122 }
123 }
124 }
125
126 return NULL;
127 }
128
129 /* Exported function, documented in hashmap.h */
130 void *
hashmap_insert(hashmap_t * hashmap,void * key)131 hashmap_insert(hashmap_t *hashmap, void *key)
132 {
133 uint32_t hash = hashmap->params->key_hash(key);
134 uint32_t bucket = hash % hashmap->bucket_count;
135 hashmap_entry_t *entry = hashmap->buckets[bucket];
136 void *new_key, *new_value;
137
138 for(;entry != NULL; entry = entry->next) {
139 if (entry->key_hash == hash) {
140 if (hashmap->params->key_eq(key, entry->key)) {
141 /* This key is already here */
142 new_key = hashmap->params->key_clone(key);
143 if (new_key == NULL) {
144 /* Allocation failed */
145 return NULL;
146 }
147 new_value = hashmap->params->value_alloc(entry->key);
148 if (new_value == NULL) {
149 /* Allocation failed */
150 hashmap->params->key_destroy(new_key);
151 return NULL;
152 }
153 hashmap->params->value_destroy(entry->value);
154 hashmap->params->key_destroy(entry->key);
155 entry->value = new_value;
156 entry->key = new_key;
157 return entry->value;
158 }
159 }
160 }
161
162 /* The key was not found in the map, so allocate a new entry */
163 entry = malloc(sizeof(*entry));
164
165 if (entry == NULL) {
166 return NULL;
167 }
168
169 memset(entry, 0, sizeof(*entry));
170
171 entry->key = hashmap->params->key_clone(key);
172 if (entry->key == NULL) {
173 goto err;
174 }
175 entry->key_hash = hash;
176
177 entry->value = hashmap->params->value_alloc(entry->key);
178 if (entry->value == NULL) {
179 goto err;
180 }
181
182 entry->prevptr = &(hashmap->buckets[bucket]);
183 entry->next = hashmap->buckets[bucket];
184 if (entry->next != NULL) {
185 entry->next->prevptr = &entry->next;
186 }
187
188 hashmap->buckets[bucket] = entry;
189
190 hashmap->entry_count++;
191
192 return entry->value;
193
194 err:
195 if (entry->value != NULL)
196 hashmap->params->value_destroy(entry->value);
197 if (entry->key != NULL)
198 hashmap->params->key_destroy(entry->key);
199 free(entry);
200
201 return NULL;
202 }
203
204 /* Exported function, documented in hashmap.h */
205 bool
hashmap_remove(hashmap_t * hashmap,void * key)206 hashmap_remove(hashmap_t *hashmap, void *key)
207 {
208 uint32_t hash = hashmap->params->key_hash(key);
209
210 hashmap_entry_t *entry = hashmap->buckets[hash % hashmap->bucket_count];
211
212 for(;entry != NULL; entry = entry->next) {
213 if (entry->key_hash == hash) {
214 if (hashmap->params->key_eq(key, entry->key)) {
215 hashmap->params->value_destroy(entry->value);
216 hashmap->params->key_destroy(entry->key);
217 if (entry->next != NULL) {
218 entry->next->prevptr = entry->prevptr;
219 }
220 *entry->prevptr = entry->next;
221 free(entry);
222 hashmap->entry_count--;
223 return true;
224 }
225 }
226 }
227
228 return false;
229 }
230
231 /* Exported function, documented in hashmap.h */
232 bool
hashmap_iterate(hashmap_t * hashmap,hashmap_iteration_cb_t cb,void * ctx)233 hashmap_iterate(hashmap_t *hashmap, hashmap_iteration_cb_t cb, void *ctx)
234 {
235 for (uint32_t bucket = 0;
236 bucket < hashmap->bucket_count;
237 bucket++) {
238 for (hashmap_entry_t *entry = hashmap->buckets[bucket];
239 entry != NULL;
240 entry = entry->next) {
241 /* If the callback returns true, we early-exit */
242 if (cb(entry->key, entry->value, ctx))
243 return true;
244 }
245 }
246
247 return false;
248 }
249
250 /* Exported function, documented in hashmap.h */
251 size_t
hashmap_count(hashmap_t * hashmap)252 hashmap_count(hashmap_t *hashmap)
253 {
254 return hashmap->entry_count;
255 }
256