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