text: /* quicklist.h - A generic doubly linked quicklist implementation
   *
   * Copyright (c) 2014, Matt Stancliff <matt@genges.com>
   * All rights reserved.
   *
   * Redistribution and use in source and binary forms, with or without
   * modification, are permitted provided that the following conditions are met:
   *
   *   * Redistributions of source code must retain the above copyright notice,
   *     this quicklist of conditions and the following disclaimer.
   *   * Redistributions in binary form must reproduce the above copyright
   *     notice, this quicklist of conditions and the following disclaimer in the
   *     documentation and/or other materials provided with the distribution.
   *   * Neither the name of Redis nor the names of its contributors may be used
   *     to endorse or promote products derived from this software without
   *     specific prior written permission.
   *
   * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
   * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
   * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
   * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
   * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
   * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
   * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
   * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
   * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
   * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
   * POSSIBILITY OF SUCH DAMAGE.
   */
  
  #ifndef __QUICKLIST_H__
  #define __QUICKLIST_H__
  
  /* Node, quicklist, and Iterator are the only data structures used currently. */
  
  /* quicklistNode is a 32 byte struct describing a ziplist for a quicklist.
   * We use bit fields keep the quicklistNode at 32 bytes.
   * count: 16 bits, max 65536 (max zl bytes is 65k, so max count actually < 32k).
   * encoding: 2 bits, RAW=1, LZF=2. 
   * container: 2 bits, NONE=1, ZIPLIST=2.
   * recompress: 1 bit, bool, true if node is temporarry decompressed for usage.
   * attempted_compress: 1 bit, boolean, used for verifying during testing.
   * extra: 12 bits, free for future use; pads out the remainder of 32 bits */
  typedef struct quicklistNode {
      struct quicklistNode *prev;
      struct quicklistNode *next;
      unsigned char *zl;
      unsigned int sz;             /* ziplist size in bytes */ //ziplist的内存长度
      unsigned int count : 16;     /* count of items in ziplist */ //ziplist内部数据的个数
      unsigned int encoding : 2;   /* RAW==1 or LZF==2 */ //ziplist编码方式，1为默认方式，2为LZF数据压缩方式
      unsigned int container : 2;  /* NONE==1 or ZIPLIST==2 */ // 预留字段，存放数据的方式，1--NONE，2--ziplist
      unsigned int recompress : 1; /* was this node previous compressed? */// 解压标记，当查看一个被压缩的数据时，需要暂时解压，标记此参数为1，之后再重新进行压缩
      unsigned int attempted_compress : 1; /* node can't compress; too small */// 测试相关
      unsigned int extra : 10; /* more bits to steal for future usage */
  } quicklistNode;
  
  /* quicklistLZF is a 4+N byte struct holding 'sz' followed by 'compressed'.
   * 'sz' is byte length of 'compressed' field.
   * 'compressed' is LZF data with total (compressed) length 'sz'
   * NOTE: uncompressed length is stored in quicklistNode->sz.
   * When quicklistNode->zl is compressed, node->zl points to a quicklistLZF */
  typedef struct quicklistLZF {
      unsigned int sz; /* LZF size in bytes*/// LZF压缩后占用的字节数
      char compressed[]; //指向数据部分
  } quicklistLZF;
  
  /* quicklist is a 40 byte struct (on 64-bit systems) describing a quicklist.
   * 'count' is the number of total entries.
   * 'len' is the number of quicklist nodes.
   * 'compress' is: -1 if compression disabled, otherwise it's the number
   *                of quicklistNodes to leave uncompressed at ends of quicklist.
   * 'fill' is the user-requested (or default) fill factor. */
  typedef struct quicklist {
      quicklistNode *head;
      quicklistNode *tail;
      unsigned long count;        /* total count of all entries in all ziplists */ //链表内的entries总数量
      unsigned long len;          /* number of quicklistNodes */ //节点数
      int fill : 16;              /* fill factor for individual nodes */ //保存ziplist的大小，配置文件设定，占16bits
      unsigned int compress : 16; /* depth of end nodes not to compress;0=off *///保存压缩程度值，配置文件设定，占16bits，0表示不压缩
  } quicklist;
  
  typedef struct quicklistIter {
      const quicklist *quicklist;
      quicklistNode *current;
      unsigned char *zi; //指向当前quicklist节点中迭代的ziplist
      long offset; /* offset in current ziplist */ //当前ziplist结构中的entry偏移量，反响迭代-1开始
      int direction; //迭代方向
  } quicklistIter;
  
  typedef struct quicklistEntry {
      const quicklist *quicklist;
      quicklistNode *node;
      unsigned char *zi; //指向当前ziplist结构偏移指针
      unsigned char *value; //指向当前ziplist结构的字符串vlaue成员
      long long longval;  //指向当前ziplist结构的整数value成员
      unsigned int sz; //保存当前ziplist结构的字节数大小
      int offset; //当前ziplist的entry偏移量
  } quicklistEntry;
  
  #define QUICKLIST_HEAD 0
  #define QUICKLIST_TAIL -1
  
  /* quicklist node encodings */
  #define QUICKLIST_NODE_ENCODING_RAW 1
  #define QUICKLIST_NODE_ENCODING_LZF 2
  
  /* quicklist compression disable */
  #define QUICKLIST_NOCOMPRESS 0
  
  /* quicklist container formats */
  #define QUICKLIST_NODE_CONTAINER_NONE 1
  #define QUICKLIST_NODE_CONTAINER_ZIPLIST 2
  
  #define quicklistNodeIsCompressed(node)                                        \
      ((node)->encoding == QUICKLIST_NODE_ENCODING_LZF)
  
  /* Prototypes */
  quicklist *quicklistCreate(void);
  quicklist *quicklistNew(int fill, int compress);
  void quicklistSetCompressDepth(quicklist *quicklist, int depth);
  void quicklistSetFill(quicklist *quicklist, int fill);
  void quicklistSetOptions(quicklist *quicklist, int fill, int depth);
  void quicklistRelease(quicklist *quicklist);
  int quicklistPushHead(quicklist *quicklist, void *value, const size_t sz);
  int quicklistPushTail(quicklist *quicklist, void *value, const size_t sz);
  void quicklistPush(quicklist *quicklist, void *value, const size_t sz,
                     int where);
  void quicklistAppendZiplist(quicklist *quicklist, unsigned char *zl);
  quicklist *quicklistAppendValuesFromZiplist(quicklist *quicklist,
                                              unsigned char *zl);
  quicklist *quicklistCreateFromZiplist(int fill, int compress,
                                        unsigned char *zl);
  void quicklistInsertAfter(quicklist *quicklist, quicklistEntry *node,
                            void *value, const size_t sz);
  void quicklistInsertBefore(quicklist *quicklist, quicklistEntry *node,
                             void *value, const size_t sz);
  void quicklistDelEntry(quicklistIter *iter, quicklistEntry *entry);
  int quicklistReplaceAtIndex(quicklist *quicklist, long index, void *data,
                              int sz);
  int quicklistDelRange(quicklist *quicklist, const long start, const long stop);
  quicklistIter *quicklistGetIterator(const quicklist *quicklist, int direction);
  quicklistIter *quicklistGetIteratorAtIdx(const quicklist *quicklist,
                                           int direction, const long long idx);
  int quicklistNext(quicklistIter *iter, quicklistEntry *node);
  void quicklistReleaseIterator(quicklistIter *iter);
  quicklist *quicklistDup(quicklist *orig);
  int quicklistIndex(const quicklist *quicklist, const long long index,
                     quicklistEntry *entry);
  void quicklistRewind(quicklist *quicklist, quicklistIter *li);
  void quicklistRewindTail(quicklist *quicklist, quicklistIter *li);
  void quicklistRotate(quicklist *quicklist);
  int quicklistPopCustom(quicklist *quicklist, int where, unsigned char **data,
                         unsigned int *sz, long long *sval,
                         void *(*saver)(unsigned char *data, unsigned int sz));
  int quicklistPop(quicklist *quicklist, int where, unsigned char **data,
                   unsigned int *sz, long long *slong);
  unsigned long quicklistCount(const quicklist *ql);
  int quicklistCompare(unsigned char *p1, unsigned char *p2, int p2_len);
  size_t quicklistGetLzf(const quicklistNode *node, void **data);
  
  #ifdef REDIS_TEST
  int quicklistTest(int argc, char *argv[]);
  #endif
  
  /* Directions for iterators */
  #define AL_START_HEAD 0
  #define AL_START_TAIL 1
  
  #endif /* __QUICKLIST_H__ */
  