【C Hash Map from Redis】

  • 将Redis源码中的哈希表底层逻辑提取,并进行最小demo级测试
  • 将对应文件抽出,通过宏替换等方式保证源码编译通过
  • main.c编写测试demo ,注册哈希函数和值比较函数(必选项)
/* Hash Tables Implementation.** This file implements in-memory hash tables with insert/del/replace/find/* get-random-element operations. Hash tables will auto-resize if needed* tables of power of two in size are used, collisions are handled by* chaining. See the source code for more information... :)** Copyright (c) 2006-2012, Salvatore Sanfilippo <antirez at gmail dot com>* All rights reserved.** Redistribution and use in source and binary forms, with or without* modification, are permitted provided that the following conditions are met:**   * Redistributions of source code must retain the above copyright notice,*     this list of conditions and the following disclaimer.*   * Redistributions in binary form must reproduce the above copyright*     notice, this list of conditions and the following disclaimer in the*     documentation and/or other materials provided with the distribution.*   * Neither the name of Redis nor the names of its contributors may be used*     to endorse or promote products derived from this software without*     specific prior written permission.** THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"* AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE* ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE* LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR* CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF* SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS* INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN* CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)* ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE* POSSIBILITY OF SUCH DAMAGE.*/#ifndef __DICT_H
#define __DICT_H#include "mt19937-64.h"
#include <limits.h>
#include <stdint.h>
#include <stdlib.h>#define DICT_OK 0
#define DICT_ERR 1/* Unused arguments generate annoying warnings... */
#define DICT_NOTUSED(V) ((void) V)typedef struct dictEntry {void *key;union {void *val;uint64_t u64;int64_t s64;double d;} v;struct dictEntry *next;
} dictEntry;typedef struct dictType {uint64_t (*hashFunction)(const void *key);void *(*keyDup)(void *privdata, const void *key);void *(*valDup)(void *privdata, const void *obj);int (*keyCompare)(void *privdata, const void *key1, const void *key2);void (*keyDestructor)(void *privdata, void *key);void (*valDestructor)(void *privdata, void *obj);int (*expandAllowed)(size_t moreMem, double usedRatio);
} dictType;/* This is our hash table structure. Every dictionary has two of this as we* implement incremental rehashing, for the old to the new table. */
typedef struct dictht {dictEntry **table;unsigned long size;unsigned long sizemask;unsigned long used;
} dictht;typedef struct dict {dictType *type;void *privdata;dictht ht[2];long rehashidx; /* rehashing not in progress if rehashidx == -1 */int16_t pauserehash; /* If >0 rehashing is paused (<0 indicates coding error) */
} dict;/* If safe is set to 1 this is a safe iterator, that means, you can call* dictAdd, dictFind, and other functions against the dictionary even while* iterating. Otherwise it is a non safe iterator, and only dictNext()* should be called while iterating. */
typedef struct dictIterator {dict *d;long index;int table, safe;dictEntry *entry, *nextEntry;/* unsafe iterator fingerprint for misuse detection. */unsigned long long fingerprint;
} dictIterator;typedef void (dictScanFunction)(void *privdata, const dictEntry *de);
typedef void (dictScanBucketFunction)(void *privdata, dictEntry **bucketref);/* This is the initial size of every hash table */
#define DICT_HT_INITIAL_SIZE     4/* ------------------------------- Macros ------------------------------------*/
#define dictFreeVal(d, entry) \if ((d)->type->valDestructor) \(d)->type->valDestructor((d)->privdata, (entry)->v.val)#define dictSetVal(d, entry, _val_) do { \if ((d)->type->valDup) \(entry)->v.val = (d)->type->valDup((d)->privdata, _val_); \else \(entry)->v.val = (_val_); \
} while(0)#define dictSetSignedIntegerVal(entry, _val_) \do { (entry)->v.s64 = _val_; } while(0)#define dictSetUnsignedIntegerVal(entry, _val_) \do { (entry)->v.u64 = _val_; } while(0)#define dictSetDoubleVal(entry, _val_) \do { (entry)->v.d = _val_; } while(0)#define dictFreeKey(d, entry) \if ((d)->type->keyDestructor) \(d)->type->keyDestructor((d)->privdata, (entry)->key)#define dictSetKey(d, entry, _key_) do { \if ((d)->type->keyDup) \(entry)->key = (d)->type->keyDup((d)->privdata, _key_); \else \(entry)->key = (_key_); \
} while(0)#define dictCompareKeys(d, key1, key2) \(((d)->type->keyCompare) ? \(d)->type->keyCompare((d)->privdata, key1, key2) : \(key1) == (key2))#define dictHashKey(d, key) (d)->type->hashFunction(key)
#define dictGetKey(he) ((he)->key)
#define dictGetVal(he) ((he)->v.val)
#define dictGetSignedIntegerVal(he) ((he)->v.s64)
#define dictGetUnsignedIntegerVal(he) ((he)->v.u64)
#define dictGetDoubleVal(he) ((he)->v.d)
#define dictSlots(d) ((d)->ht[0].size+(d)->ht[1].size)
#define dictSize(d) ((d)->ht[0].used+(d)->ht[1].used)
#define dictIsRehashing(d) ((d)->rehashidx != -1)
#define dictPauseRehashing(d) (d)->pauserehash++
#define dictResumeRehashing(d) (d)->pauserehash--/* If our unsigned long type can store a 64 bit number, use a 64 bit PRNG. */
#if ULONG_MAX >= 0xffffffffffffffff
#define randomULong() ((unsigned long) genrand64_int64())
#else
#define randomULong() random()
#endiftypedef enum {DICT_RESIZE_ENABLE,DICT_RESIZE_AVOID,DICT_RESIZE_FORBID,
} dictResizeEnable;/* API */
dict *dictCreate(dictType *type, void *privDataPtr);
int dictExpand(dict *d, unsigned long size);
int dictTryExpand(dict *d, unsigned long size);
int dictAdd(dict *d, void *key, void *val);
dictEntry *dictAddRaw(dict *d, void *key, dictEntry **existing);
dictEntry *dictAddOrFind(dict *d, void *key);
int dictReplace(dict *d, void *key, void *val);
int dictDelete(dict *d, const void *key);
dictEntry *dictUnlink(dict *ht, const void *key);
void dictFreeUnlinkedEntry(dict *d, dictEntry *he);
void dictRelease(dict *d);
dictEntry * dictFind(dict *d, const void *key);
void *dictFetchValue(dict *d, const void *key);
int dictResize(dict *d);
dictIterator *dictGetIterator(dict *d);
dictIterator *dictGetSafeIterator(dict *d);
dictEntry *dictNext(dictIterator *iter);
void dictReleaseIterator(dictIterator *iter);
dictEntry *dictGetRandomKey(dict *d);
dictEntry *dictGetFairRandomKey(dict *d);
unsigned int dictGetSomeKeys(dict *d, dictEntry **des, unsigned int count);
void dictGetStats(char *buf, size_t bufsize, dict *d);
uint64_t dictGenHashFunction(const void *key, int len);
uint64_t dictGenCaseHashFunction(const unsigned char *buf, int len);
void dictEmpty(dict *d, void(callback)(void*));
void dictSetResizeEnabled(dictResizeEnable enable);
int dictRehash(dict *d, int n);
int dictRehashMilliseconds(dict *d, int ms);
void dictSetHashFunctionSeed(uint8_t *seed);
uint8_t *dictGetHashFunctionSeed(void);
unsigned long dictScan(dict *d, unsigned long v, dictScanFunction *fn, dictScanBucketFunction *bucketfn, void *privdata);
uint64_t dictGetHash(dict *d, const void *key);
dictEntry **dictFindEntryRefByPtrAndHash(dict *d, const void *oldptr, uint64_t hash);/* Hash table types */
extern dictType dictTypeHeapStringCopyKey;
extern dictType dictTypeHeapStrings;
extern dictType dictTypeHeapStringCopyKeyValue;#ifdef REDIS_TEST
int dictTest(int argc, char *argv[], int accurate);
#endif/*  defined by blogger  */
#define zcalloc(n) calloc(n, sizeof(char))
#define zmalloc    malloc
#define zfree      free
#define ztrycalloc zcalloc#endif /* __DICT_H */
/* Hash Tables Implementation.** This file implements in memory hash tables with insert/del/replace/find/* get-random-element operations. Hash tables will auto resize if needed* tables of power of two in size are used, collisions are handled by* chaining. See the source code for more information... :)** Copyright (c) 2006-2012, Salvatore Sanfilippo <antirez at gmail dot com>* All rights reserved.** Redistribution and use in source and binary forms, with or without* modification, are permitted provided that the following conditions are met:**   * Redistributions of source code must retain the above copyright notice,*     this list of conditions and the following disclaimer.*   * Redistributions in binary form must reproduce the above copyright*     notice, this list of conditions and the following disclaimer in the*     documentation and/or other materials provided with the distribution.*   * Neither the name of Redis nor the names of its contributors may be used*     to endorse or promote products derived from this software without*     specific prior written permission.** THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"* AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE* ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE* LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR* CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF* SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS* INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN* CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)* ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE* POSSIBILITY OF SUCH DAMAGE.*///#include "fmacros.h"#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <string.h>
#include <stdarg.h>
#include <limits.h>
#include <sys/time.h>
#include <assert.h>
#include "dict.h"
//#include "zmalloc.h"
//#include "redisassert.h"/* Using dictEnableResize() / dictDisableResize() we make possible to disable* resizing and rehashing of the hash table as needed. This is very important* for Redis, as we use copy-on-write and don't want to move too much memory* around when there is a child performing saving operations.** Note that even when dict_can_resize is set to 0, not all resizes are* prevented: a hash table is still allowed to grow if the ratio between* the number of elements and the buckets > dict_force_resize_ratio. */
static dictResizeEnable dict_can_resize = DICT_RESIZE_ENABLE;
static unsigned int dict_force_resize_ratio = 5;/* -------------------------- private prototypes ---------------------------- */static int _dictExpandIfNeeded(dict *ht);
static unsigned long _dictNextPower(unsigned long size);
static long _dictKeyIndex(dict *ht, const void *key, uint64_t hash, dictEntry **existing);
static int _dictInit(dict *ht, dictType *type, void *privDataPtr);/* -------------------------- hash functions -------------------------------- */static uint8_t dict_hash_function_seed[16];void dictSetHashFunctionSeed(uint8_t *seed) {memcpy(dict_hash_function_seed,seed,sizeof(dict_hash_function_seed));
}uint8_t *dictGetHashFunctionSeed(void) {return dict_hash_function_seed;
}/* The default hashing function uses SipHash implementation* in siphash.c. */uint64_t siphash(const uint8_t *in, const size_t inlen, const uint8_t *k);
uint64_t siphash_nocase(const uint8_t *in, const size_t inlen, const uint8_t *k);uint64_t dictGenHashFunction(const void *key, int len) {return siphash(key,len,dict_hash_function_seed);
}uint64_t dictGenCaseHashFunction(const unsigned char *buf, int len) {return siphash_nocase(buf,len,dict_hash_function_seed);
}/* ----------------------------- API implementation ------------------------- *//* Reset a hash table already initialized with ht_init().* NOTE: This function should only be called by ht_destroy(). */
static void _dictReset(dictht *ht)
{ht->table = NULL;ht->size = 0;ht->sizemask = 0;ht->used = 0;
}/* Create a new hash table */
dict *dictCreate(dictType *type,void *privDataPtr)
{dict *d = zmalloc(sizeof(*d));_dictInit(d,type,privDataPtr);return d;
}/* Initialize the hash table */
int _dictInit(dict *d, dictType *type,void *privDataPtr)
{_dictReset(&d->ht[0]);_dictReset(&d->ht[1]);d->type = type;d->privdata = privDataPtr;d->rehashidx = -1;d->pauserehash = 0;return DICT_OK;
}/* Resize the table to the minimal size that contains all the elements,* but with the invariant of a USED/BUCKETS ratio near to <= 1 */
int dictResize(dict *d)
{unsigned long minimal;if (dict_can_resize != DICT_RESIZE_ENABLE || dictIsRehashing(d)) return DICT_ERR;minimal = d->ht[0].used;if (minimal < DICT_HT_INITIAL_SIZE)minimal = DICT_HT_INITIAL_SIZE;return dictExpand(d, minimal);
}/* Expand or create the hash table,* when malloc_failed is non-NULL, it'll avoid panic if malloc fails (in which case it'll be set to 1).* Returns DICT_OK if expand was performed, and DICT_ERR if skipped. */
int _dictExpand(dict *d, unsigned long size, int* malloc_failed)
{if (malloc_failed) *malloc_failed = 0;/* the size is invalid if it is smaller than the number of* elements already inside the hash table */if (dictIsRehashing(d) || d->ht[0].used > size)return DICT_ERR;dictht n; /* the new hash table */unsigned long realsize = _dictNextPower(size);/* Detect overflows */if (realsize < size || realsize * sizeof(dictEntry*) < realsize)return DICT_ERR;/* Rehashing to the same table size is not useful. */if (realsize == d->ht[0].size) return DICT_ERR;/* Allocate the new hash table and initialize all pointers to NULL */n.size = realsize;n.sizemask = realsize-1;if (malloc_failed) {n.table = ztrycalloc(realsize*sizeof(dictEntry*));*malloc_failed = n.table == NULL;if (*malloc_failed)return DICT_ERR;} elsen.table = zcalloc(realsize*sizeof(dictEntry*));n.used = 0;/* Is this the first initialization? If so it's not really a rehashing* we just set the first hash table so that it can accept keys. */if (d->ht[0].table == NULL) {d->ht[0] = n;return DICT_OK;}/* Prepare a second hash table for incremental rehashing */d->ht[1] = n;d->rehashidx = 0;return DICT_OK;
}/* return DICT_ERR if expand was not performed */
int dictExpand(dict *d, unsigned long size) {return _dictExpand(d, size, NULL);
}/* return DICT_ERR if expand failed due to memory allocation failure */
int dictTryExpand(dict *d, unsigned long size) {int malloc_failed;_dictExpand(d, size, &malloc_failed);return malloc_failed? DICT_ERR : DICT_OK;
}/* Performs N steps of incremental rehashing. Returns 1 if there are still* keys to move from the old to the new hash table, otherwise 0 is returned.** Note that a rehashing step consists in moving a bucket (that may have more* than one key as we use chaining) from the old to the new hash table, however* since part of the hash table may be composed of empty spaces, it is not* guaranteed that this function will rehash even a single bucket, since it* will visit at max N*10 empty buckets in total, otherwise the amount of* work it does would be unbound and the function may block for a long time. */
int dictRehash(dict *d, int n) {int empty_visits = n*10; /* Max number of empty buckets to visit. */unsigned long s0 = d->ht[0].size;unsigned long s1 = d->ht[1].size;if (dict_can_resize == DICT_RESIZE_FORBID || !dictIsRehashing(d)) return 0;if (dict_can_resize == DICT_RESIZE_AVOID && ((s1 > s0 && s1 / s0 < dict_force_resize_ratio) ||(s1 < s0 && s0 / s1 < dict_force_resize_ratio))){return 0;}while(n-- && d->ht[0].used != 0) {dictEntry *de, *nextde;/* Note that rehashidx can't overflow as we are sure there are more* elements because ht[0].used != 0 */assert(d->ht[0].size > (unsigned long)d->rehashidx);while(d->ht[0].table[d->rehashidx] == NULL) {d->rehashidx++;if (--empty_visits == 0) return 1;}de = d->ht[0].table[d->rehashidx];/* Move all the keys in this bucket from the old to the new hash HT */while(de) {uint64_t h;nextde = de->next;/* Get the index in the new hash table */h = dictHashKey(d, de->key) & d->ht[1].sizemask;de->next = d->ht[1].table[h];d->ht[1].table[h] = de;d->ht[0].used--;d->ht[1].used++;de = nextde;}d->ht[0].table[d->rehashidx] = NULL;d->rehashidx++;}/* Check if we already rehashed the whole table... */if (d->ht[0].used == 0) {zfree(d->ht[0].table);d->ht[0] = d->ht[1];_dictReset(&d->ht[1]);d->rehashidx = -1;return 0;}/* More to rehash... */return 1;
}long long timeInMilliseconds(void) {struct timeval tv;gettimeofday(&tv,NULL);return (((long long)tv.tv_sec)*1000)+(tv.tv_usec/1000);
}/* Rehash in ms+"delta" milliseconds. The value of "delta" is larger * than 0, and is smaller than 1 in most cases. The exact upper bound * depends on the running time of dictRehash(d,100).*/
int dictRehashMilliseconds(dict *d, int ms) {if (d->pauserehash > 0) return 0;long long start = timeInMilliseconds();int rehashes = 0;while(dictRehash(d,100)) {rehashes += 100;if (timeInMilliseconds()-start > ms) break;}return rehashes;
}/* This function performs just a step of rehashing, and only if hashing has* not been paused for our hash table. When we have iterators in the* middle of a rehashing we can't mess with the two hash tables otherwise* some element can be missed or duplicated.** This function is called by common lookup or update operations in the* dictionary so that the hash table automatically migrates from H1 to H2* while it is actively used. */
static void _dictRehashStep(dict *d) {if (d->pauserehash == 0) dictRehash(d,1);
}/* Add an element to the target hash table */
int dictAdd(dict *d, void *key, void *val)
{dictEntry *entry = dictAddRaw(d,key,NULL);if (!entry) return DICT_ERR;dictSetVal(d, entry, val);return DICT_OK;
}/* Low level add or find:* This function adds the entry but instead of setting a value returns the* dictEntry structure to the user, that will make sure to fill the value* field as they wish.** This function is also directly exposed to the user API to be called* mainly in order to store non-pointers inside the hash value, example:** entry = dictAddRaw(dict,mykey,NULL);* if (entry != NULL) dictSetSignedIntegerVal(entry,1000);** Return values:** If key already exists NULL is returned, and "*existing" is populated* with the existing entry if existing is not NULL.** If key was added, the hash entry is returned to be manipulated by the caller.*/
dictEntry *dictAddRaw(dict *d, void *key, dictEntry **existing)
{long index;dictEntry *entry;dictht *ht;if (dictIsRehashing(d)) _dictRehashStep(d);/* Get the index of the new element, or -1 if* the element already exists. */if ((index = _dictKeyIndex(d, key, dictHashKey(d,key), existing)) == -1)return NULL;/* Allocate the memory and store the new entry.* Insert the element in top, with the assumption that in a database* system it is more likely that recently added entries are accessed* more frequently. */ht = dictIsRehashing(d) ? &d->ht[1] : &d->ht[0];entry = zmalloc(sizeof(*entry));entry->next = ht->table[index];ht->table[index] = entry;ht->used++;/* Set the hash entry fields. */dictSetKey(d, entry, key);return entry;
}/* Add or Overwrite:* Add an element, discarding the old value if the key already exists.* Return 1 if the key was added from scratch, 0 if there was already an* element with such key and dictReplace() just performed a value update* operation. */
int dictReplace(dict *d, void *key, void *val)
{dictEntry *entry, *existing, auxentry;/* Try to add the element. If the key* does not exists dictAdd will succeed. */entry = dictAddRaw(d,key,&existing);if (entry) {dictSetVal(d, entry, val);return 1;}/* Set the new value and free the old one. Note that it is important* to do that in this order, as the value may just be exactly the same* as the previous one. In this context, think to reference counting,* you want to increment (set), and then decrement (free), and not the* reverse. */auxentry = *existing;dictSetVal(d, existing, val);dictFreeVal(d, &auxentry);return 0;
}/* Add or Find:* dictAddOrFind() is simply a version of dictAddRaw() that always* returns the hash entry of the specified key, even if the key already* exists and can't be added (in that case the entry of the already* existing key is returned.)** See dictAddRaw() for more information. */
dictEntry *dictAddOrFind(dict *d, void *key) {dictEntry *entry, *existing;entry = dictAddRaw(d,key,&existing);return entry ? entry : existing;
}/* Search and remove an element. This is an helper function for* dictDelete() and dictUnlink(), please check the top comment* of those functions. */
static dictEntry *dictGenericDelete(dict *d, const void *key, int nofree) {uint64_t h, idx;dictEntry *he, *prevHe;int table;if (d->ht[0].used == 0 && d->ht[1].used == 0) return NULL;if (dictIsRehashing(d)) _dictRehashStep(d);h = dictHashKey(d, key);for (table = 0; table <= 1; table++) {idx = h & d->ht[table].sizemask;he = d->ht[table].table[idx];prevHe = NULL;while(he) {if (key==he->key || dictCompareKeys(d, key, he->key)) {/* Unlink the element from the list */if (prevHe)prevHe->next = he->next;elsed->ht[table].table[idx] = he->next;if (!nofree) {dictFreeKey(d, he);dictFreeVal(d, he);zfree(he);}d->ht[table].used--;return he;}prevHe = he;he = he->next;}if (!dictIsRehashing(d)) break;}return NULL; /* not found */
}/* Remove an element, returning DICT_OK on success or DICT_ERR if the* element was not found. */
int dictDelete(dict *ht, const void *key) {return dictGenericDelete(ht,key,0) ? DICT_OK : DICT_ERR;
}/* Remove an element from the table, but without actually releasing* the key, value and dictionary entry. The dictionary entry is returned* if the element was found (and unlinked from the table), and the user* should later call `dictFreeUnlinkedEntry()` with it in order to release it.* Otherwise if the key is not found, NULL is returned.** This function is useful when we want to remove something from the hash* table but want to use its value before actually deleting the entry.* Without this function the pattern would require two lookups:**  entry = dictFind(...);*  // Do something with entry*  dictDelete(dictionary,entry);** Thanks to this function it is possible to avoid this, and use* instead:** entry = dictUnlink(dictionary,entry);* // Do something with entry* dictFreeUnlinkedEntry(entry); // <- This does not need to lookup again.*/
dictEntry *dictUnlink(dict *ht, const void *key) {return dictGenericDelete(ht,key,1);
}/* You need to call this function to really free the entry after a call* to dictUnlink(). It's safe to call this function with 'he' = NULL. */
void dictFreeUnlinkedEntry(dict *d, dictEntry *he) {if (he == NULL) return;dictFreeKey(d, he);dictFreeVal(d, he);zfree(he);
}/* Destroy an entire dictionary */
int _dictClear(dict *d, dictht *ht, void(callback)(void *)) {unsigned long i;/* Free all the elements */for (i = 0; i < ht->size && ht->used > 0; i++) {dictEntry *he, *nextHe;if (callback && (i & 65535) == 0) callback(d->privdata);if ((he = ht->table[i]) == NULL) continue;while(he) {nextHe = he->next;dictFreeKey(d, he);dictFreeVal(d, he);zfree(he);ht->used--;he = nextHe;}}/* Free the table and the allocated cache structure */zfree(ht->table);/* Re-initialize the table */_dictReset(ht);return DICT_OK; /* never fails */
}/* Clear & Release the hash table */
void dictRelease(dict *d)
{_dictClear(d,&d->ht[0],NULL);_dictClear(d,&d->ht[1],NULL);zfree(d);
}dictEntry *dictFind(dict *d, const void *key)
{dictEntry *he;uint64_t h, idx, table;if (dictSize(d) == 0) return NULL; /* dict is empty */if (dictIsRehashing(d)) _dictRehashStep(d);h = dictHashKey(d, key);for (table = 0; table <= 1; table++) {idx = h & d->ht[table].sizemask;he = d->ht[table].table[idx];while(he) {if (key==he->key || dictCompareKeys(d, key, he->key))return he;he = he->next;}if (!dictIsRehashing(d)) return NULL;}return NULL;
}void *dictFetchValue(dict *d, const void *key) {dictEntry *he;he = dictFind(d,key);return he ? dictGetVal(he) : NULL;
}/* A fingerprint is a 64 bit number that represents the state of the dictionary* at a given time, it's just a few dict properties xored together.* When an unsafe iterator is initialized, we get the dict fingerprint, and check* the fingerprint again when the iterator is released.* If the two fingerprints are different it means that the user of the iterator* performed forbidden operations against the dictionary while iterating. */
unsigned long long dictFingerprint(dict *d) {unsigned long long integers[6], hash = 0;int j;integers[0] = (long) d->ht[0].table;integers[1] = d->ht[0].size;integers[2] = d->ht[0].used;integers[3] = (long) d->ht[1].table;integers[4] = d->ht[1].size;integers[5] = d->ht[1].used;/* We hash N integers by summing every successive integer with the integer* hashing of the previous sum. Basically:** Result = hash(hash(hash(int1)+int2)+int3) ...** This way the same set of integers in a different order will (likely) hash* to a different number. */for (j = 0; j < 6; j++) {hash += integers[j];/* For the hashing step we use Tomas Wang's 64 bit integer hash. */hash = (~hash) + (hash << 21); // hash = (hash << 21) - hash - 1;hash = hash ^ (hash >> 24);hash = (hash + (hash << 3)) + (hash << 8); // hash * 265hash = hash ^ (hash >> 14);hash = (hash + (hash << 2)) + (hash << 4); // hash * 21hash = hash ^ (hash >> 28);hash = hash + (hash << 31);}return hash;
}dictIterator *dictGetIterator(dict *d)
{dictIterator *iter = zmalloc(sizeof(*iter));iter->d = d;iter->table = 0;iter->index = -1;iter->safe = 0;iter->entry = NULL;iter->nextEntry = NULL;return iter;
}dictIterator *dictGetSafeIterator(dict *d) {dictIterator *i = dictGetIterator(d);i->safe = 1;return i;
}dictEntry *dictNext(dictIterator *iter)
{while (1) {if (iter->entry == NULL) {dictht *ht = &iter->d->ht[iter->table];if (iter->index == -1 && iter->table == 0) {if (iter->safe)dictPauseRehashing(iter->d);elseiter->fingerprint = dictFingerprint(iter->d);}iter->index++;if (iter->index >= (long) ht->size) {if (dictIsRehashing(iter->d) && iter->table == 0) {iter->table++;iter->index = 0;ht = &iter->d->ht[1];} else {break;}}iter->entry = ht->table[iter->index];} else {iter->entry = iter->nextEntry;}if (iter->entry) {/* We need to save the 'next' here, the iterator user* may delete the entry we are returning. */iter->nextEntry = iter->entry->next;return iter->entry;}}return NULL;
}void dictReleaseIterator(dictIterator *iter)
{if (!(iter->index == -1 && iter->table == 0)) {if (iter->safe)dictResumeRehashing(iter->d);elseassert(iter->fingerprint == dictFingerprint(iter->d));}zfree(iter);
}/* Return a random entry from the hash table. Useful to* implement randomized algorithms */
dictEntry *dictGetRandomKey(dict *d)
{dictEntry *he, *orighe;unsigned long h;int listlen, listele;if (dictSize(d) == 0) return NULL;if (dictIsRehashing(d)) _dictRehashStep(d);if (dictIsRehashing(d)) {do {/* We are sure there are no elements in indexes from 0* to rehashidx-1 */h = d->rehashidx + (randomULong() % (dictSlots(d) - d->rehashidx));he = (h >= d->ht[0].size) ? d->ht[1].table[h - d->ht[0].size] :d->ht[0].table[h];} while(he == NULL);} else {do {h = randomULong() & d->ht[0].sizemask;he = d->ht[0].table[h];} while(he == NULL);}/* Now we found a non empty bucket, but it is a linked* list and we need to get a random element from the list.* The only sane way to do so is counting the elements and* select a random index. */listlen = 0;orighe = he;while(he) {he = he->next;listlen++;}listele = random() % listlen;he = orighe;while(listele--) he = he->next;return he;
}/* This function samples the dictionary to return a few keys from random* locations.** It does not guarantee to return all the keys specified in 'count', nor* it does guarantee to return non-duplicated elements, however it will make* some effort to do both things.** Returned pointers to hash table entries are stored into 'des' that* points to an array of dictEntry pointers. The array must have room for* at least 'count' elements, that is the argument we pass to the function* to tell how many random elements we need.** The function returns the number of items stored into 'des', that may* be less than 'count' if the hash table has less than 'count' elements* inside, or if not enough elements were found in a reasonable amount of* steps.** Note that this function is not suitable when you need a good distribution* of the returned items, but only when you need to "sample" a given number* of continuous elements to run some kind of algorithm or to produce* statistics. However the function is much faster than dictGetRandomKey()* at producing N elements. */
unsigned int dictGetSomeKeys(dict *d, dictEntry **des, unsigned int count) {unsigned long j; /* internal hash table id, 0 or 1. */unsigned long tables; /* 1 or 2 tables? */unsigned long stored = 0, maxsizemask;unsigned long maxsteps;if (dictSize(d) < count) count = dictSize(d);maxsteps = count*10;/* Try to do a rehashing work proportional to 'count'. */for (j = 0; j < count; j++) {if (dictIsRehashing(d))_dictRehashStep(d);elsebreak;}tables = dictIsRehashing(d) ? 2 : 1;maxsizemask = d->ht[0].sizemask;if (tables > 1 && maxsizemask < d->ht[1].sizemask)maxsizemask = d->ht[1].sizemask;/* Pick a random point inside the larger table. */unsigned long i = randomULong() & maxsizemask;unsigned long emptylen = 0; /* Continuous empty entries so far. */while(stored < count && maxsteps--) {for (j = 0; j < tables; j++) {/* Invariant of the dict.c rehashing: up to the indexes already* visited in ht[0] during the rehashing, there are no populated* buckets, so we can skip ht[0] for indexes between 0 and idx-1. */if (tables == 2 && j == 0 && i < (unsigned long) d->rehashidx) {/* Moreover, if we are currently out of range in the second* table, there will be no elements in both tables up to* the current rehashing index, so we jump if possible.* (this happens when going from big to small table). */if (i >= d->ht[1].size)i = d->rehashidx;elsecontinue;}if (i >= d->ht[j].size) continue; /* Out of range for this table. */dictEntry *he = d->ht[j].table[i];/* Count contiguous empty buckets, and jump to other* locations if they reach 'count' (with a minimum of 5). */if (he == NULL) {emptylen++;if (emptylen >= 5 && emptylen > count) {i = randomULong() & maxsizemask;emptylen = 0;}} else {emptylen = 0;while (he) {/* Collect all the elements of the buckets found non* empty while iterating. */*des = he;des++;he = he->next;stored++;if (stored == count) return stored;}}}i = (i+1) & maxsizemask;}return stored;
}/* This is like dictGetRandomKey() from the POV of the API, but will do more* work to ensure a better distribution of the returned element.** This function improves the distribution because the dictGetRandomKey()* problem is that it selects a random bucket, then it selects a random* element from the chain in the bucket. However elements being in different* chain lengths will have different probabilities of being reported. With* this function instead what we do is to consider a "linear" range of the table* that may be constituted of N buckets with chains of different lengths* appearing one after the other. Then we report a random element in the range.* In this way we smooth away the problem of different chain lengths. */
#define GETFAIR_NUM_ENTRIES 15
dictEntry *dictGetFairRandomKey(dict *d) {dictEntry *entries[GETFAIR_NUM_ENTRIES];unsigned int count = dictGetSomeKeys(d,entries,GETFAIR_NUM_ENTRIES);/* Note that dictGetSomeKeys() may return zero elements in an unlucky* run() even if there are actually elements inside the hash table. So* when we get zero, we call the true dictGetRandomKey() that will always* yield the element if the hash table has at least one. */if (count == 0) return dictGetRandomKey(d);unsigned int idx = rand() % count;return entries[idx];
}/* Function to reverse bits. Algorithm from:* http://graphics.stanford.edu/~seander/bithacks.html#ReverseParallel */
static unsigned long rev(unsigned long v) {unsigned long s = CHAR_BIT * sizeof(v); // bit size; must be power of 2unsigned long mask = ~0UL;while ((s >>= 1) > 0) {mask ^= (mask << s);v = ((v >> s) & mask) | ((v << s) & ~mask);}return v;
}/* dictScan() is used to iterate over the elements of a dictionary.** Iterating works the following way:** 1) Initially you call the function using a cursor (v) value of 0.* 2) The function performs one step of the iteration, and returns the*    new cursor value you must use in the next call.* 3) When the returned cursor is 0, the iteration is complete.** The function guarantees all elements present in the* dictionary get returned between the start and end of the iteration.* However it is possible some elements get returned multiple times.** For every element returned, the callback argument 'fn' is* called with 'privdata' as first argument and the dictionary entry* 'de' as second argument.** HOW IT WORKS.** The iteration algorithm was designed by Pieter Noordhuis.* The main idea is to increment a cursor starting from the higher order* bits. That is, instead of incrementing the cursor normally, the bits* of the cursor are reversed, then the cursor is incremented, and finally* the bits are reversed again.** This strategy is needed because the hash table may be resized between* iteration calls.** dict.c hash tables are always power of two in size, and they* use chaining, so the position of an element in a given table is given* by computing the bitwise AND between Hash(key) and SIZE-1* (where SIZE-1 is always the mask that is equivalent to taking the rest*  of the division between the Hash of the key and SIZE).** For example if the current hash table size is 16, the mask is* (in binary) 1111. The position of a key in the hash table will always be* the last four bits of the hash output, and so forth.** WHAT HAPPENS IF THE TABLE CHANGES IN SIZE?** If the hash table grows, elements can go anywhere in one multiple of* the old bucket: for example let's say we already iterated with* a 4 bit cursor 1100 (the mask is 1111 because hash table size = 16).** If the hash table will be resized to 64 elements, then the new mask will* be 111111. The new buckets you obtain by substituting in ??1100* with either 0 or 1 can be targeted only by keys we already visited* when scanning the bucket 1100 in the smaller hash table.** By iterating the higher bits first, because of the inverted counter, the* cursor does not need to restart if the table size gets bigger. It will* continue iterating using cursors without '1100' at the end, and also* without any other combination of the final 4 bits already explored.** Similarly when the table size shrinks over time, for example going from* 16 to 8, if a combination of the lower three bits (the mask for size 8* is 111) were already completely explored, it would not be visited again* because we are sure we tried, for example, both 0111 and 1111 (all the* variations of the higher bit) so we don't need to test it again.** WAIT... YOU HAVE *TWO* TABLES DURING REHASHING!** Yes, this is true, but we always iterate the smaller table first, then* we test all the expansions of the current cursor into the larger* table. For example if the current cursor is 101 and we also have a* larger table of size 16, we also test (0)101 and (1)101 inside the larger* table. This reduces the problem back to having only one table, where* the larger one, if it exists, is just an expansion of the smaller one.** LIMITATIONS** This iterator is completely stateless, and this is a huge advantage,* including no additional memory used.** The disadvantages resulting from this design are:** 1) It is possible we return elements more than once. However this is usually*    easy to deal with in the application level.* 2) The iterator must return multiple elements per call, as it needs to always*    return all the keys chained in a given bucket, and all the expansions, so*    we are sure we don't miss keys moving during rehashing.* 3) The reverse cursor is somewhat hard to understand at first, but this*    comment is supposed to help.*/
unsigned long dictScan(dict *d,unsigned long v,dictScanFunction *fn,dictScanBucketFunction* bucketfn,void *privdata)
{dictht *t0, *t1;const dictEntry *de, *next;unsigned long m0, m1;if (dictSize(d) == 0) return 0;/* This is needed in case the scan callback tries to do dictFind or alike. */dictPauseRehashing(d);if (!dictIsRehashing(d)) {t0 = &(d->ht[0]);m0 = t0->sizemask;/* Emit entries at cursor */if (bucketfn) bucketfn(privdata, &t0->table[v & m0]);de = t0->table[v & m0];while (de) {next = de->next;fn(privdata, de);de = next;}/* Set unmasked bits so incrementing the reversed cursor* operates on the masked bits */v |= ~m0;/* Increment the reverse cursor */v = rev(v);v++;v = rev(v);} else {t0 = &d->ht[0];t1 = &d->ht[1];/* Make sure t0 is the smaller and t1 is the bigger table */if (t0->size > t1->size) {t0 = &d->ht[1];t1 = &d->ht[0];}m0 = t0->sizemask;m1 = t1->sizemask;/* Emit entries at cursor */if (bucketfn) bucketfn(privdata, &t0->table[v & m0]);de = t0->table[v & m0];while (de) {next = de->next;fn(privdata, de);de = next;}/* Iterate over indices in larger table that are the expansion* of the index pointed to by the cursor in the smaller table */do {/* Emit entries at cursor */if (bucketfn) bucketfn(privdata, &t1->table[v & m1]);de = t1->table[v & m1];while (de) {next = de->next;fn(privdata, de);de = next;}/* Increment the reverse cursor not covered by the smaller mask.*/v |= ~m1;v = rev(v);v++;v = rev(v);/* Continue while bits covered by mask difference is non-zero */} while (v & (m0 ^ m1));}dictResumeRehashing(d);return v;
}/* ------------------------- private functions ------------------------------ *//* Because we may need to allocate huge memory chunk at once when dict* expands, we will check this allocation is allowed or not if the dict* type has expandAllowed member function. */
static int dictTypeExpandAllowed(dict *d) {if (d->type->expandAllowed == NULL) return 1;return d->type->expandAllowed(_dictNextPower(d->ht[0].used + 1) * sizeof(dictEntry*),(double)d->ht[0].used / d->ht[0].size);
}/* Expand the hash table if needed */
static int _dictExpandIfNeeded(dict *d)
{/* Incremental rehashing already in progress. Return. */if (dictIsRehashing(d)) return DICT_OK;/* If the hash table is empty expand it to the initial size. */if (d->ht[0].size == 0) return dictExpand(d, DICT_HT_INITIAL_SIZE);/* If we reached the 1:1 ratio, and we are allowed to resize the hash* table (global setting) or we should avoid it but the ratio between* elements/buckets is over the "safe" threshold, we resize doubling* the number of buckets. */if (!dictTypeExpandAllowed(d))return DICT_OK;if ((dict_can_resize == DICT_RESIZE_ENABLE &&d->ht[0].used >= d->ht[0].size) ||(dict_can_resize != DICT_RESIZE_FORBID &&d->ht[0].used / d->ht[0].size > dict_force_resize_ratio)){return dictExpand(d, d->ht[0].used + 1);}return DICT_OK;
}/* Our hash table capability is a power of two */
static unsigned long _dictNextPower(unsigned long size)
{unsigned long i = DICT_HT_INITIAL_SIZE;if (size >= LONG_MAX) return LONG_MAX + 1LU;while(1) {if (i >= size)return i;i *= 2;}
}/* Returns the index of a free slot that can be populated with* a hash entry for the given 'key'.* If the key already exists, -1 is returned* and the optional output parameter may be filled.** Note that if we are in the process of rehashing the hash table, the* index is always returned in the context of the second (new) hash table. */
static long _dictKeyIndex(dict *d, const void *key, uint64_t hash, dictEntry **existing)
{unsigned long idx, table;dictEntry *he;if (existing) *existing = NULL;/* Expand the hash table if needed */if (_dictExpandIfNeeded(d) == DICT_ERR)return -1;for (table = 0; table <= 1; table++) {idx = hash & d->ht[table].sizemask;/* Search if this slot does not already contain the given key */he = d->ht[table].table[idx];while(he) {if (key==he->key || dictCompareKeys(d, key, he->key)) {if (existing) *existing = he;return -1;}he = he->next;}if (!dictIsRehashing(d)) break;}return idx;
}void dictEmpty(dict *d, void(callback)(void*)) {_dictClear(d,&d->ht[0],callback);_dictClear(d,&d->ht[1],callback);d->rehashidx = -1;d->pauserehash = 0;
}void dictSetResizeEnabled(dictResizeEnable enable) {dict_can_resize = enable;
}uint64_t dictGetHash(dict *d, const void *key) {return dictHashKey(d, key);
}/* Finds the dictEntry reference by using pointer and pre-calculated hash.* oldkey is a dead pointer and should not be accessed.* the hash value should be provided using dictGetHash.* no string / key comparison is performed.* return value is the reference to the dictEntry if found, or NULL if not found. */
dictEntry **dictFindEntryRefByPtrAndHash(dict *d, const void *oldptr, uint64_t hash) {dictEntry *he, **heref;unsigned long idx, table;if (dictSize(d) == 0) return NULL; /* dict is empty */for (table = 0; table <= 1; table++) {idx = hash & d->ht[table].sizemask;heref = &d->ht[table].table[idx];he = *heref;while(he) {if (oldptr==he->key)return heref;heref = &he->next;he = *heref;}if (!dictIsRehashing(d)) return NULL;}return NULL;
}/* ------------------------------- Debugging ---------------------------------*/#define DICT_STATS_VECTLEN 50
size_t _dictGetStatsHt(char *buf, size_t bufsize, dictht *ht, int tableid) {unsigned long i, slots = 0, chainlen, maxchainlen = 0;unsigned long totchainlen = 0;unsigned long clvector[DICT_STATS_VECTLEN];size_t l = 0;if (ht->used == 0) {return snprintf(buf,bufsize,"Hash table %d stats (%s):\n""No stats available for empty dictionaries\n",tableid, (tableid == 0) ? "main hash table" : "rehashing target");}/* Compute stats. */for (i = 0; i < DICT_STATS_VECTLEN; i++) clvector[i] = 0;for (i = 0; i < ht->size; i++) {dictEntry *he;if (ht->table[i] == NULL) {clvector[0]++;continue;}slots++;/* For each hash entry on this slot... */chainlen = 0;he = ht->table[i];while(he) {chainlen++;he = he->next;}clvector[(chainlen < DICT_STATS_VECTLEN) ? chainlen : (DICT_STATS_VECTLEN-1)]++;if (chainlen > maxchainlen) maxchainlen = chainlen;totchainlen += chainlen;}/* Generate human readable stats. */l += snprintf(buf+l,bufsize-l,"Hash table %d stats (%s):\n"" table size: %lu\n"" number of elements: %lu\n"" different slots: %lu\n"" max chain length: %lu\n"" avg chain length (counted): %.02f\n"" avg chain length (computed): %.02f\n"" Chain length distribution:\n",tableid, (tableid == 0) ? "main hash table" : "rehashing target",ht->size, ht->used, slots, maxchainlen,(float)totchainlen/slots, (float)ht->used/slots);for (i = 0; i < DICT_STATS_VECTLEN-1; i++) {if (clvector[i] == 0) continue;if (l >= bufsize) break;l += snprintf(buf+l,bufsize-l,"   %s%ld: %ld (%.02f%%)\n",(i == DICT_STATS_VECTLEN-1)?">= ":"",i, clvector[i], ((float)clvector[i]/ht->size)*100);}/* Unlike snprintf(), return the number of characters actually written. */if (bufsize) buf[bufsize-1] = '\0';return strlen(buf);
}void dictGetStats(char *buf, size_t bufsize, dict *d) {size_t l;char *orig_buf = buf;size_t orig_bufsize = bufsize;l = _dictGetStatsHt(buf,bufsize,&d->ht[0],0);buf += l;bufsize -= l;if (dictIsRehashing(d) && bufsize > 0) {_dictGetStatsHt(buf,bufsize,&d->ht[1],1);}/* Make sure there is a NULL term at the end. */if (orig_bufsize) orig_buf[orig_bufsize-1] = '\0';
}/* ------------------------------- Benchmark ---------------------------------*/#ifdef REDIS_TESTuint64_t hashCallback(const void *key) {return dictGenHashFunction((unsigned char*)key, strlen((char*)key));
}int compareCallback(void *privdata, const void *key1, const void *key2) {int l1,l2;DICT_NOTUSED(privdata);l1 = strlen((char*)key1);l2 = strlen((char*)key2);if (l1 != l2) return 0;return memcmp(key1, key2, l1) == 0;
}void freeCallback(void *privdata, void *val) {DICT_NOTUSED(privdata);zfree(val);
}char *stringFromLongLong(long long value) {char buf[32];int len;char *s;len = sprintf(buf,"%lld",value);s = zmalloc(len+1);memcpy(s, buf, len);s[len] = '\0';return s;
}dictType BenchmarkDictType = {hashCallback,NULL,NULL,compareCallback,freeCallback,NULL,NULL
};#define start_benchmark() start = timeInMilliseconds()
#define end_benchmark(msg) do { \elapsed = timeInMilliseconds()-start; \printf(msg ": %ld items in %lld ms\n", count, elapsed); \
} while(0)/* ./redis-server test dict [<count> | --accurate] */
int dictTest(int argc, char **argv, int accurate) {long j;long long start, elapsed;dict *dict = dictCreate(&BenchmarkDictType,NULL);long count = 0;if (argc == 4) {if (accurate) {count = 5000000;} else {count = strtol(argv[3],NULL,10);}} else {count = 5000;}start_benchmark();for (j = 0; j < count; j++) {int retval = dictAdd(dict,stringFromLongLong(j),(void*)j);assert(retval == DICT_OK);}end_benchmark("Inserting");assert((long)dictSize(dict) == count);/* Wait for rehashing. */while (dictIsRehashing(dict)) {dictRehashMilliseconds(dict,100);}start_benchmark();for (j = 0; j < count; j++) {char *key = stringFromLongLong(j);dictEntry *de = dictFind(dict,key);assert(de != NULL);zfree(key);}end_benchmark("Linear access of existing elements");start_benchmark();for (j = 0; j < count; j++) {char *key = stringFromLongLong(j);dictEntry *de = dictFind(dict,key);assert(de != NULL);zfree(key);}end_benchmark("Linear access of existing elements (2nd round)");start_benchmark();for (j = 0; j < count; j++) {char *key = stringFromLongLong(rand() % count);dictEntry *de = dictFind(dict,key);assert(de != NULL);zfree(key);}end_benchmark("Random access of existing elements");start_benchmark();for (j = 0; j < count; j++) {dictEntry *de = dictGetRandomKey(dict);assert(de != NULL);}end_benchmark("Accessing random keys");start_benchmark();for (j = 0; j < count; j++) {char *key = stringFromLongLong(rand() % count);key[0] = 'X';dictEntry *de = dictFind(dict,key);assert(de == NULL);zfree(key);}end_benchmark("Accessing missing");start_benchmark();for (j = 0; j < count; j++) {char *key = stringFromLongLong(j);int retval = dictDelete(dict,key);assert(retval == DICT_OK);key[0] += 17; /* Change first number to letter. */retval = dictAdd(dict,key,(void*)j);assert(retval == DICT_OK);}end_benchmark("Removing and adding");dictRelease(dict);return 0;
}
#endif
#include <stdio.h>
#include <stdint.h>
#include "dict.h"#define sdslen strlen/* -------------------------- hash functions -------------------------------- *//* Generic hash function (a popular one from Bernstein).* I tested a few and this was the best. */
// static unsigned int dictGenHashFunction(const unsigned char *buf, int len) {
//     unsigned int hash = 5381;//     while (len--)
//         hash = ((hash << 5) + hash) + (*buf++); /* hash * 33 + c */
//     return hash;
// }uint64_t dictSdsHash(const void *key) {return dictGenHashFunction((unsigned char*)key, sdslen((char*)key));
}int dictSdsKeyCompare(void *privdata, const void *key1,const void *key2)
{int l1,l2;DICT_NOTUSED(privdata);// l1 = sdslen((sds)key1);// l2 = sdslen((sds)key2);// if (l1 != l2) return 0;return memcmp(key1, key2, l1) == 0;
}/* Dict type without destructor */
dictType sdsReplyDictType = {dictSdsHash,                /* hash function */NULL,                       /* key dup */NULL,                       /* val dup */dictSdsKeyCompare,          /* key compare */NULL,                       /* key destructor */NULL,                       /* val destructor */NULL                        /* allow to expand */
};#define serverAssert(_e) (_e)?(void)0 : (fprintf(stderr, "==> '%s' is not true [%s:%d]\n", #_e,__FILE__,__LINE__))typedef struct _MapEntry 
{char *key;char *value;
}MapEntry_t;int main()
{int index = 0;dict *dictHd = dictCreate(&sdsReplyDictType, NULL);if(NULL == dictHd){printf("NULL == entry\n");return -1;}dictExpand(dictHd, 1024);MapEntry_t mapEntry[] = {[0] = {"key1", "1"},[1] = {"key2", "2"},[2] = {"key3", "3"},};int numcommands = sizeof(mapEntry)/sizeof(MapEntry_t);printf("numcommands %d \n", numcommands);for(index = 0; index < numcommands; index++){printf("add:  key: %s, value: %s\n", mapEntry[index].key, mapEntry[index].value);int retVal  = dictAdd(dictHd, (void *)mapEntry[index].key, (void *)mapEntry[index].value);serverAssert(retVal == DICT_OK);}dictEntry *find = NULL;find =  dictFind(dictHd, mapEntry[0].key);serverAssert(find != NULL); printf("key %s, value %s\n", mapEntry[0].key, find->v.val);if (find != NULL)dictReplace(dictHd, mapEntry[0].key, "11");find =  dictFind(dictHd, mapEntry[0].key);serverAssert(find != NULL);if (find != NULL) printf("key %s, value %s\n", mapEntry[0].key, find->v.val);dictDelete(dictHd, mapEntry[0].key);find =  dictFind(dictHd, mapEntry[0].key);serverAssert(find != NULL);if (find != NULL) printf("key %s, value %s\n", mapEntry[0].key, find->v.val);find =  dictFind(dictHd, mapEntry[2].key);serverAssert(find != NULL);if (find != NULL) printf("key %s %s, value %s\n", mapEntry[2].key, find->key,find->v.val);return 0;
}
  • result

在这里插入图片描述

  • 完整代码
    https://github.com/AntigravityCC/hash_map_from_redis

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/308183.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

【spring】AOP切面注解学习(二)

文接上篇&#xff1a;【spring】AOP切面注解学习&#xff08;一&#xff09; AOP切面注解测试示例代码 示例代码 一 maven的pom文件导入 <dependency><groupId>org.springframework</groupId><artifactId>spring-aop</artifactId></depende…

某次众测的加解密对抗

前言 起源于某次众测中&#xff0c;遇到请求包响应包全密文的情况&#xff0c;最终实现burp中加解密。 用到的工具有 sekiro&#xff08;rpc转发&#xff09;flask&#xff08;autodecoder自定义接口&#xff09;autodecoder&#xff08;burp插件转发&#xff09; debug部分…

说说我理解的数据库中的Schema吧

一、SQL标准对schema如何定义&#xff1f; ISO/IEC 9075-1 SQL标准中将schema定义为描述符的持久命名集合&#xff08;a persistent, named collection of descriptors&#xff09;。 大部分的网上资料定义Schema如下&#xff1a; schema是用来组织和管理数据的一种方式。它…

【LAMMPS学习】八、基础知识(2.7)NEMD 模拟

8. 基础知识 此部分描述了如何使用 LAMMPS 为用户和开发人员执行各种任务。术语表页面还列出了 MD 术语&#xff0c;以及相应 LAMMPS 手册页的链接。 LAMMPS 源代码分发的 examples 目录中包含的示例输入脚本以及示例脚本页面上突出显示的示例输入脚本还展示了如何设置和运行各…

Linux的学习之路:9、冯诺依曼与进程(1)

摘要 本章主要是说一下冯诺依曼体系结构和进程的一部分东西。 目录 摘要 一、冯诺依曼体系结构 二、操作系统的概念 三、设计OS的目的 四、管理 五、进程的基本概念 六、PCB 七、在Linux环境下查看进程 八、使用代码创建进程 九、思维导图 一、冯诺依曼体系结构 如…

【每日一算】冒泡算法

冒泡算法就是给数据排序的意思。比如说升序&#xff0c;17&#xff0c;8&#xff0c;9&#xff0c;28&#xff0c;5.升序之后的结果就是5&#xff0c;8&#xff0c;9&#xff0c;17&#xff0c;28. 从我们的大脑思维来看&#xff0c;结果一眼就有了&#xff0c;可是机器要怎么才…

排序1——C语言

排序 1. 复杂度2. 插入排序2.1 直接插入排序2.2 希尔排序 3. 选择排序3.1 直接选择排序3.2 堆排序 排序在生活中很常见&#xff0c;比如在网购时&#xff0c;按价格排序&#xff0c;按好评数排序&#xff0c;点餐时&#xff0c;按评分排序等等。而排序有快和慢&#xff0c;快的…

【排序 贪心】3107. 使数组中位数等于 K 的最少操作数

算法可以发掘本质&#xff0c;如&#xff1a; 一&#xff0c;若干师傅和徒弟互有好感&#xff0c;有好感的师徒可以结对学习。师傅和徒弟都只能参加一个对子。如何让对子最多。 二&#xff0c;有无限多1X2和2X1的骨牌&#xff0c;某个棋盘若干格子坏了&#xff0c;如何在没有坏…

C语言中抽象的编译和链接原理

今天04.12&#xff0c;身体小有不适&#xff0c;但是睡不着觉&#xff0c;秉着不能浪费时间的原则&#xff0c;现在就简单写一下有关我们C语言中编译和链接的大体过程吧&#xff0c;因为编译和链接是比较抽象的&#xff0c;而且内容是比较底层&#xff0c;我们这里就简单了解它…

Chatgpt掘金之旅—有爱AI商业实战篇|SEO 咨询业务|(十七)

演示站点&#xff1a; https://ai.uaai.cn 对话模块 官方论坛&#xff1a; www.jingyuai.com 京娱AI 一、AI技术创业在SEO 咨询业务有哪些机会&#xff1f; 人工智能&#xff08;AI&#xff09;技术作为当今科技创新的前沿领域&#xff0c;为创业者提供了广阔的机会和挑战。随…

策略模式(知识点)——设计模式学习笔记

文章目录 0 概念1 使用场景2 优缺点2.1 优点2.2 缺点 3 实现方式4 和其他模式的区别5 具体例子实现5.1 实现代码 0 概念 定义&#xff1a;定义一个算法族&#xff0c;并分别封装起来。策略让算法的变化独立于它的客户&#xff08;这样就可在不修改上下文代码或其他策略的情况下…

蓝桥杯 每天2题 day6

碎碎念&#xff1a;哇咔咔 要不是中间缺勤一天就圆满day7了&#xff01;最后一晚上&#xff01;写题复习哇咔咔 唉&#xff0c;睡了一觉就看不下去了&#xff0c;&#xff0c;&#xff0c;看看之前的笔记洗洗睡觉&#xff0c;&#xff0c;&#xff0c; 记得打印准考证带好东西…

Java面试篇9——并发编程

并发编程知识梳理 提示&#xff0c;此仅为面试&#xff0c;若想对线程有跟完整了解&#xff0c;请点击这里 提示&#xff1a;直接翻到最后面看面试真题&#xff0c;上面的为详解 面试考点 文档说明 在文档中对所有的面试题都进行了难易程度和出现频率的等级说明 星数越多代表…

LeetCode34:在排序数组中查找元素的第一个和最后一个位置(Java)

目录 题目&#xff1a; 题解&#xff1a; 方法一&#xff1a; 方法二&#xff1a; 题目&#xff1a; 给你一个按照非递减顺序排列的整数数组 nums&#xff0c;和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。 如果数组中不存在目标值 target&…

3D场景编辑方法——CustomNeRF

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 摘要Abstract文献阅读&#xff1a;3D场景编辑方法——CustomNeRF1、研究背景2、提出方法3、CustomNeRF3.1、整体框架步骤3.2、对特定问题的解决 4、实验结果5、总结…

一辆汽车的节拍时间是怎样的?

节拍时间&#xff0c;又称 takt time&#xff0c;是德语中“节奏”的意思。在汽车制造业中&#xff0c;它指的是按照客户需求和生产计划&#xff0c;生产一辆汽车所需的时间。这个时间是固定的&#xff0c;它决定了生产线上每个工序的操作速度和节奏&#xff0c;是生产线上所有…

配置交换机 SSH 管理和端口安全

实验1:配置交换机基本安全和 SSH管理 1、实验目的 通过本实验可以掌握&#xff1a; 交换机基本安全配置。SSH 的工作原理和 SSH服务端和客户端的配置。 2、实验拓扑 交换机基本安全和 SSH管理实验拓扑如图所示。 3、实验步骤 &#xff08;1&#xff09;配置交换机S1 Swit…

liunx系统发布.net core项目

liunx系统发布.net core项目 准备.net6程序运行环境部署nginx&#xff0c;通过一个地址既能访问web api&#xff0c;又能访问web项目有一个客户把web api放到docker中&#xff0c;想通过nginx转发&#xff0c;nginx也支持配置多个程序api接口的其它 liunx系统&#xff1a;cento…

SQL执行流程图文分析:从连接到执行的全貌

SQL执行总流程 下面就是 MySQL 执行一条 SQL 查询语句的流程&#xff0c;也从图中可以看到 MySQL 内部架构里的各个功能模块。 MySQL 的架构共分为两层&#xff1a;Server 层和存储引擎层&#xff0c; Server 层负责建立连接、分析和执行 SQL。MySQL 大多数的核心功能模块都在…

STM32利用软件I2C通讯读MPU6050的ID号

今天的读ID号是建立在上篇文章中有了底层的I2C通讯的6个基本时序来编写的。首先需要完成的就是MPU6050的初始化函数 然后就是编写 指定地址写函数&#xff1a; 一&#xff1a;开始 二&#xff1a;发送 从机地址读写位&#xff08;1&#xff1a;读 0&#xff1…