summaryrefslogtreecommitdiff
path: root/utils/hashtable.c
blob: 3a1711da0bd52552b437e767164d76c9d2d521c4 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
/*
 * Copyright 2006 Rob Kendrick <rjek@rjek.com>
 * Copyright 2006 Richard Wilson <info@tinct.net>
 *
 * This file is part of NetSurf, http://www.netsurf-browser.org/
 *
 * NetSurf is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; version 2 of the License.
 *
 * NetSurf is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program.  If not, see <http://www.gnu.org/licenses/>.
 */

/**
 * \file
 * Write-Once hash table for string to string mappings.
 *
 * This implementation is unit tested, if you make changes please
 * ensure the tests continute to pass and if possible, through
 * valgrind to make sure there are no memory leaks or invalid memory
 * accesses.  If you add new functionality, please include a test for
 * it that has good coverage along side the other tests.
 */

#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#include "utils/hashtable.h"
#include "utils/log.h"


struct hash_entry {
	char *pairing;		 /**< block containing 'key\0value\0' */
	unsigned int key_length; /**< length of key */
	struct hash_entry *next; /**< next entry */
};

struct hash_table {
	unsigned int nchains;
	struct hash_entry **chain;
};


/**
 * Hash a string, returning a 32bit value.  The hash algorithm used is
 * Fowler Noll Vo - a very fast and simple hash, ideal for short strings.
 * See http://en.wikipedia.org/wiki/Fowler_Noll_Vo_hash for more details.
 *
 * \param  datum   The string to hash.
 * \param  len	   Pointer to unsigned integer to record datum's length in.
 * \return The calculated hash value for the datum.
 */
static inline unsigned int hash_string_fnv(const char *datum, unsigned int *len)
{
	unsigned int z = 0x811c9dc5;
	const char *start = datum;
	*len = 0;

	if (datum == NULL)
		return 0;

	while (*datum) {
		z *= 0x01000193;
		z ^= *datum++;
	}
	*len = datum - start;

	return z;
}


/* exported interface documented in utils/hashtable.h */
struct hash_table *hash_create(unsigned int chains)
{
	struct hash_table *r = malloc(sizeof(struct hash_table));

	if (r == NULL) {
		NSLOG(netsurf, INFO, "Not enough memory for hash table.");
		return NULL;
	}

	r->nchains = chains;
	r->chain = calloc(chains, sizeof(struct hash_entry *));

	if (r->chain == NULL) {
		NSLOG(netsurf, INFO,
		      "Not enough memory for %d hash table chains.", chains);
		free(r);
		return NULL;
	}

	return r;
}


/* exported interface documented in utils/hashtable.h */
void hash_destroy(struct hash_table *ht)
{
	unsigned int i;

	if (ht == NULL)
		return;

	for (i = 0; i < ht->nchains; i++) {
		if (ht->chain[i] != NULL) {
			struct hash_entry *e = ht->chain[i];
			while (e) {
				struct hash_entry *n = e->next;
				free(e->pairing);
				free(e);
				e = n;
			}
		}
	}

	free(ht->chain);
	free(ht);
}


/* exported interface documented in utils/hashtable.h */
bool hash_add(struct hash_table *ht, const char *key, const char *value)
{
	unsigned int h, c, v;
	struct hash_entry *e;

	if (ht == NULL || key == NULL || value == NULL)
		return false;

	e = malloc(sizeof(struct hash_entry));
	if (e == NULL) {
		NSLOG(netsurf, INFO, "Not enough memory for hash entry.");
		return false;
	}

	h = hash_string_fnv(key, &(e->key_length));
	c = h % ht->nchains;

	v = strlen(value) ;
	e->pairing = malloc(v + e->key_length + 2);
	if (e->pairing == NULL) {
		NSLOG(netsurf, INFO,
		      "Not enough memory for string duplication.");
		free(e);
		return false;
	}
	memcpy(e->pairing, key, e->key_length + 1);
	memcpy(e->pairing + e->key_length + 1, value, v + 1);

	e->next = ht->chain[c];
	ht->chain[c] = e;

	return true;
}


/* exported interface documented in utils/hashtable.h */
const char *hash_get(struct hash_table *ht, const char *key)
{
	unsigned int h, c, key_length;
	struct hash_entry *e;

	if (ht == NULL || key == NULL)
		return NULL;

	h = hash_string_fnv(key, &key_length);
	c = h % ht->nchains;

	for (e = ht->chain[c]; e; e = e->next)
		if ((key_length == e->key_length) &&
				(memcmp(key, e->pairing, key_length) == 0))
			return e->pairing + key_length + 1;

	return NULL;
}