diff options
Diffstat (limited to 'examples/redis-unstable/src/dict.c')
| -rw-r--r-- | examples/redis-unstable/src/dict.c | 2340 |
1 files changed, 0 insertions, 2340 deletions
diff --git a/examples/redis-unstable/src/dict.c b/examples/redis-unstable/src/dict.c deleted file mode 100644 index d0885ff..0000000 --- a/examples/redis-unstable/src/dict.c +++ /dev/null @@ -1,2340 +0,0 @@ -/* 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-Present, Redis Ltd. - * All rights reserved. - * - * Licensed under your choice of (a) the Redis Source Available License 2.0 - * (RSALv2); or (b) the Server Side Public License v1 (SSPLv1); or (c) the - * GNU Affero General Public License v3 (AGPLv3). - */ - -#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 <stddef.h> - -#include "dict.h" -#include "zmalloc.h" -#include "redisassert.h" -#include "monotonic.h" -#include "util.h" - -/* Using dictSetResizeEnabled() 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 DICT_RESIZE_AVOID, not all - * resizes are prevented: - * - A hash table is still allowed to expand if the ratio between the number - * of elements and the buckets >= dict_force_resize_ratio. - * - A hash table is still allowed to shrink if the ratio between the number - * of elements and the buckets <= 1 / (HASHTABLE_MIN_FILL * dict_force_resize_ratio). */ -static dictResizeEnable dict_can_resize = DICT_RESIZE_ENABLE; -static unsigned int dict_force_resize_ratio = 4; - -/* -------------------------- types ----------------------------------------- */ -struct dictEntry { - struct dictEntry *next; /* Must be first */ - void *key; /* Must be second */ - union { - void *val; - uint64_t u64; - int64_t s64; - double d; - } v; -}; - -typedef struct dictEntryNoValue { - dictEntry *next; /* Must be first */ - void *key; /* Must be second */ -} dictEntryNoValue; - -static_assert(offsetof(dictEntry, next) == offsetof(dictEntryNoValue, next), "dictEntry & dictEntryNoValue next not aligned"); -static_assert(offsetof(dictEntry, key) == offsetof(dictEntryNoValue, key), "dictEntry & dictEntryNoValue key not aligned"); - -/* -------------------------- private prototypes ---------------------------- */ - -static int _dictExpandIfNeeded(dict *d); -static void _dictShrinkIfNeeded(dict *d); -static void _dictRehashStepIfNeeded(dict *d, uint64_t visitedIdx); -static signed char _dictNextExp(unsigned long size); -static int _dictInit(dict *d, dictType *type); -static dictEntryLink dictGetNextLink(dictEntry *de); -static void dictSetNext(dictEntry *de, dictEntry *next); -static int dictDefaultCompare(dictCmpCache *cache, const void *key1, const void *key2); -static dictEntryLink dictFindLinkInternal(dict *d, const void *key, dictEntryLink *bucket); -dictEntryLink dictFindLinkForInsert(dict *d, const void *key, dictEntry **existing); -static dictEntry *dictInsertKeyAtLink(dict *d, void *key __stored_key, dictEntryLink link); - -/* -------------------------- unused --------------------------- */ -void dictSetSignedIntegerVal(dictEntry *de, int64_t val); -int64_t dictGetSignedIntegerVal(const dictEntry *de); -double dictIncrDoubleVal(dictEntry *de, double val); -void *dictEntryMetadata(dictEntry *de); -int64_t dictIncrSignedIntegerVal(dictEntry *de, int64_t val); - -/* -------------------------- misc inline functions -------------------------------- */ - -typedef int (*keyCmpFunc)(dictCmpCache *cache, const void *key1, const void *key2); -static inline keyCmpFunc dictGetCmpFunc(dict *d) { - if (d->type->keyCompare) - return d->type->keyCompare; - return dictDefaultCompare; -} - -static const void *dictStoredKey2Key(dict *d, const void *key __stored_key) { - return (d->type->keyFromStoredKey) ? d->type->keyFromStoredKey(key) : key; -} - -/* -------------------------- 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)); -} - -/* 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, size_t len) { - return siphash(key, len, dict_hash_function_seed); -} - -uint64_t dictGenCaseHashFunction(const unsigned char *buf, size_t len) { - return siphash_nocase(buf,len,dict_hash_function_seed); -} - -/* --------------------- dictEntry pointer bit tricks ---------------------- */ - -/* The 3 least significant bits in a pointer to a dictEntry determines what the - * pointer actually points to. If the least bit is set, it's a key. Otherwise, - * the bit pattern of the least 3 significant bits mark the kind of entry. */ - -#define ENTRY_PTR_MASK 7 /* 111 */ -#define ENTRY_PTR_NORMAL 0 /* 000 : If a pointer to an entry with value. */ -#define ENTRY_PTR_IS_ODD_KEY 1 /* XX1 : If a pointer to odd key address (must be 1). */ -#define ENTRY_PTR_IS_EVEN_KEY 2 /* 010 : If a pointer to even key address. (must be 2 or 4). */ -#define ENTRY_PTR_UNUSED 4 /* 100 : Unused. */ - -/* Returns 1 if the entry pointer is a pointer to a key, rather than to an - * allocated entry. Returns 0 otherwise. */ -static inline int entryIsKey(const dictEntry *de) { - return ((uintptr_t)de & (ENTRY_PTR_IS_ODD_KEY | ENTRY_PTR_IS_EVEN_KEY)); -} - -/* Returns 1 if the pointer is actually a pointer to a dictEntry struct. Returns - * 0 otherwise. */ -static inline int entryIsNormal(const dictEntry *de) { - return ((uintptr_t)(void *)de & ENTRY_PTR_MASK) == ENTRY_PTR_NORMAL; -} - -/* Creates an entry without a value field. */ -static inline dictEntry *createEntryNoValue(void *key __stored_key, dictEntry *next) { - dictEntryNoValue *entry = zmalloc(sizeof(*entry)); - entry->key = key; - entry->next = next; - return (dictEntry *) entry; -} - -static inline dictEntry *encodeMaskedPtr(const void *ptr, unsigned int bits) { - assert(((uintptr_t)ptr & ENTRY_PTR_MASK) == 0); - return (dictEntry *)(void *)((uintptr_t)ptr | bits); -} - -static inline void *decodeMaskedPtr(const dictEntry *de) { - return (void *)((uintptr_t)(void *)de & ~ENTRY_PTR_MASK); -} - -/* Encode a key pointer for storage in a no_value dict bucket. - * For odd keys (like SDS strings), the key can be stored directly. - * For even keys, we need to tag it with ENTRY_PTR_IS_EVEN_KEY. */ -static inline dictEntry *encodeEntryKey(dict *d, void *key) { - if (d->type->keys_are_odd) { - debugAssert(((uintptr_t)key & ENTRY_PTR_IS_ODD_KEY) == ENTRY_PTR_IS_ODD_KEY); - return key; - } else { - return encodeMaskedPtr(key, ENTRY_PTR_IS_EVEN_KEY); - } -} - -/* Decodes the pointer to an entry without value, when you know it is an entry - * without value. Hint: Use entryIsNoValue to check. */ -static inline dictEntryNoValue *decodeEntryNoValue(const dictEntry *de) { - return decodeMaskedPtr(de); -} - -/* Returns 1 if the entry has a value field and 0 otherwise. */ -static inline int entryHasValue(const dictEntry *de) { - return entryIsNormal(de); -} - -/* ----------------------------- API implementation ------------------------- */ - -/* Reset hash table parameters already initialized with _dictInit()*/ -static void _dictReset(dict *d, int htidx) -{ - d->ht_table[htidx] = NULL; - d->ht_size_exp[htidx] = -1; - d->ht_used[htidx] = 0; -} - -/* Create a new hash table */ -dict *dictCreate(dictType *type) -{ - size_t metasize = type->dictMetadataBytes ? type->dictMetadataBytes(NULL) : 0; - dict *d = zmalloc(sizeof(*d)+metasize); - if (metasize > 0) { - memset(dictMetadata(d), 0, metasize); - } - _dictInit(d,type); - return d; -} - -/* Change dictType of dict to another one with metadata support - * Rest of dictType's values must stay the same */ -void dictTypeAddMeta(dict **d, dictType *typeWithMeta) { - /* Verify new dictType is compatible with the old one */ - dictType toCmp = *typeWithMeta; - /* Ignore 'dictMetadataBytes' and 'onDictRelease' in comparison */ - toCmp.dictMetadataBytes = (*d)->type->dictMetadataBytes; - toCmp.onDictRelease = (*d)->type->onDictRelease; - assert(memcmp((*d)->type, &toCmp, sizeof(dictType)) == 0); /* The rest of the dictType fields must be the same */ - - *d = zrealloc(*d, sizeof(dict) + typeWithMeta->dictMetadataBytes(*d)); - (*d)->type = typeWithMeta; -} - -/* Initialize the hash table */ -int _dictInit(dict *d, dictType *type) -{ - _dictReset(d, 0); - _dictReset(d, 1); - d->type = type; - d->rehashidx = -1; - d->pauserehash = 0; - d->pauseAutoResize = 0; - return DICT_OK; -} - -/* Resize 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 resize was performed, and DICT_ERR if skipped. */ -int _dictResize(dict *d, unsigned long size, int* malloc_failed) -{ - if (malloc_failed) *malloc_failed = 0; - - /* We can't rehash twice if rehashing is ongoing. */ - assert(!dictIsRehashing(d)); - - /* the new hash table */ - dictEntry **new_ht_table; - unsigned long new_ht_used; - signed char new_ht_size_exp = _dictNextExp(size); - - /* Detect overflows */ - size_t newsize = DICTHT_SIZE(new_ht_size_exp); - if (newsize < size || newsize * sizeof(dictEntry*) < newsize) - return DICT_ERR; - - /* Rehashing to the same table size is not useful. */ - if (new_ht_size_exp == d->ht_size_exp[0]) return DICT_ERR; - - /* Allocate the new hash table and initialize all pointers to NULL */ - if (malloc_failed) { - new_ht_table = ztrycalloc(newsize*sizeof(dictEntry*)); - *malloc_failed = new_ht_table == NULL; - if (*malloc_failed) - return DICT_ERR; - } else - new_ht_table = zcalloc(newsize*sizeof(dictEntry*)); - - new_ht_used = 0; - - /* Prepare a second hash table for incremental rehashing. - * We do this even for the first initialization, so that we can trigger the - * rehashingStarted more conveniently, we will clean it up right after. */ - d->ht_size_exp[1] = new_ht_size_exp; - d->ht_used[1] = new_ht_used; - d->ht_table[1] = new_ht_table; - d->rehashidx = 0; - if (d->type->rehashingStarted) d->type->rehashingStarted(d); - if (d->type->bucketChanged) - d->type->bucketChanged(d, DICTHT_SIZE(d->ht_size_exp[1])); - - /* Is this the first initialization or is the first hash table empty? If so - * it's not really a rehashing, we can just set the first hash table so that - * it can accept keys. */ - if (d->ht_table[0] == NULL || d->ht_used[0] == 0) { - if (d->type->rehashingCompleted) d->type->rehashingCompleted(d); - if (d->type->bucketChanged) - d->type->bucketChanged(d, -(long long)DICTHT_SIZE(d->ht_size_exp[0])); - if (d->ht_table[0]) zfree(d->ht_table[0]); - d->ht_size_exp[0] = new_ht_size_exp; - d->ht_used[0] = new_ht_used; - d->ht_table[0] = new_ht_table; - _dictReset(d, 1); - d->rehashidx = -1; - return DICT_OK; - } - - /* Force a full rehashing of the dictionary */ - if (d->type->force_full_rehash) { - while (dictRehash(d, 1000)) { - /* Continue rehashing */ - } - } - return DICT_OK; -} - -int _dictExpand(dict *d, unsigned long size, int* malloc_failed) { - /* the size is invalid if it is smaller than the size of the hash table - * or smaller than the number of elements already inside the hash table */ - if (dictIsRehashing(d) || d->ht_used[0] > size || DICTHT_SIZE(d->ht_size_exp[0]) >= size) - return DICT_ERR; - return _dictResize(d, size, malloc_failed); -} - -/* 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 = 0; - _dictExpand(d, size, &malloc_failed); - return malloc_failed? DICT_ERR : DICT_OK; -} - -/* return DICT_ERR if shrink was not performed */ -int dictShrink(dict *d, unsigned long size) { - /* the size is invalid if it is bigger than the size of the hash table - * or smaller than the number of elements already inside the hash table */ - if (dictIsRehashing(d) || d->ht_used[0] > size || DICTHT_SIZE(d->ht_size_exp[0]) <= size) - return DICT_ERR; - return _dictResize(d, size, NULL); -} - -/* Helper function for `dictRehash` and `dictBucketRehash` which rehashes all the keys - * in a bucket at index `idx` from the old to the new hash HT. */ -static void rehashEntriesInBucketAtIndex(dict *d, uint64_t idx) { - dictEntry *de = d->ht_table[0][idx]; - uint64_t h; - dictEntry *nextde; - while (de) { - nextde = dictGetNext(de); - void *storedKey = dictGetKey(de); - /* Get the index in the new hash table */ - if (d->ht_size_exp[1] > d->ht_size_exp[0]) { - const void *key = dictStoredKey2Key(d, storedKey); - h = dictGetHash(d, key) & DICTHT_SIZE_MASK(d->ht_size_exp[1]); - } else { - /* We're shrinking the table. The tables sizes are powers of - * two, so we simply mask the bucket index in the larger table - * to get the bucket index in the smaller table. */ - h = idx & DICTHT_SIZE_MASK(d->ht_size_exp[1]); - } - if (d->type->no_value) { - if (!d->ht_table[1][h]) { - /* The destination bucket is empty, allowing the key to be stored - * directly without allocating a dictEntry. If an old entry was - * previously allocated, free its memory. */ - if (!entryIsKey(de)) zfree(decodeMaskedPtr(de)); - - de = encodeEntryKey(d, storedKey); - - } else if (entryIsKey(de)) { - /* We don't have an allocated entry but we need one. */ - de = createEntryNoValue(storedKey, d->ht_table[1][h]); - } else { - dictSetNext(de, d->ht_table[1][h]); - } - } else { - dictSetNext(de, d->ht_table[1][h]); - } - d->ht_table[1][h] = de; - d->ht_used[0]--; - d->ht_used[1]++; - de = nextde; - } - d->ht_table[0][idx] = NULL; -} - -/* This checks if we already rehashed the whole table and if more rehashing is required */ -static int dictCheckRehashingCompleted(dict *d) { - if (d->ht_used[0] != 0) return 0; - - if (d->type->rehashingCompleted) d->type->rehashingCompleted(d); - if (d->type->bucketChanged) - d->type->bucketChanged(d, -(long long)DICTHT_SIZE(d->ht_size_exp[0])); - zfree(d->ht_table[0]); - /* Copy the new ht onto the old one */ - d->ht_table[0] = d->ht_table[1]; - d->ht_used[0] = d->ht_used[1]; - d->ht_size_exp[0] = d->ht_size_exp[1]; - _dictReset(d, 1); - d->rehashidx = -1; - return 1; -} - -/* 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 = DICTHT_SIZE(d->ht_size_exp[0]); - unsigned long s1 = DICTHT_SIZE(d->ht_size_exp[1]); - if (dict_can_resize == DICT_RESIZE_FORBID || !dictIsRehashing(d)) return 0; - /* If dict_can_resize is DICT_RESIZE_AVOID, we want to avoid rehashing. - * - If expanding, the threshold is dict_force_resize_ratio which is 4. - * - If shrinking, the threshold is 1 / (HASHTABLE_MIN_FILL * dict_force_resize_ratio) which is 1/32. */ - if (dict_can_resize == DICT_RESIZE_AVOID && - ((s1 > s0 && s1 < dict_force_resize_ratio * s0) || - (s1 < s0 && s0 < HASHTABLE_MIN_FILL * dict_force_resize_ratio * s1))) - { - return 0; - } - - while(n-- && d->ht_used[0] != 0) { - /* Note that rehashidx can't overflow as we are sure there are more - * elements because ht[0].used != 0 */ - assert(DICTHT_SIZE(d->ht_size_exp[0]) > (unsigned long)d->rehashidx); - while(d->ht_table[0][d->rehashidx] == NULL) { - d->rehashidx++; - if (--empty_visits == 0) return 1; - } - /* Move all the keys in this bucket from the old to the new hash HT */ - rehashEntriesInBucketAtIndex(d, d->rehashidx); - d->rehashidx++; - } - - return !dictCheckRehashingCompleted(d); -} - -long long timeInMilliseconds(void) { - struct timeval tv; - - gettimeofday(&tv,NULL); - return (((long long)tv.tv_sec)*1000)+(tv.tv_usec/1000); -} - -/* Rehash in us+"delta" microseconds. The value of "delta" is larger - * than 0, and is smaller than 1000 in most cases. The exact upper bound - * depends on the running time of dictRehash(d,100).*/ -int dictRehashMicroseconds(dict *d, uint64_t us) { - if (d->pauserehash > 0) return 0; - - monotime timer; - elapsedStart(&timer); - int rehashes = 0; - - while(dictRehash(d,100)) { - rehashes += 100; - if (elapsedUs(timer) >= us) 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 elements 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); -} - -/* Performs rehashing on a single bucket. */ -int _dictBucketRehash(dict *d, uint64_t idx) { - if (d->pauserehash != 0) return 0; - unsigned long s0 = DICTHT_SIZE(d->ht_size_exp[0]); - unsigned long s1 = DICTHT_SIZE(d->ht_size_exp[1]); - if (dict_can_resize == DICT_RESIZE_FORBID || !dictIsRehashing(d)) return 0; - /* If dict_can_resize is DICT_RESIZE_AVOID, we want to avoid rehashing. - * - If expanding, the threshold is dict_force_resize_ratio which is 4. - * - If shrinking, the threshold is 1 / (HASHTABLE_MIN_FILL * dict_force_resize_ratio) which is 1/32. */ - if (dict_can_resize == DICT_RESIZE_AVOID && - ((s1 > s0 && s1 < dict_force_resize_ratio * s0) || - (s1 < s0 && s0 < HASHTABLE_MIN_FILL * dict_force_resize_ratio * s1))) - { - return 0; - } - rehashEntriesInBucketAtIndex(d, idx); - dictCheckRehashingCompleted(d); - return 1; -} - -/* Add an element to the target hash table */ -int dictAdd(dict *d, void *key __stored_key, void *val) -{ - dictEntry *entry = dictAddRaw(d,key,NULL); - - if (!entry) return DICT_ERR; - if (!d->type->no_value) dictSetVal(d, entry, val); - return DICT_OK; -} - -int dictCompareKeys(dict *d, const void *key1, const void *key2) { - dictCmpCache cache = {0}; - keyCmpFunc cmpFunc = dictGetCmpFunc(d); - return cmpFunc(&cache, key1, key2); -} - -/* 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 __stored_key, dictEntry **existing) -{ - /* Get the position for the new key or NULL if the key already exists. */ - void *position = dictFindLinkForInsert(d, dictStoredKey2Key(d, key), existing); - if (!position) return NULL; - - /* Dup the key if necessary. */ - if (d->type->keyDup) key = d->type->keyDup(d, key); - - return dictInsertKeyAtLink(d, key, position); -} - -/* Adds a key in the dict's hashtable at the link returned by a preceding - * call to dictFindLinkForInsert(). This is a low level function which allows - * splitting dictAddRaw in two parts. Normally, dictAddRaw or dictAdd should be - * used instead. It assumes that dictExpandIfNeeded() was called before. */ -dictEntry *dictInsertKeyAtLink(dict *d, void *key __stored_key, dictEntryLink link) { - dictEntryLink bucket = link; /* It's a bucket, but the API hides that. */ - dictEntry *entry; - /* If rehashing is ongoing, we insert in table 1, otherwise in table 0. - * Assert that the provided bucket is the right table. */ - int htidx = dictIsRehashing(d) ? 1 : 0; - assert(bucket >= &d->ht_table[htidx][0] && - bucket <= &d->ht_table[htidx][DICTHT_SIZE_MASK(d->ht_size_exp[htidx])]); - if (d->type->no_value) { - if (!*bucket) { - /* We can store the key directly in the destination bucket without - * allocating dictEntry. - */ - entry = encodeEntryKey(d, key); - assert(entryIsKey(entry)); - } else { - /* Allocate an entry without value. */ - entry = createEntryNoValue(key, *bucket); - } - } else { - /* 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. */ - entry = zmalloc(sizeof(*entry)); - assert(entryIsNormal(entry)); /* Check alignment of allocation */ - entry->key = key; - entry->next = *bucket; - } - *bucket = entry; - d->ht_used[htidx]++; - - 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 __stored_key, void *val) -{ - dictEntry *entry, *existing; - - /* 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. */ - void *oldval = dictGetVal(existing); - dictSetVal(d, existing, val); - if (d->type->valDestructor) - d->type->valDestructor(d, oldval); - 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 __stored_key) { - dictEntry *entry, *existing; - entry = dictAddRaw(d,key,&existing); - return entry ? entry : existing; -} - -/* Search and remove an element. This is a helper function for - * dictDelete() and dictUnlink(), please check the top comment - * of those functions. */ -static dictEntry *dictGenericDelete(dict *d, const void *key, int nofree) { - dictCmpCache cmpCache = {0}; - uint64_t h, idx; - dictEntry *he, *prevHe; - int table; - - /* dict is empty */ - if (dictSize(d) == 0) return NULL; - - h = dictGetHash(d, key); - idx = h & DICTHT_SIZE_MASK(d->ht_size_exp[0]); - - /* Rehash the hash table if needed */ - _dictRehashStepIfNeeded(d,idx); - - keyCmpFunc cmpFunc = dictGetCmpFunc(d); - - for (table = 0; table <= 1; table++) { - if (table == 0 && (long)idx < d->rehashidx) continue; - idx = h & DICTHT_SIZE_MASK(d->ht_size_exp[table]); - he = d->ht_table[table][idx]; - prevHe = NULL; - while(he) { - const void *he_key = dictStoredKey2Key(d, dictGetKey(he)); - if (key == he_key || cmpFunc(&cmpCache, key, he_key)) { - /* Unlink the element from the list */ - if (prevHe) - dictSetNext(prevHe, dictGetNext(he)); - else - d->ht_table[table][idx] = dictGetNext(he); - if (!nofree) { - dictFreeUnlinkedEntry(d, he); - } - d->ht_used[table]--; - _dictShrinkIfNeeded(d); - return he; - } - prevHe = he; - he = dictGetNext(he); - } - 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 *d, const void *key) { - return dictGenericDelete(d,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); - if (!entryIsKey(he)) zfree(decodeMaskedPtr(he)); -} - -/* Destroy an entire dictionary */ -int _dictClear(dict *d, int htidx, void(callback)(dict*)) { - unsigned long i; - - /* Free all the elements */ - for (i = 0; i < DICTHT_SIZE(d->ht_size_exp[htidx]) && d->ht_used[htidx] > 0; i++) { - dictEntry *he, *nextHe; - /* Callback will be called once for every 65535 deletions. Beware, - * if dict has less than 65535 items, it will not be called at all.*/ - if (callback && i != 0 && (i & 65535) == 0) callback(d); - - if ((he = d->ht_table[htidx][i]) == NULL) continue; - while(he) { - nextHe = dictGetNext(he); - dictFreeKey(d, he); - dictFreeVal(d, he); - if (!entryIsKey(he)) zfree(decodeMaskedPtr(he)); - d->ht_used[htidx]--; - he = nextHe; - } - } - /* Free the table and the allocated cache structure */ - zfree(d->ht_table[htidx]); - /* Re-initialize the table */ - _dictReset(d, htidx); - return DICT_OK; /* never fails */ -} - -/* Clear & Release the hash table */ -void dictRelease(dict *d) -{ - /* Someone may be monitoring a dict that started rehashing, before - * destroying the dict fake completion. */ - if (dictIsRehashing(d) && d->type->rehashingCompleted) - d->type->rehashingCompleted(d); - - /* Subtract the size of all buckets. */ - if (d->type->bucketChanged) - d->type->bucketChanged(d, -(long long)dictBuckets(d)); - - if (d->type->onDictRelease) - d->type->onDictRelease(d); - - _dictClear(d,0,NULL); - _dictClear(d,1,NULL); - zfree(d); -} - -/* Finds a given key. Like dictFindLink(), yet search bucket even if dict is empty. - * - * Returns dictEntryLink reference if found. Otherwise, return NULL. - * - * bucket - return pointer to bucket that the key was mapped. unless dict is empty. - */ -static dictEntryLink dictFindLinkInternal(dict *d, const void *key, dictEntryLink *bucket) { - dictCmpCache cmpCache = {0}; - dictEntryLink link; - uint64_t idx; - int table; - - if (bucket) { - *bucket = NULL; - } else { - /* If dict is empty and no need to find bucket, return NULL */ - if (dictSize(d) == 0) return NULL; - } - - const uint64_t hash = dictGetHash(d, key); - idx = hash & DICTHT_SIZE_MASK(d->ht_size_exp[0]); - keyCmpFunc cmpFunc = dictGetCmpFunc(d); - - /* Rehash the hash table if needed */ - _dictRehashStepIfNeeded(d,idx); - - int tables = (dictIsRehashing(d)) ? 2 : 1; - for (table = 0; table < tables; table++) { - if (table == 0 && (long)idx < d->rehashidx) continue; - idx = hash & DICTHT_SIZE_MASK(d->ht_size_exp[table]); - - link = &(d->ht_table[table][idx]); - if (bucket) *bucket = link; - while(link && *link) { - const void *visitedKey = dictStoredKey2Key(d, dictGetKey(*link)); - - if (key == visitedKey || cmpFunc( &cmpCache, key, visitedKey)) - return link; - - link = dictGetNextLink(*link); - } - } - return NULL; -} - -dictEntry *dictFind(dict *d, const void *key) -{ - dictEntryLink link = dictFindLink(d, key, NULL); - return (link) ? *link : NULL; -} - -/* Finds the dictEntry 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 a pointer to the dictEntry if found, or NULL if not found. */ -dictEntry *dictFindByHashAndPtr(dict *d, const void *oldptr, const uint64_t hash) { - dictEntry *he; - unsigned long idx, table; - - if (dictSize(d) == 0) return NULL; /* dict is empty */ - for (table = 0; table <= 1; table++) { - idx = hash & DICTHT_SIZE_MASK(d->ht_size_exp[table]); - if (table == 0 && (long)idx < d->rehashidx) continue; - he = d->ht_table[table][idx]; - while(he) { - if (oldptr == dictGetKey(he)) - return he; - he = dictGetNext(he); - } - if (!dictIsRehashing(d)) return NULL; - } - return NULL; -} - -/* Find a key and return its dictEntryLink reference. Otherwise, return NULL - * - * A dictEntryLink pointer being used to find preceding dictEntry of searched item. - * It is Useful for deletion, addition, unlinking and updating, especially for - * dict configured with 'no_value'. In such cases returning only `dictEntry` from - * a lookup may be insufficient since it might be opt-out to be the object itself. - * By locating preceding dictEntry (dictEntryLink) these ops can be properly handled. - * - * After calling link = dictFindLink(...), any necessary updates based on returned - * link or bucket must be performed immediately after by calling dictSetKeyAtLink() - * without any intervening operations on given dict. Otherwise, `dictEntryLink` may - * become invalid. Example with kvobj of replacing key with new key: - * - * link = dictFindLink(d, key, &bucket, 0); - * ... Do something, but don't modify the dict ... - * // assert(link != NULL); - * dictSetKeyAtLink(d, kv, &link, 0); - * - * To add new value (If no space for the new key, dict will be expanded by - * dictSetKeyAtLink() and bucket will be looked up again.): - * - * link = dictFindLink(d, key, &bucket); - * ... Do something, but don't modify the dict ... - * // assert(link == NULL); - * dictSetKeyAtLink(d, kv, &bucket, 1); - * - * bucket - return link to bucket that the key was mapped. unless dict is empty. - */ -dictEntryLink dictFindLink(dict *d, const void *key, dictEntryLink *bucket) { - if (bucket) *bucket = NULL; - if (unlikely(dictSize(d) == 0)) - return NULL; - - return dictFindLinkInternal(d, key, bucket); -} - -/* Set the key with link - * - * link: - When `newItem` is set, `link` points to the bucket of the key. - * - When `newItem` is not set, `link` points to the link of the key. - * - If *link is NULL, dictFindLink() will be called to locate the key. - * - On return, get updated, by need, to the inserted key. - * - * newItem: 1 = Add a key with a new dictEntry. - * 0 = Set a key to an existing dictEntry. - */ -void dictSetKeyAtLink(dict *d, void *key __stored_key, dictEntryLink *link, int newItem) { - dictEntryLink dummy = NULL; - if (link == NULL) link = &dummy; - void *addedKey = (d->type->keyDup) ? d->type->keyDup(d, key) : key; - - if (newItem) { - signed char snap[2] = {d->ht_size_exp[0], d->ht_size_exp[1] }; - - /* Make room if needed for the new key */ - dictExpandIfNeeded(d); - - /* Lookup key's link if tables reallocated or if given link is set to NULL */ - if (snap[0] != d->ht_size_exp[0] || snap[1] != d->ht_size_exp[1] || *link == NULL) { - dictEntryLink bucket; - /* Bypass dictFindLink() to search bucket even if dict is empty!!! */ - *link = dictFindLinkInternal(d, dictStoredKey2Key(d, key), &bucket); - assert(bucket != NULL); - assert(*link == NULL); - *link = bucket; /* On newItem the link should be the bucket */ - } - dictInsertKeyAtLink(d, addedKey, *link); - return; - } - - /* Setting key of existing dictEntry (newItem == 0)*/ - - if (*link == NULL) { - *link = dictFindLink(d, key, NULL); - assert(*link != NULL); - } - - dictEntry **de = *link; - if (entryIsKey(*de)) { - /* `de` opt-out to be actually a key. Replace key but keep the lsb flags */ - *de = encodeEntryKey(d, addedKey); - } else { - /* either dictEntry or dictEntryNoValue */ - (*de)->key = addedKey; - } -} - -void *dictFetchValue(dict *d, const void *key) { - dictEntry *he; - - he = dictFind(d,key); - return he ? dictGetVal(he) : NULL; -} - -/* Find an element from the table. A link is returned if the element is found, and - * the user should later call `dictTwoPhaseUnlinkFree` with it in order to unlink - * and release it. Otherwise if the key is not found, NULL is returned. These two - * functions should be used in pair. - * `dictTwoPhaseUnlinkFind` pauses rehash and `dictTwoPhaseUnlinkFree` resumes rehash. - * - * We can use like this: - * - * dictEntryLink link = dictTwoPhaseUnlinkFind(db->dict,key->ptr, &table); - * // Do something, but we can't modify the dict - * dictTwoPhaseUnlinkFree(db->dict, link, table); // We don't need to lookup again - * - * If we want to find an entry before delete this entry, this an optimization to avoid - * dictFind followed by dictDelete. i.e. the first API is a find, and it gives some info - * to the second one to avoid repeating the lookup - */ -dictEntryLink dictTwoPhaseUnlinkFind(dict *d, const void *key, int *table_index) { - dictCmpCache cmpCache = {0}; - uint64_t h, idx, table; - - if (dictSize(d) == 0) return NULL; /* dict is empty */ - if (dictIsRehashing(d)) _dictRehashStep(d); - - h = dictGetHash(d, key); - keyCmpFunc cmpFunc = dictGetCmpFunc(d); - - for (table = 0; table <= 1; table++) { - idx = h & DICTHT_SIZE_MASK(d->ht_size_exp[table]); - if (table == 0 && (long)idx < d->rehashidx) continue; - dictEntry **ref = &d->ht_table[table][idx]; - while (ref && *ref) { - const void *de_key = dictStoredKey2Key(d, dictGetKey(*ref)); - if (key == de_key || cmpFunc(&cmpCache, key, de_key)) { - *table_index = table; - dictPauseRehashing(d); - return ref; - } - ref = dictGetNextLink(*ref); - } - if (!dictIsRehashing(d)) return NULL; - } - return NULL; -} - -void dictTwoPhaseUnlinkFree(dict *d, dictEntryLink plink, int table_index) { - if (plink == NULL || *plink == NULL) return; - dictEntry *de = *plink; - d->ht_used[table_index]--; - - *plink = dictGetNext(de); - dictFreeKey(d, de); - dictFreeVal(d, de); - if (!entryIsKey(de)) zfree(decodeMaskedPtr(de)); - _dictShrinkIfNeeded(d); - dictResumeRehashing(d); -} - -void dictSetKey(dict *d, dictEntry* de, void *key __stored_key) { - assert(!d->type->no_value); - if (d->type->keyDup) - de->key = d->type->keyDup(d, key); - else - de->key = key; -} - -void dictSetVal(dict *d, dictEntry *de, void *val) { - assert(entryHasValue(de)); - de->v.val = d->type->valDup ? d->type->valDup(d, val) : val; -} - -void dictSetSignedIntegerVal(dictEntry *de, int64_t val) { - assert(entryHasValue(de)); - de->v.s64 = val; -} - -void dictSetUnsignedIntegerVal(dictEntry *de, uint64_t val) { - assert(entryHasValue(de)); - de->v.u64 = val; -} - -void dictSetDoubleVal(dictEntry *de, double val) { - assert(entryHasValue(de)); - de->v.d = val; -} - -int64_t dictIncrSignedIntegerVal(dictEntry *de, int64_t val) { - assert(entryHasValue(de)); - return de->v.s64 += val; -} - -uint64_t dictIncrUnsignedIntegerVal(dictEntry *de, uint64_t val) { - assert(entryHasValue(de)); - return de->v.u64 += val; -} - -double dictIncrDoubleVal(dictEntry *de, double val) { - assert(entryHasValue(de)); - return de->v.d += val; -} - -int dictEntryIsKey(const dictEntry *de) { - return entryIsKey(de); -} - -void *dictGetKey(const dictEntry *de) { - /* if entryIsKey() */ - if ((uintptr_t)de & ENTRY_PTR_IS_ODD_KEY) return (void *) de; - if ((uintptr_t)de & ENTRY_PTR_IS_EVEN_KEY) return decodeMaskedPtr(de); - /* Regular entry */ - return de->key; -} - -void *dictGetVal(const dictEntry *de) { - assert(entryHasValue(de)); - return de->v.val; -} - -int64_t dictGetSignedIntegerVal(const dictEntry *de) { - assert(entryHasValue(de)); - return de->v.s64; -} - -uint64_t dictGetUnsignedIntegerVal(const dictEntry *de) { - assert(entryHasValue(de)); - return de->v.u64; -} - -double dictGetDoubleVal(const dictEntry *de) { - assert(entryHasValue(de)); - return de->v.d; -} - -/* Returns a mutable reference to the value as a double within the entry. */ -double *dictGetDoubleValPtr(dictEntry *de) { - assert(entryHasValue(de)); - return &de->v.d; -} - -/* Returns the 'next' field of the entry or NULL if the entry doesn't have a - * 'next' field. */ -dictEntry *dictGetNext(const dictEntry *de) { - if (entryIsKey(de)) return NULL; /* there's no next */ - /* Must come after entryIsKey() check */ - return de->next; -} - -/* Returns a pointer to the 'next' field in the entry or NULL if the entry - * doesn't have a next field. */ -static dictEntryLink dictGetNextLink(dictEntry *de) { - if (entryIsKey(de)) return NULL; - /* Must come after entryIsKey() check */ - return &de->next; -} - -static void dictSetNext(dictEntry *de, dictEntry *next) { - assert(!entryIsKey(de)); - /* dictEntryNoValue & dictEntry are layout-compatible */ - de->next = next; -} - -/* Returns the memory usage in bytes of the dict, excluding the size of the keys - * and values. */ -size_t dictMemUsage(const dict *d) { - return dictSize(d) * sizeof(dictEntry) + - dictBuckets(d) * sizeof(dictEntry*); -} - -size_t dictEntryMemUsage(int noValueDict) { - return (noValueDict) ? sizeof(dictEntryNoValue) :sizeof(dictEntry); -} - -/* 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_table[0]; - integers[1] = d->ht_size_exp[0]; - integers[2] = d->ht_used[0]; - integers[3] = (long) d->ht_table[1]; - integers[4] = d->ht_size_exp[1]; - integers[5] = d->ht_used[1]; - - /* 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 * 265 - hash = hash ^ (hash >> 14); - hash = (hash + (hash << 2)) + (hash << 4); // hash * 21 - hash = hash ^ (hash >> 28); - hash = hash + (hash << 31); - } - return hash; -} - -void dictInitIterator(dictIterator *iter, dict *d) -{ - iter->d = d; - iter->table = 0; - iter->index = -1; - iter->safe = 0; - iter->entry = NULL; - iter->nextEntry = NULL; -} - -void dictInitSafeIterator(dictIterator *iter, dict *d) -{ - dictInitIterator(iter, d); - iter->safe = 1; -} - -void dictResetIterator(dictIterator *iter) -{ - if (!(iter->index == -1 && iter->table == 0)) { - if (iter->safe) - dictResumeRehashing(iter->d); - else - assert(iter->fingerprint == dictFingerprint(iter->d)); - } -} - -dictIterator *dictGetIterator(dict *d) -{ - dictIterator *iter = zmalloc(sizeof(*iter)); - dictInitIterator(iter, d); - 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) { - if (iter->index == -1 && iter->table == 0) { - if (iter->safe) - dictPauseRehashing(iter->d); - else - iter->fingerprint = dictFingerprint(iter->d); - - /* skip the rehashed slots in table[0] */ - if (dictIsRehashing(iter->d)) { - iter->index = iter->d->rehashidx - 1; - } - } - iter->index++; - if (iter->index >= (long) DICTHT_SIZE(iter->d->ht_size_exp[iter->table])) { - if (dictIsRehashing(iter->d) && iter->table == 0) { - iter->table++; - iter->index = 0; - } else { - break; - } - } - iter->entry = iter->d->ht_table[iter->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 = dictGetNext(iter->entry); - return iter->entry; - } - } - return NULL; -} - -void dictReleaseIterator(dictIterator *iter) -{ - dictResetIterator(iter); - 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)) { - unsigned long s0 = DICTHT_SIZE(d->ht_size_exp[0]); - do { - /* We are sure there are no elements in indexes from 0 - * to rehashidx-1 */ - h = d->rehashidx + (randomULong() % (dictBuckets(d) - d->rehashidx)); - he = (h >= s0) ? d->ht_table[1][h - s0] : d->ht_table[0][h]; - } while(he == NULL); - } else { - unsigned long m = DICTHT_SIZE_MASK(d->ht_size_exp[0]); - do { - h = randomULong() & m; - he = d->ht_table[0][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 = dictGetNext(he); - listlen++; - } - listele = random() % listlen; - he = orighe; - while(listele--) he = dictGetNext(he); - 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); - else - break; - } - - tables = dictIsRehashing(d) ? 2 : 1; - maxsizemask = DICTHT_SIZE_MASK(d->ht_size_exp[0]); - if (tables > 1 && maxsizemask < DICTHT_SIZE_MASK(d->ht_size_exp[1])) - maxsizemask = DICTHT_SIZE_MASK(d->ht_size_exp[1]); - - /* 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 >= DICTHT_SIZE(d->ht_size_exp[1])) - i = d->rehashidx; - else - continue; - } - if (i >= DICTHT_SIZE(d->ht_size_exp[j])) continue; /* Out of range for this table. */ - dictEntry *he = d->ht_table[j][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. - * To avoid the issue of being unable to sample the end of a long chain, - * we utilize the Reservoir Sampling algorithm to optimize the sampling process. - * This means that even when the maximum number of samples has been reached, - * we continue sampling until we reach the end of the chain. - * See https://en.wikipedia.org/wiki/Reservoir_sampling. */ - if (stored < count) { - des[stored] = he; - } else { - unsigned long r = randomULong() % (stored + 1); - if (r < count) des[r] = he; - } - - he = dictGetNext(he); - stored++; - } - if (stored >= count) goto end; - } - } - i = (i+1) & maxsizemask; - } - -end: - return stored > count ? count : stored; -} - - -/* Reallocate the dictEntry, key and value allocations in a bucket using the - * provided allocation functions in order to defrag them. */ -static void dictDefragBucket(dict *d, dictEntry **bucketref, dictDefragFunctions *defragfns) { - dictDefragAllocFunction *defragalloc = defragfns->defragAlloc; - dictDefragAllocFunction *defragkey = defragfns->defragKey; - dictDefragAllocFunction *defragval = defragfns->defragVal; - while (bucketref && *bucketref) { - dictEntry *de = *bucketref, *newde = NULL; - void *newkey = defragkey ? defragkey(dictGetKey(de)) : NULL; - - if (d->type->no_value) { - if (entryIsKey(de)) { - if (newkey) *bucketref = encodeEntryKey(d, newkey); - } else { - dictEntryNoValue *entry = decodeEntryNoValue(de), *newentry; - if ((newentry = defragalloc(entry))) { - newde = (dictEntry *) newentry; - entry = newentry; - } - if (newkey) entry->key = newkey; - } - } else { - void *newval = defragval ? defragval(dictGetVal(de)) : NULL; - assert(entryIsNormal(de)); - newde = defragalloc(de); - if (newde) de = newde; - if (newkey) de->key = newkey; - if (newval) de->v.val = newval; - } - if (newde) { - *bucketref = newde; - } - bucketref = dictGetNextLink(*bucketref); - } -} - -/* 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 2 - unsigned 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, - void *privdata) -{ - return dictScanDefrag(d, v, fn, NULL, privdata); -} - -void dictScanDefragBucket(dict *d,dictScanFunction *fn, - dictDefragFunctions *defragfns, - void *privdata, - dictEntry **bucketref) { - dictEntry **plink, *de, *next; - - /* Emit entries at bucket */ - if (defragfns) dictDefragBucket(d, bucketref, defragfns); - - de = *bucketref; - plink = bucketref; - while (de) { - next = dictGetNext(de); - fn(privdata, de, plink); - - if (!next) break; /* if last element, break */ - - /* if `*plink` still pointing to 'de', then it means that the - * visited item wasn't deleted by fn() */ - if (*plink == de) - plink = &(de->next); - - de = next; - } -} - -/* Like dictScan, but additionally reallocates the memory used by the dict - * entries using the provided allocation function. This feature was added for - * the active defrag feature. - * - * The 'defragfns' callbacks are called with a pointer to memory that callback - * can reallocate. The callbacks should return a new memory address or NULL, - * where NULL means that no reallocation happened and the old memory is still - * valid. */ -unsigned long dictScanDefrag(dict *d, - unsigned long v, - dictScanFunction *fn, - dictDefragFunctions *defragfns, - void *privdata) -{ - int htidx0, htidx1; - 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)) { - htidx0 = 0; - m0 = DICTHT_SIZE_MASK(d->ht_size_exp[htidx0]); - dictScanDefragBucket(d, fn, defragfns, privdata, &d->ht_table[htidx0][v & m0]); - - /* 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 { - htidx0 = 0; - htidx1 = 1; - - /* Make sure t0 is the smaller and t1 is the bigger table */ - if (DICTHT_SIZE(d->ht_size_exp[htidx0]) > DICTHT_SIZE(d->ht_size_exp[htidx1])) { - htidx0 = 1; - htidx1 = 0; - } - - m0 = DICTHT_SIZE_MASK(d->ht_size_exp[htidx0]); - m1 = DICTHT_SIZE_MASK(d->ht_size_exp[htidx1]); - - dictScanDefragBucket(d, fn, defragfns, privdata, &d->ht_table[htidx0][v & m0]); - - /* Iterate over indices in larger table that are the expansion - * of the index pointed to by the cursor in the smaller table */ - do { - dictScanDefragBucket(d, fn, defragfns, privdata, &d->ht_table[htidx1][v & m1]); - - /* 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 - * resizes, we will check this allocation is allowed or not if the dict - * type has resizeAllowed member function. */ -static int dictTypeResizeAllowed(dict *d, size_t size) { - if (d->type->resizeAllowed == NULL) return 1; - return d->type->resizeAllowed( - DICTHT_SIZE(_dictNextExp(size)) * sizeof(dictEntry*), - (double)d->ht_used[0] / DICTHT_SIZE(d->ht_size_exp[0])); -} - -/* Returning DICT_OK indicates a successful expand or the dictionary is undergoing rehashing, - * and there is nothing else we need to do about this dictionary currently. While DICT_ERR indicates - * that expand has not been triggered (may be try shrinking?)*/ -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 (DICTHT_SIZE(d->ht_size_exp[0]) == 0) { - dictExpand(d, DICT_HT_INITIAL_SIZE); - return DICT_OK; - } - - /* 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 ((dict_can_resize == DICT_RESIZE_ENABLE && - d->ht_used[0] >= DICTHT_SIZE(d->ht_size_exp[0])) || - (dict_can_resize != DICT_RESIZE_FORBID && - d->ht_used[0] >= dict_force_resize_ratio * DICTHT_SIZE(d->ht_size_exp[0]))) - { - if (dictTypeResizeAllowed(d, d->ht_used[0] + 1)) - dictExpand(d, d->ht_used[0] + 1); - return DICT_OK; - } - return DICT_ERR; -} - -/* Expand the hash table if needed (OK=Expanded, ERR=Not expanded) */ -static int _dictExpandIfNeeded(dict *d) { - /* Automatic resizing is disallowed. Return */ - if (d->pauseAutoResize > 0) return DICT_ERR; - - return dictExpandIfNeeded(d); -} - -/* Returning DICT_OK indicates a successful shrinking or the dictionary is undergoing rehashing, - * and there is nothing else we need to do about this dictionary currently. While DICT_ERR indicates - * that shrinking has not been triggered (may be try expanding?)*/ -int dictShrinkIfNeeded(dict *d) { - /* Incremental rehashing already in progress. Return. */ - if (dictIsRehashing(d)) return DICT_OK; - - /* If the size of hash table is DICT_HT_INITIAL_SIZE, don't shrink it. */ - if (DICTHT_SIZE(d->ht_size_exp[0]) <= DICT_HT_INITIAL_SIZE) return DICT_OK; - - /* If we reached below 1:8 elements/buckets ratio, and we are allowed to resize - * the hash table (global setting) or we should avoid it but the ratio is below 1:32, - * we'll trigger a resize of the hash table. */ - if ((dict_can_resize == DICT_RESIZE_ENABLE && - d->ht_used[0] * HASHTABLE_MIN_FILL <= DICTHT_SIZE(d->ht_size_exp[0])) || - (dict_can_resize != DICT_RESIZE_FORBID && - d->ht_used[0] * HASHTABLE_MIN_FILL * dict_force_resize_ratio <= DICTHT_SIZE(d->ht_size_exp[0]))) - { - if (dictTypeResizeAllowed(d, d->ht_used[0])) - dictShrink(d, d->ht_used[0]); - return DICT_OK; - } - return DICT_ERR; -} - -static void _dictShrinkIfNeeded(dict *d) -{ - /* Automatic resizing is disallowed. Return */ - if (d->pauseAutoResize > 0) return; - - dictShrinkIfNeeded(d); -} - -static void _dictRehashStepIfNeeded(dict *d, uint64_t visitedIdx) { - if ((!dictIsRehashing(d)) || (d->pauserehash != 0)) - return; - /* rehashing not in progress if rehashidx == -1 */ - if ((long)visitedIdx >= d->rehashidx && d->ht_table[0][visitedIdx]) { - /* If we have a valid hash entry at `idx` in ht0, we perform - * rehash on the bucket at `idx` (being more CPU cache friendly) */ - _dictBucketRehash(d, visitedIdx); - } else { - /* If the hash entry is not in ht0, we rehash the buckets based - * on the rehashidx (not CPU cache friendly). */ - dictRehash(d,1); - } -} - -/* Our hash table capability is a power of two */ -static signed char _dictNextExp(unsigned long size) -{ - if (size <= DICT_HT_INITIAL_SIZE) return DICT_HT_INITIAL_EXP; - if (size >= LONG_MAX) return (8*sizeof(long)-1); - - return 8*sizeof(long) - __builtin_clzl(size-1); -} - -/* Finds and returns the link within the dict where the provided key should - * be inserted using dictInsertKeyAtLink() if the key does not already exist in - * the dict. If the key exists in the dict, NULL is returned and the optional - * 'existing' entry pointer is populated, if provided. */ -dictEntryLink dictFindLinkForInsert(dict *d, const void *key, dictEntry **existing) { - unsigned long idx, table; - dictCmpCache cmpCache = {0}; - dictEntry *he; - uint64_t hash = dictGetHash(d, key); - if (existing) *existing = NULL; - idx = hash & DICTHT_SIZE_MASK(d->ht_size_exp[0]); - - /* Rehash the hash table if needed */ - _dictRehashStepIfNeeded(d,idx); - - /* Expand the hash table if needed */ - _dictExpandIfNeeded(d); - keyCmpFunc cmpFunc = dictGetCmpFunc(d); - - for (table = 0; table <= 1; table++) { - if (table == 0 && (long)idx < d->rehashidx) continue; - idx = hash & DICTHT_SIZE_MASK(d->ht_size_exp[table]); - /* Search if this slot does not already contain the given key */ - he = d->ht_table[table][idx]; - while(he) { - const void *he_key = dictStoredKey2Key(d, dictGetKey(he)); - if (key == he_key || cmpFunc(&cmpCache, key, he_key)) { - if (existing) *existing = he; - return NULL; - } - he = dictGetNext(he); - } - if (!dictIsRehashing(d)) break; - } - - /* If we are in the process of rehashing the hash table, the bucket is - * always returned in the context of the second (new) hash table. */ - dictEntry **bucket = &d->ht_table[dictIsRehashing(d) ? 1 : 0][idx]; - return bucket; -} - - -void dictEmpty(dict *d, void(callback)(dict*)) { - /* Someone may be monitoring a dict that started rehashing, before - * destroying the dict fake completion. */ - if (dictIsRehashing(d) && d->type->rehashingCompleted) - d->type->rehashingCompleted(d); - - /* Subtract the size of all buckets. */ - if (d->type->bucketChanged) - d->type->bucketChanged(d, -(long long)dictBuckets(d)); - - _dictClear(d,0,callback); - _dictClear(d,1,callback); - d->rehashidx = -1; - d->pauserehash = 0; - d->pauseAutoResize = 0; -} - -void dictSetResizeEnabled(dictResizeEnable enable) { - dict_can_resize = enable; -} - -/* Compiler inlines this for internal calls within dict.c (verified with -O3). */ -uint64_t dictGetHash(dict *d, const void *key) { - return d->type->hashFunction(key); -} - -/* Provides the old and new ht size for a given dictionary during rehashing. This method - * should only be invoked during initialization/rehashing. */ -void dictRehashingInfo(dict *d, unsigned long long *from_size, unsigned long long *to_size) { - /* Invalid method usage if rehashing isn't ongoing. */ - assert(dictIsRehashing(d)); - *from_size = DICTHT_SIZE(d->ht_size_exp[0]); - *to_size = DICTHT_SIZE(d->ht_size_exp[1]); -} - -/* ------------------------------- Debugging ---------------------------------*/ -#define DICT_STATS_VECTLEN 50 -void dictFreeStats(dictStats *stats) { - zfree(stats->clvector); - zfree(stats); -} - -void dictCombineStats(dictStats *from, dictStats *into) { - into->buckets += from->buckets; - into->maxChainLen = (from->maxChainLen > into->maxChainLen) ? from->maxChainLen : into->maxChainLen; - into->totalChainLen += from->totalChainLen; - into->htSize += from->htSize; - into->htUsed += from->htUsed; - for (int i = 0; i < DICT_STATS_VECTLEN; i++) { - into->clvector[i] += from->clvector[i]; - } -} - -dictStats *dictGetStatsHt(dict *d, int htidx, int full) { - unsigned long *clvector = zcalloc(sizeof(unsigned long) * DICT_STATS_VECTLEN); - dictStats *stats = zcalloc(sizeof(dictStats)); - stats->htidx = htidx; - stats->clvector = clvector; - stats->htSize = DICTHT_SIZE(d->ht_size_exp[htidx]); - stats->htUsed = d->ht_used[htidx]; - if (!full) return stats; - /* Compute stats. */ - for (unsigned long i = 0; i < DICTHT_SIZE(d->ht_size_exp[htidx]); i++) { - dictEntry *he; - - if (d->ht_table[htidx][i] == NULL) { - clvector[0]++; - continue; - } - stats->buckets++; - /* For each hash entry on this slot... */ - unsigned long chainlen = 0; - he = d->ht_table[htidx][i]; - while(he) { - chainlen++; - he = dictGetNext(he); - } - clvector[(chainlen < DICT_STATS_VECTLEN) ? chainlen : (DICT_STATS_VECTLEN-1)]++; - if (chainlen > stats->maxChainLen) stats->maxChainLen = chainlen; - stats->totalChainLen += chainlen; - } - - return stats; -} - -/* Generates human readable stats. */ -size_t dictGetStatsMsg(char *buf, size_t bufsize, dictStats *stats, int full) { - if (stats->htUsed == 0) { - return snprintf(buf,bufsize, - "Hash table %d stats (%s):\n" - "No stats available for empty dictionaries\n", - stats->htidx, (stats->htidx == 0) ? "main hash table" : "rehashing target"); - } - size_t l = 0; - l += snprintf(buf + l, bufsize - l, - "Hash table %d stats (%s):\n" - " table size: %lu\n" - " number of elements: %lu\n", - stats->htidx, (stats->htidx == 0) ? "main hash table" : "rehashing target", - stats->htSize, stats->htUsed); - if (full) { - l += snprintf(buf + l, bufsize - l, - " 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", - stats->buckets, stats->maxChainLen, - (float) stats->totalChainLen / stats->buckets, (float) stats->htUsed / stats->buckets); - - for (unsigned long i = 0; i < DICT_STATS_VECTLEN - 1; i++) { - if (stats->clvector[i] == 0) continue; - if (l >= bufsize) break; - l += snprintf(buf + l, bufsize - l, - " %ld: %ld (%.02f%%)\n", - i, stats->clvector[i], ((float) stats->clvector[i] / stats->htSize) * 100); - } - } - - /* Make sure there is a NULL term at the end. */ - buf[bufsize-1] = '\0'; - /* Unlike snprintf(), return the number of characters actually written. */ - return strlen(buf); -} - -void dictGetStats(char *buf, size_t bufsize, dict *d, int full) { - size_t l; - char *orig_buf = buf; - size_t orig_bufsize = bufsize; - - dictStats *mainHtStats = dictGetStatsHt(d, 0, full); - l = dictGetStatsMsg(buf, bufsize, mainHtStats, full); - dictFreeStats(mainHtStats); - buf += l; - bufsize -= l; - if (dictIsRehashing(d) && bufsize > 0) { - dictStats *rehashHtStats = dictGetStatsHt(d, 1, full); - dictGetStatsMsg(buf, bufsize, rehashHtStats, full); - dictFreeStats(rehashHtStats); - } - /* Make sure there is a NULL term at the end. */ - orig_buf[orig_bufsize-1] = '\0'; -} - -static int dictDefaultCompare(dictCmpCache *cache, const void *key1, const void *key2) { - (void)(cache); /*unused*/ - return key1 == key2; -} - -/* ------------------------------- Benchmark ---------------------------------*/ - -#ifdef REDIS_TEST -#include "testhelp.h" - -#define UNUSED(V) ((void) V) -#define TEST(name) printf("test — %s\n", name); - -uint64_t hashCallback(const void *key) { - return dictGenHashFunction((unsigned char*)key, strlen((char*)key)); -} - -int compareCallback(dictCmpCache *cache, const void *key1, const void *key2) { - int l1,l2; - UNUSED(cache); - - l1 = strlen((char*)key1); - l2 = strlen((char*)key2); - if (l1 != l2) return 0; - return memcmp(key1, key2, l1) == 0; -} - -void freeCallback(dict *d, void *val) { - UNUSED(d); - - zfree(val); -} - -char *stringFromLongLong(long long value) { - char buf[32]; - int len; - char *s; - - len = snprintf(buf,sizeof(buf),"%lld",value); - s = zmalloc(len+1); - memcpy(s, buf, len); - s[len] = '\0'; - return s; -} - -char *stringFromSubstring(void) { - #define LARGE_STRING_SIZE 10000 - #define MIN_STRING_SIZE 100 - #define MAX_STRING_SIZE 500 - static char largeString[LARGE_STRING_SIZE + 1]; - static int init = 0; - if (init == 0) { - /* Generate a large string */ - for (size_t i = 0; i < LARGE_STRING_SIZE; i++) { - /* Random printable ASCII character (33 to 126) */ - largeString[i] = 33 + (rand() % 94); - } - /* Null-terminate the large string */ - largeString[LARGE_STRING_SIZE] = '\0'; - init = 1; - } - /* Randomly choose a size between minSize and maxSize */ - size_t substringSize = MIN_STRING_SIZE + (rand() % (MAX_STRING_SIZE - MIN_STRING_SIZE + 1)); - size_t startIndex = rand() % (LARGE_STRING_SIZE - substringSize + 1); - /* Allocate memory for the substring (+1 for null terminator) */ - char *s = zmalloc(substringSize + 1); - memcpy(s, largeString + startIndex, substringSize); // Copy the substring - s[substringSize] = '\0'; // Null-terminate the string - 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 flags) { - long j; - long long start, elapsed; - int retval; - dict *d = dictCreate(&BenchmarkDictType); - dictEntry* de = NULL; - dictEntry* existing = NULL; - long count = 0; - unsigned long new_dict_size, current_dict_used, remain_keys; - int accurate = (flags & REDIS_TEST_ACCURATE); - - if (argc == 4) { - if (accurate) { - count = 5000000; - } else { - count = strtol(argv[3],NULL,10); - } - } else { - count = 5000; - } - - TEST("Add 16 keys and verify dict resize is ok") { - dictSetResizeEnabled(DICT_RESIZE_ENABLE); - for (j = 0; j < 16; j++) { - retval = dictAdd(d,stringFromLongLong(j),(void*)j); - assert(retval == DICT_OK); - } - while (dictIsRehashing(d)) dictRehashMicroseconds(d,1000); - assert(dictSize(d) == 16); - assert(dictBuckets(d) == 16); - } - - TEST("Use DICT_RESIZE_AVOID to disable the dict resize and pad to (dict_force_resize_ratio * 16)") { - /* Use DICT_RESIZE_AVOID to disable the dict resize, and pad - * the number of keys to (dict_force_resize_ratio * 16), so we can satisfy - * dict_force_resize_ratio in next test. */ - dictSetResizeEnabled(DICT_RESIZE_AVOID); - for (j = 16; j < (long)dict_force_resize_ratio * 16; j++) { - retval = dictAdd(d,stringFromLongLong(j),(void*)j); - assert(retval == DICT_OK); - } - current_dict_used = dict_force_resize_ratio * 16; - assert(dictSize(d) == current_dict_used); - assert(dictBuckets(d) == 16); - } - - TEST("Add one more key, trigger the dict resize") { - retval = dictAdd(d,stringFromLongLong(current_dict_used),(void*)(current_dict_used)); - assert(retval == DICT_OK); - current_dict_used++; - new_dict_size = 1UL << _dictNextExp(current_dict_used); - assert(dictSize(d) == current_dict_used); - assert(DICTHT_SIZE(d->ht_size_exp[0]) == 16); - assert(DICTHT_SIZE(d->ht_size_exp[1]) == new_dict_size); - - /* Wait for rehashing. */ - dictSetResizeEnabled(DICT_RESIZE_ENABLE); - while (dictIsRehashing(d)) dictRehashMicroseconds(d,1000); - assert(dictSize(d) == current_dict_used); - assert(DICTHT_SIZE(d->ht_size_exp[0]) == new_dict_size); - assert(DICTHT_SIZE(d->ht_size_exp[1]) == 0); - } - - TEST("Delete keys until we can trigger shrink in next test") { - /* Delete keys until we can satisfy (1 / HASHTABLE_MIN_FILL) in the next test. */ - for (j = new_dict_size / HASHTABLE_MIN_FILL + 1; j < (long)current_dict_used; j++) { - char *key = stringFromLongLong(j); - retval = dictDelete(d, key); - zfree(key); - assert(retval == DICT_OK); - } - current_dict_used = new_dict_size / HASHTABLE_MIN_FILL + 1; - assert(dictSize(d) == current_dict_used); - assert(DICTHT_SIZE(d->ht_size_exp[0]) == new_dict_size); - assert(DICTHT_SIZE(d->ht_size_exp[1]) == 0); - } - - TEST("Delete one more key, trigger the dict resize") { - current_dict_used--; - char *key = stringFromLongLong(current_dict_used); - retval = dictDelete(d, key); - zfree(key); - unsigned long oldDictSize = new_dict_size; - new_dict_size = 1UL << _dictNextExp(current_dict_used); - assert(retval == DICT_OK); - assert(dictSize(d) == current_dict_used); - assert(DICTHT_SIZE(d->ht_size_exp[0]) == oldDictSize); - assert(DICTHT_SIZE(d->ht_size_exp[1]) == new_dict_size); - - /* Wait for rehashing. */ - while (dictIsRehashing(d)) dictRehashMicroseconds(d,1000); - assert(dictSize(d) == current_dict_used); - assert(DICTHT_SIZE(d->ht_size_exp[0]) == new_dict_size); - assert(DICTHT_SIZE(d->ht_size_exp[1]) == 0); - } - - TEST("Empty the dictionary and add 128 keys") { - dictEmpty(d, NULL); - for (j = 0; j < 128; j++) { - retval = dictAdd(d,stringFromLongLong(j),(void*)j); - assert(retval == DICT_OK); - } - while (dictIsRehashing(d)) dictRehashMicroseconds(d,1000); - assert(dictSize(d) == 128); - assert(dictBuckets(d) == 128); - } - - TEST("Use DICT_RESIZE_AVOID to disable the dict resize and reduce to 3") { - /* Use DICT_RESIZE_AVOID to disable the dict reset, and reduce - * the number of keys until we can trigger shrinking in next test. */ - dictSetResizeEnabled(DICT_RESIZE_AVOID); - remain_keys = DICTHT_SIZE(d->ht_size_exp[0]) / (HASHTABLE_MIN_FILL * dict_force_resize_ratio) + 1; - for (j = remain_keys; j < 128; j++) { - char *key = stringFromLongLong(j); - retval = dictDelete(d, key); - zfree(key); - assert(retval == DICT_OK); - } - current_dict_used = remain_keys; - assert(dictSize(d) == remain_keys); - assert(dictBuckets(d) == 128); - } - - TEST("Delete one more key, trigger the dict resize") { - current_dict_used--; - char *key = stringFromLongLong(current_dict_used); - retval = dictDelete(d, key); - zfree(key); - new_dict_size = 1UL << _dictNextExp(current_dict_used); - assert(retval == DICT_OK); - assert(dictSize(d) == current_dict_used); - assert(DICTHT_SIZE(d->ht_size_exp[0]) == 128); - assert(DICTHT_SIZE(d->ht_size_exp[1]) == new_dict_size); - - /* Wait for rehashing. */ - dictSetResizeEnabled(DICT_RESIZE_ENABLE); - while (dictIsRehashing(d)) dictRehashMicroseconds(d,1000); - assert(dictSize(d) == current_dict_used); - assert(DICTHT_SIZE(d->ht_size_exp[0]) == new_dict_size); - assert(DICTHT_SIZE(d->ht_size_exp[1]) == 0); - } - - TEST("Restore to original state") { - dictEmpty(d, NULL); - dictSetResizeEnabled(DICT_RESIZE_ENABLE); - } - srand(12345); - start_benchmark(); - for (j = 0; j < count; j++) { - /* Create a dynamically allocated substring */ - char *key = stringFromSubstring(); - - /* Insert the range directly from the large string */ - de = dictAddRaw(d, key, &existing); - assert(de != NULL || existing != NULL); - /* If key already exists NULL is returned so we need to free the temp key string */ - if (de == NULL) zfree(key); - } - end_benchmark("Inserting random substrings (100-500B) from large string with symbols"); - assert((long)dictSize(d) <= count); - dictEmpty(d, NULL); - - start_benchmark(); - for (j = 0; j < count; j++) { - retval = dictAdd(d,stringFromLongLong(j),(void*)j); - assert(retval == DICT_OK); - } - end_benchmark("Inserting via dictAdd() non existing"); - assert((long)dictSize(d) == count); - - dictEmpty(d, NULL); - - start_benchmark(); - for (j = 0; j < count; j++) { - de = dictAddRaw(d,stringFromLongLong(j),NULL); - assert(de != NULL); - } - end_benchmark("Inserting via dictAddRaw() non existing"); - assert((long)dictSize(d) == count); - - start_benchmark(); - for (j = 0; j < count; j++) { - void *key = stringFromLongLong(j); - de = dictAddRaw(d,key,&existing); - assert(existing != NULL); - zfree(key); - } - end_benchmark("Inserting via dictAddRaw() existing (no insertion)"); - assert((long)dictSize(d) == count); - - /* Wait for rehashing. */ - while (dictIsRehashing(d)) { - dictRehashMicroseconds(d,100*1000); - } - - start_benchmark(); - for (j = 0; j < count; j++) { - char *key = stringFromLongLong(j); - dictEntry *de = dictFind(d,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(d,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(d,key); - assert(de != NULL); - zfree(key); - } - end_benchmark("Random access of existing elements"); - - start_benchmark(); - for (j = 0; j < count; j++) { - dictEntry *de = dictGetRandomKey(d); - 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(d,key); - assert(de == NULL); - zfree(key); - } - end_benchmark("Accessing missing"); - - start_benchmark(); - for (j = 0; j < count; j++) { - char *key = stringFromLongLong(j); - retval = dictDelete(d,key); - assert(retval == DICT_OK); - key[0] += 17; /* Change first number to letter. */ - retval = dictAdd(d,key,(void*)j); - assert(retval == DICT_OK); - } - end_benchmark("Removing and adding"); - dictRelease(d); - - TEST("Use dict without values (no_value=1)") { - dictType dt = BenchmarkDictType; - dt.no_value = 1; - - /* Allocate array of size count and fill it with keys (stringFromLongLong(j) */ - char **lookupKeys = zmalloc(sizeof(char*) * count); - for (long j = 0; j < count; j++) - lookupKeys[j] = stringFromLongLong(j); - - - /* Add keys without values. */ - dict *d = dictCreate(&dt); - for (j = 0; j < count; j++) { - retval = dictAdd(d,lookupKeys[j],NULL); - assert(retval == DICT_OK); - } - - /* Now, we should be able to find the keys. */ - for (j = 0; j < count; j++) { - dictEntry *de = dictFind(d,lookupKeys[j]); - assert(de != NULL); - } - - /* Find non exists keys. */ - for (j = 0; j < count; j++) { - /* Temporarily override first char of key */ - char tmp = lookupKeys[j][0]; - lookupKeys[j][0] = 'X'; - dictEntry *de = dictFind(d,lookupKeys[j]); - lookupKeys[j][0] = tmp; - assert(de == NULL); - } - - dictRelease(d); - zfree(lookupKeys); - } - - TEST("Test dictFindLink() functionality") { - dictType dt = BenchmarkDictType; - dict *d = dictCreate(&dt); - - /* find in empty dict */ - dictEntryLink link = dictFindLink(d, "key", NULL); - assert(link == NULL); - - /* Add keys to dict and test */ - for (j = 0; j < 10; j++) { - /* Add another key to dict */ - char *key = stringFromLongLong(j); - retval = dictAdd(d, key, (void*)j); - assert(retval == DICT_OK); - /* find existing keys with dictFindLink() */ - dictEntryLink link = dictFindLink(d, key, NULL); - assert(link != NULL); - assert(*link != NULL); - assert(dictGetKey(*link) != NULL); - - /* Test that the key found is the correct one */ - void *foundKey = dictGetKey(*link); - assert(compareCallback( NULL, foundKey, key)); - - /* Test finding a non-existing key */ - char *nonExistingKey = stringFromLongLong(j + 10); - link = dictFindLink(d, nonExistingKey, NULL); - assert(link == NULL); - - /* Test with bucket parameter */ - dictEntryLink bucket = NULL; - link = dictFindLink(d, key, &bucket); - assert(link != NULL); - assert(bucket != NULL); - - /* Test bucket parameter with non-existing key */ - link = dictFindLink(d, nonExistingKey, &bucket); - assert(link == NULL); - assert(bucket != NULL); /* Bucket should still be set even for non-existing keys */ - - /* Clean up */ - zfree(nonExistingKey); - } - - dictRelease(d); - } - - return 0; -} -#endif |