support for include directive in config parser

[redis.git] / zipmap.c

diff --git a/zipmap.c b/zipmap.c
index ba5ea0e3ea20337e52d57d7f5c1e86088141f20a..f45ef0dd64c7d795638178d732934bb9755b6a36 100644 (file)
--- a/zipmap.c
+++ b/zipmap.c
@@ -67,14 +67,14 @@
  *
  * The most compact representation of the above two elements hash is actually:
  *
  *
  * The most compact representation of the above two elements hash is actually:
  *

- * "\x00\x03\x00foo\x03\x00bar\x05\x00hello\x05\x00world\xff"
+ * "\x00\x03foo\x03\x00bar\x05hello\x05\x00world\xff"

  *
  * Empty space is marked using a 254 bytes + a <len> (coded as already
  * specified). The length includes the 254 bytes in the count and the
  * space taken by the <len> field. So for instance removing the "foo" key
  * from the zipmap above will lead to the following representation:
  *
  *
  * Empty space is marked using a 254 bytes + a <len> (coded as already
  * specified). The length includes the 254 bytes in the count and the
  * space taken by the <len> field. So for instance removing the "foo" key
  * from the zipmap above will lead to the following representation:
  *

- * "\xfd\x10........\x05\x00hello\x05\x00world\xff"
+ * "\x00\xfd\x10........\x05hello\x05\x00world\xff"

  *
  * Note that because empty space, keys, values, are all prefixed length
  * "objects", the lookup will take O(N) where N is the numeber of elements
  *
  * Note that because empty space, keys, values, are all prefixed length
  * "objects", the lookup will take O(N) where N is the numeber of elements


@@ -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);


@@ -111,7 +116,7 @@ static unsigned int zipmapDecodeLength(unsigned char *p) {
     unsigned int len = *p;
 
     if (len < ZIPMAP_BIGLEN) return len;
     unsigned int len = *p;
 
     if (len < ZIPMAP_BIGLEN) return len;

-    memcpy(&len,p,sizeof(unsigned int));
+    memcpy(&len,p+1,sizeof(unsigned int));

     return len;
 }
 
     return len;
 }
 


@@ -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;


@@ -147,7 +152,7 @@ static unsigned int zipmapEncodeLength(unsigned char *p, unsigned int len) {
 static unsigned char *zipmapLookupRaw(unsigned char *zm, unsigned char *key, unsigned int klen, unsigned int *totlen, unsigned int *freeoff, unsigned int *freelen) {
     unsigned char *p = zm+1;
     unsigned int l;
 static unsigned char *zipmapLookupRaw(unsigned char *zm, unsigned char *key, unsigned int klen, unsigned int *totlen, unsigned int *freeoff, unsigned int *freelen) {
     unsigned char *p = zm+1;
     unsigned int l;

-    unsigned int reqfreelen;
+    unsigned int reqfreelen = 0; /* initialized just to prevent warning */

 
     if (freelen) {
         reqfreelen = *freelen;
 
     if (freelen) {
         reqfreelen = *freelen;


@@ -192,14 +197,14 @@ static unsigned long zipmapRequiredLength(unsigned int klen, unsigned int vlen)
     return l;
 }
 
     return l;
 }
 

-/* Return the total amonut used by a key (encoded length + payload) */
+/* Return the total amount used by a key (encoded length + payload) */

 static unsigned int zipmapRawKeyLength(unsigned char *p) {
     unsigned int l = zipmapDecodeLength(p);
     
     return zipmapEncodeLength(NULL,l) + l;
 }
 
 static unsigned int zipmapRawKeyLength(unsigned char *p) {
     unsigned int l = zipmapDecodeLength(p);
     
     return zipmapEncodeLength(NULL,l) + l;
 }
 

-/* Return the total amonut used by a value
+/* Return the total amount used by a value

  * (encoded length + single byte free count + payload) */
 static unsigned int zipmapRawValueLength(unsigned char *p) {
     unsigned int l = zipmapDecodeLength(p);
  * (encoded length + single byte free count + payload) */
 static unsigned int zipmapRawValueLength(unsigned char *p) {
     unsigned int l = zipmapDecodeLength(p);


@@ -210,23 +215,33 @@ static unsigned int zipmapRawValueLength(unsigned char *p) {
     return used;
 }
 
     return used;
 }
 

-/* 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) {
+/* If 'p' points to a key, this function returns the total amount of
+ * bytes used to store this entry (entry = key + associated value + trailing
+ * free space if any). */
+static unsigned int zipmapRawEntryLength(unsigned char *p) {
+    unsigned int l = zipmapRawKeyLength(p);
+
+    return l + zipmapRawValueLength(p+l);
+}
+
+/* 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;


@@ -236,14 +251,16 @@ 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);
         if (freelen < reqlen) {
         freelen = zipmapRawKeyLength(b);
         b += freelen;
         freelen += zipmapRawValueLength(b);
         if (freelen < reqlen) {

-            /* Mark this blog as free and recurse */
+            /* Mark this entry as free and recurse */

             p[0] = ZIPMAP_EMPTY;
             zipmapEncodeLength(p+1,freelen);
             p[0] = ZIPMAP_EMPTY;
             zipmapEncodeLength(p+1,freelen);

-            return zipmapSet(zm,key,klen,val,vlen);
+            zm[0] |= ZIPMAP_STATUS_FRAGMENTED;
+            return zipmapSet(zm,key,klen,val,vlen,NULL);

         }
     }
 
         }
     }
 


@@ -277,6 +294,84 @@ unsigned char *zipmapSet(unsigned char *zm, unsigned char *key, unsigned int kle
     return zm;
 }
 
     return zm;
 }
 

+/* Remove the specified key. If 'deleted' is not NULL the pointed integer is
+ * set to 0 if the key was not found, to 1 if it was found and deleted. */
+unsigned char *zipmapDel(unsigned char *zm, unsigned char *key, unsigned int klen, int *deleted) {
+    unsigned char *p = zipmapLookupRaw(zm,key,klen,NULL,NULL,NULL);
+    if (p) {
+        unsigned int freelen = zipmapRawEntryLength(p);
+
+        p[0] = ZIPMAP_EMPTY;
+        zipmapEncodeLength(p+1,freelen);
+        zm[0] |= ZIPMAP_STATUS_FRAGMENTED;
+        if (deleted) *deleted = 1;
+    } else {
+        if (deleted) *deleted = 0;
+    }
+    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:
+ *
+ * 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);
+ * }
+ */
+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);
+        *key += ZIPMAP_LEN_BYTES(*klen);
+    }
+    zm += zipmapRawKeyLength(zm);
+    if (value) {
+        *value = zm+1;
+        *vlen = zipmapDecodeLength(zm);
+        *value += ZIPMAP_LEN_BYTES(*vlen);
+    }
+    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;
+}
+
+/* Return the number of entries inside a zipmap */
+unsigned int zipmapLen(unsigned char *zm) {
+    unsigned char *p = zipmapRewind(zm);
+    unsigned int len = 0;
+
+    while((p = zipmapNext(p,NULL,NULL,NULL,NULL)) != NULL) len++;
+    return len;
+}
+

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


@@ -303,7 +398,7 @@ void zipmapRepr(unsigned char *p) {
             p += zipmapEncodeLength(NULL,l);
             e = *p++;
             fwrite(p,l,1,stdout);
             p += zipmapEncodeLength(NULL,l);
             e = *p++;
             fwrite(p,l,1,stdout);

-            p += l;
+            p += l+e;

             if (e) {
                 printf("[");
                 while(e--) printf(".");
             if (e) {
                 printf("[");
                 while(e--) printf(".");


@@ -314,12 +409,49 @@ 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*) "name",4, (unsigned char*) "foo",3,NULL);
+    zm = zipmapSet(zm,(unsigned char*) "surname",7, (unsigned char*) "foo",3,NULL);
+    zm = zipmapSet(zm,(unsigned char*) "age",3, (unsigned char*) "foo",3,NULL);

     zipmapRepr(zm);
     zipmapRepr(zm);

+    exit(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);
+    zm = zipmapSet(zm,(unsigned char*) "foo",3, (unsigned char*) "12345",5,NULL);
+    zipmapRepr(zm);
+    zm = zipmapSet(zm,(unsigned char*) "new",3, (unsigned char*) "xx",2,NULL);
+    zm = zipmapSet(zm,(unsigned char*) "noval",5, (unsigned char*) "",0,NULL);
+    zipmapRepr(zm);
+    zm = zipmapDel(zm,(unsigned char*) "new",3,NULL);
+    zipmapRepr(zm);
+    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 = zipmapRewind(zm);
+        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);
+        }
+    }

     return 0;
 }
     return 0;
 }

+#endif