1 // hashmap.c -- Basic implementation of a hashmap abstract data type
2 // Copyright (C) 2008-2009 Markus Gutschke <markus@shellinabox.com>
3 //
4 // This program is free software; you can redistribute it and/or modify
5 // it under the terms of the GNU General Public License version 2 as
6 // published by the Free Software Foundation.
7 //
8 // This program is distributed in the hope that it will be useful,
9 // but WITHOUT ANY WARRANTY; without even the implied warranty of
10 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
11 // GNU General Public License for more details.
12 //
13 // You should have received a copy of the GNU General Public License along
14 // with this program; if not, write to the Free Software Foundation, Inc.,
15 // 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
16 //
17 // In addition to these license terms, the author grants the following
18 // additional rights:
19 //
20 // If you modify this program, or any covered work, by linking or
21 // combining it with the OpenSSL project's OpenSSL library (or a
22 // modified version of that library), containing parts covered by the
23 // terms of the OpenSSL or SSLeay licenses, the author
24 // grants you additional permission to convey the resulting work.
25 // Corresponding Source for a non-source form of such a combination
26 // shall include the source code for the parts of OpenSSL used as well
27 // as that of the covered work.
28 //
29 // You may at your option choose to remove this additional permission from
30 // the work, or from any part of it.
31 //
32 // It is possible to build this program in a way that it loads OpenSSL
33 // libraries at run-time. If doing so, the following notices are required
34 // by the OpenSSL and SSLeay licenses:
35 //
36 // This product includes software developed by the OpenSSL Project
37 // for use in the OpenSSL Toolkit. (http://www.openssl.org/)
38 //
39 // This product includes cryptographic software written by Eric Young
40 // (eay@cryptsoft.com)
41 //
42 //
43 // The most up-to-date version of this program is always available from
44 // http://shellinabox.com
45
46 #include "config.h"
47
48 #include <stdlib.h>
49 #include <string.h>
50
51 #include "libhttp/hashmap.h"
52 #include "logging/logging.h"
53
newHashMap(void (* destructor)(void * arg,char * key,char * value),void * arg)54 struct HashMap *newHashMap(void (*destructor)(void *arg, char *key,
55 char *value),
56 void *arg) {
57 struct HashMap *hashmap;
58 check(hashmap = malloc(sizeof(struct HashMap)));
59 initHashMap(hashmap, destructor, arg);
60 return hashmap;
61 }
62
initHashMap(struct HashMap * hashmap,void (* destructor)(void * arg,char * key,char * value),void * arg)63 void initHashMap(struct HashMap *hashmap,
64 void (*destructor)(void *arg, char *key, char *value),
65 void *arg) {
66 hashmap->destructor = destructor;
67 hashmap->arg = arg;
68 hashmap->entries = NULL;
69 hashmap->mapSize = 0;
70 hashmap->numEntries = 0;
71 }
72
destroyHashMap(struct HashMap * hashmap)73 void destroyHashMap(struct HashMap *hashmap) {
74 if (hashmap) {
75 for (int i = 0; i < hashmap->mapSize; i++) {
76 if (hashmap->entries[i]) {
77 for (int j = 0; hashmap->entries[i][j].key; j++) {
78 if (hashmap->destructor) {
79 hashmap->destructor(hashmap->arg,
80 (char *)hashmap->entries[i][j].key,
81 (char *)hashmap->entries[i][j].value);
82 }
83 }
84 free(hashmap->entries[i]);
85 }
86 }
87 free(hashmap->entries);
88 }
89 }
90
deleteHashMap(struct HashMap * hashmap)91 void deleteHashMap(struct HashMap *hashmap) {
92 destroyHashMap(hashmap);
93 free(hashmap);
94 }
95
stringHashFunc(const char * s)96 static unsigned int stringHashFunc(const char *s) {
97 unsigned int h = 0;
98 while (*s) {
99 h = 31*h + *(unsigned char *)s++;
100 }
101 return h;
102 }
103
addToHashMap(struct HashMap * hashmap,const char * key,const char * value)104 const void *addToHashMap(struct HashMap *hashmap, const char *key,
105 const char *value) {
106 if (hashmap->numEntries + 1 > (hashmap->mapSize * 8)/10) {
107 struct HashMap newMap;
108 newMap.numEntries = hashmap->numEntries;
109 if (hashmap->mapSize == 0) {
110 newMap.mapSize = 32;
111 } else if (hashmap->mapSize < 1024) {
112 newMap.mapSize = 2*hashmap->mapSize;
113 } else {
114 newMap.mapSize = hashmap->mapSize + 1024;
115 }
116 check(newMap.entries = calloc(sizeof(void *), newMap.mapSize));
117 for (int i = 0; i < hashmap->mapSize; i++) {
118 if (!hashmap->entries[i]) {
119 continue;
120 }
121 for (int j = 0; hashmap->entries[i][j].key; j++) {
122 addToHashMap(&newMap, hashmap->entries[i][j].key,
123 hashmap->entries[i][j].value);
124 }
125 free(hashmap->entries[i]);
126 }
127 free(hashmap->entries);
128 hashmap->entries = newMap.entries;
129 hashmap->mapSize = newMap.mapSize;
130 hashmap->numEntries = newMap.numEntries;
131 }
132 unsigned hash = stringHashFunc(key);
133 int idx = hash % hashmap->mapSize;
134 int i = 0;
135 if (hashmap->entries[idx]) {
136 for (i = 0; hashmap->entries[idx][i].key; i++) {
137 if (!strcmp(hashmap->entries[idx][i].key, key)) {
138 if (hashmap->destructor) {
139 hashmap->destructor(hashmap->arg,
140 (char *)hashmap->entries[idx][i].key,
141 (char *)hashmap->entries[idx][i].value);
142 }
143 hashmap->entries[idx][i].key = key;
144 hashmap->entries[idx][i].value = value;
145 return value;
146 }
147 }
148 }
149 check(hashmap->entries[idx] = realloc(hashmap->entries[idx],
150 (i+2)*sizeof(*hashmap->entries[idx])));
151 hashmap->entries[idx][i].key = key;
152 hashmap->entries[idx][i].value = value;
153 memset(&hashmap->entries[idx][i+1], 0, sizeof(*hashmap->entries[idx]));
154 hashmap->numEntries++;
155 return value;
156 }
157
deleteFromHashMap(struct HashMap * hashmap,const char * key)158 void deleteFromHashMap(struct HashMap *hashmap, const char *key) {
159 if (hashmap->mapSize == 0) {
160 return;
161 }
162 unsigned hash = stringHashFunc(key);
163 int idx = hash % hashmap->mapSize;
164 if (!hashmap->entries[idx]) {
165 return;
166 }
167 for (int i = 0; hashmap->entries[idx][i].key; i++) {
168 if (!strcmp(hashmap->entries[idx][i].key, key)) {
169 int j = i + 1;
170 while (hashmap->entries[idx][j].key) {
171 j++;
172 }
173 if (hashmap->destructor) {
174 hashmap->destructor(hashmap->arg,
175 (char *)hashmap->entries[idx][i].key,
176 (char *)hashmap->entries[idx][i].value);
177 }
178 if (i != j-1) {
179 memcpy(&hashmap->entries[idx][i], &hashmap->entries[idx][j-1],
180 sizeof(*hashmap->entries[idx]));
181 }
182 memset(&hashmap->entries[idx][j-1], 0, sizeof(*hashmap->entries[idx]));
183 check(--hashmap->numEntries >= 0);
184 }
185 }
186 }
187
getRefFromHashMap(const struct HashMap * hashmap,const char * key)188 char **getRefFromHashMap(const struct HashMap *hashmap, const char *key) {
189 if (hashmap->mapSize == 0) {
190 return NULL;
191 }
192 unsigned hash = stringHashFunc(key);
193 int idx = hash % hashmap->mapSize;
194 if (!hashmap->entries[idx]) {
195 return NULL;
196 }
197 for (int i = 0; hashmap->entries[idx][i].key; i++) {
198 if (!strcmp(hashmap->entries[idx][i].key, key)) {
199 return (char **)&hashmap->entries[idx][i].value;
200 }
201 }
202 return NULL;
203 }
204
getFromHashMap(const struct HashMap * hashmap,const char * key)205 const char *getFromHashMap(const struct HashMap *hashmap, const char *key) {
206 char **ref = getRefFromHashMap(hashmap, key);
207 return ref ? *ref : NULL;
208 }
209
iterateOverHashMap(struct HashMap * hashmap,int (* fnc)(void * arg,const char * key,char ** value),void * arg)210 void iterateOverHashMap(struct HashMap *hashmap,
211 int (*fnc)(void *arg, const char *key, char **value),
212 void *arg) {
213 for (int i = 0; i < hashmap->mapSize; i++) {
214 if (hashmap->entries[i]) {
215 int count = 0;
216 while (hashmap->entries[i][count].key) {
217 count++;
218 }
219 for (int j = 0; j < count; j++) {
220 if (!fnc(arg, hashmap->entries[i][j].key,
221 (char **)&hashmap->entries[i][j].value)) {
222 if (hashmap->destructor) {
223 hashmap->destructor(hashmap->arg,
224 (char *)hashmap->entries[i][j].key,
225 (char *)hashmap->entries[i][j].value);
226 }
227 if (j != count-1) {
228 memcpy(&hashmap->entries[i][j], &hashmap->entries[i][count-1],
229 sizeof(*hashmap->entries[i]));
230 }
231 memset(&hashmap->entries[i][count-1], 0,
232 sizeof(*hashmap->entries[i]));
233 count--;
234 j--;
235 }
236 }
237 }
238 }
239 }
240
getHashmapSize(const struct HashMap * hashmap)241 int getHashmapSize(const struct HashMap *hashmap) {
242 return hashmap->numEntries;
243 }
244