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 /* Returns an offset to use for iterating with ziplistNext. */
 111 unsigned char *ziplistIndex(unsigned char *zl, unsigned int index) {
 112     unsigned char *p = zl+ZIPLIST_HEADER_SIZE;
 113     unsigned int i = 0;
 114     for (; i < index; i++) {
 115         if (*p == ZIP_END) break;
 116         p += zipRawEntryLength(p);
 117     }
 118     return p;
 119 }
 120
 121 /* Store entry at current position in sds *value and return pointer
 122  * to the next entry. */
 123 unsigned char *ziplistNext(unsigned char *p, sds *value) {
 124     if (*p == ZIP_END) return NULL;
 125     if (value) {
 126         unsigned int len;
 127         len = zipDecodeLength(p);
 128         *value = sdsnewlen(p+zipEncodeLength(NULL,len),len);
 129     }
 130     p += zipRawEntryLength(p);
 131     return p;
 132 }
 133
 134 void ziplistRepr(unsigned char *zl) {
 135     unsigned char *p;
 136     unsigned int l;
 137
 138     printf("{bytes %d} {length %u}\n",ZIPLIST_BYTES(zl), ZIPLIST_LENGTH(zl));
 139     p = ziplistHead(zl);
 140     while(*p != ZIP_END) {
 141         l = zipDecodeLength(p);
 142         printf("{key %u}",l);
 143         p += zipEncodeLength(NULL,l);
 144         fwrite(p,l,1,stdout);
 145         printf("\n");
 146         p += l;
 147     }
 148     printf("{end}\n\n");
 149 }
 150
 151 #ifdef ZIPLIST_TEST_MAIN
 152
 153 unsigned char *createList() {
 154     unsigned char *zl = ziplistNew();
 155     zl = ziplistPush(zl, (unsigned char*)"foo", 3, ZIPLIST_TAIL);
 156     zl = ziplistPush(zl, (unsigned char*)"quux", 4, ZIPLIST_TAIL);
 157     zl = ziplistPush(zl, (unsigned char*)"hello", 5, ZIPLIST_HEAD);
 158     return zl;
 159 }
 160
 161 int main(int argc, char **argv) {
 162     unsigned char *zl, *p;
 163     sds s;
 164
 165     zl = createList();
 166     ziplistRepr(zl);
 167
 168     zl = ziplistPop(zl, &s, ZIPLIST_TAIL);
 169     printf("Pop tail: %s (length %ld)\n", s, sdslen(s));
 170     ziplistRepr(zl);
 171
 172     zl = ziplistPop(zl, &s, ZIPLIST_HEAD);
 173     printf("Pop head: %s (length %ld)\n", s, sdslen(s));
 174     ziplistRepr(zl);
 175
 176     printf("Iterate list from 0 to end:\n");
 177     {
 178         zl = createList();
 179         p = ziplistIndex(zl, 0);
 180         while ((p = ziplistNext(p, &s)) != NULL) {
 181             printf("Entry: %s (length %ld)\n", s, sdslen(s));
 182         }
 183         printf("\n");
 184     }
 185
 186     printf("Iterate list from 1 to end:\n");
 187     {
 188         zl = createList();
 189         p = ziplistIndex(zl, 1);
 190         while ((p = ziplistNext(p, &s)) != NULL) {
 191             printf("Entry: %s (length %ld)\n", s, sdslen(s));
 192         }
 193         printf("\n");
 194     }
 195
 196     printf("Iterate list from 2 to end:\n");
 197     {
 198         zl = createList();
 199         p = ziplistIndex(zl, 2);
 200         while ((p = ziplistNext(p, &s)) != NULL) {
 201             printf("Entry: %s (length %ld)\n", s, sdslen(s));
 202         }
 203         printf("\n");
 204     }
 205
 206     printf("Iterate starting out of range:\n");
 207     {
 208         zl = createList();
 209         p = ziplistIndex(zl, 3);
 210         if (ziplistNext(p, &s) == NULL) {
 211             printf("No entry\n");
 212         } else {
 213             printf("ERROR\n");
 214         }
 215     }
 216
 217     return 0;
 218 }
 219 #endif