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