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 | * |
8 | * Copyright (c) 2006-2009, 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; |
f2923bec |
63 | unsigned long size; |
64 | unsigned long sizemask; |
65 | unsigned long used; |
ed9b544e |
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 */ |
12fea928 |
76 | #define DICT_HT_INITIAL_SIZE 4 |
ed9b544e |
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) |
3305306f |
110 | #define dictSlots(ht) ((ht)->size) |
111 | #define dictSize(ht) ((ht)->used) |
ed9b544e |
112 | |
113 | /* API */ |
114 | dict *dictCreate(dictType *type, void *privDataPtr); |
f2923bec |
115 | int dictExpand(dict *ht, unsigned long size); |
ed9b544e |
116 | int dictAdd(dict *ht, void *key, void *val); |
117 | int dictReplace(dict *ht, void *key, void *val); |
118 | int dictDelete(dict *ht, const void *key); |
119 | int dictDeleteNoFree(dict *ht, const void *key); |
120 | void dictRelease(dict *ht); |
121 | dictEntry * dictFind(dict *ht, const void *key); |
122 | int dictResize(dict *ht); |
123 | dictIterator *dictGetIterator(dict *ht); |
124 | dictEntry *dictNext(dictIterator *iter); |
125 | void dictReleaseIterator(dictIterator *iter); |
126 | dictEntry *dictGetRandomKey(dict *ht); |
127 | void dictPrintStats(dict *ht); |
128 | unsigned int dictGenHashFunction(const unsigned char *buf, int len); |
129 | void dictEmpty(dict *ht); |
130 | |
131 | /* Hash table types */ |
132 | extern dictType dictTypeHeapStringCopyKey; |
133 | extern dictType dictTypeHeapStrings; |
134 | extern dictType dictTypeHeapStringCopyKeyValue; |
135 | |
136 | #endif /* __DICT_H */ |