redis源码解析（十五）快速链表API功能函数解析

矫情吗；* 2024-04-18 23:40 70阅读 0赞

### 一. 前言 ###

本文继前文基础上继续分析剩余的快速链表函数源码。

### 二. 源码分析 ###

/* Replace quicklist entry at offset 'index' by 'data' with length 'sz'. * * Returns 1 if replace happened. * Returns 0 if replace failed and no changes happened. */
    int quicklistReplaceAtIndex(quicklist *quicklist, long index, void *data,
                                int sz) { 
        quicklistEntry entry;
        if (likely(quicklistIndex(quicklist, index, &entry))) { 
            /* quicklistIndex provides an uncompressed node */
            entry.node->zl = ziplistDelete(entry.node->zl, &entry.zi);
            entry.node->zl = ziplistInsert(entry.node->zl, entry.zi, data, sz);
            quicklistNodeUpdateSz(entry.node);
            quicklistCompress(quicklist, entry.node);
            return 1;
        } else { 
            return 0;
        }
    }
    
    /* 融合两个节点的压缩链表，返回融合后的新节点 * Given two nodes, try to merge their ziplists. * * This helps us not have a quicklist with 3 element ziplists if * our fill factor can handle much higher levels. * * Note: 'a' must be to the LEFT of 'b'. * * After calling this function, both 'a' and 'b' should be considered * unusable. The return value from this function must be used * instead of re-using any of the quicklistNode input arguments. * * Returns the input node picked to merge against or NULL if * merging was not possible. */
    REDIS_STATIC quicklistNode *_quicklistZiplistMerge(quicklist *quicklist,
                                                       quicklistNode *a,
                                                       quicklistNode *b) { 
        D("Requested merge (a,b) (%u, %u)", a->count, b->count);
    
    	//展开节点
        quicklistDecompressNode(a);
        quicklistDecompressNode(b);
    
    	//压缩链表融合
        if ((ziplistMerge(&a->zl, &b->zl))) { 
            /* We merged ziplists! Now remove the unused quicklistNode. */
            quicklistNode *keep = NULL, *nokeep = NULL;
    
    		//根据融合结果选择保留a还是b
            if (!a->zl) { 
                nokeep = a;
                keep = b;
            } else if (!b->zl) { 
                nokeep = b;
                keep = a;
            }
    
    		//更新信息
            keep->count = ziplistLen(keep->zl);
            quicklistNodeUpdateSz(keep);
    
    		//删除无用节点，对新节点进行压缩处理
            nokeep->count = 0;
            __quicklistDelNode(quicklist, nokeep);
            quicklistCompress(quicklist, keep);
            return keep;
        } else { 
            /* else, the merge returned NULL and nothing changed. */
            return NULL;
        }
    }
    
    /* 对快速链表从中间开始两边分别融合：前2个+中间+后2个融合成1个节点 * Attempt to merge ziplists within two nodes on either side of 'center'. * * We attempt to merge: * - (center->prev->prev, center->prev) * - (center->next, center->next->next) * - (center->prev, center) * - (center, center->next) */
    REDIS_STATIC void _quicklistMergeNodes(quicklist *quicklist,
                                           quicklistNode *center) { 
        int fill = quicklist->fill;
        quicklistNode *prev, *prev_prev, *next, *next_next, *target;
        prev = prev_prev = next = next_next = target = NULL;
    
    	//获取前向节点
        if (center->prev) { 
            prev = center->prev;
            if (center->prev->prev)
                prev_prev = center->prev->prev;
        }
    
    	//获取后向节点
        if (center->next) { 
            next = center->next;
            if (center->next->next)
                next_next = center->next->next;
        }
    
        /* 尝试前向节点融合 * Try to merge prev_prev and prev */
        if (_quicklistNodeAllowMerge(prev, prev_prev, fill)) { 
            _quicklistZiplistMerge(quicklist, prev_prev, prev);
            prev_prev = prev = NULL; /* they could have moved, invalidate them. */
        }
    
        /* 尝试后向节点融合 * Try to merge next and next_next */
        if (_quicklistNodeAllowMerge(next, next_next, fill)) { 
            _quicklistZiplistMerge(quicklist, next, next_next);
            next = next_next = NULL; /* they could have moved, invalidate them. */
        }
    
        /* 中间节点和前向进行融合 * Try to merge center node and previous node */
        if (_quicklistNodeAllowMerge(center, center->prev, fill)) { 
            target = _quicklistZiplistMerge(quicklist, center->prev, center);
            center = NULL; /* center could have been deleted, invalidate it. */
        } else { 
            /* else, we didn't merge here, but target needs to be valid below. */
            target = center;
        }
    
        /* 和后向新节点进行融合 * Use result of center merge (or original) to merge with next node. */
        if (_quicklistNodeAllowMerge(target, target->next, fill)) { 
            _quicklistZiplistMerge(quicklist, target, target->next);
        }
    }
    
    /* 根据offset和after分割快速链表的节点 * after为1则返回包含从offset到结尾的值的节点，0到offset的值保存在传参指针node中 * after为0则刚好相反 * Split 'node' into two parts, parameterized by 'offset' and 'after'. * * The 'after' argument controls which quicklistNode gets returned. * If 'after'==1, returned node has elements after 'offset'. * input node keeps elements up to 'offset', including 'offset'. * If 'after'==0, returned node has elements up to 'offset', including 'offset'. * input node keeps elements after 'offset'. * * If 'after'==1, returned node will have elements _after_ 'offset'. * The returned node will have elements [OFFSET+1, END]. * The input node keeps elements [0, OFFSET]. * * If 'after'==0, returned node will keep elements up to and including 'offset'. * The returned node will have elements [0, OFFSET]. * The input node keeps elements [OFFSET+1, END]. * * The input node keeps all elements not taken by the returned node. * * Returns newly created node or NULL if split not possible. */
    REDIS_STATIC quicklistNode *_quicklistSplitNode(quicklistNode *node, int offset,
                                                    int after) { 
        //获取压缩链表的大小
        size_t zl_sz = node->sz;
    
    	//创建新快速链表节点保存
        quicklistNode *new_node = quicklistCreateNode();
        new_node->zl = zmalloc(zl_sz);
    
        /* 拷贝压缩链表到新节点 * Copy original ziplist so we can split it */
        memcpy(new_node->zl, node->zl, zl_sz);
    
        /* -1 here means "continue deleting until the list ends" */
        int orig_start = after ? offset + 1 : 0;
        int orig_extent = after ? -1 : offset;
        int new_start = after ? 0 : offset;
        int new_extent = after ? offset + 1 : -1;
    
        D("After %d (%d); ranges: [%d, %d], [%d, %d]", after, offset, orig_start,
          orig_extent, new_start, new_extent);
    
    	//删除orig_start到orig_extent的压缩链表节点项
        node->zl = ziplistDeleteRange(node->zl, orig_start, orig_extent);
        node->count = ziplistLen(node->zl);
        quicklistNodeUpdateSz(node);
    	
    	//删除new_start到new_extent的压缩链表节点项
        new_node->zl = ziplistDeleteRange(new_node->zl, new_start, new_extent);
        new_node->count = ziplistLen(new_node->zl);
        quicklistNodeUpdateSz(new_node);
    
        D("After split lengths: orig (%d), new (%d)", node->count, new_node->count);
        return new_node;
    }
    
    /* 根据after的值在快速链表项前/后插入新项，值为value,大小为sz * Insert a new entry before or after existing entry 'entry'. * * If after == 1, the new value is inserted after 'entry', otherwise * the new value is inserted before 'entry'. */
    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) { 
            /* 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;
        }
    
        /* 检测当前节点是否可以插入 * Populate accounting flags for easier boolean checks later */
        if (!_quicklistNodeAllowInsert(node, fill, sz)) { 
            D("Current node is full with count %d with requested fill %lu",
              node->count, fill);
            full = 1;
        }
    
    	//尾部插入的情况，检测是否可以插入
        if (after && (entry->offset == node->count)) { 
            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;
            }
        }
    
        /* 根据上面的检测决定如何、在哪里插入新元素 * Now determine where and how to insert the new element */
        if (!full && after) { 
            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) { 
            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) { 
            /* If we are: at tail, next has free space, and inserting after: * - insert entry at head of next 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) { 
            /* If we are: at head, previous has free space, and inserting before: * - insert entry at tail of previous 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))) { 
            /* If we are: full, and our prev/next is full, then: * - create new node and attach to quicklist */
            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) { 
            /* else, node is full we need to split it. */
            /* covers both after and !after cases */
            D("\tsplitting node...");
            quicklistDecompressNodeForUse(node);
            new_node = _quicklistSplitNode(node, entry->offset, after);
            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++;
    }
    
    void quicklistInsertBefore(quicklist *quicklist, quicklistEntry *entry,
                               void *value, const size_t sz) { 
        _quicklistInsert(quicklist, entry, value, sz, 0);
    }
    
    void quicklistInsertAfter(quicklist *quicklist, quicklistEntry *entry,
                              void *value, const size_t sz) { 
        _quicklistInsert(quicklist, entry, value, sz, 1);
    }
    
    /* 删除一个范围内的快速链表 * Delete a range of elements from the quicklist. * * elements may span across multiple quicklistNodes, so we * have to be careful about tracking where we start and end. * * Returns 1 if entries were deleted, 0 if nothing was deleted. */
    int quicklistDelRange(quicklist *quicklist, const long start,
                          const long count) { 
        if (count <= 0)
            return 0;
    
        unsigned long extent = count; /* range is inclusive of start position */
    
    	//考虑到可能范围超过了存在的节点数，因此需要对start和count进行判断处理
        if (start >= 0 && extent > (quicklist->count - start)) { 
            /* if requesting delete more elements than exist, limit to list size. */
            extent = quicklist->count - start;
        } else if (start < 0 && extent > (unsigned long)(-start)) { 
            /* else, if at negative offset, limit max size to rest of list. */
            extent = -start; /* c.f. LREM -29 29; just delete until end. */
        }
    
    	//根据start查找入口节点entry
        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) { 
                /* 若需要删除的多于节点总数，则直接删除整个节点 * If we are deleting more than the count of this node, we * can just delete the entire node without ziplist math. */
                delete_entire_node = 1;
                del = node->count;
            } else if (entry.offset >= 0 && extent >= node->count) { 
                /* 根据需要删除节点数计算删除数 * If deleting more nodes after this one, calculate delete based * on size of current node. */
                del = node->count - entry.offset;
            } else if (entry.offset < 0) { 
                /* 负值表示删除整个范围 * If offset is negative, we are in the first run of this loop * and we are deleting the entire range * from this start offset to end of list. Since the Negative * offset is the number of elements until the tail of the list, * just use it directly as the deletion count. */
                del = -entry.offset;
    
                /* If the positive offset is greater than the remaining extent, * we only delete the remaining extent, not the entire offset. */
                if (del > extent)
                    del = extent;
            } else { 
                /* else, we are deleting less than the extent of this node, so * use extent directly. */
                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) { 
                __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;
    
            node = next;
    
            entry.offset = 0;
        }
        return 1;
    }
    
    /* Passthrough to ziplistCompare() */
    int quicklistCompare(unsigned char *p1, unsigned char *p2, int p2_len) { 
        return ziplistCompare(p1, p2, p2_len);
    }
    
    /* 返回快速列表迭代器 * Returns a quicklist iterator 'iter'. After the initialization every * call to quicklistNext() will return the next element of the quicklist. */
    quicklistIter *quicklistGetIterator(const quicklist *quicklist, int direction) { 
        quicklistIter *iter;
    
        iter = zmalloc(sizeof(*iter));
    
    	//根据方向赋值iter
        if (direction == AL_START_HEAD) { 
            iter->current = quicklist->head;
            iter->offset = 0;
        } else if (direction == AL_START_TAIL) { 
            iter->current = quicklist->tail;
            iter->offset = -1;
        }
    
        iter->direction = direction;
        iter->quicklist = quicklist;
    
        iter->zi = NULL;
    
        return iter;
    }
    
    /* 在指定位置idx初始化一个iter迭代器指针 * Initialize an iterator at a specific offset 'idx' and make the iterator * return nodes in 'direction' direction. */
    quicklistIter *quicklistGetIteratorAtIdx(const quicklist *quicklist,
                                             const int direction,
                                             const long long idx) { 
        quicklistEntry entry;
    
    	//原理就是先找到指定节点，再在指定节点获取iter，再给其赋值
        if (quicklistIndex(quicklist, idx, &entry)) { 
            quicklistIter *base = quicklistGetIterator(quicklist, direction);
            base->zi = NULL;
            base->current = entry.node;
            base->offset = entry.offset;
            return base;
        } else { 
            return NULL;
        }
    }
    
    /* Release iterator. * If we still have a valid current node, then re-encode current node. */
    void quicklistReleaseIterator(quicklistIter *iter) { 
        if (iter->current)
            quicklistCompress(iter->quicklist, iter->current);
    
        zfree(iter);
    }
    
    /* 获取下一个iter * Get next element in iterator. * * Note: You must NOT insert into the list while iterating over it. * You *may* delete from the list while iterating using the * quicklistDelEntry() function. * If you insert into the quicklist while iterating, you should * re-create the iterator after your addition. * * iter = quicklistGetIterator(quicklist,<direction>); * quicklistEntry entry; * while (quicklistNext(iter, &entry)) { * if (entry.value) * [[ use entry.value with entry.sz ]] * else * [[ use entry.longval ]] * } * * Populates 'entry' with values for this iteration. * Returns 0 when iteration is complete or if iteration not possible. * If return value is 0, the contents of 'entry' are not valid. */
    int quicklistNext(quicklistIter *iter, quicklistEntry *entry) { 
        initEntry(entry);
    
    	//空指针异常处理
        if (!iter) { 
            D("Returning because no iter!");
            return 0;
        }
    
    	//记录当前iter
        entry->quicklist = iter->quicklist;
        entry->node = iter->current;
    
    	//节点空则返回
        if (!iter->current) { 
            D("Returning because current node is NULL")
            return 0;
        }
    
    	//函数指针用于根据方向判断调用上一个还是下一个的函数
        unsigned char *(*nextFn)(unsigned char *, unsigned char *) = NULL;
        int offset_update = 0;
    
    	//若zi为空则获取当前索引
        if (!iter->zi) { 
            /* If !zi, use current index. */
            quicklistDecompressNodeForUse(iter->current);
            iter->zi = ziplistIndex(iter->current->zl, iter->offset);
        } else { 
            /* else, use existing iterator offset and get prev/next as necessary. */
            if (iter->direction == AL_START_HEAD) { 
                nextFn = ziplistNext;
                offset_update = 1;
            } else if (iter->direction == AL_START_TAIL) { 
                nextFn = ziplistPrev;
                offset_update = -1;
            }
            iter->zi = nextFn(iter->current->zl, iter->zi);
            iter->offset += offset_update;
        }
    
    	//记录zi和offset
        entry->zi = iter->zi;
        entry->offset = iter->offset;
    
    	//若zi大于0则直接获取并返回，否则需要进入下一个快速链表项
        if (iter->zi) { 
            /* Populate value from existing ziplist position */
            ziplistGet(entry->zi, &entry->value, &entry->sz, &entry->longval);
            return 1;
        } else { 
            /* We ran out of ziplist entries. * Pick next node, update offset, then re-run retrieval. */
            quicklistCompress(iter->quicklist, iter->current);
            if (iter->direction == AL_START_HEAD) { 
                /* Forward traversal */
                D("Jumping to start of next node");
                iter->current = iter->current->next;
                iter->offset = 0;
            } else if (iter->direction == AL_START_TAIL) { 
                /* Reverse traversal */
                D("Jumping to end of previous node");
                iter->current = iter->current->prev;
                iter->offset = -1;
            }
            iter->zi = NULL;
            return quicklistNext(iter, entry);
        }
    }
    
    /* 复制快速链表，返回复制成功的原快速链表 * Duplicate the quicklist. * On success a copy of the original quicklist is returned. * * The original quicklist both on success or error is never modified. * * Returns newly allocated quicklist. */
    quicklist *quicklistDup(quicklist *orig) { 
        quicklist *copy;
    
    	//创建新的链表
        copy = quicklistNew(orig->fill, orig->compress);
    
    	//循环获取每一个快速链表节点并拷贝
        for (quicklistNode *current = orig->head; current;
             current = current->next) { 
            quicklistNode *node = quicklistCreateNode();
    
    		//根据编码类型不同进行不同赋值
            if (current->encoding == QUICKLIST_NODE_ENCODING_LZF) { 
                quicklistLZF *lzf = (quicklistLZF *)current->zl;
                size_t lzf_sz = sizeof(*lzf) + lzf->sz;
                node->zl = zmalloc(lzf_sz);
                memcpy(node->zl, current->zl, lzf_sz);
            } else if (current->encoding == QUICKLIST_NODE_ENCODING_RAW) { 
                node->zl = zmalloc(current->sz);
                memcpy(node->zl, current->zl, current->sz);
            }
    
            node->count = current->count;
            copy->count += node->count;
            node->sz = current->sz;
            node->encoding = current->encoding;
    
    		//在拷贝快速链表中插入该项
            _quicklistInsertNodeAfter(copy, copy->tail, node);
        }
    
        /* copy->count must equal orig->count here */
        return copy;
    }
    
    /* 根据idx返回对应的快速链表项 * Populate 'entry' with the element at the specified zero-based index * where 0 is the head, 1 is the element next to head * and so on. Negative integers are used in order to count * from the tail, -1 is the last element, -2 the penultimate * and so on. If the index is out of range 0 is returned. * * Returns 1 if element found * Returns 0 if element not found */
    int quicklistIndex(const quicklist *quicklist, const long long idx,
                       quicklistEntry *entry) { 
        quicklistNode *n;
        unsigned long long accum = 0;
        unsigned long long index;
        int forward = idx < 0 ? 0 : 1; /* < 0 -> reverse, 0+ -> forward */
    
        initEntry(entry);
        entry->quicklist = quicklist;
    
    	//根据forward判断方向
        if (!forward) { 
            index = (-idx) - 1;
            n = quicklist->tail;
        } else { 
            index = idx;
            n = quicklist->head;
        }
    
        if (index >= quicklist->count)
            return 0;
    
    	//查找节点
        while (likely(n)) { 
            if ((accum + n->count) > index) { 
                break;
            } else { 
                D("Skipping over (%p) %u at accum %lld", (void *)n, n->count,
                  accum);
                accum += n->count;
                n = forward ? n->next : n->prev;
            }
        }
    
        if (!n)
            return 0;
    
        D("Found node: %p at accum %llu, idx %llu, sub+ %llu, sub- %llu", (void *)n,
          accum, index, index - accum, (-index) - 1 + accum);
    
    	//根据找到的节点赋值
        entry->node = n;
        if (forward) { 
            /* forward = normal head-to-tail offset. */
            entry->offset = index - accum;
        } else { 
            /* reverse = need negative offset for tail-to-head, so undo * the result of the original if (index < 0) above. */
            entry->offset = (-index) - 1 + accum;
        }
    
    	//解压节点并赋值
        quicklistDecompressNodeForUse(entry->node);
        entry->zi = ziplistIndex(entry->node->zl, entry->offset);
        ziplistGet(entry->zi, &entry->value, &entry->sz, &entry->longval);
        /* The caller will use our result, so we don't re-compress here. * The caller can recompress or delete the node as needed. */
        return 1;
    }
    
    /* 旋转快速链表：首尾位置互换 * Rotate quicklist by moving the tail element to the head. */
    void quicklistRotate(quicklist *quicklist) { 
        if (quicklist->count <= 1)
            return;
    
        /* 获取尾部节点 * First, get the tail entry */
        unsigned char *p = ziplistIndex(quicklist->tail->zl, -1);
        unsigned char *value;
        long long longval;
        unsigned int sz;
        char longstr[32] = { 0};
        ziplistGet(p, &value, &sz, &longval);
    
        /* 若尾节点值为空则赋值0 * If value found is NULL, then ziplistGet populated longval instead */
        if (!value) { 
            /* Write the longval as a string so we can re-add it */
            sz = ll2string(longstr, sizeof(longstr), longval);
            value = (unsigned char *)longstr;
        }
    
        /* 将尾部节点加入头部 * Add tail entry to head (must happen before tail is deleted). */
        quicklistPushHead(quicklist, value, sz);
    
        /* 针对仅有一个节点的特殊处理：重新获取p * If quicklist has only one node, the head ziplist is also the * tail ziplist and PushHead() could have reallocated our single ziplist, * which would make our pre-existing 'p' unusable. */
        if (quicklist->len == 1) { 
            p = ziplistIndex(quicklist->tail->zl, -1);
        }
    
        /* Remove tail entry. */
        quicklistDelIndex(quicklist, quicklist->tail, &p);
    }
    
    /* 从快速链表弹出一项，返回数据指针。where必须为首或者尾部，不能弹出中间项 * pop from quicklist and return result in 'data' ptr. Value of 'data' * is the return value of 'saver' function pointer if the data is NOT a number. * * If the quicklist element is a long long, then the return value is returned in * 'sval'. * * Return value of 0 means no elements available. * Return value of 1 means check 'data' and 'sval' for values. * If 'data' is set, use 'data' and 'sz'. Otherwise, use 'sval'. */
    int quicklistPopCustom(quicklist *quicklist, int where, unsigned char **data,
                           unsigned int *sz, long long *sval,
                           void *(*saver)(unsigned char *data, unsigned int sz)) { 
        unsigned char *p;
        unsigned char *vstr;
        unsigned int vlen;
        long long vlong;
        int pos = (where == QUICKLIST_HEAD) ? 0 : -1;
    
        if (quicklist->count == 0)
            return 0;
    
        if (data)
            *data = NULL;
        if (sz)
            *sz = 0;
        if (sval)
            *sval = -123456789;
    
    	//判断首尾
        quicklistNode *node;
        if (where == QUICKLIST_HEAD && quicklist->head) { 
            node = quicklist->head;
        } else if (where == QUICKLIST_TAIL && quicklist->tail) { 
            node = quicklist->tail;
        } else { 
            return 0;
        }
    
        p = ziplistIndex(node->zl, pos);
        if (ziplistGet(p, &vstr, &vlen, &vlong)) { 
            if (vstr) { 
                if (data)
                    *data = saver(vstr, vlen);
                if (sz)
                    *sz = vlen;
            } else { 
                if (data)
                    *data = NULL;
                if (sval)
                    *sval = vlong;
            }
            quicklistDelIndex(quicklist, node, &p);
            return 1;
        }
        return 0;
    }
    
    /* Return a malloc'd copy of data passed in */
    REDIS_STATIC void *_quicklistSaver(unsigned char *data, unsigned int sz) { 
        unsigned char *vstr;
        if (data) { 
            vstr = zmalloc(sz);
            memcpy(vstr, data, sz);
            return vstr;
        }
        return NULL;
    }
    
    /* Default pop function * * Returns malloc'd value from quicklist */
    int quicklistPop(quicklist *quicklist, int where, unsigned char **data,
                     unsigned int *sz, long long *slong) { 
        unsigned char *vstr;
        unsigned int vlen;
        long long vlong;
        if (quicklist->count == 0)
            return 0;
        int ret = quicklistPopCustom(quicklist, where, &vstr, &vlen, &vlong,
                                     _quicklistSaver);
        if (data)
            *data = vstr;
        if (slong)
            *slong = vlong;
        if (sz)
            *sz = vlen;
        return ret;
    }
    
    /* Wrapper to allow argument-based switching between HEAD/TAIL pop */
    void quicklistPush(quicklist *quicklist, void *value, const size_t sz,
                       int where) { 
        if (where == QUICKLIST_HEAD) { 
            quicklistPushHead(quicklist, value, sz);
        } else if (where == QUICKLIST_TAIL) { 
            quicklistPushTail(quicklist, value, sz);
        }
    }