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 | #include "fmacros.h" |
37 | #include "alloc.h" |
38 | #include <stdlib.h> |
39 | #include <assert.h> |
40 | #include <limits.h> |
41 | #include "dict.h" |
42 | |
43 | /* -------------------------- private prototypes ---------------------------- */ |
44 | |
45 | static int _dictExpandIfNeeded(dict *ht); |
46 | static unsigned long _dictNextPower(unsigned long size); |
47 | static int _dictKeyIndex(dict *ht, const void *key); |
48 | static int _dictInit(dict *ht, dictType *type, void *privDataPtr); |
49 | |
50 | /* -------------------------- hash functions -------------------------------- */ |
51 | |
52 | /* Generic hash function (a popular one from Bernstein). |
53 | * I tested a few and this was the best. */ |
54 | static unsigned int dictGenHashFunction(const unsigned char *buf, int len) { |
55 | unsigned int hash = 5381; |
56 | |
57 | while (len--) |
58 | hash = ((hash << 5) + hash) + (*buf++); /* hash * 33 + c */ |
59 | return hash; |
60 | } |
61 | |
62 | /* ----------------------------- API implementation ------------------------- */ |
63 | |
64 | /* Reset an hashtable already initialized with ht_init(). |
65 | * NOTE: This function should only called by ht_destroy(). */ |
66 | static void _dictReset(dict *ht) { |
67 | ht->table = NULL; |
68 | ht->size = 0; |
69 | ht->sizemask = 0; |
70 | ht->used = 0; |
71 | } |
72 | |
73 | /* Create a new hash table */ |
74 | static dict *dictCreate(dictType *type, void *privDataPtr) { |
75 | dict *ht = hi_malloc(sizeof(*ht)); |
76 | if (ht == NULL) |
77 | return NULL; |
78 | |
79 | _dictInit(ht,type,privDataPtr); |
80 | return ht; |
81 | } |
82 | |
83 | /* Initialize the hash table */ |
84 | static int _dictInit(dict *ht, dictType *type, void *privDataPtr) { |
85 | _dictReset(ht); |
86 | ht->type = type; |
87 | ht->privdata = privDataPtr; |
88 | return DICT_OK; |
89 | } |
90 | |
91 | /* Expand or create the hashtable */ |
92 | static int dictExpand(dict *ht, unsigned long size) { |
93 | dict n; /* the new hashtable */ |
94 | unsigned long realsize = _dictNextPower(size), i; |
95 | |
96 | /* the size is invalid if it is smaller than the number of |
97 | * elements already inside the hashtable */ |
98 | if (ht->used > size) |
99 | return DICT_ERR; |
100 | |
101 | _dictInit(&n, ht->type, ht->privdata); |
102 | n.size = realsize; |
103 | n.sizemask = realsize-1; |
104 | n.table = hi_calloc(realsize,sizeof(dictEntry*)); |
105 | if (n.table == NULL) |
106 | return DICT_ERR; |
107 | |
108 | /* Copy all the elements from the old to the new table: |
109 | * note that if the old hash table is empty ht->size is zero, |
110 | * so dictExpand just creates an hash table. */ |
111 | n.used = ht->used; |
112 | for (i = 0; i < ht->size && ht->used > 0; i++) { |
113 | dictEntry *he, *nextHe; |
114 | |
115 | if (ht->table[i] == NULL) continue; |
116 | |
117 | /* For each hash entry on this slot... */ |
118 | he = ht->table[i]; |
119 | while(he) { |
120 | unsigned int h; |
121 | |
122 | nextHe = he->next; |
123 | /* Get the new element index */ |
124 | h = dictHashKey(ht, he->key) & n.sizemask; |
125 | he->next = n.table[h]; |
126 | n.table[h] = he; |
127 | ht->used--; |
128 | /* Pass to the next element */ |
129 | he = nextHe; |
130 | } |
131 | } |
132 | assert(ht->used == 0); |
133 | hi_free(ht->table); |
134 | |
135 | /* Remap the new hashtable in the old */ |
136 | *ht = n; |
137 | return DICT_OK; |
138 | } |
139 | |
140 | /* Add an element to the target hash table */ |
141 | static int dictAdd(dict *ht, void *key, void *val) { |
142 | int index; |
143 | dictEntry *entry; |
144 | |
145 | /* Get the index of the new element, or -1 if |
146 | * the element already exists. */ |
147 | if ((index = _dictKeyIndex(ht, key)) == -1) |
148 | return DICT_ERR; |
149 | |
150 | /* Allocates the memory and stores key */ |
151 | entry = hi_malloc(sizeof(*entry)); |
152 | if (entry == NULL) |
153 | return DICT_ERR; |
154 | |
155 | entry->next = ht->table[index]; |
156 | ht->table[index] = entry; |
157 | |
158 | /* Set the hash entry fields. */ |
159 | dictSetHashKey(ht, entry, key); |
160 | dictSetHashVal(ht, entry, val); |
161 | ht->used++; |
162 | return DICT_OK; |
163 | } |
164 | |
165 | /* Add an element, discarding the old if the key already exists. |
166 | * Return 1 if the key was added from scratch, 0 if there was already an |
167 | * element with such key and dictReplace() just performed a value update |
168 | * operation. */ |
169 | static int dictReplace(dict *ht, void *key, void *val) { |
170 | dictEntry *entry, auxentry; |
171 | |
172 | /* Try to add the element. If the key |
173 | * does not exists dictAdd will succeed. */ |
174 | if (dictAdd(ht, key, val) == DICT_OK) |
175 | return 1; |
176 | /* It already exists, get the entry */ |
177 | entry = dictFind(ht, key); |
178 | if (entry == NULL) |
179 | return 0; |
180 | |
181 | /* Free the old value and set the new one */ |
182 | /* Set the new value and free the old one. Note that it is important |
183 | * to do that in this order, as the value may just be exactly the same |
184 | * as the previous one. In this context, think to reference counting, |
185 | * you want to increment (set), and then decrement (free), and not the |
186 | * reverse. */ |
187 | auxentry = *entry; |
188 | dictSetHashVal(ht, entry, val); |
189 | dictFreeEntryVal(ht, &auxentry); |
190 | return 0; |
191 | } |
192 | |
193 | /* Search and remove an element */ |
194 | static int dictDelete(dict *ht, const void *key) { |
195 | unsigned int h; |
196 | dictEntry *de, *prevde; |
197 | |
198 | if (ht->size == 0) |
199 | return DICT_ERR; |
200 | h = dictHashKey(ht, key) & ht->sizemask; |
201 | de = ht->table[h]; |
202 | |
203 | prevde = NULL; |
204 | while(de) { |
205 | if (dictCompareHashKeys(ht,key,de->key)) { |
206 | /* Unlink the element from the list */ |
207 | if (prevde) |
208 | prevde->next = de->next; |
209 | else |
210 | ht->table[h] = de->next; |
211 | |
212 | dictFreeEntryKey(ht,de); |
213 | dictFreeEntryVal(ht,de); |
214 | hi_free(de); |
215 | ht->used--; |
216 | return DICT_OK; |
217 | } |
218 | prevde = de; |
219 | de = de->next; |
220 | } |
221 | return DICT_ERR; /* not found */ |
222 | } |
223 | |
224 | /* Destroy an entire hash table */ |
225 | static int _dictClear(dict *ht) { |
226 | unsigned long i; |
227 | |
228 | /* Free all the elements */ |
229 | for (i = 0; i < ht->size && ht->used > 0; i++) { |
230 | dictEntry *he, *nextHe; |
231 | |
232 | if ((he = ht->table[i]) == NULL) continue; |
233 | while(he) { |
234 | nextHe = he->next; |
235 | dictFreeEntryKey(ht, he); |
236 | dictFreeEntryVal(ht, he); |
237 | hi_free(he); |
238 | ht->used--; |
239 | he = nextHe; |
240 | } |
241 | } |
242 | /* Free the table and the allocated cache structure */ |
243 | hi_free(ht->table); |
244 | /* Re-initialize the table */ |
245 | _dictReset(ht); |
246 | return DICT_OK; /* never fails */ |
247 | } |
248 | |
249 | /* Clear & Release the hash table */ |
250 | static void dictRelease(dict *ht) { |
251 | _dictClear(ht); |
252 | hi_free(ht); |
253 | } |
254 | |
255 | static dictEntry *dictFind(dict *ht, const void *key) { |
256 | dictEntry *he; |
257 | unsigned int h; |
258 | |
259 | if (ht->size == 0) return NULL; |
260 | h = dictHashKey(ht, key) & ht->sizemask; |
261 | he = ht->table[h]; |
262 | while(he) { |
263 | if (dictCompareHashKeys(ht, key, he->key)) |
264 | return he; |
265 | he = he->next; |
266 | } |
267 | return NULL; |
268 | } |
269 | |
270 | static void dictInitIterator(dictIterator *iter, dict *ht) { |
271 | iter->ht = ht; |
272 | iter->index = -1; |
273 | iter->entry = NULL; |
274 | iter->nextEntry = NULL; |
275 | } |
276 | |
277 | static dictEntry *dictNext(dictIterator *iter) { |
278 | while (1) { |
279 | if (iter->entry == NULL) { |
280 | iter->index++; |
281 | if (iter->index >= |
282 | (signed)iter->ht->size) break; |
283 | iter->entry = iter->ht->table[iter->index]; |
284 | } else { |
285 | iter->entry = iter->nextEntry; |
286 | } |
287 | if (iter->entry) { |
288 | /* We need to save the 'next' here, the iterator user |
289 | * may delete the entry we are returning. */ |
290 | iter->nextEntry = iter->entry->next; |
291 | return iter->entry; |
292 | } |
293 | } |
294 | return NULL; |
295 | } |
296 | |
297 | /* ------------------------- private functions ------------------------------ */ |
298 | |
299 | /* Expand the hash table if needed */ |
300 | static int _dictExpandIfNeeded(dict *ht) { |
301 | /* If the hash table is empty expand it to the initial size, |
302 | * if the table is "full" double its size. */ |
303 | if (ht->size == 0) |
304 | return dictExpand(ht, DICT_HT_INITIAL_SIZE); |
305 | if (ht->used == ht->size) |
306 | return dictExpand(ht, ht->size*2); |
307 | return DICT_OK; |
308 | } |
309 | |
310 | /* Our hash table capability is a power of two */ |
311 | static unsigned long _dictNextPower(unsigned long size) { |
312 | unsigned long i = DICT_HT_INITIAL_SIZE; |
313 | |
314 | if (size >= LONG_MAX) return LONG_MAX; |
315 | while(1) { |
316 | if (i >= size) |
317 | return i; |
318 | i *= 2; |
319 | } |
320 | } |
321 | |
322 | /* Returns the index of a free slot that can be populated with |
323 | * an hash entry for the given 'key'. |
324 | * If the key already exists, -1 is returned. */ |
325 | static int _dictKeyIndex(dict *ht, const void *key) { |
326 | unsigned int h; |
327 | dictEntry *he; |
328 | |
329 | /* Expand the hashtable if needed */ |
330 | if (_dictExpandIfNeeded(ht) == DICT_ERR) |
331 | return -1; |
332 | /* Compute the key hash value */ |
333 | h = dictHashKey(ht, key) & ht->sizemask; |
334 | /* Search if this slot does not already contain the given key */ |
335 | he = ht->table[h]; |
336 | while(he) { |
337 | if (dictCompareHashKeys(ht, key, he->key)) |
338 | return -1; |
339 | he = he->next; |
340 | } |
341 | return h; |
342 | } |
343 | |
344 | |