NetSurf
hashtable.c
Go to the documentation of this file.
1/*
2 * Copyright 2006 Rob Kendrick <rjek@rjek.com>
3 * Copyright 2006 Richard Wilson <info@tinct.net>
4 *
5 * This file is part of NetSurf, http://www.netsurf-browser.org/
6 *
7 * NetSurf is free software; you can redistribute it and/or modify
8 * it under the terms of the GNU General Public License as published by
9 * the Free Software Foundation; version 2 of the License.
10 *
11 * NetSurf is distributed in the hope that it will be useful,
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 * GNU General Public License for more details.
15 *
16 * You should have received a copy of the GNU General Public License
17 * along with this program. If not, see <http://www.gnu.org/licenses/>.
18 */
19
20/**
21 * \file
22 * Write-Once hash table for string to string mappings.
23 *
24 * This implementation is unit tested, if you make changes please
25 * ensure the tests continute to pass and if possible, through
26 * valgrind to make sure there are no memory leaks or invalid memory
27 * accesses. If you add new functionality, please include a test for
28 * it that has good coverage along side the other tests.
29 */
30
31#include <stdint.h>
32#include <stdbool.h>
33#include <stdlib.h>
34#include <string.h>
35#include <zlib.h>
36#include <errno.h>
37
38#include "utils/log.h"
39#include "utils/hashtable.h"
40
41
42struct hash_entry {
43 char *pairing; /**< block containing 'key\0value\0' */
44 unsigned int key_length; /**< length of key */
45 struct hash_entry *next; /**< next entry */
46};
47
48struct hash_table {
49 unsigned int nchains;
50 struct hash_entry **chain;
51};
52
53/** maximum length of line for file or inline add */
54#define LINE_BUFFER_SIZE 512
55
56/**
57 * Hash a string, returning a 32bit value. The hash algorithm used is
58 * Fowler Noll Vo - a very fast and simple hash, ideal for short strings.
59 * See http://en.wikipedia.org/wiki/Fowler_Noll_Vo_hash for more details.
60 *
61 * \param datum The string to hash.
62 * \param len Pointer to unsigned integer to record datum's length in.
63 * \return The calculated hash value for the datum.
64 */
65static inline unsigned int hash_string_fnv(const char *datum, unsigned int *len)
66{
67 unsigned int z = 0x811c9dc5;
68 const char *start = datum;
69 *len = 0;
70
71 if (datum == NULL)
72 return 0;
73
74 while (*datum) {
75 z *= 0x01000193;
76 z ^= *datum++;
77 }
78 *len = datum - start;
79
80 return z;
81}
82
83
84
85/**
86 * process a line of input.
87 *
88 * \param hash The hash table to add the line to
89 * \param ln The line to process
90 * \param lnlen The length of \ln
91 * \return NSERROR_OK on success else NSERROR_INVALID
92 */
93static nserror
94process_line(struct hash_table *hash, uint8_t *ln, int lnlen)
95{
96 uint8_t *key;
97 uint8_t *value;
98 uint8_t *colon;
99
100 key = ln; /* set key to start of line */
101 value = ln + lnlen; /* set value to end of line */
102
103 /* skip leading whitespace */
104 while ((key < value) &&
105 ((*key == ' ') || (*key == '\t'))) {
106 key++;
107 }
108
109 /* empty or comment lines */
110 if ((*key == 0) || (*key == '#')) {
111 return NSERROR_OK;
112 }
113
114 /* find first colon as key/value separator */
115 for (colon = key; colon < value; colon++) {
116 if (*colon == ':') {
117 break;
118 }
119 }
120 if (colon == value) {
121 /* no colon found */
122 return NSERROR_INVALID;
123 }
124
125 *colon = 0; /* terminate key */
126 value = colon + 1;
127
128 if (hash_add(hash, (char *)key, (char *)value) == false) {
129 NSLOG(netsurf, INFO,
130 "Unable to add %s:%s to hash table", ln, value);
131 return NSERROR_INVALID;
132 }
133 return NSERROR_OK;
134}
135
136
137/**
138 * adds key/value pairs to a hash from a memory area
139 */
140static nserror
141hash_add_inline_plain(struct hash_table *ht, const uint8_t *data, size_t size)
142{
143 uint8_t s[LINE_BUFFER_SIZE]; /* line buffer */
144 unsigned int slen = 0;
145 nserror res = NSERROR_OK;
146
147 while (size > 0) {
148 s[slen] = *data;
149
150 if (s[slen] == '\n') {
151 s[slen] = 0; /* replace newline with null termination */
152 res = process_line(ht, s, slen);
153 slen = 0;
154 if (res != NSERROR_OK) {
155 break;
156 }
157 } else {
158 slen++;
159 if (slen > sizeof s) {
160 NSLOG(netsurf, INFO, "Overlength line\n");
161 slen = 0;
162 }
163 }
164
165 size--;
166 data++;
167 }
168 if (slen > 0) {
169 s[slen] = 0;
170 res = process_line(ht, s, slen);
171 }
172
173 return res;
174}
175
176/**
177 * adds key/value pairs to a hash from a compressed memory area
178 */
179static nserror
180hash_add_inline_gzip(struct hash_table *ht, const uint8_t *data, size_t size)
181{
182 nserror res;
183 int ret; /* zlib return value */
184 z_stream strm;
185 uint8_t s[LINE_BUFFER_SIZE]; /* line buffer */
186 size_t used = 0; /* number of bytes in buffer in use */
187 uint8_t *nl;
188
189 strm.zalloc = Z_NULL;
190 strm.zfree = Z_NULL;
191 strm.opaque = Z_NULL;
192
193 strm.next_in = (uint8_t *)data;
194 strm.avail_in = size;
195
196 ret = inflateInit2(&strm, 32 + MAX_WBITS);
197 if (ret != Z_OK) {
198 NSLOG(netsurf, INFO, "inflateInit returned %d", ret);
199 return NSERROR_INVALID;
200 }
201
202 do {
203 strm.next_out = s + used;
204 strm.avail_out = sizeof(s) - used;
205
206 ret = inflate(&strm, Z_NO_FLUSH);
207 if ((ret != Z_OK) && (ret != Z_STREAM_END)) {
208 break;
209 }
210
211 used = sizeof(s) - strm.avail_out;
212 while (used > 0) {
213 /* find nl */
214 for (nl = &s[0]; nl < &s[used]; nl++) {
215 if (*nl == '\n') {
216 break;
217 }
218 }
219 if (nl == &s[used]) {
220 /* no nl found */
221 break;
222 }
223 /* found newline */
224 *nl = 0; /* null terminate line */
225 res = process_line(ht, &s[0], nl - &s[0]);
226 if (res != NSERROR_OK) {
227 inflateEnd(&strm);
228 return res;
229 }
230
231 /* move data down */
232 memmove(&s[0], nl + 1, used - ((nl + 1) - &s[0]) );
233 used -= ((nl +1) - &s[0]);
234 }
235 if (used == sizeof(s)) {
236 /* entire buffer used and no newline */
237 NSLOG(netsurf, INFO, "Overlength line");
238 used = 0;
239 }
240 } while (ret != Z_STREAM_END);
241
242 inflateEnd(&strm);
243
244 if (ret != Z_STREAM_END) {
245 NSLOG(netsurf, INFO, "inflate returned %d", ret);
246 return NSERROR_INVALID;
247 }
248 return NSERROR_OK;
249
250}
251
252
253/* exported interface documented in utils/hashtable.h */
254struct hash_table *hash_create(unsigned int chains)
255{
256 struct hash_table *r = malloc(sizeof(struct hash_table));
257
258 if (r == NULL) {
259 NSLOG(netsurf, INFO, "Not enough memory for hash table.");
260 return NULL;
261 }
262
263 r->nchains = chains;
264 r->chain = calloc(chains, sizeof(struct hash_entry *));
265
266 if (r->chain == NULL) {
267 NSLOG(netsurf, INFO,
268 "Not enough memory for %d hash table chains.", chains);
269 free(r);
270 return NULL;
271 }
272
273 return r;
274}
275
276
277/* exported interface documented in utils/hashtable.h */
278void hash_destroy(struct hash_table *ht)
279{
280 unsigned int i;
281
282 if (ht == NULL)
283 return;
284
285 for (i = 0; i < ht->nchains; i++) {
286 if (ht->chain[i] != NULL) {
287 struct hash_entry *e = ht->chain[i];
288 while (e) {
289 struct hash_entry *n = e->next;
290 free(e->pairing);
291 free(e);
292 e = n;
293 }
294 }
295 }
296
297 free(ht->chain);
298 free(ht);
299}
300
301
302/* exported interface documented in utils/hashtable.h */
303bool hash_add(struct hash_table *ht, const char *key, const char *value)
304{
305 unsigned int h, c, v;
306 struct hash_entry *e;
307
308 if (ht == NULL || key == NULL || value == NULL)
309 return false;
310
311 e = malloc(sizeof(struct hash_entry));
312 if (e == NULL) {
313 NSLOG(netsurf, INFO, "Not enough memory for hash entry.");
314 return false;
315 }
316
317 h = hash_string_fnv(key, &(e->key_length));
318 c = h % ht->nchains;
319
320 v = strlen(value) ;
321 e->pairing = malloc(v + e->key_length + 2);
322 if (e->pairing == NULL) {
323 NSLOG(netsurf, INFO,
324 "Not enough memory for string duplication.");
325 free(e);
326 return false;
327 }
328 memcpy(e->pairing, key, e->key_length + 1);
329 memcpy(e->pairing + e->key_length + 1, value, v + 1);
330
331 e->next = ht->chain[c];
332 ht->chain[c] = e;
333
334 return true;
335}
336
337
338/* exported interface documented in utils/hashtable.h */
339const char *hash_get(struct hash_table *ht, const char *key)
340{
341 unsigned int h, c, key_length;
342 struct hash_entry *e;
343
344 if (ht == NULL || key == NULL)
345 return NULL;
346
347 h = hash_string_fnv(key, &key_length);
348 c = h % ht->nchains;
349
350 for (e = ht->chain[c]; e; e = e->next) {
351 if ((key_length == e->key_length) &&
352 (memcmp(key, e->pairing, key_length) == 0)) {
353 return e->pairing + key_length + 1;
354 }
355 }
356
357 return NULL;
358}
359
360
361
362/* exported interface documented in utils/hashtable.h */
363nserror hash_add_file(struct hash_table *ht, const char *path)
364{
365 nserror res = NSERROR_OK;
366 char s[LINE_BUFFER_SIZE]; /* line buffer */
367 gzFile fp; /* compressed file handle */
368
369 if (path == NULL) {
371 }
372
373 fp = gzopen(path, "r");
374 if (!fp) {
375 NSLOG(netsurf, INFO,
376 "Unable to open file \"%.100s\": %s", path,
377 strerror(errno));
378
379 return NSERROR_NOT_FOUND;
380 }
381
382 while (gzgets(fp, s, sizeof s)) {
383 int slen = strlen(s);
384 s[--slen] = 0; /* remove \n at end */
385
386 res = process_line(ht, (uint8_t *)s, slen);
387 if (res != NSERROR_OK) {
388 break;
389 }
390 }
391
392 gzclose(fp);
393
394 return res;
395}
396
397
398/* exported interface documented in utils/hashtable.h */
399nserror hash_add_inline(struct hash_table *ht, const uint8_t *data, size_t size)
400{
401 if ((data[0]==0x1f) && (data[1] == 0x8b)) {
402 /* gzip header detected */
403 return hash_add_inline_gzip(ht, data, size);
404 }
405 return hash_add_inline_plain(ht, data, size);
406}
nserror
Enumeration of error codes.
Definition: errors.h:29
@ NSERROR_NOT_FOUND
Requested item not found.
Definition: errors.h:34
@ NSERROR_BAD_PARAMETER
Bad Parameter.
Definition: errors.h:48
@ NSERROR_INVALID
Invalid data.
Definition: errors.h:49
@ NSERROR_OK
No error.
Definition: errors.h:30
struct hash_table * hash_create(unsigned int chains)
Create a new hash table.
Definition: hashtable.c:254
static unsigned int hash_string_fnv(const char *datum, unsigned int *len)
Hash a string, returning a 32bit value.
Definition: hashtable.c:65
bool hash_add(struct hash_table *ht, const char *key, const char *value)
Adds a key/value pair to a hash table.
Definition: hashtable.c:303
nserror hash_add_inline(struct hash_table *ht, const uint8_t *data, size_t size)
Add key/value pairs to a hash table with data from a memory buffer.
Definition: hashtable.c:399
nserror hash_add_file(struct hash_table *ht, const char *path)
Add key/value pairs to a hash table with data from a file.
Definition: hashtable.c:363
static nserror hash_add_inline_plain(struct hash_table *ht, const uint8_t *data, size_t size)
adds key/value pairs to a hash from a memory area
Definition: hashtable.c:141
static nserror hash_add_inline_gzip(struct hash_table *ht, const uint8_t *data, size_t size)
adds key/value pairs to a hash from a compressed memory area
Definition: hashtable.c:180
static nserror process_line(struct hash_table *hash, uint8_t *ln, int lnlen)
process a line of input.
Definition: hashtable.c:94
void hash_destroy(struct hash_table *ht)
Destroys a hash table.
Definition: hashtable.c:278
const char * hash_get(struct hash_table *ht, const char *key)
Looks up a the value associated with with a key from a specific hash table.
Definition: hashtable.c:339
#define LINE_BUFFER_SIZE
maximum length of line for file or inline add
Definition: hashtable.c:54
Interface to Write-Once hash table for string to string mapping.
#define NSLOG(catname, level, logmsg, args...)
Definition: log.h:116
Interface to utility string handling.
Definition: hashtable.c:42
struct hash_entry * next
next entry
Definition: hashtable.c:45
char * pairing
block containing 'key\0value\0'
Definition: hashtable.c:43
unsigned int key_length
length of key
Definition: hashtable.c:44
struct hash_entry ** chain
Definition: hashtable.c:50
unsigned int nchains
Definition: hashtable.c:49
static nserror path(const struct redraw_context *ctx, const plot_style_t *pstyle, const float *p, unsigned int n, const float transform[6])
Plots a path.
Definition: plot.c:821