1/* Hash table implementation.
2 *
3 * This file implements in memory hash tables with insert/del/replace/find/
4 * get-random-element operations. Hash tables will auto resize if needed
5 * tables of power of two in size are used, collisions are handled by
6 * chaining. See the source code for more information... :)
7 *
8 * Copyright (c) 2006-2010, Salvatore Sanfilippo <antirez at gmail dot com>
9 * All rights reserved.
10 *
11 * Redistribution and use in source and binary forms, with or without
12 * modification, are permitted provided that the following conditions are met:
13 *
14 * * Redistributions of source code must retain the above copyright notice,
15 * this list of conditions and the following disclaimer.
16 * * Redistributions in binary form must reproduce the above copyright
17 * notice, this list of conditions and the following disclaimer in the
18 * documentation and/or other materials provided with the distribution.
19 * * Neither the name of Redis nor the names of its contributors may be used
20 * to endorse or promote products derived from this software without
21 * specific prior written permission.
22 *
23 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
24 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
25 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
26 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
27 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
28 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
29 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
30 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
31 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
32 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
33 * POSSIBILITY OF SUCH DAMAGE.
34 */
35
36#include "fmacros.h"
37#include "alloc.h"
38#include <stdlib.h>
39#include <assert.h>
40#include <limits.h>
41#include "dict.h"
42
43/* -------------------------- private prototypes ---------------------------- */
44
45static int _dictExpandIfNeeded(dict *ht);
46static unsigned long _dictNextPower(unsigned long size);
47static int _dictKeyIndex(dict *ht, const void *key);
48static int _dictInit(dict *ht, dictType *type, void *privDataPtr);
49
50/* -------------------------- hash functions -------------------------------- */
51
52/* Generic hash function (a popular one from Bernstein).
53 * I tested a few and this was the best. */
54static unsigned int dictGenHashFunction(const unsigned char *buf, int len) {
55 unsigned int hash = 5381;
56
57 while (len--)
58 hash = ((hash << 5) + hash) + (*buf++); /* hash * 33 + c */
59 return hash;
60}
61
62/* ----------------------------- API implementation ------------------------- */
63
64/* Reset an hashtable already initialized with ht_init().
65 * NOTE: This function should only called by ht_destroy(). */
66static void _dictReset(dict *ht) {
67 ht->table = NULL;
68 ht->size = 0;
69 ht->sizemask = 0;
70 ht->used = 0;
71}
72
73/* Create a new hash table */
74static dict *dictCreate(dictType *type, void *privDataPtr) {
75 dict *ht = hi_malloc(sizeof(*ht));
76 if (ht == NULL)
77 return NULL;
78
79 _dictInit(ht,type,privDataPtr);
80 return ht;
81}
82
83/* Initialize the hash table */
84static int _dictInit(dict *ht, dictType *type, void *privDataPtr) {
85 _dictReset(ht);
86 ht->type = type;
87 ht->privdata = privDataPtr;
88 return DICT_OK;
89}
90
91/* Expand or create the hashtable */
92static int dictExpand(dict *ht, unsigned long size) {
93 dict n; /* the new hashtable */
94 unsigned long realsize = _dictNextPower(size), i;
95
96 /* the size is invalid if it is smaller than the number of
97 * elements already inside the hashtable */
98 if (ht->used > size)
99 return DICT_ERR;
100
101 _dictInit(&n, ht->type, ht->privdata);
102 n.size = realsize;
103 n.sizemask = realsize-1;
104 n.table = hi_calloc(realsize,sizeof(dictEntry*));
105 if (n.table == NULL)
106 return DICT_ERR;
107
108 /* Copy all the elements from the old to the new table:
109 * note that if the old hash table is empty ht->size is zero,
110 * so dictExpand just creates an hash table. */
111 n.used = ht->used;
112 for (i = 0; i < ht->size && ht->used > 0; i++) {
113 dictEntry *he, *nextHe;
114
115 if (ht->table[i] == NULL) continue;
116
117 /* For each hash entry on this slot... */
118 he = ht->table[i];
119 while(he) {
120 unsigned int h;
121
122 nextHe = he->next;
123 /* Get the new element index */
124 h = dictHashKey(ht, he->key) & n.sizemask;
125 he->next = n.table[h];
126 n.table[h] = he;
127 ht->used--;
128 /* Pass to the next element */
129 he = nextHe;
130 }
131 }
132 assert(ht->used == 0);
133 hi_free(ht->table);
134
135 /* Remap the new hashtable in the old */
136 *ht = n;
137 return DICT_OK;
138}
139
140/* Add an element to the target hash table */
141static int dictAdd(dict *ht, void *key, void *val) {
142 int index;
143 dictEntry *entry;
144
145 /* Get the index of the new element, or -1 if
146 * the element already exists. */
147 if ((index = _dictKeyIndex(ht, key)) == -1)
148 return DICT_ERR;
149
150 /* Allocates the memory and stores key */
151 entry = hi_malloc(sizeof(*entry));
152 if (entry == NULL)
153 return DICT_ERR;
154
155 entry->next = ht->table[index];
156 ht->table[index] = entry;
157
158 /* Set the hash entry fields. */
159 dictSetHashKey(ht, entry, key);
160 dictSetHashVal(ht, entry, val);
161 ht->used++;
162 return DICT_OK;
163}
164
165/* Add an element, discarding the old if the key already exists.
166 * Return 1 if the key was added from scratch, 0 if there was already an
167 * element with such key and dictReplace() just performed a value update
168 * operation. */
169static int dictReplace(dict *ht, void *key, void *val) {
170 dictEntry *entry, auxentry;
171
172 /* Try to add the element. If the key
173 * does not exists dictAdd will succeed. */
174 if (dictAdd(ht, key, val) == DICT_OK)
175 return 1;
176 /* It already exists, get the entry */
177 entry = dictFind(ht, key);
178 if (entry == NULL)
179 return 0;
180
181 /* Free the old value and set the new one */
182 /* Set the new value and free the old one. Note that it is important
183 * to do that in this order, as the value may just be exactly the same
184 * as the previous one. In this context, think to reference counting,
185 * you want to increment (set), and then decrement (free), and not the
186 * reverse. */
187 auxentry = *entry;
188 dictSetHashVal(ht, entry, val);
189 dictFreeEntryVal(ht, &auxentry);
190 return 0;
191}
192
193/* Search and remove an element */
194static int dictDelete(dict *ht, const void *key) {
195 unsigned int h;
196 dictEntry *de, *prevde;
197
198 if (ht->size == 0)
199 return DICT_ERR;
200 h = dictHashKey(ht, key) & ht->sizemask;
201 de = ht->table[h];
202
203 prevde = NULL;
204 while(de) {
205 if (dictCompareHashKeys(ht,key,de->key)) {
206 /* Unlink the element from the list */
207 if (prevde)
208 prevde->next = de->next;
209 else
210 ht->table[h] = de->next;
211
212 dictFreeEntryKey(ht,de);
213 dictFreeEntryVal(ht,de);
214 hi_free(de);
215 ht->used--;
216 return DICT_OK;
217 }
218 prevde = de;
219 de = de->next;
220 }
221 return DICT_ERR; /* not found */
222}
223
224/* Destroy an entire hash table */
225static int _dictClear(dict *ht) {
226 unsigned long i;
227
228 /* Free all the elements */
229 for (i = 0; i < ht->size && ht->used > 0; i++) {
230 dictEntry *he, *nextHe;
231
232 if ((he = ht->table[i]) == NULL) continue;
233 while(he) {
234 nextHe = he->next;
235 dictFreeEntryKey(ht, he);
236 dictFreeEntryVal(ht, he);
237 hi_free(he);
238 ht->used--;
239 he = nextHe;
240 }
241 }
242 /* Free the table and the allocated cache structure */
243 hi_free(ht->table);
244 /* Re-initialize the table */
245 _dictReset(ht);
246 return DICT_OK; /* never fails */
247}
248
249/* Clear & Release the hash table */
250static void dictRelease(dict *ht) {
251 _dictClear(ht);
252 hi_free(ht);
253}
254
255static dictEntry *dictFind(dict *ht, const void *key) {
256 dictEntry *he;
257 unsigned int h;
258
259 if (ht->size == 0) return NULL;
260 h = dictHashKey(ht, key) & ht->sizemask;
261 he = ht->table[h];
262 while(he) {
263 if (dictCompareHashKeys(ht, key, he->key))
264 return he;
265 he = he->next;
266 }
267 return NULL;
268}
269
270static void dictInitIterator(dictIterator *iter, dict *ht) {
271 iter->ht = ht;
272 iter->index = -1;
273 iter->entry = NULL;
274 iter->nextEntry = NULL;
275}
276
277static dictEntry *dictNext(dictIterator *iter) {
278 while (1) {
279 if (iter->entry == NULL) {
280 iter->index++;
281 if (iter->index >=
282 (signed)iter->ht->size) break;
283 iter->entry = iter->ht->table[iter->index];
284 } else {
285 iter->entry = iter->nextEntry;
286 }
287 if (iter->entry) {
288 /* We need to save the 'next' here, the iterator user
289 * may delete the entry we are returning. */
290 iter->nextEntry = iter->entry->next;
291 return iter->entry;
292 }
293 }
294 return NULL;
295}
296
297/* ------------------------- private functions ------------------------------ */
298
299/* Expand the hash table if needed */
300static int _dictExpandIfNeeded(dict *ht) {
301 /* If the hash table is empty expand it to the initial size,
302 * if the table is "full" double its size. */
303 if (ht->size == 0)
304 return dictExpand(ht, DICT_HT_INITIAL_SIZE);
305 if (ht->used == ht->size)
306 return dictExpand(ht, ht->size*2);
307 return DICT_OK;
308}
309
310/* Our hash table capability is a power of two */
311static unsigned long _dictNextPower(unsigned long size) {
312 unsigned long i = DICT_HT_INITIAL_SIZE;
313
314 if (size >= LONG_MAX) return LONG_MAX;
315 while(1) {
316 if (i >= size)
317 return i;
318 i *= 2;
319 }
320}
321
322/* Returns the index of a free slot that can be populated with
323 * an hash entry for the given 'key'.
324 * If the key already exists, -1 is returned. */
325static int _dictKeyIndex(dict *ht, const void *key) {
326 unsigned int h;
327 dictEntry *he;
328
329 /* Expand the hashtable if needed */
330 if (_dictExpandIfNeeded(ht) == DICT_ERR)
331 return -1;
332 /* Compute the key hash value */
333 h = dictHashKey(ht, key) & ht->sizemask;
334 /* Search if this slot does not already contain the given key */
335 he = ht->table[h];
336 while(he) {
337 if (dictCompareHashKeys(ht, key, he->key))
338 return -1;
339 he = he->next;
340 }
341 return h;
342}
343
344