redis的list数据结构简介

/* 
 * @param zl：插入的zplist
 * @param p：插入的位置
 * @param s：待插入的字符串
 * @param slen：待插入的字符串的长度
 * Insert item at "p". 
 */
unsigned char *__ziplistInsert(unsigned char *zl, unsigned char *p,
					 unsigned char *s, unsigned int slen) {
	/* curlen表示ziplist的插入前的长度
	   reqlen表示存储新插入结点的长度
	*/
    size_t curlen = intrev32ifbe(ZIPLIST_BYTES(zl)), reqlen;
	/* prevlen:待插入结点的前一个结点的长度
	   prevlensize:存储prvlen字段所需的长度*/
    unsigned int prevlensize, prevlen = 0;
    size_t offset;
    int nextdiff = 0;
    unsigned char encoding = 0;
    long long value = 123456789; /* initialized to avoid warning. Using a value
                                    that is easy to see if for some reason
                                    we use it uninitialized. */
    zlentry tail;

    /* Find out prevlen for the entry that is inserted. */
	/* 得到prvelen*/
    if (p[0] != ZIP_END) {
		/* 插入位置不是最末尾，那么p指向的是一个正常结点
		   新插入结点的前一个结点是p结点的前一个结点
		   所以prevlen等于p结点的prevlen字段*/
        ZIP_DECODE_PREVLEN(p, prevlensize, prevlen);
    } else {
		/* 插入位置是最末尾*/
        unsigned char *ptail = ZIPLIST_ENTRY_TAIL(zl);
        if (ptail[0] != ZIP_END) {
			/* 当前list不为空时，新插入结点的前一个结点是尾结点
			   所以prevlen等于尾结点的长度*/
            prevlen = zipRawEntryLength(ptail);
        }
    }

    /* See if the entry can be encoded */
	/* 检验新插入的数据是否能编码为整数存储*/
    if (zipTryEncoding(s,slen,&value,&encoding)) {
        /* 'encoding' is set to the appropriate integer encoding */
		/* 可以编码为整数，数据(entry-data字段)的长度*/
        reqlen = zipIntSize(encoding);
    } else {
        /* 'encoding' is untouched, however zipStoreEntryEncoding will use the
         * string length to figure out how to encode it. */
		 /* 编码为字符串存储时，数据(entry-data字段)的长度*/
        reqlen = slen;
    }
    /* We need space for both the length of the previous entry and
     * the length of the payload. */
	 /* 计算prevlen字段的长度*/
    reqlen += zipStorePrevEntryLength(NULL,prevlen);
	/* 计算encoding字段的长度*/
    reqlen += zipStoreEntryEncoding(NULL,encoding,slen);

    /* When the insert position is not equal to the tail, we need to
     * make sure that the next entry can hold this entry's length in
     * its prevlen field. */
	/* 如果p指向一个正常结点时，插入后，p结点的前一个结点变成了新插入的结点
	   p结点的prevlen的值可能发生了变化，因为prevlen采用变长编码，
	   p结点的prevlen占的空间长度也可能发生变化。
	   这是先计算prevlen长度的变化值，后面ziplist扩容时可以正确计算这部分空间的变化*/
    int forcelarge = 0;	/*结点p的prevlen字段是否变长*/
	/*nextdiff表示变化的字节数*/
    nextdiff = (p[0] != ZIP_END) ? zipPrevLenByteDiff(p,reqlen) : 0;
    if (nextdiff == -4 && reqlen < 4) {
        nextdiff = 0;
        forcelarge = 1;
    }

    /* Store offset because a realloc may change the address of zl. */
	/* zl进行扩容 
	   扩容前存储结点p的偏移量，因为扩容后zl的地址可能发生变化*/
    offset = p-zl;
    zl = ziplistResize(zl,curlen+reqlen+nextdiff);
    p = zl+offset;

	/* 扩容后，空间已经足够
	   先把结点p及它后面的数据整体右移
	   移动后，尾结点发生了变化，同时更新zltail字段
	   */
    /* Apply memory move when necessary and update tail offset. */
    if (p[0] != ZIP_END) {
        /* Subtract one because of the ZIP_END bytes */
        memmove(p+reqlen,p-nextdiff,curlen-offset-1+nextdiff);

        /* Encode this entry's raw length in the next entry. */
		/* 更新结点p的prevlen字段 */
        if (forcelarge)
            zipStorePrevEntryLengthLarge(p+reqlen,reqlen);
        else
            zipStorePrevEntryLength(p+reqlen,reqlen);

        /* Update offset for tail */
		/* 更新zltail字段 */
        ZIPLIST_TAIL_OFFSET(zl) =
            intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))+reqlen);

        /* When the tail contains more than one entry, we need to take
         * "nextdiff" in account as well. Otherwise, a change in the
         * size of prevlen doesn't have an effect on the *tail* offset. */
		/* 结点p的prevlen字段长度的变化可能也会影响zltail字段
		   1. 如果结点p是尾结点那么不影响
		   2. 如果结点p不是尾结点那么影响*/
        zipEntry(p+reqlen, &tail);
        if (p[reqlen+tail.headersize+tail.len] != ZIP_END) {
            ZIPLIST_TAIL_OFFSET(zl) =
                intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))+nextdiff);
        }
    } else {
        /* This element will be the new tail. */
		/* 插入最末尾的情况下，不需要整体平移，只更新zltail字段*/
        ZIPLIST_TAIL_OFFSET(zl) = intrev32ifbe(p-zl);
    }

    /* When nextdiff != 0, the raw length of the next entry has changed, so
     * we need to cascade the update throughout the ziplist */
	/* 结点p的长度发生变化时，处理可能发生连锁更新*/
    if (nextdiff != 0) {
        offset = p-zl;
        zl = __ziplistCascadeUpdate(zl,p+reqlen);
        p = zl+offset;
    }

    /* Write the entry */
	/* 写入新插入的元素*/
    p += zipStorePrevEntryLength(p,prevlen);
    p += zipStoreEntryEncoding(p,encoding,slen);
    if (ZIP_IS_STR(encoding)) {
        memcpy(p,s,slen);
    } else {
        zipSaveInteger(p,value,encoding);
    }
	/* 更新zllen字段*/
    ZIPLIST_INCR_LENGTH(zl,1);
    return zl;
}

/* 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'. */
/* 在entry结点前面或者后面插入一个新的结点
 * 如果after==1，新的结点插入entry结点后面
 * 其他情况，新的结点插入entry结点前面
 * @param quicklist：结点插入的quicklist
 * @param entry：插入位置
 * @param value：新插入结点的值
 * @param sz：value的长度
 * @param after：after==1 插入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;
    /* fill参数和单个ziplist的容量限制有关，目前有两种方式
     * 1. 按照据占在空间，这是默认方式，不超过8Kb
     * 2. 按照ziplist中结点个数限制，在配置文件(list-max-ziplist-size)中配置
     */
    int fill = quicklist->fill;
	/* quicklistNode结构体表示quicklist中一个ziplist*/
    quicklistNode *node = entry->node;
    quicklistNode *new_node = NULL;

    if (!node) {
        /* we have no reference node, so let's create only node in the list */
        /*ziplist为空的情况，新建ziplist并插入结点*/
        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 */
    /* 根据fill参数的设置，检查当前ziplist是否超过容量限制
       full = 1表示当前ziplist达到容量限制*/
    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)) {
        /*插入位置是当前ziplist末尾时，检查下一个ziplist是否达到容量限制
         * full_next=1 表示下一个ziplist已经达到容量限制
         */
        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)) {
        /*插入位置是当前ziplist开头时，检查上一个ziplist是否达到容量限制
         * full_prev=1 表示上一个ziplist已经达到容量限制
         */
        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) {
        /* 当前ziplist未达到容量限制，插入末尾*/
        D("Not full, inserting after current position.");
        /* ziplist中间的结点可能是压缩存储的(配置文件里的list-compress-depth控制)，
          如果是，这里会先解压*/
        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);
        }
        //更新ziplist的结点数
        node->count++;
        //更新quicklist的结点数
        quicklistNodeUpdateSz(node);
        //重新压缩，如果需要的话
        quicklistRecompressOnly(quicklist, node);
    } else if (!full && !after) {
        /* 当前ziplist未达到容量限制，插入开头*/
        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) {
        /* 当前ziplist达到容量限制，插入末尾，下一个ziplist末达到容量限制
           插入下一个ziplist开头*/
        /* 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) {
        /* 当前ziplist达到容量限制，插入末尾，上一个ziplist末达到容量限制
           插入下一个ziplist的结尾*/
        /* 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))) {
        /*插入位置在ziplist开头或末尾，而且ziplist都达到容量限制，
          直接创建新的ziplist*/
        /* 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) {
        /*插入位置在ziplist中间，而且ziplist都达到容量限制，
          当前ziplist分裂为两个ziplist*/
        /* 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++;
}

/* Insert, delete or replace the specified element 'ele' of length 'len' at
 * the specified position 'p', with 'p' being a listpack element pointer
 * obtained with lpFirst(), lpLast(), lpIndex(), lpNext(), lpPrev() or
 * lpSeek().
 *
 * The element is inserted before, after, or replaces the element pointed
 * by 'p' depending on the 'where' argument, that can be LP_BEFORE, LP_AFTER
 * or LP_REPLACE.
 *
 * If 'ele' is set to NULL, the function removes the element pointed by 'p'
 * instead of inserting one.
 *
 * Returns NULL on out of memory or when the listpack total length would exceed
 * the max allowed size of 2^32-1, otherwise the new pointer to the listpack
 * holding the new element is returned (and the old pointer passed is no longer
 * considered valid)
 *
 * If 'newp' is not NULL, at the end of a successful call '*newp' will be set
 * to the address of the element just added, so that it will be possible to
 * continue an interation with lpNext() and lpPrev().
 *
 * For deletion operations ('ele' set to NULL) 'newp' is set to the next
 * element, on the right of the deleted one, or to NULL if the deleted element
 * was the last one. */
/* 该方法有插入、删除和替换三种功能,这里重点说明插入
 * @param lp：listpack
 * @param ele：插入结点数据
 * @param size：插入结点数据长度
 * @param p：插入结点的位置
 * @param where: LP_BEFORE表示前面插入，LE_AFTER表示后面插入，LP_REPLACE 表示替换
 * @param newp：新插入结点的指针
 */
unsigned char *lpInsert(unsigned char *lp, unsigned char *ele, uint32_t size, 
		unsigned char *p, int where, unsigned char **newp) {
    /*intenc存储encoding-type字段*/
    unsigned char intenc[LP_MAX_INT_ENCODING_LEN];
    /*backlen存储element-total-len字段*/
    unsigned char backlen[LP_MAX_BACKLEN_SIZE];

    uint64_t enclen; /* The length of the encoded element. */

    /* An element pointer set to NULL means deletion, which is conceptually
     * replacing the element with a zero-length element. So whatever we
     * get passed as 'where', set it to LP_REPLACE. */
    if (ele == NULL) where = LP_REPLACE;

    /* If we need to insert after the current element, we just jump to the
     * next element (that could be the EOF one) and handle the case of
     * inserting before. So the function will actually deal with just two
     * cases: LP_BEFORE and LP_REPLACE. */
    if (where == LP_AFTER) {
        p = lpSkip(p);
        where = LP_BEFORE;
    }

    /* Store the offset of the element 'p', so that we can obtain its
     * address again after a reallocation. */
    /*插入位置的偏移量*/
    unsigned long poff = p-lp;

    /* Calling lpEncodeGetType() results into the encoded version of the
     * element to be stored into 'intenc' in case it is representable as
     * an integer: in that case, the function returns LP_ENCODING_INT.
     * Otherwise if LP_ENCODING_STR is returned, we'll have to call
     * lpEncodeString() to actually write the encoded string on place later.
     *
     * Whatever the returned encoding is, 'enclen' is populated with the
     * length of the encoded element. */
    /*得到插入结点的编码类型*/
    int enctype;
    if (ele) {
        enctype = lpEncodeGetType(ele,size,intenc,&enclen);
    } else {
        enctype = -1;
        enclen = 0;
    }

    /* We need to also encode the backward-parsable length of the element
     * and append it to the end: this allows to traverse the listpack from
     * the end to the start. */
    /*得到新插入结点的element-total-len字段所需的存储空间*/
    unsigned long backlen_size = ele ? lpEncodeBacklen(backlen,enclen) : 0;
    uint64_t old_listpack_bytes = lpGetTotalBytes(lp);
    uint32_t replaced_len  = 0;
    if (where == LP_REPLACE) {
        replaced_len = lpCurrentEncodedSize(p);
        replaced_len += lpEncodeBacklen(NULL,replaced_len);
    }

    uint64_t new_listpack_bytes = old_listpack_bytes + enclen + backlen_size
                                  - replaced_len;
    if (new_listpack_bytes > UINT32_MAX) return NULL;

    /* We now need to reallocate in order to make space or shrink the
     * allocation (in case 'when' value is LP_REPLACE and the new element is
     * smaller). However we do that before memmoving the memory to
     * make room for the new element if the final allocation will get
     * larger, or we do it after if the final allocation will get smaller. */

    unsigned char *dst = lp + poff; /* May be updated after reallocation. */

    /* Realloc before: we need more room. */
    if (new_listpack_bytes > old_listpack_bytes) {
        if ((lp = lp_realloc(lp,new_listpack_bytes)) == NULL) return NULL;
        dst = lp + poff;
    }

    /* Setup the listpack relocating the elements to make the exact room
     * we need to store the new one. */
    /* 从插入位置开始，结点整体右移，插入情况下，replaced_len=0*/
    if (where == LP_BEFORE) {
        memmove(dst+enclen+backlen_size,dst,old_listpack_bytes-poff);
    } else { /* LP_REPLACE. */
        long lendiff = (enclen+backlen_size)-replaced_len;
        memmove(dst+replaced_len+lendiff,
                dst+replaced_len,
                old_listpack_bytes-poff-replaced_len);
    }

    /* Realloc after: we need to free space. */
    if (new_listpack_bytes < old_listpack_bytes) {
        if ((lp = lp_realloc(lp,new_listpack_bytes)) == NULL) return NULL;
        dst = lp + poff;
    }

    /* Store the entry. */
    if (newp) {
        *newp = dst;
        /* In case of deletion, set 'newp' to NULL if the next element is
         * the EOF element. */
        if (!ele && dst[0] == LP_EOF) *newp = NULL;
    }
    /*写入新的结点*/
    if (ele) {
        if (enctype == LP_ENCODING_INT) {
            memcpy(dst,intenc,enclen);
        } else {
            lpEncodeString(dst,ele,size);
        }
        dst += enclen;
        memcpy(dst,backlen,backlen_size);
        dst += backlen_size;
    }

    /* Update header. */
    if (where != LP_REPLACE || ele == NULL) {
        uint32_t num_elements = lpGetNumElements(lp);
        if (num_elements != LP_HDR_NUMELE_UNKNOWN) {
            if (ele)
                lpSetNumElements(lp,num_elements+1);
            else
                lpSetNumElements(lp,num_elements-1);
        }
    }
    lpSetTotalBytes(lp,new_listpack_bytes);

    return lp;
}