text: #include <stdio.h>
  #include <stdlib.h>
  #include <string.h>
  #include <stdint.h>
  #include <limits.h>
  #include "zmalloc.h"
  #include "util.h"
  #include "ziplist.h"
  #include "endianconv.h"
  #include "redisassert.h"
  
  #define ZIP_END 255         /* Special "end of ziplist" entry. */
  #define ZIP_BIG_PREVLEN 254 /* Max number of bytes of the previous entry, for
                                 the "prevlen" field prefixing each entry, to be
                                 represented with just a single byte. Otherwise
                                 it is represented as FF AA BB CC DD, where
                                 AA BB CC DD are a 4 bytes unsigned integer
                                 representing the previous entry len. */
  
  // 字符串和整数的掩码
  #define ZIP_STR_MASK 0xc0
  #define ZIP_INT_MASK 0x30
  
  // 字符串
  #define ZIP_STR_06B (0 << 6)    // 1 bytes - 2B = 6B （前两个Bit为00，用后6个Bit记录<= 63 bytes 的字符串）
  #define ZIP_STR_14B (1 << 6)    // 2 bytes - 2B = 14B（前两个Bit为01，用后14个Bit记录<= 16383 bytes 的字符串）
  #define ZIP_STR_32B (2 << 6)    // 5 bytes - 2B - 6B （前两个Bit为01，后6个Bit没有意义，用后32个Bit记录<= 4294967295 bytes 的字符串）
  
  // 整数（如果节点保存的是整数值，那么其编码长度固定为1个字节，     前两个Bit为11，用于表示节点保存的是整数值。）
  #define ZIP_INT_16B (0xc0 | 0<<4)   // 11 000000（int16_t（2 bytes））
  #define ZIP_INT_32B (0xc0 | 1<<4)   // 11 010000（int32_t（4 bytes））
  #define ZIP_INT_64B (0xc0 | 2<<4)   // 11 100000（int64_t（8 bytes））
  #define ZIP_INT_24B (0xc0 | 3<<4)   // 11 110000（24位有符整数）
  #define ZIP_INT_8B 0xfe             // 11 111110（8位有符整数）
  
  // 当编码为1111xxxx时，表示没有内容部分，xxxx（4Bit）已经存放了当前的整数值，包括整数0~12，即xxxx可以表示0000~1101。
  // 编码为11111111代表ziplist的结尾。
  #define ZIP_INT_IMM_MASK 0x0f   /* Mask to extract the 4 bits value. To add
                                     one is needed to reconstruct the value. */
  #define ZIP_INT_IMM_MIN 0xf1    /* 11110001 */
  #define ZIP_INT_IMM_MAX 0xfd    /* 11111101 */
  
  #define INT24_MAX 0x7fffff
  #define INT24_MIN (-INT24_MAX - 1)
  
  // 计算encoding类型，是否为字符串，返回true或者false
  #define ZIP_IS_STR(enc) (((enc) & ZIP_STR_MASK) < ZIP_STR_MASK)
  
  /* Utility macros.*/
  
  // 返回ziplist整体长度
  #define ZIPLIST_BYTES(zl)       (*((uint32_t*)(zl)))
  
  // 取出头尾偏移
  #define ZIPLIST_TAIL_OFFSET(zl) (*((uint32_t*)((zl)+sizeof(uint32_t))))
  
  // 取出zipliest中节点个数
  #define ZIPLIST_LENGTH(zl)      (*((uint16_t*)((zl)+sizeof(uint32_t)*2)))
  
  // ziplist头长度
  #define ZIPLIST_HEADER_SIZE     (sizeof(uint32_t)*2+sizeof(uint16_t))
  
  // ziplist尾长度
  #define ZIPLIST_END_SIZE        (sizeof(uint8_t))
  
  // 返回ziplist跳过头信息的第一个节点位置
  #define ZIPLIST_ENTRY_HEAD(zl)  ((zl)+ZIPLIST_HEADER_SIZE)
  
  // 返回ziplist最后一个节点位置
  #define ZIPLIST_ENTRY_TAIL(zl)  ((zl)+intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl)))
  
  // 返回ziplist尾部位置
  #define ZIPLIST_ENTRY_END(zl)   ((zl)+intrev32ifbe(ZIPLIST_BYTES(zl))-1)
  
  /* Increment the number of items field in the ziplist header. Note that this
   * macro should never overflow the unsigned 16 bit integer, since entires are
   * always pushed one at a time. When UINT16_MAX is reached we want the count
   * to stay there to signal that a full scan is needed to get the number of
   * items inside the ziplist. */
  #define ZIPLIST_INCR_LENGTH(zl,incr) { \
      if (ZIPLIST_LENGTH(zl) < UINT16_MAX) \
          ZIPLIST_LENGTH(zl) = intrev16ifbe(intrev16ifbe(ZIPLIST_LENGTH(zl))+incr); \
  }
  
  
  // 节点的数据结构定义
  // 很显然，内存上不能直接存放结构体，于是，Redis提供了一系列的编码和解码操作函数。这里以编码前置节点长度和解码前置节点长度
  typedef struct zlentry {
      unsigned int prevrawlensize; // 前置节点长度和编码所需长度
      unsigned int prevrawlen;
  
      unsigned int lensize;        // 当前节点长度和编码所需长度
      unsigned int len;
  
      unsigned int headersize;     // 头的大小（ prevrawlensize + lensize. ）
  
      unsigned char encoding;      // 编码类型
      unsigned char *p;            // 数据部分
  } zlentry;
  
  #define ZIPLIST_ENTRY_ZERO(zle) { \
      (zle)->prevrawlensize = (zle)->prevrawlen = 0; \
      (zle)->lensize = (zle)->len = (zle)->headersize = 0; \
      (zle)->encoding = 0; \
      (zle)->p = NULL; \
  }
  
  /* Extract the encoding from the byte pointed by 'ptr' and set it into
   * 'encoding' field of the zlentry structure. */
  #define ZIP_ENTRY_ENCODING(ptr, encoding) do {  \
      (encoding) = (ptr[0]); \
      if ((encoding) < ZIP_STR_MASK) (encoding) &= ZIP_STR_MASK; \
  } while(0)
  
  /* Return bytes needed to store integer encoded by 'encoding'. */
  unsigned int zipIntSize(unsigned char encoding) {
      switch(encoding) {
      case ZIP_INT_8B:  return 1;
      case ZIP_INT_16B: return 2;
      case ZIP_INT_24B: return 3;
      case ZIP_INT_32B: return 4;
      case ZIP_INT_64B: return 8;
      }
      if (encoding >= ZIP_INT_IMM_MIN && encoding <= ZIP_INT_IMM_MAX)
          return 0; /* 4 bit immediate */
      panic("Invalid integer encoding 0x%02X", encoding);
      return 0;
  }
  
  /* Write the encoidng header of the entry in 'p'. If p is NULL it just returns
   * the amount of bytes required to encode such a length. Arguments:
   *
   * 'encoding' is the encoding we are using for the entry. It could be
   * ZIP_INT_* or ZIP_STR_* or between ZIP_INT_IMM_MIN and ZIP_INT_IMM_MAX
   * for single-byte small immediate integers.
   *
   * 'rawlen' is only used for ZIP_STR_* encodings and is the length of the
   * srting that this entry represents.
   *
   * The function returns the number of bytes used by the encoding/length
   * header stored in 'p'. */
  unsigned int zipStoreEntryEncoding(unsigned char *p, unsigned char encoding, unsigned int rawlen) {
      unsigned char len = 1, buf[5];
  
      if (ZIP_IS_STR(encoding)) {
          /* Although encoding is given it may not be set for strings,
           * so we determine it here using the raw length. */
          if (rawlen <= 0x3f) {
              if (!p) return len;
              buf[0] = ZIP_STR_06B | rawlen;
          } else if (rawlen <= 0x3fff) {
              len += 1;
              if (!p) return len;
              buf[0] = ZIP_STR_14B | ((rawlen >> 8) & 0x3f);
              buf[1] = rawlen & 0xff;
          } else {
              len += 4;
              if (!p) return len;
              buf[0] = ZIP_STR_32B;
              buf[1] = (rawlen >> 24) & 0xff;
              buf[2] = (rawlen >> 16) & 0xff;
              buf[3] = (rawlen >> 8) & 0xff;
              buf[4] = rawlen & 0xff;
          }
      } else {
          /* Implies integer encoding, so length is always 1. */
          if (!p) return len;
          buf[0] = encoding;
      }
  
      /* Store this length at p. */
      memcpy(p,buf,len);
      return len;
  }
  
  /* Decode the entry encoding type and data length (string length for strings,
   * number of bytes used for the integer for integer entries) encoded in 'ptr'.
   * The 'encoding' variable will hold the entry encoding, the 'lensize'
   * variable will hold the number of bytes required to encode the entry
   * length, and the 'len' variable will hold the entry length. */
  #define ZIP_DECODE_LENGTH(ptr, encoding, lensize, len) do {                    \
      ZIP_ENTRY_ENCODING((ptr), (encoding));                                     \
      if ((encoding) < ZIP_STR_MASK) {                                           \
          if ((encoding) == ZIP_STR_06B) {                                       \
              (lensize) = 1;                                                     \
              (len) = (ptr)[0] & 0x3f;                                           \
          } else if ((encoding) == ZIP_STR_14B) {                                \
              (lensize) = 2;                                                     \
              (len) = (((ptr)[0] & 0x3f) << 8) | (ptr)[1];                       \
          } else if ((encoding) == ZIP_STR_32B) {                                \
              (lensize) = 5;                                                     \
              (len) = ((ptr)[1] << 24) |                                         \
                      ((ptr)[2] << 16) |                                         \
                      ((ptr)[3] <<  8) |                                         \
                      ((ptr)[4]);                                                \
          } else {                                                               \
              panic("Invalid string encoding 0x%02X", (encoding));               \
          }                                                                      \
      } else {                                                                   \
          (lensize) = 1;                                                         \
          (len) = zipIntSize(encoding);                                          \
      }                                                                          \
  } while(0);
  
  // 编码前一个节点长度 >254使用5bytes保存的情况
  int zipStorePrevEntryLengthLarge(unsigned char *p, unsigned int len) {
      if (p != NULL) {
          p[0] = ZIP_BIG_PREVLEN;
          memcpy(p+1,&len,sizeof(len));
          memrev32ifbe(p+1);
      }
      return 1+sizeof(len);
  }
  
  // 编码前一个节点，将其长度保存并返回需要几个bytes保存
  unsigned int zipStorePrevEntryLength(unsigned char *p, unsigned int len) {
      if (p == NULL) {
          return (len < ZIP_BIG_PREVLEN) ? 1 : sizeof(len)+1;
      } else {
          if (len < ZIP_BIG_PREVLEN) {// < 254    用1bytes编码
              p[0] = len;
              return 1;
          } else {                    // > 254    用5bytes编码
              return zipStorePrevEntryLengthLarge(p,len);
          }
      }
  }
  
  // 解码前一个节点的长度需要用几个bytes保存
  #define ZIP_DECODE_PREVLENSIZE(ptr, prevlensize) do {                          \
      if ((ptr)[0] < ZIP_BIG_PREVLEN) {                                          \
          (prevlensize) = 1;                                                     \
      } else {                                                                   \
          (prevlensize) = 5;                                                     \
      }                                                                          \
  } while(0);
  
  // 解码出来前一个节点的真实长度
  #define ZIP_DECODE_PREVLEN(ptr, prevlensize, prevlen) do {                     \
      ZIP_DECODE_PREVLENSIZE(ptr, prevlensize);                                  \
      if ((prevlensize) == 1) {                                                  \
          (prevlen) = (ptr)[0];                                                  \
      } else if ((prevlensize) == 5) {                                           \
          assert(sizeof((prevlensize)) == 4);                                    \
          memcpy(&(prevlen), ((char*)(ptr)) + 1, 4);                             \
          memrev32ifbe(&prevlen);                                                \
      }                                                                          \
  } while(0);
  
  /* Given a pointer 'p' to the prevlen info that prefixes an entry, this
   * function returns the difference in number of bytes needed to encode
   * the prevlen if the previous entry changes of size.
   *
   * So if A is the number of bytes used right now to encode the 'prevlen'
   * field.
   *
   * And B is the number of bytes that are needed in order to encode the
   * 'prevlen' if the previous element will be updated to one of size 'len'.
   *
   * Then the function returns B - A
   *
   * So the function returns a positive number if more space is needed,
   * a negative number if less space is needed, or zero if the same space
   * is needed. */
  int zipPrevLenByteDiff(unsigned char *p, unsigned int len) {
      unsigned int prevlensize;
      ZIP_DECODE_PREVLENSIZE(p, prevlensize);
      return zipStorePrevEntryLength(NULL, len) - prevlensize;
  }
  
  /* Return the total number of bytes used by the entry pointed to by 'p'. */
  unsigned int zipRawEntryLength(unsigned char *p) {
      unsigned int prevlensize, encoding, lensize, len;
      ZIP_DECODE_PREVLENSIZE(p, prevlensize);
      ZIP_DECODE_LENGTH(p + prevlensize, encoding, lensize, len);
      return prevlensize + lensize + len;
  }
  
  // 试图编码为int类型
  int zipTryEncoding(unsigned char *entry, unsigned int entrylen, long long *v, unsigned char *encoding) {
      long long value;
  
      if (entrylen >= 32 || entrylen == 0) return 0;                      // 如果字符串长度>=32或=0 就不能编码为int
      if (string2ll((char*)entry,entrylen,&value)) {                      // 字符串转int
          if (value >= 0 && value <= 12) {// 0<=val<=12
              *encoding = ZIP_INT_IMM_MIN+value;                          //
          } else if (value >= INT8_MIN && value <= INT8_MAX) {
              *encoding = ZIP_INT_8B;
          } else if (value >= INT16_MIN && value <= INT16_MAX) {
              *encoding = ZIP_INT_16B;
          } else if (value >= INT24_MIN && value <= INT24_MAX) {
              *encoding = ZIP_INT_24B;
          } else if (value >= INT32_MIN && value <= INT32_MAX) {
              *encoding = ZIP_INT_32B;
          } else {
              *encoding = ZIP_INT_64B;
          }
          *v = value;
          return 1;
      }
      return 0;
  }
  
  /* Store integer 'value' at 'p', encoded as 'encoding' */
  void zipSaveInteger(unsigned char *p, int64_t value, unsigned char encoding) {
      int16_t i16;
      int32_t i32;
      int64_t i64;
      if (encoding == ZIP_INT_8B) {
          ((int8_t*)p)[0] = (int8_t)value;
      } else if (encoding == ZIP_INT_16B) {
          i16 = value;
          memcpy(p,&i16,sizeof(i16));
          memrev16ifbe(p);
      } else if (encoding == ZIP_INT_24B) {
          i32 = value<<8;
          memrev32ifbe(&i32);
          memcpy(p,((uint8_t*)&i32)+1,sizeof(i32)-sizeof(uint8_t));
      } else if (encoding == ZIP_INT_32B) {
          i32 = value;
          memcpy(p,&i32,sizeof(i32));
          memrev32ifbe(p);
      } else if (encoding == ZIP_INT_64B) {
          i64 = value;
          memcpy(p,&i64,sizeof(i64));
          memrev64ifbe(p);
      } else if (encoding >= ZIP_INT_IMM_MIN && encoding <= ZIP_INT_IMM_MAX) {
          /* Nothing to do, the value is stored in the encoding itself. */
      } else {
          assert(NULL);
      }
  }
  
  /* Read integer encoded as 'encoding' from 'p' */
  int64_t zipLoadInteger(unsigned char *p, unsigned char encoding) {
      int16_t i16;
      int32_t i32;
      int64_t i64, ret = 0;
      if (encoding == ZIP_INT_8B) {
          ret = ((int8_t*)p)[0];
      } else if (encoding == ZIP_INT_16B) {
          memcpy(&i16,p,sizeof(i16));
          memrev16ifbe(&i16);
          ret = i16;
      } else if (encoding == ZIP_INT_32B) {
          memcpy(&i32,p,sizeof(i32));
          memrev32ifbe(&i32);
          ret = i32;
      } else if (encoding == ZIP_INT_24B) {
          i32 = 0;
          memcpy(((uint8_t*)&i32)+1,p,sizeof(i32)-sizeof(uint8_t));
          memrev32ifbe(&i32);
          ret = i32>>8;
      } else if (encoding == ZIP_INT_64B) {
          memcpy(&i64,p,sizeof(i64));
          memrev64ifbe(&i64);
          ret = i64;
      } else if (encoding >= ZIP_INT_IMM_MIN && encoding <= ZIP_INT_IMM_MAX) {
          ret = (encoding & ZIP_INT_IMM_MASK)-1;
      } else {
          assert(NULL);
      }
      return ret;
  }
  
  /* Return a struct with all information about an entry. */
  void zipEntry(unsigned char *p, zlentry *e) {
  
      ZIP_DECODE_PREVLEN(p, e->prevrawlensize, e->prevrawlen);
      ZIP_DECODE_LENGTH(p + e->prevrawlensize, e->encoding, e->lensize, e->len);
      e->headersize = e->prevrawlensize + e->lensize;
      e->p = p;
  }
  
  // 创建空ziplist
  unsigned char *ziplistNew(void) {
      // 空ziplist的大小为11个字节，头部10字节，尾部1字节
      // zlbytes：表示压缩列表占总内存的字节数  （uint32_t）
      // zltail：表示压缩列表头和尾之间的偏移量  （uint32_t）
      // zllen：表示压缩列表中节点的数量        （uint16_t）
      unsigned int bytes = ZIPLIST_HEADER_SIZE+1;                     // 11 bytes
      unsigned char *zl = zmalloc(bytes);                             // 分配内存
  
      // 设定ziplist的属性
      ZIPLIST_BYTES(zl) = intrev32ifbe(bytes);                        // 设定ziplist所占的字节数（设置zlbytes）
      ZIPLIST_TAIL_OFFSET(zl) = intrev32ifbe(ZIPLIST_HEADER_SIZE);    // 设定ziplist的偏移量（设置zltail）
      ZIPLIST_LENGTH(zl) = 0;                                         // 设定ziplist内的节点数（设置zllen）
      zl[bytes-1] = ZIP_END;                                          // 设定尾部一个字节位0xFF
      return zl;
  }
  
  /* Resize the ziplist. */
  unsigned char *ziplistResize(unsigned char *zl, unsigned int len) {
      zl = zrealloc(zl,len);
      ZIPLIST_BYTES(zl) = intrev32ifbe(len);
      zl[len-1] = ZIP_END;
      return zl;
  }
  
  /* When an entry is inserted, we need to set the prevlen field of the next
   * entry to equal the length of the inserted entry. It can occur that this
   * length cannot be encoded in 1 byte and the next entry needs to be grow
   * a bit larger to hold the 5-byte encoded prevlen. This can be done for free,
   * because this only happens when an entry is already being inserted (which
   * causes a realloc and memmove). However, encoding the prevlen may require
   * that this entry is grown as well. This effect may cascade throughout
   * the ziplist when there are consecutive entries with a size close to
   * ZIP_BIG_PREVLEN, so we need to check that the prevlen can be encoded in
   * every consecutive entry.
   *
   * Note that this effect can also happen in reverse, where the bytes required
   * to encode the prevlen field can shrink. This effect is deliberately ignored,
   * because it can cause a "flapping" effect where a chain prevlen fields is
   * first grown and then shrunk again after consecutive inserts. Rather, the
   * field is allowed to stay larger than necessary, because a large prevlen
   * field implies the ziplist is holding large entries anyway.
   *
   * The pointer "p" points to the first entry that does NOT need to be
   * updated, i.e. consecutive fields MAY need an update. */
  unsigned char *__ziplistCascadeUpdate(unsigned char *zl, unsigned char *p) {
      size_t curlen = intrev32ifbe(ZIPLIST_BYTES(zl)), rawlen, rawlensize;
      size_t offset, noffset, extra;
      unsigned char *np;
      zlentry cur, next;
  
      while (p[0] != ZIP_END) {
          zipEntry(p, &cur);
          rawlen = cur.headersize + cur.len;
          rawlensize = zipStorePrevEntryLength(NULL,rawlen);
  
          /* Abort if there is no next entry. */
          if (p[rawlen] == ZIP_END) break;
          zipEntry(p+rawlen, &next);
  
          /* Abort when "prevlen" has not changed. */
          if (next.prevrawlen == rawlen) break;
  
          if (next.prevrawlensize < rawlensize) {
              /* The "prevlen" field of "next" needs more bytes to hold
               * the raw length of "cur". */
              offset = p-zl;
              extra = rawlensize-next.prevrawlensize;
              zl = ziplistResize(zl,curlen+extra);
              p = zl+offset;
  
              /* Current pointer and offset for next element. */
              np = p+rawlen;
              noffset = np-zl;
  
              /* Update tail offset when next element is not the tail element. */
              if ((zl+intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))) != np) {
                  ZIPLIST_TAIL_OFFSET(zl) =
                      intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))+extra);
              }
  
              /* Move the tail to the back. */
              memmove(np+rawlensize,
                  np+next.prevrawlensize,
                  curlen-noffset-next.prevrawlensize-1);
              zipStorePrevEntryLength(np,rawlen);
  
              /* Advance the cursor */
              p += rawlen;
              curlen += extra;
          } else {
              if (next.prevrawlensize > rawlensize) {
                  /* This would result in shrinking, which we want to avoid.
                   * So, set "rawlen" in the available bytes. */
                  zipStorePrevEntryLengthLarge(p+rawlen,rawlen);
              } else {
                  zipStorePrevEntryLength(p+rawlen,rawlen);
              }
  
              /* Stop here, as the raw length of "next" has not changed. */
              break;
          }
      }
      return zl;
  }
  
  /* Delete "num" entries, starting at "p". Returns pointer to the ziplist. */
  unsigned char *__ziplistDelete(unsigned char *zl, unsigned char *p, unsigned int num) {
      unsigned int i, totlen, deleted = 0;
      size_t offset;
      int nextdiff = 0;
      zlentry first, tail;
  
      zipEntry(p, &first);
      for (i = 0; p[0] != ZIP_END && i < num; i++) {
          p += zipRawEntryLength(p);
          deleted++;
      }
  
      totlen = p-first.p; /* Bytes taken by the element(s) to delete. */
      if (totlen > 0) {
          if (p[0] != ZIP_END) {
              /* Storing `prevrawlen` in this entry may increase or decrease the
               * number of bytes required compare to the current `prevrawlen`.
               * There always is room to store this, because it was previously
               * stored by an entry that is now being deleted. */
              nextdiff = zipPrevLenByteDiff(p,first.prevrawlen);
  
              /* Note that there is always space when p jumps backward: if
               * the new previous entry is large, one of the deleted elements
               * had a 5 bytes prevlen header, so there is for sure at least
               * 5 bytes free and we need just 4. */
              p -= nextdiff;
              zipStorePrevEntryLength(p,first.prevrawlen);
  
              /* Update offset for tail */
              ZIPLIST_TAIL_OFFSET(zl) =
                  intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))-totlen);
  
              /* When the tail contains more than one entry, we need to take
               * "nextdiff" in account as well. Otherwise, a change in the
               * size of prevlen doesn't have an effect on the *tail* offset. */
              zipEntry(p, &tail);
              if (p[tail.headersize+tail.len] != ZIP_END) {
                  ZIPLIST_TAIL_OFFSET(zl) =
                     intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))+nextdiff);
              }
  
              /* Move tail to the front of the ziplist */
              memmove(first.p,p,
                  intrev32ifbe(ZIPLIST_BYTES(zl))-(p-zl)-1);
          } else {
              /* The entire tail was deleted. No need to move memory. */
              ZIPLIST_TAIL_OFFSET(zl) =
                  intrev32ifbe((first.p-zl)-first.prevrawlen);
          }
  
          /* Resize and update length */
          offset = first.p-zl;
          zl = ziplistResize(zl, intrev32ifbe(ZIPLIST_BYTES(zl))-totlen+nextdiff);
          ZIPLIST_INCR_LENGTH(zl,-deleted);
          p = zl+offset;
  
          /* When nextdiff != 0, the raw length of the next entry has changed, so
           * we need to cascade the update throughout the ziplist */
          if (nextdiff != 0)
              zl = __ziplistCascadeUpdate(zl,p);
      }
      return zl;
  }
  
  // 在p的位置上插入元素
  unsigned char *__ziplistInsert(unsigned char *zl, unsigned char *p, unsigned char *s, unsigned int slen) {
      size_t curlen = intrev32ifbe(ZIPLIST_BYTES(zl)), reqlen;    // 当前长度和插入节点后需要的长度
      unsigned int prevlensize, prevlen = 0;                        // 前置节点长度和编码该长度值所需的长度
      size_t offset;
      int nextdiff = 0;
      unsigned char encoding = 0;
      long long value = 123456789;                                  // 为了避免警告，初始化其值
      zlentry tail;
  
      // 找出待插入节点的前置节点长度
      if (p[0] != ZIP_END) {// 如果p[0]不指向列表末端，说明列表非空，并且p指向其中一个节点
          ZIP_DECODE_PREVLEN(p, prevlensize, prevlen);            // 解码前置节点p的长度和编码该长度需要的字节
      } else {// 如果p指向列表末端，表示列表为空
          unsigned char *ptail = ZIPLIST_ENTRY_TAIL(zl);
          if (ptail[0] != ZIP_END) {
              prevlen = zipRawEntryLength(ptail);                 // 计算尾节点的长度
          }
      }
  
      // 判断是否能够编码为整数
      if (zipTryEncoding(s,slen,&value,&encoding)) {
          reqlen = zipIntSize(encoding);                         // 该节点已经编码为整数，通过encoding来获取编码长度
      } else {
          reqlen = slen;                                         // 采用字符串来编码该节点
      }
  
      reqlen += zipStorePrevEntryLength(NULL,prevlen);        // 加上前置节点的编码长度 加入第一个节点时(+1)
      reqlen += zipStoreEntryEncoding(NULL,encoding,slen);    // 加上当前节点的编码长度 加入第一个节点时(int +1)
  
      // 只要不是插入到列表的末端，都需要判断当前p所指向的节点header是否能存放新节点的长度编码
      // nextdiff保存新旧编码之间的字节大小差，如果这个值大于0
      // 那就说明当前p指向的节点的header进行扩展
      int forcelarge = 0;
      nextdiff = (p[0] != ZIP_END) ? zipPrevLenByteDiff(p,reqlen) : 0;
      if (nextdiff == -4 && reqlen < 4) {
          nextdiff = 0;
          forcelarge = 1;
      }
  
      // 存储p相对于列表zl的偏移地址
      offset = p-zl;
  
      // 重新分配空间，curlen当前列表的长度
      // reqlen 新节点的全部长度
      // nextdiff 新节点的后继节点扩展header的长度
      zl = ziplistResize(zl,curlen+reqlen+nextdiff);
  
      // 重新获取p的值
      p = zl+offset;
  
  
      if (p[0] != ZIP_END) {// 非表尾插入，需要重新计算表尾的偏移量
          memmove(p+reqlen,p-nextdiff,curlen-offset-1+nextdiff);              // 移动现有元素，为新元素的插入提供空间
  
          /* Encode this entry's raw length in the next entry. */
          if (forcelarge)
              zipStorePrevEntryLengthLarge(p+reqlen,reqlen);
          else
              zipStorePrevEntryLength(p+reqlen,reqlen);
  
          /* Update offset for tail */
          ZIPLIST_TAIL_OFFSET(zl) =
              intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))+reqlen);
  
          /* When the tail contains more than one entry, we need to take
           * "nextdiff" in account as well. Otherwise, a change in the
           * size of prevlen doesn't have an effect on the *tail* offset. */
          zipEntry(p+reqlen, &tail);
          if (p[reqlen+tail.headersize+tail.len] != ZIP_END) {
              ZIPLIST_TAIL_OFFSET(zl) =
                  intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))+nextdiff);
          }
      } else {// 表尾插入，直接计算偏移量
          /* This element will be the new tail. */
          ZIPLIST_TAIL_OFFSET(zl) = intrev32ifbe(p-zl);
      }
  
      /* When nextdiff != 0, the raw length of the next entry has changed, so
       * we need to cascade the update throughout the ziplist */
      if (nextdiff != 0) {
          offset = p-zl;
          zl = __ziplistCascadeUpdate(zl,p+reqlen);
          p = zl+offset;
      }
  
      /* Write the entry */
      p += zipStorePrevEntryLength(p,prevlen);
      p += zipStoreEntryEncoding(p,encoding,slen);
      if (ZIP_IS_STR(encoding)) {
          memcpy(p,s,slen);
      } else {
          zipSaveInteger(p,value,encoding);
      }
      ZIPLIST_INCR_LENGTH(zl,1);
      return zl;
  }
  
  /* Merge ziplists 'first' and 'second' by appending 'second' to 'first'.
   *
   * NOTE: The larger ziplist is reallocated to contain the new merged ziplist.
   * Either 'first' or 'second' can be used for the result.  The parameter not
   * used will be free'd and set to NULL.
   *
   * After calling this function, the input parameters are no longer valid since
   * they are changed and free'd in-place.
   *
   * The result ziplist is the contents of 'first' followed by 'second'.
   *
   * On failure: returns NULL if the merge is impossible.
   * On success: returns the merged ziplist (which is expanded version of either
   * 'first' or 'second', also frees the other unused input ziplist, and sets the
   * input ziplist argument equal to newly reallocated ziplist return value. */
  unsigned char *ziplistMerge(unsigned char **first, unsigned char **second) {
      /* If any params are null, we can't merge, so NULL. */
      if (first == NULL || *first == NULL || second == NULL || *second == NULL)
          return NULL;
  
      /* Can't merge same list into itself. */
      if (*first == *second)
          return NULL;
  
      size_t first_bytes = intrev32ifbe(ZIPLIST_BYTES(*first));
      size_t first_len = intrev16ifbe(ZIPLIST_LENGTH(*first));
  
      size_t second_bytes = intrev32ifbe(ZIPLIST_BYTES(*second));
      size_t second_len = intrev16ifbe(ZIPLIST_LENGTH(*second));
  
      int append;
      unsigned char *source, *target;
      size_t target_bytes, source_bytes;
      /* Pick the largest ziplist so we can resize easily in-place.
       * We must also track if we are now appending or prepending to
       * the target ziplist. */
      if (first_len >= second_len) {
          /* retain first, append second to first. */
          target = *first;
          target_bytes = first_bytes;
          source = *second;
          source_bytes = second_bytes;
          append = 1;
      } else {
          /* else, retain second, prepend first to second. */
          target = *second;
          target_bytes = second_bytes;
          source = *first;
          source_bytes = first_bytes;
          append = 0;
      }
  
      /* Calculate final bytes (subtract one pair of metadata) */
      size_t zlbytes = first_bytes + second_bytes -
                       ZIPLIST_HEADER_SIZE - ZIPLIST_END_SIZE;
      size_t zllength = first_len + second_len;
  
      /* Combined zl length should be limited within UINT16_MAX */
      zllength = zllength < UINT16_MAX ? zllength : UINT16_MAX;
  
      /* Save offset positions before we start ripping memory apart. */
      size_t first_offset = intrev32ifbe(ZIPLIST_TAIL_OFFSET(*first));
      size_t second_offset = intrev32ifbe(ZIPLIST_TAIL_OFFSET(*second));
  
      /* Extend target to new zlbytes then append or prepend source. */
      target = zrealloc(target, zlbytes);
      if (append) {
          /* append == appending to target */
          /* Copy source after target (copying over original [END]):
           *   [TARGET - END, SOURCE - HEADER] */
          memcpy(target + target_bytes - ZIPLIST_END_SIZE,
                 source + ZIPLIST_HEADER_SIZE,
                 source_bytes - ZIPLIST_HEADER_SIZE);
      } else {
          /* !append == prepending to target */
          /* Move target *contents* exactly size of (source - [END]),
           * then copy source into vacataed space (source - [END]):
           *   [SOURCE - END, TARGET - HEADER] */
          memmove(target + source_bytes - ZIPLIST_END_SIZE,
                  target + ZIPLIST_HEADER_SIZE,
                  target_bytes - ZIPLIST_HEADER_SIZE);
          memcpy(target, source, source_bytes - ZIPLIST_END_SIZE);
      }
  
      /* Update header metadata. */
      ZIPLIST_BYTES(target) = intrev32ifbe(zlbytes);
      ZIPLIST_LENGTH(target) = intrev16ifbe(zllength);
      /* New tail offset is:
       *   + N bytes of first ziplist
       *   - 1 byte for [END] of first ziplist
       *   + M bytes for the offset of the original tail of the second ziplist
       *   - J bytes for HEADER because second_offset keeps no header. */
      ZIPLIST_TAIL_OFFSET(target) = intrev32ifbe(
                                     (first_bytes - ZIPLIST_END_SIZE) +
                                     (second_offset - ZIPLIST_HEADER_SIZE));
  
      /* __ziplistCascadeUpdate just fixes the prev length values until it finds a
       * correct prev length value (then it assumes the rest of the list is okay).
       * We tell CascadeUpdate to start at the first ziplist's tail element to fix
       * the merge seam. */
      target = __ziplistCascadeUpdate(target, target+first_offset);
  
      /* Now free and NULL out what we didn't realloc */
      if (append) {
          zfree(*second);
          *second = NULL;
          *first = target;
      } else {
          zfree(*first);
          *first = NULL;
          *second = target;
      }
      return target;
  }
  
  // ziplist中插入节点
  // ziplist插入节点只能往头或者尾部插入
  // zl: 待插入的ziplist
  // s，slen: 待插入节点和其长度
  // where: 待插入的位置，0代表头部插入，1代表尾部插入
  unsigned char *ziplistPush(unsigned char *zl, unsigned char *s, unsigned int slen, int where) {
      unsigned char *p;
  
      // 如果是从头部插入：p返回的是zl+ZIPLIST_HEADER_SIZE的地址
      // 如果是从尾部插入：p返回的是zl+(zl前四个字节中存储的值zlbytes)-1 （-1是要去掉尾部的一个字节）
      // p是要插入的头部地址或尾部地址
      p = (where == ZIPLIST_HEAD) ? ZIPLIST_ENTRY_HEAD(zl) : ZIPLIST_ENTRY_END(zl);
      return __ziplistInsert(zl,p,s,slen);
  }
  
  /* Returns an offset to use for iterating with ziplistNext. When the given
   * index is negative, the list is traversed back to front. When the list
   * doesn't contain an element at the provided index, NULL is returned. */
  unsigned char *ziplistIndex(unsigned char *zl, int index) {
      unsigned char *p;
      unsigned int prevlensize, prevlen = 0;
      if (index < 0) {
          index = (-index)-1;
          p = ZIPLIST_ENTRY_TAIL(zl);
          if (p[0] != ZIP_END) {
              ZIP_DECODE_PREVLEN(p, prevlensize, prevlen);
              while (prevlen > 0 && index--) {
                  p -= prevlen;
                  ZIP_DECODE_PREVLEN(p, prevlensize, prevlen);
              }
          }
      } else {
          p = ZIPLIST_ENTRY_HEAD(zl);
          while (p[0] != ZIP_END && index--) {
              p += zipRawEntryLength(p);
          }
      }
      return (p[0] == ZIP_END || index > 0) ? NULL : p;
  }
  
  /* Return pointer to next entry in ziplist.
   *
   * zl is the pointer to the ziplist
   * p is the pointer to the current element
   *
   * The element after 'p' is returned, otherwise NULL if we are at the end. */
  unsigned char *ziplistNext(unsigned char *zl, unsigned char *p) {
      ((void) zl);
  
      /* "p" could be equal to ZIP_END, caused by ziplistDelete,
       * and we should return NULL. Otherwise, we should return NULL
       * when the *next* element is ZIP_END (there is no next entry). */
      if (p[0] == ZIP_END) {
          return NULL;
      }
  
      p += zipRawEntryLength(p);
      if (p[0] == ZIP_END) {
          return NULL;
      }
  
      return p;
  }
  
  /* Return pointer to previous entry in ziplist. */
  unsigned char *ziplistPrev(unsigned char *zl, unsigned char *p) {
      unsigned int prevlensize, prevlen = 0;
  
      /* Iterating backwards from ZIP_END should return the tail. When "p" is
       * equal to the first element of the list, we're already at the head,
       * and should return NULL. */
      if (p[0] == ZIP_END) {
          p = ZIPLIST_ENTRY_TAIL(zl);
          return (p[0] == ZIP_END) ? NULL : p;
      } else if (p == ZIPLIST_ENTRY_HEAD(zl)) {
          return NULL;
      } else {
          ZIP_DECODE_PREVLEN(p, prevlensize, prevlen);
          assert(prevlen > 0);
          return p-prevlen;
      }
  }
  
  /* Get entry pointed to by 'p' and store in either '*sstr' or 'sval' depending
   * on the encoding of the entry. '*sstr' is always set to NULL to be able
   * to find out whether the string pointer or the integer value was set.
   * Return 0 if 'p' points to the end of the ziplist, 1 otherwise. */
  unsigned int ziplistGet(unsigned char *p, unsigned char **sstr, unsigned int *slen, long long *sval) {
      zlentry entry;
      if (p == NULL || p[0] == ZIP_END) return 0;
      if (sstr) *sstr = NULL;
  
      zipEntry(p, &entry);
      if (ZIP_IS_STR(entry.encoding)) {
          if (sstr) {
              *slen = entry.len;
              *sstr = p+entry.headersize;
          }
      } else {
          if (sval) {
              *sval = zipLoadInteger(p+entry.headersize,entry.encoding);
          }
      }
      return 1;
  }
  
  /* Insert an entry at "p". */
  unsigned char *ziplistInsert(unsigned char *zl, unsigned char *p, unsigned char *s, unsigned int slen) {
      return __ziplistInsert(zl,p,s,slen);
  }
  
  /* Delete a single entry from the ziplist, pointed to by *p.
   * Also update *p in place, to be able to iterate over the
   * ziplist, while deleting entries. */
  unsigned char *ziplistDelete(unsigned char *zl, unsigned char **p) {
      size_t offset = *p-zl;
      zl = __ziplistDelete(zl,*p,1);
  
      /* Store pointer to current element in p, because ziplistDelete will
       * do a realloc which might result in a different "zl"-pointer.
       * When the delete direction is back to front, we might delete the last
       * entry and end up with "p" pointing to ZIP_END, so check this. */
      *p = zl+offset;
      return zl;
  }
  
  /* Delete a range of entries from the ziplist. */
  unsigned char *ziplistDeleteRange(unsigned char *zl, int index, unsigned int num) {
      unsigned char *p = ziplistIndex(zl,index);
      return (p == NULL) ? zl : __ziplistDelete(zl,p,num);
  }
  
  /* Compare entry pointer to by 'p' with 'sstr' of length 'slen'. */
  /* Return 1 if equal. */
  unsigned int ziplistCompare(unsigned char *p, unsigned char *sstr, unsigned int slen) {
      zlentry entry;
      unsigned char sencoding;
      long long zval, sval;
      if (p[0] == ZIP_END) return 0;
  
      zipEntry(p, &entry);
      if (ZIP_IS_STR(entry.encoding)) {
          /* Raw compare */
          if (entry.len == slen) {
              return memcmp(p+entry.headersize,sstr,slen) == 0;
          } else {
              return 0;
          }
      } else {
          /* Try to compare encoded values. Don't compare encoding because
           * different implementations may encoded integers differently. */
          if (zipTryEncoding(sstr,slen,&sval,&sencoding)) {
            zval = zipLoadInteger(p+entry.headersize,entry.encoding);
            return zval == sval;
          }
      }
      return 0;
  }
  
  /* Find pointer to the entry equal to the specified entry. Skip 'skip' entries
   * between every comparison. Returns NULL when the field could not be found. */
  unsigned char *ziplistFind(unsigned char *p, unsigned char *vstr, unsigned int vlen, unsigned int skip) {
      int skipcnt = 0;
      unsigned char vencoding = 0;
      long long vll = 0;
  
      while (p[0] != ZIP_END) {
          unsigned int prevlensize, encoding, lensize, len;
          unsigned char *q;
  
          ZIP_DECODE_PREVLENSIZE(p, prevlensize);
          ZIP_DECODE_LENGTH(p + prevlensize, encoding, lensize, len);
          q = p + prevlensize + lensize;
  
          if (skipcnt == 0) {
              /* Compare current entry with specified entry */
              if (ZIP_IS_STR(encoding)) {
                  if (len == vlen && memcmp(q, vstr, vlen) == 0) {
                      return p;
                  }
              } else {
                  /* Find out if the searched field can be encoded. Note that
                   * we do it only the first time, once done vencoding is set
                   * to non-zero and vll is set to the integer value. */
                  if (vencoding == 0) {
                      if (!zipTryEncoding(vstr, vlen, &vll, &vencoding)) {
                          /* If the entry can't be encoded we set it to
                           * UCHAR_MAX so that we don't retry again the next
                           * time. */
                          vencoding = UCHAR_MAX;
                      }
                      /* Must be non-zero by now */
                      assert(vencoding);
                  }
  
                  /* Compare current entry with specified entry, do it only
                   * if vencoding != UCHAR_MAX because if there is no encoding
                   * possible for the field it can't be a valid integer. */
                  if (vencoding != UCHAR_MAX) {
                      long long ll = zipLoadInteger(q, encoding);
                      if (ll == vll) {
                          return p;
                      }
                  }
              }
  
              /* Reset skip count */
              skipcnt = skip;
          } else {
              /* Skip entry */
              skipcnt--;
          }
  
          /* Move to next entry */
          p = q + len;
      }
  
      return NULL;
  }
  
  /* Return length of ziplist. */
  unsigned int ziplistLen(unsigned char *zl) {
      unsigned int len = 0;
      if (intrev16ifbe(ZIPLIST_LENGTH(zl)) < UINT16_MAX) {
          len = intrev16ifbe(ZIPLIST_LENGTH(zl));
      } else {
          unsigned char *p = zl+ZIPLIST_HEADER_SIZE;
          while (*p != ZIP_END) {
              p += zipRawEntryLength(p);
              len++;
          }
  
          /* Re-store length if small enough */
          if (len < UINT16_MAX) ZIPLIST_LENGTH(zl) = intrev16ifbe(len);
      }
      return len;
  }
  
  /* Return ziplist blob size in bytes. */
  size_t ziplistBlobLen(unsigned char *zl) {
      return intrev32ifbe(ZIPLIST_BYTES(zl));
  }
  
  void ziplistRepr(unsigned char *zl) {
      unsigned char *p;
      int index = 0;
      zlentry entry;
  
      printf(
          "{total bytes %d} "
          "{num entries %u}\n"
          "{tail offset %u}\n",
          intrev32ifbe(ZIPLIST_BYTES(zl)),
          intrev16ifbe(ZIPLIST_LENGTH(zl)),
          intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl)));
      p = ZIPLIST_ENTRY_HEAD(zl);
      while(*p != ZIP_END) {
          zipEntry(p, &entry);
          printf(
              "{\n"
                  "\taddr 0x%08lx,\n"
                  "\tindex %2d,\n"
                  "\toffset %5ld,\n"
                  "\thdr+entry len: %5u,\n"
                  "\thdr len%2u,\n"
                  "\tprevrawlen: %5u,\n"
                  "\tprevrawlensize: %2u,\n"
                  "\tpayload %5u\n",
              (long unsigned)p,
              index,
              (unsigned long) (p-zl),
              entry.headersize+entry.len,
              entry.headersize,
              entry.prevrawlen,
              entry.prevrawlensize,
              entry.len);
          printf("\tbytes: ");
          for (unsigned int i = 0; i < entry.headersize+entry.len; i++) {
              printf("%02x|",p[i]);
          }
          printf("\n");
          p += entry.headersize;
          if (ZIP_IS_STR(entry.encoding)) {
              printf("\t[str]");
              if (entry.len > 40) {
                  if (fwrite(p,40,1,stdout) == 0) perror("fwrite");
                  printf("...");
              } else {
                  if (entry.len &&
                      fwrite(p,entry.len,1,stdout) == 0) perror("fwrite");
              }
          } else {
              printf("\t[int]%lld", (long long) zipLoadInteger(p,entry.encoding));
          }
          printf("\n}\n");
          p += entry.len;
          index++;
      }
      printf("{end}\n\n");
  }
  
  #ifdef REDIS_TEST
  #include <sys/time.h>
  #include "adlist.h"
  #include "sds.h"
  
  #define debug(f, ...) { if (DEBUG) printf(f, __VA_ARGS__); }
  
  static unsigned char *createList() {
      unsigned char *zl = ziplistNew();
      zl = ziplistPush(zl, (unsigned char*)"foo", 3, ZIPLIST_TAIL);
      zl = ziplistPush(zl, (unsigned char*)"quux", 4, ZIPLIST_TAIL);
      zl = ziplistPush(zl, (unsigned char*)"hello", 5, ZIPLIST_HEAD);
      zl = ziplistPush(zl, (unsigned char*)"1024", 4, ZIPLIST_TAIL);
      return zl;
  }
  
  static unsigned char *createIntList() {
      unsigned char *zl = ziplistNew();
      char buf[32];
  
      sprintf(buf, "100");
      zl = ziplistPush(zl, (unsigned char*)buf, strlen(buf), ZIPLIST_TAIL);
      sprintf(buf, "128000");
      zl = ziplistPush(zl, (unsigned char*)buf, strlen(buf), ZIPLIST_TAIL);
      sprintf(buf, "-100");
      zl = ziplistPush(zl, (unsigned char*)buf, strlen(buf), ZIPLIST_HEAD);
      sprintf(buf, "4294967296");
      zl = ziplistPush(zl, (unsigned char*)buf, strlen(buf), ZIPLIST_HEAD);
      sprintf(buf, "non integer");
      zl = ziplistPush(zl, (unsigned char*)buf, strlen(buf), ZIPLIST_TAIL);
      sprintf(buf, "much much longer non integer");
      zl = ziplistPush(zl, (unsigned char*)buf, strlen(buf), ZIPLIST_TAIL);
      return zl;
  }
  
  static long long usec(void) {
      struct timeval tv;
      gettimeofday(&tv,NULL);
      return (((long long)tv.tv_sec)*1000000)+tv.tv_usec;
  }
  
  static void stress(int pos, int num, int maxsize, int dnum) {
      int i,j,k;
      unsigned char *zl;
      char posstr[2][5] = { "HEAD", "TAIL" };
      long long start;
      for (i = 0; i < maxsize; i+=dnum) {
          zl = ziplistNew();
          for (j = 0; j < i; j++) {
              zl = ziplistPush(zl,(unsigned char*)"quux",4,ZIPLIST_TAIL);
          }
  
          /* Do num times a push+pop from pos */
          start = usec();
          for (k = 0; k < num; k++) {
              zl = ziplistPush(zl,(unsigned char*)"quux",4,pos);
              zl = ziplistDeleteRange(zl,0,1);
          }
          printf("List size: %8d, bytes: %8d, %dx push+pop (%s): %6lld usec\n",
              i,intrev32ifbe(ZIPLIST_BYTES(zl)),num,posstr[pos],usec()-start);
          zfree(zl);
      }
  }
  
  static unsigned char *pop(unsigned char *zl, int where) {
      unsigned char *p, *vstr;
      unsigned int vlen;
      long long vlong;
  
      p = ziplistIndex(zl,where == ZIPLIST_HEAD ? 0 : -1);
      if (ziplistGet(p,&vstr,&vlen,&vlong)) {
          if (where == ZIPLIST_HEAD)
              printf("Pop head: ");
          else
              printf("Pop tail: ");
  
          if (vstr) {
              if (vlen && fwrite(vstr,vlen,1,stdout) == 0) perror("fwrite");
          }
          else {
              printf("%lld", vlong);
          }
  
          printf("\n");
          return ziplistDelete(zl,&p);
      } else {
          printf("ERROR: Could not pop\n");
          exit(1);
      }
  }
  
  static int randstring(char *target, unsigned int min, unsigned int max) {
      int p = 0;
      int len = min+rand()%(max-min+1);
      int minval, maxval;
      switch(rand() % 3) {
      case 0:
          minval = 0;
          maxval = 255;
      break;
      case 1:
          minval = 48;
          maxval = 122;
      break;
      case 2:
          minval = 48;
          maxval = 52;
      break;
      default:
          assert(NULL);
      }
  
      while(p < len)
          target[p++] = minval+rand()%(maxval-minval+1);
      return len;
  }
  
  static void verify(unsigned char *zl, zlentry *e) {
      int len = ziplistLen(zl);
      zlentry _e;
  
      ZIPLIST_ENTRY_ZERO(&_e);
  
      for (int i = 0; i < len; i++) {
          memset(&e[i], 0, sizeof(zlentry));
          zipEntry(ziplistIndex(zl, i), &e[i]);
  
          memset(&_e, 0, sizeof(zlentry));
          zipEntry(ziplistIndex(zl, -len+i), &_e);
  
          assert(memcmp(&e[i], &_e, sizeof(zlentry)) == 0);
      }
  }
  
  int ziplistTest(int argc, char **argv) {
      unsigned char *zl, *p;
      unsigned char *entry;
      unsigned int elen;
      long long value;
  
      /* If an argument is given, use it as the random seed. */
      if (argc == 2)
          srand(atoi(argv[1]));
  
      zl = createIntList();
      ziplistRepr(zl);
  
      zfree(zl);
  
      zl = createList();
      ziplistRepr(zl);
  
      zl = pop(zl,ZIPLIST_TAIL);
      ziplistRepr(zl);
  
      zl = pop(zl,ZIPLIST_HEAD);
      ziplistRepr(zl);
  
      zl = pop(zl,ZIPLIST_TAIL);
      ziplistRepr(zl);
  
      zl = pop(zl,ZIPLIST_TAIL);
      ziplistRepr(zl);
  
      zfree(zl);
  
      printf("Get element at index 3:\n");
      {
          zl = createList();
          p = ziplistIndex(zl, 3);
          if (!ziplistGet(p, &entry, &elen, &value)) {
              printf("ERROR: Could not access index 3\n");
              return 1;
          }
          if (entry) {
              if (elen && fwrite(entry,elen,1,stdout) == 0) perror("fwrite");
              printf("\n");
          } else {
              printf("%lld\n", value);
          }
          printf("\n");
          zfree(zl);
      }
  
      printf("Get element at index 4 (out of range):\n");
      {
          zl = createList();
          p = ziplistIndex(zl, 4);
          if (p == NULL) {
              printf("No entry\n");
          } else {
              printf("ERROR: Out of range index should return NULL, returned offset: %ld\n", p-zl);
              return 1;
          }
          printf("\n");
          zfree(zl);
      }
  
      printf("Get element at index -1 (last element):\n");
      {
          zl = createList();
          p = ziplistIndex(zl, -1);
          if (!ziplistGet(p, &entry, &elen, &value)) {
              printf("ERROR: Could not access index -1\n");
              return 1;
          }
          if (entry) {
              if (elen && fwrite(entry,elen,1,stdout) == 0) perror("fwrite");
              printf("\n");
          } else {
              printf("%lld\n", value);
          }
          printf("\n");
          zfree(zl);
      }
  
      printf("Get element at index -4 (first element):\n");
      {
          zl = createList();
          p = ziplistIndex(zl, -4);
          if (!ziplistGet(p, &entry, &elen, &value)) {
              printf("ERROR: Could not access index -4\n");
              return 1;
          }
          if (entry) {
              if (elen && fwrite(entry,elen,1,stdout) == 0) perror("fwrite");
              printf("\n");
          } else {
              printf("%lld\n", value);
          }
          printf("\n");
          zfree(zl);
      }
  
      printf("Get element at index -5 (reverse out of range):\n");
      {
          zl = createList();
          p = ziplistIndex(zl, -5);
          if (p == NULL) {
              printf("No entry\n");
          } else {
              printf("ERROR: Out of range index should return NULL, returned offset: %ld\n", p-zl);
              return 1;
          }
          printf("\n");
          zfree(zl);
      }
  
      printf("Iterate list from 0 to end:\n");
      {
          zl = createList();
          p = ziplistIndex(zl, 0);
          while (ziplistGet(p, &entry, &elen, &value)) {
              printf("Entry: ");
              if (entry) {
                  if (elen && fwrite(entry,elen,1,stdout) == 0) perror("fwrite");
              } else {
                  printf("%lld", value);
              }
              p = ziplistNext(zl,p);
              printf("\n");
          }
          printf("\n");
          zfree(zl);
      }
  
      printf("Iterate list from 1 to end:\n");
      {
          zl = createList();
          p = ziplistIndex(zl, 1);
          while (ziplistGet(p, &entry, &elen, &value)) {
              printf("Entry: ");
              if (entry) {
                  if (elen && fwrite(entry,elen,1,stdout) == 0) perror("fwrite");
              } else {
                  printf("%lld", value);
              }
              p = ziplistNext(zl,p);
              printf("\n");
          }
          printf("\n");
          zfree(zl);
      }
  
      printf("Iterate list from 2 to end:\n");
      {
          zl = createList();
          p = ziplistIndex(zl, 2);
          while (ziplistGet(p, &entry, &elen, &value)) {
              printf("Entry: ");
              if (entry) {
                  if (elen && fwrite(entry,elen,1,stdout) == 0) perror("fwrite");
              } else {
                  printf("%lld", value);
              }
              p = ziplistNext(zl,p);
              printf("\n");
          }
          printf("\n");
          zfree(zl);
      }
  
      printf("Iterate starting out of range:\n");
      {
          zl = createList();
          p = ziplistIndex(zl, 4);
          if (!ziplistGet(p, &entry, &elen, &value)) {
              printf("No entry\n");
          } else {
              printf("ERROR\n");
          }
          printf("\n");
          zfree(zl);
      }
  
      printf("Iterate from back to front:\n");
      {
          zl = createList();
          p = ziplistIndex(zl, -1);
          while (ziplistGet(p, &entry, &elen, &value)) {
              printf("Entry: ");
              if (entry) {
                  if (elen && fwrite(entry,elen,1,stdout) == 0) perror("fwrite");
              } else {
                  printf("%lld", value);
              }
              p = ziplistPrev(zl,p);
              printf("\n");
          }
          printf("\n");
          zfree(zl);
      }
  
      printf("Iterate from back to front, deleting all items:\n");
      {
          zl = createList();
          p = ziplistIndex(zl, -1);
          while (ziplistGet(p, &entry, &elen, &value)) {
              printf("Entry: ");
              if (entry) {
                  if (elen && fwrite(entry,elen,1,stdout) == 0) perror("fwrite");
              } else {
                  printf("%lld", value);
              }
              zl = ziplistDelete(zl,&p);
              p = ziplistPrev(zl,p);
              printf("\n");
          }
          printf("\n");
          zfree(zl);
      }
  
      printf("Delete inclusive range 0,0:\n");
      {
          zl = createList();
          zl = ziplistDeleteRange(zl, 0, 1);
          ziplistRepr(zl);
          zfree(zl);
      }
  
      printf("Delete inclusive range 0,1:\n");
      {
          zl = createList();
          zl = ziplistDeleteRange(zl, 0, 2);
          ziplistRepr(zl);
          zfree(zl);
      }
  
      printf("Delete inclusive range 1,2:\n");
      {
          zl = createList();
          zl = ziplistDeleteRange(zl, 1, 2);
          ziplistRepr(zl);
          zfree(zl);
      }
  
      printf("Delete with start index out of range:\n");
      {
          zl = createList();
          zl = ziplistDeleteRange(zl, 5, 1);
          ziplistRepr(zl);
          zfree(zl);
      }
  
      printf("Delete with num overflow:\n");
      {
          zl = createList();
          zl = ziplistDeleteRange(zl, 1, 5);
          ziplistRepr(zl);
          zfree(zl);
      }
  
      printf("Delete foo while iterating:\n");
      {
          zl = createList();
          p = ziplistIndex(zl,0);
          while (ziplistGet(p,&entry,&elen,&value)) {
              if (entry && strncmp("foo",(char*)entry,elen) == 0) {
                  printf("Delete foo\n");
                  zl = ziplistDelete(zl,&p);
              } else {
                  printf("Entry: ");
                  if (entry) {
                      if (elen && fwrite(entry,elen,1,stdout) == 0)
                          perror("fwrite");
                  } else {
                      printf("%lld",value);
                  }
                  p = ziplistNext(zl,p);
                  printf("\n");
              }
          }
          printf("\n");
          ziplistRepr(zl);
          zfree(zl);
      }
  
      printf("Regression test for >255 byte strings:\n");
      {
          char v1[257] = {0}, v2[257] = {0};
          memset(v1,'x',256);
          memset(v2,'y',256);
          zl = ziplistNew();
          zl = ziplistPush(zl,(unsigned char*)v1,strlen(v1),ZIPLIST_TAIL);
          zl = ziplistPush(zl,(unsigned char*)v2,strlen(v2),ZIPLIST_TAIL);
  
          /* Pop values again and compare their value. */
          p = ziplistIndex(zl,0);
          assert(ziplistGet(p,&entry,&elen,&value));
          assert(strncmp(v1,(char*)entry,elen) == 0);
          p = ziplistIndex(zl,1);
          assert(ziplistGet(p,&entry,&elen,&value));
          assert(strncmp(v2,(char*)entry,elen) == 0);
          printf("SUCCESS\n\n");
          zfree(zl);
      }
  
      printf("Regression test deleting next to last entries:\n");
      {
          char v[3][257] = {{0}};
          zlentry e[3] = {{.prevrawlensize = 0, .prevrawlen = 0, .lensize = 0,
                           .len = 0, .headersize = 0, .encoding = 0, .p = NULL}};
          size_t i;
  
          for (i = 0; i < (sizeof(v)/sizeof(v[0])); i++) {
              memset(v[i], 'a' + i, sizeof(v[0]));
          }
  
          v[0][256] = '\0';
          v[1][  1] = '\0';
          v[2][256] = '\0';
  
          zl = ziplistNew();
          for (i = 0; i < (sizeof(v)/sizeof(v[0])); i++) {
              zl = ziplistPush(zl, (unsigned char *) v[i], strlen(v[i]), ZIPLIST_TAIL);
          }
  
          verify(zl, e);
  
          assert(e[0].prevrawlensize == 1);
          assert(e[1].prevrawlensize == 5);
          assert(e[2].prevrawlensize == 1);
  
          /* Deleting entry 1 will increase `prevrawlensize` for entry 2 */
          unsigned char *p = e[1].p;
          zl = ziplistDelete(zl, &p);
  
          verify(zl, e);
  
          assert(e[0].prevrawlensize == 1);
          assert(e[1].prevrawlensize == 5);
  
          printf("SUCCESS\n\n");
          zfree(zl);
      }
  
      printf("Create long list and check indices:\n");
      {
          zl = ziplistNew();
          char buf[32];
          int i,len;
          for (i = 0; i < 1000; i++) {
              len = sprintf(buf,"%d",i);
              zl = ziplistPush(zl,(unsigned char*)buf,len,ZIPLIST_TAIL);
          }
          for (i = 0; i < 1000; i++) {
              p = ziplistIndex(zl,i);
              assert(ziplistGet(p,NULL,NULL,&value));
              assert(i == value);
  
              p = ziplistIndex(zl,-i-1);
              assert(ziplistGet(p,NULL,NULL,&value));
              assert(999-i == value);
          }
          printf("SUCCESS\n\n");
          zfree(zl);
      }
  
      printf("Compare strings with ziplist entries:\n");
      {
          zl = createList();
          p = ziplistIndex(zl,0);
          if (!ziplistCompare(p,(unsigned char*)"hello",5)) {
              printf("ERROR: not \"hello\"\n");
              return 1;
          }
          if (ziplistCompare(p,(unsigned char*)"hella",5)) {
              printf("ERROR: \"hella\"\n");
              return 1;
          }
  
          p = ziplistIndex(zl,3);
          if (!ziplistCompare(p,(unsigned char*)"1024",4)) {
              printf("ERROR: not \"1024\"\n");
              return 1;
          }
          if (ziplistCompare(p,(unsigned char*)"1025",4)) {
              printf("ERROR: \"1025\"\n");
              return 1;
          }
          printf("SUCCESS\n\n");
          zfree(zl);
      }
  
      printf("Merge test:\n");
      {
          /* create list gives us: [hello, foo, quux, 1024] */
          zl = createList();
          unsigned char *zl2 = createList();
  
          unsigned char *zl3 = ziplistNew();
          unsigned char *zl4 = ziplistNew();
  
          if (ziplistMerge(&zl4, &zl4)) {
              printf("ERROR: Allowed merging of one ziplist into itself.\n");
              return 1;
          }
  
          /* Merge two empty ziplists, get empty result back. */
          zl4 = ziplistMerge(&zl3, &zl4);
          ziplistRepr(zl4);
          if (ziplistLen(zl4)) {
              printf("ERROR: Merging two empty ziplists created entries.\n");
              return 1;
          }
          zfree(zl4);
  
          zl2 = ziplistMerge(&zl, &zl2);
          /* merge gives us: [hello, foo, quux, 1024, hello, foo, quux, 1024] */
          ziplistRepr(zl2);
  
          if (ziplistLen(zl2) != 8) {
              printf("ERROR: Merged length not 8, but: %u\n", ziplistLen(zl2));
              return 1;
          }
  
          p = ziplistIndex(zl2,0);
          if (!ziplistCompare(p,(unsigned char*)"hello",5)) {
              printf("ERROR: not \"hello\"\n");
              return 1;
          }
          if (ziplistCompare(p,(unsigned char*)"hella",5)) {
              printf("ERROR: \"hella\"\n");
              return 1;
          }
  
          p = ziplistIndex(zl2,3);
          if (!ziplistCompare(p,(unsigned char*)"1024",4)) {
              printf("ERROR: not \"1024\"\n");
              return 1;
          }
          if (ziplistCompare(p,(unsigned char*)"1025",4)) {
              printf("ERROR: \"1025\"\n");
              return 1;
          }
  
          p = ziplistIndex(zl2,4);
          if (!ziplistCompare(p,(unsigned char*)"hello",5)) {
              printf("ERROR: not \"hello\"\n");
              return 1;
          }
          if (ziplistCompare(p,(unsigned char*)"hella",5)) {
              printf("ERROR: \"hella\"\n");
              return 1;
          }
  
          p = ziplistIndex(zl2,7);
          if (!ziplistCompare(p,(unsigned char*)"1024",4)) {
              printf("ERROR: not \"1024\"\n");
              return 1;
          }
          if (ziplistCompare(p,(unsigned char*)"1025",4)) {
              printf("ERROR: \"1025\"\n");
              return 1;
          }
          printf("SUCCESS\n\n");
          zfree(zl);
      }
  
      printf("Stress with random payloads of different encoding:\n");
      {
          int i,j,len,where;
          unsigned char *p;
          char buf[1024];
          int buflen;
          list *ref;
          listNode *refnode;
  
          /* Hold temp vars from ziplist */
          unsigned char *sstr;
          unsigned int slen;
          long long sval;
  
          for (i = 0; i < 20000; i++) {
              zl = ziplistNew();
              ref = listCreate();
              listSetFreeMethod(ref,(void (*)(void*))sdsfree);
              len = rand() % 256;
  
              /* Create lists */
              for (j = 0; j < len; j++) {
                  where = (rand() & 1) ? ZIPLIST_HEAD : ZIPLIST_TAIL;
                  if (rand() % 2) {
                      buflen = randstring(buf,1,sizeof(buf)-1);
                  } else {
                      switch(rand() % 3) {
                      case 0:
                          buflen = sprintf(buf,"%lld",(0LL + rand()) >> 20);
                          break;
                      case 1:
                          buflen = sprintf(buf,"%lld",(0LL + rand()));
                          break;
                      case 2:
                          buflen = sprintf(buf,"%lld",(0LL + rand()) << 20);
                          break;
                      default:
                          assert(NULL);
                      }
                  }
  
                  /* Add to ziplist */
                  zl = ziplistPush(zl, (unsigned char*)buf, buflen, where);
  
                  /* Add to reference list */
                  if (where == ZIPLIST_HEAD) {
                      listAddNodeHead(ref,sdsnewlen(buf, buflen));
                  } else if (where == ZIPLIST_TAIL) {
                      listAddNodeTail(ref,sdsnewlen(buf, buflen));
                  } else {
                      assert(NULL);
                  }
              }
  
              assert(listLength(ref) == ziplistLen(zl));
              for (j = 0; j < len; j++) {
                  /* Naive way to get elements, but similar to the stresser
                   * executed from the Tcl test suite. */
                  p = ziplistIndex(zl,j);
                  refnode = listIndex(ref,j);
  
                  assert(ziplistGet(p,&sstr,&slen,&sval));
                  if (sstr == NULL) {
                      buflen = sprintf(buf,"%lld",sval);
                  } else {
                      buflen = slen;
                      memcpy(buf,sstr,buflen);
                      buf[buflen] = '\0';
                  }
                  assert(memcmp(buf,listNodeValue(refnode),buflen) == 0);
              }
              zfree(zl);
              listRelease(ref);
          }
          printf("SUCCESS\n\n");
      }
  
      printf("Stress with variable ziplist size:\n");
      {
          stress(ZIPLIST_HEAD,100000,16384,256);
          stress(ZIPLIST_TAIL,100000,16384,256);
      }
  
      return 0;
  }
  #endif
  