1 /* vim:expandtab:tw=80:ts=2:sts=2:sw=2
2 */
3 /*-
4 * Copyright (c) 2011 Christoph Erhardt. All rights reserved.
5 *
6 * Redistribution and use in source and binary forms, with or without
7 * modification, are permitted provided that the following conditions are met:
8 * 1. Redistributions of source code must retain the above copyright notice,
9 * this list of conditions and the following disclaimer.
10 * 2. Redistributions in binary form must reproduce the above copyright notice,
11 * this list of conditions and the following disclaimer in the documentation
12 * and/or other materials provided with the distribution.
13 *
14 * THIS SOFTWARE IS PROVIDED BY CHRISTOPH ERHARDT ``AS IS'' AND ANY EXPRESS OR
15 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
16 * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO
17 * EVENT SHALL CHRISTOPH ERHARDT OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
18 * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
19 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
20 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
21 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
22 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
23 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
24 */
25 /*-
26 * Modified by Clemens Lang to accept values of arbitrary type.
27 */
28
29
30 #ifndef _BSD_SOURCE
31 #define _BSD_SOURCE
32 #endif
33 #ifndef _CRT_NONSTDC_NO_DEPRECATE
34 #define _CRT_NONSTDC_NO_DEPRECATE
35 #endif
36
37 #include "hashmap.h"
38 #include <limits.h>
39 #include <stdint.h>
40 #include <string.h>
41
42
43 static const size_t INITIAL_CAPACITY = 16; /* Must be a power of 2 */
44 static const size_t MAXIMUM_CAPACITY = (1U << 31);
45 static const float LOAD_FACTOR = 0.75;
46
47
48 typedef struct HashMapEntry {
49 char *key;
50 const void *value;
51 struct HashMapEntry *next;
52 uint32_t hash;
53 } HashMapEntry;
54
55 struct HashMap {
56 HashMapEntry **table;
57 size_t capacity;
58 size_t size;
59 size_t threshold;
60 void (*freeFunc)(const void *);
61 };
62
63
setTable(HashMap * map,HashMapEntry ** table,size_t capacity)64 static void setTable(HashMap *map, HashMapEntry **table, size_t capacity) {
65 map->table = table;
66 map->capacity = capacity;
67 map->threshold = (size_t) (capacity * LOAD_FACTOR);
68 }
69
70
doHash(const char key[])71 static uint32_t doHash(const char key[]) {
72 size_t length;
73 size_t i;
74 uint32_t h = 0;
75 if (key == NULL)
76 return 0;
77 length = strlen(key);
78 for (i = 0; i < length; ++i) {
79 h = (31 * h) + key[i];
80 }
81 h ^= (h >> 20) ^ (h >> 12);
82 return h ^ (h >> 7) ^ (h >> 4);
83 }
84
85
indexFor(uint32_t hash,size_t length)86 static size_t indexFor(uint32_t hash, size_t length) {
87 return hash & (length - 1);
88 }
89
90
isHit(HashMapEntry * e,const char key[],uint32_t hash)91 static int isHit(HashMapEntry *e, const char key[], uint32_t hash) {
92 return (e->hash == hash
93 && (e->key == key || (key != NULL && strcmp(e->key, key) == 0)));
94 }
95
96
copyOrFree(void (* freeFunc)(const void *),const void * value,const void ** valPtr)97 static void copyOrFree(void (*freeFunc)(const void *),
98 const void *value, const void **valPtr) {
99 if (valPtr != NULL)
100 *valPtr = value;
101 else
102 freeFunc(value);
103 }
104
105
updateValue(HashMap * map,HashMapEntry * e,const void * newVal,const void ** oldValPtr)106 static int updateValue(HashMap *map, HashMapEntry *e, const void *newVal,
107 const void **oldValPtr) {
108 copyOrFree(map->freeFunc, e->value, oldValPtr);
109 e->value = newVal;
110 return 1;
111 }
112
113
114 /* Creates a hash map. */
hashMapCreate(void (* freeFunc)(const void *))115 HashMap *hashMapCreate(void (*freeFunc)(const void *)) {
116 HashMapEntry **table;
117 HashMap *map = malloc(sizeof(*map));
118 if (map == NULL)
119 return NULL;
120 table = calloc(INITIAL_CAPACITY, sizeof(*map->table));
121 if (table == NULL) {
122 free(map);
123 return NULL;
124 }
125 setTable(map, table, INITIAL_CAPACITY);
126 map->size = 0;
127 map->freeFunc = freeFunc;
128 return map;
129 }
130
131
132 /* Inserts a key-value pair into a hash map. */
hashMapPut(HashMap * map,const char key[],const void * const value,const void ** oldValPtr)133 int hashMapPut(HashMap *map, const char key[], const void * const value,
134 const void **oldValPtr) {
135
136 HashMapEntry *e;
137 size_t newCapacity;
138 HashMapEntry **newTable;
139 size_t i;
140
141 /* If an entry with the same key exists, update it */
142 uint32_t hash = doHash(key);
143 size_t index = indexFor(hash, map->capacity);
144 for (e = map->table[index]; e != NULL; e = e->next) {
145 if (isHit(e, key, hash) == 0)
146 continue;
147 return updateValue(map, e, value, oldValPtr);
148 }
149
150 /* Create a new entry */
151 e = calloc(1, sizeof(HashMapEntry)); /* Must be zeroed */
152 if (e == NULL)
153 return 0;
154
155 /* Copy key and value into the entry */
156 if (key != NULL) {
157 e->key = strdup(key);
158 if (e->key == NULL) {
159 free(e);
160 return 0;
161 }
162 }
163 if (updateValue(map, e, value, oldValPtr) == 0) {
164 free(e->key);
165 free(e);
166 return 0;
167 }
168
169 /* Insert entry into the table */
170 e->hash = hash;
171 e->next = map->table[index];
172 map->table[index] = e;
173 if (map->size++ < map->threshold)
174 return 1;
175
176 /* If the size exceeds the threshold, double the table's capacity */
177 newCapacity = 2 * map->capacity;
178 if (map->capacity == MAXIMUM_CAPACITY) {
179 map->threshold = UINT_MAX;
180 return 1;
181 }
182 newTable = calloc(newCapacity, sizeof(*newTable));
183 if (newTable == NULL)
184 return 0;
185
186 /* Copy entries from the old table into the new one */
187 for (i = 0; i < map->capacity; ++i) {
188 HashMapEntry *next;
189 for (e = map->table[i]; e != NULL; e = next) {
190 index = indexFor(e->hash, newCapacity);
191 next = e->next;
192 e->next = newTable[index];
193 newTable[index] = e;
194 }
195 }
196
197 /* Release the old table and set the new one */
198 free(map->table);
199 setTable(map, newTable, newCapacity);
200 return 1;
201 }
202
203
204 /* Performs a hash map lookup. */
hashMapGet(HashMap * map,const char key[])205 const void *hashMapGet(HashMap *map, const char key[]) {
206 HashMapEntry *e;
207 uint32_t hash = doHash(key);
208 size_t index = indexFor(hash, map->capacity);
209 for (e = map->table[index]; e != NULL; e = e->next) {
210 if (isHit(e, key, hash))
211 return e->value;
212 }
213 return NULL;
214 }
215
216
217 /* Checks whether a hash map contains an entry with a certain key. */
hashMapContainsKey(HashMap * map,const char key[])218 int hashMapContainsKey(HashMap *map, const char key[]) {
219 HashMapEntry *e;
220 uint32_t hash = doHash(key);
221 size_t index = indexFor(hash, map->capacity);
222 for (e = map->table[index]; e != NULL; e = e->next) {
223 if (isHit(e, key, hash))
224 return 1;
225 }
226 return 0;
227 }
228
229
230 /* Removes a key-value pair from a hash map. */
hashMapRemove(HashMap * map,const char key[],const void ** valPtr)231 void hashMapRemove(HashMap *map, const char key[], const void **valPtr) {
232 uint32_t hash = doHash(key);
233 size_t index = indexFor(hash, map->capacity);
234 HashMapEntry *prev = map->table[index];
235 HashMapEntry *e = prev;
236 while (e != NULL) {
237 HashMapEntry *next = e->next;
238 if (isHit(e, key, hash)) {
239 map->size--;
240 if (prev == e)
241 map->table[index] = next;
242 else
243 prev->next = next;
244 break;
245 }
246 prev = e;
247 e = next;
248 }
249 if (e == NULL) {
250 copyOrFree(map->freeFunc, NULL, valPtr);
251 return;
252 }
253 free(e->key);
254 copyOrFree(map->freeFunc, e->value, valPtr);
255 free(e);
256 }
257
258
259 /* Returns the number of elements stored in a hash map. */
hashMapSize(const HashMap * map)260 size_t hashMapSize(const HashMap *map) {
261 return map->size;
262 }
263
264
265 /* Checks whether a hash map is empty. */
hashMapIsEmpty(const HashMap * map)266 int hashMapIsEmpty(const HashMap *map) {
267 return (map->size == 0);
268 }
269
270
271 /* Removes all entries from a hash map. */
hashMapClear(HashMap * map)272 void hashMapClear(HashMap *map) {
273 size_t i;
274 for (i = 0; i < map->capacity; ++i) {
275 HashMapEntry *e;
276 HashMapEntry *next;
277 for (e = map->table[i]; e != NULL; e = next) {
278 free(e->key);
279 map->freeFunc(e->value);
280 next = e->next;
281 free(e);
282 }
283 map->table[i] = NULL;
284 }
285 }
286
287
288 /* Destroys a hash map. */
hashMapDestroy(HashMap * map)289 void hashMapDestroy(HashMap *map) {
290 if (map == NULL)
291 return;
292 hashMapClear(map);
293 free(map->table);
294 free(map);
295 }
296