]>
git.saurik.com Git - redis.git/blob - ziplist.c
1 /* Memory layout of a ziplist, containing "foo", "bar", "quux":
2 * <zlbytes><zllen><len>"foo"<len>"bar"<len>"quux"
4 * <zlbytes> is an unsigned integer to hold the number of bytes that
5 * the ziplist occupies. This is stored to not have to traverse the ziplist
6 * to know the new length when pushing.
8 * <zllen> is the number of items in the ziplist. When this value is
9 * greater than 254, we need to traverse the entire list to know
10 * how many items it holds.
12 * <len> is the number of bytes occupied by a single entry. When this
13 * number is greater than 253, the length will occupy 5 bytes, where
14 * the extra bytes contain an unsigned integer to hold the length.
26 /* Important note: the ZIP_END value is used to depict the end of the
27 * ziplist structure. When a pointer contains an entry, the first couple
28 * of bytes contain the encoded length of the previous entry. This length
29 * is encoded as ZIP_ENC_RAW length, so the first two bits will contain 00
30 * and the byte will therefore never have a value of 255. */
32 #define ZIP_BIGLEN 254
36 #define ZIP_ENC_SHORT 1
38 #define ZIP_ENC_LLONG 3
39 #define ZIP_ENCODING(p) ((p)[0] >> 6)
41 /* Length encoding for raw entries */
42 #define ZIP_LEN_INLINE 0
43 #define ZIP_LEN_UINT16 1
44 #define ZIP_LEN_UINT32 2
47 #define ZIPLIST_BYTES(zl) (*((unsigned int*)(zl)))
48 #define ZIPLIST_TAIL_OFFSET(zl) (*((unsigned int*)((zl)+sizeof(unsigned int))))
49 #define ZIPLIST_LENGTH(zl) (*((zl)+2*sizeof(unsigned int)))
50 #define ZIPLIST_HEADER_SIZE (2*sizeof(unsigned int)+1)
51 #define ZIPLIST_ENTRY_HEAD(zl) ((zl)+ZIPLIST_HEADER_SIZE)
52 #define ZIPLIST_ENTRY_TAIL(zl) ((zl)+ZIPLIST_TAIL_OFFSET(zl))
53 #define ZIPLIST_ENTRY_END(zl) ((zl)+ZIPLIST_BYTES(zl)-1)
54 #define ZIPLIST_INCR_LENGTH(zl,incr) { \
55 if (ZIPLIST_LENGTH(zl) < ZIP_BIGLEN) ZIPLIST_LENGTH(zl)+=incr; }
57 typedef struct zlentry
{
58 unsigned int prevrawlensize
, prevrawlen
;
59 unsigned int lensize
, len
;
60 unsigned int headersize
;
61 unsigned char encoding
;
65 /* Return bytes needed to store integer encoded by 'encoding' */
66 static unsigned int zipEncodingSize(unsigned char encoding
) {
67 if (encoding
== ZIP_ENC_SHORT
) {
68 return sizeof(short int);
69 } else if (encoding
== ZIP_ENC_INT
) {
71 } else if (encoding
== ZIP_ENC_LLONG
) {
72 return sizeof(long long);
77 /* Decode the encoded length pointed by 'p'. If a pointer to 'lensize' is
78 * provided, it is set to the number of bytes required to encode the length. */
79 static unsigned int zipDecodeLength(unsigned char *p
, unsigned int *lensize
) {
80 unsigned char encoding
= ZIP_ENCODING(p
), lenenc
;
83 if (encoding
== ZIP_ENC_RAW
) {
84 lenenc
= (p
[0] >> 4) & 0x3;
85 if (lenenc
== ZIP_LEN_INLINE
) {
87 if (lensize
) *lensize
= 1;
88 } else if (lenenc
== ZIP_LEN_UINT16
) {
89 len
= p
[1] | (p
[2] << 8);
90 if (lensize
) *lensize
= 3;
92 len
= p
[1] | (p
[2] << 8) | (p
[3] << 16) | (p
[4] << 24);
93 if (lensize
) *lensize
= 5;
96 len
= zipEncodingSize(encoding
);
97 if (lensize
) *lensize
= 1;
102 /* Encode the length 'l' writing it in 'p'. If p is NULL it just returns
103 * the amount of bytes required to encode such a length. */
104 static unsigned int zipEncodeLength(unsigned char *p
, char encoding
, unsigned int rawlen
) {
105 unsigned char len
= 1, lenenc
, buf
[5];
106 if (encoding
== ZIP_ENC_RAW
) {
109 lenenc
= ZIP_LEN_INLINE
;
111 } else if (rawlen
<= 0xffff) {
114 lenenc
= ZIP_LEN_UINT16
;
115 buf
[1] = (rawlen
) & 0xff;
116 buf
[2] = (rawlen
>> 8) & 0xff;
120 lenenc
= ZIP_LEN_UINT32
;
121 buf
[1] = (rawlen
) & 0xff;
122 buf
[2] = (rawlen
>> 8) & 0xff;
123 buf
[3] = (rawlen
>> 16) & 0xff;
124 buf
[4] = (rawlen
>> 24) & 0xff;
126 buf
[0] = (lenenc
<< 4) | (buf
[0] & 0xf);
130 /* Apparently we need to store the length in 'p' */
131 buf
[0] = (encoding
<< 6) | (buf
[0] & 0x3f);
136 /* Decode the length of the previous element stored at "p". */
137 static unsigned int zipPrevDecodeLength(unsigned char *p
, unsigned int *lensize
) {
138 unsigned int len
= *p
;
139 if (len
< ZIP_BIGLEN
) {
140 if (lensize
) *lensize
= 1;
142 if (lensize
) *lensize
= 1+sizeof(len
);
143 memcpy(&len
,p
+1,sizeof(len
));
148 /* Encode the length of the previous entry and write it to "p". Return the
149 * number of bytes needed to encode this length if "p" is NULL. */
150 static unsigned int zipPrevEncodeLength(unsigned char *p
, unsigned int len
) {
152 return (len
< ZIP_BIGLEN
) ? 1 : sizeof(len
)+1;
154 if (len
< ZIP_BIGLEN
) {
159 memcpy(p
+1,&len
,sizeof(len
));
160 return 1+sizeof(len
);
165 /* Return the difference in number of bytes needed to store the new length
166 * "len" on the entry pointed to by "p". */
167 static int zipPrevLenByteDiff(unsigned char *p
, unsigned int len
) {
168 unsigned int prevlensize
;
169 zipPrevDecodeLength(p
,&prevlensize
);
170 return zipPrevEncodeLength(NULL
,len
)-prevlensize
;
173 /* Check if string pointed to by 'entry' can be encoded as an integer.
174 * Stores the integer value in 'v' and its encoding in 'encoding'.
175 * Warning: this function requires a NULL-terminated string! */
176 static int zipTryEncoding(unsigned char *entry
, long long *v
, unsigned char *encoding
) {
180 if (entry
[0] == '-' || (entry
[0] >= '0' && entry
[0] <= '9')) {
181 value
= strtoll((char*)entry
,&eptr
,10);
182 if (eptr
[0] != '\0') return 0;
183 if (value
>= SHRT_MIN
&& value
<= SHRT_MAX
) {
184 *encoding
= ZIP_ENC_SHORT
;
185 } else if (value
>= INT_MIN
&& value
<= INT_MAX
) {
186 *encoding
= ZIP_ENC_INT
;
188 *encoding
= ZIP_ENC_LLONG
;
196 /* Store integer 'value' at 'p', encoded as 'encoding' */
197 static void zipSaveInteger(unsigned char *p
, long long value
, unsigned char encoding
) {
201 if (encoding
== ZIP_ENC_SHORT
) {
203 memcpy(p
,&s
,sizeof(s
));
204 } else if (encoding
== ZIP_ENC_INT
) {
206 memcpy(p
,&i
,sizeof(i
));
207 } else if (encoding
== ZIP_ENC_LLONG
) {
209 memcpy(p
,&l
,sizeof(l
));
215 /* Read integer encoded as 'encoding' from 'p' */
216 static long long zipLoadInteger(unsigned char *p
, unsigned char encoding
) {
220 if (encoding
== ZIP_ENC_SHORT
) {
221 memcpy(&s
,p
,sizeof(s
));
223 } else if (encoding
== ZIP_ENC_INT
) {
224 memcpy(&i
,p
,sizeof(i
));
226 } else if (encoding
== ZIP_ENC_LLONG
) {
227 memcpy(&l
,p
,sizeof(l
));
235 /* Return a struct with all information about an entry. */
236 static zlentry
zipEntry(unsigned char *p
) {
238 e
.prevrawlen
= zipPrevDecodeLength(p
,&e
.prevrawlensize
);
239 e
.len
= zipDecodeLength(p
+e
.prevrawlensize
,&e
.lensize
);
240 e
.headersize
= e
.prevrawlensize
+e
.lensize
;
241 e
.encoding
= ZIP_ENCODING(p
+e
.prevrawlensize
);
246 /* Return the total number of bytes used by the entry at "p". */
247 static unsigned int zipRawEntryLength(unsigned char *p
) {
248 zlentry e
= zipEntry(p
);
249 return e
.headersize
+ e
.len
;
252 /* Create a new empty ziplist. */
253 unsigned char *ziplistNew(void) {
254 unsigned int bytes
= ZIPLIST_HEADER_SIZE
+1;
255 unsigned char *zl
= zmalloc(bytes
);
256 ZIPLIST_BYTES(zl
) = bytes
;
257 ZIPLIST_TAIL_OFFSET(zl
) = ZIPLIST_HEADER_SIZE
;
258 ZIPLIST_LENGTH(zl
) = 0;
259 zl
[bytes
-1] = ZIP_END
;
263 /* Resize the ziplist. */
264 static unsigned char *ziplistResize(unsigned char *zl
, unsigned int len
) {
265 zl
= zrealloc(zl
,len
);
266 ZIPLIST_BYTES(zl
) = len
;
271 /* Delete "num" entries, starting at "p". Returns pointer to the ziplist. */
272 static unsigned char *__ziplistDelete(unsigned char *zl
, unsigned char *p
, unsigned int num
) {
273 unsigned int i
, totlen
, deleted
= 0;
275 zlentry first
= zipEntry(p
);
276 for (i
= 0; p
[0] != ZIP_END
&& i
< num
; i
++) {
277 p
+= zipRawEntryLength(p
);
283 if (p
[0] != ZIP_END
) {
284 /* Tricky: storing the prevlen in this entry might reduce or
285 * increase the number of bytes needed, compared to the current
286 * prevlen. Note that we can always store this length because
287 * it was previously stored by an entry that is being deleted. */
288 nextdiff
= zipPrevLenByteDiff(p
,first
.prevrawlen
);
289 zipPrevEncodeLength(p
-nextdiff
,first
.prevrawlen
);
291 /* Update offset for tail */
292 ZIPLIST_TAIL_OFFSET(zl
) -= totlen
+nextdiff
;
294 /* Move tail to the front of the ziplist */
295 memmove(first
.p
,p
-nextdiff
,ZIPLIST_BYTES(zl
)-(p
-zl
)-1+nextdiff
);
297 /* The entire tail was deleted. No need to move memory. */
298 ZIPLIST_TAIL_OFFSET(zl
) = (first
.p
-zl
)-first
.prevrawlen
;
301 /* Resize and update length */
302 zl
= ziplistResize(zl
, ZIPLIST_BYTES(zl
)-totlen
+nextdiff
);
303 ZIPLIST_INCR_LENGTH(zl
,-deleted
);
308 /* Insert item at "p". */
309 static unsigned char *__ziplistInsert(unsigned char *zl
, unsigned char *p
, unsigned char *s
, unsigned int slen
) {
310 unsigned int curlen
= ZIPLIST_BYTES(zl
), reqlen
, prevlen
= 0;
311 unsigned int offset
, nextdiff
= 0;
313 unsigned char encoding
= ZIP_ENC_RAW
;
317 /* Find out prevlen for the entry that is inserted. */
318 if (p
[0] != ZIP_END
) {
320 prevlen
= entry
.prevrawlen
;
322 tail
= ZIPLIST_ENTRY_TAIL(zl
);
323 if (tail
[0] != ZIP_END
) {
324 prevlen
= zipRawEntryLength(tail
);
328 /* See if the entry can be encoded */
329 if (zipTryEncoding(s
,&value
,&encoding
)) {
330 reqlen
= zipEncodingSize(encoding
);
335 /* We need space for both the length of the previous entry and
336 * the length of the payload. */
337 reqlen
+= zipPrevEncodeLength(NULL
,prevlen
);
338 reqlen
+= zipEncodeLength(NULL
,encoding
,slen
);
340 /* When the insert position is not equal to the tail, we need to
341 * make sure that the next entry can hold this entry's length in
342 * its prevlen field. */
343 nextdiff
= (p
[0] != ZIP_END
) ? zipPrevLenByteDiff(p
,reqlen
) : 0;
345 /* Store offset because a realloc may change the address of zl. */
347 zl
= ziplistResize(zl
,curlen
+reqlen
+nextdiff
);
350 /* Apply memory move when necessary and update tail offset. */
351 if (p
[0] != ZIP_END
) {
352 /* Subtract one because of the ZIP_END bytes */
353 memmove(p
+reqlen
,p
-nextdiff
,curlen
-offset
-1+nextdiff
);
354 /* Encode this entry's raw length in the next entry. */
355 zipPrevEncodeLength(p
+reqlen
,reqlen
);
356 /* Update offset for tail */
357 ZIPLIST_TAIL_OFFSET(zl
) += reqlen
+nextdiff
;
359 /* This element will be the new tail. */
360 ZIPLIST_TAIL_OFFSET(zl
) = p
-zl
;
363 /* Write the entry */
364 p
+= zipPrevEncodeLength(p
,prevlen
);
365 p
+= zipEncodeLength(p
,encoding
,slen
);
366 if (encoding
!= ZIP_ENC_RAW
) {
367 zipSaveInteger(p
,value
,encoding
);
371 ZIPLIST_INCR_LENGTH(zl
,1);
375 unsigned char *ziplistPush(unsigned char *zl
, unsigned char *s
, unsigned int slen
, int where
) {
377 p
= (where
== ZIPLIST_HEAD
) ? ZIPLIST_ENTRY_HEAD(zl
) : ZIPLIST_ENTRY_END(zl
);
378 return __ziplistInsert(zl
,p
,s
,slen
);
381 unsigned char *ziplistPop(unsigned char *zl
, sds
*target
, int where
) {
385 if (target
) *target
= NULL
;
387 /* Get pointer to element to remove */
388 p
= (where
== ZIPLIST_HEAD
) ? ZIPLIST_ENTRY_HEAD(zl
) : ZIPLIST_ENTRY_TAIL(zl
);
389 if (*p
== ZIP_END
) return zl
;
393 if (entry
.encoding
== ZIP_ENC_RAW
) {
394 *target
= sdsnewlen(p
+entry
.headersize
,entry
.len
);
396 value
= zipLoadInteger(p
+entry
.headersize
,entry
.encoding
);
397 *target
= sdscatprintf(sdsempty(), "%lld", value
);
401 zl
= __ziplistDelete(zl
,p
,1);
405 /* Returns an offset to use for iterating with ziplistNext. When the given
406 * index is negative, the list is traversed back to front. When the list
407 * doesn't contain an element at the provided index, NULL is returned. */
408 unsigned char *ziplistIndex(unsigned char *zl
, int index
) {
413 p
= ZIPLIST_ENTRY_TAIL(zl
);
414 if (p
[0] != ZIP_END
) {
416 while (entry
.prevrawlen
> 0 && index
--) {
417 p
-= entry
.prevrawlen
;
422 p
= ZIPLIST_ENTRY_HEAD(zl
);
423 while (p
[0] != ZIP_END
&& index
--) {
424 p
+= zipRawEntryLength(p
);
427 return (p
[0] == ZIP_END
|| index
> 0) ? NULL
: p
;
430 /* Return pointer to next entry in ziplist. */
431 unsigned char *ziplistNext(unsigned char *zl
, unsigned char *p
) {
434 /* "p" could be equal to ZIP_END, caused by ziplistDelete,
435 * and we should return NULL. Otherwise, we should return NULL
436 * when the *next* element is ZIP_END (there is no next entry). */
437 if (p
[0] == ZIP_END
) {
440 p
= p
+zipRawEntryLength(p
);
441 return (p
[0] == ZIP_END
) ? NULL
: p
;
445 /* Return pointer to previous entry in ziplist. */
446 unsigned char *ziplistPrev(unsigned char *zl
, unsigned char *p
) {
449 /* Iterating backwards from ZIP_END should return the tail. When "p" is
450 * equal to the first element of the list, we're already at the head,
451 * and should return NULL. */
452 if (p
[0] == ZIP_END
) {
453 p
= ZIPLIST_ENTRY_TAIL(zl
);
454 return (p
[0] == ZIP_END
) ? NULL
: p
;
455 } else if (p
== ZIPLIST_ENTRY_HEAD(zl
)) {
459 return p
-entry
.prevrawlen
;
463 /* Get entry pointer to by 'p' and store in either 'e' or 'v' depending
464 * on the encoding of the entry. 'e' is always set to NULL to be able
465 * to find out whether the string pointer or the integer value was set.
466 * Return 0 if 'p' points to the end of the zipmap, 1 otherwise. */
467 unsigned int ziplistGet(unsigned char *p
, unsigned char **sstr
, unsigned int *slen
, long long *sval
) {
469 if (p
== NULL
|| p
[0] == ZIP_END
) return 0;
470 if (sstr
) *sstr
= NULL
;
473 if (entry
.encoding
== ZIP_ENC_RAW
) {
476 *sstr
= p
+entry
.headersize
;
480 *sval
= zipLoadInteger(p
+entry
.headersize
,entry
.encoding
);
486 /* Insert an entry at "p". */
487 unsigned char *ziplistInsert(unsigned char *zl
, unsigned char *p
, unsigned char *s
, unsigned int slen
) {
488 return __ziplistInsert(zl
,p
,s
,slen
);
491 /* Delete a single entry from the ziplist, pointed to by *p.
492 * Also update *p in place, to be able to iterate over the
493 * ziplist, while deleting entries. */
494 unsigned char *ziplistDelete(unsigned char *zl
, unsigned char **p
) {
495 unsigned int offset
= *p
-zl
;
496 zl
= __ziplistDelete(zl
,*p
,1);
498 /* Store pointer to current element in p, because ziplistDelete will
499 * do a realloc which might result in a different "zl"-pointer.
500 * When the delete direction is back to front, we might delete the last
501 * entry and end up with "p" pointing to ZIP_END, so check this. */
506 /* Delete a range of entries from the ziplist. */
507 unsigned char *ziplistDeleteRange(unsigned char *zl
, unsigned int index
, unsigned int num
) {
508 unsigned char *p
= ziplistIndex(zl
,index
);
509 return (p
== NULL
) ? zl
: __ziplistDelete(zl
,p
,num
);
512 /* Compare entry pointer to by 'p' with 'entry'. Return 1 if equal. */
513 unsigned int ziplistCompare(unsigned char *p
, unsigned char *sstr
, unsigned int slen
) {
515 unsigned char sencoding
;
516 long long zval
, sval
;
517 if (p
[0] == ZIP_END
) return 0;
520 if (entry
.encoding
== ZIP_ENC_RAW
) {
522 if (entry
.len
== slen
) {
523 return memcmp(p
+entry
.headersize
,sstr
,slen
) == 0;
528 /* Try to compare encoded values */
529 if (zipTryEncoding(sstr
,&sval
,&sencoding
)) {
530 if (entry
.encoding
== sencoding
) {
531 zval
= zipLoadInteger(p
+entry
.headersize
,entry
.encoding
);
539 /* Return length of ziplist. */
540 unsigned int ziplistLen(unsigned char *zl
) {
541 unsigned int len
= 0;
542 if (ZIPLIST_LENGTH(zl
) < ZIP_BIGLEN
) {
543 len
= ZIPLIST_LENGTH(zl
);
545 unsigned char *p
= zl
+ZIPLIST_HEADER_SIZE
;
546 while (*p
!= ZIP_END
) {
547 p
+= zipRawEntryLength(p
);
551 /* Re-store length if small enough */
552 if (len
< ZIP_BIGLEN
) ZIPLIST_LENGTH(zl
) = len
;
557 /* Return size in bytes of ziplist. */
558 unsigned int ziplistSize(unsigned char *zl
) {
559 return ZIPLIST_BYTES(zl
);
562 void ziplistRepr(unsigned char *zl
) {
566 printf("{total bytes %d} {length %u}\n",ZIPLIST_BYTES(zl
), ZIPLIST_LENGTH(zl
));
567 p
= ZIPLIST_ENTRY_HEAD(zl
);
568 while(*p
!= ZIP_END
) {
570 printf("{offset %ld, header %u, payload %u} ",p
-zl
,entry
.headersize
,entry
.len
);
571 p
+= entry
.headersize
;
572 if (entry
.encoding
== ZIP_ENC_RAW
) {
573 fwrite(p
,entry
.len
,1,stdout
);
575 printf("%lld", zipLoadInteger(p
,entry
.encoding
));
583 #ifdef ZIPLIST_TEST_MAIN
585 unsigned char *createList() {
586 unsigned char *zl
= ziplistNew();
587 zl
= ziplistPush(zl
, (unsigned char*)"foo", 3, ZIPLIST_TAIL
);
588 zl
= ziplistPush(zl
, (unsigned char*)"quux", 4, ZIPLIST_TAIL
);
589 zl
= ziplistPush(zl
, (unsigned char*)"hello", 5, ZIPLIST_HEAD
);
590 zl
= ziplistPush(zl
, (unsigned char*)"1024", 4, ZIPLIST_TAIL
);
594 unsigned char *createIntList() {
595 unsigned char *zl
= ziplistNew();
599 zl
= ziplistPush(zl
, (unsigned char*)buf
, strlen(buf
), ZIPLIST_TAIL
);
600 sprintf(buf
, "128000");
601 zl
= ziplistPush(zl
, (unsigned char*)buf
, strlen(buf
), ZIPLIST_TAIL
);
602 sprintf(buf
, "-100");
603 zl
= ziplistPush(zl
, (unsigned char*)buf
, strlen(buf
), ZIPLIST_HEAD
);
604 sprintf(buf
, "4294967296");
605 zl
= ziplistPush(zl
, (unsigned char*)buf
, strlen(buf
), ZIPLIST_HEAD
);
606 sprintf(buf
, "non integer");
607 zl
= ziplistPush(zl
, (unsigned char*)buf
, strlen(buf
), ZIPLIST_TAIL
);
608 sprintf(buf
, "much much longer non integer");
609 zl
= ziplistPush(zl
, (unsigned char*)buf
, strlen(buf
), ZIPLIST_TAIL
);
613 int main(int argc
, char **argv
) {
614 unsigned char *zl
, *p
;
615 unsigned char *entry
;
620 zl
= createIntList();
626 zl
= ziplistPop(zl
, &s
, ZIPLIST_TAIL
);
627 printf("Pop tail: %s (length %ld)\n", s
, sdslen(s
));
630 zl
= ziplistPop(zl
, &s
, ZIPLIST_HEAD
);
631 printf("Pop head: %s (length %ld)\n", s
, sdslen(s
));
634 zl
= ziplistPop(zl
, &s
, ZIPLIST_TAIL
);
635 printf("Pop tail: %s (length %ld)\n", s
, sdslen(s
));
638 zl
= ziplistPop(zl
, &s
, ZIPLIST_TAIL
);
639 printf("Pop tail: %s (length %ld)\n", s
, sdslen(s
));
642 printf("Get element at index 3:\n");
645 p
= ziplistIndex(zl
, 3);
646 if (!ziplistGet(p
, &entry
, &elen
, &value
)) {
647 printf("ERROR: Could not access index 3\n");
651 fwrite(entry
,elen
,1,stdout
);
654 printf("%lld\n", value
);
659 printf("Get element at index 4 (out of range):\n");
662 p
= ziplistIndex(zl
, 4);
664 printf("No entry\n");
666 printf("ERROR: Out of range index should return NULL, returned offset: %ld\n", p
-zl
);
672 printf("Get element at index -1 (last element):\n");
675 p
= ziplistIndex(zl
, -1);
676 if (!ziplistGet(p
, &entry
, &elen
, &value
)) {
677 printf("ERROR: Could not access index -1\n");
681 fwrite(entry
,elen
,1,stdout
);
684 printf("%lld\n", value
);
689 printf("Get element at index -4 (first element):\n");
692 p
= ziplistIndex(zl
, -4);
693 if (!ziplistGet(p
, &entry
, &elen
, &value
)) {
694 printf("ERROR: Could not access index -4\n");
698 fwrite(entry
,elen
,1,stdout
);
701 printf("%lld\n", value
);
706 printf("Get element at index -5 (reverse out of range):\n");
709 p
= ziplistIndex(zl
, -5);
711 printf("No entry\n");
713 printf("ERROR: Out of range index should return NULL, returned offset: %ld\n", p
-zl
);
719 printf("Iterate list from 0 to end:\n");
722 p
= ziplistIndex(zl
, 0);
723 while (ziplistGet(p
, &entry
, &elen
, &value
)) {
726 fwrite(entry
,elen
,1,stdout
);
728 printf("%lld", value
);
730 p
= ziplistNext(zl
,p
);
736 printf("Iterate list from 1 to end:\n");
739 p
= ziplistIndex(zl
, 1);
740 while (ziplistGet(p
, &entry
, &elen
, &value
)) {
743 fwrite(entry
,elen
,1,stdout
);
745 printf("%lld", value
);
747 p
= ziplistNext(zl
,p
);
753 printf("Iterate list from 2 to end:\n");
756 p
= ziplistIndex(zl
, 2);
757 while (ziplistGet(p
, &entry
, &elen
, &value
)) {
760 fwrite(entry
,elen
,1,stdout
);
762 printf("%lld", value
);
764 p
= ziplistNext(zl
,p
);
770 printf("Iterate starting out of range:\n");
773 p
= ziplistIndex(zl
, 4);
774 if (!ziplistGet(p
, &entry
, &elen
, &value
)) {
775 printf("No entry\n");
782 printf("Iterate from back to front:\n");
785 p
= ziplistIndex(zl
, -1);
786 while (ziplistGet(p
, &entry
, &elen
, &value
)) {
789 fwrite(entry
,elen
,1,stdout
);
791 printf("%lld", value
);
793 p
= ziplistPrev(zl
,p
);
799 printf("Iterate from back to front, deleting all items:\n");
802 p
= ziplistIndex(zl
, -1);
803 while (ziplistGet(p
, &entry
, &elen
, &value
)) {
806 fwrite(entry
,elen
,1,stdout
);
808 printf("%lld", value
);
810 zl
= ziplistDelete(zl
,&p
);
811 p
= ziplistPrev(zl
,p
);
817 printf("Delete inclusive range 0,0:\n");
820 zl
= ziplistDeleteRange(zl
, 0, 1);
824 printf("Delete inclusive range 0,1:\n");
827 zl
= ziplistDeleteRange(zl
, 0, 2);
831 printf("Delete inclusive range 1,2:\n");
834 zl
= ziplistDeleteRange(zl
, 1, 2);
838 printf("Delete with start index out of range:\n");
841 zl
= ziplistDeleteRange(zl
, 5, 1);
845 printf("Delete with num overflow:\n");
848 zl
= ziplistDeleteRange(zl
, 1, 5);
852 printf("Delete foo while iterating:\n");
855 p
= ziplistIndex(zl
,0);
856 while (ziplistGet(p
,&entry
,&elen
,&value
)) {
857 if (entry
&& strncmp("foo",(char*)entry
,elen
) == 0) {
858 printf("Delete foo\n");
859 zl
= ziplistDelete(zl
,&p
);
863 fwrite(entry
,elen
,1,stdout
);
865 printf("%lld",value
);
867 p
= ziplistNext(zl
,p
);
875 printf("Create long list and check indices:\n");
880 for (i
= 0; i
< 1000; i
++) {
881 len
= sprintf(buf
,"%d",i
);
882 zl
= ziplistPush(zl
,(unsigned char*)buf
,len
,ZIPLIST_TAIL
);
884 for (i
= 0; i
< 1000; i
++) {
885 p
= ziplistIndex(zl
,i
);
886 assert(ziplistGet(p
,NULL
,NULL
,&value
));
889 p
= ziplistIndex(zl
,-i
-1);
890 assert(ziplistGet(p
,NULL
,NULL
,&value
));
891 assert(999-i
== value
);
893 printf("SUCCESS\n\n");
896 printf("Compare strings with ziplist entries:\n");
899 p
= ziplistIndex(zl
,0);
900 if (!ziplistCompare(p
,(unsigned char*)"hello",5)) {
901 printf("ERROR: not \"hello\"\n");
904 if (ziplistCompare(p
,(unsigned char*)"hella",5)) {
905 printf("ERROR: \"hella\"\n");
909 p
= ziplistIndex(zl
,3);
910 if (!ziplistCompare(p
,(unsigned char*)"1024",4)) {
911 printf("ERROR: not \"1024\"\n");
914 if (ziplistCompare(p
,(unsigned char*)"1025",4)) {
915 printf("ERROR: \"1025\"\n");