redis 5.0.7ソース読み取り-圧縮リストziplist
31760 ワード
redisで圧縮リストziplistに関連するファイルはziplistです.hとziplist.c
圧縮リストはredisがメモリを節約するために開発したメモリ符号化データ構造である.ソースコードの圧縮リストに関するコメントも詳しく書かれています.
一、データ構造
圧縮リストの全体的な構造は以下の通りです(redisソース注釈を借ります):
各セクションの意味:
アイテム
を選択します.
長さ
用途
zlbytes
uint32_t
4B
ziplist総バイト数zlbytesを含む
zltail
uint32_t
4B
最後のentryのオフセット量
zllen
uint16_t
2B
entry数
zlend
uint8_t
1B
ziplist固定末尾、値固定0 xFF
entry
不定
不定
ziplistの各ノード、具体的な構造は不定です
entryについては、redisソース注釈の構造を借りて改造します.
prevlenは、前のentryの長さを表し、逆ループ、すなわち最後の要素から最初の要素にループします.各entryの長さは不確定なので、前のentryの長さを記録します.prevlen自体の長さも不定であり,前のentryの実際の長さと関係がある.長さが254未満であれば、1 Bだけでよい.実際の長さが254以上であれば5 Bが必要であり、第1 Bは254に固定され、後4 Bは実際の長さを記憶する.
Encodingはentryに格納されているdataに関係します.
Encoding上位2位
Encodingコンテンツ
义齿
entry-dataタイプ
entry-data長
00
|00pppppp|
1B
string
6 bで表される数字は、0~63、encodingに格納される長さが大端バイト順
01
|01pppppp|qqqqqqqq|
2B
string
14 bで表すことができる数字、64~16383、encodingに格納されている長さは大端バイト順
10
|10000000|qqqqqqqq|rrrrrrrr|ssssssss|tttttttt|
5B
string
int 32が表す数字、16384~2^32-1、encodingに格納されている長さは大端バイト順
11
|11000000|
1B
int16
2B
11
|11010000|
1B
int32
4B
11
|11100000|
1B
int64
8B
11
|11110000|
1B
int24
3B
11
|11111110|
1B
int8
1B
11
|1111xxxx|
1B
なし
xxxxは[00011101]の間で、0~12の数字を表し、格納時に+1操作を行う
11
|11111111|
1B
なし
End of ziplist special entry(ソース注釈)
特定のziplistの場合、2つのメンバー「2」と「5」があります.
zlbytesの値は15で、このziplistの総長が15 Bであることを示しています.
zltailの値は12で、最後のentryのオフセット量が12であることを示します.
zllenの値は2で、合計2つのentryがあることを示します
最初のentryのprevlenは0です.最初のメンバーは以前は他のメンバーがいなかったので、0で、1 Bを占めています.値は「2」であり、数字で表すことができ、[0,12]の間であるため、1111 xxxxxのencoding方式を使用してentry-dataがない.2のバイナリ符号化は0010,+1後は0011であり,実際には11110011,すなわち0 xF 3である.同様に,5のencodingは0 xF 6である.2番目のentryとしては、前のentryの総長が2であるため、prevlen値は2である.
zlend固定は0 xFFです.
二、基本操作
redisでは、マクロ定義と関数の組み合わせ操作ziplistが大量に使用されています.
1、作成
新しく作成されたziplistはentryがなく、zlbytes、zltail、zllen、zlendのみです.
2、挿入
次のziplistがあるとします.
ノード3を2と5の間に挿入するには、次の手順に従います.
a.挿入する位置の現在のノード「5」のprevlen=2,prevlen_を取得するsize=1
挿入する位置がendであればzltailを取り出してオフセットし,「5」ノードに取り出し,直接計算する.現在空のziplistであれば、直接0になります.
b.ノード「3」の実際の長さを取得し、純粋な数字であれば、デジタルストレージを使用してメモリを節約することができる.そうでなければ、外部から送られてきたstringの長さを直接使用します.
ここに少しあります.
デジタル符号化を試みた場合,len>=32であれば直接試みず,この32がどのように来たのか分からない.
この例では、「3」は直接デジタル符号化を用いることができ、[0,12]の間であるためentry-dataはない
c.本entryの全長、すなわちprevlen、encoding、entry-dataの長さとを得る.ここでは1+1=2
d.挿入後、後のentryのprevlenが新しいentryの長さを格納するのに十分かどうかを判断します.新しい長さは2で、元entryのprevlenは1 Bしかなく、十分です.
ここでは、本来5 Bのprevlenであれば、現在1 Bが十分に記憶されていれば、何の処理もせずに、1 Bが記憶できる数字を強制的に5 Bを用いて記憶させることに注意が必要である.元が1 Bで、現在は5 Bであれば、4 Bの空間も必要です.
e.ziplistスペースを再割り当てします.新しく追加されたバイト数は、c、dの2ステップの和です.ここには2 Bの余分なスペースしか必要ありません.
スペースの割り当て後:
スペースを再割り当てするとzlendとzlbytesが自動的に設定されます
f.「5」以降のノード(zlendを除く)を後ろに移動する:
g.現在の「5」の位置を修正するprevlen=2:
h.zltailの変更:
i.新しいentryを記入する:
j.zllenの更新:
これに基づいて、「3」の前に256の長さのstring Xが挿入されると、
a.「3」のprevlenとprevlen_を取得するsize
prevlen=2,prevlen_size=1
b.長さが32より大きく、stringで記憶し、実際の長さdata_len=256
c.entry全長取得
ここでprevlenの長さは1 B、encodingの長さは2 B、entry-dataの長さは256 B、合計1+2+256=259
d.挿入後、後のentryのprevlenが新しいentryの長さを格納するのに十分かどうかを判断します.新しい長さは259で、254を超えて5 Bが必要ですが、もともと1 Bしかなく、4 Bも足りません.すなわちnextdiff=4
e.スペースを割り当てる.新たに増加したバイト数は259+4=263で、280 B、すなわち0 x 118である.
スペースの割り当て後:
f.memmove操作
ziplistでのmemmove操作:
操作後:
ヘッダーがzlbytes、zltail、tllen
実は以下の書き方と同じ効果があります.
この書き方は操作後:
目的は同じで,元のノードを正しい位置に移動する.
g.現在の「3」の位置を修正するprevlen=259、すなわち0 X 103:
h.このときノード「3」の長さが変化し、次のノード「5」のprevlenを更新する必要がある.
i.zltailの変更:
j.新しいentryを記入する:
Encoding値:01000001 00000000、すなわち0 x 4100、大端バイトシーケンス
記入後:
k.zllenの更新:
連続する数entryの長さが[250523]Bの間であれば,新しいノードを挿入した後に連鎖更新がある可能性がある.
次のziplistのように(entryの一部のみを保持し、残りのノードは省略します).
E 1のprevlenはFD、すなわち長さ253である.このとき、E 1の前に長さ256のノードを挿入し、E 1はprevlenの長さを増やす必要があり、E 1全体の長さを増加させる.
E 2のprevlenはFD、すなわちE 1の長さは253である.4つのノードを増やした後は257であり,E 2もprevlenの長さを増やす必要がある.
その後、E 3、E 4などのentryが処理され、連鎖反応が発生し、以下の状況になるまで停止する可能性があります.
i.zlendに着いた
ii.拡張を続ける必要はありません
iii.prevlenバイト数を減らす必要がある場合
連鎖更新時には空間を複数回再割り当てする必要があり,最悪の場合はn個のノードのziplistがあり,n回の空間を割り当てる必要があるが,各割り当ての最悪の場合時間複雑度はO(n)であるため,連鎖更新の最悪の場合時間複雑度はO(n^2)である.
3、検索
ziplistの検索プロセスは、prevlen、encoding、entry-dataの順に解析され、encodingタイプに応じてstrcmpを使用するか、直接数字を使用するかの比較を決定します.最初に数字の比較を行うと、検索する列が入ってきて、一度に数字に変換しようとします.変換できない場合は、数値比較操作はスキップされます.
検索操作は、いくつかのentryごとに比較操作をサポートします.たとえば、5つのentryごとに「1」の値を持つentryを検索します.
4、削除
次のziplistがあります.
削除されたのはノード「5」です.最後のノードであるため、zltailを変更する必要があります.
そしてresize:
最後にzllenを変更します.
このziplistの場合:
削除が正しいノード「3」の場合、削除後、「3」ノードの後の「2」ノードのprevlen長さが十分かどうかを計算してから、直接書き込みます.この場合、長さが足りず、スペースを直接再割り当てするのではなく、前の「3」セクションの最後の4 Bスペースを直接使用します.
次にzltailを変更します.
次にmemmove操作を行います.
resizeアクション:
最後にノード「2」とその後entryのprevlenを更新します.
注意この時点で更新も連鎖反応を起こす可能性があります.
削除操作は、指定された位置からn個のentryを連続して削除することをサポートし、操作は類似しています.
圧縮リストはredisがメモリを節約するために開発したメモリ符号化データ構造である.ソースコードの圧縮リストに関するコメントも詳しく書かれています.
一、データ構造
圧縮リストの全体的な構造は以下の通りです(redisソース注釈を借ります):
1 /*
2 ...
3 */各セクションの意味:
アイテム
を選択します.
長さ
用途
zlbytes
uint32_t
4B
ziplist総バイト数zlbytesを含む
zltail
uint32_t
4B
最後のentryのオフセット量
zllen
uint16_t
2B
entry数
zlend
uint8_t
1B
ziplist固定末尾、値固定0 xFF
entry
不定
不定
ziplistの各ノード、具体的な構造は不定です
entryについては、redisソース注釈の構造を借りて改造します.
1 /*
2 []
3 */prevlenは、前のentryの長さを表し、逆ループ、すなわち最後の要素から最初の要素にループします.各entryの長さは不確定なので、前のentryの長さを記録します.prevlen自体の長さも不定であり,前のentryの実際の長さと関係がある.長さが254未満であれば、1 Bだけでよい.実際の長さが254以上であれば5 Bが必要であり、第1 Bは254に固定され、後4 Bは実際の長さを記憶する.
Encodingはentryに格納されているdataに関係します.
Encoding上位2位
Encodingコンテンツ
义齿
entry-dataタイプ
entry-data長
00
|00pppppp|
1B
string
6 bで表される数字は、0~63、encodingに格納される長さが大端バイト順
01
|01pppppp|qqqqqqqq|
2B
string
14 bで表すことができる数字、64~16383、encodingに格納されている長さは大端バイト順
10
|10000000|qqqqqqqq|rrrrrrrr|ssssssss|tttttttt|
5B
string
int 32が表す数字、16384~2^32-1、encodingに格納されている長さは大端バイト順
11
|11000000|
1B
int16
2B
11
|11010000|
1B
int32
4B
11
|11100000|
1B
int64
8B
11
|11110000|
1B
int24
3B
11
|11111110|
1B
int8
1B
11
|1111xxxx|
1B
なし
xxxxは[00011101]の間で、0~12の数字を表し、格納時に+1操作を行う
11
|11111111|
1B
なし
End of ziplist special entry(ソース注釈)
特定のziplistの場合、2つのメンバー「2」と「5」があります.
/*
[0f 00 00 00] [0c 00 00 00] [02 00] [00 f3] [02 f6] [ff]
| | | | | |
zlbytes zltail zllen "2" "5" end
*/zlbytesの値は15で、このziplistの総長が15 Bであることを示しています.
zltailの値は12で、最後のentryのオフセット量が12であることを示します.
zllenの値は2で、合計2つのentryがあることを示します
最初のentryのprevlenは0です.最初のメンバーは以前は他のメンバーがいなかったので、0で、1 Bを占めています.値は「2」であり、数字で表すことができ、[0,12]の間であるため、1111 xxxxxのencoding方式を使用してentry-dataがない.2のバイナリ符号化は0010,+1後は0011であり,実際には11110011,すなわち0 xF 3である.同様に,5のencodingは0 xF 6である.2番目のentryとしては、前のentryの総長が2であるため、prevlen値は2である.
zlend固定は0 xFFです.
二、基本操作
redisでは、マクロ定義と関数の組み合わせ操作ziplistが大量に使用されています.
1、作成
1 #define ZIPLIST_HEADER_SIZE (sizeof(uint32_t)*2+sizeof(uint16_t))
2 #define ZIPLIST_END_SIZE (sizeof(uint8_t))
3 #define ZIPLIST_BYTES(zl) (*((uint32_t*)(zl)))
4 #define ZIPLIST_TAIL_OFFSET(zl) (*((uint32_t*)((zl)+sizeof(uint32_t))))
5 #define ZIPLIST_LENGTH(zl) (*((uint16_t*)((zl)+sizeof(uint32_t)*2)))
6 #define ZIP_END 255
7
8
9 unsigned char *ziplistNew(void) {
10 unsigned int bytes = ZIPLIST_HEADER_SIZE+ZIPLIST_END_SIZE;
11 unsigned char *zl = zmalloc(bytes);
12 ZIPLIST_BYTES(zl) = intrev32ifbe(bytes);
13 ZIPLIST_TAIL_OFFSET(zl) = intrev32ifbe(ZIPLIST_HEADER_SIZE);
14 ZIPLIST_LENGTH(zl) = 0;
15 zl[bytes-1] = ZIP_END;
16 return zl;
17 }新しく作成されたziplistはentryがなく、zlbytes、zltail、zllen、zlendのみです.
1 /*
2 [0b 00 00 00] [0a 00 00 00] [00 00] [ff]
3 | | | |
4 zlbytes zltail zllen end
5 */2、挿入
次のziplistがあるとします.
1 /*
2 [0f 00 00 00] [0c 00 00 00] [02 00] [00 f3] [02 f6] [ff]
3 | | | | | |
4 zlbytes zltail zllen "2" "5" end
5 */ノード3を2と5の間に挿入するには、次の手順に従います.
a.挿入する位置の現在のノード「5」のprevlen=2,prevlen_を取得するsize=1
挿入する位置がendであればzltailを取り出してオフセットし,「5」ノードに取り出し,直接計算する.現在空のziplistであれば、直接0になります.
b.ノード「3」の実際の長さを取得し、純粋な数字であれば、デジタルストレージを使用してメモリを節約することができる.そうでなければ、外部から送られてきたstringの長さを直接使用します.
ここに少しあります.
1 int zipTryEncoding(unsigned char *entry, unsigned int entrylen, long long *v, unsigned char *encoding) {
2 long long value;
3
4 if (entrylen >= 32 || entrylen == 0) return 0;
5 if (string2ll((char*)entry,entrylen,&value)) {
6 /* Great, the string can be encoded. Check what's the smallest
7 * of our encoding types that can hold this value. */
8 if (value >= 0 && value <= 12) {
9 *encoding = ZIP_INT_IMM_MIN+value;
10 } else if (value >= INT8_MIN && value <= INT8_MAX) {
11 *encoding = ZIP_INT_8B;
12 } else if (value >= INT16_MIN && value <= INT16_MAX) {
13 *encoding = ZIP_INT_16B;
14 } else if (value >= INT24_MIN && value <= INT24_MAX) {
15 *encoding = ZIP_INT_24B;
16 } else if (value >= INT32_MIN && value <= INT32_MAX) {
17 *encoding = ZIP_INT_32B;
18 } else {
19 *encoding = ZIP_INT_64B;
20 }
21 *v = value;
22 return 1;
23 }
24 return 0;
25 }デジタル符号化を試みた場合,len>=32であれば直接試みず,この32がどのように来たのか分からない.
この例では、「3」は直接デジタル符号化を用いることができ、[0,12]の間であるためentry-dataはない
c.本entryの全長、すなわちprevlen、encoding、entry-dataの長さとを得る.ここでは1+1=2
d.挿入後、後のentryのprevlenが新しいentryの長さを格納するのに十分かどうかを判断します.新しい長さは2で、元entryのprevlenは1 Bしかなく、十分です.
ここでは、本来5 Bのprevlenであれば、現在1 Bが十分に記憶されていれば、何の処理もせずに、1 Bが記憶できる数字を強制的に5 Bを用いて記憶させることに注意が必要である.元が1 Bで、現在は5 Bであれば、4 Bの空間も必要です.
e.ziplistスペースを再割り当てします.新しく追加されたバイト数は、c、dの2ステップの和です.ここには2 Bの余分なスペースしか必要ありません.
スペースの割り当て後:
1 /*
2 [11 00 00 00] [0c 00 00 00] [02 00] [00 f3] [02 f6] [ff] [00 ff]
3 | | | | | |
4 zlbytes zltail zllen "2" "5" end
5 */スペースを再割り当てするとzlendとzlbytesが自動的に設定されます
f.「5」以降のノード(zlendを除く)を後ろに移動する:
1 /*
2 [11 00 00 00] [0c 00 00 00] [02 00] [00 f3] [02 f6] [02 f6] [ff]
3 | | | | | |
4 zlbytes zltail zllen "2" "5" "5"
5 */g.現在の「5」の位置を修正するprevlen=2:
1 /*
2 [11 00 00 00] [0c 00 00 00] [02 00] [00 f3] [02 f6] [02 f6] [ff]
3 | | | | | |
4 zlbytes zltail zllen "2" "5" "5"
5 */h.zltailの変更:
1 /*
2 [11 00 00 00] [0e 00 00 00] [02 00] [00 f3] [02 f6] [02 f6] [ff]
3 | | | | | |
4 zlbytes zltail zllen "2" "5" "5"
5 */i.新しいentryを記入する:
1 /*
2 [11 00 00 00] [0e 00 00 00] [02 00] [00 f3] [02 f4] [02 f6] [ff]
3 | | | | | |
4 zlbytes zltail zllen "2" "3" "5"
5 */j.zllenの更新:
1 /*
2 [11 00 00 00] [0e 00 00 00] [03 00] [00 f3] [02 f4] [02 f6] [ff]
3 | | | | | |
4 zlbytes zltail zllen "2" "3" "5"
5 */これに基づいて、「3」の前に256の長さのstring Xが挿入されると、
a.「3」のprevlenとprevlen_を取得するsize
prevlen=2,prevlen_size=1
b.長さが32より大きく、stringで記憶し、実際の長さdata_len=256
c.entry全長取得
ここでprevlenの長さは1 B、encodingの長さは2 B、entry-dataの長さは256 B、合計1+2+256=259
d.挿入後、後のentryのprevlenが新しいentryの長さを格納するのに十分かどうかを判断します.新しい長さは259で、254を超えて5 Bが必要ですが、もともと1 Bしかなく、4 Bも足りません.すなわちnextdiff=4
e.スペースを割り当てる.新たに増加したバイト数は259+4=263で、280 B、すなわち0 x 118である.
スペースの割り当て後:
1 /*
2 [0x118] [0xe] [03 00] [00 f3] [02 f4] [02 f6] [...] [ff]
3 | | | | | | |
4 zlbytes zltail zllen "2" "3" "5" 263B
5 4B 4B
6 */f.memmove操作
ziplistでのmemmove操作:
1 memmove(p+reqlen,p-nextdiff,curlen-offset-1+nextdiff);操作後:
1 /*
2 [...] [00 f3] [02 f4] [02 f6] [...] [03 00] [00 f3] [02 f4] [02 f6] [ff]
3 | | | | | | | |
4 header "2" "3" "5" 255B "2" "3" "5"
5 10B
6 */ヘッダーがzlbytes、zltail、tllen
実は以下の書き方と同じ効果があります.
1 memmove(p+reqlen+nextdiff,p,curlen-offset-1+nextdiff);この書き方は操作後:
1 /*
2 [0x118] [0xe] [03 00] [00 f3] [02 f4] [02 f6] [...] [02 f4] [02 f6] [ff]
3 | | | | | | | | |
4 zlbytes zltail zllen "2" "3" "5" 259B "3" "5"
5 4B 4B
6 */目的は同じで,元のノードを正しい位置に移動する.
g.現在の「3」の位置を修正するprevlen=259、すなわち0 X 103:
1 /*
2 [0x118] [0xe] [03 00] [00 f3] [...] [FE 03 01 00 00 f4] [02 f6] [ff]
3 | | | | | | |
4 zlbytes zltail zllen "2" 259B "3" "5"
5 4B 4B
6 */h.このときノード「3」の長さが変化し、次のノード「5」のprevlenを更新する必要がある.
1 /*
2 [0x118] [0xe] [03 00] [00 f3] [...] [FE 03 01 00 00 f4] [06 f6] [ff]
3 | | | | | | |
4 zlbytes zltail zllen "2" 259B "3" "5"
5 4B 4B
6 */i.zltailの変更:
1 /*
2 [0x118] [0x115] [03 00] [00 f3] [...] [FE 00 00 01 03 f4] [06 f6] [ff]
3 | | | | | | |
4 zlbytes zltail zllen "2" 259B "3" "5"
5 4B 4B
6 */j.新しいentryを記入する:
Encoding値:01000001 00000000、すなわち0 x 4100、大端バイトシーケンス
記入後:
1 /*
2 [0x118] [0x115] [03 00] [00 f3] [02 41 00 ...] [FE 00 00 01 03 f4] [06 f6] [ff]
3 | | | | | | |
4 zlbytes zltail zllen "2" X "3" "5"
5 4B 4B 259B
6 */k.zllenの更新:
1 /*
2 [0x118] [0x115] [04 00] [00 f3] [02 41 00 ...] [FE 00 00 01 03 f4] [06 f6] [ff]
3 | | | | | | |
4 zlbytes zltail zllen "2" X "3" "5"
5 4B 4B 259B
6 */連続する数entryの長さが[250523]Bの間であれば,新しいノードを挿入した後に連鎖更新がある可能性がある.
次のziplistのように(entryの一部のみを保持し、残りのノードは省略します).
1 /*
2 ... [FD 40 FA ...] [FD 40 FA ...] ...
3 | |
4 E1 253B E2 253B
5 */E 1のprevlenはFD、すなわち長さ253である.このとき、E 1の前に長さ256のノードを挿入し、E 1はprevlenの長さを増やす必要があり、E 1全体の長さを増加させる.
E 2のprevlenはFD、すなわちE 1の長さは253である.4つのノードを増やした後は257であり,E 2もprevlenの長さを増やす必要がある.
その後、E 3、E 4などのentryが処理され、連鎖反応が発生し、以下の状況になるまで停止する可能性があります.
i.zlendに着いた
ii.拡張を続ける必要はありません
iii.prevlenバイト数を減らす必要がある場合
連鎖更新時には空間を複数回再割り当てする必要があり,最悪の場合はn個のノードのziplistがあり,n回の空間を割り当てる必要があるが,各割り当ての最悪の場合時間複雑度はO(n)であるため,連鎖更新の最悪の場合時間複雑度はO(n^2)である.
3、検索
ziplistの検索プロセスは、prevlen、encoding、entry-dataの順に解析され、encodingタイプに応じてstrcmpを使用するか、直接数字を使用するかの比較を決定します.最初に数字の比較を行うと、検索する列が入ってきて、一度に数字に変換しようとします.変換できない場合は、数値比較操作はスキップされます.
検索操作は、いくつかのentryごとに比較操作をサポートします.たとえば、5つのentryごとに「1」の値を持つentryを検索します.
4、削除
次のziplistがあります.
1 /*
2 [0x118] [0x115] [04 00] [00 f3] [02 41 00 ...] [FE 00 00 01 03 f4] [06 f6] [ff]
3 | | | | | | |
4 zlbytes zltail zllen "2" X "3" "5"
5 4B 4B 259B
6 */削除されたのはノード「5」です.最後のノードであるため、zltailを変更する必要があります.
1 /*
2 [0x118] [0x10F] [04 00] [00 f3] [02 41 00 ...] [FE 00 00 01 03 f4] [06 f6] [ff]
3 | | | | | | |
4 zlbytes zltail zllen "2" X "3" "5"
5 4B 4B 259B
6 */そしてresize:
1 /*
2 [0x116] [0x10F] [04 00] [00 f3] [02 41 00 ...] [FE 00 00 01 03 f4] [ff]
3 | | | | | |
4 zlbytes zltail zllen "2" X "3"
5 4B 4B 259B
6 */最後にzllenを変更します.
1 /*
2 [0x116] [0x10F] [03 00] [00 f3] [02 41 00 ...] [FE 00 00 01 03 f4] [ff]
3 | | | | | |
4 zlbytes zltail zllen "2" X "3"
5 4B 4B 259B
6 */このziplistの場合:
1 /*
2 [0x118] [0x115] [04 00] [00 41 00 ...] [FE 00 00 01 03 f4] [06 f3] [02 f6] [ff]
3 | | | | | | |
4 zlbytes zltail zllen X "3" "2" "5"
5 4B 4B 259B
6 */削除が正しいノード「3」の場合、削除後、「3」ノードの後の「2」ノードのprevlen長さが十分かどうかを計算してから、直接書き込みます.この場合、長さが足りず、スペースを直接再割り当てするのではなく、前の「3」セクションの最後の4 Bスペースを直接使用します.
1 /*
2 [0x118] [0x115] [04 00] [00 41 00 ...] [FE 00] [FE 00 00 01 03 f3] [02 f6] [ff]
3 | | | | | | |
4 zlbytes zltail zllen X 2B "2" "5"
5 4B 4B 259B
6 */次にzltailを変更します.
1 /*
2 [0x118] [0x113] [04 00] [00 41 00 ...] [FE 00] [FE 00 00 01 03 f3] [02 f6] [ff]
3 | | | | | | |
4 zlbytes zltail zllen X 2B "2" "5"
5 4B 4B 259B
6 */次にmemmove操作を行います.
1 /*
2 [0x118] [0x113] [04 00] [00 41 00 ...] [FE 00 00 01 03 f3] [02 f6] [02 f6] [ff]
3 | | | | | | |
4 zlbytes zltail zllen X "2" "5" "5"
5 4B 4B 259B
6 */resizeアクション:
1 /*
2 [0x116] [0x113] [04 00] [00 41 00 ...] [FE 00 00 01 03 f3] [02 f6] [ff]
3 | | | | | |
4 zlbytes zltail zllen X "2" "5"
5 4B 4B 259B
6 */最後にノード「2」とその後entryのprevlenを更新します.
1 /*
2 [0x116] [0x113] [04 00] [00 41 00 ...] [FE 00 00 01 03 f3] [06 f6] [ff]
3 | | | | | |
4 zlbytes zltail zllen X "2" "5"
5 4B 4B 259B
6 */注意この時点で更新も連鎖反応を起こす可能性があります.
削除操作は、指定された位置からn個のentryを連続して削除することをサポートし、操作は類似しています.