redis源码解析（十四）快速链表基本功能函数解析

小鱼儿 2024-04-18 13:30 62阅读 0赞

### 1. 简介 ###

本文分析快速链表创建、删除、合并等基本功能操作。快速链表由一系列的节点构成，而每个节点又可以携带一个压缩链表，因此快速链表的创建、节点上压缩链表的创建删除、节点的删除、合并、查找等功能都较为复杂，需要先考虑最简单的基本功能函数再由此完成复杂功能。

### 2. 源码分析 ###

/* 优化等级 * Optimization levels for size-based filling */
    static const size_t optimization_level[] = { 4096, 8192, 16384, 32768, 65536};
    
    /* 压缩链表最大字节数 * Maximum size in bytes of any multi-element ziplist. * Larger values will live in their own isolated ziplists. */
    #define SIZE_SAFETY_LIMIT 8192
    
    /* 压缩链表压缩后最小字节数 * Minimum ziplist size in bytes for attempting compression. */
    #define MIN_COMPRESS_BYTES 48
    
    /* 最小压缩提升：意在防止出现压缩后反而占据跟多字节的情况出现 * Minimum size reduction in bytes to store compressed quicklistNode data. * This also prevents us from storing compression if the compression * resulted in a larger size than the original data. */
    #define MIN_COMPRESS_IMPROVE 8
    
    /* If not verbose testing, remove all debug printing. */
    #ifndef REDIS_TEST_VERBOSE
    #define D(...)
    #else
    #define D(...) \ do { \ printf("%s:%s:%d:\t", __FILE__, __FUNCTION__, __LINE__); \ printf(__VA_ARGS__); \ printf("\n"); \ } while (0);
    #endif
    
    /* Simple way to give quicklistEntry structs default values with one call. */
    #define initEntry(e) \ do { \ (e)->zi = (e)->value = NULL; \ (e)->longval = -123456789; \ (e)->quicklist = NULL; \ (e)->node = NULL; \ (e)->offset = 123456789; \ (e)->sz = 0; \ } while (0)
    
    #if __GNUC__ >= 3
    #define likely(x) __builtin_expect(!!(x), 1)
    #define unlikely(x) __builtin_expect(!!(x), 0)
    #else
    #define likely(x) (x)
    #define unlikely(x) (x)
    #endif
    
    /* 创建压缩链表，全部赋初始值，指针为NLL * Create a new quicklist. * Free with quicklistRelease(). */
    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;
        return quicklist;
    }
    
    #define COMPRESS_MAX (1 << 16)
    
    /*设置compress值，即压缩程度*/
    void quicklistSetCompressDepth(quicklist *quicklist, int compress) { 
        if (compress > COMPRESS_MAX) { 
            compress = COMPRESS_MAX;
        } else if (compress < 0) { 
            compress = 0;
        }
        quicklist->compress = compress;
    }
    
    #define FILL_MAX (1 << 15)
    void quicklistSetFill(quicklist *quicklist, int fill) { 
        if (fill > FILL_MAX) { 
            fill = FILL_MAX;
        } else if (fill < -5) { 
            fill = -5;
        }
        quicklist->fill = fill;
    }
    
    /* 设置fill和compress值 */
    void quicklistSetOptions(quicklist *quicklist, int fill, int depth) { 
        quicklistSetFill(quicklist, fill);
        quicklistSetCompressDepth(quicklist, depth);
    }
    
    /* 新建快速链表并根据fill和compress设置初始值 * Create a new quicklist with some default parameters. */
    quicklist *quicklistNew(int fill, int compress) { 
        quicklist *quicklist = quicklistCreate();
        quicklistSetOptions(quicklist, fill, compress);
        return quicklist;
    }
    
    /* 创建快速链表节点 */
    REDIS_STATIC quicklistNode *quicklistCreateNode(void) { 
        quicklistNode *node;
        node = zmalloc(sizeof(*node));
        node->zl = NULL;
        node->count = 0;
        node->sz = 0;
        node->next = node->prev = NULL;
        node->encoding = QUICKLIST_NODE_ENCODING_RAW;
        node->container = QUICKLIST_NODE_CONTAINER_ZIPLIST;
        node->recompress = 0;
        return node;
    }
    
    /* 返回快速链表节点数 * Return cached quicklist count */
    unsigned long quicklistCount(const quicklist *ql) {  return ql->count; }
    
    /* 释放快速链表 * Free entire quicklist. */
    void quicklistRelease(quicklist *quicklist) { 
        unsigned long len;
        quicklistNode *current, *next;
    
        current = quicklist->head;
        len = quicklist->len;
        while (len--) { 
            next = current->next;
    
    		//释放压缩链表，压缩链表节点数递减
            zfree(current->zl);
            quicklist->count -= current->count;
    
    		// 释放当前节点，快速链表节点数减1
            zfree(current);
    
            quicklist->len--;
            current = next;
        }
        zfree(quicklist);
    }
    
    /* 对节点中的压缩链表进行压缩并更新编码状态 * Compress the ziplist in 'node' and update encoding details. * Returns 1 if ziplist compressed successfully. * Returns 0 if compression failed or if ziplist too small to compress. */
    REDIS_STATIC int __quicklistCompressNode(quicklistNode *node) { 
    #ifdef REDIS_TEST
        node->attempted_compress = 1;
    #endif
    
        /* 节点较小则不压缩 * Don't bother compressing small values */
        if (node->sz < MIN_COMPRESS_BYTES)
            return 0;
    
        quicklistLZF *lzf = zmalloc(sizeof(*lzf) + node->sz);
    
        /* 压缩失败或压缩提升小则取消 * Cancel if compression fails or doesn't compress small enough */
        if (((lzf->sz = lzf_compress(node->zl, node->sz, lzf->compressed,
                                     node->sz)) == 0) ||
            lzf->sz + MIN_COMPRESS_IMPROVE >= node->sz) { 
            /* lzf_compress aborts/rejects compression if value not compressable. */
            zfree(lzf);
            return 0;
        }
    
    	//用lzf取代旧的zl
        lzf = zrealloc(lzf, sizeof(*lzf) + lzf->sz);
        zfree(node->zl);
        node->zl = (unsigned char *)lzf;
        node->encoding = QUICKLIST_NODE_ENCODING_LZF;
        node->recompress = 0;
        return 1;
    }
    
    /* 对未压缩节点进行压缩操作 * Compress only uncompressed nodes. */
    #define quicklistCompressNode(_node) \ do { \ if ((_node) && (_node)->encoding == QUICKLIST_NODE_ENCODING_RAW) { \ __quicklistCompressNode((_node)); \ } \ } while (0)
    
    /* 对节点node中的压缩链表进行解压缩 * Uncompress the ziplist in 'node' and update encoding details. * Returns 1 on successful decode, 0 on failure to decode. */
    REDIS_STATIC int __quicklistDecompressNode(quicklistNode *node) { 
    #ifdef REDIS_TEST
        node->attempted_compress = 0;
    #endif
    
    	// decompressed存放解压后的节点数据
        void *decompressed = zmalloc(node->sz);
        quicklistLZF *lzf = (quicklistLZF *)node->zl;
    	
    	// 调用lzf解压API，失败则返回0
        if (lzf_decompress(lzf->compressed, lzf->sz, decompressed, node->sz) == 0) { 
            /* Someone requested decompress, but we can't decompress. Not good. */
            zfree(decompressed);
            return 0;
        }
    	
    	//释放压缩数据，给节点的zl重新赋值为decompressed
        zfree(lzf);
        node->zl = decompressed;
        node->encoding = QUICKLIST_NODE_ENCODING_RAW;
        return 1;
    }
    
    /* 解压压缩的节点，调用__quicklistDecompressNode实现 * Decompress only compressed nodes. */
    #define quicklistDecompressNode(_node) \ do { \ if ((_node) && (_node)->encoding == QUICKLIST_NODE_ENCODING_LZF) { \ __quicklistDecompressNode((_node)); \ } \ } while (0)
    
    /* 解压之后给节点recompress赋值，使其不能立刻被在此压缩 * Force node to not be immediately re-compresable */
    #define quicklistDecompressNodeForUse(_node) \ do { \ if ((_node) && (_node)->encoding == QUICKLIST_NODE_ENCODING_LZF) { \ __quicklistDecompressNode((_node)); \ (_node)->recompress = 1; \ } \ } while (0)
    
    /* 从node中获取lzf数据，存在data中 * Extract the raw LZF data from this quicklistNode. * Pointer to LZF data is assigned to '*data'. * Return value is the length of compressed LZF data. */
    size_t quicklistGetLzf(const quicklistNode *node, void **data) { 
        quicklistLZF *lzf = (quicklistLZF *)node->zl;
        *data = lzf->compressed;
        return lzf->sz;
    }
    
    #define quicklistAllowsCompression(_ql) ((_ql)->compress != 0)
    
    /* 按压缩规则压缩快速链表中的节点node * Force 'quicklist' to meet compression guidelines set by compress depth. * The only way to guarantee interior nodes get compressed is to iterate * to our "interior" compress depth then compress the next node we find. * If compress depth is larger than the entire list, we return immediately. */
    REDIS_STATIC void __quicklistCompress(const quicklist *quicklist,
                                          quicklistNode *node) { 
        /* 快速链表总长度小于压缩深度则没有压缩的空间，直接返回 * If length is less than our compress depth (from both sides), * we can't compress anything. */
        if (!quicklistAllowsCompression(quicklist) ||
            quicklist->len < (unsigned int)(quicklist->compress * 2))
            return;
    
    #if 0
        /* Optimized cases for small depth counts */
        if (quicklist->compress == 1) { 
            quicklistNode *h = quicklist->head, *t = quicklist->tail;
            quicklistDecompressNode(h);
            quicklistDecompressNode(t);
            if (h != node && t != node)
                quicklistCompressNode(node);
            return;
        } else if (quicklist->compress == 2) { 
            quicklistNode *h = quicklist->head, *hn = h->next, *hnn = hn->next;
            quicklistNode *t = quicklist->tail, *tp = t->prev, *tpp = tp->prev;
            quicklistDecompressNode(h);
            quicklistDecompressNode(hn);
            quicklistDecompressNode(t);
            quicklistDecompressNode(tp);
            if (h != node && hn != node && t != node && tp != node) { 
                quicklistCompressNode(node);
            }
            if (hnn != t) { 
                quicklistCompressNode(hnn);
            }
            if (tpp != h) { 
                quicklistCompressNode(tpp);
            }
            return;
        }
    #endif
    
        /* 首尾压缩深度内的节点不压缩，通过双向循环直至中间 * Iterate until we reach compress depth for both sides of the list.a * Note: because we do length checks at the *top* of this function, * we can skip explicit null checks below. Everything exists. */
        quicklistNode *forward = quicklist->head;
        quicklistNode *reverse = quicklist->tail;
        int depth = 0;
        int in_depth = 0;
    
    	// 深度之外的节点不压缩
        while (depth++ < quicklist->compress) { 
            quicklistDecompressNode(forward);
            quicklistDecompressNode(reverse);
    
            if (forward == node || reverse == node)
                in_depth = 1;
    
    		// 到达中间，循环结束
            if (forward == reverse)
                return;
    
            forward = forward->next;
            reverse = reverse->prev;
        }
    
    	// node如果不在收尾深度内则压缩
        if (!in_depth)
            quicklistCompressNode(node);
    
    	// depth大于2的情况仅出现于forward, reverse刚好需要压缩
        if (depth > 2) { 
            /* At this point, forward and reverse are one node beyond depth */
            quicklistCompressNode(forward);
            quicklistCompressNode(reverse);
        }
    }
    
    // 压缩节点node，如果定义了重压缩则不需要检测直接压缩，否则要检测
    #define quicklistCompress(_ql, _node) \ do { \ if ((_node)->recompress) \ quicklistCompressNode((_node)); \ else \ __quicklistCompress((_ql), (_node)); \ } while (0)
    
    /* 仅压缩需要重压缩的节点 * If we previously used quicklistDecompressNodeForUse(), just recompress. */
    #define quicklistRecompressOnly(_ql, _node) \ do { \ if ((_node)->recompress) \ quicklistCompressNode((_node)); \ } while (0)
    
    /* 插入节点，after表示插入的方向，new_node为新节点 * Insert 'new_node' after 'old_node' if 'after' is 1. * Insert 'new_node' before 'old_node' if 'after' is 0. * Note: 'new_node' is *always* uncompressed, so if we assign it to * head or tail, we do not need to uncompress it. */
    REDIS_STATIC void __quicklistInsertNode(quicklist *quicklist,
                                            quicklistNode *old_node,
                                            quicklistNode *new_node, int after) { 
    	// after为1则在old_node之后插入new_node
    	if (after) { 
            new_node->prev = old_node;
            if (old_node) { 
                new_node->next = old_node->next;
                if (old_node->next)
                    old_node->next->prev = new_node;
                old_node->next = new_node;
            }
            if (quicklist->tail == old_node)
                quicklist->tail = new_node;
        } else { 
            new_node->next = old_node;
            if (old_node) { 
                new_node->prev = old_node->prev;
                if (old_node->prev)
                    old_node->prev->next = new_node;
                old_node->prev = new_node;
            }
            if (quicklist->head == old_node)
                quicklist->head = new_node;
        }
    	
        /* 若是加入第一个元素则初始化首尾 * If this insert creates the only element so far, initialize head/tail. */
        if (quicklist->len == 0) { 
            quicklist->head = quicklist->tail = new_node;
        }
    
    	// 压缩旧节点
        if (old_node)
            quicklistCompress(quicklist, old_node);
    
        quicklist->len++;
    }
    
    /* 对函数__quicklistInsertNode进行封装 * Wrappers for node inserting around existing node. */
    REDIS_STATIC void _quicklistInsertNodeBefore(quicklist *quicklist,
                                                 quicklistNode *old_node,
                                                 quicklistNode *new_node) { 
        __quicklistInsertNode(quicklist, old_node, new_node, 0);
    }
    
    REDIS_STATIC void _quicklistInsertNodeAfter(quicklist *quicklist,
                                                quicklistNode *old_node,
                                                quicklistNode *new_node) { 
        __quicklistInsertNode(quicklist, old_node, new_node, 1);
    }
    
    /*根据sz大小判断优化等级是否满足要求*/
    REDIS_STATIC int
    _quicklistNodeSizeMeetsOptimizationRequirement(const size_t sz,
                                                   const int fill) { 
        if (fill >= 0)
            return 0;
    
        size_t offset = (-fill) - 1;
        if (offset < (sizeof(optimization_level) / sizeof(*optimization_level))) { 
            if (sz <= optimization_level[offset]) { 
                return 1;
            } else { 
                return 0;
            }
        } else { 
            return 0;
        }
    }
    
    #define sizeMeetsSafetyLimit(sz) ((sz) <= SIZE_SAFETY_LIMIT)
    
    // 调用上述函数判断是否可以加入节点
    REDIS_STATIC int _quicklistNodeAllowInsert(const quicklistNode *node,
                                               const int fill, const size_t sz) { 
        //节点为空返回0
        if (unlikely(!node))
            return 0;
    
        int ziplist_overhead;
    	
        /* 前置偏移量加入sz * size of previous offset */
        if (sz < 254)
            ziplist_overhead = 1;
        else
            ziplist_overhead = 5;
    
        /* 后续偏移量加入sz * size of forward offset */
        if (sz < 64)
            ziplist_overhead += 1;
        else if (likely(sz < 16384))
            ziplist_overhead += 2;
        else
            ziplist_overhead += 5;
    
        /* 加入节点后的预估sz * new_sz overestimates if 'sz' encodes to an integer type */
        unsigned int new_sz = node->sz + sz + ziplist_overhead;
    
    	//调用函数判断是否可以插入
        if (likely(_quicklistNodeSizeMeetsOptimizationRequirement(new_sz, fill)))
            return 1;
        else if (!sizeMeetsSafetyLimit(new_sz))
            return 0;
        else if ((int)node->count < fill)
            return 1;
        else
            return 0;
    }
    
    // 融合a和b
    REDIS_STATIC int _quicklistNodeAllowMerge(const quicklistNode *a,
                                              const quicklistNode *b,
                                              const int fill) { 
        if (!a || !b)
            return 0;
    
        /* 融合后大小：需要减去一个头部11字节 * approximate merged ziplist size (- 11 to remove one ziplist * header/trailer) */
        unsigned int merge_sz = a->sz + b->sz - 11;
        if (likely(_quicklistNodeSizeMeetsOptimizationRequirement(merge_sz, fill)))
            return 1;
        else if (!sizeMeetsSafetyLimit(merge_sz))
            return 0;
        else if ((int)(a->count + b->count) <= fill)
            return 1;
        else
            return 0;
    }
    
    #define quicklistNodeUpdateSz(node) \ do { \ (node)->sz = ziplistBlobLen((node)->zl); \ } while (0)
    
    /* 为快速链表头部键入新项 * Add new entry to head node of quicklist. * * 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 (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);
    }
    
    /* 在尾部插入新项，和头部类似，如果可以插入则直接插入 * 否则新建尾部并插入 * Add new entry to tail node of quicklist. * * 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 (likely(
                _quicklistNodeAllowInsert(quicklist->tail, quicklist->fill, sz))) { 
            quicklist->tail->zl =
                ziplistPush(quicklist->tail->zl, value, sz, ZIPLIST_TAIL);
            quicklistNodeUpdateSz(quicklist->tail);
        } else { 
            quicklistNode *node = quicklistCreateNode();
            node->zl = ziplistPush(ziplistNew(), value, sz, ZIPLIST_TAIL);
    
            quicklistNodeUpdateSz(node);
            _quicklistInsertNodeAfter(quicklist, quicklist->tail, node);
        }
        quicklist->count++;
        quicklist->tail->count++;
        return (orig_tail != quicklist->tail);
    }
    
    /* 在快速链表尾部插入一个新节点保存压缩链表 * Create new node consisting of a pre-formed ziplist. * Used for loading RDBs where entire ziplists have been stored * to be retrieved later. */
    void quicklistAppendZiplist(quicklist *quicklist, unsigned char *zl) { 
        quicklistNode *node = quicklistCreateNode();
    
        node->zl = zl;
        node->count = ziplistLen(node->zl);
        node->sz = ziplistBlobLen(zl);
    
        _quicklistInsertNodeAfter(quicklist, quicklist->tail, node);
        quicklist->count += node->count;
    }
    
    /* 将压缩链表zl添加至快速链表中。 * Append all values of ziplist 'zl' individually into 'quicklist'. * * This allows us to restore old RDB ziplists into new quicklists * with smaller ziplist sizes than the saved RDB ziplist. * * Returns 'quicklist' argument. Frees passed-in ziplist 'zl' */
    quicklist *quicklistAppendValuesFromZiplist(quicklist *quicklist,
                                                unsigned char *zl) { 
        unsigned char *value;
        unsigned int sz;
        long long longval;
        char longstr[32] = { 0};
    
        unsigned char *p = ziplistIndex(zl, 0);
    	
    	//循环读出压缩链表各项，并依次存在快速链表尾部
        while (ziplistGet(p, &value, &sz, &longval)) { 
            if (!value) { 
                /* Write the longval as a string so we can re-add it */
                sz = ll2string(longstr, sizeof(longstr), longval);
                value = (unsigned char *)longstr;
            }
            quicklistPushTail(quicklist, value, sz);
            p = ziplistNext(zl, p);
        }
        zfree(zl);
        return quicklist;
    }
    
    /* 根据已有的压缩链表创建快速链表：调用上面的函数实现，即加入空快速链表 * Create new (potentially multi-node) quicklist from a single existing ziplist. * * Returns new quicklist. Frees passed-in ziplist 'zl'. */
    quicklist *quicklistCreateFromZiplist(int fill, int compress,
                                          unsigned char *zl) { 
        return quicklistAppendValuesFromZiplist(quicklistNew(fill, compress), zl);
    }
    
    #define quicklistDeleteIfEmpty(ql, n) \ do { \ if ((n)->count == 0) { \ __quicklistDelNode((ql), (n)); \ (n) = NULL; \ } \ } while (0)
    
    //删除快速链表节点
    REDIS_STATIC void __quicklistDelNode(quicklist *quicklist,
                                         quicklistNode *node) { 
        //处理前后节点指针关系
        if (node->next)
            node->next->prev = node->prev;
        if (node->prev)
            node->prev->next = node->next;
    
    	//判断首/尾节点特殊情况
        if (node == quicklist->tail) { 
            quicklist->tail = node->prev;
        }
    
        if (node == quicklist->head) { 
            quicklist->head = node->next;
        }
    
        /* 内部节点的删除使得整个链表需要重新根据压缩深度整理 * If we deleted a node within our compress depth, we * now have compressed nodes needing to be decompressed. */
        __quicklistCompress(quicklist, NULL);
    
    	//计数减少
        quicklist->count -= node->count;
    
    	//释放节点
        zfree(node->zl);
        zfree(node);
        quicklist->len--;
    }
    
    /* 根据给出的节点和指针删除指定压缩链表表项 * Delete one entry from list given the node for the entry and a pointer * to the entry in the node. * * Note: quicklistDelIndex() *requires* uncompressed nodes because you * already had to get *p from an uncompressed node somewhere. * * Returns 1 if the entire node was deleted, 0 if node still exists. * Also updates in/out param 'p' with the next offset in the ziplist. */
    REDIS_STATIC int quicklistDelIndex(quicklist *quicklist, quicklistNode *node,
                                       unsigned char **p) { 
        int gone = 0;
    
    	//删除zl中的p指向的节点，计数递减
        node->zl = ziplistDelete(node->zl, p);
        node->count--;
    
    	//若该zl中已无节点则删除该zl返回1，否则更新快速链表大小返回0
        if (node->count == 0) { 
            gone = 1;
            __quicklistDelNode(quicklist, node);
        } else { 
            quicklistNodeUpdateSz(node);
        }
    	//快速链表节点递减
        quicklist->count--;
        /* If we deleted the node, the original node is no longer valid */
        return gone ? 1 : 0;
    }
    
    /* 删除快速链表表项 * Delete one element represented by 'entry' * * 'entry' stores enough metadata to delete the proper position in * the correct ziplist in the correct quicklist node. */
    void quicklistDelEntry(quicklistIter *iter, quicklistEntry *entry) { 
    
    	//保留前后指针
        quicklistNode *prev = entry->node->prev;
        quicklistNode *next = entry->node->next;
    
    	//根据表项entry和索引zi删除节点
        int deleted_node = quicklistDelIndex((quicklist *)entry->quicklist,
                                             entry->node, &entry->zi);
    
        /* after delete, the zi is now invalid for any future usage. */
        iter->zi = NULL;
    
        /* 若当前节点被删除，则需要更新迭代器 * If current node is deleted, we must update iterator node and offset. */
        if (deleted_node) { 
            if (iter->direction == AL_START_HEAD) { 
                iter->current = next;
                iter->offset = 0;
            } else if (iter->direction == AL_START_TAIL) { 
                iter->current = prev;
                iter->offset = -1;
            }
        }
    	
        /* else if (!deleted_node), no changes needed. * we already reset iter->zi above, and the existing iter->offset * doesn't move again because: * - [1, 2, 3] => delete offset 1 => [1, 3]: next element still offset 1 * - [1, 2, 3] => delete offset 0 => [2, 3]: next element still offset 0 * if we deleted the last element at offet N and now * length of this ziplist is N-1, the next call into * quicklistNext() will jump to the next node. */
    }