zipmaps functions to get, iterate, test for existence. Initial works for Hash data...

diff --git a/Makefile b/Makefile
index 9f7dde3a98d0a93fa3a85d1fa01ce04c00e51a37..15ae660f78020e5517a6b5d26d242dcb28e200fe 100644 (file)
--- a/Makefile
+++ b/Makefile
@@ -14,7 +14,7 @@ endif
 CCOPT= $(CFLAGS) $(CCLINK) $(ARCH) $(PROF)
 DEBUG?= -g -rdynamic -ggdb 
 
 CCOPT= $(CFLAGS) $(CCLINK) $(ARCH) $(PROF)
 DEBUG?= -g -rdynamic -ggdb 
 

-OBJ = adlist.o ae.o anet.o dict.o redis.o sds.o zmalloc.o lzf_c.o lzf_d.o pqsort.o
+OBJ = adlist.o ae.o anet.o dict.o redis.o sds.o zmalloc.o lzf_c.o lzf_d.o pqsort.o zipmap.o

 BENCHOBJ = ae.o anet.o redis-benchmark.o sds.o adlist.o zmalloc.o
 CLIOBJ = anet.o sds.o adlist.o redis-cli.o zmalloc.o
 
 BENCHOBJ = ae.o anet.o redis-benchmark.o sds.o adlist.o zmalloc.o
 CLIOBJ = anet.o sds.o adlist.o redis-cli.o zmalloc.o
 


@@ -39,8 +39,9 @@ redis-benchmark.o: redis-benchmark.c fmacros.h ae.h anet.h sds.h adlist.h \
   zmalloc.h
 redis-cli.o: redis-cli.c fmacros.h anet.h sds.h adlist.h zmalloc.h
 redis.o: redis.c fmacros.h config.h redis.h ae.h sds.h anet.h dict.h \
   zmalloc.h
 redis-cli.o: redis-cli.c fmacros.h anet.h sds.h adlist.h zmalloc.h
 redis.o: redis.c fmacros.h config.h redis.h ae.h sds.h anet.h dict.h \

-  adlist.h zmalloc.h lzf.h pqsort.h staticsymbols.h
+  adlist.h zmalloc.h lzf.h pqsort.h zipmap.h staticsymbols.h

 sds.o: sds.c sds.h zmalloc.h
 sds.o: sds.c sds.h zmalloc.h

+zipmap.o: zipmap.c zmalloc.h

 zmalloc.o: zmalloc.c config.h
 
 redis-server: $(OBJ)
 zmalloc.o: zmalloc.c config.h
 
 redis-server: $(OBJ)

diff --git a/redis.c b/redis.c
index 0464554b47041b8fa760fff5f32b69ba5641fc1b..11056d54cbd6c1979083236614c36c6b7f6f8f19 100644 (file)
--- a/redis.c
+++ b/redis.c
@@ -75,6 +75,7 @@
 #include "zmalloc.h" /* total memory usage aware version of malloc/free */
 #include "lzf.h"    /* LZF compression library */
 #include "pqsort.h" /* Partial qsort for SORT+LIMIT */
 #include "zmalloc.h" /* total memory usage aware version of malloc/free */
 #include "lzf.h"    /* LZF compression library */
 #include "pqsort.h" /* Partial qsort for SORT+LIMIT */

+#include "zipmap.h"

 
 /* Error codes */
 #define REDIS_OK                0
 
 /* Error codes */
 #define REDIS_OK                0


@@ -118,9 +119,13 @@
 #define REDIS_ZSET 3
 #define REDIS_HASH 4
 
 #define REDIS_ZSET 3
 #define REDIS_HASH 4
 

-/* Objects encoding */
+/* Objects encoding. Some kind of objects like Strings and Hashes can be
+ * internally represented in multiple ways. The 'encoding' field of the object
+ * is set to one of this fields for this object. */

 #define REDIS_ENCODING_RAW 0    /* Raw representation */
 #define REDIS_ENCODING_INT 1    /* Encoded as integer */
 #define REDIS_ENCODING_RAW 0    /* Raw representation */
 #define REDIS_ENCODING_INT 1    /* Encoded as integer */

+#define REDIS_ENCODING_ZIPMAP 2 /* Encoded as zipmap */
+#define REDIS_ENCODING_HT 3     /* Encoded as an hash table */

 
 /* Object types only used for dumping to disk */
 #define REDIS_EXPIRETIME 253
 
 /* Object types only used for dumping to disk */
 #define REDIS_EXPIRETIME 253


@@ -1011,7 +1016,7 @@ static dictType zsetDictType = {
 };
 
 /* Db->dict */
 };
 
 /* Db->dict */

-static dictType hashDictType = {
+static dictType dbDictType = {

     dictObjHash,                /* hash function */
     NULL,                       /* key dup */
     NULL,                       /* val dup */
     dictObjHash,                /* hash function */
     NULL,                       /* key dup */
     NULL,                       /* val dup */


@@ -1030,6 +1035,16 @@ static dictType keyptrDictType = {
     NULL                       /* val destructor */
 };
 
     NULL                       /* val destructor */
 };
 

+/* Hash type hash table (note that small hashes are represented with zimpaps) */
+static dictType hashDictType = {
+    dictEncObjHash,             /* hash function */
+    NULL,                       /* key dup */
+    NULL,                       /* val dup */
+    dictEncObjKeyCompare,       /* key compare */
+    dictRedisObjectDestructor,  /* key destructor */
+    dictRedisObjectDestructor   /* val destructor */
+};
+

 /* Keylist hash table type has unencoded redis objects as keys and
  * lists as values. It's used for blocking operations (BLPOP) and to
  * map swapped keys to a list of clients waiting for this keys to be loaded. */
 /* Keylist hash table type has unencoded redis objects as keys and
  * lists as values. It's used for blocking operations (BLPOP) and to
  * map swapped keys to a list of clients waiting for this keys to be loaded. */


@@ -1493,7 +1508,7 @@ static void initServer() {
         exit(1);
     }
     for (j = 0; j < server.dbnum; j++) {
         exit(1);
     }
     for (j = 0; j < server.dbnum; j++) {

-        server.db[j].dict = dictCreate(&hashDictType,NULL);
+        server.db[j].dict = dictCreate(&dbDictType,NULL);

         server.db[j].expires = dictCreate(&keyptrDictType,NULL);
         server.db[j].blockingkeys = dictCreate(&keylistDictType,NULL);
         if (server.vm_enabled)
         server.db[j].expires = dictCreate(&keyptrDictType,NULL);
         server.db[j].blockingkeys = dictCreate(&keylistDictType,NULL);
         if (server.vm_enabled)


@@ -2543,6 +2558,16 @@ static robj *createSetObject(void) {
     return createObject(REDIS_SET,d);
 }
 
     return createObject(REDIS_SET,d);
 }
 

+static robj *createHashObject(void) {
+    /* All the Hashes start as zipmaps. Will be automatically converted
+     * into hash tables if there are enough elements or big elements
+     * inside. */
+    unsigned char *zm = zipmapNew();
+    robj *o = createObject(REDIS_HASH,zm);
+    o->encoding = REDIS_ENCODING_ZIPMAP;
+    return o;
+}
+

 static robj *createZsetObject(void) {
     zset *zs = zmalloc(sizeof(*zs));
 
 static robj *createZsetObject(void) {
     zset *zs = zmalloc(sizeof(*zs));
 

diff --git a/zipmap.c b/zipmap.c
index e8acf86d4ab42dc5cf215252c8e41b159b979ca6..136549bcc8431108ab844a512ee2819bd69802c3 100644 (file)
--- a/zipmap.c
+++ b/zipmap.c
@@ -97,6 +97,11 @@
  * comments above, that is, the max number of trailing bytes in a value. */
 #define ZIPMAP_VALUE_MAX_FREE 5
 
  * comments above, that is, the max number of trailing bytes in a value. */
 #define ZIPMAP_VALUE_MAX_FREE 5
 

+/* The following macro returns the number of bytes needed to encode the length
+ * for the integer value _l, that is, 1 byte for lengths < ZIPMAP_BIGLEN and
+ * 5 bytes for all the other lengths. */
+#define ZIPMAP_LEN_BYTES(_l) (((_l) < ZIPMAP_BIGLEN) ? 1 : sizeof(unsigned int)+1)
+

 /* Create a new empty zipmap. */
 unsigned char *zipmapNew(void) {
     unsigned char *zm = zmalloc(2);
 /* Create a new empty zipmap. */
 unsigned char *zipmapNew(void) {
     unsigned char *zm = zmalloc(2);


@@ -119,7 +124,7 @@ static unsigned int zipmapDecodeLength(unsigned char *p) {
  * the amount of bytes required to encode such a length. */
 static unsigned int zipmapEncodeLength(unsigned char *p, unsigned int len) {
     if (p == NULL) {
  * the amount of bytes required to encode such a length. */
 static unsigned int zipmapEncodeLength(unsigned char *p, unsigned int len) {
     if (p == NULL) {

-        return (len < ZIPMAP_BIGLEN) ? 1 : 1+sizeof(unsigned int);
+        return ZIPMAP_LEN_BYTES(len);

     } else {
         if (len < ZIPMAP_BIGLEN) {
             p[0] = len;
     } else {
         if (len < ZIPMAP_BIGLEN) {
             p[0] = len;


@@ -219,23 +224,24 @@ static unsigned int zipmapRawEntryLength(unsigned char *p) {
     return l + zipmapRawValueLength(p+l);
 }
 
     return l + zipmapRawValueLength(p+l);
 }
 

-/* Set key to value, creating the key if it does not already exist. */
-unsigned char *zipmapSet(unsigned char *zm, unsigned char *key, unsigned int klen, unsigned char *val, unsigned int vlen) {
+/* Set key to value, creating the key if it does not already exist.
+ * If 'update' is not NULL, *update is set to 1 if the key was
+ * already preset, otherwise to 0. */
+unsigned char *zipmapSet(unsigned char *zm, unsigned char *key, unsigned int klen, unsigned char *val, unsigned int vlen, int *update) {

     unsigned int oldlen = 0, freeoff = 0, freelen;
     unsigned int reqlen = zipmapRequiredLength(klen,vlen);
     unsigned int empty, vempty;
     unsigned char *p;
    
     freelen = reqlen;
     unsigned int oldlen = 0, freeoff = 0, freelen;
     unsigned int reqlen = zipmapRequiredLength(klen,vlen);
     unsigned int empty, vempty;
     unsigned char *p;
    
     freelen = reqlen;

+    if (update) *update = 0;

     p = zipmapLookupRaw(zm,key,klen,&oldlen,&freeoff,&freelen);
     if (p == NULL && freelen == 0) {
     p = zipmapLookupRaw(zm,key,klen,&oldlen,&freeoff,&freelen);
     if (p == NULL && freelen == 0) {

-        printf("HERE oldlen:%u required:%u\n",oldlen,reqlen);

         /* Key not found, and not space for the new key. Enlarge */
         zm = zrealloc(zm,oldlen+reqlen);
         p = zm+oldlen-1;
         zm[oldlen+reqlen-1] = ZIPMAP_END;
         freelen = reqlen;
         /* Key not found, and not space for the new key. Enlarge */
         zm = zrealloc(zm,oldlen+reqlen);
         p = zm+oldlen-1;
         zm[oldlen+reqlen-1] = ZIPMAP_END;
         freelen = reqlen;

-        printf("New total length is: %u\n", oldlen+reqlen);

     } else if (p == NULL) {
         /* Key not found, but there is enough free space. */
         p = zm+freeoff;
     } else if (p == NULL) {
         /* Key not found, but there is enough free space. */
         p = zm+freeoff;


@@ -245,6 +251,7 @@ unsigned char *zipmapSet(unsigned char *zm, unsigned char *key, unsigned int kle
 
         /* Key found. Is there enough space for the new value? */
         /* Compute the total length: */
 
         /* Key found. Is there enough space for the new value? */
         /* Compute the total length: */

+        if (update) *update = 1;

         freelen = zipmapRawKeyLength(b);
         b += freelen;
         freelen += zipmapRawValueLength(b);
         freelen = zipmapRawKeyLength(b);
         b += freelen;
         freelen += zipmapRawValueLength(b);


@@ -253,7 +260,7 @@ unsigned char *zipmapSet(unsigned char *zm, unsigned char *key, unsigned int kle
             p[0] = ZIPMAP_EMPTY;
             zipmapEncodeLength(p+1,freelen);
             zm[0] |= ZIPMAP_STATUS_FRAGMENTED;
             p[0] = ZIPMAP_EMPTY;
             zipmapEncodeLength(p+1,freelen);
             zm[0] |= ZIPMAP_STATUS_FRAGMENTED;

-            return zipmapSet(zm,key,klen,val,vlen);
+            return zipmapSet(zm,key,klen,val,vlen,NULL);

         }
     }
 
         }
     }
 


@@ -304,37 +311,58 @@ unsigned char *zipmapDel(unsigned char *zm, unsigned char *key, unsigned int kle
     return zm;
 }
 
     return zm;
 }
 

+/* Call it before to iterate trought elements via zipmapNext() */
+unsigned char *zipmapRewind(unsigned char *zm) {
+    return zm+1;
+}
+

 /* This function is used to iterate through all the zipmap elements.
  * In the first call the first argument is the pointer to the zipmap + 1.
  * In the next calls what zipmapNext returns is used as first argument.
  * Example:
  *
 /* This function is used to iterate through all the zipmap elements.
  * In the first call the first argument is the pointer to the zipmap + 1.
  * In the next calls what zipmapNext returns is used as first argument.
  * Example:
  *

- * unsigned char *i = my_zipmap+1;
+ * unsigned char *i = zipmapRewind(my_zipmap);

  * while((i = zipmapNext(i,&key,&klen,&value,&vlen)) != NULL) {
  *     printf("%d bytes key at $p\n", klen, key);
  *     printf("%d bytes value at $p\n", vlen, value);
  * }
  */
  * while((i = zipmapNext(i,&key,&klen,&value,&vlen)) != NULL) {
  *     printf("%d bytes key at $p\n", klen, key);
  *     printf("%d bytes value at $p\n", vlen, value);
  * }
  */

-unsigned char *zipmapNext(unsigned char *zm, unsigned char **key,
-            unsigned int *klen, unsigned char **value, unsigned int *vlen) {
+unsigned char *zipmapNext(unsigned char *zm, unsigned char **key, unsigned int *klen, unsigned char **value, unsigned int *vlen) {

     while(zm[0] == ZIPMAP_EMPTY)
         zm += zipmapDecodeLength(zm+1);
     if (zm[0] == ZIPMAP_END) return NULL;
     if (key) {
         *key = zm;
         *klen = zipmapDecodeLength(zm);
     while(zm[0] == ZIPMAP_EMPTY)
         zm += zipmapDecodeLength(zm+1);
     if (zm[0] == ZIPMAP_END) return NULL;
     if (key) {
         *key = zm;
         *klen = zipmapDecodeLength(zm);

-        *key += (*klen < ZIPMAP_BIGLEN) ? 1 : sizeof(unsigned int);
+        *key += ZIPMAP_LEN_BYTES(*klen);

     }
     zm += zipmapRawKeyLength(zm);
     if (value) {
         *value = zm+1;
         *vlen = zipmapDecodeLength(zm);
     }
     zm += zipmapRawKeyLength(zm);
     if (value) {
         *value = zm+1;
         *vlen = zipmapDecodeLength(zm);

-        *value += (*vlen < ZIPMAP_BIGLEN) ? 1 : sizeof(unsigned int);
+        *value += ZIPMAP_LEN_BYTES(*vlen);

     }
     zm += zipmapRawValueLength(zm);
     return zm;
 }
 
     }
     zm += zipmapRawValueLength(zm);
     return zm;
 }
 

+/* Search a key and retrieve the pointer and len of the associated value.
+ * If the key is found the function returns 1, otherwise 0. */
+int zipmapGet(unsigned char *zm, unsigned char *key, unsigned int klen, unsigned char **value, unsigned int *vlen) {
+    unsigned char *p;
+
+    if ((p = zipmapLookupRaw(zm,key,klen,NULL,NULL,NULL)) == NULL) return 0;
+    p += zipmapRawKeyLength(p);
+    *vlen = zipmapDecodeLength(p);
+    *value = p + ZIPMAP_LEN_BYTES(*vlen) + 1;
+    return 1;
+}
+
+/* Return 1 if the key exists, otherwise 0 is returned. */
+int zipmapExists(unsigned char *zm, unsigned char *key, unsigned int klen) {
+    return zipmapLookupRaw(zm,key,klen,NULL,NULL,NULL) != NULL;
+}
+

 void zipmapRepr(unsigned char *p) {
     unsigned int l;
 
 void zipmapRepr(unsigned char *p) {
     unsigned int l;
 


@@ -372,29 +400,41 @@ void zipmapRepr(unsigned char *p) {
     printf("\n");
 }
 
     printf("\n");
 }
 

+#ifdef ZIPMAP_TEST_MAIN

 int main(void) {
     unsigned char *zm;
 
     zm = zipmapNew();
 int main(void) {
     unsigned char *zm;
 
     zm = zipmapNew();

-    zm = zipmapSet(zm,(unsigned char*) "hello",5, (unsigned char*) "world!",6);
-    zm = zipmapSet(zm,(unsigned char*) "foo",3, (unsigned char*) "bar",3);
-    zm = zipmapSet(zm,(unsigned char*) "foo",3, (unsigned char*) "!",1);
+    zm = zipmapSet(zm,(unsigned char*) "hello",5, (unsigned char*) "world!",6,NULL);
+    zm = zipmapSet(zm,(unsigned char*) "foo",3, (unsigned char*) "bar",3,NULL);
+    zm = zipmapSet(zm,(unsigned char*) "foo",3, (unsigned char*) "!",1,NULL);

     zipmapRepr(zm);
     zipmapRepr(zm);

-    zm = zipmapSet(zm,(unsigned char*) "foo",3, (unsigned char*) "12345",5);
+    zm = zipmapSet(zm,(unsigned char*) "foo",3, (unsigned char*) "12345",5,NULL);

     zipmapRepr(zm);
     zipmapRepr(zm);

-    zm = zipmapSet(zm,(unsigned char*) "new",3, (unsigned char*) "xx",2);
+    zm = zipmapSet(zm,(unsigned char*) "new",3, (unsigned char*) "xx",2,NULL);

     zipmapRepr(zm);
     zm = zipmapDel(zm,(unsigned char*) "new",3,NULL);
     zipmapRepr(zm);
     zipmapRepr(zm);
     zm = zipmapDel(zm,(unsigned char*) "new",3,NULL);
     zipmapRepr(zm);

-    printf("Iterate trought elements:\n");
+    printf("\nPerform a direct lookup:\n");
+    {
+        unsigned char *value;
+        unsigned int vlen;
+
+        if (zipmapGet(zm,(unsigned char*) "foo",3,&value,&vlen)) {
+            printf("  foo is associated to the %d bytes value: %.*s\n",
+                vlen, vlen, value);
+        }
+    }
+    printf("\nIterate trought elements:\n");

     {
     {

-        unsigned char *i = zm+1;
+        unsigned char *i = zipmapRewind(zm);

         unsigned char *key, *value;
         unsigned int klen, vlen;
 
         while((i = zipmapNext(i,&key,&klen,&value,&vlen)) != NULL) {
         unsigned char *key, *value;
         unsigned int klen, vlen;
 
         while((i = zipmapNext(i,&key,&klen,&value,&vlen)) != NULL) {

-            printf("%d:%.*s => %d:%.*s\n", klen, klen, key, vlen, vlen, value);
+            printf("  %d:%.*s => %d:%.*s\n", klen, klen, key, vlen, vlen, value);

         }
     }
     return 0;
 }
         }
     }
     return 0;
 }

+#endif

diff --git a/zipmap.h b/zipmap.h
new file mode 100644 (file)
index 0000000..bf65740
--- /dev/null
+++ b/zipmap.h
@@ -0,0 +1,46 @@
+/* String -> String Map data structure optimized for size.
+ *
+ * See zipmap.c for more info.
+ *
+ * --------------------------------------------------------------------------
+ *
+ * Copyright (c) 2009-2010, Salvatore Sanfilippo <antirez at gmail dot com>
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions are met:
+ *
+ *   * Redistributions of source code must retain the above copyright notice,
+ *     this list of conditions and the following disclaimer.
+ *   * Redistributions in binary form must reproduce the above copyright
+ *     notice, this list of conditions and the following disclaimer in the
+ *     documentation and/or other materials provided with the distribution.
+ *   * Neither the name of Redis nor the names of its contributors may be used
+ *     to endorse or promote products derived from this software without
+ *     specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+ * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
+ * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
+ * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
+ * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
+ * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
+ * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
+ * POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#ifndef _ZIMMAP_H
+#define _ZIPMAP_H
+
+unsigned char *zipmapNew(void);
+unsigned char *zipmapSet(unsigned char *zm, unsigned char *key, unsigned int klen, unsigned char *val, unsigned int vlen, int *update);
+unsigned char *zipmapDel(unsigned char *zm, unsigned char *key, unsigned int klen, int *deleted);
+unsigned char *zipmapRewind(unsigned char *zm);
+unsigned char *zipmapNext(unsigned char *zm, unsigned char **key, unsigned int *klen, unsigned char **value, unsigned int *vlen);
+int zipmapGet(unsigned char *zm, unsigned char *key, unsigned int klen, unsigned char **value, unsigned int *vlen);
+int zipmapExists(unsigned char *zm, unsigned char *key, unsigned int klen);
+
+#endif