| 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(&prevlen); \ |
| 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 |