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
45typedef struct dictEntry {
46 void *key;
47 void *val;
48 struct dictEntry *next;
49} dictEntry;
50
51typedef 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
60typedef 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
69typedef 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 */
114static unsigned int dictGenHashFunction(const unsigned char *buf, int len);
115static dict *dictCreate(dictType *type, void *privDataPtr);
116static int dictExpand(dict *ht, unsigned long size);
117static int dictAdd(dict *ht, void *key, void *val);
118static int dictReplace(dict *ht, void *key, void *val);
119static int dictDelete(dict *ht, const void *key);
120static void dictRelease(dict *ht);
121static dictEntry * dictFind(dict *ht, const void *key);
122static void dictInitIterator(dictIterator *iter, dict *ht);
123static dictEntry *dictNext(dictIterator *iter);
124
125#endif /* __DICT_H */
126