X-Git-Url: https://git.saurik.com/redis.git/blobdiff_plain/5171777bf112a6a930c4750949037ce741f3bf28..4c8bd905a0751c19279c98d2dbd681a08297e38e:/src/dict.c diff --git a/src/dict.c b/src/dict.c index a1060d45..a573bcd6 100644 --- a/src/dict.c +++ b/src/dict.c @@ -42,6 +42,7 @@ #include #include #include +#include #include "dict.h" #include "zmalloc.h" @@ -94,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(). @@ -193,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 */ @@ -234,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 @@ -247,6 +258,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; @@ -257,9 +292,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]; @@ -267,9 +302,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. @@ -286,18 +320,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) { @@ -314,15 +359,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--; @@ -356,8 +401,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; @@ -390,7 +435,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; } @@ -403,7 +448,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) @@ -413,17 +458,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) { @@ -450,7 +504,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); } @@ -552,7 +607,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; }