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