🏵️ quickList

1. 数据结构

• 时间 & 空间 的折中

// 节点类
typedef struct quicklistNode {
    struct quicklistNode *prev; // 前置节点
    struct quicklistNode *next; // 后置节点
    unsigned char *entry; // 数据指针，若节点数据未被压缩，则指向 ziplist；若否，指向 quicklistLZF 结构
    size_t sz;             /* entry 大小，若 entry 被压缩，大小仍为 未被压缩前的大小 */
    unsigned int count : 16;     /* ziplist 里面的数据项个数 */
    unsigned int encoding : 2;   /* 是否被压缩，RAW==1 or LZF==2 */
    unsigned int container : 2;  /* 预留字段，固定为 2；PLAIN==1 or PACKED==2 */
    unsigned int recompress : 1; /* 记录当前节点之前是否被压缩，例如查看某个节点时，若被压缩，那么查看后需要修改为 1，之后有时间再压缩回去 */
    unsigned int attempted_compress : 1; /* 节点不能被压缩，用于自动化测试 */
    unsigned int dont_compress : 1; /* 阻止节点的压缩 */
    unsigned int extra : 9; /* 预留字段 */
} quicklistNode;

// 被压缩的 entry 结构
typedef struct quicklistLZF {
    size_t sz; // 被压缩后的 entry 大小
    char compressed[]; // 柔性数组，存放压缩后的 ziplist 字节数组
} quicklistLZF;

// quicklist
typedef struct quicklist {
    quicklistNode *head; // 头节点
    quicklistNode *tail; // 尾节点
    unsigned long count; // 所有 ziplist 数据项的 个数和
    unsigned long len;  // 节点数
    signed int fill : QL_FILL_BITS; // 大小设置，存放 list-max-ziplist-size 参数值
    unsigned int compress : QL_COMP_BITS; // 节点压缩深度，存放 list-compress-depth 参数值
    unsigned int bookmark_count: QL_BM_BITS;
    quicklistBookmark bookmarks[];
} quicklist;

---

2. 参数特征

1) list-max-ziplist-size

1. 正数
   • 每个 quicklistNode 上的 ziplist 个数
2. 负数
   • -1
     • 每个 quicklistNode 上的 ziplist 大小 <= 4KB
   • -2
     • 每个 quicklistNode 上的 ziplist 大小 <= 8KB
     • default
   • -3
     • 每个 quicklistNode 上的 ziplist 大小 <= 16KB
   • -4
     • 每个 quicklistNode 上的 ziplist 大小 <= 32KB
   • -5
     • 每个 quicklistNode 上的 ziplist 大小 <= 64KB

2) list-compress-depth

1. 一个 quicklist 两端不被压缩的节点个数
2. 取值：
   • 0
     • 不压缩
     • default
   • 1
     • 两端各有 1 个节点不被压缩，中间节点被压缩
   • 2
   • 3
   • ...

---

2. 常见函数

1) 初始化

// 链表初始化
quicklist *quicklistCreate(void) {
    struct quicklist *quicklist;

    quicklist = zmalloc(sizeof(*quicklist));
    quicklist->head = quicklist->tail = NULL;
    quicklist->len = 0;
    quicklist->count = 0;
    quicklist->compress = 0;
    quicklist->fill = -2;
    quicklist->bookmark_count = 0;
    return quicklist;
}

2) 头尾插入节点

/* 头部插入节点
 *
 * Returns 0 if used existing head.
 * Returns 1 if new head created. */
int quicklistPushHead(quicklist *quicklist, void *value, size_t sz) {
    quicklistNode *orig_head = quicklist->head;

    if (unlikely(isLargeElement(sz))) {
        __quicklistInsertPlainNode(quicklist, quicklist->head, value, sz, 0);
        return 1;
    }

    if (likely( // 在 entry 中插入新节点
        _quicklistNodeAllowInsert(quicklist->head, quicklist->fill, sz))) {
        quicklist->head->entry = lpPrepend(quicklist->head->entry, value, sz);
        quicklistNodeUpdateSz(quicklist->head);
    } else { // 新建一个 entry，然后插入
        quicklistNode *node = quicklistCreateNode();
        node->entry = lpPrepend(lpNew(0), value, sz);
        quicklistNodeUpdateSz(node);
        _quicklistInsertNodeBefore(quicklist, quicklist->head, node);
    }
    quicklist->count++;
    quicklist->head->count++;
    return (orig_head != quicklist->head);
}

/* 尾部插入节点
 *
 * Returns 0 if used existing tail.
 * Returns 1 if new tail created. */
int quicklistPushTail(quicklist *quicklist, void *value, size_t sz) {
    quicklistNode *orig_tail = quicklist->tail;
    if (unlikely(isLargeElement(sz))) {
        __quicklistInsertPlainNode(quicklist, quicklist->tail, value, sz, 1);
        return 1;
    }

    if (likely(
        _quicklistNodeAllowInsert(quicklist->tail, quicklist->fill, sz))) {
        quicklist->tail->entry = lpAppend(quicklist->tail->entry, value, sz);
        quicklistNodeUpdateSz(quicklist->tail);
    } else {
        quicklistNode *node = quicklistCreateNode();
        node->entry = lpAppend(lpNew(0), value, sz);

        quicklistNodeUpdateSz(node);
        _quicklistInsertNodeAfter(quicklist, quicklist->tail, node);
    }
    quicklist->count++;
    quicklist->tail->count++;
    return (orig_tail != quicklist->tail);
}