【redis源码】（五）Ziplist

lee_hirisun

　　和zipmap作为dict数据结构的备选一样，ziplist同样追求牺牲性能的情况下节省内存，毕竟redis被看做是一个in-memory的nosql工具。
　　
　　zipmap的源码中，印象最深的两个细节是：
　　1. 作者为了节省内存，如果存入的value是一个能转化成int的数字串，存储的时候，ziplist会将其转换成int类型存储
　　2. 同样为了节省内存，在存储长度的字段都是用1or5的存储方式，当被存储字段长度小于254的时候，使用一个字节，大于等于254的时候再使用额外四个字节去存储长度【吐槽一下，代码中最麻烦的那30%的代码都和这个细节有关~~~~~~如果直接用4个字节不好吗，亲？】
　　
　　添加了简单注释的代码如下
　　Ziplist.h



1 #define ZIPLIST_HEAD 0
2 #define ZIPLIST_TAIL 1
3
4 unsigned char *ziplistNew(void);
5 unsigned char *ziplistPush(unsigned char *zl, unsigned char *s, unsigned int slen, int where);
6 unsigned char *ziplistIndex(unsigned char *zl, int index);
7 unsigned char *ziplistNext(unsigned char *zl, unsigned char *p);
8 unsigned char *ziplistPrev(unsigned char *zl, unsigned char *p);
9 unsigned int ziplistGet(unsigned char *p, unsigned char **sval, unsigned int *slen, long long *lval);
10 unsigned char *ziplistInsert(unsigned char *zl, unsigned char *p, unsigned char *s, unsigned int slen);
11 unsigned char *ziplistDelete(unsigned char *zl, unsigned char **p);
12 unsigned char *ziplistDeleteRange(unsigned char *zl, unsigned int index, unsigned int num);
13 unsigned int ziplistCompare(unsigned char *p, unsigned char *s, unsigned int slen);
14 unsigned int ziplistLen(unsigned char *zl);
15 unsigned int ziplistSize(unsigned char *zl);
　　
　　Ziplist.c



   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  *
  14  *
  15  *  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  *  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  *  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  *  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
  64 #include
  65 #include
  66 #include
  67 #include
  68 #include
  69 #include "zmalloc.h"
  70 #include "ziplist.h"
  71
  72 int ll2string(char *s, size_t len, long long value);
  73
  74 #define ZIP_END 255
  75 #define ZIP_BIGLEN 254
  76
  77 // 4 + 4  + 2  + sizeof(entry)* + 4
  78 /* Different encoding/length possibilities */
  79
  80 // =  +
  81 #define ZIP_STR_06B (0 = INT16_MIN && value = INT32_MIN && value  rawlensize) {
480                 /* This would result in shrinking, which we want to avoid.
481                  * So, set "rawlen" in the available bytes. */
482                 zipPrevEncodeLengthForceLarge(p+rawlen,rawlen);
483             } else {
484                 zipPrevEncodeLength(p+rawlen,rawlen);
485             }
486
487             /* Stop here, as the raw length of "next" has not changed. */
488             break;
489         }
490     }
491     return zl;
492 }
493
494 //从p指定entry开始，删除连续的num个entry
495 /* Delete "num" entries, starting at "p". Returns pointer to the ziplist. */
496 static unsigned char *__ziplistDelete(unsigned char *zl, unsigned char *p, unsigned int num) {
497     unsigned int i, totlen, deleted = 0;
498     int offset, nextdiff = 0;
499     zlentry first, tail;
500
501     //计算指定删除区域的最后一段的下一段的entry头指针
502     first = zipEntry(p);
503     for (i = 0; p[0] != ZIP_END && i < num; i++) {
504         p += zipRawEntryLength(p);
505         deleted++;
506     }
507     //需要删除的总字节数totlen
508     totlen = p-first.p;
509     if (totlen > 0) {
510         //如果删除的最后一段的下一段不是ZIP_END
511         if (p[0] != ZIP_END) {
512             /* Tricky: storing the prevlen in this entry might reduce or
513              * increase the number of bytes needed, compared to the current
514              * prevlen. Note that we can always store this length because
515              * it was previously stored by an entry that is being deleted. */
516             //得到删除区域的下一段的prevlen和删除区域前一段的长度作比较，得到diff
517             nextdiff = zipPrevLenByteDiff(p,first.prevrawlen);
518             zipPrevEncodeLength(p-nextdiff,first.prevrawlen);
519
520             /* Update offset for tail */
521             ZIPLIST_TAIL_OFFSET(zl) -= totlen;
522
523             /* When the tail contains more than one entry, we need to take
524              * "nextdiff" in account as well. Otherwise, a change in the
525              * size of prevlen doesn't have an effect on the *tail* offset. */
526             tail = zipEntry(p);
527             if (p[tail.headersize+tail.len] != ZIP_END)
528                 ZIPLIST_TAIL_OFFSET(zl) += nextdiff;
529
530             /* Move tail to the front of the ziplist */
531             memmove(first.p,p-nextdiff,ZIPLIST_BYTES(zl)-(p-zl)-1+nextdiff);
532         } else {
533             /* The entire tail was deleted. No need to move memory. */
534             ZIPLIST_TAIL_OFFSET(zl) = (first.p-zl)-first.prevrawlen;
535         }
536
537         /* Resize and update length */
538         offset = first.p-zl;
539         zl = ziplistResize(zl, ZIPLIST_BYTES(zl)-totlen+nextdiff);
540         ZIPLIST_INCR_LENGTH(zl,-deleted);
541         p = zl+offset;
542
543         /* When nextdiff != 0, the raw length of the next entry has changed, so
544          * we need to cascade the update throughout the ziplist */
545         if (nextdiff != 0)
546             zl = __ziplistCascadeUpdate(zl,p);
547     }
548     return zl;
549 }
550
551 //在位置p插入一个新entry，
552 /* Insert item at "p". */
553 static unsigned char *__ziplistInsert(unsigned char *zl, unsigned char *p, unsigned char *s, unsigned int slen) {
554     unsigned int curlen = ZIPLIST_BYTES(zl), reqlen, prevlen = 0;
555     unsigned int offset, nextdiff = 0;
556     unsigned char encoding = 0;
557     long long value;
558     zlentry entry, tail;
559
560     /* Find out prevlen for the entry that is inserted. */
561     //如果插入的位置不是最后一个，得到p所在的entry的prevlen字段的大小，准备赋给新entry的prevlen字段
562     if (p[0] != ZIP_END) {
563         entry = zipEntry(p);
564         prevlen = entry.prevrawlen;
565     //如果插入的位置是最后一个，即在zl的最后push进一个entry，得到tail元素的prevlen字段的值，准备赋给新entry的prevlen字段
566     } else {
567         unsigned char *ptail = ZIPLIST_ENTRY_TAIL(zl);
568         if (ptail[0] != ZIP_END) {
569             prevlen = zipRawEntryLength(ptail);
570         }
571     }
572     //看这个要存如的数据是否可以存储成int类型，如果可以，返回value及encoding，如果不可以，则存入原字符串
573     /* See if the entry can be encoded */
574     if (zipTryEncoding(s,slen,&value,&encoding)) {
575         /* 'encoding' is set to the appropriate integer encoding */
576         reqlen = zipIntSize(encoding);
577     } else {
578         /* 'encoding' is untouched, however zipEncodeLength will use the
579          * string length to figure out how to encode it. */
580         reqlen = slen;
581     }
582     //得到当前entry头部两个字段需要的字节数，加上存入数据的长度，即得到整个entry所需要的字节数
583     /* We need space for both the length of the previous entry and
584      * the length of the payload. */
585     reqlen += zipPrevEncodeLength(NULL,prevlen);
586     reqlen += zipEncodeLength(NULL,encoding,slen);
587
588     /* When the insert position is not equal to the tail, we need to
589      * make sure that the next entry can hold this entry's length in
590      * its prevlen field. */
591      //得到下个entry的prevlen字段需要的自己数和当前字节数的差
592     nextdiff = (p[0] != ZIP_END) ? zipPrevLenByteDiff(p,reqlen) : 0;
593
594     //所以共需要增加的数据长度为reqlen+nextdiff
595     /* Store offset because a realloc may change the address of zl. */
596     offset = p-zl;
597     zl = ziplistResize(zl,curlen+reqlen+nextdiff);
598     p = zl+offset;
599
600     /* Apply memory move when necessary and update tail offset. */
601     if (p[0] != ZIP_END) {
602         /* Subtract one because of the ZIP_END bytes */
603         //为新entry流出reqlen长度的空隙
604         memmove(p+reqlen,p-nextdiff,curlen-offset-1+nextdiff);
605
606         /* Encode this entry's raw length in the next entry. */
607         //修改下个entry的prevlen字段
608         zipPrevEncodeLength(p+reqlen,reqlen);
609         //更新zl的offset字段
610         /* Update offset for tail */
611         ZIPLIST_TAIL_OFFSET(zl) += reqlen;
612
613         /* When the tail contains more than one entry, we need to take
614          * "nextdiff" in account as well. Otherwise, a change in the
615          * size of prevlen doesn't have an effect on the *tail* offset. */
616         //得到下一个entry的结构体
617         tail = zipEntry(p+reqlen);
618         if (p[reqlen+tail.headersize+tail.len] != ZIP_END)
619             ZIPLIST_TAIL_OFFSET(zl) += nextdiff;
620     //插入的entry在zl尾部，更新offerset
621     } else {
622         /* This element will be the new tail. */
623         ZIPLIST_TAIL_OFFSET(zl) = p-zl;
624     }
625
626     /* When nextdiff != 0, the raw length of the next entry has changed, so
627      * we need to cascade the update throughout the ziplist */
628     if (nextdiff != 0) {
629         offset = p-zl;
630         zl = __ziplistCascadeUpdate(zl,p+reqlen);
631         p = zl+offset;
632     }
633
634     //把entry写入空隙中
635     /* Write the entry */
636     p += zipPrevEncodeLength(p,prevlen);
637     p += zipEncodeLength(p,encoding,slen);
638     if (ZIP_IS_STR(encoding)) {
639         memcpy(p,s,slen);
640     } else {
641         zipSaveInteger(p,value,encoding);
642     }
643     //更新zl的zllen字段
644     ZIPLIST_INCR_LENGTH(zl,1);
645     return zl;
646 }
647
648 //向zl中push一个s开头长度slen的字符串
649 unsigned char *ziplistPush(unsigned char *zl, unsigned char *s, unsigned int slen, int where) {
650     unsigned char *p;
651     p = (where == ZIPLIST_HEAD) ? ZIPLIST_ENTRY_HEAD(zl) : ZIPLIST_ENTRY_END(zl);
652     return __ziplistInsert(zl,p,s,slen);
653 }
654
655
656
657 //遍历zl，找到index所在位置的头指针，如果超出范围则返回NULL指针
658 /* Returns an offset to use for iterating with ziplistNext. When the given
659  * index is negative, the list is traversed back to front. When the list
660  * doesn't contain an element at the provided index, NULL is returned. */
661 unsigned char *ziplistIndex(unsigned char *zl, int index) {
662     unsigned char *p;
663     zlentry entry;
664     if (index < 0) {
665         index = (-index)-1;
666         p = ZIPLIST_ENTRY_TAIL(zl);
667         if (p[0] != ZIP_END) {
668             entry = zipEntry(p);
669             while (entry.prevrawlen > 0 && index--) {
670                 p -= entry.prevrawlen;
671                 entry = zipEntry(p);
672             }
673         }
674     } else {
675         p = ZIPLIST_ENTRY_HEAD(zl);
676         while (p[0] != ZIP_END && index--) {
677             p += zipRawEntryLength(p);
678         }
679     }
680     return (p[0] == ZIP_END || index > 0) ? NULL : p;
681 }
682
683 //输入当前entry的头指针p，得到下一个entry的头指针，如果不存在，返回NULL
684 /* Return pointer to next entry in ziplist.
685  *
686  * zl is the pointer to the ziplist
687  * p is the pointer to the current element
688  *
689  * The element after 'p' is returned, otherwise NULL if we are at the end. */
690 unsigned char *ziplistNext(unsigned char *zl, unsigned char *p) {
691     ((void) zl);
692
693     /* "p" could be equal to ZIP_END, caused by ziplistDelete,
694      * and we should return NULL. Otherwise, we should return NULL
695      * when the *next* element is ZIP_END (there is no next entry). */
696     if (p[0] == ZIP_END) {
697         return NULL;
698     } else {
699         p = p+zipRawEntryLength(p);
700         return (p[0] == ZIP_END) ? NULL : p;
701     }
702 }
703
704
705 //输入zl中的一个entry的头指针p，返回其前一个元素的头指针，如果不存在，返回NULL
706 /* Return pointer to previous entry in ziplist. */
707 unsigned char *ziplistPrev(unsigned char *zl, unsigned char *p) {
708     zlentry entry;
709
710     /* Iterating backwards from ZIP_END should return the tail. When "p" is
711      * equal to the first element of the list, we're already at the head,
712      * and should return NULL. */
713     if (p[0] == ZIP_END) {
714         p = ZIPLIST_ENTRY_TAIL(zl);
715         return (p[0] == ZIP_END) ? NULL : p;
716     } else if (p == ZIPLIST_ENTRY_HEAD(zl)) {
717         return NULL;
718     } else {
719         entry = zipEntry(p);
720         assert(entry.prevrawlen > 0);
721         return p-entry.prevrawlen;
722     }
723 }
724
725 //根据entry的头指针，提取其中的内容，如果p为NULL或者是尾节点，则返回0，否则返回1. 如果p entry中的数据为字符串，则存入*sstr,如果是数字，存入*sval
726 /* Get entry pointer to by 'p' and store in either 'e' or 'v' depending
727  * on the encoding of the entry. 'e' is always set to NULL to be able
728  * to find out whether the string pointer or the integer value was set.
729  * Return 0 if 'p' points to the end of the zipmap, 1 otherwise. */
730 unsigned int ziplistGet(unsigned char *p, unsigned char **sstr, unsigned int *slen, long long *sval) {
731     zlentry entry;
732     if (p == NULL || p[0] == ZIP_END) return 0;
733     if (sstr) *sstr = NULL;
734
735     entry = zipEntry(p);
736     if (ZIP_IS_STR(entry.encoding)) {
737         if (sstr) {
738             *slen = entry.len;
739             *sstr = p+entry.headersize;
740         }
741     } else {
742         if (sval) {
743             *sval = zipLoadInteger(p+entry.headersize,entry.encoding);
744         }
745     }
746     return 1;
747 }
748
749 //在zl的p位置存入元素s，s的长度为slen
750 /* Insert an entry at "p". */
751 unsigned char *ziplistInsert(unsigned char *zl, unsigned char *p, unsigned char *s, unsigned int slen) {
752     return __ziplistInsert(zl,p,s,slen);
753 }
754
755 //删除*p指向entry，并返回下一个entry的头指针*p
756 /* Delete a single entry from the ziplist, pointed to by *p.
757  * Also update *p in place, to be able to iterate over the
758  * ziplist, while deleting entries. */
759 unsigned char *ziplistDelete(unsigned char *zl, unsigned char **p) {
760     unsigned int offset = *p-zl;
761     zl = __ziplistDelete(zl,*p,1);
762
763     /* Store pointer to current element in p, because ziplistDelete will
764      * do a realloc which might result in a different "zl"-pointer.
765      * When the delete direction is back to front, we might delete the last
766      * entry and end up with "p" pointing to ZIP_END, so check this. */
767     *p = zl+offset;
768     return zl;
769 }
770
771 //从index，开始，删除num个entry
772 /* Delete a range of entries from the ziplist. */
773 unsigned char *ziplistDeleteRange(unsigned char *zl, unsigned int index, unsigned int num) {
774     unsigned char *p = ziplistIndex(zl,index);
775     return (p == NULL) ? zl : __ziplistDelete(zl,p,num);
776 }
777
778 //把p开始的entry所包含的value和长度为slen的sstr串作比较
779 /* Compare entry pointer to by 'p' with 'entry'. Return 1 if equal. */
780 unsigned int ziplistCompare(unsigned char *p, unsigned char *sstr, unsigned int slen) {
781     zlentry entry;
782     unsigned char sencoding;
783     long long zval, sval;
784     if (p[0] == ZIP_END) return 0;
785
786     entry = zipEntry(p);
787     if (ZIP_IS_STR(entry.encoding)) {
788         /* Raw compare */
789         if (entry.len == slen) {
790             return memcmp(p+entry.headersize,sstr,slen) == 0;
791         } else {
792             return 0;
793         }
794     } else {
795         /* Try to compare encoded values */
796         if (zipTryEncoding(sstr,slen,&sval,&sencoding)) {
797             if (entry.encoding == sencoding) {
798                 zval = zipLoadInteger(p+entry.headersize,entry.encoding);
799                 return zval == sval;
800             }
801         }
802     }
803     return 0;
804 }
805
806 //返回zl所包含的entry数量，如果数量小于2字节能表示的数量【UINT16_MAX】直接返回zl第三段头信息，否则做遍历count数量
807 /* Return length of ziplist. */
808 unsigned int ziplistLen(unsigned char *zl) {
809     unsigned int len = 0;
810     if (ZIPLIST_LENGTH(zl) < UINT16_MAX) {
811         len = ZIPLIST_LENGTH(zl);
812     } else {
813         unsigned char *p = zl+ZIPLIST_HEADER_SIZE;
814         while (*p != ZIP_END) {
815             p += zipRawEntryLength(p);
816             len++;
817         }
818
819         /* Re-store length if small enough */
820         if (len < UINT16_MAX) ZIPLIST_LENGTH(zl) = len;
821     }
822     return len;
823 }
824
825 //得到zl整个占用的内存大小，单位bytes
826 /* Return size in bytes of ziplist. */
827 unsigned int ziplistSize(unsigned char *zl) {
828     return ZIPLIST_BYTES(zl);
829 }
830
831 //把zl tostring了~
832 void ziplistRepr(unsigned char *zl) {
833     unsigned char *p;
834     int index = 0;
835     zlentry entry;
836
837     printf(
838         "{total bytes %d} "
839         "{length %u}\n"
840         "{tail offset %u}\n",
841         ZIPLIST_BYTES(zl),
842         ZIPLIST_LENGTH(zl),
843         ZIPLIST_TAIL_OFFSET(zl));
844     p = ZIPLIST_ENTRY_HEAD(zl);
845     while(*p != ZIP_END) {
846         entry = zipEntry(p);
847         printf(
848             "{"
849                 "addr 0x%08lx, "
850                 "index %2d, "
851                 "offset %5ld, "
852                 "rl: %5u, "
853                 "hs %2u, "
854                 "pl: %5u, "
855                 "pls: %2u, "
856                 "payload %5u"
857             "} ",
858             (long unsigned)p,
859             index,
860             (unsigned long) (p-zl),
861             entry.headersize+entry.len,
862             entry.headersize,
863             entry.prevrawlen,
864             entry.prevrawlensize,
865             entry.len);
866         p += entry.headersize;
867         if (ZIP_IS_STR(entry.encoding)) {
868             if (entry.len > 40) {
869                 if (fwrite(p,40,1,stdout) == 0) perror("fwrite");
870                 printf("...");
871             } else {
872                 if (entry.len &&
873                     fwrite(p,entry.len,1,stdout) == 0) perror("fwrite");
874             }
875         } else {
876             printf("%lld", (long long) zipLoadInteger(p,entry.encoding));
877         }
878         printf("\n");
879         p += entry.len;
880         index++;
881     }
882     printf("{end}\n\n");
883 }
884
885 #ifdef ZIPLIST_TEST_MAIN
886 #include
887 #include "adlist.h"
888 #include "sds.h"
889
890 #define debug(f, ...) { if (DEBUG) printf(f, __VA_ARGS__); }
891
892 unsigned char *createList() {
893     unsigned char *zl = ziplistNew();
894     zl = ziplistPush(zl, (unsigned char*)"foo", 3, ZIPLIST_TAIL);
895     zl = ziplistPush(zl, (unsigned char*)"quux", 4, ZIPLIST_TAIL);
896     zl = ziplistPush(zl, (unsigned char*)"hello", 5, ZIPLIST_HEAD);
897     zl = ziplistPush(zl, (unsigned char*)"1024", 4, ZIPLIST_TAIL);
898     return zl;
899 }
900
901 unsigned char *createIntList() {
902     unsigned char *zl = ziplistNew();
903     char buf[32];
904
905     sprintf(buf, "100");
906     zl = ziplistPush(zl, (unsigned char*)buf, strlen(buf), ZIPLIST_TAIL);
907     sprintf(buf, "128000");
908     zl = ziplistPush(zl, (unsigned char*)buf, strlen(buf), ZIPLIST_TAIL);
909     sprintf(buf, "-100");
910     zl = ziplistPush(zl, (unsigned char*)buf, strlen(buf), ZIPLIST_HEAD);
911     sprintf(buf, "4294967296");
912     zl = ziplistPush(zl, (unsigned char*)buf, strlen(buf), ZIPLIST_HEAD);
913     sprintf(buf, "non integer");
914     zl = ziplistPush(zl, (unsigned char*)buf, strlen(buf), ZIPLIST_TAIL);
915     sprintf(buf, "much much longer non integer");
916     zl = ziplistPush(zl, (unsigned char*)buf, strlen(buf), ZIPLIST_TAIL);
917     return zl;
918 }
919
920 long long usec(void) {
921     struct timeval tv;
922     gettimeofday(&tv,NULL);
923     return (((long long)tv.tv_sec)*1000000)+tv.tv_usec;
924 }
925
926 void stress(int pos, int num, int maxsize, int dnum) {
927     int i,j,k;
928     unsigned char *zl;
929     char posstr[2][5] = { "HEAD", "TAIL" };
930     long long start;
931     for (i = 0; i < maxsize; i+=dnum) {
932         zl = ziplistNew();
933         for (j = 0; j < i; j++) {
934             zl = ziplistPush(zl,(unsigned char*)"quux",4,ZIPLIST_TAIL);
935         }
936
937         /* Do num times a push+pop from pos */
938         start = usec();
939         for (k = 0; k < num; k++) {
940             zl = ziplistPush(zl,(unsigned char*)"quux",4,pos);
941             zl = ziplistDeleteRange(zl,0,1);
942         }
943         printf("List size: %8d, bytes: %8d, %dx push+pop (%s): %6lld usec\n",
944             i,ZIPLIST_BYTES(zl),num,posstr[pos],usec()-start);
945         zfree(zl);
946     }
947 }
948
949 void pop(unsigned char *zl, int where) {
950     unsigned char *p, *vstr;
951     unsigned int vlen;
952     long long vlong;
953
954     p = ziplistIndex(zl,where == ZIPLIST_HEAD ? 0 : -1);
955     if (ziplistGet(p,&vstr,&vlen,&vlong)) {
956         if (where == ZIPLIST_HEAD)
957             printf("Pop head: ");
958         else
959             printf("Pop tail: ");
960
961         if (vstr)
962             if (vlen && fwrite(vstr,vlen,1,stdout) == 0) perror("fwrite");
963         else
964             printf("%lld", vlong);
965
966         printf("\n");
967         ziplistDeleteRange(zl,-1,1);
968     } else {
969         printf("ERROR: Could not pop\n");
970         exit(1);
971     }
972 }
973
974 int randstring(char *target, unsigned int min, unsigned int max) {
975     int p, len = min+rand()%(max-min+1);
976     int minval, maxval;
977     switch(rand() % 3) {
978     case 0:
979         minval = 0;
980         maxval = 255;
981     break;
982     case 1:
983         minval = 48;
984         maxval = 122;
985     break;
986     case 2:
987         minval = 48;
988         maxval = 52;
989     break;
990     default:
991         assert(NULL);
992     }
993
994     while(p < len)
995         target[p++] = minval+rand()%(maxval-minval+1);
996     return len;
997 }
998
999 int main(int argc, char **argv) {
1000     unsigned char *zl, *p;
1001     unsigned char *entry;
1002     unsigned int elen;
1003     long long value;
1004
1005     /* If an argument is given, use it as the random seed. */
1006     if (argc == 2)
1007         srand(atoi(argv[1]));
1008
1009     zl = createIntList();
1010     ziplistRepr(zl);
1011
1012     zl = createList();
1013     ziplistRepr(zl);
1014
1015     pop(zl,ZIPLIST_TAIL);
1016     ziplistRepr(zl);
1017
1018     pop(zl,ZIPLIST_HEAD);
1019     ziplistRepr(zl);
1020
1021     pop(zl,ZIPLIST_TAIL);
1022     ziplistRepr(zl);
1023
1024     pop(zl,ZIPLIST_TAIL);
1025     ziplistRepr(zl);
1026
1027     printf("Get element at index 3:\n");
1028     {
1029         zl = createList();
1030         p = ziplistIndex(zl, 3);
1031         if (!ziplistGet(p, &entry, &elen, &value)) {
1032             printf("ERROR: Could not access index 3\n");
1033             return 1;
1034         }
1035         if (entry) {
1036             if (elen && fwrite(entry,elen,1,stdout) == 0) perror("fwrite");
1037             printf("\n");
1038         } else {
1039             printf("%lld\n", value);
1040         }
1041         printf("\n");
1042     }
1043
1044     printf("Get element at index 4 (out of range):\n");
1045     {
1046         zl = createList();
1047         p = ziplistIndex(zl, 4);
1048         if (p == NULL) {
1049             printf("No entry\n");
1050         } else {
1051             printf("ERROR: Out of range index should return NULL, returned offset: %ld\n", p-zl);
1052             return 1;
1053         }
1054         printf("\n");
1055     }
1056
1057     printf("Get element at index -1 (last element):\n");
1058     {
1059         zl = createList();
1060         p = ziplistIndex(zl, -1);
1061         if (!ziplistGet(p, &entry, &elen, &value)) {
1062             printf("ERROR: Could not access index -1\n");
1063             return 1;
1064         }
1065         if (entry) {
1066             if (elen && fwrite(entry,elen,1,stdout) == 0) perror("fwrite");
1067             printf("\n");
1068         } else {
1069             printf("%lld\n", value);
1070         }
1071         printf("\n");
1072     }
1073
1074     printf("Get element at index -4 (first element):\n");
1075     {
1076         zl = createList();
1077         p = ziplistIndex(zl, -4);
1078         if (!ziplistGet(p, &entry, &elen, &value)) {
1079             printf("ERROR: Could not access index -4\n");
1080             return 1;
1081         }
1082         if (entry) {
1083             if (elen && fwrite(entry,elen,1,stdout) == 0) perror("fwrite");
1084             printf("\n");
1085         } else {
1086             printf("%lld\n", value);
1087         }
1088         printf("\n");
1089     }
1090
1091     printf("Get element at index -5 (reverse out of range):\n");
1092     {
1093         zl = createList();
1094         p = ziplistIndex(zl, -5);
1095         if (p == NULL) {
1096             printf("No entry\n");
1097         } else {
1098             printf("ERROR: Out of range index should return NULL, returned offset: %ld\n", p-zl);
1099             return 1;
1100         }
1101         printf("\n");
1102     }
1103
1104     printf("Iterate list from 0 to end:\n");
1105     {
1106         zl = createList();
1107         p = ziplistIndex(zl, 0);
1108         while (ziplistGet(p, &entry, &elen, &value)) {
1109             printf("Entry: ");
1110             if (entry) {
1111                 if (elen && fwrite(entry,elen,1,stdout) == 0) perror("fwrite");
1112             } else {
1113                 printf("%lld", value);
1114             }
1115             p = ziplistNext(zl,p);
1116             printf("\n");
1117         }
1118         printf("\n");
1119     }
1120
1121     printf("Iterate list from 1 to end:\n");
1122     {
1123         zl = createList();
1124         p = ziplistIndex(zl, 1);
1125         while (ziplistGet(p, &entry, &elen, &value)) {
1126             printf("Entry: ");
1127             if (entry) {
1128                 if (elen && fwrite(entry,elen,1,stdout) == 0) perror("fwrite");
1129             } else {
1130                 printf("%lld", value);
1131             }
1132             p = ziplistNext(zl,p);
1133             printf("\n");
1134         }
1135         printf("\n");
1136     }
1137
1138     printf("Iterate list from 2 to end:\n");
1139     {
1140         zl = createList();
1141         p = ziplistIndex(zl, 2);
1142         while (ziplistGet(p, &entry, &elen, &value)) {
1143             printf("Entry: ");
1144             if (entry) {
1145                 if (elen && fwrite(entry,elen,1,stdout) == 0) perror("fwrite");
1146             } else {
1147                 printf("%lld", value);
1148             }
1149             p = ziplistNext(zl,p);
1150             printf("\n");
1151         }
1152         printf("\n");
1153     }
1154
1155     printf("Iterate starting out of range:\n");
1156     {
1157         zl = createList();
1158         p = ziplistIndex(zl, 4);
1159         if (!ziplistGet(p, &entry, &elen, &value)) {
1160             printf("No entry\n");
1161         } else {
1162             printf("ERROR\n");
1163         }
1164         printf("\n");
1165     }
1166
1167     printf("Iterate from back to front:\n");
1168     {
1169         zl = createList();
1170         p = ziplistIndex(zl, -1);
1171         while (ziplistGet(p, &entry, &elen, &value)) {
1172             printf("Entry: ");
1173             if (entry) {
1174                 if (elen && fwrite(entry,elen,1,stdout) == 0) perror("fwrite");
1175             } else {
1176                 printf("%lld", value);
1177             }
1178             p = ziplistPrev(zl,p);
1179             printf("\n");
1180         }
1181         printf("\n");
1182     }
1183
1184     printf("Iterate from back to front, deleting all items:\n");
1185     {
1186         zl = createList();
1187         p = ziplistIndex(zl, -1);
1188         while (ziplistGet(p, &entry, &elen, &value)) {
1189             printf("Entry: ");
1190             if (entry) {
1191                 if (elen && fwrite(entry,elen,1,stdout) == 0) perror("fwrite");
1192             } else {
1193                 printf("%lld", value);
1194             }
1195             zl = ziplistDelete(zl,&p);
1196             p = ziplistPrev(zl,p);
1197             printf("\n");
1198         }
1199         printf("\n");
1200     }
1201
1202     printf("Delete inclusive range 0,0:\n");
1203     {
1204         zl = createList();
1205         zl = ziplistDeleteRange(zl, 0, 1);
1206         ziplistRepr(zl);
1207     }
1208
1209     printf("Delete inclusive range 0,1:\n");
1210     {
1211         zl = createList();
1212         zl = ziplistDeleteRange(zl, 0, 2);
1213         ziplistRepr(zl);
1214     }
1215
1216     printf("Delete inclusive range 1,2:\n");
1217     {
1218         zl = createList();
1219         zl = ziplistDeleteRange(zl, 1, 2);
1220         ziplistRepr(zl);
1221     }
1222
1223     printf("Delete with start index out of range:\n");
1224     {
1225         zl = createList();
1226         zl = ziplistDeleteRange(zl, 5, 1);
1227         ziplistRepr(zl);
1228     }
1229
1230     printf("Delete with num overflow:\n");
1231     {
1232         zl = createList();
1233         zl = ziplistDeleteRange(zl, 1, 5);
1234         ziplistRepr(zl);
1235     }
1236
1237     printf("Delete foo while iterating:\n");
1238     {
1239         zl = createList();
1240         p = ziplistIndex(zl,0);
1241         while (ziplistGet(p,&entry,&elen,&value)) {
1242             if (entry && strncmp("foo",(char*)entry,elen) == 0) {
1243                 printf("Delete foo\n");
1244                 zl = ziplistDelete(zl,&p);
1245             } else {
1246                 printf("Entry: ");
1247                 if (entry) {
1248                     if (elen && fwrite(entry,elen,1,stdout) == 0)
1249                         perror("fwrite");
1250                 } else {
1251                     printf("%lld",value);
1252                 }
1253                 p = ziplistNext(zl,p);
1254                 printf("\n");
1255             }
1256         }
1257         printf("\n");
1258         ziplistRepr(zl);
1259     }
1260
1261     printf("Regression test for >255 byte strings:\n");
1262     {
1263         char v1[257],v2[257];
1264         memset(v1,'x',256);
1265         memset(v2,'y',256);
1266         zl = ziplistNew();
1267         zl = ziplistPush(zl,(unsigned char*)v1,strlen(v1),ZIPLIST_TAIL);
1268         zl = ziplistPush(zl,(unsigned char*)v2,strlen(v2),ZIPLIST_TAIL);
1269
1270         /* Pop values again and compare their value. */
1271         p = ziplistIndex(zl,0);
1272         assert(ziplistGet(p,&entry,&elen,&value));
1273         assert(strncmp(v1,(char*)entry,elen) == 0);
1274         p = ziplistIndex(zl,1);
1275         assert(ziplistGet(p,&entry,&elen,&value));
1276         assert(strncmp(v2,(char*)entry,elen) == 0);
1277         printf("SUCCESS\n\n");
1278     }
1279
1280     printf("Create long list and check indices:\n");
1281     {
1282         zl = ziplistNew();
1283         char buf[32];
1284         int i,len;
1285         for (i = 0; i < 1000; i++) {
1286             len = sprintf(buf,"%d",i);
1287             zl = ziplistPush(zl,(unsigned char*)buf,len,ZIPLIST_TAIL);
1288         }
1289         for (i = 0; i < 1000; i++) {
1290             p = ziplistIndex(zl,i);
1291             assert(ziplistGet(p,NULL,NULL,&value));
1292             assert(i == value);
1293
1294             p = ziplistIndex(zl,-i-1);
1295             assert(ziplistGet(p,NULL,NULL,&value));
1296             assert(999-i == value);
1297         }
1298         printf("SUCCESS\n\n");
1299     }
1300
1301     printf("Compare strings with ziplist entries:\n");
1302     {
1303         zl = createList();
1304         p = ziplistIndex(zl,0);
1305         if (!ziplistCompare(p,(unsigned char*)"hello",5)) {
1306             printf("ERROR: not \"hello\"\n");
1307             return 1;
1308         }
1309         if (ziplistCompare(p,(unsigned char*)"hella",5)) {
1310             printf("ERROR: \"hella\"\n");
1311             return 1;
1312         }
1313
1314         p = ziplistIndex(zl,3);
1315         if (!ziplistCompare(p,(unsigned char*)"1024",4)) {
1316             printf("ERROR: not \"1024\"\n");
1317             return 1;
1318         }
1319         if (ziplistCompare(p,(unsigned char*)"1025",4)) {
1320             printf("ERROR: \"1025\"\n");
1321             return 1;
1322         }
1323         printf("SUCCESS\n\n");
1324     }
1325
1326     printf("Stress with random payloads of different encoding:\n");
1327     {
1328         int i,j,len,where;
1329         unsigned char *p;
1330         char buf[1024];
1331         int buflen;
1332         list *ref;
1333         listNode *refnode;
1334
1335         /* Hold temp vars from ziplist */
1336         unsigned char *sstr;
1337         unsigned int slen;
1338         long long sval;
1339
1340         for (i = 0; i < 20000; i++) {
1341             zl = ziplistNew();
1342             ref = listCreate();
1343             listSetFreeMethod(ref,sdsfree);
1344             len = rand() % 256;
1345
1346             /* Create lists */
1347             for (j = 0; j < len; j++) {
1348                 where = (rand() & 1) ? ZIPLIST_HEAD : ZIPLIST_TAIL;
1349                 if (rand() % 2) {
1350                     buflen = randstring(buf,1,sizeof(buf)-1);
1351                 } else {
1352                     switch(rand() % 3) {
1353                     case 0:
1354                         buflen = sprintf(buf,"%lld",(0LL + rand()) >> 20);
1355                         break;
1356                     case 1:
1357                         buflen = sprintf(buf,"%lld",(0LL + rand()));
1358                         break;
1359                     case 2:
1360                         buflen = sprintf(buf,"%lld",(0LL + rand())