Fix overflow in mstime() in redis-cli and benchmark.

[redis.git] / src / dict.c

diff --git a/src/dict.c b/src/dict.c
index 9d3368412d0443a8c22db585101bd95290915625..1e7d7609d2841726e435b4da9f3bfbce529dab21 100644 (file)
--- a/src/dict.c
+++ b/src/dict.c
@@ -5,7 +5,7 @@
  * tables of power of two in size are used, collisions are handled by
  * chaining. See the source code for more information... :)
  *
  * tables of power of two in size are used, collisions are handled by
  * chaining. See the source code for more information... :)
  *

- * Copyright (c) 2006-2010, Salvatore Sanfilippo <antirez at gmail dot com>
+ * Copyright (c) 2006-2012, Salvatore Sanfilippo <antirez at gmail dot com>

  * All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
  * All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without


@@ -85,19 +85,73 @@ unsigned int dictIdentityHashFunction(unsigned int key)
     return key;
 }
 
     return key;
 }
 

-/* 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;
+static uint32_t dict_hash_function_seed = 5381;

 
 

-    while (len--)
-        hash = ((hash << 5) + hash) + (*buf++); /* hash * 33 + c */
-    return hash;
+void dictSetHashFunctionSeed(uint32_t seed) {
+    dict_hash_function_seed = seed;
+}
+
+uint32_t dictGetHashFunctionSeed(void) {
+    return dict_hash_function_seed;
+}
+
+/* MurmurHash2, by Austin Appleby
+ * Note - This code makes a few assumptions about how your machine behaves -
+ * 1. We can read a 4-byte value from any address without crashing
+ * 2. sizeof(int) == 4
+ *
+ * And it has a few limitations -
+ *
+ * 1. It will not work incrementally.
+ * 2. It will not produce the same results on little-endian and big-endian
+ *    machines.
+ */
+unsigned int dictGenHashFunction(const void *key, int len) {
+    /* 'm' and 'r' are mixing constants generated offline.
+     They're not really 'magic', they just happen to work well.  */
+    uint32_t seed = dict_hash_function_seed;
+    const uint32_t m = 0x5bd1e995;
+    const int r = 24;
+
+    /* Initialize the hash to a 'random' value */
+    uint32_t h = seed ^ len;
+
+    /* Mix 4 bytes at a time into the hash */
+    const unsigned char *data = (const unsigned char *)key;
+
+    while(len >= 4) {
+        uint32_t k = *(uint32_t*)data;
+
+        k *= m;
+        k ^= k >> r;
+        k *= m;
+
+        h *= m;
+        h ^= k;
+
+        data += 4;
+        len -= 4;
+    }
+
+    /* Handle the last few bytes of the input array  */
+    switch(len) {
+    case 3: h ^= data[2] << 16;
+    case 2: h ^= data[1] << 8;
+    case 1: h ^= data[0]; h *= m;
+    };
+
+    /* Do a few final mixes of the hash to ensure the last few
+     * bytes are well-incorporated. */
+    h ^= h >> 13;
+    h *= m;
+    h ^= h >> 15;
+
+    return (unsigned int)h;

 }
 
 }
 

-/* And a case insensitive version */
+/* And a case insensitive hash function (based on djb hash) */

 unsigned int dictGenCaseHashFunction(const unsigned char *buf, int len) {
 unsigned int dictGenCaseHashFunction(const unsigned char *buf, int len) {

-    unsigned int hash = 5381;
+    unsigned int hash = (unsigned int)dict_hash_function_seed;

 
     while (len--)
         hash = ((hash << 5) + hash) + (tolower(*buf++)); /* hash * 33 + c */
 
     while (len--)
         hash = ((hash << 5) + hash) + (tolower(*buf++)); /* hash * 33 + c */


@@ -106,8 +160,8 @@ unsigned int dictGenCaseHashFunction(const unsigned char *buf, int len) {
 
 /* ----------------------------- API implementation ------------------------- */
 
 
 /* ----------------------------- API implementation ------------------------- */
 

-/* Reset an hashtable already initialized with ht_init().
- * NOTE: This function should only called by ht_destroy(). */
+/* Reset a hash table already initialized with ht_init().
+ * NOTE: This function should only be called by ht_destroy(). */

 static void _dictReset(dictht *ht)
 {
     ht->table = NULL;
 static void _dictReset(dictht *ht)
 {
     ht->table = NULL;


@@ -140,7 +194,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 ratio near to <= 1 */
+ * but with the invariant of a USED/BUCKETS ratio near to <= 1 */

 int dictResize(dict *d)
 {
     int minimal;
 int dictResize(dict *d)
 {
     int minimal;


@@ -152,18 +206,18 @@ int dictResize(dict *d)
     return dictExpand(d, minimal);
 }
 
     return dictExpand(d, minimal);
 }
 

-/* Expand or create the hashtable */
+/* Expand or create the hash table */

 int dictExpand(dict *d, unsigned long size)
 {
 int dictExpand(dict *d, unsigned long size)
 {

-    dictht n; /* the new hashtable */
+    dictht n; /* the new hash table */

     unsigned long realsize = _dictNextPower(size);
 
     /* the size is invalid if it is smaller than the number of
     unsigned long realsize = _dictNextPower(size);
 
     /* the size is invalid if it is smaller than the number of

-     * elements already inside the hashtable */
+     * elements already inside the hash table */

     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 */
+    /* Allocate the new hash table and initialize all pointers to NULL */

     n.size = realsize;
     n.sizemask = realsize-1;
     n.table = zcalloc(realsize*sizeof(dictEntry*));
     n.size = realsize;
     n.sizemask = realsize-1;
     n.table = zcalloc(realsize*sizeof(dictEntry*));


@@ -262,7 +316,7 @@ int dictAdd(dict *d, void *key, void *val)
     dictEntry *entry = dictAddRaw(d,key);
 
     if (!entry) return DICT_ERR;
     dictEntry *entry = dictAddRaw(d,key);
 
     if (!entry) return DICT_ERR;

-    dictSetHashVal(d, entry, val);
+    dictSetVal(d, entry, val);

     return DICT_OK;
 }
 
     return DICT_OK;
 }
 


@@ -270,11 +324,11 @@ int dictAdd(dict *d, void *key, void *val)
  * a value returns the dictEntry structure to the user, that will make
  * sure to fill the value field as he wishes.
  *
  * 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
+ * This function is also directly exposed to user API to be called

  * mainly in order to store non-pointers inside the hash value, example:
  *
  * entry = dictAddRaw(dict,mykey);
  * mainly in order to store non-pointers inside the hash value, example:
  *
  * entry = dictAddRaw(dict,mykey);

- * if (entry != NULL) dictSetValSignedInteger(entry,1000);
+ * if (entry != NULL) dictSetSignedIntegerVal(entry,1000);

  *
  * Return values:
  *
  *
  * Return values:
  *


@@ -302,7 +356,7 @@ dictEntry *dictAddRaw(dict *d, void *key)
     ht->used++;
 
     /* Set the hash entry fields. */
     ht->used++;
 
     /* Set the hash entry fields. */

-    dictSetHashKey(d, entry, key);
+    dictSetKey(d, entry, key);

     return entry;
 }
 
     return entry;
 }
 


@@ -326,8 +380,8 @@ int dictReplace(dict *d, void *key, void *val)
      * you want to increment (set), and then decrement (free), and not the
      * reverse. */
     auxentry = *entry;
      * 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;
 }
 
     return 0;
 }
 


@@ -359,15 +413,15 @@ static int dictGenericDelete(dict *d, const void *key, int nofree)
         he = d->ht[table].table[idx];
         prevHe = NULL;
         while(he) {
         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) {
                 /* 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--;
                 }
                 zfree(he);
                 d->ht[table].used--;


@@ -401,8 +455,8 @@ int _dictClear(dict *d, dictht *ht)
         if ((he = ht->table[i]) == NULL) continue;
         while(he) {
             nextHe = he->next;
         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;
             zfree(he);
             ht->used--;
             he = nextHe;


@@ -435,7 +489,7 @@ dictEntry *dictFind(dict *d, const void *key)
         idx = h & d->ht[table].sizemask;
         he = d->ht[table].table[idx];
         while(he) {
         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;
         }
                 return he;
             he = he->next;
         }


@@ -448,7 +502,7 @@ void *dictFetchValue(dict *d, const void *key) {
     dictEntry *he;
 
     he = dictFind(d,key);
     dictEntry *he;
 
     he = dictFind(d,key);

-    return he ? dictGetEntryVal(he) : NULL;
+    return he ? dictGetVal(he) : NULL;

 }
 
 dictIterator *dictGetIterator(dict *d)
 }
 
 dictIterator *dictGetIterator(dict *d)


@@ -597,7 +651,7 @@ static int _dictKeyIndex(dict *d, const void *key)
     unsigned int h, idx, table;
     dictEntry *he;
 
     unsigned int h, idx, table;
     dictEntry *he;
 

-    /* Expand the hashtable if needed */
+    /* Expand the hash table if needed */

     if (_dictExpandIfNeeded(d) == DICT_ERR)
         return -1;
     /* Compute the key hash value */
     if (_dictExpandIfNeeded(d) == DICT_ERR)
         return -1;
     /* Compute the key hash value */


@@ -607,7 +661,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) {
         /* 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;
         }
                 return -1;
             he = he->next;
         }


@@ -623,6 +677,21 @@ void dictEmpty(dict *d) {
     d->iterators = 0;
 }
 
     d->iterators = 0;
 }
 

+void dictEnableResize(void) {
+    dict_can_resize = 1;
+}
+
+void dictDisableResize(void) {
+    dict_can_resize = 0;
+}
+
+#if 0
+
+/* The following is code that we don't use for Redis currently, but that is part
+of the library. */
+
+/* ----------------------- Debugging ------------------------*/
+

 #define DICT_STATS_VECTLEN 50
 static void _dictPrintStatsHt(dictht *ht) {
     unsigned long i, slots = 0, chainlen, maxchainlen = 0;
 #define DICT_STATS_VECTLEN 50
 static void _dictPrintStatsHt(dictht *ht) {
     unsigned long i, slots = 0, chainlen, maxchainlen = 0;


@@ -676,20 +745,6 @@ void dictPrintStats(dict *d) {
     }
 }
 
     }
 }
 

-void dictEnableResize(void) {
-    dict_can_resize = 1;
-}
-
-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)
 /* ----------------------- StringCopy Hash Table Type ------------------------*/
 
 static unsigned int _dictStringCopyHTHashFunction(const void *key)