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 #ifndef __DICT_H
37 #define __DICT_H
38 
39 #define DICT_OK 0
40 #define DICT_ERR 1
41 
42 /* Unused arguments generate annoying warnings... */
43 #define DICT_NOTUSED(V) ((void) V)
44 
45 typedef struct dictEntry {
46     void *key;
47     void *val;
48     struct dictEntry *next;
49 } dictEntry;
50 
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);
58 } dictType;
59 
60 typedef struct dict {
61     dictEntry **table;
62     dictType *type;
63     unsigned long size;
64     unsigned long sizemask;
65     unsigned long used;
66     void *privdata;
67 } dict;
68 
69 typedef struct dictIterator {
70     dict *ht;
71     int index;
72     dictEntry *entry, *nextEntry;
73 } dictIterator;
74 
75 /* This is the initial size of every hash table */
76 #define DICT_HT_INITIAL_SIZE     4
77 
78 /* ------------------------------- Macros ------------------------------------*/
79 #define dictFreeEntryVal(ht, entry) \
80     if ((ht)->type->valDestructor) \
81         (ht)->type->valDestructor((ht)->privdata, (entry)->val)
82 
83 #define dictSetHashVal(ht, entry, _val_) do { \
84     if ((ht)->type->valDup) \
85         entry->val = (ht)->type->valDup((ht)->privdata, _val_); \
86     else \
87         entry->val = (_val_); \
88 } while(0)
89 
90 #define dictFreeEntryKey(ht, entry) \
91     if ((ht)->type->keyDestructor) \
92         (ht)->type->keyDestructor((ht)->privdata, (entry)->key)
93 
94 #define dictSetHashKey(ht, entry, _key_) do { \
95     if ((ht)->type->keyDup) \
96         entry->key = (ht)->type->keyDup((ht)->privdata, _key_); \
97     else \
98         entry->key = (_key_); \
99 } while(0)
100 
101 #define dictCompareHashKeys(ht, key1, key2) \
102     (((ht)->type->keyCompare) ? \
103         (ht)->type->keyCompare((ht)->privdata, key1, key2) : \
104         (key1) == (key2))
105 
106 #define dictHashKey(ht, key) (ht)->type->hashFunction(key)
107 
108 #define dictGetEntryKey(he) ((he)->key)
109 #define dictGetEntryVal(he) ((he)->val)
110 #define dictSlots(ht) ((ht)->size)
111 #define dictSize(ht) ((ht)->used)
112 
113 /* API */
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);
125 
126 #endif /* __DICT_H */
127