#include <assert.h>
#include <limits.h>
#include <sys/time.h>
+#include <ctype.h>
#include "dict.h"
#include "zmalloc.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. */
+ * 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 ---------------------------- */
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().
}
/* 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;
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) {
/* 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 */
}
/* 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
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) {
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);
}
/* 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;
}
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)
_dictStringDestructor, /* key destructor */
_dictStringDestructor, /* val destructor */
};
+#endif
projects / redis.git / blobdiff