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-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 #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 /* 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 { 63 dictEntry **table; 64 unsigned long size; 65 unsigned long sizemask; 66 unsigned long used; 67 } dictht; 68 69 typedef struct dict { 70 dictType *type; 71 void *privdata; 72 dictht ht[2]; 73 int rehashidx; /* rehashing not in progress if rehashidx == -1 */ 74 int iterators; /* number of iterators currently running */ 75 } dict; 76 77 typedef struct dictIterator { 78 dict *d; 79 int table; 80 int index; 81 dictEntry *entry, *nextEntry; 82 } dictIterator; 83 84 /* This is the initial size of every hash table */ 85 #define DICT_HT_INITIAL_SIZE 4 86 87 /* ------------------------------- Macros ------------------------------------*/ 88 #define dictFreeEntryVal(d, entry) \ 89 if ((d)->type->valDestructor) \ 90 (d)->type->valDestructor((d)->privdata, (entry)->val) 91 92 #define dictSetHashVal(d, entry, _val_) do { \ 93 if ((d)->type->valDup) \ 94 entry->val = (d)->type->valDup((d)->privdata, _val_); \ 95 else \ 96 entry->val = (_val_); \ 97 } while(0) 98 99 #define dictFreeEntryKey(d, entry) \ 100 if ((d)->type->keyDestructor) \ 101 (d)->type->keyDestructor((d)->privdata, (entry)->key) 102 103 #define dictSetHashKey(d, entry, _key_) do { \ 104 if ((d)->type->keyDup) \ 105 entry->key = (d)->type->keyDup((d)->privdata, _key_); \ 106 else \ 107 entry->key = (_key_); \ 108 } while(0) 109 110 #define dictCompareHashKeys(d, key1, key2) \ 111 (((d)->type->keyCompare) ? \ 112 (d)->type->keyCompare((d)->privdata, key1, key2) : \ 113 (key1) == (key2)) 114 115 #define dictHashKey(d, key) (d)->type->hashFunction(key) 116 117 #define dictGetEntryKey(he) ((he)->key) 118 #define dictGetEntryVal(he) ((he)->val) 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) 122 123 /* API */ 124 dict *dictCreate(dictType *type, void *privDataPtr); 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); 132 void *dictFetchValue(dict *d, const void *key); 133 int dictResize(dict *d); 134 dictIterator *dictGetIterator(dict *d); 135 dictEntry *dictNext(dictIterator *iter); 136 void dictReleaseIterator(dictIterator *iter); 137 dictEntry *dictGetRandomKey(dict *d); 138 void dictPrintStats(dict *d); 139 unsigned int dictGenHashFunction(const unsigned char *buf, int len); 140 unsigned int dictGenCaseHashFunction(const unsigned char *buf, int len); 141 void dictEmpty(dict *d); 142 void dictEnableResize(void); 143 void dictDisableResize(void); 144 int dictRehash(dict *d, int n); 145 int dictRehashMilliseconds(dict *d, int ms); 146 147 /* Hash table types */ 148 extern dictType dictTypeHeapStringCopyKey; 149 extern dictType dictTypeHeapStrings; 150 extern dictType dictTypeHeapStringCopyKeyValue; 151 152 #endif /* __DICT_H */ 153