]> git.saurik.com Git - redis.git/blob - ziplist.c
fix signedness errors in ziplist testing code
[redis.git] / ziplist.c
1 /* Memory layout of a ziplist, containing "foo", "bar", "quux":
2 * <zlbytes><zllen><len>"foo"<len>"bar"<len>"quux"
3 *
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.
7 *
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.
11 *
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.
15 */
16
17 #include <stdio.h>
18 #include <stdlib.h>
19 #include <string.h>
20 #include <assert.h>
21 #include <limits.h>
22 #include "zmalloc.h"
23 #include "sds.h"
24 #include "ziplist.h"
25
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. */
31 #define ZIP_END 255
32 #define ZIP_BIGLEN 254
33
34 /* Entry encoding */
35 #define ZIP_ENC_RAW 0
36 #define ZIP_ENC_SHORT 1
37 #define ZIP_ENC_INT 2
38 #define ZIP_ENC_LLONG 3
39 #define ZIP_ENCODING(p) ((p)[0] >> 6)
40
41 /* Length encoding for raw entries */
42 #define ZIP_LEN_INLINE 0
43 #define ZIP_LEN_UINT16 1
44 #define ZIP_LEN_UINT32 2
45
46 /* Utility macros */
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; }
56
57 typedef struct zlentry {
58 unsigned int prevrawlensize, prevrawlen;
59 unsigned int lensize, len;
60 unsigned int headersize;
61 unsigned char encoding;
62 unsigned char *p;
63 } zlentry;
64
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) {
70 return sizeof(int);
71 } else if (encoding == ZIP_ENC_LLONG) {
72 return sizeof(long long);
73 }
74 assert(NULL);
75 }
76
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;
81 unsigned int len;
82
83 if (encoding == ZIP_ENC_RAW) {
84 lenenc = (p[0] >> 4) & 0x3;
85 if (lenenc == ZIP_LEN_INLINE) {
86 len = p[0] & 0xf;
87 if (lensize) *lensize = 1;
88 } else if (lenenc == ZIP_LEN_UINT16) {
89 len = p[1] | (p[2] << 8);
90 if (lensize) *lensize = 3;
91 } else {
92 len = p[1] | (p[2] << 8) | (p[3] << 16) | (p[4] << 24);
93 if (lensize) *lensize = 5;
94 }
95 } else {
96 len = zipEncodingSize(encoding);
97 if (lensize) *lensize = 1;
98 }
99 return len;
100 }
101
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) {
107 if (rawlen <= 0xf) {
108 if (!p) return len;
109 lenenc = ZIP_LEN_INLINE;
110 buf[0] = rawlen;
111 } else if (rawlen <= 0xffff) {
112 len += 2;
113 if (!p) return len;
114 lenenc = ZIP_LEN_UINT16;
115 buf[1] = (rawlen ) & 0xff;
116 buf[2] = (rawlen >> 8) & 0xff;
117 } else {
118 len += 4;
119 if (!p) return len;
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;
125 }
126 buf[0] = (lenenc << 4) | (buf[0] & 0xf);
127 }
128 if (!p) return len;
129
130 /* Apparently we need to store the length in 'p' */
131 buf[0] = (encoding << 6) | (buf[0] & 0x3f);
132 memcpy(p,buf,len);
133 return len;
134 }
135
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;
141 } else {
142 if (lensize) *lensize = 1+sizeof(len);
143 memcpy(&len,p+1,sizeof(len));
144 }
145 return len;
146 }
147
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) {
151 if (p == NULL) {
152 return (len < ZIP_BIGLEN) ? 1 : sizeof(len)+1;
153 } else {
154 if (len < ZIP_BIGLEN) {
155 p[0] = len;
156 return 1;
157 } else {
158 p[0] = ZIP_BIGLEN;
159 memcpy(p+1,&len,sizeof(len));
160 return 1+sizeof(len);
161 }
162 }
163 }
164
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;
171 }
172
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) {
177 long long value;
178 char *eptr;
179
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;
187 } else {
188 *encoding = ZIP_ENC_LLONG;
189 }
190 *v = value;
191 return 1;
192 }
193 return 0;
194 }
195
196 /* Store integer 'value' at 'p', encoded as 'encoding' */
197 static void zipSaveInteger(unsigned char *p, long long value, unsigned char encoding) {
198 short int s;
199 int i;
200 long long l;
201 if (encoding == ZIP_ENC_SHORT) {
202 s = value;
203 memcpy(p,&s,sizeof(s));
204 } else if (encoding == ZIP_ENC_INT) {
205 i = value;
206 memcpy(p,&i,sizeof(i));
207 } else if (encoding == ZIP_ENC_LLONG) {
208 l = value;
209 memcpy(p,&l,sizeof(l));
210 } else {
211 assert(NULL);
212 }
213 }
214
215 /* Read integer encoded as 'encoding' from 'p' */
216 static long long zipLoadInteger(unsigned char *p, unsigned char encoding) {
217 short int s;
218 int i;
219 long long l, ret;
220 if (encoding == ZIP_ENC_SHORT) {
221 memcpy(&s,p,sizeof(s));
222 ret = s;
223 } else if (encoding == ZIP_ENC_INT) {
224 memcpy(&i,p,sizeof(i));
225 ret = i;
226 } else if (encoding == ZIP_ENC_LLONG) {
227 memcpy(&l,p,sizeof(l));
228 ret = l;
229 } else {
230 assert(NULL);
231 }
232 return ret;
233 }
234
235 /* Return a struct with all information about an entry. */
236 static zlentry zipEntry(unsigned char *p) {
237 zlentry e;
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);
242 e.p = p;
243 return e;
244 }
245
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;
250 }
251
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;
260 return zl;
261 }
262
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;
267 zl[len-1] = ZIP_END;
268 return zl;
269 }
270
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;
274 int nextdiff = 0;
275 zlentry first = zipEntry(p);
276 for (i = 0; p[0] != ZIP_END && i < num; i++) {
277 p += zipRawEntryLength(p);
278 deleted++;
279 }
280
281 totlen = p-first.p;
282 if (totlen > 0) {
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);
290
291 /* Update offset for tail */
292 ZIPLIST_TAIL_OFFSET(zl) -= totlen+nextdiff;
293
294 /* Move tail to the front of the ziplist */
295 memmove(first.p,p-nextdiff,ZIPLIST_BYTES(zl)-(p-zl)-1+nextdiff);
296 } else {
297 /* The entire tail was deleted. No need to move memory. */
298 ZIPLIST_TAIL_OFFSET(zl) = (first.p-zl)-first.prevrawlen;
299 }
300
301 /* Resize and update length */
302 zl = ziplistResize(zl, ZIPLIST_BYTES(zl)-totlen+nextdiff);
303 ZIPLIST_INCR_LENGTH(zl,-deleted);
304 }
305 return zl;
306 }
307
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;
312 unsigned char *tail;
313 unsigned char encoding = ZIP_ENC_RAW;
314 long long value;
315 zlentry entry;
316
317 /* Find out prevlen for the entry that is inserted. */
318 if (p[0] != ZIP_END) {
319 entry = zipEntry(p);
320 prevlen = entry.prevrawlen;
321 } else {
322 tail = ZIPLIST_ENTRY_TAIL(zl);
323 if (tail[0] != ZIP_END) {
324 prevlen = zipRawEntryLength(tail);
325 }
326 }
327
328 /* See if the entry can be encoded */
329 if (zipTryEncoding(s,&value,&encoding)) {
330 reqlen = zipEncodingSize(encoding);
331 } else {
332 reqlen = slen;
333 }
334
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);
339
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;
344
345 /* Store offset because a realloc may change the address of zl. */
346 offset = p-zl;
347 zl = ziplistResize(zl,curlen+reqlen+nextdiff);
348 p = zl+offset;
349
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;
358 } else {
359 /* This element will be the new tail. */
360 ZIPLIST_TAIL_OFFSET(zl) = p-zl;
361 }
362
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);
368 } else {
369 memcpy(p,s,slen);
370 }
371 ZIPLIST_INCR_LENGTH(zl,1);
372 return zl;
373 }
374
375 unsigned char *ziplistPush(unsigned char *zl, unsigned char *s, unsigned int slen, int where) {
376 unsigned char *p;
377 p = (where == ZIPLIST_HEAD) ? ZIPLIST_ENTRY_HEAD(zl) : ZIPLIST_ENTRY_END(zl);
378 return __ziplistInsert(zl,p,s,slen);
379 }
380
381 unsigned char *ziplistPop(unsigned char *zl, sds *target, int where) {
382 zlentry entry;
383 unsigned char *p;
384 long long value;
385 if (target) *target = NULL;
386
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;
390
391 entry = zipEntry(p);
392 if (target) {
393 if (entry.encoding == ZIP_ENC_RAW) {
394 *target = sdsnewlen(p+entry.headersize,entry.len);
395 } else {
396 value = zipLoadInteger(p+entry.headersize,entry.encoding);
397 *target = sdscatprintf(sdsempty(), "%lld", value);
398 }
399 }
400
401 zl = __ziplistDelete(zl,p,1);
402 return zl;
403 }
404
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) {
409 unsigned char *p;
410 zlentry entry;
411 if (index < 0) {
412 index = (-index)-1;
413 p = ZIPLIST_ENTRY_TAIL(zl);
414 if (p[0] != ZIP_END) {
415 entry = zipEntry(p);
416 while (entry.prevrawlen > 0 && index--) {
417 p -= entry.prevrawlen;
418 entry = zipEntry(p);
419 }
420 }
421 } else {
422 p = ZIPLIST_ENTRY_HEAD(zl);
423 while (p[0] != ZIP_END && index--) {
424 p += zipRawEntryLength(p);
425 }
426 }
427 return (p[0] == ZIP_END || index > 0) ? NULL : p;
428 }
429
430 /* Return pointer to next entry in ziplist. */
431 unsigned char *ziplistNext(unsigned char *zl, unsigned char *p) {
432 ((void) zl);
433
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) {
438 return NULL;
439 } else {
440 p = p+zipRawEntryLength(p);
441 return (p[0] == ZIP_END) ? NULL : p;
442 }
443 }
444
445 /* Return pointer to previous entry in ziplist. */
446 unsigned char *ziplistPrev(unsigned char *zl, unsigned char *p) {
447 zlentry entry;
448
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)) {
456 return NULL;
457 } else {
458 entry = zipEntry(p);
459 return p-entry.prevrawlen;
460 }
461 }
462
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) {
468 zlentry entry;
469 if (p == NULL || p[0] == ZIP_END) return 0;
470 if (sstr) *sstr = NULL;
471
472 entry = zipEntry(p);
473 if (entry.encoding == ZIP_ENC_RAW) {
474 if (sstr) {
475 *slen = entry.len;
476 *sstr = p+entry.headersize;
477 }
478 } else {
479 if (sval) {
480 *sval = zipLoadInteger(p+entry.headersize,entry.encoding);
481 }
482 }
483 return 1;
484 }
485
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);
489 }
490
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);
497
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. */
502 *p = zl+offset;
503 return zl;
504 }
505
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);
510 }
511
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) {
514 zlentry entry;
515 unsigned char sencoding;
516 long long zval, sval;
517 if (p[0] == ZIP_END) return 0;
518
519 entry = zipEntry(p);
520 if (entry.encoding == ZIP_ENC_RAW) {
521 /* Raw compare */
522 if (entry.len == slen) {
523 return memcmp(p+entry.headersize,sstr,slen) == 0;
524 } else {
525 return 0;
526 }
527 } else {
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);
532 return zval == sval;
533 }
534 }
535 }
536 return 0;
537 }
538
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);
544 } else {
545 unsigned char *p = zl+ZIPLIST_HEADER_SIZE;
546 while (*p != ZIP_END) {
547 p += zipRawEntryLength(p);
548 len++;
549 }
550
551 /* Re-store length if small enough */
552 if (len < ZIP_BIGLEN) ZIPLIST_LENGTH(zl) = len;
553 }
554 return len;
555 }
556
557 /* Return size in bytes of ziplist. */
558 unsigned int ziplistSize(unsigned char *zl) {
559 return ZIPLIST_BYTES(zl);
560 }
561
562 void ziplistRepr(unsigned char *zl) {
563 unsigned char *p;
564 zlentry entry;
565
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) {
569 entry = zipEntry(p);
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);
574 } else {
575 printf("%lld", zipLoadInteger(p,entry.encoding));
576 }
577 printf("\n");
578 p += entry.len;
579 }
580 printf("{end}\n\n");
581 }
582
583 #ifdef ZIPLIST_TEST_MAIN
584
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);
591 return zl;
592 }
593
594 unsigned char *createIntList() {
595 unsigned char *zl = ziplistNew();
596 char buf[32];
597
598 sprintf(buf, "100");
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);
610 return zl;
611 }
612
613 int main(int argc, char **argv) {
614 unsigned char *zl, *p;
615 unsigned char *entry;
616 unsigned int elen;
617 long long value;
618 sds s;
619
620 zl = createIntList();
621 ziplistRepr(zl);
622
623 zl = createList();
624 ziplistRepr(zl);
625
626 zl = ziplistPop(zl, &s, ZIPLIST_TAIL);
627 printf("Pop tail: %s (length %ld)\n", s, sdslen(s));
628 ziplistRepr(zl);
629
630 zl = ziplistPop(zl, &s, ZIPLIST_HEAD);
631 printf("Pop head: %s (length %ld)\n", s, sdslen(s));
632 ziplistRepr(zl);
633
634 zl = ziplistPop(zl, &s, ZIPLIST_TAIL);
635 printf("Pop tail: %s (length %ld)\n", s, sdslen(s));
636 ziplistRepr(zl);
637
638 zl = ziplistPop(zl, &s, ZIPLIST_TAIL);
639 printf("Pop tail: %s (length %ld)\n", s, sdslen(s));
640 ziplistRepr(zl);
641
642 printf("Get element at index 3:\n");
643 {
644 zl = createList();
645 p = ziplistIndex(zl, 3);
646 if (!ziplistGet(p, &entry, &elen, &value)) {
647 printf("ERROR: Could not access index 3\n");
648 return 1;
649 }
650 if (entry) {
651 fwrite(entry,elen,1,stdout);
652 printf("\n");
653 } else {
654 printf("%lld\n", value);
655 }
656 printf("\n");
657 }
658
659 printf("Get element at index 4 (out of range):\n");
660 {
661 zl = createList();
662 p = ziplistIndex(zl, 4);
663 if (p == NULL) {
664 printf("No entry\n");
665 } else {
666 printf("ERROR: Out of range index should return NULL, returned offset: %ld\n", p-zl);
667 return 1;
668 }
669 printf("\n");
670 }
671
672 printf("Get element at index -1 (last element):\n");
673 {
674 zl = createList();
675 p = ziplistIndex(zl, -1);
676 if (!ziplistGet(p, &entry, &elen, &value)) {
677 printf("ERROR: Could not access index -1\n");
678 return 1;
679 }
680 if (entry) {
681 fwrite(entry,elen,1,stdout);
682 printf("\n");
683 } else {
684 printf("%lld\n", value);
685 }
686 printf("\n");
687 }
688
689 printf("Get element at index -4 (first element):\n");
690 {
691 zl = createList();
692 p = ziplistIndex(zl, -4);
693 if (!ziplistGet(p, &entry, &elen, &value)) {
694 printf("ERROR: Could not access index -4\n");
695 return 1;
696 }
697 if (entry) {
698 fwrite(entry,elen,1,stdout);
699 printf("\n");
700 } else {
701 printf("%lld\n", value);
702 }
703 printf("\n");
704 }
705
706 printf("Get element at index -5 (reverse out of range):\n");
707 {
708 zl = createList();
709 p = ziplistIndex(zl, -5);
710 if (p == NULL) {
711 printf("No entry\n");
712 } else {
713 printf("ERROR: Out of range index should return NULL, returned offset: %ld\n", p-zl);
714 return 1;
715 }
716 printf("\n");
717 }
718
719 printf("Iterate list from 0 to end:\n");
720 {
721 zl = createList();
722 p = ziplistIndex(zl, 0);
723 while (ziplistGet(p, &entry, &elen, &value)) {
724 printf("Entry: ");
725 if (entry) {
726 fwrite(entry,elen,1,stdout);
727 } else {
728 printf("%lld", value);
729 }
730 p = ziplistNext(zl,p);
731 printf("\n");
732 }
733 printf("\n");
734 }
735
736 printf("Iterate list from 1 to end:\n");
737 {
738 zl = createList();
739 p = ziplistIndex(zl, 1);
740 while (ziplistGet(p, &entry, &elen, &value)) {
741 printf("Entry: ");
742 if (entry) {
743 fwrite(entry,elen,1,stdout);
744 } else {
745 printf("%lld", value);
746 }
747 p = ziplistNext(zl,p);
748 printf("\n");
749 }
750 printf("\n");
751 }
752
753 printf("Iterate list from 2 to end:\n");
754 {
755 zl = createList();
756 p = ziplistIndex(zl, 2);
757 while (ziplistGet(p, &entry, &elen, &value)) {
758 printf("Entry: ");
759 if (entry) {
760 fwrite(entry,elen,1,stdout);
761 } else {
762 printf("%lld", value);
763 }
764 p = ziplistNext(zl,p);
765 printf("\n");
766 }
767 printf("\n");
768 }
769
770 printf("Iterate starting out of range:\n");
771 {
772 zl = createList();
773 p = ziplistIndex(zl, 4);
774 if (!ziplistGet(p, &entry, &elen, &value)) {
775 printf("No entry\n");
776 } else {
777 printf("ERROR\n");
778 }
779 printf("\n");
780 }
781
782 printf("Iterate from back to front:\n");
783 {
784 zl = createList();
785 p = ziplistIndex(zl, -1);
786 while (ziplistGet(p, &entry, &elen, &value)) {
787 printf("Entry: ");
788 if (entry) {
789 fwrite(entry,elen,1,stdout);
790 } else {
791 printf("%lld", value);
792 }
793 p = ziplistPrev(zl,p);
794 printf("\n");
795 }
796 printf("\n");
797 }
798
799 printf("Iterate from back to front, deleting all items:\n");
800 {
801 zl = createList();
802 p = ziplistIndex(zl, -1);
803 while (ziplistGet(p, &entry, &elen, &value)) {
804 printf("Entry: ");
805 if (entry) {
806 fwrite(entry,elen,1,stdout);
807 } else {
808 printf("%lld", value);
809 }
810 zl = ziplistDelete(zl,&p);
811 p = ziplistPrev(zl,p);
812 printf("\n");
813 }
814 printf("\n");
815 }
816
817 printf("Delete inclusive range 0,0:\n");
818 {
819 zl = createList();
820 zl = ziplistDeleteRange(zl, 0, 1);
821 ziplistRepr(zl);
822 }
823
824 printf("Delete inclusive range 0,1:\n");
825 {
826 zl = createList();
827 zl = ziplistDeleteRange(zl, 0, 2);
828 ziplistRepr(zl);
829 }
830
831 printf("Delete inclusive range 1,2:\n");
832 {
833 zl = createList();
834 zl = ziplistDeleteRange(zl, 1, 2);
835 ziplistRepr(zl);
836 }
837
838 printf("Delete with start index out of range:\n");
839 {
840 zl = createList();
841 zl = ziplistDeleteRange(zl, 5, 1);
842 ziplistRepr(zl);
843 }
844
845 printf("Delete with num overflow:\n");
846 {
847 zl = createList();
848 zl = ziplistDeleteRange(zl, 1, 5);
849 ziplistRepr(zl);
850 }
851
852 printf("Delete foo while iterating:\n");
853 {
854 zl = createList();
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);
860 } else {
861 printf("Entry: ");
862 if (entry) {
863 fwrite(entry,elen,1,stdout);
864 } else {
865 printf("%lld",value);
866 }
867 p = ziplistNext(zl,p);
868 printf("\n");
869 }
870 }
871 printf("\n");
872 ziplistRepr(zl);
873 }
874
875 printf("Create long list and check indices:\n");
876 {
877 zl = ziplistNew();
878 char buf[32];
879 int i,len;
880 for (i = 0; i < 1000; i++) {
881 len = sprintf(buf,"%d",i);
882 zl = ziplistPush(zl,(unsigned char*)buf,len,ZIPLIST_TAIL);
883 }
884 for (i = 0; i < 1000; i++) {
885 p = ziplistIndex(zl,i);
886 assert(ziplistGet(p,NULL,NULL,&value));
887 assert(i == value);
888
889 p = ziplistIndex(zl,-i-1);
890 assert(ziplistGet(p,NULL,NULL,&value));
891 assert(999-i == value);
892 }
893 printf("SUCCESS\n\n");
894 }
895
896 printf("Compare strings with ziplist entries:\n");
897 {
898 zl = createList();
899 p = ziplistIndex(zl,0);
900 if (!ziplistCompare(p,(unsigned char*)"hello",5)) {
901 printf("ERROR: not \"hello\"\n");
902 return 1;
903 }
904 if (ziplistCompare(p,(unsigned char*)"hella",5)) {
905 printf("ERROR: \"hella\"\n");
906 return 1;
907 }
908
909 p = ziplistIndex(zl,3);
910 if (!ziplistCompare(p,(unsigned char*)"1024",4)) {
911 printf("ERROR: not \"1024\"\n");
912 return 1;
913 }
914 if (ziplistCompare(p,(unsigned char*)"1025",4)) {
915 printf("ERROR: \"1025\"\n");
916 return 1;
917 }
918 printf("SUCCESS\n");
919 }
920
921 return 0;
922 }
923 #endif