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, unsigned char **entry, unsigned int *elen) {
 124     if (*p == ZIP_END) return NULL;
 125     if (entry) {
 126         *elen = zipDecodeLength(p);
 127         *entry = p+ZIP_LEN_BYTES(*elen);
 128     }
 129     p += zipRawEntryLength(p);
 130     return p;
 131 }
 132
 133 void ziplistRepr(unsigned char *zl) {
 134     unsigned char *p;
 135     unsigned int l;
 136
 137     printf("{bytes %d} {length %u}\n",ZIPLIST_BYTES(zl), ZIPLIST_LENGTH(zl));
 138     p = ziplistHead(zl);
 139     while(*p != ZIP_END) {
 140         l = zipDecodeLength(p);
 141         printf("{key %u}",l);
 142         p += zipEncodeLength(NULL,l);
 143         fwrite(p,l,1,stdout);
 144         printf("\n");
 145         p += l;
 146     }
 147     printf("{end}\n\n");
 148 }
 149
 150 #ifdef ZIPLIST_TEST_MAIN
 151
 152 unsigned char *createList() {
 153     unsigned char *zl = ziplistNew();
 154     zl = ziplistPush(zl, (unsigned char*)"foo", 3, ZIPLIST_TAIL);
 155     zl = ziplistPush(zl, (unsigned char*)"quux", 4, ZIPLIST_TAIL);
 156     zl = ziplistPush(zl, (unsigned char*)"hello", 5, ZIPLIST_HEAD);
 157     return zl;
 158 }
 159
 160 int main(int argc, char **argv) {
 161     unsigned char *zl, *p, *entry;
 162     unsigned int elen;
 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, &entry, &elen)) != NULL) {
 181             printf("Entry: ");
 182             fwrite(entry,elen,1,stdout);
 183             printf(" (length %d)\n", elen);
 184         }
 185         printf("\n");
 186     }
 187
 188     printf("Iterate list from 1 to end:\n");
 189     {
 190         zl = createList();
 191         p = ziplistIndex(zl, 1);
 192         while ((p = ziplistNext(p, &entry, &elen)) != NULL) {
 193             printf("Entry: ");
 194             fwrite(entry,elen,1,stdout);
 195             printf(" (length %d)\n", elen);
 196         }
 197         printf("\n");
 198     }
 199
 200     printf("Iterate list from 2 to end:\n");
 201     {
 202         zl = createList();
 203         p = ziplistIndex(zl, 2);
 204         while ((p = ziplistNext(p, &entry, &elen)) != NULL) {
 205             printf("Entry: ");
 206             fwrite(entry,elen,1,stdout);
 207             printf(" (length %d)\n", elen);
 208         }
 209         printf("\n");
 210     }
 211
 212     printf("Iterate starting out of range:\n");
 213     {
 214         zl = createList();
 215         p = ziplistIndex(zl, 3);
 216         if (ziplistNext(p, &entry, &elen) == NULL) {
 217             printf("No entry\n");
 218         } else {
 219             printf("ERROR\n");
 220         }
 221     }
 222
 223     return 0;
 224 }
 225 #endif