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     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     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 **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         if (ZIPLIST_LENGTH(zl) < ZIP_BIGLEN) ZIPLIST_LENGTH(zl) -= deleted;
 151     }
 152     return zl;
 153 }
 154
 155 void ziplistRepr(unsigned char *zl) {
 156     unsigned char *p;
 157     unsigned int l;
 158
 159     printf("{bytes %d} {length %u}\n",ZIPLIST_BYTES(zl), ZIPLIST_LENGTH(zl));
 160     p = ziplistHead(zl);
 161     while(*p != ZIP_END) {
 162         l = zipDecodeLength(p);
 163         printf("{key %u}",l);
 164         p += zipEncodeLength(NULL,l);
 165         fwrite(p,l,1,stdout);
 166         printf("\n");
 167         p += l;
 168     }
 169     printf("{end}\n\n");
 170 }
 171
 172 #ifdef ZIPLIST_TEST_MAIN
 173
 174 unsigned char *createList() {
 175     unsigned char *zl = ziplistNew();
 176     zl = ziplistPush(zl, (unsigned char*)"foo", 3, ZIPLIST_TAIL);
 177     zl = ziplistPush(zl, (unsigned char*)"quux", 4, ZIPLIST_TAIL);
 178     zl = ziplistPush(zl, (unsigned char*)"hello", 5, ZIPLIST_HEAD);
 179     return zl;
 180 }
 181
 182 int main(int argc, char **argv) {
 183     unsigned char *zl, *p, *entry;
 184     unsigned int elen;
 185     sds s;
 186
 187     zl = createList();
 188     ziplistRepr(zl);
 189
 190     zl = ziplistPop(zl, &s, ZIPLIST_TAIL);
 191     printf("Pop tail: %s (length %ld)\n", s, sdslen(s));
 192     ziplistRepr(zl);
 193
 194     zl = ziplistPop(zl, &s, ZIPLIST_HEAD);
 195     printf("Pop head: %s (length %ld)\n", s, sdslen(s));
 196     ziplistRepr(zl);
 197
 198     printf("Iterate list from 0 to end:\n");
 199     {
 200         zl = createList();
 201         p = ziplistIndex(zl, 0);
 202         while ((p = ziplistNext(p, NULL, &entry, &elen)) != NULL) {
 203             printf("Entry: ");
 204             fwrite(entry,elen,1,stdout);
 205             printf(" (length %d)\n", elen);
 206         }
 207         printf("\n");
 208     }
 209
 210     printf("Iterate list from 1 to end:\n");
 211     {
 212         zl = createList();
 213         p = ziplistIndex(zl, 1);
 214         while ((p = ziplistNext(p, NULL, &entry, &elen)) != NULL) {
 215             printf("Entry: ");
 216             fwrite(entry,elen,1,stdout);
 217             printf(" (length %d)\n", elen);
 218         }
 219         printf("\n");
 220     }
 221
 222     printf("Iterate list from 2 to end:\n");
 223     {
 224         zl = createList();
 225         p = ziplistIndex(zl, 2);
 226         while ((p = ziplistNext(p, NULL, &entry, &elen)) != NULL) {
 227             printf("Entry: ");
 228             fwrite(entry,elen,1,stdout);
 229             printf(" (length %d)\n", elen);
 230         }
 231         printf("\n");
 232     }
 233
 234     printf("Iterate starting out of range:\n");
 235     {
 236         zl = createList();
 237         p = ziplistIndex(zl, 3);
 238         if (ziplistNext(p, &entry, NULL, &elen) == NULL) {
 239             printf("No entry\n");
 240         } else {
 241             printf("ERROR\n");
 242         }
 243         printf("\n");
 244     }
 245
 246     printf("Delete inclusive range 0,0:\n");
 247     {
 248         zl = createList();
 249         zl = ziplistDeleteRange(zl, 0, 1);
 250         ziplistRepr(zl);
 251     }
 252
 253     printf("Delete inclusive range 0,1:\n");
 254     {
 255         zl = createList();
 256         zl = ziplistDeleteRange(zl, 0, 2);
 257         ziplistRepr(zl);
 258     }
 259
 260     printf("Delete inclusive range 1,2:\n");
 261     {
 262         zl = createList();
 263         zl = ziplistDeleteRange(zl, 1, 2);
 264         ziplistRepr(zl);
 265     }
 266
 267     printf("Delete with start index out of range:\n");
 268     {
 269         zl = createList();
 270         zl = ziplistDeleteRange(zl, 5, 1);
 271         ziplistRepr(zl);
 272     }
 273
 274     printf("Delete with num overflow:\n");
 275     {
 276         zl = createList();
 277         zl = ziplistDeleteRange(zl, 1, 5);
 278         ziplistRepr(zl);
 279     }
 280
 281     return 0;
 282 }
 283 #endif