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 <stdlib.h>
  19 #include <string.h>
  20 #include <assert.h>
  21 #include <limits.h>
  22 #include "zmalloc.h"
  23 #include "sds.h"
  24 #include "ziplist.h"
  25
  26 #define ZIP_END 255
  27
  28 /* Entry encoding */
  29 #define ZIP_ENC_RAW     0
  30 #define ZIP_ENC_SHORT   1
  31 #define ZIP_ENC_INT     2
  32 #define ZIP_ENC_LLONG   3
  33 #define ZIP_ENCODING(p) ((p)[0] >> 6)
  34
  35 /* Length encoding for raw entries */
  36 #define ZIP_LEN_INLINE  0
  37 #define ZIP_LEN_UINT16  1
  38 #define ZIP_LEN_UINT32  2
  39
  40 /* Utility macros */
  41 #define ZIPLIST_BYTES(zl) (*((unsigned int*)(zl)))
  42 #define ZIPLIST_LENGTH(zl) (*((zl)+sizeof(unsigned int)))
  43 #define ZIPLIST_HEADER_SIZE (sizeof(unsigned int)+1)
  44 #define ZIPLIST_INCR_LENGTH(zl,incr) { \
  45     if (ZIPLIST_LENGTH(zl) < (ZIP_END-1)) ZIPLIST_LENGTH(zl)+=incr; }
  46
  47 /* Return bytes needed to store integer encoded by 'encoding' */
  48 static unsigned int zipEncodingSize(char encoding) {
  49     if (encoding == ZIP_ENC_SHORT) {
  50         return sizeof(short int);
  51     } else if (encoding == ZIP_ENC_INT) {
  52         return sizeof(int);
  53     } else if (encoding == ZIP_ENC_LLONG) {
  54         return sizeof(long long);
  55     }
  56     assert(NULL);
  57 }
  58
  59 /* Decode the encoded length pointed by 'p'. If a pointer to 'lensize' is
  60  * provided, it is set to the number of bytes required to encode the length. */
  61 static unsigned int zipDecodeLength(unsigned char *p, unsigned int *lensize) {
  62     unsigned char encoding = ZIP_ENCODING(p), lenenc;
  63     unsigned int len;
  64
  65     if (encoding == ZIP_ENC_RAW) {
  66         lenenc = (p[0] >> 4) & 0x3;
  67         if (lenenc == ZIP_LEN_INLINE) {
  68             len = p[0] & 0xf;
  69             if (lensize) *lensize = 1;
  70         } else if (lenenc == ZIP_LEN_UINT16) {
  71             len = p[1] | (p[2] << 8);
  72             if (lensize) *lensize = 3;
  73         } else {
  74             len = p[1] | (p[2] << 8) | (p[3] << 16) | (p[4] << 24);
  75             if (lensize) *lensize = 5;
  76         }
  77     } else {
  78         len = zipEncodingSize(encoding);
  79         if (lensize) *lensize = 1;
  80     }
  81     return len;
  82 }
  83
  84 /* Encode the length 'l' writing it in 'p'. If p is NULL it just returns
  85  * the amount of bytes required to encode such a length. */
  86 static unsigned int zipEncodeLength(unsigned char *p, char encoding, unsigned int rawlen) {
  87     unsigned char len = 1, lenenc, buf[5];
  88     if (encoding == ZIP_ENC_RAW) {
  89         if (rawlen <= 0xf) {
  90             if (!p) return len;
  91             lenenc = ZIP_LEN_INLINE;
  92             buf[0] = rawlen;
  93         } else if (rawlen <= 0xffff) {
  94             len += 2;
  95             if (!p) return len;
  96             lenenc = ZIP_LEN_UINT16;
  97             buf[1] = (rawlen     ) & 0xff;
  98             buf[2] = (rawlen >> 8) & 0xff;
  99         } else {
 100             len += 4;
 101             if (!p) return len;
 102             lenenc = ZIP_LEN_UINT32;
 103             buf[1] = (rawlen      ) & 0xff;
 104             buf[2] = (rawlen >>  8) & 0xff;
 105             buf[3] = (rawlen >> 16) & 0xff;
 106             buf[4] = (rawlen >> 24) & 0xff;
 107         }
 108         buf[0] = (lenenc << 4) | (buf[0] & 0xf);
 109     }
 110     if (!p) return len;
 111
 112     /* Apparently we need to store the length in 'p' */
 113     buf[0] = (encoding << 6) | (buf[0] & 0x3f);
 114     memcpy(p,buf,len);
 115     return len;
 116 }
 117
 118 /* Check if string pointed to by 'entry' can be encoded as an integer.
 119  * Stores the integer value in 'v' and its encoding in 'encoding'.
 120  * Warning: this function requires a NULL-terminated string! */
 121 static int zipTryEncoding(unsigned char *entry, long long *v, char *encoding) {
 122     long long value;
 123     char *eptr;
 124
 125     if (entry[0] == '-' || (entry[0] >= '0' && entry[0] <= '9')) {
 126         value = strtoll(entry,&eptr,10);
 127         if (eptr[0] != '\0') return 0;
 128         if (value >= SHRT_MIN && value <= SHRT_MAX) {
 129             *encoding = ZIP_ENC_SHORT;
 130         } else if (value >= INT_MIN && value <= INT_MAX) {
 131             *encoding = ZIP_ENC_INT;
 132         } else {
 133             *encoding = ZIP_ENC_LLONG;
 134         }
 135         *v = value;
 136         return 1;
 137     }
 138     return 0;
 139 }
 140
 141 /* Store integer 'value' at 'p', encoded as 'encoding' */
 142 static void zipSaveInteger(unsigned char *p, long long value, char encoding) {
 143     short int s;
 144     int i;
 145     long long l;
 146     if (encoding == ZIP_ENC_SHORT) {
 147         s = value;
 148         memcpy(p,&s,sizeof(s));
 149     } else if (encoding == ZIP_ENC_INT) {
 150         i = value;
 151         memcpy(p,&i,sizeof(i));
 152     } else if (encoding == ZIP_ENC_LLONG) {
 153         l = value;
 154         memcpy(p,&l,sizeof(l));
 155     } else {
 156         assert(NULL);
 157     }
 158 }
 159
 160 /* Read integer encoded as 'encoding' from 'p' */
 161 static long long zipLoadInteger(unsigned char *p, char encoding) {
 162     short int s;
 163     int i;
 164     long long l, ret;
 165     if (encoding == ZIP_ENC_SHORT) {
 166         memcpy(&s,p,sizeof(s));
 167         ret = s;
 168     } else if (encoding == ZIP_ENC_INT) {
 169         memcpy(&i,p,sizeof(i));
 170         ret = i;
 171     } else if (encoding == ZIP_ENC_LLONG) {
 172         memcpy(&l,p,sizeof(l));
 173         ret = l;
 174     } else {
 175         assert(NULL);
 176     }
 177     return ret;
 178 }
 179
 180 /* Return the total amount used by an entry (encoded length + payload). */
 181 static unsigned int zipRawEntryLength(unsigned char *p) {
 182     unsigned int lensize, len;
 183     len = zipDecodeLength(p, &lensize);
 184     return lensize + len;
 185 }
 186
 187 /* Create a new empty ziplist. */
 188 unsigned char *ziplistNew(void) {
 189     unsigned int bytes = ZIPLIST_HEADER_SIZE+1;
 190     unsigned char *zl = zmalloc(bytes);
 191     ZIPLIST_BYTES(zl) = bytes;
 192     ZIPLIST_LENGTH(zl) = 0;
 193     zl[bytes-1] = ZIP_END;
 194     return zl;
 195 }
 196
 197 /* Resize the ziplist. */
 198 static unsigned char *ziplistResize(unsigned char *zl, unsigned int len) {
 199     zl = zrealloc(zl,len);
 200     ZIPLIST_BYTES(zl) = len;
 201     zl[len-1] = ZIP_END;
 202     return zl;
 203 }
 204
 205 static unsigned char *ziplistHead(unsigned char *zl) {
 206     return zl+ZIPLIST_HEADER_SIZE;
 207 }
 208
 209 static unsigned char *ziplistTail(unsigned char *zl) {
 210     unsigned char *p, *q;
 211     p = q = ziplistHead(zl);
 212     while (*p != ZIP_END) {
 213         q = p;
 214         p += zipRawEntryLength(p);
 215     }
 216     return q;
 217 }
 218
 219 unsigned char *ziplistPush(unsigned char *zl, unsigned char *entry, unsigned int elen, int where) {
 220     unsigned int curlen = ZIPLIST_BYTES(zl), reqlen;
 221     unsigned char *p;
 222     char encoding = ZIP_ENC_RAW;
 223     long long value;
 224
 225     /* See if the entry can be encoded */
 226     if (zipTryEncoding(entry,&value,&encoding)) {
 227         reqlen = zipEncodingSize(encoding);
 228     } else {
 229         reqlen = elen;
 230     }
 231     reqlen += zipEncodeLength(NULL,encoding,elen);
 232
 233     /* Resize the ziplist and move if needed */
 234     zl = ziplistResize(zl,curlen+reqlen);
 235     if (where == ZIPLIST_HEAD) {
 236         p = zl+ZIPLIST_HEADER_SIZE;
 237         if (*p != ZIP_END) {
 238             /* Subtract one because of the ZIP_END bytes */
 239             memmove(p+reqlen,p,curlen-ZIPLIST_HEADER_SIZE-1);
 240         }
 241     } else {
 242         p = zl+curlen-1;
 243     }
 244
 245     /* Write the entry */
 246     p += zipEncodeLength(p,encoding,elen);
 247     if (encoding != ZIP_ENC_RAW) {
 248         zipSaveInteger(p,value,encoding);
 249     } else {
 250         memcpy(p,entry,elen);
 251     }
 252     ZIPLIST_INCR_LENGTH(zl,1);
 253     return zl;
 254 }
 255
 256 unsigned char *ziplistPop(unsigned char *zl, sds *target, int where) {
 257     unsigned int curlen = ZIPLIST_BYTES(zl), rawlen;
 258     unsigned int len, lensize;
 259     unsigned char *p;
 260     long long value;
 261     if (target) *target = NULL;
 262
 263     /* Get pointer to element to remove */
 264     p = (where == ZIPLIST_HEAD) ? ziplistHead(zl) : ziplistTail(zl);
 265     if (*p == ZIP_END) return zl;
 266     len = zipDecodeLength(p,&lensize);
 267     if (target) {
 268         if (ZIP_ENCODING(p) == ZIP_ENC_RAW) {
 269             *target = sdsnewlen(p+lensize,len);
 270         } else {
 271             value = zipLoadInteger(p+lensize,ZIP_ENCODING(p));
 272             *target = sdscatprintf(sdsempty(), "%lld", value);
 273         }
 274     }
 275
 276     /* Move list to front when popping from the head */
 277     rawlen = lensize+len;
 278     if (where == ZIPLIST_HEAD) {
 279         memmove(p,p+rawlen,curlen-ZIPLIST_HEADER_SIZE-len);
 280     }
 281
 282     /* Resize and update length */
 283     zl = ziplistResize(zl,curlen-rawlen);
 284     ZIPLIST_INCR_LENGTH(zl,-1);
 285     return zl;
 286 }
 287
 288 /* Returns an offset to use for iterating with ziplistNext. */
 289 unsigned char *ziplistIndex(unsigned char *zl, unsigned int index) {
 290     unsigned char *p = zl+ZIPLIST_HEADER_SIZE;
 291     unsigned int i = 0;
 292     for (; i < index; i++) {
 293         if (*p == ZIP_END) break;
 294         p += zipRawEntryLength(p);
 295     }
 296     return p;
 297 }
 298
 299 /* Store entry at current position in sds *value and return pointer
 300  * to the next entry. */
 301 unsigned char *ziplistNext(unsigned char *p, unsigned char **q, unsigned char **entry, unsigned int *elen) {
 302     unsigned int lensize;
 303     if (*p == ZIP_END) return NULL;
 304     if (entry) {
 305         *elen = zipDecodeLength(p,&lensize);
 306         *entry = p+lensize;
 307     }
 308     if (q != NULL) *q = p;
 309     p += zipRawEntryLength(p);
 310     return p;
 311 }
 312
 313 /* Delete a range of entries from the ziplist. */
 314 unsigned char *ziplistDeleteRange(unsigned char *zl, unsigned int index, unsigned int num) {
 315     unsigned char *p, *first = ziplistIndex(zl, index);
 316     unsigned int i, deleted = 0, totlen, newlen;
 317     for (p = first, i = 0; *p != ZIP_END && i < num; i++) {
 318         p += zipRawEntryLength(p);
 319         deleted++;
 320     }
 321
 322     totlen = p-first;
 323     if (totlen > 0) {
 324         /* Move current tail to the new tail when there *is* a tail */
 325         if (*p != ZIP_END) memmove(first,p,ZIPLIST_BYTES(zl)-(p-zl)-1);
 326
 327         /* Resize and update length */
 328         zl = ziplistResize(zl, ZIPLIST_BYTES(zl)-totlen);
 329         ZIPLIST_INCR_LENGTH(zl,-deleted);
 330     }
 331     return zl;
 332 }
 333
 334 /* Delete a single entry from the ziplist, pointed to by *p.
 335  * Also update *p in place, to be able to iterate over the
 336  * ziplist, while deleting entries. */
 337 unsigned char *ziplistDelete(unsigned char *zl, unsigned char **p) {
 338     unsigned int offset = *p-zl, tail, len;
 339     len = zipRawEntryLength(*p);
 340     tail = ZIPLIST_BYTES(zl)-offset-len-1;
 341
 342     /* Move current tail to the new tail when there *is* a tail */
 343     if (tail > 0) memmove(*p,*p+len,tail);
 344
 345     /* Resize and update length */
 346     zl = ziplistResize(zl, ZIPLIST_BYTES(zl)-len);
 347     ZIPLIST_INCR_LENGTH(zl,-1);
 348
 349     /* Store new pointer to current element in p.
 350      * This needs to be done because zl can change on realloc. */
 351     *p = zl+offset;
 352     return zl;
 353 }
 354
 355 void ziplistRepr(unsigned char *zl) {
 356     unsigned char *p, encoding;
 357     unsigned int l, lsize;
 358     long long value;
 359
 360     printf("{total bytes %d} {length %u}\n",ZIPLIST_BYTES(zl), ZIPLIST_LENGTH(zl));
 361     p = ziplistHead(zl);
 362     while(*p != ZIP_END) {
 363         l = zipDecodeLength(p,&lsize);
 364         printf("{header %u, payload %u} ",lsize,l);
 365         encoding = ZIP_ENCODING(p);
 366         p += lsize;
 367         if (encoding == ZIP_ENC_RAW) {
 368             fwrite(p,l,1,stdout);
 369         } else {
 370             printf("%lld", zipLoadInteger(p,encoding));
 371         }
 372         printf("\n");
 373         p += l;
 374     }
 375     printf("{end}\n\n");
 376 }
 377
 378 #ifdef ZIPLIST_TEST_MAIN
 379
 380 unsigned char *createList() {
 381     unsigned char *zl = ziplistNew();
 382     zl = ziplistPush(zl, (unsigned char*)"foo", 3, ZIPLIST_TAIL);
 383     zl = ziplistPush(zl, (unsigned char*)"quux", 4, ZIPLIST_TAIL);
 384     zl = ziplistPush(zl, (unsigned char*)"hello", 5, ZIPLIST_HEAD);
 385     return zl;
 386 }
 387
 388 unsigned char *createIntList() {
 389     unsigned char *zl = ziplistNew();
 390     char buf[32];
 391
 392     sprintf(buf, "100");
 393     zl = ziplistPush(zl, buf, strlen(buf), ZIPLIST_TAIL);
 394     sprintf(buf, "128000");
 395     zl = ziplistPush(zl, buf, strlen(buf), ZIPLIST_TAIL);
 396     sprintf(buf, "-100");
 397     zl = ziplistPush(zl, buf, strlen(buf), ZIPLIST_HEAD);
 398     sprintf(buf, "4294967296");
 399     zl = ziplistPush(zl, buf, strlen(buf), ZIPLIST_HEAD);
 400     sprintf(buf, "non integer");
 401     zl = ziplistPush(zl, buf, strlen(buf), ZIPLIST_TAIL);
 402     sprintf(buf, "much much longer non integer");
 403     zl = ziplistPush(zl, buf, strlen(buf), ZIPLIST_TAIL);
 404     return zl;
 405 }
 406
 407 int main(int argc, char **argv) {
 408     unsigned char *zl, *p, *q, *entry;
 409     unsigned int elen;
 410     sds s;
 411
 412     zl = createIntList();
 413     ziplistRepr(zl);
 414
 415     zl = createList();
 416     ziplistRepr(zl);
 417
 418     zl = ziplistPop(zl, &s, ZIPLIST_TAIL);
 419     printf("Pop tail: %s (length %ld)\n", s, sdslen(s));
 420     ziplistRepr(zl);
 421
 422     zl = ziplistPop(zl, &s, ZIPLIST_HEAD);
 423     printf("Pop head: %s (length %ld)\n", s, sdslen(s));
 424     ziplistRepr(zl);
 425
 426     printf("Iterate list from 0 to end:\n");
 427     {
 428         zl = createList();
 429         p = ziplistIndex(zl, 0);
 430         while ((p = ziplistNext(p, NULL, &entry, &elen)) != NULL) {
 431             printf("Entry: ");
 432             fwrite(entry,elen,1,stdout);
 433             printf(" (length %d)\n", elen);
 434         }
 435         printf("\n");
 436     }
 437
 438     printf("Iterate list from 1 to end:\n");
 439     {
 440         zl = createList();
 441         p = ziplistIndex(zl, 1);
 442         while ((p = ziplistNext(p, NULL, &entry, &elen)) != NULL) {
 443             printf("Entry: ");
 444             fwrite(entry,elen,1,stdout);
 445             printf(" (length %d)\n", elen);
 446         }
 447         printf("\n");
 448     }
 449
 450     printf("Iterate list from 2 to end:\n");
 451     {
 452         zl = createList();
 453         p = ziplistIndex(zl, 2);
 454         while ((p = ziplistNext(p, NULL, &entry, &elen)) != NULL) {
 455             printf("Entry: ");
 456             fwrite(entry,elen,1,stdout);
 457             printf(" (length %d)\n", elen);
 458         }
 459         printf("\n");
 460     }
 461
 462     printf("Iterate starting out of range:\n");
 463     {
 464         zl = createList();
 465         p = ziplistIndex(zl, 3);
 466         if (ziplistNext(p, &entry, NULL, &elen) == NULL) {
 467             printf("No entry\n");
 468         } else {
 469             printf("ERROR\n");
 470         }
 471         printf("\n");
 472     }
 473
 474     printf("Delete inclusive range 0,0:\n");
 475     {
 476         zl = createList();
 477         zl = ziplistDeleteRange(zl, 0, 1);
 478         ziplistRepr(zl);
 479     }
 480
 481     printf("Delete inclusive range 0,1:\n");
 482     {
 483         zl = createList();
 484         zl = ziplistDeleteRange(zl, 0, 2);
 485         ziplistRepr(zl);
 486     }
 487
 488     printf("Delete inclusive range 1,2:\n");
 489     {
 490         zl = createList();
 491         zl = ziplistDeleteRange(zl, 1, 2);
 492         ziplistRepr(zl);
 493     }
 494
 495     printf("Delete with start index out of range:\n");
 496     {
 497         zl = createList();
 498         zl = ziplistDeleteRange(zl, 5, 1);
 499         ziplistRepr(zl);
 500     }
 501
 502     printf("Delete with num overflow:\n");
 503     {
 504         zl = createList();
 505         zl = ziplistDeleteRange(zl, 1, 5);
 506         ziplistRepr(zl);
 507     }
 508
 509     printf("Delete foo while iterating:\n");
 510     {
 511         zl = createList();
 512         p = ziplistIndex(zl, 0);
 513         while ((p = ziplistNext(p, &q, &entry, &elen)) != NULL) {
 514             if (strncmp("foo", entry, elen) == 0) {
 515                 printf("Delete foo\n");
 516                 zl = ziplistDelete(zl, &q);
 517                 p = q;
 518             } else {
 519                 printf("Entry: ");
 520                 fwrite(entry,elen,1,stdout);
 521                 printf(" (length %d)\n", elen);
 522             }
 523         }
 524         printf("\n");
 525         ziplistRepr(zl);
 526         printf("\n");
 527     }
 528
 529     return 0;
 530 }
 531 #endif