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
45 static int _dictExpandIfNeeded(dict *ht);
46 static unsigned long _dictNextPower(unsigned long size);
47 static int _dictKeyIndex(dict *ht, const void *key);
48 static 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. */
dictGenHashFunction(const unsigned char * buf,int len)54 static 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(). */
_dictReset(dict * ht)66 static 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 */
dictCreate(dictType * type,void * privDataPtr)74 static dict *dictCreate(dictType *type, void *privDataPtr) {
75 dict *ht = hi_malloc(sizeof(*ht));
76 _dictInit(ht,type,privDataPtr);
77 return ht;
78 }
79
80 /* Initialize the hash table */
_dictInit(dict * ht,dictType * type,void * privDataPtr)81 static int _dictInit(dict *ht, dictType *type, void *privDataPtr) {
82 _dictReset(ht);
83 ht->type = type;
84 ht->privdata = privDataPtr;
85 return DICT_OK;
86 }
87
88 /* Expand or create the hashtable */
dictExpand(dict * ht,unsigned long size)89 static int dictExpand(dict *ht, unsigned long size) {
90 dict n; /* the new hashtable */
91 unsigned long realsize = _dictNextPower(size), i;
92
93 /* the size is invalid if it is smaller than the number of
94 * elements already inside the hashtable */
95 if (ht->used > size)
96 return DICT_ERR;
97
98 _dictInit(&n, ht->type, ht->privdata);
99 n.size = realsize;
100 n.sizemask = realsize-1;
101 n.table = calloc(realsize,sizeof(dictEntry*));
102
103 /* Copy all the elements from the old to the new table:
104 * note that if the old hash table is empty ht->size is zero,
105 * so dictExpand just creates an hash table. */
106 n.used = ht->used;
107 for (i = 0; i < ht->size && ht->used > 0; i++) {
108 dictEntry *he, *nextHe;
109
110 if (ht->table[i] == NULL) continue;
111
112 /* For each hash entry on this slot... */
113 he = ht->table[i];
114 while(he) {
115 unsigned int h;
116
117 nextHe = he->next;
118 /* Get the new element index */
119 h = dictHashKey(ht, he->key) & n.sizemask;
120 he->next = n.table[h];
121 n.table[h] = he;
122 ht->used--;
123 /* Pass to the next element */
124 he = nextHe;
125 }
126 }
127 assert(ht->used == 0);
128 free(ht->table);
129
130 /* Remap the new hashtable in the old */
131 *ht = n;
132 return DICT_OK;
133 }
134
135 /* Add an element to the target hash table */
dictAdd(dict * ht,void * key,void * val)136 static int dictAdd(dict *ht, void *key, void *val) {
137 int index;
138 dictEntry *entry;
139
140 /* Get the index of the new element, or -1 if
141 * the element already exists. */
142 if ((index = _dictKeyIndex(ht, key)) == -1)
143 return DICT_ERR;
144
145 /* Allocates the memory and stores key */
146 entry = hi_malloc(sizeof(*entry));
147 entry->next = ht->table[index];
148 ht->table[index] = entry;
149
150 /* Set the hash entry fields. */
151 dictSetHashKey(ht, entry, key);
152 dictSetHashVal(ht, entry, val);
153 ht->used++;
154 return DICT_OK;
155 }
156
157 /* Add an element, discarding the old if the key already exists.
158 * Return 1 if the key was added from scratch, 0 if there was already an
159 * element with such key and dictReplace() just performed a value update
160 * operation. */
dictReplace(dict * ht,void * key,void * val)161 static int dictReplace(dict *ht, void *key, void *val) {
162 dictEntry *entry, auxentry;
163
164 /* Try to add the element. If the key
165 * does not exists dictAdd will succeed. */
166 if (dictAdd(ht, key, val) == DICT_OK)
167 return 1;
168 /* It already exists, get the entry */
169 entry = dictFind(ht, key);
170 /* Free the old value and set the new one */
171 /* Set the new value and free the old one. Note that it is important
172 * to do that in this order, as the value may just be exactly the same
173 * as the previous one. In this context, think to reference counting,
174 * you want to increment (set), and then decrement (free), and not the
175 * reverse. */
176 auxentry = *entry;
177 dictSetHashVal(ht, entry, val);
178 dictFreeEntryVal(ht, &auxentry);
179 return 0;
180 }
181
182 /* Search and remove an element */
dictDelete(dict * ht,const void * key)183 static int dictDelete(dict *ht, const void *key) {
184 unsigned int h;
185 dictEntry *de, *prevde;
186
187 if (ht->size == 0)
188 return DICT_ERR;
189 h = dictHashKey(ht, key) & ht->sizemask;
190 de = ht->table[h];
191
192 prevde = NULL;
193 while(de) {
194 if (dictCompareHashKeys(ht,key,de->key)) {
195 /* Unlink the element from the list */
196 if (prevde)
197 prevde->next = de->next;
198 else
199 ht->table[h] = de->next;
200
201 dictFreeEntryKey(ht,de);
202 dictFreeEntryVal(ht,de);
203 free(de);
204 ht->used--;
205 return DICT_OK;
206 }
207 prevde = de;
208 de = de->next;
209 }
210 return DICT_ERR; /* not found */
211 }
212
213 /* Destroy an entire hash table */
_dictClear(dict * ht)214 static int _dictClear(dict *ht) {
215 unsigned long i;
216
217 /* Free all the elements */
218 for (i = 0; i < ht->size && ht->used > 0; i++) {
219 dictEntry *he, *nextHe;
220
221 if ((he = ht->table[i]) == NULL) continue;
222 while(he) {
223 nextHe = he->next;
224 dictFreeEntryKey(ht, he);
225 dictFreeEntryVal(ht, he);
226 free(he);
227 ht->used--;
228 he = nextHe;
229 }
230 }
231 /* Free the table and the allocated cache structure */
232 free(ht->table);
233 /* Re-initialize the table */
234 _dictReset(ht);
235 return DICT_OK; /* never fails */
236 }
237
238 /* Clear & Release the hash table */
dictRelease(dict * ht)239 static void dictRelease(dict *ht) {
240 _dictClear(ht);
241 free(ht);
242 }
243
dictFind(dict * ht,const void * key)244 static dictEntry *dictFind(dict *ht, const void *key) {
245 dictEntry *he;
246 unsigned int h;
247
248 if (ht->size == 0) return NULL;
249 h = dictHashKey(ht, key) & ht->sizemask;
250 he = ht->table[h];
251 while(he) {
252 if (dictCompareHashKeys(ht, key, he->key))
253 return he;
254 he = he->next;
255 }
256 return NULL;
257 }
258
dictGetIterator(dict * ht)259 static dictIterator *dictGetIterator(dict *ht) {
260 dictIterator *iter = hi_malloc(sizeof(*iter));
261
262 iter->ht = ht;
263 iter->index = -1;
264 iter->entry = NULL;
265 iter->nextEntry = NULL;
266 return iter;
267 }
268
dictNext(dictIterator * iter)269 static dictEntry *dictNext(dictIterator *iter) {
270 while (1) {
271 if (iter->entry == NULL) {
272 iter->index++;
273 if (iter->index >=
274 (signed)iter->ht->size) break;
275 iter->entry = iter->ht->table[iter->index];
276 } else {
277 iter->entry = iter->nextEntry;
278 }
279 if (iter->entry) {
280 /* We need to save the 'next' here, the iterator user
281 * may delete the entry we are returning. */
282 iter->nextEntry = iter->entry->next;
283 return iter->entry;
284 }
285 }
286 return NULL;
287 }
288
dictReleaseIterator(dictIterator * iter)289 static void dictReleaseIterator(dictIterator *iter) {
290 free(iter);
291 }
292
293 /* ------------------------- private functions ------------------------------ */
294
295 /* Expand the hash table if needed */
_dictExpandIfNeeded(dict * ht)296 static int _dictExpandIfNeeded(dict *ht) {
297 /* If the hash table is empty expand it to the initial size,
298 * if the table is "full" dobule its size. */
299 if (ht->size == 0)
300 return dictExpand(ht, DICT_HT_INITIAL_SIZE);
301 if (ht->used == ht->size)
302 return dictExpand(ht, ht->size*2);
303 return DICT_OK;
304 }
305
306 /* Our hash table capability is a power of two */
_dictNextPower(unsigned long size)307 static unsigned long _dictNextPower(unsigned long size) {
308 unsigned long i = DICT_HT_INITIAL_SIZE;
309
310 if (size >= LONG_MAX) return LONG_MAX;
311 while(1) {
312 if (i >= size)
313 return i;
314 i *= 2;
315 }
316 }
317
318 /* Returns the index of a free slot that can be populated with
319 * an hash entry for the given 'key'.
320 * If the key already exists, -1 is returned. */
_dictKeyIndex(dict * ht,const void * key)321 static int _dictKeyIndex(dict *ht, const void *key) {
322 unsigned int h;
323 dictEntry *he;
324
325 /* Expand the hashtable if needed */
326 if (_dictExpandIfNeeded(ht) == DICT_ERR)
327 return -1;
328 /* Compute the key hash value */
329 h = dictHashKey(ht, key) & ht->sizemask;
330 /* Search if this slot does not already contain the given key */
331 he = ht->table[h];
332 while(he) {
333 if (dictCompareHashKeys(ht, key, he->key))
334 return -1;
335 he = he->next;
336 }
337 return h;
338 }
339
340