底层数据结构-quickList

快速链表（3.2版本后加的，替换之前的linkedlist）
结合了双端链表以及压缩链表的特性
- 用双端链表来描述整个快速链表，而其中每个节点都用一个压缩链表作为底层数据存储
- 由于链表对头与尾访问最频繁，而对中间数据访问并不是特别频繁，所以会对中间节点底层压缩链表所使用的内存进行压缩（用到了LZF算法）

引用ziplist后封装生成节点，组成双端链表结构

##单个节点
typedef struct quicklistNode {

    struct quicklistNode *prev; //上一个节点
    struct quicklistNode *next; //下一个节点
    
    unsigned char *zl; //引用原版ziplist或者压缩后的quicklistLZF
    unsigned int sz; //未压缩的ziplist占用的字节数（size）
    unsigned int count:16; // ziplist中含有的元素数目
    
    unsigned int encoding:2; //ziplist是否被压缩，压了就是LZF(1)，没压就是RAW(2)
    unsigned int container:2; //节点持有的数据类型，目前只有ZIPLIST(2)
    unsigned int recompress:1; //ziplist是否暂时被解压了，解了就是1
    unsigned int attempted_compress:1;
    unsigned int extra : 10; //保留以后使用
} quicklistNode;

##如果ziplist要被压缩，那就放到这里面，由上面的zl去引用
typedef struct quicklistLZF {
    unsigned int sz; //压缩后的ziplist占用的字节数（size）
    char compressed[]; //压缩后的数据
}

##整个快速链表
typedef struct quicklist {
    quicklistNode *head; //链表头部节点
    quicklistNode *tail; //链表尾部节点
    unsigned long count; //统计所有ziplist内的所有entry的数量
    unsigned long len; //所有节点的数量
    int fill:16; //控制着ziplist的最大长度，若取正数N代表最多N个entry
    //若取负数（-1代表4kb，-2代表8kb...-5代表64kb）
    unsigned int compress:16; //控制着ziplist是否需要压缩
    //若取0表示不压缩，取N表示除头N个末N个其他全部压缩
    quicklistBookmark bookmarks[]; //可选加书签，最好在大量节点下才用
} quicklist;

##类似于ziplist的entry，quicklist也有自己的entry
##目的是封装并隐藏底层复杂的引用关系，使得看上去像是其中有一个个entry
typedef struct quicklistEntry {
    const quicklist *quicklist; //所属的快速链表
    quicklistNode *node; //所属的某个链表节点
    unsigned char *zi; //单个链表节点中，某个数据节点entry的位置引用
    unsigned char *value; //如果数据是字符串，就用这个指向那个数据
    long long longval; //如果数据是整数，就保存在这里
    unsigned int sz; //如果数据是字符串，用这个记录长度
    int offset; //单个链表节点中，某个数据节点entry的偏移
}

Keyboard shortcuts

底层数据结构-quickList