X-Git-Url: https://git.saurik.com/redis.git/blobdiff_plain/b1e0bd4b9b5a9c203a4400bd52a06e377876f423..53272781d0b7f664fc6e3fcd5c9032dd09103bbc:/src/dict.c diff --git a/src/dict.c b/src/dict.c index 79c005b6..24001fdd 100644 --- a/src/dict.c +++ b/src/dict.c @@ -42,6 +42,7 @@ #include #include #include +#include #include "dict.h" #include "zmalloc.h" @@ -49,35 +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; - -/* ---------------------------- Utility funcitons --------------------------- */ - -static void _dictPanic(const char *fmt, ...) -{ - va_list ap; - - va_start(ap, fmt); - fprintf(stderr, "\nDICT LIBRARY PANIC: "); - vfprintf(stderr, fmt, ap); - fprintf(stderr, "\n\n"); - va_end(ap); -} - -/* ------------------------- Heap Management Wrappers------------------------ */ - -static void *_dictAlloc(size_t size) -{ - void *p = zmalloc(size); - if (p == NULL) - _dictPanic("Out of memory"); - return p; -} - -static void _dictFree(void *ptr) { - zfree(ptr); -} +static unsigned int dict_force_resize_ratio = 5; /* -------------------------- private prototypes ---------------------------- */ @@ -116,6 +95,15 @@ unsigned int dictGenHashFunction(const unsigned char *buf, int len) { return hash; } +/* And a case insensitive version */ +unsigned int dictGenCaseHashFunction(const unsigned char *buf, int len) { + unsigned int hash = 5381; + + while (len--) + hash = ((hash << 5) + hash) + (tolower(*buf++)); /* hash * 33 + c */ + return hash; +} + /* ----------------------------- API implementation ------------------------- */ /* Reset an hashtable already initialized with ht_init(). @@ -132,7 +120,7 @@ static void _dictReset(dictht *ht) dict *dictCreate(dictType *type, void *privDataPtr) { - dict *d = _dictAlloc(sizeof(*d)); + dict *d = zmalloc(sizeof(*d)); _dictInit(d,type,privDataPtr); return d; @@ -152,7 +140,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; @@ -175,14 +163,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 = _dictAlloc(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) { @@ -208,7 +194,7 @@ int dictRehash(dict *d, int n) { /* Check if we already rehashed the whole table... */ if (d->ht[0].used == 0) { - _dictFree(d->ht[0].table); + zfree(d->ht[0].table); d->ht[0] = d->ht[1]; _dictReset(&d->ht[1]); d->rehashidx = -1; @@ -217,6 +203,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 */ @@ -258,9 +245,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 @@ -285,7 +272,7 @@ int dictAdd(dict *d, void *key, void *val) /* Allocates the memory and stores key */ ht = dictIsRehashing(d) ? &d->ht[1] : &d->ht[0]; - entry = _dictAlloc(sizeof(*entry)); + entry = zmalloc(sizeof(*entry)); entry->next = ht->table[index]; ht->table[index] = entry; ht->used++; @@ -348,7 +335,7 @@ static int dictGenericDelete(dict *d, const void *key, int nofree) dictFreeEntryKey(d, he); dictFreeEntryVal(d, he); } - _dictFree(he); + zfree(he); d->ht[table].used--; return DICT_OK; } @@ -382,13 +369,13 @@ int _dictClear(dict *d, dictht *ht) nextHe = he->next; dictFreeEntryKey(d, he); dictFreeEntryVal(d, he); - _dictFree(he); + zfree(he); ht->used--; he = nextHe; } } /* Free the table and the allocated cache structure */ - _dictFree(ht->table); + zfree(ht->table); /* Re-initialize the table */ _dictReset(ht); return DICT_OK; /* never fails */ @@ -399,7 +386,7 @@ void dictRelease(dict *d) { _dictClear(d,&d->ht[0]); _dictClear(d,&d->ht[1]); - _dictFree(d); + zfree(d); } dictEntry *dictFind(dict *d, const void *key) @@ -432,22 +419,31 @@ void *dictFetchValue(dict *d, const void *key) { dictIterator *dictGetIterator(dict *d) { - dictIterator *iter = _dictAlloc(sizeof(*iter)); + dictIterator *iter = zmalloc(sizeof(*iter)); iter->d = d; iter->table = 0; iter->index = -1; + iter->safe = 0; iter->entry = NULL; iter->nextEntry = NULL; return iter; } +dictIterator *dictGetSafeIterator(dict *d) { + dictIterator *i = dictGetIterator(d); + + i->safe = 1; + return i; +} + dictEntry *dictNext(dictIterator *iter) { while (1) { if (iter->entry == NULL) { dictht *ht = &iter->d->ht[iter->table]; - if (iter->index == -1 && iter->table == 0) 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) { @@ -474,8 +470,9 @@ dictEntry *dictNext(dictIterator *iter) void dictReleaseIterator(dictIterator *iter) { - if (!(iter->index == -1 && iter->table == 0)) iter->d->iterators--; - _dictFree(iter); + if (iter->safe && !(iter->index == -1 && iter->table == 0)) + iter->d->iterators--; + zfree(iter); } /* Return a random entry from the hash table. Useful to @@ -522,14 +519,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; } @@ -644,6 +650,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) @@ -654,7 +666,7 @@ static unsigned int _dictStringCopyHTHashFunction(const void *key) static void *_dictStringDup(void *privdata, const void *key) { int len = strlen(key); - char *copy = _dictAlloc(len+1); + char *copy = zmalloc(len+1); DICT_NOTUSED(privdata); memcpy(copy, key, len); @@ -674,7 +686,7 @@ static void _dictStringDestructor(void *privdata, void *key) { DICT_NOTUSED(privdata); - _dictFree(key); + zfree(key); } dictType dictTypeHeapStringCopyKey = { @@ -707,3 +719,4 @@ dictType dictTypeHeapStringCopyKeyValue = { _dictStringDestructor, /* key destructor */ _dictStringDestructor, /* val destructor */ }; +#endif