dict.c Rehashing visualization code snippet added to utils.

2 files changed, 145 insertions, 0 deletions

diff --git a/utils/hashtable/README b/utils/hashtable/README
new file mode 100644
index 000000000..e2862f012
--- /dev/null
+++ b/utils/hashtable/README
@@ -0,0 +1,13 @@
+Hash table implementation related utilities.
+
+rehashing.c
+---
+
+Visually show buckets in the two hash tables between rehashings. Also stress
+test getRandomKeys() implementation, that may actually disappear from
+Redis soon, however visualizaiton some code is reusable in new bugs
+investigation.
+
+Compile with:
+
+    cc -I ../../src/ rehashing.c ../../src/zmalloc.c ../../src/dict.c -o rehashing_test
diff --git a/utils/hashtable/rehashing.c b/utils/hashtable/rehashing.c
new file mode 100644
index 000000000..df1f52bb1
--- /dev/null
+++ b/utils/hashtable/rehashing.c
@@ -0,0 +1,132 @@
+#include "redis.h"
+#include "dict.h"
+
+void _redisAssert(char *x, char *y, int l) {
+    printf("ASSERT: %s %s %d\n",x,y,l);
+    exit(1);
+}
+
+unsigned int dictKeyHash(const void *keyp) {
+    unsigned long key = (unsigned long)keyp;
+    key = dictGenHashFunction(&key,sizeof(key));
+    key += ~(key << 15);
+    key ^=  (key >> 10);
+    key +=  (key << 3);
+    key ^=  (key >> 6);
+    key += ~(key << 11);
+    key ^=  (key >> 16);
+    return key;
+}
+
+int dictKeyCompare(void *privdata, const void *key1, const void *key2) {
+    unsigned long k1 = (unsigned long)key1;
+    unsigned long k2 = (unsigned long)key2;
+    return k1 == k2;
+}
+
+dictType dictTypeTest = {
+    dictKeyHash,                   /* hash function */
+    NULL,                          /* key dup */
+    NULL,                          /* val dup */
+    dictKeyCompare,                /* key compare */
+    NULL,                          /* key destructor */
+    NULL                           /* val destructor */
+};
+
+void showBuckets(dictht ht) {
+    if (ht.table == NULL) {
+        printf("NULL\n");
+    } else {
+        int j;
+        for (j = 0; j < ht.size; j++) {
+            printf("%c", ht.table[j] ? '1' : '0');
+        }
+        printf("\n");
+    }
+}
+
+void show(dict *d) {
+    int j;
+    if (d->rehashidx != -1) {
+        printf("rhidx: ");
+        for (j = 0; j < d->rehashidx; j++)
+            printf(".");
+        printf("|\n");
+    }
+    printf("ht[0]: ");
+    showBuckets(d->ht[0]);
+    printf("ht[1]: ");
+    showBuckets(d->ht[1]);
+    printf("\n");
+}
+
+int sortPointers(const void *a, const void *b) {
+    unsigned long la, lb;
+
+    la = (long) (*((dictEntry**)a));
+    lb = (long) (*((dictEntry**)b));
+    return la-lb;
+}
+
+void stressGetKeys(dict *d, int times) {
+    int j;
+    dictEntry **des = zmalloc(sizeof(dictEntry*)*dictSize(d));
+    for (j = 0; j < times; j++) {
+        int requested = rand() % (dictSize(d)+1);
+        int returned = dictGetRandomKeys(d, des, requested);
+        if (requested != returned) {
+            printf("*** ERROR! Req: %d, Ret: %d\n", requested, returned);
+            exit(1);
+        }
+        qsort(des,returned,sizeof(dictEntry*),sortPointers);
+        if (returned > 1) {
+            int i;
+            for (i = 0; i < returned-1; i++) {
+                if (des[i] == des[i+1]) {
+                    printf("*** ERROR! Duplicated element detected\n");
+                    exit(1);
+                }
+            }
+        }
+    }
+    zfree(des);
+}
+
+#define MAX1 120
+#define MAX2 1000
+int main(void) {
+    dict *d = dictCreate(&dictTypeTest,NULL);
+    unsigned long i;
+    srand(time(NULL));
+
+    for (i = 0; i < MAX1; i++) {
+        dictAdd(d,(void*)i,NULL);
+        show(d);
+    }
+    printf("Size: %d\n", (int)dictSize(d));
+
+    for (i = 0; i < MAX1; i++) {
+        dictDelete(d,(void*)i);
+        dictResize(d);
+        show(d);
+    }
+    dictRelease(d);
+
+    d = dictCreate(&dictTypeTest,NULL);
+    printf("Getkeys stress test\n");
+
+    for (i = 0; i < MAX2; i++) {
+        dictAdd(d,(void*)i,NULL);
+        stressGetKeys(d,100);
+    }
+
+    for (i = 0; i < MAX2; i++) {
+        dictDelete(d,(void*)i);
+        dictResize(d);
+        stressGetKeys(d,100);
+    }
+    dictRelease(d);
+
+    printf("TEST PASSED!\n");
+    return 0;
+}