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 /* Return pointer to next entry in ziplist. */
 300 unsigned char *ziplistNext(unsigned char *p) {
 301     return *p == ZIP_END ? p : p+zipRawEntryLength(p);
 302 }
 303
 304 /* Get entry pointer to by 'p' and store in either 'e' or 'v' depending
 305  * on the encoding of the entry. 'e' is always set to NULL to be able
 306  * to find out whether the string pointer or the integer value was set.
 307  * Return 0 if 'p' points to the end of the zipmap, 1 otherwise. */
 308 unsigned int ziplistGet(unsigned char *p, unsigned char **e, unsigned int *elen, long long *v) {
 309     unsigned int len, lensize;
 310     if (*p == ZIP_END) return 0;
 311     if (e) *e = NULL;
 312     len = zipDecodeLength(p,&lensize);
 313     if (ZIP_ENCODING(p) == ZIP_ENC_RAW) {
 314         if (e) {
 315             *elen = len;
 316             *e = p+lensize;
 317         }
 318     } else {
 319         if (v) {
 320             *v = zipLoadInteger(p+lensize,ZIP_ENCODING(p));
 321         }
 322     }
 323     return 1;
 324 }
 325
 326 /* Delete a range of entries from the ziplist. */
 327 unsigned char *ziplistDeleteRange(unsigned char *zl, unsigned int index, unsigned int num) {
 328     unsigned char *p, *first = ziplistIndex(zl, index);
 329     unsigned int i, deleted = 0, totlen, newlen;
 330     for (p = first, i = 0; *p != ZIP_END && i < num; i++) {
 331         p += zipRawEntryLength(p);
 332         deleted++;
 333     }
 334
 335     totlen = p-first;
 336     if (totlen > 0) {
 337         /* Move current tail to the new tail when there *is* a tail */
 338         if (*p != ZIP_END) memmove(first,p,ZIPLIST_BYTES(zl)-(p-zl)-1);
 339
 340         /* Resize and update length */
 341         zl = ziplistResize(zl, ZIPLIST_BYTES(zl)-totlen);
 342         ZIPLIST_INCR_LENGTH(zl,-deleted);
 343     }
 344     return zl;
 345 }
 346
 347 /* Delete a single entry from the ziplist, pointed to by *p.
 348  * Also update *p in place, to be able to iterate over the
 349  * ziplist, while deleting entries. */
 350 unsigned char *ziplistDelete(unsigned char *zl, unsigned char **p) {
 351     unsigned int offset = *p-zl, tail, len;
 352     len = zipRawEntryLength(*p);
 353     tail = ZIPLIST_BYTES(zl)-offset-len-1;
 354
 355     /* Move current tail to the new tail when there *is* a tail */
 356     if (tail > 0) memmove(*p,*p+len,tail);
 357
 358     /* Resize and update length */
 359     zl = ziplistResize(zl, ZIPLIST_BYTES(zl)-len);
 360     ZIPLIST_INCR_LENGTH(zl,-1);
 361
 362     /* Store new pointer to current element in p.
 363      * This needs to be done because zl can change on realloc. */
 364     *p = zl+offset;
 365     return zl;
 366 }
 367
 368 void ziplistRepr(unsigned char *zl) {
 369     unsigned char *p, encoding;
 370     unsigned int l, lsize;
 371     long long value;
 372
 373     printf("{total bytes %d} {length %u}\n",ZIPLIST_BYTES(zl), ZIPLIST_LENGTH(zl));
 374     p = ziplistHead(zl);
 375     while(*p != ZIP_END) {
 376         l = zipDecodeLength(p,&lsize);
 377         printf("{header %u, payload %u} ",lsize,l);
 378         encoding = ZIP_ENCODING(p);
 379         p += lsize;
 380         if (encoding == ZIP_ENC_RAW) {
 381             fwrite(p,l,1,stdout);
 382         } else {
 383             printf("%lld", zipLoadInteger(p,encoding));
 384         }
 385         printf("\n");
 386         p += l;
 387     }
 388     printf("{end}\n\n");
 389 }
 390
 391 #ifdef ZIPLIST_TEST_MAIN
 392
 393 unsigned char *createList() {
 394     unsigned char *zl = ziplistNew();
 395     zl = ziplistPush(zl, (unsigned char*)"foo", 3, ZIPLIST_TAIL);
 396     zl = ziplistPush(zl, (unsigned char*)"quux", 4, ZIPLIST_TAIL);
 397     zl = ziplistPush(zl, (unsigned char*)"hello", 5, ZIPLIST_HEAD);
 398     zl = ziplistPush(zl, (unsigned char*)"1024", 4, ZIPLIST_TAIL);
 399     return zl;
 400 }
 401
 402 unsigned char *createIntList() {
 403     unsigned char *zl = ziplistNew();
 404     char buf[32];
 405
 406     sprintf(buf, "100");
 407     zl = ziplistPush(zl, buf, strlen(buf), ZIPLIST_TAIL);
 408     sprintf(buf, "128000");
 409     zl = ziplistPush(zl, buf, strlen(buf), ZIPLIST_TAIL);
 410     sprintf(buf, "-100");
 411     zl = ziplistPush(zl, buf, strlen(buf), ZIPLIST_HEAD);
 412     sprintf(buf, "4294967296");
 413     zl = ziplistPush(zl, buf, strlen(buf), ZIPLIST_HEAD);
 414     sprintf(buf, "non integer");
 415     zl = ziplistPush(zl, buf, strlen(buf), ZIPLIST_TAIL);
 416     sprintf(buf, "much much longer non integer");
 417     zl = ziplistPush(zl, buf, strlen(buf), ZIPLIST_TAIL);
 418     return zl;
 419 }
 420
 421 int main(int argc, char **argv) {
 422     unsigned char *zl, *p, *q, *entry;
 423     unsigned int elen;
 424     long long value;
 425     sds s;
 426
 427     zl = createIntList();
 428     ziplistRepr(zl);
 429
 430     zl = createList();
 431     ziplistRepr(zl);
 432
 433     zl = ziplistPop(zl, &s, ZIPLIST_TAIL);
 434     printf("Pop tail: %s (length %ld)\n", s, sdslen(s));
 435     ziplistRepr(zl);
 436
 437     zl = ziplistPop(zl, &s, ZIPLIST_HEAD);
 438     printf("Pop head: %s (length %ld)\n", s, sdslen(s));
 439     ziplistRepr(zl);
 440
 441     printf("Iterate list from 0 to end:\n");
 442     {
 443         zl = createList();
 444         p = ziplistIndex(zl, 0);
 445         while (ziplistGet(p, &entry, &elen, &value)) {
 446             printf("Entry: ");
 447             if (entry) {
 448                 fwrite(entry,elen,1,stdout);
 449             } else {
 450                 printf("%lld", value);
 451             }
 452             p = ziplistNext(p);
 453             printf("\n");
 454         }
 455         printf("\n");
 456     }
 457
 458     printf("Iterate list from 1 to end:\n");
 459     {
 460         zl = createList();
 461         p = ziplistIndex(zl, 1);
 462         while (ziplistGet(p, &entry, &elen, &value)) {
 463             printf("Entry: ");
 464             if (entry) {
 465                 fwrite(entry,elen,1,stdout);
 466             } else {
 467                 printf("%lld", value);
 468             }
 469             p = ziplistNext(p);
 470             printf("\n");
 471         }
 472         printf("\n");
 473     }
 474
 475     printf("Iterate list from 2 to end:\n");
 476     {
 477         zl = createList();
 478         p = ziplistIndex(zl, 2);
 479         while (ziplistGet(p, &entry, &elen, &value)) {
 480             printf("Entry: ");
 481             if (entry) {
 482                 fwrite(entry,elen,1,stdout);
 483             } else {
 484                 printf("%lld", value);
 485             }
 486             p = ziplistNext(p);
 487             printf("\n");
 488         }
 489         printf("\n");
 490     }
 491
 492     printf("Iterate starting out of range:\n");
 493     {
 494         zl = createList();
 495         p = ziplistIndex(zl, 4);
 496         if (!ziplistGet(p, &entry, &elen, &value)) {
 497             printf("No entry\n");
 498         } else {
 499             printf("ERROR\n");
 500         }
 501         printf("\n");
 502     }
 503
 504     printf("Delete inclusive range 0,0:\n");
 505     {
 506         zl = createList();
 507         zl = ziplistDeleteRange(zl, 0, 1);
 508         ziplistRepr(zl);
 509     }
 510
 511     printf("Delete inclusive range 0,1:\n");
 512     {
 513         zl = createList();
 514         zl = ziplistDeleteRange(zl, 0, 2);
 515         ziplistRepr(zl);
 516     }
 517
 518     printf("Delete inclusive range 1,2:\n");
 519     {
 520         zl = createList();
 521         zl = ziplistDeleteRange(zl, 1, 2);
 522         ziplistRepr(zl);
 523     }
 524
 525     printf("Delete with start index out of range:\n");
 526     {
 527         zl = createList();
 528         zl = ziplistDeleteRange(zl, 5, 1);
 529         ziplistRepr(zl);
 530     }
 531
 532     printf("Delete with num overflow:\n");
 533     {
 534         zl = createList();
 535         zl = ziplistDeleteRange(zl, 1, 5);
 536         ziplistRepr(zl);
 537     }
 538
 539     printf("Delete foo while iterating:\n");
 540     {
 541         zl = createList();
 542         p = ziplistIndex(zl, 0);
 543         while (ziplistGet(p, &entry, &elen, &value)) {
 544             if (entry && strncmp("foo", entry, elen) == 0) {
 545                 printf("Delete foo\n");
 546                 zl = ziplistDelete(zl, &p);
 547             } else {
 548                 printf("Entry: ");
 549                 if (entry) {
 550                     fwrite(entry,elen,1,stdout);
 551                 } else {
 552                     printf("%lld", value);
 553                 }
 554                 p = ziplistNext(p);
 555                 printf("\n");
 556             }
 557         }
 558         printf("\n");
 559         ziplistRepr(zl);
 560         printf("\n");
 561     }
 562
 563     return 0;
 564 }
 565 #endif