Skip to content

HTTPS clone URL

Subversion checkout URL

You can clone with
or
.
Download ZIP
Newer
Older
100644 152 lines (132 sloc) 5.525 kB
ed9b544 @antirez first commit
antirez authored
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 *
12d090d @antirez A problem with replication with multiple slaves connectiong to a sing…
antirez authored
8 * Copyright (c) 2006-2010, Salvatore Sanfilippo <antirez at gmail dot com>
ed9b544 @antirez first commit
antirez authored
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
5413c40 @antirez Incrementally rehahsing hash table! Thanks to Derek Collison and Piet…
antirez authored
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 {
ed9b544 @antirez first commit
antirez authored
63 dictEntry **table;
f2923be @antirez dict.c modified to be able to handle more than 150,000,000 keys
antirez authored
64 unsigned long size;
65 unsigned long sizemask;
66 unsigned long used;
5413c40 @antirez Incrementally rehahsing hash table! Thanks to Derek Collison and Piet…
antirez authored
67 } dictht;
68
69 typedef struct dict {
70 dictType *type;
ed9b544 @antirez first commit
antirez authored
71 void *privdata;
5413c40 @antirez Incrementally rehahsing hash table! Thanks to Derek Collison and Piet…
antirez authored
72 dictht ht[2];
73 int rehashidx; /* rehashing not in progress if rehashidx == -1 */
74 int iterators; /* number of iterators currently running */
ed9b544 @antirez first commit
antirez authored
75 } dict;
76
77 typedef struct dictIterator {
5413c40 @antirez Incrementally rehahsing hash table! Thanks to Derek Collison and Piet…
antirez authored
78 dict *d;
79 int table;
ed9b544 @antirez first commit
antirez authored
80 int index;
81 dictEntry *entry, *nextEntry;
82 } dictIterator;
83
84 /* This is the initial size of every hash table */
12fea92 @antirez SPOP implemented. Hash table resizing for Sets and Expires too. Chang…
antirez authored
85 #define DICT_HT_INITIAL_SIZE 4
ed9b544 @antirez first commit
antirez authored
86
87 /* ------------------------------- Macros ------------------------------------*/
5413c40 @antirez Incrementally rehahsing hash table! Thanks to Derek Collison and Piet…
antirez authored
88 #define dictFreeEntryVal(d, entry) \
89 if ((d)->type->valDestructor) \
90 (d)->type->valDestructor((d)->privdata, (entry)->val)
ed9b544 @antirez first commit
antirez authored
91
5413c40 @antirez Incrementally rehahsing hash table! Thanks to Derek Collison and Piet…
antirez authored
92 #define dictSetHashVal(d, entry, _val_) do { \
93 if ((d)->type->valDup) \
94 entry->val = (d)->type->valDup((d)->privdata, _val_); \
ed9b544 @antirez first commit
antirez authored
95 else \
96 entry->val = (_val_); \
97 } while(0)
98
5413c40 @antirez Incrementally rehahsing hash table! Thanks to Derek Collison and Piet…
antirez authored
99 #define dictFreeEntryKey(d, entry) \
100 if ((d)->type->keyDestructor) \
101 (d)->type->keyDestructor((d)->privdata, (entry)->key)
ed9b544 @antirez first commit
antirez authored
102
5413c40 @antirez Incrementally rehahsing hash table! Thanks to Derek Collison and Piet…
antirez authored
103 #define dictSetHashKey(d, entry, _key_) do { \
104 if ((d)->type->keyDup) \
105 entry->key = (d)->type->keyDup((d)->privdata, _key_); \
ed9b544 @antirez first commit
antirez authored
106 else \
107 entry->key = (_key_); \
108 } while(0)
109
5413c40 @antirez Incrementally rehahsing hash table! Thanks to Derek Collison and Piet…
antirez authored
110 #define dictCompareHashKeys(d, key1, key2) \
111 (((d)->type->keyCompare) ? \
112 (d)->type->keyCompare((d)->privdata, key1, key2) : \
ed9b544 @antirez first commit
antirez authored
113 (key1) == (key2))
114
5413c40 @antirez Incrementally rehahsing hash table! Thanks to Derek Collison and Piet…
antirez authored
115 #define dictHashKey(d, key) (d)->type->hashFunction(key)
ed9b544 @antirez first commit
antirez authored
116
117 #define dictGetEntryKey(he) ((he)->key)
118 #define dictGetEntryVal(he) ((he)->val)
5413c40 @antirez Incrementally rehahsing hash table! Thanks to Derek Collison and Piet…
antirez authored
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)
ed9b544 @antirez first commit
antirez authored
122
123 /* API */
124 dict *dictCreate(dictType *type, void *privDataPtr);
8ca3e9d @antirez Active rehashing
antirez authored
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);
58e1c9c @antirez added dictFetchValue() to dict.c to make hash table API a bit less ve…
antirez authored
132 void *dictFetchValue(dict *d, const void *key);
8ca3e9d @antirez Active rehashing
antirez authored
133 int dictResize(dict *d);
134 dictIterator *dictGetIterator(dict *d);
ed9b544 @antirez first commit
antirez authored
135 dictEntry *dictNext(dictIterator *iter);
136 void dictReleaseIterator(dictIterator *iter);
8ca3e9d @antirez Active rehashing
antirez authored
137 dictEntry *dictGetRandomKey(dict *d);
138 void dictPrintStats(dict *d);
ed9b544 @antirez first commit
antirez authored
139 unsigned int dictGenHashFunction(const unsigned char *buf, int len);
8ca3e9d @antirez Active rehashing
antirez authored
140 void dictEmpty(dict *d);
884d4b3 @antirez Prevent hash table resize while there are active child processes in o…
antirez authored
141 void dictEnableResize(void);
142 void dictDisableResize(void);
5413c40 @antirez Incrementally rehahsing hash table! Thanks to Derek Collison and Piet…
antirez authored
143 int dictRehash(dict *d, int n);
8ca3e9d @antirez Active rehashing
antirez authored
144 int dictRehashMilliseconds(dict *d, int ms);
ed9b544 @antirez first commit
antirez authored
145
146 /* Hash table types */
147 extern dictType dictTypeHeapStringCopyKey;
148 extern dictType dictTypeHeapStrings;
149 extern dictType dictTypeHeapStringCopyKeyValue;
150
151 #endif /* __DICT_H */
Something went wrong with that request. Please try again.