ed9b544e |
1 | /* Hash Tables 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 | * |
12d090d2 |
8 | * Copyright (c) 2006-2010, Salvatore Sanfilippo <antirez at gmail dot com> |
ed9b544e |
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 | |
5413c40d |
60 | /* This is our hash table structure. Every dictionary has two of this as we |
61 | * implement incremental rehashing, for the old to the new table. */ |
62 | typedef struct dictht { |
ed9b544e |
63 | dictEntry **table; |
f2923bec |
64 | unsigned long size; |
65 | unsigned long sizemask; |
66 | unsigned long used; |
5413c40d |
67 | } dictht; |
68 | |
69 | typedef struct dict { |
70 | dictType *type; |
ed9b544e |
71 | void *privdata; |
5413c40d |
72 | dictht ht[2]; |
73 | int rehashidx; /* rehashing not in progress if rehashidx == -1 */ |
74 | int iterators; /* number of iterators currently running */ |
ed9b544e |
75 | } dict; |
76 | |
77 | typedef struct dictIterator { |
5413c40d |
78 | dict *d; |
79 | int table; |
ed9b544e |
80 | int index; |
81 | dictEntry *entry, *nextEntry; |
82 | } dictIterator; |
83 | |
84 | /* This is the initial size of every hash table */ |
12fea928 |
85 | #define DICT_HT_INITIAL_SIZE 4 |
ed9b544e |
86 | |
87 | /* ------------------------------- Macros ------------------------------------*/ |
5413c40d |
88 | #define dictFreeEntryVal(d, entry) \ |
89 | if ((d)->type->valDestructor) \ |
90 | (d)->type->valDestructor((d)->privdata, (entry)->val) |
ed9b544e |
91 | |
5413c40d |
92 | #define dictSetHashVal(d, entry, _val_) do { \ |
93 | if ((d)->type->valDup) \ |
94 | entry->val = (d)->type->valDup((d)->privdata, _val_); \ |
ed9b544e |
95 | else \ |
96 | entry->val = (_val_); \ |
97 | } while(0) |
98 | |
5413c40d |
99 | #define dictFreeEntryKey(d, entry) \ |
100 | if ((d)->type->keyDestructor) \ |
101 | (d)->type->keyDestructor((d)->privdata, (entry)->key) |
ed9b544e |
102 | |
5413c40d |
103 | #define dictSetHashKey(d, entry, _key_) do { \ |
104 | if ((d)->type->keyDup) \ |
105 | entry->key = (d)->type->keyDup((d)->privdata, _key_); \ |
ed9b544e |
106 | else \ |
107 | entry->key = (_key_); \ |
108 | } while(0) |
109 | |
5413c40d |
110 | #define dictCompareHashKeys(d, key1, key2) \ |
111 | (((d)->type->keyCompare) ? \ |
112 | (d)->type->keyCompare((d)->privdata, key1, key2) : \ |
ed9b544e |
113 | (key1) == (key2)) |
114 | |
5413c40d |
115 | #define dictHashKey(d, key) (d)->type->hashFunction(key) |
ed9b544e |
116 | |
117 | #define dictGetEntryKey(he) ((he)->key) |
118 | #define dictGetEntryVal(he) ((he)->val) |
5413c40d |
119 | #define dictSlots(d) ((d)->ht[0].size+(d)->ht[1].size) |
120 | #define dictSize(d) ((d)->ht[0].used+(d)->ht[1].used) |
121 | #define dictIsRehashing(ht) ((ht)->rehashidx != -1) |
ed9b544e |
122 | |
123 | /* API */ |
124 | dict *dictCreate(dictType *type, void *privDataPtr); |
8ca3e9d1 |
125 | int dictExpand(dict *d, unsigned long size); |
126 | int dictAdd(dict *d, void *key, void *val); |
127 | int dictReplace(dict *d, void *key, void *val); |
128 | int dictDelete(dict *d, const void *key); |
129 | int dictDeleteNoFree(dict *d, const void *key); |
130 | void dictRelease(dict *d); |
131 | dictEntry * dictFind(dict *d, const void *key); |
58e1c9c1 |
132 | void *dictFetchValue(dict *d, const void *key); |
8ca3e9d1 |
133 | int dictResize(dict *d); |
134 | dictIterator *dictGetIterator(dict *d); |
ed9b544e |
135 | dictEntry *dictNext(dictIterator *iter); |
136 | void dictReleaseIterator(dictIterator *iter); |
8ca3e9d1 |
137 | dictEntry *dictGetRandomKey(dict *d); |
138 | void dictPrintStats(dict *d); |
ed9b544e |
139 | unsigned int dictGenHashFunction(const unsigned char *buf, int len); |
8ca3e9d1 |
140 | void dictEmpty(dict *d); |
884d4b39 |
141 | void dictEnableResize(void); |
142 | void dictDisableResize(void); |
5413c40d |
143 | int dictRehash(dict *d, int n); |
8ca3e9d1 |
144 | int dictRehashMilliseconds(dict *d, int ms); |
ed9b544e |
145 | |
146 | /* Hash table types */ |
147 | extern dictType dictTypeHeapStringCopyKey; |
148 | extern dictType dictTypeHeapStrings; |
149 | extern dictType dictTypeHeapStringCopyKeyValue; |
150 | |
151 | #endif /* __DICT_H */ |