]> git.saurik.com Git - redis.git/blame_incremental - src/dict.h
fix a typo in a comment
[redis.git] / src / dict.h
... / ...
CommitLineData
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-2012, 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 <stdint.h>
37
38#ifndef __DICT_H
39#define __DICT_H
40
41#define DICT_OK 0
42#define DICT_ERR 1
43
44/* Unused arguments generate annoying warnings... */
45#define DICT_NOTUSED(V) ((void) V)
46
47typedef struct dictEntry {
48 void *key;
49 union {
50 void *val;
51 uint64_t u64;
52 int64_t s64;
53 } v;
54 struct dictEntry *next;
55} dictEntry;
56
57typedef struct dictType {
58 unsigned int (*hashFunction)(const void *key);
59 void *(*keyDup)(void *privdata, const void *key);
60 void *(*valDup)(void *privdata, const void *obj);
61 int (*keyCompare)(void *privdata, const void *key1, const void *key2);
62 void (*keyDestructor)(void *privdata, void *key);
63 void (*valDestructor)(void *privdata, void *obj);
64} dictType;
65
66/* This is our hash table structure. Every dictionary has two of this as we
67 * implement incremental rehashing, for the old to the new table. */
68typedef struct dictht {
69 dictEntry **table;
70 unsigned long size;
71 unsigned long sizemask;
72 unsigned long used;
73} dictht;
74
75typedef struct dict {
76 dictType *type;
77 void *privdata;
78 dictht ht[2];
79 int rehashidx; /* rehashing not in progress if rehashidx == -1 */
80 int iterators; /* number of iterators currently running */
81} dict;
82
83/* If safe is set to 1 this is a safe iterator, that means, you can call
84 * dictAdd, dictFind, and other functions against the dictionary even while
85 * iterating. Otherwise it is a non safe iterator, and only dictNext()
86 * should be called while iterating. */
87typedef struct dictIterator {
88 dict *d;
89 int table, index, safe;
90 dictEntry *entry, *nextEntry;
91} dictIterator;
92
93/* This is the initial size of every hash table */
94#define DICT_HT_INITIAL_SIZE 4
95
96/* ------------------------------- Macros ------------------------------------*/
97#define dictFreeVal(d, entry) \
98 if ((d)->type->valDestructor) \
99 (d)->type->valDestructor((d)->privdata, (entry)->v.val)
100
101#define dictSetVal(d, entry, _val_) do { \
102 if ((d)->type->valDup) \
103 entry->v.val = (d)->type->valDup((d)->privdata, _val_); \
104 else \
105 entry->v.val = (_val_); \
106} while(0)
107
108#define dictSetSignedIntegerVal(entry, _val_) \
109 do { entry->v.s64 = _val_; } while(0)
110
111#define dictSetUnsignedIntegerVal(entry, _val_) \
112 do { entry->v.u64 = _val_; } while(0)
113
114#define dictFreeKey(d, entry) \
115 if ((d)->type->keyDestructor) \
116 (d)->type->keyDestructor((d)->privdata, (entry)->key)
117
118#define dictSetKey(d, entry, _key_) do { \
119 if ((d)->type->keyDup) \
120 entry->key = (d)->type->keyDup((d)->privdata, _key_); \
121 else \
122 entry->key = (_key_); \
123} while(0)
124
125#define dictCompareKeys(d, key1, key2) \
126 (((d)->type->keyCompare) ? \
127 (d)->type->keyCompare((d)->privdata, key1, key2) : \
128 (key1) == (key2))
129
130#define dictHashKey(d, key) (d)->type->hashFunction(key)
131#define dictGetKey(he) ((he)->key)
132#define dictGetVal(he) ((he)->v.val)
133#define dictGetSignedIntegerVal(he) ((he)->v.s64)
134#define dictGetUnsignedIntegerVal(he) ((he)->v.u64)
135#define dictSlots(d) ((d)->ht[0].size+(d)->ht[1].size)
136#define dictSize(d) ((d)->ht[0].used+(d)->ht[1].used)
137#define dictIsRehashing(ht) ((ht)->rehashidx != -1)
138
139/* API */
140dict *dictCreate(dictType *type, void *privDataPtr);
141int dictExpand(dict *d, unsigned long size);
142int dictAdd(dict *d, void *key, void *val);
143dictEntry *dictAddRaw(dict *d, void *key);
144int dictReplace(dict *d, void *key, void *val);
145dictEntry *dictReplaceRaw(dict *d, void *key);
146int dictDelete(dict *d, const void *key);
147int dictDeleteNoFree(dict *d, const void *key);
148void dictRelease(dict *d);
149dictEntry * dictFind(dict *d, const void *key);
150void *dictFetchValue(dict *d, const void *key);
151int dictResize(dict *d);
152dictIterator *dictGetIterator(dict *d);
153dictIterator *dictGetSafeIterator(dict *d);
154dictEntry *dictNext(dictIterator *iter);
155void dictReleaseIterator(dictIterator *iter);
156dictEntry *dictGetRandomKey(dict *d);
157void dictPrintStats(dict *d);
158unsigned int dictGenHashFunction(const void *key, int len);
159unsigned int dictGenCaseHashFunction(const unsigned char *buf, int len);
160void dictEmpty(dict *d);
161void dictEnableResize(void);
162void dictDisableResize(void);
163int dictRehash(dict *d, int n);
164int dictRehashMilliseconds(dict *d, int ms);
165void dictSetHashFunctionSeed(unsigned int initval);
166unsigned int dictGetHashFunctionSeed(void);
167
168/* Hash table types */
169extern dictType dictTypeHeapStringCopyKey;
170extern dictType dictTypeHeapStrings;
171extern dictType dictTypeHeapStringCopyKeyValue;
172
173#endif /* __DICT_H */