1 /* The ziplist is a specially encoded dually linked list that is designed 2 * to be very memory efficient. It stores both strings and integer values, 3 * where integers are encoded as actual integers instead of a series of 4 * characters. It allows push and pop operations on either side of the list 5 * in O(1) time. However, because every operation requires a reallocation of 6 * the memory used by the ziplist, the actual complexity is related to the 7 * amount of memory used by the ziplist. 8 * 9 * ---------------------------------------------------------------------------- 10 * 11 * ZIPLIST OVERALL LAYOUT: 12 * The general layout of the ziplist is as follows: 13 * <zlbytes><zltail><zllen><entry><entry><zlend> 14 * 15 * <zlbytes> is an unsigned integer to hold the number of bytes that the 16 * ziplist occupies. This value needs to be stored to be able to resize the 17 * entire structure without the need to traverse it first. 18 * 19 * <zltail> is the offset to the last entry in the list. This allows a pop 20 * operation on the far side of the list without the need for full traversal. 21 * 22 * <zllen> is the number of entries.When this value is larger than 2**16-2, 23 * we need to traverse the entire list to know how many items it holds. 24 * 25 * <zlend> is a single byte special value, equal to 255, which indicates the 26 * end of the list. 27 * 28 * ZIPLIST ENTRIES: 29 * Every entry in the ziplist is prefixed by a header that contains two pieces 30 * of information. First, the length of the previous entry is stored to be 31 * able to traverse the list from back to front. Second, the encoding with an 32 * optional string length of the entry itself is stored. 33 * 34 * The length of the previous entry is encoded in the following way: 35 * If this length is smaller than 254 bytes, it will only consume a single 36 * byte that takes the length as value. When the length is greater than or 37 * equal to 254, it will consume 5 bytes. The first byte is set to 254 to 38 * indicate a larger value is following. The remaining 4 bytes take the 39 * length of the previous entry as value. 40 * 41 * The other header field of the entry itself depends on the contents of the 42 * entry. When the entry is a string, the first 2 bits of this header will hold 43 * the type of encoding used to store the length of the string, followed by the 44 * actual length of the string. When the entry is an integer the first 2 bits 45 * are both set to 1. The following 2 bits are used to specify what kind of 46 * integer will be stored after this header. An overview of the different 47 * types and encodings is as follows: 48 * 49 * |00pppppp| - 1 byte 50 * String value with length less than or equal to 63 bytes (6 bits). 51 * |01pppppp|qqqqqqqq| - 2 bytes 52 * String value with length less than or equal to 16383 bytes (14 bits). 53 * |10______|qqqqqqqq|rrrrrrrr|ssssssss|tttttttt| - 5 bytes 54 * String value with length greater than or equal to 16384 bytes. 55 * |1100____| - 1 byte 56 * Integer encoded as int16_t (2 bytes). 57 * |1101____| - 1 byte 58 * Integer encoded as int32_t (4 bytes). 59 * |1110____| - 1 byte 60 * Integer encoded as int64_t (8 bytes). 61 */ 62 63 #include <stdio.h> 64 #include <stdlib.h> 65 #include <string.h> 66 #include <stdint.h> 67 #include <assert.h> 68 #include <limits.h> 69 #include "zmalloc.h" 70 #include "util.h" 71 #include "ziplist.h" 72 #include "endianconv.h" 73 74 #define ZIP_END 255 75 #define ZIP_BIGLEN 254 76 77 /* Different encoding/length possibilities */ 78 #define ZIP_STR_MASK (0xc0) 79 #define ZIP_INT_MASK (0x30) 80 #define ZIP_STR_06B (0 << 6) 81 #define ZIP_STR_14B (1 << 6) 82 #define ZIP_STR_32B (2 << 6) 83 #define ZIP_INT_16B (0xc0 | 0<<4) 84 #define ZIP_INT_32B (0xc0 | 1<<4) 85 #define ZIP_INT_64B (0xc0 | 2<<4) 86 87 /* Macro to determine type */ 88 #define ZIP_IS_STR(enc) (((enc) & ZIP_STR_MASK) < ZIP_STR_MASK) 89 90 /* Utility macros */ 91 #define ZIPLIST_BYTES(zl) (*((uint32_t*)(zl))) 92 #define ZIPLIST_TAIL_OFFSET(zl) (*((uint32_t*)((zl)+sizeof(uint32_t)))) 93 #define ZIPLIST_LENGTH(zl) (*((uint16_t*)((zl)+sizeof(uint32_t)*2))) 94 #define ZIPLIST_HEADER_SIZE (sizeof(uint32_t)*2+sizeof(uint16_t)) 95 #define ZIPLIST_ENTRY_HEAD(zl) ((zl)+ZIPLIST_HEADER_SIZE) 96 #define ZIPLIST_ENTRY_TAIL(zl) ((zl)+intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))) 97 #define ZIPLIST_ENTRY_END(zl) ((zl)+intrev32ifbe(ZIPLIST_BYTES(zl))-1) 98 99 /* We know a positive increment can only be 1 because entries can only be 100 * pushed one at a time. */ 101 #define ZIPLIST_INCR_LENGTH(zl,incr) { \ 102 if (ZIPLIST_LENGTH(zl) < UINT16_MAX) \ 103 ZIPLIST_LENGTH(zl) = intrev16ifbe(intrev16ifbe(ZIPLIST_LENGTH(zl))+incr); \ 104 } 105 106 typedef struct zlentry { 107 unsigned int prevrawlensize, prevrawlen; 108 unsigned int lensize, len; 109 unsigned int headersize; 110 unsigned char encoding; 111 unsigned char *p; 112 } zlentry; 113 114 #define ZIP_ENTRY_ENCODING(ptr, encoding) do { \ 115 (encoding) = (ptr[0]) & (ZIP_STR_MASK | ZIP_INT_MASK); \ 116 if (((encoding) & ZIP_STR_MASK) < ZIP_STR_MASK) { \ 117 /* String encoding: 2 MSBs */ \ 118 (encoding) &= ZIP_STR_MASK; \ 119 } \ 120 } while(0) 121 122 /* Return bytes needed to store integer encoded by 'encoding' */ 123 static unsigned int zipIntSize(unsigned char encoding) { 124 switch(encoding) { 125 case ZIP_INT_16B: return sizeof(int16_t); 126 case ZIP_INT_32B: return sizeof(int32_t); 127 case ZIP_INT_64B: return sizeof(int64_t); 128 } 129 assert(NULL); 130 return 0; 131 } 132 133 /* Encode the length 'l' writing it in 'p'. If p is NULL it just returns 134 * the amount of bytes required to encode such a length. */ 135 static unsigned int zipEncodeLength(unsigned char *p, unsigned char encoding, unsigned int rawlen) { 136 unsigned char len = 1, buf[5]; 137 138 if (ZIP_IS_STR(encoding)) { 139 /* Although encoding is given it may not be set for strings, 140 * so we determine it here using the raw length. */ 141 if (rawlen <= 0x3f) { 142 if (!p) return len; 143 buf[0] = ZIP_STR_06B | rawlen; 144 } else if (rawlen <= 0x3fff) { 145 len += 1; 146 if (!p) return len; 147 buf[0] = ZIP_STR_14B | ((rawlen >> 8) & 0x3f); 148 buf[1] = rawlen & 0xff; 149 } else { 150 len += 4; 151 if (!p) return len; 152 buf[0] = ZIP_STR_32B; 153 buf[1] = (rawlen >> 24) & 0xff; 154 buf[2] = (rawlen >> 16) & 0xff; 155 buf[3] = (rawlen >> 8) & 0xff; 156 buf[4] = rawlen & 0xff; 157 } 158 } else { 159 /* Implies integer encoding, so length is always 1. */ 160 if (!p) return len; 161 buf[0] = encoding; 162 } 163 164 /* Store this length at p */ 165 memcpy(p,buf,len); 166 return len; 167 } 168 169 /* Decode the length encoded in 'ptr'. The 'encoding' variable will hold the 170 * entries encoding, the 'lensize' variable will hold the number of bytes 171 * required to encode the entries length, and the 'len' variable will hold the 172 * entries length. */ 173 #define ZIP_DECODE_LENGTH(ptr, encoding, lensize, len) do { \ 174 ZIP_ENTRY_ENCODING((ptr), (encoding)); \ 175 if ((encoding) < ZIP_STR_MASK) { \ 176 if ((encoding) == ZIP_STR_06B) { \ 177 (lensize) = 1; \ 178 (len) = (ptr)[0] & 0x3f; \ 179 } else if ((encoding) == ZIP_STR_14B) { \ 180 (lensize) = 2; \ 181 (len) = (((ptr)[0] & 0x3f) << 8) | (ptr)[1]; \ 182 } else if (encoding == ZIP_STR_32B) { \ 183 (lensize) = 5; \ 184 (len) = ((ptr)[1] << 24) | \ 185 ((ptr)[2] << 16) | \ 186 ((ptr)[3] << 8) | \ 187 ((ptr)[4]); \ 188 } else { \ 189 assert(NULL); \ 190 } \ 191 } else { \ 192 (lensize) = 1; \ 193 (len) = zipIntSize(encoding); \ 194 } \ 195 } while(0); 196 197 /* Encode the length of the previous entry and write it to "p". Return the 198 * number of bytes needed to encode this length if "p" is NULL. */ 199 static unsigned int zipPrevEncodeLength(unsigned char *p, unsigned int len) { 200 if (p == NULL) { 201 return (len < ZIP_BIGLEN) ? 1 : sizeof(len)+1; 202 } else { 203 if (len < ZIP_BIGLEN) { 204 p[0] = len; 205 return 1; 206 } else { 207 p[0] = ZIP_BIGLEN; 208 memcpy(p+1,&len,sizeof(len)); 209 memrev32ifbe(p+1); 210 return 1+sizeof(len); 211 } 212 } 213 } 214 215 /* Encode the length of the previous entry and write it to "p". This only 216 * uses the larger encoding (required in __ziplistCascadeUpdate). */ 217 static void zipPrevEncodeLengthForceLarge(unsigned char *p, unsigned int len) { 218 if (p == NULL) return; 219 p[0] = ZIP_BIGLEN; 220 memcpy(p+1,&len,sizeof(len)); 221 memrev32ifbe(p+1); 222 } 223 224 /* Decode the number of bytes required to store the length of the previous 225 * element, from the perspective of the entry pointed to by 'ptr'. */ 226 #define ZIP_DECODE_PREVLENSIZE(ptr, prevlensize) do { \ 227 if ((ptr)[0] < ZIP_BIGLEN) { \ 228 (prevlensize) = 1; \ 229 } else { \ 230 (prevlensize) = 5; \ 231 } \ 232 } while(0); 233 234 /* Decode the length of the previous element, from the perspective of the entry 235 * pointed to by 'ptr'. */ 236 #define ZIP_DECODE_PREVLEN(ptr, prevlensize, prevlen) do { \ 237 ZIP_DECODE_PREVLENSIZE(ptr, prevlensize); \ 238 if ((prevlensize) == 1) { \ 239 (prevlen) = (ptr)[0]; \ 240 } else if ((prevlensize) == 5) { \ 241 assert(sizeof((prevlensize)) == 4); \ 242 memcpy(&(prevlen), ((char*)(ptr)) + 1, 4); \ 243 memrev32ifbe(&len); \ 244 } \ 245 } while(0); 246 247 /* Return the difference in number of bytes needed to store the length of the 248 * previous element 'len', in the entry pointed to by 'p'. */ 249 static int zipPrevLenByteDiff(unsigned char *p, unsigned int len) { 250 unsigned int prevlensize; 251 ZIP_DECODE_PREVLENSIZE(p, prevlensize); 252 return zipPrevEncodeLength(NULL, len) - prevlensize; 253 } 254 255 /* Return the total number of bytes used by the entry pointed to by 'p'. */ 256 static unsigned int zipRawEntryLength(unsigned char *p) { 257 unsigned int prevlensize, encoding, lensize, len; 258 ZIP_DECODE_PREVLENSIZE(p, prevlensize); 259 ZIP_DECODE_LENGTH(p + prevlensize, encoding, lensize, len); 260 return prevlensize + lensize + len; 261 } 262 263 /* Check if string pointed to by 'entry' can be encoded as an integer. 264 * Stores the integer value in 'v' and its encoding in 'encoding'. */ 265 static int zipTryEncoding(unsigned char *entry, unsigned int entrylen, long long *v, unsigned char *encoding) { 266 long long value; 267 268 if (entrylen >= 32 || entrylen == 0) return 0; 269 if (string2ll((char*)entry,entrylen,&value)) { 270 /* Great, the string can be encoded. Check what's the smallest 271 * of our encoding types that can hold this value. */ 272 if (value >= INT16_MIN && value <= INT16_MAX) { 273 *encoding = ZIP_INT_16B; 274 } else if (value >= INT32_MIN && value <= INT32_MAX) { 275 *encoding = ZIP_INT_32B; 276 } else { 277 *encoding = ZIP_INT_64B; 278 } 279 *v = value; 280 return 1; 281 } 282 return 0; 283 } 284 285 /* Store integer 'value' at 'p', encoded as 'encoding' */ 286 static void zipSaveInteger(unsigned char *p, int64_t value, unsigned char encoding) { 287 int16_t i16; 288 int32_t i32; 289 int64_t i64; 290 if (encoding == ZIP_INT_16B) { 291 i16 = value; 292 memcpy(p,&i16,sizeof(i16)); 293 memrev16ifbe(p); 294 } else if (encoding == ZIP_INT_32B) { 295 i32 = value; 296 memcpy(p,&i32,sizeof(i32)); 297 memrev32ifbe(p); 298 } else if (encoding == ZIP_INT_64B) { 299 i64 = value; 300 memcpy(p,&i64,sizeof(i64)); 301 memrev64ifbe(p); 302 } else { 303 assert(NULL); 304 } 305 } 306 307 /* Read integer encoded as 'encoding' from 'p' */ 308 static int64_t zipLoadInteger(unsigned char *p, unsigned char encoding) { 309 int16_t i16; 310 int32_t i32; 311 int64_t i64, ret = 0; 312 if (encoding == ZIP_INT_16B) { 313 memcpy(&i16,p,sizeof(i16)); 314 memrev16ifbe(&i16); 315 ret = i16; 316 } else if (encoding == ZIP_INT_32B) { 317 memcpy(&i32,p,sizeof(i32)); 318 memrev32ifbe(&i32); 319 ret = i32; 320 } else if (encoding == ZIP_INT_64B) { 321 memcpy(&i64,p,sizeof(i64)); 322 memrev64ifbe(&i64); 323 ret = i64; 324 } else { 325 assert(NULL); 326 } 327 return ret; 328 } 329 330 /* Return a struct with all information about an entry. */ 331 static zlentry zipEntry(unsigned char *p) { 332 zlentry e; 333 334 ZIP_DECODE_PREVLEN(p, e.prevrawlensize, e.prevrawlen); 335 ZIP_DECODE_LENGTH(p + e.prevrawlensize, e.encoding, e.lensize, e.len); 336 e.headersize = e.prevrawlensize + e.lensize; 337 e.p = p; 338 return e; 339 } 340 341 /* Create a new empty ziplist. */ 342 unsigned char *ziplistNew(void) { 343 unsigned int bytes = ZIPLIST_HEADER_SIZE+1; 344 unsigned char *zl = zmalloc(bytes); 345 ZIPLIST_BYTES(zl) = intrev32ifbe(bytes); 346 ZIPLIST_TAIL_OFFSET(zl) = intrev32ifbe(ZIPLIST_HEADER_SIZE); 347 ZIPLIST_LENGTH(zl) = 0; 348 zl[bytes-1] = ZIP_END; 349 return zl; 350 } 351 352 /* Resize the ziplist. */ 353 static unsigned char *ziplistResize(unsigned char *zl, unsigned int len) { 354 zl = zrealloc(zl,len); 355 ZIPLIST_BYTES(zl) = intrev32ifbe(len); 356 zl[len-1] = ZIP_END; 357 return zl; 358 } 359 360 /* When an entry is inserted, we need to set the prevlen field of the next 361 * entry to equal the length of the inserted entry. It can occur that this 362 * length cannot be encoded in 1 byte and the next entry needs to be grow 363 * a bit larger to hold the 5-byte encoded prevlen. This can be done for free, 364 * because this only happens when an entry is already being inserted (which 365 * causes a realloc and memmove). However, encoding the prevlen may require 366 * that this entry is grown as well. This effect may cascade throughout 367 * the ziplist when there are consecutive entries with a size close to 368 * ZIP_BIGLEN, so we need to check that the prevlen can be encoded in every 369 * consecutive entry. 370 * 371 * Note that this effect can also happen in reverse, where the bytes required 372 * to encode the prevlen field can shrink. This effect is deliberately ignored, 373 * because it can cause a "flapping" effect where a chain prevlen fields is 374 * first grown and then shrunk again after consecutive inserts. Rather, the 375 * field is allowed to stay larger than necessary, because a large prevlen 376 * field implies the ziplist is holding large entries anyway. 377 * 378 * The pointer "p" points to the first entry that does NOT need to be 379 * updated, i.e. consecutive fields MAY need an update. */ 380 static unsigned char *__ziplistCascadeUpdate(unsigned char *zl, unsigned char *p) { 381 size_t curlen = intrev32ifbe(ZIPLIST_BYTES(zl)), rawlen, rawlensize; 382 size_t offset, noffset, extra; 383 unsigned char *np; 384 zlentry cur, next; 385 386 while (p[0] != ZIP_END) { 387 cur = zipEntry(p); 388 rawlen = cur.headersize + cur.len; 389 rawlensize = zipPrevEncodeLength(NULL,rawlen); 390 391 /* Abort if there is no next entry. */ 392 if (p[rawlen] == ZIP_END) break; 393 next = zipEntry(p+rawlen); 394 395 /* Abort when "prevlen" has not changed. */ 396 if (next.prevrawlen == rawlen) break; 397 398 if (next.prevrawlensize < rawlensize) { 399 /* The "prevlen" field of "next" needs more bytes to hold 400 * the raw length of "cur". */ 401 offset = p-zl; 402 extra = rawlensize-next.prevrawlensize; 403 zl = ziplistResize(zl,curlen+extra); 404 p = zl+offset; 405 406 /* Current pointer and offset for next element. */ 407 np = p+rawlen; 408 noffset = np-zl; 409 410 /* Update tail offset when next element is not the tail element. */ 411 if ((zl+intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))) != np) { 412 ZIPLIST_TAIL_OFFSET(zl) = 413 intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))+extra); 414 } 415 416 /* Move the tail to the back. */ 417 memmove(np+rawlensize, 418 np+next.prevrawlensize, 419 curlen-noffset-next.prevrawlensize-1); 420 zipPrevEncodeLength(np,rawlen); 421 422 /* Advance the cursor */ 423 p += rawlen; 424 curlen += extra; 425 } else { 426 if (next.prevrawlensize > rawlensize) { 427 /* This would result in shrinking, which we want to avoid. 428 * So, set "rawlen" in the available bytes. */ 429 zipPrevEncodeLengthForceLarge(p+rawlen,rawlen); 430 } else { 431 zipPrevEncodeLength(p+rawlen,rawlen); 432 } 433 434 /* Stop here, as the raw length of "next" has not changed. */ 435 break; 436 } 437 } 438 return zl; 439 } 440 441 /* Delete "num" entries, starting at "p". Returns pointer to the ziplist. */ 442 static unsigned char *__ziplistDelete(unsigned char *zl, unsigned char *p, unsigned int num) { 443 unsigned int i, totlen, deleted = 0; 444 size_t offset; 445 int nextdiff = 0; 446 zlentry first, tail; 447 448 first = zipEntry(p); 449 for (i = 0; p[0] != ZIP_END && i < num; i++) { 450 p += zipRawEntryLength(p); 451 deleted++; 452 } 453 454 totlen = p-first.p; 455 if (totlen > 0) { 456 if (p[0] != ZIP_END) { 457 /* Tricky: storing the prevlen in this entry might reduce or 458 * increase the number of bytes needed, compared to the current 459 * prevlen. Note that we can always store this length because 460 * it was previously stored by an entry that is being deleted. */ 461 nextdiff = zipPrevLenByteDiff(p,first.prevrawlen); 462 zipPrevEncodeLength(p-nextdiff,first.prevrawlen); 463 464 /* Update offset for tail */ 465 ZIPLIST_TAIL_OFFSET(zl) = 466 intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))-totlen); 467 468 /* When the tail contains more than one entry, we need to take 469 * "nextdiff" in account as well. Otherwise, a change in the 470 * size of prevlen doesn't have an effect on the *tail* offset. */ 471 tail = zipEntry(p); 472 if (p[tail.headersize+tail.len] != ZIP_END) { 473 ZIPLIST_TAIL_OFFSET(zl) = 474 intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))+nextdiff); 475 } 476 477 /* Move tail to the front of the ziplist */ 478 memmove(first.p,p-nextdiff, 479 intrev32ifbe(ZIPLIST_BYTES(zl))-(p-zl)-1+nextdiff); 480 } else { 481 /* The entire tail was deleted. No need to move memory. */ 482 ZIPLIST_TAIL_OFFSET(zl) = 483 intrev32ifbe((first.p-zl)-first.prevrawlen); 484 } 485 486 /* Resize and update length */ 487 offset = first.p-zl; 488 zl = ziplistResize(zl, intrev32ifbe(ZIPLIST_BYTES(zl))-totlen+nextdiff); 489 ZIPLIST_INCR_LENGTH(zl,-deleted); 490 p = zl+offset; 491 492 /* When nextdiff != 0, the raw length of the next entry has changed, so 493 * we need to cascade the update throughout the ziplist */ 494 if (nextdiff != 0) 495 zl = __ziplistCascadeUpdate(zl,p); 496 } 497 return zl; 498 } 499 500 /* Insert item at "p". */ 501 static unsigned char *__ziplistInsert(unsigned char *zl, unsigned char *p, unsigned char *s, unsigned int slen) { 502 size_t curlen = intrev32ifbe(ZIPLIST_BYTES(zl)), reqlen, prevlen = 0; 503 size_t offset; 504 int nextdiff = 0; 505 unsigned char encoding = 0; 506 long long value = 123456789; /* initialized to avoid warning. Using a value 507 that is easy to see if for some reason 508 we use it uninitialized. */ 509 zlentry entry, tail; 510 511 /* Find out prevlen for the entry that is inserted. */ 512 if (p[0] != ZIP_END) { 513 entry = zipEntry(p); 514 prevlen = entry.prevrawlen; 515 } else { 516 unsigned char *ptail = ZIPLIST_ENTRY_TAIL(zl); 517 if (ptail[0] != ZIP_END) { 518 prevlen = zipRawEntryLength(ptail); 519 } 520 } 521 522 /* See if the entry can be encoded */ 523 if (zipTryEncoding(s,slen,&value,&encoding)) { 524 /* 'encoding' is set to the appropriate integer encoding */ 525 reqlen = zipIntSize(encoding); 526 } else { 527 /* 'encoding' is untouched, however zipEncodeLength will use the 528 * string length to figure out how to encode it. */ 529 reqlen = slen; 530 } 531 /* We need space for both the length of the previous entry and 532 * the length of the payload. */ 533 reqlen += zipPrevEncodeLength(NULL,prevlen); 534 reqlen += zipEncodeLength(NULL,encoding,slen); 535 536 /* When the insert position is not equal to the tail, we need to 537 * make sure that the next entry can hold this entry's length in 538 * its prevlen field. */ 539 nextdiff = (p[0] != ZIP_END) ? zipPrevLenByteDiff(p,reqlen) : 0; 540 541 /* Store offset because a realloc may change the address of zl. */ 542 offset = p-zl; 543 zl = ziplistResize(zl,curlen+reqlen+nextdiff); 544 p = zl+offset; 545 546 /* Apply memory move when necessary and update tail offset. */ 547 if (p[0] != ZIP_END) { 548 /* Subtract one because of the ZIP_END bytes */ 549 memmove(p+reqlen,p-nextdiff,curlen-offset-1+nextdiff); 550 551 /* Encode this entry's raw length in the next entry. */ 552 zipPrevEncodeLength(p+reqlen,reqlen); 553 554 /* Update offset for tail */ 555 ZIPLIST_TAIL_OFFSET(zl) = 556 intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))+reqlen); 557 558 /* When the tail contains more than one entry, we need to take 559 * "nextdiff" in account as well. Otherwise, a change in the 560 * size of prevlen doesn't have an effect on the *tail* offset. */ 561 tail = zipEntry(p+reqlen); 562 if (p[reqlen+tail.headersize+tail.len] != ZIP_END) { 563 ZIPLIST_TAIL_OFFSET(zl) = 564 intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))+nextdiff); 565 } 566 } else { 567 /* This element will be the new tail. */ 568 ZIPLIST_TAIL_OFFSET(zl) = intrev32ifbe(p-zl); 569 } 570 571 /* When nextdiff != 0, the raw length of the next entry has changed, so 572 * we need to cascade the update throughout the ziplist */ 573 if (nextdiff != 0) { 574 offset = p-zl; 575 zl = __ziplistCascadeUpdate(zl,p+reqlen); 576 p = zl+offset; 577 } 578 579 /* Write the entry */ 580 p += zipPrevEncodeLength(p,prevlen); 581 p += zipEncodeLength(p,encoding,slen); 582 if (ZIP_IS_STR(encoding)) { 583 memcpy(p,s,slen); 584 } else { 585 zipSaveInteger(p,value,encoding); 586 } 587 ZIPLIST_INCR_LENGTH(zl,1); 588 return zl; 589 } 590 591 unsigned char *ziplistPush(unsigned char *zl, unsigned char *s, unsigned int slen, int where) { 592 unsigned char *p; 593 p = (where == ZIPLIST_HEAD) ? ZIPLIST_ENTRY_HEAD(zl) : ZIPLIST_ENTRY_END(zl); 594 return __ziplistInsert(zl,p,s,slen); 595 } 596 597 /* Returns an offset to use for iterating with ziplistNext. When the given 598 * index is negative, the list is traversed back to front. When the list 599 * doesn't contain an element at the provided index, NULL is returned. */ 600 unsigned char *ziplistIndex(unsigned char *zl, int index) { 601 unsigned char *p; 602 zlentry entry; 603 if (index < 0) { 604 index = (-index)-1; 605 p = ZIPLIST_ENTRY_TAIL(zl); 606 if (p[0] != ZIP_END) { 607 entry = zipEntry(p); 608 while (entry.prevrawlen > 0 && index--) { 609 p -= entry.prevrawlen; 610 entry = zipEntry(p); 611 } 612 } 613 } else { 614 p = ZIPLIST_ENTRY_HEAD(zl); 615 while (p[0] != ZIP_END && index--) { 616 p += zipRawEntryLength(p); 617 } 618 } 619 return (p[0] == ZIP_END || index > 0) ? NULL : p; 620 } 621 622 /* Return pointer to next entry in ziplist. 623 * 624 * zl is the pointer to the ziplist 625 * p is the pointer to the current element 626 * 627 * The element after 'p' is returned, otherwise NULL if we are at the end. */ 628 unsigned char *ziplistNext(unsigned char *zl, unsigned char *p) { 629 ((void) zl); 630 631 /* "p" could be equal to ZIP_END, caused by ziplistDelete, 632 * and we should return NULL. Otherwise, we should return NULL 633 * when the *next* element is ZIP_END (there is no next entry). */ 634 if (p[0] == ZIP_END) { 635 return NULL; 636 } 637 638 p += zipRawEntryLength(p); 639 if (p[0] == ZIP_END) { 640 return NULL; 641 } 642 643 return p; 644 } 645 646 /* Return pointer to previous entry in ziplist. */ 647 unsigned char *ziplistPrev(unsigned char *zl, unsigned char *p) { 648 zlentry entry; 649 650 /* Iterating backwards from ZIP_END should return the tail. When "p" is 651 * equal to the first element of the list, we're already at the head, 652 * and should return NULL. */ 653 if (p[0] == ZIP_END) { 654 p = ZIPLIST_ENTRY_TAIL(zl); 655 return (p[0] == ZIP_END) ? NULL : p; 656 } else if (p == ZIPLIST_ENTRY_HEAD(zl)) { 657 return NULL; 658 } else { 659 entry = zipEntry(p); 660 assert(entry.prevrawlen > 0); 661 return p-entry.prevrawlen; 662 } 663 } 664 665 /* Get entry pointer to by 'p' and store in either 'e' or 'v' depending 666 * on the encoding of the entry. 'e' is always set to NULL to be able 667 * to find out whether the string pointer or the integer value was set. 668 * Return 0 if 'p' points to the end of the zipmap, 1 otherwise. */ 669 unsigned int ziplistGet(unsigned char *p, unsigned char **sstr, unsigned int *slen, long long *sval) { 670 zlentry entry; 671 if (p == NULL || p[0] == ZIP_END) return 0; 672 if (sstr) *sstr = NULL; 673 674 entry = zipEntry(p); 675 if (ZIP_IS_STR(entry.encoding)) { 676 if (sstr) { 677 *slen = entry.len; 678 *sstr = p+entry.headersize; 679 } 680 } else { 681 if (sval) { 682 *sval = zipLoadInteger(p+entry.headersize,entry.encoding); 683 } 684 } 685 return 1; 686 } 687 688 /* Insert an entry at "p". */ 689 unsigned char *ziplistInsert(unsigned char *zl, unsigned char *p, unsigned char *s, unsigned int slen) { 690 return __ziplistInsert(zl,p,s,slen); 691 } 692 693 /* Delete a single entry from the ziplist, pointed to by *p. 694 * Also update *p in place, to be able to iterate over the 695 * ziplist, while deleting entries. */ 696 unsigned char *ziplistDelete(unsigned char *zl, unsigned char **p) { 697 size_t offset = *p-zl; 698 zl = __ziplistDelete(zl,*p,1); 699 700 /* Store pointer to current element in p, because ziplistDelete will 701 * do a realloc which might result in a different "zl"-pointer. 702 * When the delete direction is back to front, we might delete the last 703 * entry and end up with "p" pointing to ZIP_END, so check this. */ 704 *p = zl+offset; 705 return zl; 706 } 707 708 /* Delete a range of entries from the ziplist. */ 709 unsigned char *ziplistDeleteRange(unsigned char *zl, unsigned int index, unsigned int num) { 710 unsigned char *p = ziplistIndex(zl,index); 711 return (p == NULL) ? zl : __ziplistDelete(zl,p,num); 712 } 713 714 /* Compare entry pointer to by 'p' with 'entry'. Return 1 if equal. */ 715 unsigned int ziplistCompare(unsigned char *p, unsigned char *sstr, unsigned int slen) { 716 zlentry entry; 717 unsigned char sencoding; 718 long long zval, sval; 719 if (p[0] == ZIP_END) return 0; 720 721 entry = zipEntry(p); 722 if (ZIP_IS_STR(entry.encoding)) { 723 /* Raw compare */ 724 if (entry.len == slen) { 725 return memcmp(p+entry.headersize,sstr,slen) == 0; 726 } else { 727 return 0; 728 } 729 } else { 730 /* Try to compare encoded values */ 731 if (zipTryEncoding(sstr,slen,&sval,&sencoding)) { 732 if (entry.encoding == sencoding) { 733 zval = zipLoadInteger(p+entry.headersize,entry.encoding); 734 return zval == sval; 735 } 736 } 737 } 738 return 0; 739 } 740 741 /* Find pointer to the entry equal to the specified entry. Skip 'skip' entries 742 * between every comparison. Returns NULL when the field could not be found. */ 743 unsigned char *ziplistFind(unsigned char *p, unsigned char *vstr, unsigned int vlen, unsigned int skip) { 744 int skipcnt = 0; 745 unsigned char vencoding = 0; 746 long long vll = 0; 747 748 while (p[0] != ZIP_END) { 749 unsigned int prevlensize, encoding, lensize, len; 750 unsigned char *q; 751 752 ZIP_DECODE_PREVLENSIZE(p, prevlensize); 753 ZIP_DECODE_LENGTH(p + prevlensize, encoding, lensize, len); 754 q = p + prevlensize + lensize; 755 756 if (skipcnt == 0) { 757 /* Compare current entry with specified entry */ 758 if (ZIP_IS_STR(encoding)) { 759 if (len == vlen && memcmp(q, vstr, vlen) == 0) { 760 return p; 761 } 762 } else { 763 /* Find out if the specified entry can be encoded */ 764 if (vencoding == 0) { 765 /* UINT_MAX when the entry CANNOT be encoded */ 766 if (!zipTryEncoding(vstr, vlen, &vll, &vencoding)) { 767 vencoding = UCHAR_MAX; 768 } 769 770 /* Must be non-zero by now */ 771 assert(vencoding); 772 } 773 774 /* Compare current entry with specified entry */ 775 if (encoding == vencoding) { 776 long long ll = zipLoadInteger(q, encoding); 777 if (ll == vll) { 778 return p; 779 } 780 } 781 } 782 783 /* Reset skip count */ 784 skipcnt = skip; 785 } else { 786 /* Skip entry */ 787 skipcnt--; 788 } 789 790 /* Move to next entry */ 791 p = q + len; 792 } 793 794 return NULL; 795 } 796 797 /* Return length of ziplist. */ 798 unsigned int ziplistLen(unsigned char *zl) { 799 unsigned int len = 0; 800 if (intrev16ifbe(ZIPLIST_LENGTH(zl)) < UINT16_MAX) { 801 len = intrev16ifbe(ZIPLIST_LENGTH(zl)); 802 } else { 803 unsigned char *p = zl+ZIPLIST_HEADER_SIZE; 804 while (*p != ZIP_END) { 805 p += zipRawEntryLength(p); 806 len++; 807 } 808 809 /* Re-store length if small enough */ 810 if (len < UINT16_MAX) ZIPLIST_LENGTH(zl) = intrev16ifbe(len); 811 } 812 return len; 813 } 814 815 /* Return ziplist blob size in bytes. */ 816 size_t ziplistBlobLen(unsigned char *zl) { 817 return intrev32ifbe(ZIPLIST_BYTES(zl)); 818 } 819 820 void ziplistRepr(unsigned char *zl) { 821 unsigned char *p; 822 int index = 0; 823 zlentry entry; 824 825 printf( 826 "{total bytes %d} " 827 "{length %u}\n" 828 "{tail offset %u}\n", 829 intrev32ifbe(ZIPLIST_BYTES(zl)), 830 intrev16ifbe(ZIPLIST_LENGTH(zl)), 831 intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))); 832 p = ZIPLIST_ENTRY_HEAD(zl); 833 while(*p != ZIP_END) { 834 entry = zipEntry(p); 835 printf( 836 "{" 837 "addr 0x%08lx, " 838 "index %2d, " 839 "offset %5ld, " 840 "rl: %5u, " 841 "hs %2u, " 842 "pl: %5u, " 843 "pls: %2u, " 844 "payload %5u" 845 "} ", 846 (long unsigned)p, 847 index, 848 (unsigned long) (p-zl), 849 entry.headersize+entry.len, 850 entry.headersize, 851 entry.prevrawlen, 852 entry.prevrawlensize, 853 entry.len); 854 p += entry.headersize; 855 if (ZIP_IS_STR(entry.encoding)) { 856 if (entry.len > 40) { 857 if (fwrite(p,40,1,stdout) == 0) perror("fwrite"); 858 printf("..."); 859 } else { 860 if (entry.len && 861 fwrite(p,entry.len,1,stdout) == 0) perror("fwrite"); 862 } 863 } else { 864 printf("%lld", (long long) zipLoadInteger(p,entry.encoding)); 865 } 866 printf("\n"); 867 p += entry.len; 868 index++; 869 } 870 printf("{end}\n\n"); 871 } 872 873 #ifdef ZIPLIST_TEST_MAIN 874 #include <sys/time.h> 875 #include "adlist.h" 876 #include "sds.h" 877 878 #define debug(f, ...) { if (DEBUG) printf(f, __VA_ARGS__); } 879 880 unsigned char *createList() { 881 unsigned char *zl = ziplistNew(); 882 zl = ziplistPush(zl, (unsigned char*)"foo", 3, ZIPLIST_TAIL); 883 zl = ziplistPush(zl, (unsigned char*)"quux", 4, ZIPLIST_TAIL); 884 zl = ziplistPush(zl, (unsigned char*)"hello", 5, ZIPLIST_HEAD); 885 zl = ziplistPush(zl, (unsigned char*)"1024", 4, ZIPLIST_TAIL); 886 return zl; 887 } 888 889 unsigned char *createIntList() { 890 unsigned char *zl = ziplistNew(); 891 char buf[32]; 892 893 sprintf(buf, "100"); 894 zl = ziplistPush(zl, (unsigned char*)buf, strlen(buf), ZIPLIST_TAIL); 895 sprintf(buf, "128000"); 896 zl = ziplistPush(zl, (unsigned char*)buf, strlen(buf), ZIPLIST_TAIL); 897 sprintf(buf, "-100"); 898 zl = ziplistPush(zl, (unsigned char*)buf, strlen(buf), ZIPLIST_HEAD); 899 sprintf(buf, "4294967296"); 900 zl = ziplistPush(zl, (unsigned char*)buf, strlen(buf), ZIPLIST_HEAD); 901 sprintf(buf, "non integer"); 902 zl = ziplistPush(zl, (unsigned char*)buf, strlen(buf), ZIPLIST_TAIL); 903 sprintf(buf, "much much longer non integer"); 904 zl = ziplistPush(zl, (unsigned char*)buf, strlen(buf), ZIPLIST_TAIL); 905 return zl; 906 } 907 908 long long usec(void) { 909 struct timeval tv; 910 gettimeofday(&tv,NULL); 911 return (((long long)tv.tv_sec)*1000000)+tv.tv_usec; 912 } 913 914 void stress(int pos, int num, int maxsize, int dnum) { 915 int i,j,k; 916 unsigned char *zl; 917 char posstr[2][5] = { "HEAD", "TAIL" }; 918 long long start; 919 for (i = 0; i < maxsize; i+=dnum) { 920 zl = ziplistNew(); 921 for (j = 0; j < i; j++) { 922 zl = ziplistPush(zl,(unsigned char*)"quux",4,ZIPLIST_TAIL); 923 } 924 925 /* Do num times a push+pop from pos */ 926 start = usec(); 927 for (k = 0; k < num; k++) { 928 zl = ziplistPush(zl,(unsigned char*)"quux",4,pos); 929 zl = ziplistDeleteRange(zl,0,1); 930 } 931 printf("List size: %8d, bytes: %8d, %dx push+pop (%s): %6lld usec\n", 932 i,intrev32ifbe(ZIPLIST_BYTES(zl)),num,posstr[pos],usec()-start); 933 zfree(zl); 934 } 935 } 936 937 void pop(unsigned char *zl, int where) { 938 unsigned char *p, *vstr; 939 unsigned int vlen; 940 long long vlong; 941 942 p = ziplistIndex(zl,where == ZIPLIST_HEAD ? 0 : -1); 943 if (ziplistGet(p,&vstr,&vlen,&vlong)) { 944 if (where == ZIPLIST_HEAD) 945 printf("Pop head: "); 946 else 947 printf("Pop tail: "); 948 949 if (vstr) 950 if (vlen && fwrite(vstr,vlen,1,stdout) == 0) perror("fwrite"); 951 else 952 printf("%lld", vlong); 953 954 printf("\n"); 955 ziplistDeleteRange(zl,-1,1); 956 } else { 957 printf("ERROR: Could not pop\n"); 958 exit(1); 959 } 960 } 961 962 int randstring(char *target, unsigned int min, unsigned int max) { 963 int p, len = min+rand()%(max-min+1); 964 int minval, maxval; 965 switch(rand() % 3) { 966 case 0: 967 minval = 0; 968 maxval = 255; 969 break; 970 case 1: 971 minval = 48; 972 maxval = 122; 973 break; 974 case 2: 975 minval = 48; 976 maxval = 52; 977 break; 978 default: 979 assert(NULL); 980 } 981 982 while(p < len) 983 target[p++] = minval+rand()%(maxval-minval+1); 984 return len; 985 } 986 987 int main(int argc, char **argv) { 988 unsigned char *zl, *p; 989 unsigned char *entry; 990 unsigned int elen; 991 long long value; 992 993 /* If an argument is given, use it as the random seed. */ 994 if (argc == 2) 995 srand(atoi(argv[1])); 996 997 zl = createIntList(); 998 ziplistRepr(zl); 999 1000 zl = createList(); 1001 ziplistRepr(zl); 1002 1003 pop(zl,ZIPLIST_TAIL); 1004 ziplistRepr(zl); 1005 1006 pop(zl,ZIPLIST_HEAD); 1007 ziplistRepr(zl); 1008 1009 pop(zl,ZIPLIST_TAIL); 1010 ziplistRepr(zl); 1011 1012 pop(zl,ZIPLIST_TAIL); 1013 ziplistRepr(zl); 1014 1015 printf("Get element at index 3:\n"); 1016 { 1017 zl = createList(); 1018 p = ziplistIndex(zl, 3); 1019 if (!ziplistGet(p, &entry, &elen, &value)) { 1020 printf("ERROR: Could not access index 3\n"); 1021 return 1; 1022 } 1023 if (entry) { 1024 if (elen && fwrite(entry,elen,1,stdout) == 0) perror("fwrite"); 1025 printf("\n"); 1026 } else { 1027 printf("%lld\n", value); 1028 } 1029 printf("\n"); 1030 } 1031 1032 printf("Get element at index 4 (out of range):\n"); 1033 { 1034 zl = createList(); 1035 p = ziplistIndex(zl, 4); 1036 if (p == NULL) { 1037 printf("No entry\n"); 1038 } else { 1039 printf("ERROR: Out of range index should return NULL, returned offset: %ld\n", p-zl); 1040 return 1; 1041 } 1042 printf("\n"); 1043 } 1044 1045 printf("Get element at index -1 (last element):\n"); 1046 { 1047 zl = createList(); 1048 p = ziplistIndex(zl, -1); 1049 if (!ziplistGet(p, &entry, &elen, &value)) { 1050 printf("ERROR: Could not access index -1\n"); 1051 return 1; 1052 } 1053 if (entry) { 1054 if (elen && fwrite(entry,elen,1,stdout) == 0) perror("fwrite"); 1055 printf("\n"); 1056 } else { 1057 printf("%lld\n", value); 1058 } 1059 printf("\n"); 1060 } 1061 1062 printf("Get element at index -4 (first element):\n"); 1063 { 1064 zl = createList(); 1065 p = ziplistIndex(zl, -4); 1066 if (!ziplistGet(p, &entry, &elen, &value)) { 1067 printf("ERROR: Could not access index -4\n"); 1068 return 1; 1069 } 1070 if (entry) { 1071 if (elen && fwrite(entry,elen,1,stdout) == 0) perror("fwrite"); 1072 printf("\n"); 1073 } else { 1074 printf("%lld\n", value); 1075 } 1076 printf("\n"); 1077 } 1078 1079 printf("Get element at index -5 (reverse out of range):\n"); 1080 { 1081 zl = createList(); 1082 p = ziplistIndex(zl, -5); 1083 if (p == NULL) { 1084 printf("No entry\n"); 1085 } else { 1086 printf("ERROR: Out of range index should return NULL, returned offset: %ld\n", p-zl); 1087 return 1; 1088 } 1089 printf("\n"); 1090 } 1091 1092 printf("Iterate list from 0 to end:\n"); 1093 { 1094 zl = createList(); 1095 p = ziplistIndex(zl, 0); 1096 while (ziplistGet(p, &entry, &elen, &value)) { 1097 printf("Entry: "); 1098 if (entry) { 1099 if (elen && fwrite(entry,elen,1,stdout) == 0) perror("fwrite"); 1100 } else { 1101 printf("%lld", value); 1102 } 1103 p = ziplistNext(zl,p); 1104 printf("\n"); 1105 } 1106 printf("\n"); 1107 } 1108 1109 printf("Iterate list from 1 to end:\n"); 1110 { 1111 zl = createList(); 1112 p = ziplistIndex(zl, 1); 1113 while (ziplistGet(p, &entry, &elen, &value)) { 1114 printf("Entry: "); 1115 if (entry) { 1116 if (elen && fwrite(entry,elen,1,stdout) == 0) perror("fwrite"); 1117 } else { 1118 printf("%lld", value); 1119 } 1120 p = ziplistNext(zl,p); 1121 printf("\n"); 1122 } 1123 printf("\n"); 1124 } 1125 1126 printf("Iterate list from 2 to end:\n"); 1127 { 1128 zl = createList(); 1129 p = ziplistIndex(zl, 2); 1130 while (ziplistGet(p, &entry, &elen, &value)) { 1131 printf("Entry: "); 1132 if (entry) { 1133 if (elen && fwrite(entry,elen,1,stdout) == 0) perror("fwrite"); 1134 } else { 1135 printf("%lld", value); 1136 } 1137 p = ziplistNext(zl,p); 1138 printf("\n"); 1139 } 1140 printf("\n"); 1141 } 1142 1143 printf("Iterate starting out of range:\n"); 1144 { 1145 zl = createList(); 1146 p = ziplistIndex(zl, 4); 1147 if (!ziplistGet(p, &entry, &elen, &value)) { 1148 printf("No entry\n"); 1149 } else { 1150 printf("ERROR\n"); 1151 } 1152 printf("\n"); 1153 } 1154 1155 printf("Iterate from back to front:\n"); 1156 { 1157 zl = createList(); 1158 p = ziplistIndex(zl, -1); 1159 while (ziplistGet(p, &entry, &elen, &value)) { 1160 printf("Entry: "); 1161 if (entry) { 1162 if (elen && fwrite(entry,elen,1,stdout) == 0) perror("fwrite"); 1163 } else { 1164 printf("%lld", value); 1165 } 1166 p = ziplistPrev(zl,p); 1167 printf("\n"); 1168 } 1169 printf("\n"); 1170 } 1171 1172 printf("Iterate from back to front, deleting all items:\n"); 1173 { 1174 zl = createList(); 1175 p = ziplistIndex(zl, -1); 1176 while (ziplistGet(p, &entry, &elen, &value)) { 1177 printf("Entry: "); 1178 if (entry) { 1179 if (elen && fwrite(entry,elen,1,stdout) == 0) perror("fwrite"); 1180 } else { 1181 printf("%lld", value); 1182 } 1183 zl = ziplistDelete(zl,&p); 1184 p = ziplistPrev(zl,p); 1185 printf("\n"); 1186 } 1187 printf("\n"); 1188 } 1189 1190 printf("Delete inclusive range 0,0:\n"); 1191 { 1192 zl = createList(); 1193 zl = ziplistDeleteRange(zl, 0, 1); 1194 ziplistRepr(zl); 1195 } 1196 1197 printf("Delete inclusive range 0,1:\n"); 1198 { 1199 zl = createList(); 1200 zl = ziplistDeleteRange(zl, 0, 2); 1201 ziplistRepr(zl); 1202 } 1203 1204 printf("Delete inclusive range 1,2:\n"); 1205 { 1206 zl = createList(); 1207 zl = ziplistDeleteRange(zl, 1, 2); 1208 ziplistRepr(zl); 1209 } 1210 1211 printf("Delete with start index out of range:\n"); 1212 { 1213 zl = createList(); 1214 zl = ziplistDeleteRange(zl, 5, 1); 1215 ziplistRepr(zl); 1216 } 1217 1218 printf("Delete with num overflow:\n"); 1219 { 1220 zl = createList(); 1221 zl = ziplistDeleteRange(zl, 1, 5); 1222 ziplistRepr(zl); 1223 } 1224 1225 printf("Delete foo while iterating:\n"); 1226 { 1227 zl = createList(); 1228 p = ziplistIndex(zl,0); 1229 while (ziplistGet(p,&entry,&elen,&value)) { 1230 if (entry && strncmp("foo",(char*)entry,elen) == 0) { 1231 printf("Delete foo\n"); 1232 zl = ziplistDelete(zl,&p); 1233 } else { 1234 printf("Entry: "); 1235 if (entry) { 1236 if (elen && fwrite(entry,elen,1,stdout) == 0) 1237 perror("fwrite"); 1238 } else { 1239 printf("%lld",value); 1240 } 1241 p = ziplistNext(zl,p); 1242 printf("\n"); 1243 } 1244 } 1245 printf("\n"); 1246 ziplistRepr(zl); 1247 } 1248 1249 printf("Regression test for >255 byte strings:\n"); 1250 { 1251 char v1[257],v2[257]; 1252 memset(v1,'x',256); 1253 memset(v2,'y',256); 1254 zl = ziplistNew(); 1255 zl = ziplistPush(zl,(unsigned char*)v1,strlen(v1),ZIPLIST_TAIL); 1256 zl = ziplistPush(zl,(unsigned char*)v2,strlen(v2),ZIPLIST_TAIL); 1257 1258 /* Pop values again and compare their value. */ 1259 p = ziplistIndex(zl,0); 1260 assert(ziplistGet(p,&entry,&elen,&value)); 1261 assert(strncmp(v1,(char*)entry,elen) == 0); 1262 p = ziplistIndex(zl,1); 1263 assert(ziplistGet(p,&entry,&elen,&value)); 1264 assert(strncmp(v2,(char*)entry,elen) == 0); 1265 printf("SUCCESS\n\n"); 1266 } 1267 1268 printf("Create long list and check indices:\n"); 1269 { 1270 zl = ziplistNew(); 1271 char buf[32]; 1272 int i,len; 1273 for (i = 0; i < 1000; i++) { 1274 len = sprintf(buf,"%d",i); 1275 zl = ziplistPush(zl,(unsigned char*)buf,len,ZIPLIST_TAIL); 1276 } 1277 for (i = 0; i < 1000; i++) { 1278 p = ziplistIndex(zl,i); 1279 assert(ziplistGet(p,NULL,NULL,&value)); 1280 assert(i == value); 1281 1282 p = ziplistIndex(zl,-i-1); 1283 assert(ziplistGet(p,NULL,NULL,&value)); 1284 assert(999-i == value); 1285 } 1286 printf("SUCCESS\n\n"); 1287 } 1288 1289 printf("Compare strings with ziplist entries:\n"); 1290 { 1291 zl = createList(); 1292 p = ziplistIndex(zl,0); 1293 if (!ziplistCompare(p,(unsigned char*)"hello",5)) { 1294 printf("ERROR: not \"hello\"\n"); 1295 return 1; 1296 } 1297 if (ziplistCompare(p,(unsigned char*)"hella",5)) { 1298 printf("ERROR: \"hella\"\n"); 1299 return 1; 1300 } 1301 1302 p = ziplistIndex(zl,3); 1303 if (!ziplistCompare(p,(unsigned char*)"1024",4)) { 1304 printf("ERROR: not \"1024\"\n"); 1305 return 1; 1306 } 1307 if (ziplistCompare(p,(unsigned char*)"1025",4)) { 1308 printf("ERROR: \"1025\"\n"); 1309 return 1; 1310 } 1311 printf("SUCCESS\n\n"); 1312 } 1313 1314 printf("Stress with random payloads of different encoding:\n"); 1315 { 1316 int i,j,len,where; 1317 unsigned char *p; 1318 char buf[1024]; 1319 int buflen; 1320 list *ref; 1321 listNode *refnode; 1322 1323 /* Hold temp vars from ziplist */ 1324 unsigned char *sstr; 1325 unsigned int slen; 1326 long long sval; 1327 1328 for (i = 0; i < 20000; i++) { 1329 zl = ziplistNew(); 1330 ref = listCreate(); 1331 listSetFreeMethod(ref,sdsfree); 1332 len = rand() % 256; 1333 1334 /* Create lists */ 1335 for (j = 0; j < len; j++) { 1336 where = (rand() & 1) ? ZIPLIST_HEAD : ZIPLIST_TAIL; 1337 if (rand() % 2) { 1338 buflen = randstring(buf,1,sizeof(buf)-1); 1339 } else { 1340 switch(rand() % 3) { 1341 case 0: 1342 buflen = sprintf(buf,"%lld",(0LL + rand()) >> 20); 1343 break; 1344 case 1: 1345 buflen = sprintf(buf,"%lld",(0LL + rand())); 1346 break; 1347 case 2: 1348 buflen = sprintf(buf,"%lld",(0LL + rand()) << 20); 1349 break; 1350 default: 1351 assert(NULL); 1352 } 1353 } 1354 1355 /* Add to ziplist */ 1356 zl = ziplistPush(zl, (unsigned char*)buf, buflen, where); 1357 1358 /* Add to reference list */ 1359 if (where == ZIPLIST_HEAD) { 1360 listAddNodeHead(ref,sdsnewlen(buf, buflen)); 1361 } else if (where == ZIPLIST_TAIL) { 1362 listAddNodeTail(ref,sdsnewlen(buf, buflen)); 1363 } else { 1364 assert(NULL); 1365 } 1366 } 1367 1368 assert(listLength(ref) == ziplistLen(zl)); 1369 for (j = 0; j < len; j++) { 1370 /* Naive way to get elements, but similar to the stresser 1371 * executed from the Tcl test suite. */ 1372 p = ziplistIndex(zl,j); 1373 refnode = listIndex(ref,j); 1374 1375 assert(ziplistGet(p,&sstr,&slen,&sval)); 1376 if (sstr == NULL) { 1377 buflen = sprintf(buf,"%lld",sval); 1378 } else { 1379 buflen = slen; 1380 memcpy(buf,sstr,buflen); 1381 buf[buflen] = '\0'; 1382 } 1383 assert(memcmp(buf,listNodeValue(refnode),buflen) == 0); 1384 } 1385 zfree(zl); 1386 listRelease(ref); 1387 } 1388 printf("SUCCESS\n\n"); 1389 } 1390 1391 printf("Stress with variable ziplist size:\n"); 1392 { 1393 stress(ZIPLIST_HEAD,100000,16384,256); 1394 stress(ZIPLIST_TAIL,100000,16384,256); 1395 } 1396 1397 return 0; 1398 } 1399 1400 #endif 1401