一、String
1.1.數(shù)據(jù)結(jié)構(gòu)
struct sdshdr{
int len;//字符串長度
int free;//空閑字符串長度
char buf[];//字符串?dāng)?shù)組
}
注：數(shù)組大小=len+free+1（字符的‘\0’休止符）
1.2.空間分配策略
修改字符串引起內(nèi)存重分配，消耗資源，所以引入優(yōu)化策略：空間預(yù)分配、惰性空間釋放。
1）空間預(yù)分配
如果len<1MB，分配空間=len*2+1,即free=len;
如果len>=1MB，分配空間=len + 1MB +1,即free=1MB.
- 惰性空間釋放
釋放不回收，減少內(nèi)存重分配。需要的時候可以調(diào)用api真正回收。
1.3.SDS、C字符串對比
1.3.1.SDS好處
- 獲取字符串長度時間復(fù)雜度
SDS獲取字符串長度時間復(fù)雜度為O(1)；c字符串為O(n)。 - 字符串?dāng)U容安全
SDS動態(tài)擴(kuò)容，不會發(fā)生緩沖區(qū)溢出；c字符串執(zhí)行strcat(s,"test");時，如果忘記給s分配足夠的空間，會導(dǎo)致溢出。 - 二進(jìn)制安全（數(shù)據(jù)寫入的格式和讀取的格式一致）
二、鏈表->雙向鏈表
2.1.數(shù)據(jù)結(jié)構(gòu)
2.1.1 節(jié)點(diǎn)結(jié)構(gòu)
struct listNode{
struct listNode *prev;
struct listNode *next;
void *value;
}listNode;
2.1.2 數(shù)據(jù)結(jié)構(gòu)
struct list{
listNode *head;
listNode *tail;
unsigned long len;//鏈表長度
void *(*dup)(void *ptr);//節(jié)點(diǎn)值復(fù)制函數(shù)
void *(*free)(void *ptr);//節(jié)點(diǎn)值釋放函數(shù)
int *(*match)(void *ptr,void *key);//節(jié)點(diǎn)值對比函數(shù)
}list;
2.2.特性
- 雙端
- 無環(huán)
- 帶表頭指針和表尾指針
- 有鏈表長度
- 多態(tài)
鏈表節(jié)點(diǎn)使用*void指針來保存節(jié)點(diǎn)值，可以通過list結(jié)構(gòu)的dup、free、match三個屬性為節(jié)點(diǎn)值設(shè)置類型特定函數(shù)，所以鏈表可以用于保存各種不同類型的值。
三、字典——哈希
3.1.數(shù)據(jù)結(jié)構(gòu)
3.1.1. 哈希表
struct dictht{
dictEntry **table;//哈希表數(shù)組
unsigned long size;//哈希表大小
//哈希表大小掩碼，用于計(jì)算索引值
//總是等于size-1
unsigned long sizemask;
unsigned long used;//該哈希表已有節(jié)點(diǎn)數(shù)
}dictht;
3.1.2.哈希表節(jié)點(diǎn)
struct dictEntry{
void * key;//鍵
//值
union{
void *val;
uint64_t u64;
int64_t s64;
}v;
//指向下一個哈希表節(jié)點(diǎn)，形成鏈表
struct dictEntry *next;
}dictEntry;
3.1.3. 字典
struct dict{
dicType *type;//類型特定函數(shù)
void *privdata;//私有數(shù)據(jù)
dictht ht[2];//哈希表
//rehash索引
//當(dāng)rehash不復(fù)制拷貝時，值為-1
int rehashidx;
}dict;
3.2.哈希算法（Murmurhash算法）
redis計(jì)算哈希值和索引值的方法如下：
- 使用字典設(shè)置的哈希函數(shù)，計(jì)算鍵key的哈希值
hash = dict->type->hashFunction(key); - 使用哈希表的sizemark屬性和哈希值，計(jì)算出索引值，依據(jù)情況不同，ht[x]可以是ht[0]或者h(yuǎn)t[1]
index = hash & dict->ht[x].sizemask;（sizemask為size-1）。
3.3.解決沖突
鏈地址法來解決沖突。
3.4.rehash擴(kuò)容／收縮
3.4.1.rehash步驟
為字典ht[1]分配空間。
空間分配：
a.擴(kuò)容時，ht[1]的大小為第一個大于等于ht[0].used*2的2的n次方。
b.收縮時，ht[1]的大小為第一個大于等于ht[0].used的2的n次方（2為負(fù)值）。rehashidxs設(shè)置成0，將ht[0]的值往ht[1]復(fù)制。每個節(jié)點(diǎn)復(fù)制完成后置為NULL。
遷移完成后，釋放ht[0]，將ht[1]設(shè)置成ht[0]，并創(chuàng)建新的ht[1]。
注：rehash過程中，如果發(fā)生插入操作，則直接插入ht[1]；
如果發(fā)生查找和更新操作，查ht[0]和ht[1]。
3.4.擴(kuò)容的條件(為了節(jié)約內(nèi)存)
1）沒有執(zhí)行BGSAVE或者BGREWRITEAOF命令，并且哈希表負(fù)載因子大于等于1
2）執(zhí)行BGSAVE或者BGREWRITEAOF命令，并且哈希表負(fù)載因子大于等于5
負(fù)載因子 = ht[0].used / ht[0].size
四、跳躍表
4.1.算法
采用拋硬幣的方式?jīng)Q定數(shù)字在第幾層出現(xiàn)。
跳表具有如下性質(zhì)：
由很多層結(jié)構(gòu)組成
每一層都是一個有序的鏈表
最底層(Level 1)的鏈表包含所有元素
如果一個元素出現(xiàn)在 Level i 的鏈表中，則它在 Level i 之下的鏈表也都會出現(xiàn)。
每個節(jié)點(diǎn)包含兩個指針，一個指向同一鏈表中的下一個元素，一個指向下面一層的元素。
層高都是1至32之間的隨機(jī)數(shù)；
排序都是以score排序，如果score相等，以對象sds *obj的ASCII碼從小到大排列；
分值可以相同，對象不能相同。
4.2.數(shù)據(jù)結(jié)構(gòu)
4.2.1.跳躍表節(jié)點(diǎn)
/** * ZSETs use a specialized version of Skiplists * 跳躍表中的數(shù)據(jù)節(jié)點(diǎn) */
typedef struct zskiplistNode {
//對象
sds *obj;
//分值 double score;
// 后退指針 struct zskiplistNode *backward;
// 層
struct zskiplistLevel {
// 前進(jìn)指針
struct zskiplistNode *forward;
/** * 跨度實(shí)際上是用來計(jì)算元素排名(rank)的， * 在查找某個節(jié)點(diǎn)的過程中，將沿途訪過的所有層的跨度累積起來， * 得到的結(jié)果就是目標(biāo)節(jié)點(diǎn)在跳躍表中的排位 */
unsigned long span;
} level[];
} zskiplistNode;
4.2.2.跳躍表
/** * 跳躍表結(jié)構(gòu)體 */
typedef struct zskiplist {
struct zskiplistNode *header, *tail;
//表中節(jié)點(diǎn)數(shù)量
unsigned long length;
//表中層數(shù)最大的節(jié)點(diǎn)層數(shù)
int level;
} zskiplist;
五、整數(shù)集合
5.1.數(shù)據(jù)結(jié)構(gòu)
struct intset{
//編碼方式
uint32_t encoding;
//集合包含的元素?cái)?shù)量
uint32_t length;
//保存元素的數(shù)組
uint8_t contents[];
}intset;
注：contents元素類型 依靠encoding決定；
5.2.升級
5.2.1.升級場景
往uint32_t contents[]數(shù)組插入uint64_t的元素時，數(shù)組所有元素升級到uint64_t。
升級時，插入的元素必然大于所有元素或者小于所有元素。
注：不支持降級。
5.2.2.升級的好處
1）提高靈活性，contents[]可以有uint32_t、uint64_t多種類型
2）節(jié)約內(nèi)存
六、壓縮列表
6.1.數(shù)據(jù)結(jié)構(gòu)
zlbytes記錄整個壓縮列表占用的內(nèi)存字節(jié)數(shù),在對壓縮列表進(jìn)行內(nèi)存重分配或計(jì)算zlend的位置時使用。zltail記錄壓縮列表尾節(jié)點(diǎn)距離壓縮列表的起始地址有多少字節(jié),通過這個偏移量,可以直接確定尾節(jié)點(diǎn)的位置。zllen記錄壓縮列表包含的節(jié)點(diǎn)數(shù)量,entryX表示各種節(jié)點(diǎn),數(shù)量和長度不一定。zlend用于標(biāo)記壓縮列表的末端。
如圖,如果有一個指針p指向該壓縮列表,則尾巴節(jié)點(diǎn)的長度就是指針加上偏移量179(十六進(jìn)制0xb3=16*11+3=179),列表的長度zllen為5,表示壓縮列表包含5個節(jié)點(diǎn)。zlbytes為0xd2表示壓縮列表的總長為210字節(jié)。
由上可知,每個壓縮列表的節(jié)點(diǎn)可以保存一個字節(jié)數(shù)組或者一個整數(shù)值,那么每個節(jié)點(diǎn)肯定也有自己的結(jié)構(gòu)。
6.2.壓縮列表節(jié)點(diǎn)的構(gòu)成
每個壓縮列表節(jié)點(diǎn)可以保存一個字節(jié)數(shù)組或者一個整數(shù)值，其中字節(jié)數(shù)組可以是以下三種長度的其中一種
長度小于等于63（2的6次方-1）字節(jié)的字節(jié)數(shù)組
長度小于等于16383（2的14次方-1）字節(jié)的字節(jié)數(shù)組
長度小于等于4294967295（2的32次方-1）字節(jié)的字節(jié)數(shù)組
數(shù)值則可以是以下六種長度的其中一種
4位長介于0至12之間的無符號整數(shù)
1字節(jié)長的有符號整數(shù)
3字節(jié)長的有符號整數(shù)
int16類型整數(shù)
int32類型整數(shù)
int64類型整數(shù)
6.3.壓縮列表節(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)
6.3.1.previous_entry_length 屬性
previous_entry_length 屬性以字節(jié)為單位,記錄了壓縮列表中前一個節(jié)點(diǎn)的長度,previous_entry_length屬性的長度可以是1字節(jié)或者5字節(jié)。
- 如果前一節(jié)點(diǎn)的長度小于254字節(jié)那么previous_entry_length屬性的長度為1字節(jié)
- 如果前一節(jié)點(diǎn)的長度大于等于254字節(jié)previous_entry_length屬性的長度為5字節(jié)
根據(jù)當(dāng)前節(jié)點(diǎn)的地址和previous_entry_length的值來計(jì)算出前一個節(jié)點(diǎn)的地址
壓縮列表的從表尾向表頭遍歷操作就是使用這一原理實(shí)現(xiàn)的，只要我們擁有了一個指向某個節(jié)點(diǎn)起始地址的指針，那么通過這個指針以及這個節(jié)點(diǎn)的previous_entry_length屬性
程序就可以一直向前一個節(jié)點(diǎn)回溯，最終到達(dá)壓縮列表的表頭節(jié)點(diǎn)。
6.3.2.節(jié)點(diǎn)encoding編碼
節(jié)點(diǎn)encoding屬性記錄了節(jié)點(diǎn)的content屬性所保存數(shù)據(jù)的類型以及長度。
一字節(jié)、兩字節(jié)或者五字節(jié)長，值的最高位為00 、01、或者10的是字節(jié)數(shù)組編碼。
這種編碼表示節(jié)點(diǎn)的content屬性保存著字節(jié)數(shù)組，數(shù)組的長度有編碼除去最高兩位之后的其他位記錄。一字節(jié)長 值的最高位以11開頭的是整數(shù)編碼。
這種編碼表示節(jié)點(diǎn)的content屬性保存著整數(shù)值，整數(shù)值的類型和長度有編碼除去最高兩位之后的其他位記錄。
6.3.3 節(jié)點(diǎn)的content屬性
節(jié)點(diǎn)的content屬性負(fù)責(zé)保存節(jié)點(diǎn)的值，節(jié)點(diǎn)值可以是一個字節(jié)數(shù)組或者整數(shù)。值的類型和長度由encoding決定。
6.4. 連鎖更新
每個節(jié)點(diǎn)的previous_entry_length都記錄了前一個節(jié)點(diǎn)的長度。
- 如果前一個字節(jié)的長度小于254，那么previous_entry_length需要用1字節(jié)來保存這個長度值。
- 如果前一個字節(jié)的長度大于等于254，那么previous_entry_length需要用5字節(jié)來保存這個長度值。
現(xiàn)在假設(shè)這種情況:壓縮列表有多個連續(xù)的長度介于250-253之間的節(jié)點(diǎn)e1-eN。因?yàn)槊總€節(jié)點(diǎn)的長度都小于254字節(jié)，所以這些節(jié)點(diǎn)的previous_entry_length屬性都是1字節(jié)長度。此時如果將一個長度大于254的新節(jié)點(diǎn)設(shè)置為壓縮列表的頭節(jié)點(diǎn)，那么這個新節(jié)點(diǎn)成為頭節(jié)點(diǎn)，也就是e1節(jié)點(diǎn)的前置節(jié)點(diǎn)。此時將e1的previous_entry_length擴(kuò)展為5字節(jié)長度,此時e1又超過了254，于是e2的previous_entry_length也超過了254··· .此時這些節(jié)點(diǎn)就會連鎖式的更新，并重新分配空間。
除了新增加的節(jié)點(diǎn)會引發(fā)連鎖更新之外，刪除也會。假設(shè)中間有一個小于250的刪除了，也會連鎖更新。同上面所說的類似。
連鎖更新在最壞的情況下需要對壓縮列表執(zhí)行N次空間重分配操作。每次空間重分配的最壞復(fù)雜度為O(N),所以連鎖更新的最壞復(fù)雜度為O(N^2)。
雖然這很耗費(fèi)時間，但是實(shí)際情況下這種發(fā)生的概率非常低的。對很少一部分節(jié)點(diǎn)進(jìn)行連鎖更新絕對不會影響性能的。
七、quicklist
壓縮列表是redis3.2之前為了節(jié)約內(nèi)存開發(fā)的順序性數(shù)據(jù)結(jié)構(gòu)，它被用作列表鍵和哈希鍵的底層實(shí)現(xiàn)之一，壓縮列表可以包含多個節(jié)點(diǎn)，每個節(jié)點(diǎn)保存一個字節(jié)數(shù)組或者整數(shù)值，在添加和刪除的時候，可能會引發(fā)連鎖更新操作，但是這種操作出現(xiàn)的頻率不高。
7.1 簡介
如果使用的redis3.2版本以上的,那么就會發(fā)現(xiàn)在程序中quicklist基本取代了ziplist。既然取代肯定意味著有功能上有優(yōu)化并且對程序更加友好。其實(shí)Redis對外暴露的list的數(shù)據(jù)結(jié)構(gòu)的底層實(shí)現(xiàn)就是quicklist。先回憶下list這種數(shù)據(jù)結(jié)構(gòu)的特點(diǎn):
- list兩端的增加和刪除很方便,時間復(fù)雜度為
O(1) - list是一個雙向鏈表
- list可以在中間的任意位置插入,時間復(fù)雜度為
O(N) - list可以被用來作為隊(duì)列,因?yàn)樗厦娴奶匦?/li>
而quicklist是一個ziplist的雙向鏈表(雙向鏈表是由多個節(jié)點(diǎn)Node組成的,這里上面有介紹)。也就是說quicklist的每個節(jié)點(diǎn)都是一個ziplist。ziplist本身也記錄了數(shù)據(jù)節(jié)點(diǎn)的順序，而且在內(nèi)存中的位置是相鄰的。
7.1.1 quicklist與ziplist對比
ziplist特點(diǎn)：
- 壓縮列表ziplist結(jié)構(gòu)本身就是一個連續(xù)的內(nèi)存塊，由表頭、若干個entry節(jié)點(diǎn)和壓縮列表尾部標(biāo)識符zlend組成，通過一系列編碼規(guī)則，提高內(nèi)存的利用率，使用于存儲整數(shù)和短字符串。
- 壓縮列表ziplist結(jié)構(gòu)的缺點(diǎn)是：每次插入或刪除一個元素時，都需要進(jìn)行頻繁的調(diào)用realloc()函數(shù)進(jìn)行內(nèi)存的擴(kuò)展或減小，然后進(jìn)行數(shù)據(jù)”搬移”，甚至可能引發(fā)連鎖更新，造成嚴(yán)重效率的損失。
quicklist的特點(diǎn)：
- quicklist宏觀上是一個雙向鏈表，因此，它具有一個雙向鏈表的有點(diǎn)，進(jìn)行插入或刪除操作時非常方便，雖然復(fù)雜度為O(n)，但是不需要內(nèi)存的復(fù)制，提高了效率，而且訪問兩端元素復(fù)雜度為O(1)。
- quicklist微觀上是一片片entry節(jié)點(diǎn)，每一片entry節(jié)點(diǎn)內(nèi)存連續(xù)且順序存儲，可以通過二分查找以 log2(n)的復(fù)雜度進(jìn)行定位。
7.1.2 ziplist 與linkedlist缺陷
linkedlist便于在表的兩端進(jìn)行push和pop操作，但是它的內(nèi)存開銷較大。
首先，它的每個節(jié)點(diǎn)除了要保存數(shù)據(jù)之外還要額外保存兩個指針；
其次，雙向鏈表的各個節(jié)點(diǎn)是單獨(dú)的內(nèi)存塊，地址不連續(xù)，容易產(chǎn)生內(nèi)存碎片，還容易造成抖動。
ziplist由于是一整塊連續(xù)的內(nèi)存，存儲效率很高，但不利于添加和刪除操作，每次都會重新realloc，尤其是當(dāng)ziplist很長的時候，一次realloc造成的開銷特別的大，查詢的開銷也特別的大。
在redis 3.2之前 一般的鏈表采用LINKEDLIST編碼。
在redis 3.2版本開始，所有的鏈表都采用QUICKLIST編碼。
兩者都是使用基本的雙端鏈表數(shù)據(jù)結(jié)構(gòu)，
區(qū)別是QUICKLIST每個結(jié)點(diǎn)的值都是使用ZIPLIST進(jìn)行存儲的。
7.2 quicklist的結(jié)構(gòu)
上面提到過,quicklist是由ziplist組成的雙向鏈表,鏈表中的每個節(jié)點(diǎn)都以壓縮列表ziplist的結(jié)構(gòu)保存著數(shù)據(jù),而ziplist有多個entry節(jié)點(diǎn)保存多個數(shù)據(jù)。相當(dāng)于在一個quicklist節(jié)點(diǎn)中保存的是一整片數(shù)據(jù),而不是一個單獨(dú)的數(shù)據(jù)。
//真正表示quicklist的數(shù)據(jù)結(jié)構(gòu)
typedef struct quicklist {
// 指向頭節(jié)點(diǎn)的指針（最左邊）
quicklistNode *head;
// 指向尾節(jié)點(diǎn)的指針(最右邊)
quicklistNode *tail;
// 所有ziplist數(shù)據(jù)項(xiàng)的個數(shù)總和
unsigned long count;
// quicklist節(jié)點(diǎn)的個數(shù)
unsigned int len;
// ziplist大小設(shè)置
int fill : 16;
// 節(jié)點(diǎn)壓縮深度設(shè)置
unsigned int compress : 16;
} quicklist;
typedef struct quicklistNode {
//前驅(qū)節(jié)點(diǎn)
struct quicklistNode *prev;
//后繼節(jié)點(diǎn)
struct quicklistNode *next;
//數(shù)據(jù)指針,如果當(dāng)前節(jié)點(diǎn)的數(shù)據(jù)沒有壓縮,它就指向一個ziplist結(jié)構(gòu),否則指向quicklistLZF結(jié)構(gòu)
unsigned char *zl;
// 表示zl指向的ziplist的總大小,如果ziplist被壓縮了,它的值仍然是壓縮前的大小
unsigned int sz;
// 表示ziplist里面包含的數(shù)據(jù)項(xiàng)個數(shù),這個字段16bit
unsigned int count : 16;
// 表示ziplist是否壓縮了,1代表沒有壓縮 2代表使用LZF壓縮
unsigned int encoding : 2;
// 預(yù)留字段,固定值2,表示使用ziplist作為數(shù)據(jù)容器
unsigned int container : 2;
// 此節(jié)點(diǎn)之前是否已經(jīng)壓縮過
unsigned int recompress : 1;
// 測試用的,暫時用不上
unsigned int attempted_compress : 1;
// 擴(kuò)展字段,暫時無用
unsigned int extra : 10;
} quicklistNode;
// 此結(jié)構(gòu)表示一個被壓縮過的ziplist
typedef struct quicklistLZF {
// 壓縮后的ziplist大小
unsigned int sz;
// 存放壓縮后的ziplist字節(jié)數(shù)組
char compressed[];
} quicklistLZF;
源碼看了一遍,參照上面的表述,基本可得圖下圖的quicklist的數(shù)據(jù)結(jié)構(gòu).
7.2 創(chuàng)建quicklist及其節(jié)點(diǎn)
quicklist *quicklistCreate(void) {
struct quicklist *quicklist;
// 為quicklist分配內(nèi)存
quicklist = zmalloc(sizeof(*quicklist));
// 初始條件下,頭和尾都是null
quicklist->head = quicklist->tail = NULL;
// quicklist初始長度0
quicklist->len = 0; // 設(shè)定長度
// 數(shù)據(jù)項(xiàng)的總和,初始也是0
quicklist->count = 0;
// 壓縮深度
quicklist->compress = 0;
// 設(shè)定ziplist大小限定
quicklist->fill = -2;
return quicklist;
}
7.3 quicklist查找迭代器實(shí)現(xiàn)
現(xiàn)在基本已經(jīng)知道了quicklist的基本結(jié)構(gòu),Redis為這個結(jié)構(gòu)特意實(shí)現(xiàn)了一個迭代器,看下源碼.
//quicklist的迭代器
typedef struct quicklistIter {
//指向所屬的quicklist的指針
const quicklist *quicklist;
// 當(dāng)前quicklistNode節(jié)點(diǎn)
quicklistNode *current;
// 當(dāng)前quicklist節(jié)點(diǎn)中的ziplist
unsigned char *zi;
// 當(dāng)前ziplist結(jié)構(gòu)中的偏移量,這個用處前面有介紹過,通過這個值和zllen可以得出ziplist的尾節(jié)點(diǎn)
long offset;
// 迭代的方向標(biāo)識前序還是后序,因?yàn)槭请p向列表
int direction;
} quicklistIter;
7.4 PUSH操作
push一個entry到quicklist的頭節(jié)點(diǎn)或尾節(jié)點(diǎn)中的ziplist的頭部或尾部。底層調(diào)用了ziplistPush操作。具體push過程如下代碼:
//返回0可能插在尾節(jié)點(diǎn)或者中間的某個位置
//返回1代表節(jié)點(diǎn)插入在頭部,插入的節(jié)點(diǎn)就是頭節(jié)點(diǎn)
int quicklistPushHead(quicklist *quicklist, void *value, size_t sz) {
//暫存頭結(jié)點(diǎn)的地址
quicklistNode *orig_head = quicklist->head;
//判斷ziplist允許插入entry節(jié)點(diǎn)
if (likely(
_quicklistNodeAllowInsert(quicklist->head, quicklist->fill, sz))) {
quicklist->head->zl =
ziplistPush(quicklist->head->zl, value, sz, ZIPLIST_HEAD);
//將節(jié)點(diǎn)push到頭部并更新quicklistNode記錄ziplist大小的屬性sz
quicklistNodeUpdateSz(quicklist->head);
} else {
//如果不允許插入entry節(jié)點(diǎn)到ziplist就新創(chuàng)建一個節(jié)點(diǎn)
quicklistNode *node = quicklistCreateNode();
//將entry節(jié)點(diǎn)push到新創(chuàng)建的quicklistNode節(jié)點(diǎn)中
node->zl = ziplistPush(ziplistNew(), value, sz, ZIPLIST_HEAD);
//更新sz并把新穿件的節(jié)點(diǎn)插入到頭節(jié)點(diǎn)的位置
quicklistNodeUpdateSz(node);
_quicklistInsertNodeBefore(quicklist, quicklist->head, node);
}
quicklist->count++;
quicklist->head->count++;
// 判斷整個更新過程中頭節(jié)點(diǎn)是否變化,沒有變化返回0,變化返回1
return (orig_head != quicklist->head);
}
/* Add new entry to tail node of quicklist.
* push到尾節(jié)點(diǎn),返回0表示尾節(jié)點(diǎn)指針沒有改變,返回1表示改變了
* 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);
//push到尾部,更新sz
quicklistNodeUpdateSz(quicklist->tail);
} else {
quicklistNode *node = quicklistCreateNode();
//新建一個quicklistNode,將entry節(jié)點(diǎn)push到新創(chuàng)建的quicklistNode節(jié)點(diǎn)中
node->zl = ziplistPush(ziplistNew(), value, sz, ZIPLIST_TAIL);
quicklistNodeUpdateSz(node);
//將剛剛新創(chuàng)建的節(jié)點(diǎn)插入到尾節(jié)點(diǎn)后
_quicklistInsertNodeAfter(quicklist, quicklist->tail, node);
}
quicklist->count++;
quicklist->tail->count++;
return (orig_tail != quicklist->tail);
}
7.5 POP
從quicklist的頭節(jié)點(diǎn)或尾節(jié)點(diǎn)的ziplist中pop出一個entry，分2種情況,主要看entry保存的是字符串還是整數(shù)。如果字符串的話，需要傳入一個函數(shù)指針，這個函數(shù)叫_quicklistSaver()，真正的pop操作還是在這兩個函數(shù)基礎(chǔ)上在封裝了一次，來操作拷貝字符串的操作。如下：
//從quicklist的頭節(jié)點(diǎn)或尾節(jié)點(diǎn)pop彈出出一個entry，并將value保存在傳入傳出參數(shù)
//返回0表示沒有可pop出的entry
//返回1表示pop出了entry，存在data或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; //位置下標(biāo)
if (quicklist->count == 0) //entry數(shù)量為0，彈出失敗
return 0;
//初始化
if (data)
*data = NULL;
if (sz)
*sz = 0;
if (sval)
*sval = -123456789;
quicklistNode *node;
//記錄quicklist的頭quicklistNode節(jié)點(diǎn)或尾quicklistNode節(jié)點(diǎn)
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); //獲得當(dāng)前pos的entry地址
if (ziplistGet(p, &vstr, &vlen, &vlong)) { //將entry信息讀入到參數(shù)中
if (vstr) { //entry中是字符串值
if (data)
*data = saver(vstr, vlen); //調(diào)用特定的函數(shù)將字符串值保存到*data
if (sz)
*sz = vlen; //保存字符串長度
} else { //整數(shù)值
if (data)
*data = NULL;
if (sval)
*sval = vlong; //將整數(shù)值保存在*sval中
}
quicklistDelIndex(quicklist, node, &p); //將該entry從ziplist中刪除
return 1;
}
return 0;
}
/* Return a malloc'd copy of data passed in */
//將data內(nèi)容拷貝一份并返回地址
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;
}
