ziplist.c

   1 /* Memory layout of a ziplist, containing "foo", "bar", "quux":
   2  * <zlbytes><zllen><len>"foo"<len>"bar"<len>"quux"
   3  *
   4  * <zlbytes> is an unsigned integer to hold the number of bytes that
   5  * the ziplist occupies. This is stored to not have to traverse the ziplist
   6  * to know the new length when pushing.
   7  *
   8  * <zllen> is the number of items in the ziplist. When this value is
   9  * greater than 254, we need to traverse the entire list to know
  10  * how many items it holds.
  11  *
  12  * <len> is the number of bytes occupied by a single entry. When this
  13  * number is greater than 253, the length will occupy 5 bytes, where
  14  * the extra bytes contain an unsigned integer to hold the length.
  15  */
  16
  17 #include <stdio.h>
  18 #include <string.h>
  19 #include <assert.h>
  20 #include "zmalloc.h"
  21 #include "sds.h"
  22 #include "ziplist.h"
  23 #include "zip.c"
  24
  25 #define ZIPLIST_BYTES(zl) (*((unsigned int*)(zl)))
  26 #define ZIPLIST_LENGTH(zl) (*((zl)+sizeof(unsigned int)))
  27 #define ZIPLIST_HEADER_SIZE (sizeof(unsigned int)+1)
  28
  29 /* Create a new empty ziplist. */
  30 unsigned char *ziplistNew(void) {
  31     unsigned int bytes = ZIPLIST_HEADER_SIZE+1;
  32     unsigned char *zl = zmalloc(bytes);
  33     ZIPLIST_BYTES(zl) = bytes;
  34     ZIPLIST_LENGTH(zl) = 0;
  35     zl[bytes-1] = ZIP_END;
  36     return zl;
  37 }
  38
  39 static unsigned char *ziplistResize(unsigned char *zl, unsigned int len) {
  40     zl = zipResize(zl,len);
  41     ZIPLIST_BYTES(zl) = len;
  42     zl[len-1] = ZIP_END;
  43     return zl;
  44 }
  45
  46 static unsigned char *ziplistHead(unsigned char *zl) {
  47     return zl+ZIPLIST_HEADER_SIZE;
  48 }
  49
  50 static unsigned char *ziplistTail(unsigned char *zl) {
  51     unsigned char *p, *q;
  52     p = q = ziplistHead(zl);
  53     while (*p != ZIP_END) {
  54         q = p;
  55         p += zipRawEntryLength(p);
  56     }
  57     return q;
  58 }
  59
  60 unsigned char *ziplistPush(unsigned char *zl, unsigned char *entry, unsigned int elen, int where) {
  61     unsigned int curlen = ZIPLIST_BYTES(zl);
  62     unsigned int reqlen = zipEncodeLength(NULL,elen)+elen;
  63     unsigned char *p;
  64
  65     /* Resize the ziplist */
  66     zl = ziplistResize(zl,curlen+reqlen);
  67
  68     if (where == ZIPLIST_HEAD) {
  69         p = zl+ZIPLIST_HEADER_SIZE;
  70         if (*p != ZIP_END) {
  71             /* Subtract one because of the ZIP_END bytes */
  72             memmove(p+reqlen,p,curlen-ZIPLIST_HEADER_SIZE-1);
  73         }
  74     } else {
  75         p = zl+curlen-1;
  76     }
  77
  78     /* Increase length */
  79     if (ZIPLIST_LENGTH(zl) < ZIP_BIGLEN) ZIPLIST_LENGTH(zl)++;
  80
  81     /* Write the entry */
  82     p += zipEncodeLength(p,elen);
  83     memcpy(p,entry,elen);
  84     return zl;
  85 }
  86
  87 unsigned char *ziplistPop(unsigned char *zl, sds *value, int where) {
  88     unsigned int curlen = ZIPLIST_BYTES(zl), len, rlen;
  89     unsigned char *p;
  90     *value = NULL;
  91
  92     /* Get pointer to element to remove */
  93     p = (where == ZIPLIST_HEAD) ? ziplistHead(zl) : ziplistTail(zl);
  94     if (*p == ZIP_END) return zl;
  95     len = zipDecodeLength(p);
  96     *value = sdsnewlen(p+zipEncodeLength(NULL,len),len);
  97
  98     /* Move list to front when popping from the head */
  99     rlen = zipRawEntryLength(p);
 100     if (where == ZIPLIST_HEAD) {
 101         memmove(p,p+rlen,curlen-ZIPLIST_HEADER_SIZE-len);
 102     }
 103
 104     /* Resize and update length */
 105     zl = ziplistResize(zl,curlen-rlen);
 106     if (ZIPLIST_LENGTH(zl) < ZIP_BIGLEN) ZIPLIST_LENGTH(zl)--;
 107     return zl;
 108 }
 109
 110 void ziplistRepr(unsigned char *zl) {
 111     unsigned char *p;
 112     unsigned int l;
 113
 114     printf("{bytes %d} {length %u}\n",ZIPLIST_BYTES(zl), ZIPLIST_LENGTH(zl));
 115     p = ziplistHead(zl);
 116     while(*p != ZIP_END) {
 117         l = zipDecodeLength(p);
 118         printf("{key %u}",l);
 119         p += zipEncodeLength(NULL,l);
 120         fwrite(p,l,1,stdout);
 121         printf("\n");
 122         p += l;
 123     }
 124     printf("{end}\n\n");
 125 }
 126
 127 #ifdef ZIPLIST_TEST_MAIN
 128 int main(int argc, char **argv) {
 129     unsigned char *zl;
 130     sds s;
 131
 132     zl = ziplistNew();
 133     zl = ziplistPush(zl, (unsigned char*)"foo", 3, ZIPLIST_TAIL);
 134     ziplistRepr(zl);
 135     zl = ziplistPush(zl, (unsigned char*)"quux", 4, ZIPLIST_TAIL);
 136     ziplistRepr(zl);
 137     zl = ziplistPush(zl, (unsigned char*)"hello", 5, ZIPLIST_HEAD);
 138     ziplistRepr(zl);
 139
 140     zl = ziplistPop(zl, &s, ZIPLIST_TAIL);
 141     printf("Pop tail: %s (length %ld)\n", s, sdslen(s));
 142     ziplistRepr(zl);
 143
 144     zl = ziplistPop(zl, &s, ZIPLIST_HEAD);
 145     printf("Pop head: %s (length %ld)\n", s, sdslen(s));
 146     ziplistRepr(zl);
 147
 148     return 0;
 149 }
 150 #endif