diff options
Diffstat (limited to 'src/dict.c')
| -rw-r--r-- | src/dict.c | 1219 |
1 files changed, 1219 insertions, 0 deletions
diff --git a/src/dict.c b/src/dict.c new file mode 100644 index 0000000..42d9459 --- /dev/null +++ b/src/dict.c @@ -0,0 +1,1219 @@ +/* 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 "dict.h" +#include <assert.h> + +/* Using dictEnableResize() / dictDisableResize() we make possible to + * enable/disable resizing 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 int dict_can_resize = 1; +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 = malloc(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->iterators = 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) +{ + int minimal; + + if (!dict_can_resize || 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 */ +int dictExpand(dict *d, unsigned long size) +{ + /* 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); + + /* 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; + n.table = calloc(realsize*sizeof(dictEntry*),1); + 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; +} + +/* 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. */ + if (!dictIsRehashing(d)) 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) { + free(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 for an amount of time between ms milliseconds and ms+1 milliseconds */ +int dictRehashMilliseconds(dict *d, int ms) { + 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 there are + * no safe iterators bound to 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->iterators == 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 he wishes. + * + * 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 = malloc(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; + else + d->ht[table].table[idx] = he->next; + if (!nofree) { + dictFreeKey(d, he); + dictFreeVal(d, he); + free(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); + free(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); + free(he); + ht->used--; + he = nextHe; + } + } + /* Free the table and the allocated cache structure */ + free(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); + free(d); +} + +dictEntry *dictFind(dict *d, const void *key) +{ + dictEntry *he; + uint64_t h, idx, table; + + if (d->ht[0].used + d->ht[1].used == 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. */ +long long dictFingerprint(dict *d) { + 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 * 265 + hash = hash ^ (hash >> 14); + hash = (hash + (hash << 2)) + (hash << 4); // hash * 21 + hash = hash ^ (hash >> 28); + hash = hash + (hash << 31); + } + return hash; +} + +dictIterator *dictGetIterator(dict *d) +{ + dictIterator *iter = malloc(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) + iter->d->iterators++; + else + iter->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) + iter->d->iterators--; + else + assert(iter->fingerprint == dictFingerprint(iter->d)); + } + free(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 + (random() % (d->ht[0].size + + d->ht[1].size - + 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 = random() & 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); + else + break; + } + + 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 = random() & 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; + continue; + } + 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 = random() & 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; +} + +/* Function to reverse bits. Algorithm from: + * http://graphics.stanford.edu/~seander/bithacks.html#ReverseParallel */ +static unsigned long rev(unsigned long v) { + unsigned long s = 8 * sizeof(v); // bit size; must be power of 2 + unsigned long mask = ~0; + 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; + + 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)); + } + + return v; +} + +/* ------------------------- private functions ------------------------------ */ + +/* 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 (d->ht[0].used >= d->ht[0].size && + (dict_can_resize || + d->ht[0].used/d->ht[0].size > dict_force_resize_ratio)) + { + return dictExpand(d, d->ht[0].used*2); + } + 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->iterators = 0; +} + +void dictEnableResize(void) { + dict_can_resize = 1; +} + +void dictDisableResize(void) { + dict_can_resize = 0; +} + +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 (d->ht[0].used + d->ht[1].used == 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, + "No stats available for empty dictionaries\n"); + } + + /* 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: %ld\n" + " number of elements: %ld\n" + " different slots: %ld\n" + " max chain length: %ld\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(), teturn 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 DICT_BENCHMARK_MAIN + +#include "sds.h" + +uint64_t hashCallback(const void *key) { + return dictGenHashFunction((unsigned char*)key, sdslen((char*)key)); +} + +int compareCallback(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; +} + +void freeCallback(void *privdata, void *val) { + DICT_NOTUSED(privdata); + + sdsfree(val); +} + +dictType BenchmarkDictType = { + hashCallback, + NULL, + NULL, + compareCallback, + freeCallback, + 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); + +/* dict-benchmark [count] */ +int main(int argc, char **argv) { + long j; + long long start, elapsed; + dict *dict = dictCreate(&BenchmarkDictType,NULL); + long count = 0; + + if (argc == 2) { + count = strtol(argv[1],NULL,10); + } else { + count = 5000000; + } + + start_benchmark(); + for (j = 0; j < count; j++) { + int retval = dictAdd(dict,sdsfromlonglong(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++) { + sds key = sdsfromlonglong(j); + dictEntry *de = dictFind(dict,key); + assert(de != NULL); + sdsfree(key); + } + end_benchmark("Linear access of existing elements"); + + start_benchmark(); + for (j = 0; j < count; j++) { + sds key = sdsfromlonglong(j); + dictEntry *de = dictFind(dict,key); + assert(de != NULL); + sdsfree(key); + } + end_benchmark("Linear access of existing elements (2nd round)"); + + start_benchmark(); + for (j = 0; j < count; j++) { + sds key = sdsfromlonglong(rand() % count); + dictEntry *de = dictFind(dict,key); + assert(de != NULL); + sdsfree(key); + } + end_benchmark("Random access of existing elements"); + + start_benchmark(); + for (j = 0; j < count; j++) { + sds key = sdsfromlonglong(rand() % count); + key[0] = 'X'; + dictEntry *de = dictFind(dict,key); + assert(de == NULL); + sdsfree(key); + } + end_benchmark("Accessing missing"); + + start_benchmark(); + for (j = 0; j < count; j++) { + sds key = sdsfromlonglong(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"); +} +#endif |