Redis深度历险-快速列表

快速列表就是为了实现list的功能，是基于压缩列表和双向链表的集合实现，主要是规避普通双向链表的前后指针分配和内存碎片问题

列表

void listTypePush(robj *subject, robj *value, int where) {
    //list只有快速列表一种存储方式了
    if (subject->encoding == OBJ_ENCODING_QUICKLIST) {
        int pos = (where == LIST_HEAD) ? QUICKLIST_HEAD : QUICKLIST_TAIL;
        //将数据插入到快速列表中 
        if (value->encoding == OBJ_ENCODING_INT) {
            char buf[32];
            ll2string(buf, 32, (long)value->ptr);
            quicklistPush(subject->ptr, buf, strlen(buf), pos);
        } else {
            quicklistPush(subject->ptr, value->ptr, sdslen(value->ptr), pos);
        }
    } else {
        serverPanic("Unknown list encoding");
    }
}

列表只使用了快速列表存储数据

快速列表

快速列表的结构很简单，快速列表就是一个双向链表，只不过链表中每一个节点都是一个压缩列表

结构体

快速列表

typedef struct quicklist {
    quicklistNode *head;
    quicklistNode *tail;                //快速列表的头尾节点
    unsigned long count;        //所有元素的个数
    unsigned long len;          //快速列表节点个数
    int fill : QL_FILL_BITS;                        //和压缩有关的参数，不必关注
    unsigned int compress : QL_COMP_BITS;   
    unsigned int bookmark_count: QL_BM_BITS;
    quicklistBookmark bookmarks[];
} quicklist;

压缩列表可以进行压缩以节省空间，暂时不必关注

快速列表节点

typedef struct quicklistNode {
    struct quicklistNode *prev;             
    struct quicklistNode *next;             //双向链表前一个节点和后一个节点
    unsigned char *zl;                              //压缩列表
    unsigned int sz;                        //压缩列表字节长度
    unsigned int count : 16;                //压缩列表中元素个数？ 压缩列表中不是有吗？？？
    unsigned int encoding : 2;              //编码方式，原生的还是压缩的
    unsigned int container : 2;             
    unsigned int recompress : 1;                
    unsigned int attempted_compress : 1; 
    unsigned int extra : 10;                            //为将来预留的标志位
} quicklistNode;

头部插入元素

int quicklistPushHead(quicklist *quicklist, void *value, size_t sz) {
    quicklistNode *orig_head = quicklist->head;
    //目前快速列表的头节点是否还允许插入元素
    if (likely(
            _quicklistNodeAllowInsert(quicklist->head, quicklist->fill, sz))) {
        //在快速列表头节点中插入元素
        quicklist->head->zl =
            ziplistPush(quicklist->head->zl, value, sz, ZIPLIST_HEAD);
        //更新头节点中压缩列表的字节长度
        quicklistNodeUpdateSz(quicklist->head);
    } else {
        //创建一个新的快速列表节点，并把元素插入到此节点中
        quicklistNode *node = quicklistCreateNode();
        node->zl = ziplistPush(ziplistNew(), value, sz, ZIPLIST_HEAD);
                
        //更新快速列表中压缩列表字节长度
        quicklistNodeUpdateSz(node);
        //将这个新创建的快速列表节点插入在快速列表头部
        _quicklistInsertNodeBefore(quicklist, quicklist->head, node);
    }
    //更新数量统计
    quicklist->count++;
    quicklist->head->count++;
    return (orig_head != quicklist->head);
}

因为列表只支持头部、尾部插入数据，所以整个代码还是比较清晰的