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 #define ZIPLIST_INCR_LENGTH(zl,incr) { \
  29     if (ZIPLIST_LENGTH(zl) < (ZIP_END-1)) ZIPLIST_LENGTH(zl)+=incr; }
  30
  31 /* Create a new empty ziplist. */
  32 unsigned char *ziplistNew(void) {
  33     unsigned int bytes = ZIPLIST_HEADER_SIZE+1;
  34     unsigned char *zl = zmalloc(bytes);
  35     ZIPLIST_BYTES(zl) = bytes;
  36     ZIPLIST_LENGTH(zl) = 0;
  37     zl[bytes-1] = ZIP_END;
  38     return zl;
  39 }
  40
  41 static unsigned char *ziplistResize(unsigned char *zl, unsigned int len) {
  42     zl = zipResize(zl,len);
  43     ZIPLIST_BYTES(zl) = len;
  44     zl[len-1] = ZIP_END;
  45     return zl;
  46 }
  47
  48 static unsigned char *ziplistHead(unsigned char *zl) {
  49     return zl+ZIPLIST_HEADER_SIZE;
  50 }
  51
  52 static unsigned char *ziplistTail(unsigned char *zl) {
  53     unsigned char *p, *q;
  54     p = q = ziplistHead(zl);
  55     while (*p != ZIP_END) {
  56         q = p;
  57         p += zipRawEntryLength(p);
  58     }
  59     return q;
  60 }
  61
  62 unsigned char *ziplistPush(unsigned char *zl, unsigned char *entry, unsigned int elen, int where) {
  63     unsigned int curlen = ZIPLIST_BYTES(zl);
  64     unsigned int reqlen = zipEncodeLength(NULL,elen)+elen;
  65     unsigned char *p;
  66
  67     /* Resize the ziplist */
  68     zl = ziplistResize(zl,curlen+reqlen);
  69
  70     if (where == ZIPLIST_HEAD) {
  71         p = zl+ZIPLIST_HEADER_SIZE;
  72         if (*p != ZIP_END) {
  73             /* Subtract one because of the ZIP_END bytes */
  74             memmove(p+reqlen,p,curlen-ZIPLIST_HEADER_SIZE-1);
  75         }
  76     } else {
  77         p = zl+curlen-1;
  78     }
  79
  80     /* Write the entry */
  81     p += zipEncodeLength(p,elen);
  82     memcpy(p,entry,elen);
  83     ZIPLIST_INCR_LENGTH(zl,1);
  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     if (value) *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     if (value) *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     ZIPLIST_INCR_LENGTH(zl,-1);
 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 **q, 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     if (q != NULL) *q = p;
 130     p += zipRawEntryLength(p);
 131     return p;
 132 }
 133
 134 /* Delete a range of entries from the ziplist. */
 135 unsigned char *ziplistDeleteRange(unsigned char *zl, unsigned int index, unsigned int num) {
 136     unsigned char *p, *first = ziplistIndex(zl, index);
 137     unsigned int i, deleted = 0, totlen, newlen;
 138     for (p = first, i = 0; *p != ZIP_END && i < num; i++) {
 139         p += zipRawEntryLength(p);
 140         deleted++;
 141     }
 142
 143     totlen = p-first;
 144     if (totlen > 0) {
 145         /* Move current tail to the new tail when there *is* a tail */
 146         if (*p != ZIP_END) memmove(first,p,ZIPLIST_BYTES(zl)-(p-zl)-1);
 147
 148         /* Resize and update length */
 149         zl = ziplistResize(zl, ZIPLIST_BYTES(zl)-totlen);
 150         ZIPLIST_INCR_LENGTH(zl,-deleted);
 151     }
 152     return zl;
 153 }
 154
 155 /* Delete a single entry from the ziplist, pointed to by *p.
 156  * Also update *p in place, to be able to iterate over the
 157  * ziplist, while deleting entries. */
 158 unsigned char *ziplistDelete(unsigned char *zl, unsigned char **p) {
 159     unsigned int offset = *p-zl, tail, len;
 160     len = zipRawEntryLength(*p);
 161     tail = ZIPLIST_BYTES(zl)-offset-len-1;
 162
 163     /* Move current tail to the new tail when there *is* a tail */
 164     if (tail > 0) memmove(*p,*p+len,tail);
 165
 166     /* Resize and update length */
 167     zl = ziplistResize(zl, ZIPLIST_BYTES(zl)-len);
 168     ZIPLIST_INCR_LENGTH(zl,-1);
 169
 170     /* Store new pointer to current element in p.
 171      * This needs to be done because zl can change on realloc. */
 172     *p = zl+offset;
 173     return zl;
 174 }
 175
 176 void ziplistRepr(unsigned char *zl) {
 177     unsigned char *p;
 178     unsigned int l;
 179
 180     printf("{bytes %d} {length %u}\n",ZIPLIST_BYTES(zl), ZIPLIST_LENGTH(zl));
 181     p = ziplistHead(zl);
 182     while(*p != ZIP_END) {
 183         l = zipDecodeLength(p);
 184         printf("{key %u}",l);
 185         p += zipEncodeLength(NULL,l);
 186         fwrite(p,l,1,stdout);
 187         printf("\n");
 188         p += l;
 189     }
 190     printf("{end}\n\n");
 191 }
 192
 193 #ifdef ZIPLIST_TEST_MAIN
 194
 195 unsigned char *createList() {
 196     unsigned char *zl = ziplistNew();
 197     zl = ziplistPush(zl, (unsigned char*)"foo", 3, ZIPLIST_TAIL);
 198     zl = ziplistPush(zl, (unsigned char*)"quux", 4, ZIPLIST_TAIL);
 199     zl = ziplistPush(zl, (unsigned char*)"hello", 5, ZIPLIST_HEAD);
 200     return zl;
 201 }
 202
 203 int main(int argc, char **argv) {
 204     unsigned char *zl, *p, *q, *entry;
 205     unsigned int elen;
 206     sds s;
 207
 208     zl = createList();
 209     ziplistRepr(zl);
 210
 211     zl = ziplistPop(zl, &s, ZIPLIST_TAIL);
 212     printf("Pop tail: %s (length %ld)\n", s, sdslen(s));
 213     ziplistRepr(zl);
 214
 215     zl = ziplistPop(zl, &s, ZIPLIST_HEAD);
 216     printf("Pop head: %s (length %ld)\n", s, sdslen(s));
 217     ziplistRepr(zl);
 218
 219     printf("Iterate list from 0 to end:\n");
 220     {
 221         zl = createList();
 222         p = ziplistIndex(zl, 0);
 223         while ((p = ziplistNext(p, NULL, &entry, &elen)) != NULL) {
 224             printf("Entry: ");
 225             fwrite(entry,elen,1,stdout);
 226             printf(" (length %d)\n", elen);
 227         }
 228         printf("\n");
 229     }
 230
 231     printf("Iterate list from 1 to end:\n");
 232     {
 233         zl = createList();
 234         p = ziplistIndex(zl, 1);
 235         while ((p = ziplistNext(p, NULL, &entry, &elen)) != NULL) {
 236             printf("Entry: ");
 237             fwrite(entry,elen,1,stdout);
 238             printf(" (length %d)\n", elen);
 239         }
 240         printf("\n");
 241     }
 242
 243     printf("Iterate list from 2 to end:\n");
 244     {
 245         zl = createList();
 246         p = ziplistIndex(zl, 2);
 247         while ((p = ziplistNext(p, NULL, &entry, &elen)) != NULL) {
 248             printf("Entry: ");
 249             fwrite(entry,elen,1,stdout);
 250             printf(" (length %d)\n", elen);
 251         }
 252         printf("\n");
 253     }
 254
 255     printf("Iterate starting out of range:\n");
 256     {
 257         zl = createList();
 258         p = ziplistIndex(zl, 3);
 259         if (ziplistNext(p, &entry, NULL, &elen) == NULL) {
 260             printf("No entry\n");
 261         } else {
 262             printf("ERROR\n");
 263         }
 264         printf("\n");
 265     }
 266
 267     printf("Delete inclusive range 0,0:\n");
 268     {
 269         zl = createList();
 270         zl = ziplistDeleteRange(zl, 0, 1);
 271         ziplistRepr(zl);
 272     }
 273
 274     printf("Delete inclusive range 0,1:\n");
 275     {
 276         zl = createList();
 277         zl = ziplistDeleteRange(zl, 0, 2);
 278         ziplistRepr(zl);
 279     }
 280
 281     printf("Delete inclusive range 1,2:\n");
 282     {
 283         zl = createList();
 284         zl = ziplistDeleteRange(zl, 1, 2);
 285         ziplistRepr(zl);
 286     }
 287
 288     printf("Delete with start index out of range:\n");
 289     {
 290         zl = createList();
 291         zl = ziplistDeleteRange(zl, 5, 1);
 292         ziplistRepr(zl);
 293     }
 294
 295     printf("Delete with num overflow:\n");
 296     {
 297         zl = createList();
 298         zl = ziplistDeleteRange(zl, 1, 5);
 299         ziplistRepr(zl);
 300     }
 301
 302     printf("Delete foo while iterating:\n");
 303     {
 304         zl = createList();
 305         p = ziplistIndex(zl, 0);
 306         while ((p = ziplistNext(p, &q, &entry, &elen)) != NULL) {
 307             if (strncmp("foo", entry, elen) == 0) {
 308                 printf("Delete foo\n");
 309                 zl = ziplistDelete(zl, &q);
 310                 p = q;
 311             } else {
 312                 printf("Entry: ");
 313                 fwrite(entry,elen,1,stdout);
 314                 printf(" (length %d)\n", elen);
 315             }
 316         }
 317         printf("\n");
 318         ziplistRepr(zl);
 319         printf("\n");
 320     }
 321
 322     return 0;
 323 }
 324 #endif