1 /* Hash table implementation.
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... :)
8 * Copyright (c) 2006-2010, Salvatore Sanfilippo <antirez at gmail dot com>
11 * Redistribution and use in source and binary forms, with or without
12 * modification, are permitted provided that the following conditions are met:
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.
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.
42 /* -------------------------- private prototypes ---------------------------- */
44 static int _dictExpandIfNeeded(dict *ht);
45 static unsigned long _dictNextPower(unsigned long size);
46 static int _dictKeyIndex(dict *ht, const void *key);
47 static int _dictInit(dict *ht, dictType *type, void *privDataPtr);
49 /* -------------------------- hash functions -------------------------------- */
51 /* Generic hash function (a popular one from Bernstein).
52 * I tested a few and this was the best. */
53 static unsigned int dictGenHashFunction(const unsigned char *buf, int len) {
54 unsigned int hash = 5381;
57 hash = ((hash << 5) + hash) + (*buf++); /* hash * 33 + c */
61 /* ----------------------------- API implementation ------------------------- */
63 /* Reset an hashtable already initialized with ht_init().
64 * NOTE: This function should only called by ht_destroy(). */
65 static void _dictReset(dict *ht) {
72 /* Create a new hash table */
73 static dict *dictCreate(dictType *type, void *privDataPtr) {
74 dict *ht = malloc(sizeof(*ht));
75 _dictInit(ht,type,privDataPtr);
79 /* Initialize the hash table */
80 static int _dictInit(dict *ht, dictType *type, void *privDataPtr) {
83 ht->privdata = privDataPtr;
87 /* Expand or create the hashtable */
88 static int dictExpand(dict *ht, unsigned long size) {
89 dict n; /* the new hashtable */
90 unsigned long realsize = _dictNextPower(size), i;
92 /* the size is invalid if it is smaller than the number of
93 * elements already inside the hashtable */
97 _dictInit(&n, ht->type, ht->privdata);
99 n.sizemask = realsize-1;
100 n.table = calloc(realsize,sizeof(dictEntry*));
102 /* Copy all the elements from the old to the new table:
103 * note that if the old hash table is empty ht->size is zero,
104 * so dictExpand just creates an hash table. */
106 for (i = 0; i < ht->size && ht->used > 0; i++) {
107 dictEntry *he, *nextHe;
109 if (ht->table[i] == NULL) continue;
111 /* For each hash entry on this slot... */
117 /* Get the new element index */
118 h = dictHashKey(ht, he->key) & n.sizemask;
119 he->next = n.table[h];
122 /* Pass to the next element */
126 assert(ht->used == 0);
129 /* Remap the new hashtable in the old */
134 /* Add an element to the target hash table */
135 static int dictAdd(dict *ht, void *key, void *val) {
139 /* Get the index of the new element, or -1 if
140 * the element already exists. */
141 if ((index = _dictKeyIndex(ht, key)) == -1)
144 /* Allocates the memory and stores key */
145 entry = malloc(sizeof(*entry));
146 entry->next = ht->table[index];
147 ht->table[index] = entry;
149 /* Set the hash entry fields. */
150 dictSetHashKey(ht, entry, key);
151 dictSetHashVal(ht, entry, val);
156 /* Add an element, discarding the old if the key already exists.
157 * Return 1 if the key was added from scratch, 0 if there was already an
158 * element with such key and dictReplace() just performed a value update
160 static int dictReplace(dict *ht, void *key, void *val) {
161 dictEntry *entry, auxentry;
163 /* Try to add the element. If the key
164 * does not exists dictAdd will suceed. */
165 if (dictAdd(ht, key, val) == DICT_OK)
167 /* It already exists, get the entry */
168 entry = dictFind(ht, key);
169 /* Free the old value and set the new one */
170 /* Set the new value and free the old one. Note that it is important
171 * to do that in this order, as the value may just be exactly the same
172 * as the previous one. In this context, think to reference counting,
173 * you want to increment (set), and then decrement (free), and not the
176 dictSetHashVal(ht, entry, val);
177 dictFreeEntryVal(ht, &auxentry);
181 /* Search and remove an element */
182 static int dictDelete(dict *ht, const void *key) {
184 dictEntry *de, *prevde;
188 h = dictHashKey(ht, key) & ht->sizemask;
193 if (dictCompareHashKeys(ht,key,de->key)) {
194 /* Unlink the element from the list */
196 prevde->next = de->next;
198 ht->table[h] = de->next;
200 dictFreeEntryKey(ht,de);
201 dictFreeEntryVal(ht,de);
209 return DICT_ERR; /* not found */
212 /* Destroy an entire hash table */
213 static int _dictClear(dict *ht) {
216 /* Free all the elements */
217 for (i = 0; i < ht->size && ht->used > 0; i++) {
218 dictEntry *he, *nextHe;
220 if ((he = ht->table[i]) == NULL) continue;
223 dictFreeEntryKey(ht, he);
224 dictFreeEntryVal(ht, he);
230 /* Free the table and the allocated cache structure */
232 /* Re-initialize the table */
234 return DICT_OK; /* never fails */
237 /* Clear & Release the hash table */
238 static void dictRelease(dict *ht) {
243 static dictEntry *dictFind(dict *ht, const void *key) {
247 if (ht->size == 0) return NULL;
248 h = dictHashKey(ht, key) & ht->sizemask;
251 if (dictCompareHashKeys(ht, key, he->key))
258 static dictIterator *dictGetIterator(dict *ht) {
259 dictIterator *iter = malloc(sizeof(*iter));
264 iter->nextEntry = NULL;
268 static dictEntry *dictNext(dictIterator *iter) {
270 if (iter->entry == NULL) {
273 (signed)iter->ht->size) break;
274 iter->entry = iter->ht->table[iter->index];
276 iter->entry = iter->nextEntry;
279 /* We need to save the 'next' here, the iterator user
280 * may delete the entry we are returning. */
281 iter->nextEntry = iter->entry->next;
288 static void dictReleaseIterator(dictIterator *iter) {
292 /* ------------------------- private functions ------------------------------ */
294 /* Expand the hash table if needed */
295 static int _dictExpandIfNeeded(dict *ht) {
296 /* If the hash table is empty expand it to the intial size,
297 * if the table is "full" dobule its size. */
299 return dictExpand(ht, DICT_HT_INITIAL_SIZE);
300 if (ht->used == ht->size)
301 return dictExpand(ht, ht->size*2);
305 /* Our hash table capability is a power of two */
306 static unsigned long _dictNextPower(unsigned long size) {
307 unsigned long i = DICT_HT_INITIAL_SIZE;
309 if (size >= LONG_MAX) return LONG_MAX;
317 /* Returns the index of a free slot that can be populated with
318 * an hash entry for the given 'key'.
319 * If the key already exists, -1 is returned. */
320 static int _dictKeyIndex(dict *ht, const void *key) {
324 /* Expand the hashtable if needed */
325 if (_dictExpandIfNeeded(ht) == DICT_ERR)
327 /* Compute the key hash value */
328 h = dictHashKey(ht, key) & ht->sizemask;
329 /* Search if this slot does not already contain the given key */
332 if (dictCompareHashKeys(ht, key, he->key))