X-Git-Url: https://git.saurik.com/redis.git/blobdiff_plain/c09c2c3b04f0df0e37c24ee10d29bdf49ae070ff..bb57b965c4252a48472d99a1b2e7a30d66d65796:/ziplist.c?ds=sidebyside

diff --git a/ziplist.c b/ziplist.c
index 55fcc80c..16e9dbc1 100644
--- a/ziplist.c
+++ b/ziplist.c
@@ -23,7 +23,13 @@
 #include "sds.h"
 #include "ziplist.h"
 
+/* Important note: the ZIP_END value is used to depict the end of the
+ * ziplist structure. When a pointer contains an entry, the first couple
+ * of bytes contain the encoded length of the previous entry. This length
+ * is encoded as ZIP_ENC_RAW length, so the first two bits will contain 00
+ * and the byte will therefore never have a value of 255. */
 #define ZIP_END 255
+#define ZIP_BIGLEN 254
 
 /* Entry encoding */
 #define ZIP_ENC_RAW     0
@@ -39,10 +45,18 @@
 
 /* Utility macros */
 #define ZIPLIST_BYTES(zl) (*((unsigned int*)(zl)))
-#define ZIPLIST_LENGTH(zl) (*((zl)+sizeof(unsigned int)))
-#define ZIPLIST_HEADER_SIZE (sizeof(unsigned int)+1)
+#define ZIPLIST_TAIL_OFFSET(zl) (*((zl)+sizeof(unsigned int)))
+#define ZIPLIST_LENGTH(zl) (*((zl)+2*sizeof(unsigned int)))
+#define ZIPLIST_HEADER_SIZE (2*sizeof(unsigned int)+1)
 #define ZIPLIST_INCR_LENGTH(zl,incr) { \
-    if (ZIPLIST_LENGTH(zl) < (ZIP_END-1)) ZIPLIST_LENGTH(zl)+=incr; }
+    if (ZIPLIST_LENGTH(zl) < ZIP_BIGLEN) ZIPLIST_LENGTH(zl)+=incr; }
+
+typedef struct zlentry {
+    unsigned int prevrawlensize, prevrawlen;
+    unsigned int lensize, len;
+    unsigned int headersize;
+    unsigned char encoding;
+} zlentry;
 
 /* Return bytes needed to store integer encoded by 'encoding' */
 static unsigned int zipEncodingSize(char encoding) {
@@ -115,6 +129,14 @@ static unsigned int zipEncodeLength(unsigned char *p, char encoding, unsigned in
     return len;
 }
 
+/* Return the difference in number of bytes needed to store the new length
+ * "len" on the entry pointed to by "p". */
+static int zipPrevLenByteDiff(unsigned char *p, unsigned int len) {
+    unsigned int prevlensize;
+    zipDecodeLength(p,&prevlensize);
+    return zipEncodeLength(NULL,ZIP_ENC_RAW,len)-prevlensize;
+}
+
 /* Check if string pointed to by 'entry' can be encoded as an integer.
  * Stores the integer value in 'v' and its encoding in 'encoding'.
  * Warning: this function requires a NULL-terminated string! */
@@ -123,7 +145,7 @@ static int zipTryEncoding(unsigned char *entry, long long *v, char *encoding) {
     char *eptr;
 
     if (entry[0] == '-' || (entry[0] >= '0' && entry[0] <= '9')) {
-        value = strtoll(entry,&eptr,10);
+        value = strtoll((char*)entry,&eptr,10);
         if (eptr[0] != '\0') return 0;
         if (value >= SHRT_MIN && value <= SHRT_MAX) {
             *encoding = ZIP_ENC_SHORT;
@@ -177,11 +199,20 @@ static long long zipLoadInteger(unsigned char *p, char encoding) {
     return ret;
 }
 
-/* Return the total amount used by an entry (encoded length + payload). */
+/* Return a struct with all information about an entry. */
+static zlentry zipEntry(unsigned char *p) {
+    zlentry e;
+    e.prevrawlen = zipDecodeLength(p,&e.prevrawlensize);
+    e.len = zipDecodeLength(p+e.prevrawlensize,&e.lensize);
+    e.headersize = e.prevrawlensize+e.lensize;
+    e.encoding = ZIP_ENCODING(p+e.prevrawlensize);
+    return e;
+}
+
+/* Return the total number of bytes used by the entry at "p". */
 static unsigned int zipRawEntryLength(unsigned char *p) {
-    unsigned int lensize, len;
-    len = zipDecodeLength(p, &lensize);
-    return lensize + len;
+    zlentry e = zipEntry(p);
+    return e.headersize + e.len;
 }
 
 /* Create a new empty ziplist. */
@@ -189,6 +220,7 @@ unsigned char *ziplistNew(void) {
     unsigned int bytes = ZIPLIST_HEADER_SIZE+1;
     unsigned char *zl = zmalloc(bytes);
     ZIPLIST_BYTES(zl) = bytes;
+    ZIPLIST_TAIL_OFFSET(zl) = ZIPLIST_HEADER_SIZE;
     ZIPLIST_LENGTH(zl) = 0;
     zl[bytes-1] = ZIP_END;
     return zl;
@@ -217,17 +249,30 @@ static unsigned char *ziplistTail(unsigned char *zl) {
 }
 
 unsigned char *ziplistPush(unsigned char *zl, unsigned char *entry, unsigned int elen, int where) {
-    unsigned int curlen = ZIPLIST_BYTES(zl), reqlen;
-    unsigned char *p;
+    unsigned int curlen = ZIPLIST_BYTES(zl), reqlen, prevlen;
+    unsigned char *p, *curtail;
     char encoding = ZIP_ENC_RAW;
     long long value;
 
+    /* We need to store the length of the current tail when the list
+     * is non-empty and we push at the tail. */
+    curtail = zl+ZIPLIST_TAIL_OFFSET(zl);
+    if (where == ZIPLIST_TAIL && curtail[0] != ZIP_END) {
+        prevlen = zipRawEntryLength(curtail);
+    } else {
+        prevlen = 0;
+    }
+
     /* See if the entry can be encoded */
     if (zipTryEncoding(entry,&value,&encoding)) {
         reqlen = zipEncodingSize(encoding);
     } else {
         reqlen = elen;
     }
+
+    /* We need space for both the length of the previous entry and
+     * the length of the payload. */
+    reqlen += zipEncodeLength(NULL,ZIP_ENC_RAW,prevlen);
     reqlen += zipEncodeLength(NULL,encoding,elen);
 
     /* Resize the ziplist and move if needed */
@@ -242,7 +287,17 @@ unsigned char *ziplistPush(unsigned char *zl, unsigned char *entry, unsigned int
         p = zl+curlen-1;
     }
 
+    /* Update tail offset if this is not the first element */
+    if (curtail[0] != ZIP_END) {
+        if (where == ZIPLIST_HEAD) {
+            ZIPLIST_TAIL_OFFSET(zl) += reqlen;
+        } else {
+            ZIPLIST_TAIL_OFFSET(zl) += prevlen;
+        }
+    }
+
     /* Write the entry */
+    p += zipEncodeLength(p,ZIP_ENC_RAW,prevlen);
     p += zipEncodeLength(p,encoding,elen);
     if (encoding != ZIP_ENC_RAW) {
         zipSaveInteger(p,value,encoding);
@@ -255,7 +310,8 @@ unsigned char *ziplistPush(unsigned char *zl, unsigned char *entry, unsigned int
 
 unsigned char *ziplistPop(unsigned char *zl, sds *target, int where) {
     unsigned int curlen = ZIPLIST_BYTES(zl), rawlen;
-    unsigned int len, lensize;
+    zlentry entry;
+    int nextdiff = 0;
     unsigned char *p;
     long long value;
     if (target) *target = NULL;
@@ -263,24 +319,43 @@ unsigned char *ziplistPop(unsigned char *zl, sds *target, int where) {
     /* Get pointer to element to remove */
     p = (where == ZIPLIST_HEAD) ? ziplistHead(zl) : ziplistTail(zl);
     if (*p == ZIP_END) return zl;
-    len = zipDecodeLength(p,&lensize);
+
+    entry = zipEntry(p);
+    rawlen = entry.headersize+entry.len;
     if (target) {
-        if (ZIP_ENCODING(p) == ZIP_ENC_RAW) {
-            *target = sdsnewlen(p+lensize,len);
+        if (entry.encoding == ZIP_ENC_RAW) {
+            *target = sdsnewlen(p+entry.headersize,entry.len);
         } else {
-            value = zipLoadInteger(p+lensize,ZIP_ENCODING(p));
+            value = zipLoadInteger(p+entry.headersize,entry.encoding);
             *target = sdscatprintf(sdsempty(), "%lld", value);
         }
     }
 
-    /* Move list to front when popping from the head */
-    rawlen = lensize+len;
     if (where == ZIPLIST_HEAD) {
-        memmove(p,p+rawlen,curlen-ZIPLIST_HEADER_SIZE-len);
+        /* The next entry will now be the head of the list */
+        if (p[rawlen] != ZIP_END) {
+            /* Tricky: storing the length of the previous entry in the next
+             * entry (this previous length is always 0 when popping from the
+             * head), might reduce the number of bytes needed.
+             *
+             * In this special case (new length is 0), we know that the
+             * byte difference to store is always <= 0, which means that
+             * we always have space to store it. */
+            nextdiff = zipPrevLenByteDiff(p+rawlen,0);
+            zipEncodeLength(p+rawlen-nextdiff,ZIP_ENC_RAW,0);
+        }
+        /* Move list to the front */
+        memmove(p,p+rawlen-nextdiff,curlen-ZIPLIST_HEADER_SIZE-rawlen+nextdiff);
+
+        /* Subtract the gained space from the tail offset */
+        ZIPLIST_TAIL_OFFSET(zl) -= rawlen+nextdiff;
+    } else {
+        /* Subtract the length of the previous element from the tail offset. */
+        ZIPLIST_TAIL_OFFSET(zl) -= entry.prevrawlen;
     }
 
     /* Resize and update length */
-    zl = ziplistResize(zl,curlen-rawlen);
+    zl = ziplistResize(zl,curlen-rawlen+nextdiff);
     ZIPLIST_INCR_LENGTH(zl,-1);
     return zl;
 }
@@ -305,19 +380,20 @@ unsigned char *ziplistNext(unsigned char *p) {
  * on the encoding of the entry. 'e' is always set to NULL to be able
  * to find out whether the string pointer or the integer value was set.
  * Return 0 if 'p' points to the end of the zipmap, 1 otherwise. */
-unsigned int ziplistGet(unsigned char *p, unsigned char **e, unsigned int *elen, long long *v) {
-    unsigned int len, lensize;
+unsigned int ziplistGet(unsigned char *p, unsigned char **sstr, unsigned int *slen, long long *sval) {
+    zlentry entry;
     if (*p == ZIP_END) return 0;
-    if (e) *e = NULL;
-    len = zipDecodeLength(p,&lensize);
-    if (ZIP_ENCODING(p) == ZIP_ENC_RAW) {
-        if (e) {
-            *elen = len;
-            *e = p+lensize;
+    if (sstr) *sstr = NULL;
+
+    entry = zipEntry(p);
+    if (entry.encoding == ZIP_ENC_RAW) {
+        if (sstr) {
+            *slen = entry.len;
+            *sstr = p+entry.headersize;
         }
     } else {
-        if (v) {
-            *v = zipLoadInteger(p+lensize,ZIP_ENCODING(p));
+        if (sval) {
+            *sval = zipLoadInteger(p+entry.headersize,entry.encoding);
         }
     }
     return 1;
@@ -326,7 +402,7 @@ unsigned int ziplistGet(unsigned char *p, unsigned char **e, unsigned int *elen,
 /* Delete a range of entries from the ziplist. */
 unsigned char *ziplistDeleteRange(unsigned char *zl, unsigned int index, unsigned int num) {
     unsigned char *p, *first = ziplistIndex(zl, index);
-    unsigned int i, deleted = 0, totlen, newlen;
+    unsigned int i, totlen, deleted = 0;
     for (p = first, i = 0; *p != ZIP_END && i < num; i++) {
         p += zipRawEntryLength(p);
         deleted++;
@@ -366,46 +442,72 @@ unsigned char *ziplistDelete(unsigned char *zl, unsigned char **p) {
 }
 
 /* Compare entry pointer to by 'p' with 'entry'. Return 1 if equal. */
-unsigned int ziplistCompare(unsigned char *p, unsigned char *entry, unsigned int elen) {
-    unsigned int zlen, lensize;
-    char encoding;
-    long long zval, eval;
+unsigned int ziplistCompare(unsigned char *p, unsigned char *sstr, unsigned int slen) {
+    zlentry entry;
+    unsigned char sencoding;
+    long long val, sval;
     if (*p == ZIP_END) return 0;
 
-    zlen = zipDecodeLength(p,&lensize);
-    if (zipTryEncoding(entry,&eval,&encoding)) {
-        /* Do integer compare */
-        zval = zipLoadInteger(p+lensize,ZIP_ENCODING(p));
-        return zval == eval;
-    } else {
+    entry = zipEntry(p);
+    if (entry.encoding == ZIP_ENC_RAW) {
         /* Raw compare */
-        if (zlen == elen) {
-            return memcmp(p+lensize,entry,elen) == 0;
+        if (entry.len == slen) {
+            return memcmp(p+entry.headersize,sstr,slen) == 0;
         } else {
             return 0;
         }
+    } else {
+        /* Try to compare encoded values */
+        if (zipTryEncoding(sstr,&sval,&sencoding)) {
+            if (entry.encoding == sencoding) {
+                val = zipLoadInteger(p+entry.headersize,entry.encoding);
+                return val == sval;
+            }
+        }
     }
+    return 0;
+}
+
+/* Return length of ziplist. */
+unsigned int ziplistLen(unsigned char *zl) {
+    unsigned int len = 0;
+    if (ZIPLIST_LENGTH(zl) < ZIP_BIGLEN) {
+        len = ZIPLIST_LENGTH(zl);
+    } else {
+        unsigned char *p = zl+ZIPLIST_HEADER_SIZE;
+        while (*p != ZIP_END) {
+            p += zipRawEntryLength(p);
+            len++;
+        }
+
+        /* Re-store length if small enough */
+        if (len < ZIP_BIGLEN) ZIPLIST_LENGTH(zl) = len;
+    }
+    return len;
+}
+
+/* Return size in bytes of ziplist. */
+unsigned int ziplistSize(unsigned char *zl) {
+    return ZIPLIST_BYTES(zl);
 }
 
 void ziplistRepr(unsigned char *zl) {
-    unsigned char *p, encoding;
-    unsigned int l, lsize;
-    long long value;
+    unsigned char *p;
+    zlentry entry;
 
     printf("{total bytes %d} {length %u}\n",ZIPLIST_BYTES(zl), ZIPLIST_LENGTH(zl));
     p = ziplistHead(zl);
     while(*p != ZIP_END) {
-        l = zipDecodeLength(p,&lsize);
-        printf("{header %u, payload %u} ",lsize,l);
-        encoding = ZIP_ENCODING(p);
-        p += lsize;
-        if (encoding == ZIP_ENC_RAW) {
-            fwrite(p,l,1,stdout);
+        entry = zipEntry(p);
+        printf("{offset %ld, header %u, payload %u} ",p-zl,entry.headersize,entry.len);
+        p += entry.headersize;
+        if (entry.encoding == ZIP_ENC_RAW) {
+            fwrite(p,entry.len,1,stdout);
         } else {
-            printf("%lld", zipLoadInteger(p,encoding));
+            printf("%lld", zipLoadInteger(p,entry.encoding));
         }
         printf("\n");
-        p += l;
+        p += entry.len;
     }
     printf("{end}\n\n");
 }
@@ -460,6 +562,14 @@ int main(int argc, char **argv) {
     printf("Pop head: %s (length %ld)\n", s, sdslen(s));
     ziplistRepr(zl);
 
+    zl = ziplistPop(zl, &s, ZIPLIST_TAIL);
+    printf("Pop tail: %s (length %ld)\n", s, sdslen(s));
+    ziplistRepr(zl);
+
+    zl = ziplistPop(zl, &s, ZIPLIST_TAIL);
+    printf("Pop tail: %s (length %ld)\n", s, sdslen(s));
+    ziplistRepr(zl);
+
     printf("Iterate list from 0 to end:\n");
     {
         zl = createList();
@@ -586,21 +696,21 @@ int main(int argc, char **argv) {
         zl = createList();
         p = ziplistIndex(zl, 0);
         if (!ziplistCompare(p,"hello",5)) {
-            printf("ERROR\n");
+            printf("ERROR: not \"hello\"\n");
             return;
         }
         if (ziplistCompare(p,"hella",5)) {
-            printf("ERROR\n");
+            printf("ERROR: \"hella\"\n");
             return;
         }
 
         p = ziplistIndex(zl, 3);
         if (!ziplistCompare(p,"1024",4)) {
-            printf("ERROR\n");
+            printf("ERROR: not \"1024\"\n");
             return;
         }
         if (ziplistCompare(p,"1025",4)) {
-            printf("ERROR\n");
+            printf("ERROR: \"1025\"\n");
             return;
         }
         printf("SUCCESS\n");