Redis源码学习基本数据结构之quicklist

简而言之，quicklist是一个双端链表,双端链表的节点表示的元素是一个压缩链表(ziplist),压缩链表中的每一个entry是实际数据的表示。ziplist(https://www.jianshu.com/p/adfde59df5ff)

一、结构

//占32字节 表示快速链表的节点 节点数据是一个压缩链表 压缩链表中的entry 包含的才是实际数据
typedef struct quicklistNode {
    struct quicklistNode *prev;//8字节
    struct quicklistNode *next;//8字节
    unsigned char *zl;//8字节 压缩链表首地址
    unsigned int sz;  //4字节 压缩链表的所占字节数 
    //以下总共四字节
    unsigned int count : 16; //压缩链表的entry个数
    unsigned int encoding : 2;//1表示不压缩 2 表示压缩
    unsigned int container : 2;/* NONE==1 or ZIPLIST==2 */
    unsigned int recompress : 1; // /* was this node previous compressed? */
    unsigned int attempted_compress : 1;//quicklist是否已经压缩过  
    unsigned int extra : 10;//额外bit位
} quicklistNode;//快速链表的节点

压缩链表编码后的结构
typedef struct quicklistLZF {
    unsigned int sz;
    char compressed[];
} quicklistLZF;


//占40字节(由于字节对齐)
typedef struct quicklist {//5*8=40bytes
    quicklistNode *head;        //8
    quicklistNode *tail;        //8
    unsigned long count;        //8  所有压缩链表中所有entry的个数之和      
    unsigned long len;          //8  快速链表节点个数      
    int fill : 16;              //2  ziplist大小限定，由list-max-ziplist-size给定      
    unsigned int compress : 16; //2  一个quicklist两端不被压缩的节点个数。 
} quicklist;

typedef struct quicklistIter {//快速链表迭代器
    const quicklist *quicklist;   //所在快速链表
    quicklistNode *current;       //所在的快速链表节点
    unsigned char *zi;            //ziplist中的entry首地址
    long offset;                  //数据entry在当前ziplist中的第offset位
    int direction;                //方向 向后或者向前
} quicklistIter;

//实际数据的获得表示
typedef struct quicklistEntry {
    const quicklist *quicklist;//属于的快速链表
    quicklistNode *node;    //指向的快速链表的节点
    unsigned char *zi;      //指向当前ziplist的entry的指针
    unsigned char *value;   //指向当前ziplist结构的字符串vlaue成员
    long long longval;      //指向当前ziplist结构的数字成员
    unsigned int sz;        //保存当前ziplist结构的字节数大小
    int offset;             //保存当前数据相对ziplist的偏移量
} quicklistEntry;//就是表示 实际的数据的存储方位

二、api

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);//往头部对应的ziplist插入数据
int quicklistPushTail(quicklist *quicklist, void *value, const size_t sz);//往尾部对应的ziplist插入数据
void quicklistPush(quicklist *quicklist, void *value, const size_t sz,
                   int where);//往头部或者尾部对应的ziplist插入数据
void quicklistAppendZiplist(quicklist *quicklist, unsigned char *zl);//快速链表中尾部插入压缩链表
quicklist *quicklistAppendValuesFromZiplist(quicklist *quicklist,
                                            unsigned char *zl);//将压缩链表中的每隔entry数据插入到快速链表tail里面
quicklist *quicklistCreateFromZiplist(int fill, int compress,
                                      unsigned char *zl);//创建快速链表，然后将压缩链表中的数据插入到快速链表
void quicklistInsertAfter(quicklist *quicklist, quicklistEntry *node,
                          void *value, const size_t sz);//在node所指向的数据后面插入数据
void quicklistInsertBefore(quicklist *quicklist, quicklistEntry *node,
                           void *value, const size_t sz);//在node前面插入数据
void quicklistDelEntry(quicklistIter *iter, quicklistEntry *entry);//删除entry指向的数据
int quicklistReplaceAtIndex(quicklist *quicklist, long index, void *data,
                            int sz);//替换index位置的数据
int quicklistDelRange(quicklist *quicklist, const long start, const long stop);//删除start 到 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);//得到node的下一个元素迭代器
void quicklistReleaseIterator(quicklistIter *iter);//释放当前指向的迭代器
quicklist *quicklistDup(quicklist *orig);//copy
int quicklistIndex(const quicklist *quicklist, const long long index,
                   quicklistEntry *entry);//找到第index个元素，index可以为-1表示最后一个元素，然后对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));//pop 只能从头或者尾部 pop
int quicklistPop(quicklist *quicklist, int where, unsigned char **data,
                 unsigned int *sz, long long *slong);//pop 只能从头或者尾部
unsigned long quicklistCount(const quicklist *ql);//返回所有压缩链表中所有entry的个数之和
int quicklistCompare(unsigned char *p1, unsigned char *p2, int p2_len);//比较p1所指向的entry对应的数据与p2
size_t quicklistGetLzf(const quicklistNode *node, void **data);

三、重要api介绍

1. quicklistInsertAfter

void quicklistInsertAfter(quicklist *quicklist, quicklistEntry *entry,
                          void *value, const size_t sz) {
    _quicklistInsert(quicklist, entry, value, sz, 1);
}

//after==1向后插入 ==0前插
REDIS_STATIC void _quicklistInsert(quicklist *quicklist, quicklistEntry *entry,
                                   void *value, const size_t sz, int after) {
    int full = 0, at_tail = 0, at_head = 0, full_next = 0, full_prev = 0;
    int fill = quicklist->fill;
    quicklistNode *node = entry->node;
    quicklistNode *new_node = NULL;

    if (!node) {//如果node为空 只需要创建一个新的ziplist，并将数据插入即可
        /* we have no reference node, so let's create only node in the list */
        D("No node given!");
        new_node = quicklistCreateNode();
        new_node->zl = ziplistPush(ziplistNew(), value, sz, ZIPLIST_HEAD);
        __quicklistInsertNode(quicklist, NULL, new_node, after);
        new_node->count++;
        quicklist->count++;
        return;
    }
    if (!_quicklistNodeAllowInsert(node, fill, sz)) {//对于sz长度的数据可以插入吗
        full = 1;//不允许插入的话 表示此节点满了 full设为1
    }

    if (after && (entry->offset == node->count)) {//如果这个entry是最后一个数据 应该插入这里
        D("At Tail of current ziplist");
        at_tail = 1;
        if (!_quicklistNodeAllowInsert(node->next, fill, sz)) {
            D("Next node is full too.");
            full_next = 1;//下一个节点也满了
        }
    }
    if (!after && (entry->offset == 0)) {//如果是前插
        D("At Head");
        at_head = 1;
        if (!_quicklistNodeAllowInsert(node->prev, fill, sz)) {
            D("Prev node is full too.");
            full_prev = 1;
        }
    }
    if (!full && after) {//当前node未满 向后的方向此时直接插入即可
        D("Not full, inserting after current position.");
        quicklistDecompressNodeForUse(node);
        unsigned char *next = ziplistNext(node->zl, entry->zi);
        if (next == NULL) {
            node->zl = ziplistPush(node->zl, value, sz, ZIPLIST_TAIL);
        } else {
            node->zl = ziplistInsert(node->zl, next, value, sz);
        }
        node->count++;
        quicklistNodeUpdateSz(node);
        quicklistRecompressOnly(quicklist, node);
    } else if (!full && !after) {//当前node未满 向前插入此时直接插入即可
        D("Not full, inserting before current position.");
        quicklistDecompressNodeForUse(node);
        node->zl = ziplistInsert(node->zl, entry->zi, value, sz);
        node->count++;
        quicklistNodeUpdateSz(node);
        quicklistRecompressOnly(quicklist, node);
    } else if (full && at_tail && node->next && !full_next && after) {//插入到下一个node 的条件
 
        D("Full and tail, but next isn't full; inserting next node head");
        new_node = node->next;
        quicklistDecompressNodeForUse(new_node);
        new_node->zl = ziplistPush(new_node->zl, value, sz, ZIPLIST_HEAD);
        new_node->count++;
        quicklistNodeUpdateSz(new_node);
        quicklistRecompressOnly(quicklist, new_node);
    } else if (full && at_head && node->prev && !full_prev && !after) {//插入到前一个node 的条件
      
        D("Full and head, but prev isn't full, inserting prev node tail");
        new_node = node->prev;
        quicklistDecompressNodeForUse(new_node);
        new_node->zl = ziplistPush(new_node->zl, value, sz, ZIPLIST_TAIL);
        new_node->count++;
        quicklistNodeUpdateSz(new_node);
        quicklistRecompressOnly(quicklist, new_node);
    } else if (full && ((at_tail && node->next && full_next && after) ||
                        (at_head && node->prev && full_prev && !after))) {//如果前一个node 或者后一个node也满来了 创建一个新的node
        D("\tprovisioning new node...");
        new_node = quicklistCreateNode();
        new_node->zl = ziplistPush(ziplistNew(), value, sz, ZIPLIST_HEAD);
        new_node->count++;
        quicklistNodeUpdateSz(new_node);
        __quicklistInsertNode(quicklist, node, new_node, after);
    } else if (full) {//将node对应的压缩链表分割
     
        D("\tsplitting node...");
        quicklistDecompressNodeForUse(node);
        new_node = _quicklistSplitNode(node, entry->offset, after);//把ziplist分割为两部分
        new_node->zl = ziplistPush(new_node->zl, value, sz,
                                   after ? ZIPLIST_HEAD : ZIPLIST_TAIL);
        new_node->count++;
        quicklistNodeUpdateSz(new_node);
        __quicklistInsertNode(quicklist, node, new_node, after);
        _quicklistMergeNodes(quicklist, node);
    }

    quicklist->count++;
}

2. quicklistDelRange

//返回1 表示都删除了 0表示啥也没删除
int quicklistDelRange(quicklist *quicklist, const long start,
                      const long count) {
    if (count <= 0)
        return 0;
    unsigned long extent = (unsigned long) count; /*删除的长度*/

    if (start >= 0 && extent > (quicklist->count - start)) {//如果start大于零且从start开始count个查过了总个数 更新正确删除的个数
        extent = quicklist->count - start;
    } else if (start < 0 && extent > (unsigned long)(-start)) {
        extent = -start; 
    }

    quicklistEntry entry;
    if (!quicklistIndex(quicklist, start, &entry))
        return 0;
    D("Quicklist delete request for start %ld, count %ld, extent: %ld", start,
      count, extent);
    quicklistNode *node = entry.node;

    /* iterate over next nodes until everything is deleted. */
    while (extent) {//最终应该删除这么多个数据
        quicklistNode *next = node->next;
        unsigned long del;
        int delete_entire_node = 0;
        if (entry.offset == 0 && extent >= node->count) {
            //直接删除此node   del为此ziplist数据个数
            delete_entire_node = 1;
            del = node->count;
        } else if (entry.offset >= 0 && extent >= node->count) {
            //从offset删除 del长度的数据
            del = node->count - entry.offset;
        } else if (entry.offset < 0) {
            del = -entry.offset;
            if (del > extent)
                del = extent;
        } else {
            del = extent;
        }

        D("[%ld]: asking to del: %ld because offset: %d; (ENTIRE NODE: %d), "
          "node count: %u",
          extent, del, entry.offset, delete_entire_node, node->count);

        if (delete_entire_node) {//直接ziplist全部删除
            __quicklistDelNode(quicklist, node);
        } else {//范围删除
            quicklistDecompressNodeForUse(node);
            node->zl = ziplistDeleteRange(node->zl, entry.offset, del);
            quicklistNodeUpdateSz(node);
            node->count -= del;
            quicklist->count -= del;
            quicklistDeleteIfEmpty(quicklist, node);
            if (node)
                quicklistRecompressOnly(quicklist, node);
        }

        extent -= del;//更新还要被删除的entry的个数

        node = next;

        entry.offset = 0;
    }
    return 1;
}

四、参考

• https://redis.io/
• https://blog.csdn.net/qq_30085733/article/details/79914295