https://blog.csdn.net/chenxun_2010/article/details/103762794
ziplist的特點簡單介紹：
ziplist其實就是配置設定一塊連續的記憶體，用指針和位操作來操作記憶體的一種高效的資料結構。
- Ziplist 能存儲strings和integer值，整型值被存儲為實際的整型值而不是字元數組
- Ziplist 是為了盡可能節約記憶體而設計相當特殊的雙端隊列
- Ziplist 在頭部和尾部的操作時間0（1），ziplist的操作都需要重新配置設定記憶體，是以實際的複雜度和ziplist的使用和記憶體有關。
ziplist壓縮清單存儲結構：
+---------+--------+-------+--------+--------+--------+--------+-------+
| zlbytes | zltail | zllen | entry1 | entry2 | ... | entryN | zlend |
+---------+--------+-------+--------+--------+--------+--------+-------+
zlbytes: 使用的記憶體數量。通過這個值，程式可以直接對 ziplist 的記憶體大小進行調整，而無須為了計算ziplist的記憶體大小而周遊整個清單。
zltail: 4位元組，儲存着到達清單中最後一個節點的偏移量。這個偏移量使得對表尾的操作可以在無須周遊整個清單的情況下進行。
zllen: 2位元組，儲存着清單中的節點數量。當 zllen 儲存的值大于 2**16-1= 65535 時程式需要周遊整個清單才能知道清單實際包含了多少個節點。
zlend: 1位元組，值為 255 = 0xFF，辨別清單的末尾。
// 判斷encoding是否是字元串編碼
#define ZIP_IS_STR(enc) (((enc) & ZIP_STR_MASK) < ZIP_STR_MASK)
//傳回整個壓縮清單的大小 即求zlbytes的值
/* Return total bytes a ziplist is composed of. */
#define ZIPLIST_BYTES(zl) ( *( (uint32_t*)(zl) ) )
/* Return the offset of the last item inside the ziplist. */
//傳回壓縮清單起始位置到最後一個元素的偏移量
#define ZIPLIST_TAIL_OFFSET(zl) (*((uint32_t*)((zl)+sizeof(uint32_t))))
//傳回壓縮清單的元素的個數
#define ZIPLIST_LENGTH(zl) (*((uint16_t*)((zl)+sizeof(uint32_t)*2)))
//傳回壓縮清單首部的長度 8位元組
#define ZIPLIST_HEADER_SIZE (sizeof(uint32_t)*2+sizeof(uint16_t))
//zlend 0xFF 一位元組
#define ZIPLIST_END_SIZE (sizeof(uint8_t))
//傳回指向壓縮清單的第一個元素的指針
#define ZIPLIST_ENTRY_HEAD(zl) ((zl)+ZIPLIST_HEADER_SIZE)
/* Return the pointer to the last entry of a ziplist, using the
* last entry offset inside the ziplist header. */
//傳回指向最後一個元素的指針
#define ZIPLIST_ENTRY_TAIL(zl) ((zl)+intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl)))
//傳回指針zlend的指針
/* Return the pointer to the last byte of a ziplist, which is, the
* end of ziplist FF entry. */
#define ZIPLIST_ENTRY_END(zl) ((zl)+intrev32ifbe(ZIPLIST_BYTES(zl))-1)
壓縮清單每個元素 entryX（entry1、entry2 …）的結構：
+----------+-----------+-------+
| prevlen | encoding | value |
+----------+-----------+-------+
prevlen：用來表示前一個元素entry的位元組長度，redis規定prevlen元素本身存儲在計算機所需要占用記憶體大小要麼是1個位元組，要麼是5個位元組，如果前一個元素的位元組長度（占用的記憶體）小于254，那麼prevlen占用1一個位元組，如果前一個元素>=254位元組，prevlen占用5個位元組，此時prevlen第一個位元組固定為0XFE(254),prevlen的後四位元組才真正用來表示前一個元素的長度。
encoding： value的編碼（編碼元素的類型int還是表示字元串的位元組數組/value的長度）
value： 元素的值：要麼是整數，要麼是位元組數組表示字元串
壓縮清單元素的encoding編碼規則介紹：
ziplist的元素能存儲int和字元串類型
先介紹字元串編碼：此時encoding 存貯類型和len
| encoding | 占用位元組 | 存貯結構encode/len | 字元串長度範圍 | len取值 |
|---|---|---|---|---|
| ZIP_STR_06B | 1位元組 | 00XXXXXX | 長度<64 | 後6位 |
| ZIP_STR_14B | 2位元組 | 01XXXXXX XXXXXXXX | 長度<16384 | 後14位2^14-1 |
| ZIP_STR_32B | 5位元組 | 10000000 XXXXXXXX XXXXXXXX XXXXXXXX XXXXXXXX | 長度=<2^32-1 | 32位 |
int編碼：由于整型的長度是固定的，是以 隻需存儲encoding資訊，length值可根據編碼進行計算得出。
| encoding | 占用位元組 | 存儲結構 | 取值範圍 |
|---|---|---|---|
| ZIP_INT_XX | 1位元組 | 11 11 0001~11111101 | 0~12 |
| ZIP_INT_8B | 1位元組 | 11 11 1110 | -28~28-1 |
| ZIP_INT_16B | 2位元組 | 11 00 0000 | -216~216-1 |
| ZIP_INT_24B | 3位元組 | 11 11 0000 | -224~224-1 |
| ZIP_INT_32B | 4位元組 | 11 01 0000 | -232~232-1 |
| ZIP_INT_64B | 8位元組 | 11 10 0000 | -264~264-1 |
注意到沒有：
- encoding字段第一個位元組的前2位 00 01 10的時候表示元素entryx類型是字元串，11的時候表示是整型，是以通過encoding可以知道元素value字段的類型是否是整型或者位元組數組（以及位元組數組的長度）
- 1111 0001~1111 1101表示0到12的的編碼，其後四位的取值減去1就是0到12， 例如 0001-1 = 0 、 1101-1= 12
redis預定義以下常量對應encoding字段的各編碼類型：
#define ZIP_STR_06B (0 << 6)
#define ZIP_STR_14B (1 << 6)
#define ZIP_STR_32B (2 << 6)
#define ZIP_INT_16B (0xc0 | 0<<4) ----> 11 00 0000 -2^16~2^16-1
#define ZIP_INT_32B (0xc0 | 1<<4) ----> 11 01 0000 -2^32~2^32-1
#define ZIP_INT_64B (0xc0 | 2<<4) ----> 11 10 0000 -2^64~2^64-1
#define ZIP_INT_24B (0xc0 | 3<<4) ----> 11 11 0000 -2^24~2^24-1
#define ZIP_INT_8B 0xfe ----> 11 11 1110 -2^8~2^8-1
來看一個例子：zl表中存貯2和5兩個元素
[0f 00 00 00] [0c 00 00 00] [02 00] [00 f3] [02 f6] [ff]
| | | | | |
zlbytes zltail entries "2" "5" end
- zlbytes： 上面的壓縮清單zl總長度為15位元組：是以zlbytes = 0x0f 值為15
- 注意了：redis裡面都是采用小端模式，0f 00 00 00 按照小端取值為0x00 00 00 0f
- ztail： 取值0x0000000c;是以ztail=12 ztail就是壓縮清單zl起始位置到尾部元素5的偏移量
- entries：0x0002表示壓縮清單元素的個數為2
- 第一個元素00 f3 因為是第一個元素是以prevlen=0：第一個元素前面沒有元素是以prevlen所用所需要的存貯空間占用一個字，是以00 f3的第一個位元組為00 值為0，接下來是encoding編碼，檢視接下來第一個位元組f3 11110011 的前兩位11 是以是整數，整數的類型看前四位1111 是以第一個元素的值是3-1=2
- 第二個元素02 f6，因為第一個元素的長度為2位元組小于254，是以第二個元素的prevlen所需要的記憶體隻需要一個位元組，是以02 f6的第一個位元組02表示前一個元素的長度 0x02=2， ，0xf6= 1111 0110 其中1111編碼表示整型，0110=6，6-1=5，是以第二個元素的值為5
- end的編碼0xFF
entryX元素解碼之後存儲結構
typedef struct zlentry {
unsigned int prevrawlensize; /* Bytes used to encode the previous entry len*/
unsigned int prevrawlen; /* Previous entry len. */
unsigned int lensize; /* Bytes used to encode this entry type/len.
For example strings have a 1, 2 or 5 bytes
header. Integers always use a single byte.*/
unsigned int len; /* Bytes used to represent the actual entry.
For strings this is just the string length
while for integers it is 1, 2, 3, 4, 8 or
0 (for 4 bit immediate) depending on the
number range. */
unsigned int headersize; /* prevrawlensize + lensize. */
unsigned char encoding; /* Set to ZIP_STR_* or ZIP_INT_* depending on
the entry encoding. However for 4 bits
immediate integers this can assume a range
of values and must be range-checked. */
unsigned char *p; /* Pointer to the very start of the entry, that
is, this points to prev-entry-len field. */
} zlentry;
再看一下entryX在ziplist中存儲結構，然後分析zlentry
+----------+-----------+-------+
| prevlen | encoding | value |
+----------+-----------+-------+
其上面三個字段通過zipEntry函數解析存儲結構為zlentry
- prevrawlen： 就是上面提到prevlen，表示前一個元素的長度。
- prevrawlensize： prevrawlen本身編碼的位元組數，也就是prevrawlen本身存貯所需要的記憶體空間，redis中規定前一個元素的長度小于254就占用1位元組，大于等于254占用5位元組。
- len：表示元素的長度。
- lensize：表示encoding的長度，也就是encoding所需要占用的記憶體。
- headersize：表示本元素entryX的首部長度，即prevlen和encoding兩個字段所占用的記憶體之和 headersize= prevrawlensize + lensize
zipEntry用來解碼壓縮清單元素entryX，存儲于zlentry結構體。
/* Return a struct with all information about an entry. */
void zipEntry(unsigned char *p, zlentry *e) {
//p 為encoding的起始位址，即p指向清單元素
ZIP_DECODE_PREVLEN(p, e->prevrawlensize, e->prevrawlen);
ZIP_DECODE_LENGTH(p + e->prevrawlensize, e->encoding, e->lensize, e->len);
e->headersize = e->prevrawlensize + e->lensize;
e->p = p;
}
ZIP_DECODE_PREVLEN 解析prevlen字段 — 傳入指針ptr 求prevlensize和prevlen的值
//傳入指針ptr 求prevlensize和prevlen的值
#define ZIP_DECODE_PREVLEN(ptr, prevlensize, prevlen) do { \
ZIP_DECODE_PREVLENSIZE(ptr, prevlensize); \
if ((prevlensize) == 1) { \
(prevlen) = (ptr)[0]; \
} else if ((prevlensize) == 5) { \
assert(sizeof((prevlen)) == 4); \
memcpy(&(prevlen), ((char*)(ptr)) + 1, 4); \
memrev32ifbe(&prevlen); \
} \
} while(0);
ZIP_DECODE_LENGTH 用來解碼encoding字段–傳入指針ptr 求encoding 、lensize 、 len
#define ZIP_DECODE_LENGTH(ptr, encoding, lensize, len) do { \
//ZIP_ENTRY_ENCODING求encoding
ZIP_ENTRY_ENCODING((ptr), (encoding)); \
if ((encoding) < ZIP_STR_MASK) { \
if ((encoding) == ZIP_STR_06B) { \
(lensize) = 1; \
(len) = (ptr)[0] & 0x3f; \
} else if ((encoding) == ZIP_STR_14B) { \
(lensize) = 2; \
(len) = (((ptr)[0] & 0x3f) << 8) | (ptr)[1]; \
} else if ((encoding) == ZIP_STR_32B) { \
(lensize) = 5; \
(len) = ((ptr)[1] << 24) | \
((ptr)[2] << 16) | \
((ptr)[3] << 8) | \
((ptr)[4]); \
} else { \
panic("Invalid string encoding 0x%02X", (encoding)); \
} \
} else { \
(lensize) = 1; \
(len) = zipIntSize(encoding); \
} \
} while(0);
zipRawEntryLength：傳回p的指向的元素長度
/* Return the total number of bytes used by the entry pointed to by 'p'. */
unsigned int zipRawEntryLength(unsigned char *p) {
unsigned int prevlensize, encoding, lensize, len;
ZIP_DECODE_PREVLENSIZE(p, prevlensize);
ZIP_DECODE_LENGTH(p + prevlensize, encoding, lensize, len);
return prevlensize + lensize + len;
}
上文中已經講到過位元組數組隻需要根據ptr[0]的前2位即可判斷類型：00 10 10 表示字元串，而判斷整數需要ptr[0]的前四位.
/* Return bytes needed to store integer encoded by 'encoding'. */
unsigned int zipIntSize(unsigned char encoding) {
switch(encoding) {
case ZIP_INT_8B: return 1;
case ZIP_INT_16B: return 2;
case ZIP_INT_24B: return 3;
case ZIP_INT_32B: return 4;
case ZIP_INT_64B: return 8;
}
//0----12
if (encoding >= ZIP_INT_IMM_MIN && encoding <= ZIP_INT_IMM_MAX)
return 0; /* 4 bit immediate */
panic("Invalid integer encoding 0x%02X", encoding);
return 0;
}
zipStoreEntryEncoding 此函數傳入encoding 和 length，把encoidng的值存入p 然後傳回編碼prawlen的位元組數，即prawlen所需要的記憶體
unsigned int zipStoreEntryEncoding(unsigned char *p, unsigned char encoding, unsigned int rawlen) {
unsigned char len = 1, buf[5];
if (ZIP_IS_STR(encoding)) {
/* Although encoding is given it may not be set for strings,
* so we determine it here using the raw length. */
if (rawlen <= 0x3f) { //長度小于等于63 編碼為 00xx xxxx 00表示ZIP_STR_06B編碼 xxxxxx 表示長度length
if (!p) return len;
buf[0] = ZIP_STR_06B | rawlen;
} else if (rawlen <= 0x3fff) { //長度小于16383 編碼為 01XXXXXX XXXXXXXX
len += 1;
if (!p) return len;
buf[0] = ZIP_STR_14B | ((rawlen >> 8) & 0x3f);
buf[1] = rawlen & 0xff;
} else { // 編碼為 ZIP_STR_32B 10000000 XXXXXXXX XXXXXXXX XXXXXXXX XXXXXXXX
len += 4;
if (!p) return len;
buf[0] = ZIP_STR_32B;
buf[1] = (rawlen >> 24) & 0xff;
buf[2] = (rawlen >> 16) & 0xff;
buf[3] = (rawlen >> 8) & 0xff;
buf[4] = rawlen & 0xff;
}
} else {
/* Implies integer encoding, so length is always 1. */
//整型的時候 整數的長度 隻需要一個位元組就可以編碼
if (!p) return len;
buf[0] = encoding;
}
/* Store this length at p. */
memcpy(p,buf,len);
return len;
}
//隻用len >= ZIP_BIG_PREVLEN
/* Encode the length of the previous entry and write it to "p". This only
* uses the larger encoding (required in __ziplistCascadeUpdate). */
int zipStorePrevEntryLengthLarge(unsigned char *p, unsigned int len) {
if (p != NULL) {
p[0] = ZIP_BIG_PREVLEN;
memcpy(p+1,&len,sizeof(len));
memrev32ifbe(p+1);
}
return 1+sizeof(len);
}
//編碼前一個元素length的寫入到p 傳回編碼前一個元素的length所需空間即占用的記憶體位元組數
/* Encode the length of the previous entry and write it to "p". Return the
* number of bytes needed to encode this length if "p" is NULL. */
unsigned int zipStorePrevEntryLength(unsigned char *p, unsigned int len) {
if (p == NULL) {
return (len < ZIP_BIG_PREVLEN) ? 1 : sizeof(len)+1;
} else {
if (len < ZIP_BIG_PREVLEN) {
p[0] = len;
return 1;
} else {
return zipStorePrevEntryLengthLarge(p,len);
}
}
}
zipRawEntryLength p指向元素的長度
/* Return the total number of bytes used by the entry pointed to by 'p'. */
unsigned int zipRawEntryLength(unsigned char *p) {
unsigned int prevlensize, encoding, lensize, len;
ZIP_DECODE_PREVLENSIZE(p, prevlensize);
ZIP_DECODE_LENGTH(p + prevlensize, encoding, lensize, len);
return prevlensize + lensize + len;
}
__ziplistInsert函數中nextdiff的
int zipPrevLenByteDiff(unsigned char *p, unsigned int len) {
unsigned int prevlensize;
//宏,展開之後根據p[0]處的值計算出prevlensize,如果p[0]<254,prevlensize為1,否則為5
ZIP_DECODE_PREVLENSIZE(p, prevlensize);
//zipStorePrevEntryLength函數如果第一個參數為NULL,則根據len字段計算需要的位元組數,同理,len<254為1個位元組,否則為5個位元組
return zipStorePrevEntryLength(NULL, len) - prevlensize;
}
如上函數計算nextdiff,可以看出,根據插入位置p目前儲存prev_entry_len字段的位元組數和即将插入的entry需要的位元組數相減得出nextdiff.值有三種類型
0: 空間相等
4：需要更多空間
-4：空間富餘
__ziplistInsert ：在p位置插入節點
/* Insert item at "p". */
unsigned char *__ziplistInsert(unsigned char *zl, unsigned char *p, unsigned char *s, unsigned int slen) {
/*
zl：指向壓縮清單
p：指向元素s插入的位置， 要插入的元素s插入清單後 s是p的元素的前一個元素
s：要插入元素
slen：插入元素s的長度，即所占用的記憶體
*/
//curlen 目前壓縮清單的長度
size_t curlen = intrev32ifbe(ZIPLIST_BYTES(zl)), reqlen;
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. */
//三種情況：
/*
1、當壓縮清單為空，不存在前一個元素，即前一個元素的長度為0
2、插入位置p元素存在，能根據p求出前一個元素的長度
3、插入的位置為最後一個元素：即插入的元素成為壓縮清單最後一個元素
*/
if (p[0] != ZIP_END) {
//插入的位置不在尾部
ZIP_DECODE_PREVLEN(p, prevlensize, prevlen);
} else {
//插入的位置在尾部
unsigned char *ptail = ZIPLIST_ENTRY_TAIL(zl);//指向最後一個元素
if (ptail[0] != ZIP_END) {
prevlen = zipRawEntryLength(ptail);//zipRawEntryLength 求節點長度
}
}
/* See if the entry can be encoded */
//s 指向新節點資料的指針 slen為資料的長度
/* 判斷長度為entrylen的entry字元串能否轉換為數值，轉換結果儲存在v中 編碼方式儲存在encoding中 */
if (zipTryEncoding(s,slen,&value,&encoding)) {
/* 'encoding' is set to the appropriate integer encoding */
reqlen = zipIntSize(encoding);
} else {
/* 'encoding' is untouched, however zipStoreEntryEncoding will use the
* string length to figure out how to encode it. */
reqlen = slen;
}
/* We need space for both the length of the previous entry and
* the length of the payload. */
reqlen += zipStorePrevEntryLength(NULL,prevlen); //求prevlen字段所占用記憶體大小要麼是1 要麼是5
reqlen += zipStoreEntryEncoding(NULL,encoding,slen);//求encoding字段所占用的記憶體大小
/* 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. */
int forcelarge = 0;
/*
zipPrevLenByteDiff求p指向節點prevlensize的變化 因為在p位置插入長度為reqlen位元組之後
p指向的節點prevlen=reqlen prevlensize就是reqlen的編碼位元組數 變化的值為0、4、-4
*/
nextdiff = (p[0] != ZIP_END) ? zipPrevLenByteDiff(p,reqlen) : 0;
//修複由于連鎖更新造成的bug情況
if (nextdiff == -4 && reqlen < 4) {
nextdiff = 0;
forcelarge = 1;
}
/* Store offset because a realloc may change the address of zl. */
offset = p-zl;//zl壓縮清單頭到p的位置偏移量
zl = ziplistResize(zl,curlen+reqlen+nextdiff);//重新配置設定 調整記憶體大小
p = zl+offset;
/* Apply memory move when necessary and update tail offset. */
//非空清單插入
if (p[0] != ZIP_END) {
/* Subtract one because of the ZIP_END bytes */
// 資料移動，根據nextdiff的值移動資料 例如nextdiff=4時 p-nextdiff 即從p後移4位元組的位置
// 開始移動curlen-offset-1+nextdiff長度記憶體資料，減一是zlend不需要移動。
memmove(p+reqlen,p-nextdiff,curlen-offset-1+nextdiff);
/* Encode this entry's raw length in the next entry. */
//在p位置插入元素reqlen長度後，需要更新p位置的元素的prevlen=reqlen的值
//寫入p節點前一節點的資訊長度（要插入節點的長度）
if (forcelarge)
//插入元素reqlen < 254, 但是p的位置的元素的prevlen依然占用5位元組
zipStorePrevEntryLengthLarge(p+reqlen,reqlen);
else
zipStorePrevEntryLength(p+reqlen,reqlen);
/* Update offset for tail */
//更新ztail字段的值
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. */
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. */
//元素插入後成為清單最後一個元素 空清單插入，隻更新尾節點偏移量
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 */
//考慮連鎖更新
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);
}
// 增加清單長度
ZIPLIST_INCR_LENGTH(zl,1);
return zl;
}
連鎖更新
unsigned char *__ziplistCascadeUpdate(unsigned char *zl, unsigned char *p) {
size_t curlen = intrev32ifbe(ZIPLIST_BYTES(zl)), rawlen, rawlensize;
size_t offset, noffset, extra;
unsigned char *np;
zlentry cur, next;
while (p[0] != ZIP_END) {
// 解析目前節點資訊
zipEntry(p, &cur);
// 目前節點總長
rawlen = cur.headersize + cur.len;
// 儲存目前節點長度資訊所需長度
rawlensize = zipStorePrevEntryLength(NULL,rawlen);
// 清單末尾，停止周遊
if (p[rawlen] == ZIP_END) break;
// 解析下一節點資訊
zipEntry(p+rawlen, &next);
/* Abort when "prevlen" has not changed. */
if (next.prevrawlen == rawlen) break;
if (next.prevrawlensize < rawlensize) {
/* The "prevlen" field of "next" needs more bytes to hold
* the raw length of "cur". */
offset = p-zl;
// 下一節點因 前一節點長度資訊 字段長度變更引發的自身長度變化大小
extra = rawlensize-next.prevrawlensize;
// 記憶體重新配置設定
zl = ziplistResize(zl,curlen+extra);
p = zl+offset;
/* Current pointer and offset for next element. */
np = p+rawlen;
noffset = np-zl;
// 如果下一節點不是尾節點，則需要更新 尾部節點偏移量
if ((zl+intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))) != np) {
ZIPLIST_TAIL_OFFSET(zl) =
intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))+extra);
}
/* Move the tail to the back. */
memmove(np+rawlensize,
np+next.prevrawlensize,
curlen-noffset-next.prevrawlensize-1);
zipStorePrevEntryLength(np,rawlen);
p += rawlen;
curlen += extra;
} else {
// 如果 next節點原本的 前一節點長度資訊 字段長度可以容納新插入節點的長度資訊，則直接寫入并退出周遊
if (next.prevrawlensize > rawlensize) {
/* This would result in shrinking, which we want to avoid.
* So, set "rawlen" in the available bytes. */
zipStorePrevEntryLengthLarge(p+rawlen,rawlen);
} else {
zipStorePrevEntryLength(p+rawlen,rawlen);
}
/* Stop here, as the raw length of "next" has not changed. */
break;
}
}
return zl;
}
ziplistDelete:
unsigned char *ziplistDelete(unsigned char *zl, unsigned char **p) {
size_t offset = *p-zl;
zl = __ziplistDelete(zl,*p,1);
/* Store pointer to current element in p, because ziplistDelete will
* do a realloc which might result in a different "zl"-pointer.
* When the delete direction is back to front, we might delete the last
* entry and end up with "p" pointing to ZIP_END, so check this. */
*p = zl+offset;
return zl;
}
/* Delete a range of entries from the ziplist. */
unsigned char *ziplistDeleteRange(unsigned char *zl, int index, unsigned int num) {
unsigned char *p = ziplistIndex(zl,index);
return (p == NULL) ? zl : __ziplistDelete(zl,p,num);
}
__ziplistDelete:因為可能會觸發連鎖更新，是以删除操作最壞複雜度為O(n^2)，平均複雜度為O(n)
/* Delete "num" entries, starting at "p". Returns pointer to the ziplist. */
unsigned char *__ziplistDelete(unsigned char *zl, unsigned char *p, unsigned int num) {
unsigned int i, totlen, deleted = 0;
size_t offset;
int nextdiff = 0;
zlentry first, tail;
//解碼第一個删除的元素
zipEntry(p, &first);
//周遊所有待删除的删除的元素
for (i = 0; p[0] != ZIP_END && i < num; i++) {
p += zipRawEntryLength(p);
deleted++;
}
//待删除所有元素的總長度
totlen = p-first.p; /* Bytes taken by the element(s) to delete. */
if (totlen > 0) {
if (p[0] != ZIP_END) {//如果p指向zlend 不需要進行資料複制
/* Storing `prevrawlen` in this entry may increase or decrease the
* number of bytes required compare to the current `prevrawlen`.
* There always is room to store this, because it was previously
* stored by an entry that is now being deleted. */
// 計算元素entryN長度的變化量 删除後p指向元素的prelen資訊有所變化，
// 導緻prevlensize 大小發生變化0 4 -4三種情況
nextdiff = zipPrevLenByteDiff(p,first.prevrawlen);
/* Note that there is always space when p jumps backward: if
* the new previous entry is large, one of the deleted elements
* had a 5 bytes prevlen header, so there is for sure at least
* 5 bytes free and we need just 4. */
/*根據prevlen資訊變化移動p指針*/
p -= nextdiff;
//p指針移動後把prevrawlen資訊存貯到p處
zipStorePrevEntryLength(p,first.prevrawlen);
/* Update offset for tail */
//更新ztail資訊
ZIPLIST_TAIL_OFFSET(zl) =
intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))-totlen);
/* 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指向的元素
zipEntry(p, &tail);
/* 如果p節點不是尾節點, 則尾節點偏移量需要加上nextdiff的變更量
因為尾節點偏移量是指清單首位址到尾節點首位址的距離
p節點的 【前一節點長度資訊】 字段的長度變化隻影響它字段之後的資訊位址。
p節點為尾節點時，為節點首位址在【前一節點長度資訊】字段前邊，是以不受影響。*/
if (p[tail.headersize+tail.len] != ZIP_END) {
ZIPLIST_TAIL_OFFSET(zl) =
intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))+nextdiff);
}
/* Move tail to the front of the ziplist */
//資料複制
memmove(first.p,p,
intrev32ifbe(ZIPLIST_BYTES(zl))-(p-zl)-1);
} else {
/* The entire tail was deleted. No need to move memory. */
// 一直删除到尾節點，不需要變更中間節點，隻需要調整下尾節點偏移量
ZIPLIST_TAIL_OFFSET(zl) =
intrev32ifbe((first.p-zl)-first.prevrawlen);
}
/* Resize and update length */
offset = first.p-zl;
// 重新配置設定記憶體大小
zl = ziplistResize(zl, intrev32ifbe(ZIPLIST_BYTES(zl))-totlen+nextdiff);
ZIPLIST_INCR_LENGTH(zl,-deleted);
p = zl+offset;
/* When nextdiff != 0, the raw length of the next entry has changed, so
* we need to cascade the update throughout the ziplist */
// 如果最後一個被删除節點的下一節點的【前一個節點長度資訊】字段長度 需要變更，則可能會觸發連鎖更新
if (nextdiff != 0)
zl = __ziplistCascadeUpdate(zl,p);
}
return zl;
}
![秒懂JVM的三大參數類型，就靠這十個小實驗了初級—中級—進階三個級别的大廠面試真題阿裡雲——Java 實習生/初級美團——Java 中級螞蟻金服——Java 進階基礎篇JVM 篇MySQL 篇Redis 篇[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)