1 /*
2 * This file is part of RGBDS.
3 *
4 * Copyright (c) 2019, Eldred Habert and RGBDS contributors.
5 *
6 * SPDX-License-Identifier: MIT
7 */
8
9 #include <stdint.h>
10 #include <stdbool.h>
11 #include <stdlib.h>
12 #include <string.h>
13 #include <assert.h>
14
15 #include "error.h"
16 #include "hashmap.h"
17
18 /*
19 * The lower half of the hash is used to index the "master" table,
20 * the upper half is used to help resolve collisions more quickly
21 */
22 #define UINT_BITS_(NB_BITS) uint##NB_BITS##_t
23 #define UINT_BITS(NB_BITS) UINT_BITS_(NB_BITS)
24 typedef UINT_BITS(HASH_NB_BITS) HashType;
25 typedef UINT_BITS(HALF_HASH_NB_BITS) HalfHashType;
26
27 struct HashMapEntry {
28 HalfHashType hash;
29 char const *key;
30 void *content;
31 struct HashMapEntry *next;
32 };
33
34 #define FNV_OFFSET_BASIS 0x811c9dc5
35 #define FNV_PRIME 16777619
36
37 /* FNV-1a hash */
hash(char const * str)38 static HashType hash(char const *str)
39 {
40 HashType hash = FNV_OFFSET_BASIS;
41
42 while (*str) {
43 hash ^= (uint8_t)*str++;
44 hash *= FNV_PRIME;
45 }
46 return hash;
47 }
48
hash_AddElement(HashMap map,char const * key,void * element)49 void **hash_AddElement(HashMap map, char const *key, void *element)
50 {
51 HashType hashedKey = hash(key);
52 HalfHashType index = hashedKey;
53 struct HashMapEntry *newEntry = malloc(sizeof(*newEntry));
54
55 if (!newEntry)
56 err("%s: Failed to allocate new entry", __func__);
57
58 newEntry->hash = hashedKey >> HALF_HASH_NB_BITS;
59 newEntry->key = key;
60 newEntry->content = element;
61 newEntry->next = map[index];
62 map[index] = newEntry;
63
64 return &newEntry->content;
65 }
66
hash_RemoveElement(HashMap map,char const * key)67 bool hash_RemoveElement(HashMap map, char const *key)
68 {
69 HashType hashedKey = hash(key);
70 struct HashMapEntry **ptr = &map[(HalfHashType)hashedKey];
71
72 while (*ptr) {
73 if (hashedKey >> HALF_HASH_NB_BITS == (*ptr)->hash
74 && !strcmp((*ptr)->key, key)) {
75 struct HashMapEntry *next = (*ptr)->next;
76
77 free(*ptr);
78 *ptr = next;
79 return true;
80 }
81 ptr = &(*ptr)->next;
82 }
83 return false;
84 }
85
hash_GetNode(HashMap const map,char const * key)86 void **hash_GetNode(HashMap const map, char const *key)
87 {
88 HashType hashedKey = hash(key);
89 struct HashMapEntry *ptr = map[(HalfHashType)hashedKey];
90
91 while (ptr) {
92 if (hashedKey >> HALF_HASH_NB_BITS == ptr->hash
93 && !strcmp(ptr->key, key)) {
94 return &ptr->content;
95 }
96 ptr = ptr->next;
97 }
98 return NULL;
99 }
100
hash_GetElement(HashMap const map,char const * key)101 void *hash_GetElement(HashMap const map, char const *key)
102 {
103 void **node = hash_GetNode(map, key);
104
105 return node ? *node : NULL;
106 }
107
hash_ForEach(HashMap const map,void (* func)(void *,void *),void * arg)108 void hash_ForEach(HashMap const map, void (*func)(void *, void *), void *arg)
109 {
110 for (size_t i = 0; i < HASHMAP_NB_BUCKETS; i++) {
111 struct HashMapEntry *ptr = map[i];
112
113 while (ptr) {
114 func(ptr->content, arg);
115 ptr = ptr->next;
116 }
117 }
118 }
119
hash_EmptyMap(HashMap map)120 void hash_EmptyMap(HashMap map)
121 {
122 for (size_t i = 0; i < HASHMAP_NB_BUCKETS; i++) {
123 struct HashMapEntry *ptr = map[i];
124
125 while (ptr) {
126 struct HashMapEntry *next = ptr->next;
127
128 free(ptr);
129 ptr = next;
130 }
131 map[i] = NULL;
132 }
133 }
134