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 /* Unused arguments generate annoying warnings... */
43 #define DICT_NOTUSED(V) ((void) V)
45 typedef struct dictEntry {
48 struct dictEntry *next;
51 typedef struct dictType {
52 unsigned int (*hashFunction)(const void *key);
53 void *(*keyDup)(void *privdata, const void *key);
54 void *(*valDup)(void *privdata, const void *obj);
55 int (*keyCompare)(void *privdata, const void *key1, const void *key2);
56 void (*keyDestructor)(void *privdata, void *key);
57 void (*valDestructor)(void *privdata, void *obj);
64 unsigned long sizemask;
69 typedef struct dictIterator {
72 dictEntry *entry, *nextEntry;
75 /* This is the initial size of every hash table */
76 #define DICT_HT_INITIAL_SIZE 4
78 /* ------------------------------- Macros ------------------------------------*/
79 #define dictFreeEntryVal(ht, entry) \
80 if ((ht)->type->valDestructor) \
81 (ht)->type->valDestructor((ht)->privdata, (entry)->val)
83 #define dictSetHashVal(ht, entry, _val_) do { \
84 if ((ht)->type->valDup) \
85 entry->val = (ht)->type->valDup((ht)->privdata, _val_); \
87 entry->val = (_val_); \
90 #define dictFreeEntryKey(ht, entry) \
91 if ((ht)->type->keyDestructor) \
92 (ht)->type->keyDestructor((ht)->privdata, (entry)->key)
94 #define dictSetHashKey(ht, entry, _key_) do { \
95 if ((ht)->type->keyDup) \
96 entry->key = (ht)->type->keyDup((ht)->privdata, _key_); \
98 entry->key = (_key_); \
101 #define dictCompareHashKeys(ht, key1, key2) \
102 (((ht)->type->keyCompare) ? \
103 (ht)->type->keyCompare((ht)->privdata, key1, key2) : \
106 #define dictHashKey(ht, key) (ht)->type->hashFunction(key)
108 #define dictGetEntryKey(he) ((he)->key)
109 #define dictGetEntryVal(he) ((he)->val)
110 #define dictSlots(ht) ((ht)->size)
111 #define dictSize(ht) ((ht)->used)
114 static unsigned int dictGenHashFunction(const unsigned char *buf, int len);
115 static dict *dictCreate(dictType *type, void *privDataPtr);
116 static int dictExpand(dict *ht, unsigned long size);
117 static int dictAdd(dict *ht, void *key, void *val);
118 static int dictReplace(dict *ht, void *key, void *val);
119 static int dictDelete(dict *ht, const void *key);
120 static void dictRelease(dict *ht);
121 static dictEntry * dictFind(dict *ht, const void *key);
122 static dictIterator *dictGetIterator(dict *ht);
123 static dictEntry *dictNext(dictIterator *iter);
124 static void dictReleaseIterator(dictIterator *iter);
126 #endif /* __DICT_H */