X-Git-Url: https://git.saurik.com/redis.git/blobdiff_plain/d9dd352b3693e1ad8ab2e0993b4f0a275d7fd512..7a0c72f34550c3811324464661f1b463ccfd362b:/src/dict.c diff --git a/src/dict.c b/src/dict.c index 0d4aacb7..53e16be0 100644 --- a/src/dict.c +++ b/src/dict.c @@ -42,6 +42,7 @@ #include #include #include +#include #include "dict.h" #include "zmalloc.h" @@ -49,8 +50,13 @@ /* 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. */ + * 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: an 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 ---------------------------- */ @@ -79,16 +85,35 @@ unsigned int dictIdentityHashFunction(unsigned int key) return key; } +static int dict_hash_function_seed = 5381; + +void dictSetHashFunctionSeed(unsigned int seed) { + dict_hash_function_seed = seed; +} + +unsigned int dictGetHashFunctionSeed(void) { + return dict_hash_function_seed; +} + /* Generic hash function (a popular one from Bernstein). * I tested a few and this was the best. */ unsigned int dictGenHashFunction(const unsigned char *buf, int len) { - unsigned int hash = 5381; + unsigned int hash = dict_hash_function_seed; while (len--) hash = ((hash << 5) + hash) + (*buf++); /* hash * 33 + c */ return hash; } +/* And a case insensitive version */ +unsigned int dictGenCaseHashFunction(const unsigned char *buf, int len) { + unsigned int hash = dict_hash_function_seed; + + while (len--) + hash = ((hash << 5) + hash) + (tolower(*buf++)); /* hash * 33 + c */ + return hash; +} + /* ----------------------------- API implementation ------------------------- */ /* Reset an hashtable already initialized with ht_init(). @@ -125,7 +150,7 @@ int _dictInit(dict *d, dictType *type, } /* Resize the table to the minimal size that contains all the elements, - * but with the invariant of a USER/BUCKETS ration near to <= 1 */ + * but with the invariant of a USER/BUCKETS ratio near to <= 1 */ int dictResize(dict *d) { int minimal; @@ -148,14 +173,12 @@ int dictExpand(dict *d, unsigned long size) if (dictIsRehashing(d) || d->ht[0].used > size) return DICT_ERR; + /* Allocate the new hashtable and initialize all pointers to NULL */ n.size = realsize; n.sizemask = realsize-1; - n.table = zmalloc(realsize*sizeof(dictEntry*)); + n.table = zcalloc(realsize*sizeof(dictEntry*)); n.used = 0; - /* Initialize all the pointers to NULL */ - memset(n.table, 0, realsize*sizeof(dictEntry*)); - /* 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) { @@ -190,6 +213,7 @@ int dictRehash(dict *d, int n) { /* 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)d->rehashidx); while(d->ht[0].table[d->rehashidx] == NULL) d->rehashidx++; de = d->ht[0].table[d->rehashidx]; /* Move all the keys in this bucket from the old to the new hash HT */ @@ -231,9 +255,9 @@ int dictRehashMilliseconds(dict *d, int ms) { } /* This function performs just a step of rehashing, and only if there are - * not 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. + * 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 @@ -244,6 +268,30 @@ static void _dictRehashStep(dict *d) { /* Add an element to the target hash table */ int dictAdd(dict *d, void *key, void *val) +{ + dictEntry *entry = dictAddRaw(d,key); + + if (!entry) return DICT_ERR; + dictSetVal(d, entry, val); + return DICT_OK; +} + +/* Low level add. 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 expoed to user API to be called + * mainly in order to store non-pointers inside the hash value, example: + * + * entry = dictAddRaw(dict,mykey); + * if (entry != NULL) dictSetSignedIntegerVal(entry,1000); + * + * Return values: + * + * If key already exists NULL is returned. + * If key was added, the hash entry is returned to be manipulated by the caller. + */ +dictEntry *dictAddRaw(dict *d, void *key) { int index; dictEntry *entry; @@ -254,9 +302,9 @@ int dictAdd(dict *d, void *key, void *val) /* Get the index of the new element, or -1 if * the element already exists. */ if ((index = _dictKeyIndex(d, key)) == -1) - return DICT_ERR; + return NULL; - /* Allocates the memory and stores key */ + /* Allocate the memory and store the new entry */ ht = dictIsRehashing(d) ? &d->ht[1] : &d->ht[0]; entry = zmalloc(sizeof(*entry)); entry->next = ht->table[index]; @@ -264,9 +312,8 @@ int dictAdd(dict *d, void *key, void *val) ht->used++; /* Set the hash entry fields. */ - dictSetHashKey(d, entry, key); - dictSetHashVal(d, entry, val); - return DICT_OK; + dictSetKey(d, entry, key); + return entry; } /* Add an element, discarding the old if the key already exists. @@ -283,18 +330,29 @@ int dictReplace(dict *d, void *key, void *val) return 1; /* It already exists, get the entry */ entry = dictFind(d, key); - /* Free the old value and set the new one */ /* 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 = *entry; - dictSetHashVal(d, entry, val); - dictFreeEntryVal(d, &auxentry); + dictSetVal(d, entry, val); + dictFreeVal(d, &auxentry); return 0; } +/* dictReplaceRaw() 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 *dictReplaceRaw(dict *d, void *key) { + dictEntry *entry = dictFind(d,key); + + return entry ? entry : dictAddRaw(d,key); +} + /* Search and remove an element */ static int dictGenericDelete(dict *d, const void *key, int nofree) { @@ -311,15 +369,15 @@ static int dictGenericDelete(dict *d, const void *key, int nofree) he = d->ht[table].table[idx]; prevHe = NULL; while(he) { - if (dictCompareHashKeys(d, key, he->key)) { + if (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) { - dictFreeEntryKey(d, he); - dictFreeEntryVal(d, he); + dictFreeKey(d, he); + dictFreeVal(d, he); } zfree(he); d->ht[table].used--; @@ -353,8 +411,8 @@ int _dictClear(dict *d, dictht *ht) if ((he = ht->table[i]) == NULL) continue; while(he) { nextHe = he->next; - dictFreeEntryKey(d, he); - dictFreeEntryVal(d, he); + dictFreeKey(d, he); + dictFreeVal(d, he); zfree(he); ht->used--; he = nextHe; @@ -387,7 +445,7 @@ dictEntry *dictFind(dict *d, const void *key) idx = h & d->ht[table].sizemask; he = d->ht[table].table[idx]; while(he) { - if (dictCompareHashKeys(d, key, he->key)) + if (dictCompareKeys(d, key, he->key)) return he; he = he->next; } @@ -400,7 +458,7 @@ void *dictFetchValue(dict *d, const void *key) { dictEntry *he; he = dictFind(d,key); - return he ? dictGetEntryVal(he) : NULL; + return he ? dictGetVal(he) : NULL; } dictIterator *dictGetIterator(dict *d) @@ -410,17 +468,26 @@ dictIterator *dictGetIterator(dict *d) 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) iter->d->iterators++; + if (iter->safe && iter->index == -1 && iter->table == 0) + iter->d->iterators++; iter->index++; if (iter->index >= (signed) ht->size) { if (dictIsRehashing(iter->d) && iter->table == 0) { @@ -447,7 +514,8 @@ dictEntry *dictNext(dictIterator *iter) void dictReleaseIterator(dictIterator *iter) { - if (!(iter->index == -1 && iter->table == 0)) iter->d->iterators--; + if (iter->safe && !(iter->index == -1 && iter->table == 0)) + iter->d->iterators--; zfree(iter); } @@ -495,14 +563,23 @@ dictEntry *dictGetRandomKey(dict *d) /* Expand the hash table if needed */ static int _dictExpandIfNeeded(dict *d) { - /* If the hash table is empty expand it to the intial size, - * if the table is "full" dobule its size. */ + /* Incremental rehashing already in progress. Return. */ if (dictIsRehashing(d)) return DICT_OK; - if (d->ht[0].size == 0) - return dictExpand(d, DICT_HT_INITIAL_SIZE); - if (d->ht[0].used >= d->ht[0].size && dict_can_resize) + + /* If the hash table is empty expand it to the intial 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].size > d->ht[0].used) ? d->ht[0].size : d->ht[0].used)*2); + } return DICT_OK; } @@ -540,7 +617,7 @@ static int _dictKeyIndex(dict *d, const void *key) /* Search if this slot does not already contain the given key */ he = d->ht[table].table[idx]; while(he) { - if (dictCompareHashKeys(d, key, he->key)) + if (dictCompareKeys(d, key, he->key)) return -1; he = he->next; } @@ -617,6 +694,12 @@ void dictDisableResize(void) { dict_can_resize = 0; } +#if 0 + +/* The following are just example hash table types implementations. + * Not useful for Redis so they are commented out. + */ + /* ----------------------- StringCopy Hash Table Type ------------------------*/ static unsigned int _dictStringCopyHTHashFunction(const void *key) @@ -680,3 +763,4 @@ dictType dictTypeHeapStringCopyKeyValue = { _dictStringDestructor, /* key destructor */ _dictStringDestructor, /* val destructor */ }; +#endif