Remove comment

[redis.git] / src / dict.c

diff --git a/src/dict.c b/src/dict.c
index 0d4aacb7dfca58307d7eb2e79b6d7b180a4c5dd6..6b7010ba2efba11231be224f5fe0479d8ccb605f 100644 (file)
--- a/src/dict.c
+++ b/src/dict.c
@@ -42,6 +42,7 @@
 #include <assert.h>
 #include <limits.h>
 #include <sys/time.h>
 #include <assert.h>
 #include <limits.h>
 #include <sys/time.h>

+#include <ctype.h>

 
 #include "dict.h"
 #include "zmalloc.h"
 
 #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
 /* 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 int dict_can_resize = 1;

+static unsigned int dict_force_resize_ratio = 5;

 
 /* -------------------------- private prototypes ---------------------------- */
 
 
 /* -------------------------- private prototypes ---------------------------- */
 


@@ -89,6 +95,15 @@ unsigned int dictGenHashFunction(const unsigned char *buf, int len) {
     return hash;
 }
 
     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().
 /* ----------------------------- API implementation ------------------------- */
 
 /* Reset an hashtable already initialized with ht_init().


@@ -125,7 +140,7 @@ int _dictInit(dict *d, dictType *type,
 }
 
 /* Resize the table to the minimal size that contains all the elements,
 }
 
 /* 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;
 int dictResize(dict *d)
 {
     int minimal;


@@ -148,14 +163,12 @@ int dictExpand(dict *d, unsigned long size)
     if (dictIsRehashing(d) || d->ht[0].used > size)
         return DICT_ERR;
 
     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.size = realsize;
     n.sizemask = realsize-1;

-    n.table = zmalloc(realsize*sizeof(dictEntry*));
+    n.table = zcalloc(realsize*sizeof(dictEntry*));

     n.used = 0;
 
     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) {
     /* 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 +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 */
 
         /* 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 */
         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 */


@@ -495,14 +509,23 @@ dictEntry *dictGetRandomKey(dict *d)
 /* Expand the hash table if needed */
 static int _dictExpandIfNeeded(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 (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 dictExpand(d, ((d->ht[0].size > d->ht[0].used) ?
                                     d->ht[0].size : d->ht[0].used)*2);

+    }

     return DICT_OK;
 }
 
     return DICT_OK;
 }
 


@@ -617,6 +640,12 @@ void dictDisableResize(void) {
     dict_can_resize = 0;
 }
 
     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)
 /* ----------------------- StringCopy Hash Table Type ------------------------*/
 
 static unsigned int _dictStringCopyHTHashFunction(const void *key)


@@ -680,3 +709,4 @@ dictType dictTypeHeapStringCopyKeyValue = {
     _dictStringDestructor,         /* key destructor */
     _dictStringDestructor,         /* val destructor */
 };
     _dictStringDestructor,         /* key destructor */
     _dictStringDestructor,         /* val destructor */
 };

+#endif