redis數(shù)據(jù)結(jié)構(gòu)

一刮萌、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.

  1. 惰性空間釋放

釋放不回收猜绣，減少內(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é)點結(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é)點值復(fù)制函數(shù)

void *(*free)(void *ptr);//節(jié)點值釋放函數(shù)

int *(*match)(void *ptr,void *key);//節(jié)點值對比函數(shù)

}list;
2.2.特性
  • 雙端
  • 無環(huán)
  • 帶表頭指針和表尾指針
  • 有鏈表長度
  • 多態(tài)
    鏈表節(jié)點使用*void指針來保存節(jié)點值合搅，可以通過list結(jié)構(gòu)的dup多搀、free、match三個屬性為節(jié)點值設(shè)置類型特定函數(shù)历筝，所以鏈表可以用于保存各種不同類型的值酗昼。

三廊谓、字典——哈希

3.1.數(shù)據(jù)結(jié)構(gòu)
3.1.1. 哈希表
struct dictht{

dictEntry **table;//哈希表數(shù)組

unsigned long size;//哈希表大小

//哈希表大小掩碼梳猪，用于計算索引值

//總是等于size-1

unsigned long sizemask;

unsigned long used;//該哈希表已有節(jié)點數(shù)

}dictht;
3.1.2.哈希表節(jié)點
struct dictEntry{

void * key;//鍵

//值

union{

void *val;

uint64_t u64;

int64_t s64;

}v;

//指向下一個哈希表節(jié)點，形成鏈表

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計算哈希值和索引值的方法如下：

  • 使用字典設(shè)置的哈希函數(shù)春弥，計算鍵key的哈希值
    hash = dict->type->hashFunction(key);
  • 使用哈希表的sizemark屬性和哈希值，計算出索引值叠荠，依據(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é)點復(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é)點包含兩個指針，一個指向同一鏈表中的下一個元素裙犹，一個指向下面一層的元素尽狠。

  • 層高都是1至32之間的隨機數(shù)；

  • 排序都是以score排序叶圃，如果score相等袄膏，以對象sds *obj的ASCII碼從小到大排列；

  • 分值可以相同掺冠，對象不能相同沉馆。

4.2.數(shù)據(jù)結(jié)構(gòu)
4.2.1.跳躍表節(jié)點
/** * ZSETs use a specialized version of Skiplists * 跳躍表中的數(shù)據(jù)節(jié)點 */ 
typedef struct zskiplistNode {
//對象 
sds *obj;

//分值 double score; 
// 后退指針 struct zskiplistNode *backward; 
// 層 
struct zskiplistLevel { 
// 前進(jìn)指針 
struct zskiplistNode *forward; 
/** * 跨度實際上是用來計算元素排名(rank)的， * 在查找某個節(jié)點的過程中德崭，將沿途訪過的所有層的跨度累積起來斥黑， * 得到的結(jié)果就是目標(biāo)節(jié)點在跳躍表中的排位 */ 
unsigned long span; 
} level[]; 
} zskiplistNode;
4.2.2.跳躍表
/** * 跳躍表結(jié)構(gòu)體 */ 
typedef struct zskiplist { 
struct zskiplistNode *header, *tail;

//表中節(jié)點數(shù)量 
unsigned long length;

//表中層數(shù)最大的節(jié)點層數(shù) 
int level; 
} zskiplist;

五、整數(shù)集合

5.1.數(shù)據(jù)結(jié)構(gòu)
struct intset{

//編碼方式

uint32_t encoding;

//集合包含的元素數(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)存重分配或計算zlend的位置時使用。zltail記錄壓縮列表尾節(jié)點距離壓縮列表的起始地址有多少字節(jié),通過這個偏移量,可以直接確定尾節(jié)點的位置琐簇。zllen記錄壓縮列表包含的節(jié)點數(shù)量,entryX表示各種節(jié)點,數(shù)量和長度不一定蒸健。zlend用于標(biāo)記壓縮列表的末端。
如圖,如果有一個指針p指向該壓縮列表,則尾巴節(jié)點的長度就是指針加上偏移量179(十六進(jìn)制0xb3=16*11+3=179),列表的長度zllen為5,表示壓縮列表包含5個節(jié)點婉商。zlbytes為0xd2表示壓縮列表的總長為210字節(jié)似忧。

壓縮列表的計算

由上可知,每個壓縮列表的節(jié)點可以保存一個字節(jié)數(shù)組或者一個整數(shù)值,那么每個節(jié)點肯定也有自己的結(jié)構(gòu)。

6.2.壓縮列表節(jié)點的構(gòu)成

每個壓縮列表節(jié)點可以保存一個字節(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é)點的數(shù)據(jù)結(jié)構(gòu)
壓縮列表節(jié)點
6.3.1.previous_entry_length 屬性

previous_entry_length 屬性以字節(jié)為單位,記錄了壓縮列表中前一個節(jié)點的長度,previous_entry_length屬性的長度可以是1字節(jié)或者5字節(jié)盯捌。

  • 如果前一節(jié)點的長度小于254字節(jié)那么previous_entry_length屬性的長度為1字節(jié)
  • 如果前一節(jié)點的長度大于等于254字節(jié)previous_entry_length屬性的長度為5字節(jié)

根據(jù)當(dāng)前節(jié)點的地址和previous_entry_length的值來計算出前一個節(jié)點的地址

壓縮列表的從表尾向表頭遍歷操作就是使用這一原理實現(xiàn)的，只要我們擁有了一個指向某個節(jié)點起始地址的指針蘑秽，那么通過這個指針以及這個節(jié)點的previous_entry_length屬性

程序就可以一直向前一個節(jié)點回溯饺著，最終到達(dá)壓縮列表的表頭節(jié)點。

6.3.2.節(jié)點encoding編碼

節(jié)點encoding屬性記錄了節(jié)點的content屬性所保存數(shù)據(jù)的類型以及長度肠牲。

  • 一字節(jié)幼衰、兩字節(jié)或者五字節(jié)長，值的最高位為00 缀雳、01渡嚣、或者10的是字節(jié)數(shù)組編碼。
    這種編碼表示節(jié)點的content屬性保存著字節(jié)數(shù)組肥印，數(shù)組的長度有編碼除去最高兩位之后的其他位記錄识椰。

  • 一字節(jié)長 值的最高位以11開頭的是整數(shù)編碼。
    這種編碼表示節(jié)點的content屬性保存著整數(shù)值深碱，整數(shù)值的類型和長度有編碼除去最高兩位之后的其他位記錄腹鹉。

6.3.3 節(jié)點的content屬性

節(jié)點的content屬性負(fù)責(zé)保存節(jié)點的值，節(jié)點值可以是一個字節(jié)數(shù)組或者整數(shù)敷硅。值的類型和長度由encoding決定功咒。

6.4. 連鎖更新

每個節(jié)點的previous_entry_length都記錄了前一個節(jié)點的長度。

  • 如果前一個字節(jié)的長度小于254竞膳，那么previous_entry_length需要用1字節(jié)來保存這個長度值航瞭。
  • 如果前一個字節(jié)的長度大于等于254诫硕，那么previous_entry_length需要用5字節(jié)來保存這個長度值坦辟。

現(xiàn)在假設(shè)這種情況:壓縮列表有多個連續(xù)的長度介于250-253之間的節(jié)點e1-eN。因為每個節(jié)點的長度都小于254字節(jié)章办，所以這些節(jié)點的previous_entry_length屬性都是1字節(jié)長度锉走。此時如果將一個長度大于254的新節(jié)點設(shè)置為壓縮列表的頭節(jié)點滨彻，那么這個新節(jié)點成為頭節(jié)點，也就是e1節(jié)點的前置節(jié)點挪蹭。此時將e1的previous_entry_length擴(kuò)展為5字節(jié)長度,此時e1又超過了254亭饵，于是e2的previous_entry_length也超過了254··· .此時這些節(jié)點就會連鎖式的更新，并重新分配空間梁厉。

除了新增加的節(jié)點會引發(fā)連鎖更新之外辜羊，刪除也會。假設(shè)中間有一個小于250的刪除了词顾，也會連鎖更新八秃。同上面所說的類似。

連鎖更新在最壞的情況下需要對壓縮列表執(zhí)行N次空間重分配操作肉盹。每次空間重分配的最壞復(fù)雜度為O(N),所以連鎖更新的最壞復(fù)雜度為O(N^2)昔驱。

雖然這很耗費時間，但是實際情況下這種發(fā)生的概率非常低的上忍。對很少一部分節(jié)點進(jìn)行連鎖更新絕對不會影響性能的骤肛。

七、quicklist

壓縮列表是redis3.2之前為了節(jié)約內(nèi)存開發(fā)的順序性數(shù)據(jù)結(jié)構(gòu)窍蓝，它被用作列表鍵和哈希鍵的底層實現(xiàn)之一腋颠，壓縮列表可以包含多個節(jié)點，每個節(jié)點保存一個字節(jié)數(shù)組或者整數(shù)值吓笙，在添加和刪除的時候秕豫，可能會引發(fā)連鎖更新操作，但是這種操作出現(xiàn)的頻率不高观蓄。

7.1 簡介

如果使用的redis3.2版本以上的,那么就會發(fā)現(xiàn)在程序中quicklist基本取代了ziplist混移。既然取代肯定意味著有功能上有優(yōu)化并且對程序更加友好。其實Redis對外暴露的list的數(shù)據(jù)結(jié)構(gòu)的底層實現(xiàn)就是quicklist侮穿。先回憶下list這種數(shù)據(jù)結(jié)構(gòu)的特點:

  • list兩端的增加和刪除很方便,時間復(fù)雜度為O(1)
  • list是一個雙向鏈表
  • list可以在中間的任意位置插入,時間復(fù)雜度為O(N)
  • list可以被用來作為隊列,因為它上面的特性

而quicklist是一個ziplist的雙向鏈表(雙向鏈表是由多個節(jié)點Node組成的,這里上面有介紹)歌径。也就是說quicklist的每個節(jié)點都是一個ziplist。ziplist本身也記錄了數(shù)據(jù)節(jié)點的順序亲茅，而且在內(nèi)存中的位置是相鄰的回铛。

7.1.1 quicklist與ziplist對比

ziplist特點：

  • 壓縮列表ziplist結(jié)構(gòu)本身就是一個連續(xù)的內(nèi)存塊，由表頭克锣、若干個entry節(jié)點和壓縮列表尾部標(biāo)識符zlend組成茵肃，通過一系列編碼規(guī)則，提高內(nèi)存的利用率袭祟，使用于存儲整數(shù)和短字符串验残。
  • 壓縮列表ziplist結(jié)構(gòu)的缺點是：每次插入或刪除一個元素時，都需要進(jìn)行頻繁的調(diào)用realloc()函數(shù)進(jìn)行內(nèi)存的擴(kuò)展或減小巾乳，然后進(jìn)行數(shù)據(jù)”搬移”您没，甚至可能引發(fā)連鎖更新鸟召，造成嚴(yán)重效率的損失。

quicklist的特點：

  • quicklist宏觀上是一個雙向鏈表氨鹏，因此欧募，它具有一個雙向鏈表的有點，進(jìn)行插入或刪除操作時非常方便仆抵，雖然復(fù)雜度為O(n)跟继，但是不需要內(nèi)存的復(fù)制，提高了效率镣丑，而且訪問兩端元素復(fù)雜度為O(1)还栓。
  • quicklist微觀上是一片片entry節(jié)點，每一片entry節(jié)點內(nèi)存連續(xù)且順序存儲传轰，可以通過二分查找以 log2(n)的復(fù)雜度進(jìn)行定位剩盒。
7.1.2 ziplist 與linkedlist缺陷

linkedlist便于在表的兩端進(jìn)行push和pop操作，但是它的內(nèi)存開銷較大慨蛙。

  • 首先辽聊，它的每個節(jié)點除了要保存數(shù)據(jù)之外還要額外保存兩個指針；

  • 其次期贫，雙向鏈表的各個節(jié)點是單獨的內(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é)點的值都是使用ZIPLIST進(jìn)行存儲的礁竞。
7.2 quicklist的結(jié)構(gòu)

上面提到過,quicklist是由ziplist組成的雙向鏈表,鏈表中的每個節(jié)點都以壓縮列表ziplist的結(jié)構(gòu)保存著數(shù)據(jù),而ziplist有多個entry節(jié)點保存多個數(shù)據(jù)。相當(dāng)于在一個quicklist節(jié)點中保存的是一整片數(shù)據(jù),而不是一個單獨的數(shù)據(jù)杉辙。

//真正表示quicklist的數(shù)據(jù)結(jié)構(gòu)
typedef struct quicklist {
    // 指向頭節(jié)點的指針（最左邊）
    quicklistNode *head;
    // 指向尾節(jié)點的指針(最右邊)
    quicklistNode *tail;
    // 所有ziplist數(shù)據(jù)項的個數(shù)總和
    unsigned long count;       
    // quicklist節(jié)點的個數(shù)
    unsigned int len;           
    // ziplist大小設(shè)置
    int fill : 16;              
    // 節(jié)點壓縮深度設(shè)置
    unsigned int compress : 16;
} quicklist;

typedef struct quicklistNode {
    //前驅(qū)節(jié)點
    struct quicklistNode *prev;
    //后繼節(jié)點
    struct quicklistNode *next;
    //數(shù)據(jù)指針,如果當(dāng)前節(jié)點的數(shù)據(jù)沒有壓縮,它就指向一個ziplist結(jié)構(gòu),否則指向quicklistLZF結(jié)構(gòu)
    unsigned char *zl;
    // 表示zl指向的ziplist的總大小,如果ziplist被壓縮了,它的值仍然是壓縮前的大小
    unsigned int sz;            
    // 表示ziplist里面包含的數(shù)據(jù)項個數(shù),這個字段16bit
    unsigned int count : 16;    
    // 表示ziplist是否壓縮了,1代表沒有壓縮  2代表使用LZF壓縮
    unsigned int encoding : 2;  
    // 預(yù)留字段,固定值2,表示使用ziplist作為數(shù)據(jù)容器
    unsigned int container : 2; 
    // 此節(jié)點之前是否已經(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).

quicklist
7.2 創(chuàng)建quicklist及其節(jié)點
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ù)項的總和,初始也是0
    quicklist->count = 0;
    // 壓縮深度
    quicklist->compress = 0;
    // 設(shè)定ziplist大小限定
    quicklist->fill = -2;  
    return quicklist;
}
7.3 quicklist查找迭代器實現(xiàn)

現(xiàn)在基本已經(jīng)知道了quicklist的基本結(jié)構(gòu),Redis為這個結(jié)構(gòu)特意實現(xiàn)了一個迭代器,看下源碼.

//quicklist的迭代器
typedef struct quicklistIter {
    //指向所屬的quicklist的指針
    const quicklist *quicklist;
    // 當(dāng)前quicklistNode節(jié)點
    quicklistNode *current;
    // 當(dāng)前quicklist節(jié)點中的ziplist
    unsigned char *zi;
    // 當(dāng)前ziplist結(jié)構(gòu)中的偏移量,這個用處前面有介紹過,通過這個值和zllen可以得出ziplist的尾節(jié)點
    long offset;  
    // 迭代的方向標(biāo)識前序還是后序,因為是雙向列表
    int direction;           
} quicklistIter;
7.4 PUSH操作

push一個entry到quicklist的頭節(jié)點或尾節(jié)點中的ziplist的頭部或尾部模捂。底層調(diào)用了ziplistPush操作。具體push過程如下代碼:

//返回0可能插在尾節(jié)點或者中間的某個位置
//返回1代表節(jié)點插入在頭部,插入的節(jié)點就是頭節(jié)點
int quicklistPushHead(quicklist *quicklist, void *value, size_t sz) {
    //暫存頭結(jié)點的地址
    quicklistNode *orig_head = quicklist->head; 
    //判斷ziplist允許插入entry節(jié)點
    if (likely(
            _quicklistNodeAllowInsert(quicklist->head, quicklist->fill, sz))) {
        quicklist->head->zl =
            ziplistPush(quicklist->head->zl, value, sz, ZIPLIST_HEAD);  
        //將節(jié)點push到頭部并更新quicklistNode記錄ziplist大小的屬性sz
        quicklistNodeUpdateSz(quicklist->head); 
    } else {        
        //如果不允許插入entry節(jié)點到ziplist就新創(chuàng)建一個節(jié)點
        quicklistNode *node = quicklistCreateNode(); 
        //將entry節(jié)點push到新創(chuàng)建的quicklistNode節(jié)點中
        node->zl = ziplistPush(ziplistNew(), value, sz, ZIPLIST_HEAD);
        //更新sz并把新穿件的節(jié)點插入到頭節(jié)點的位置
        quicklistNodeUpdateSz(node);    
        _quicklistInsertNodeBefore(quicklist, quicklist->head, node);   
    }
    quicklist->count++;                     
    quicklist->head->count++;  
    // 判斷整個更新過程中頭節(jié)點是否變化,沒有變化返回0,變化返回1
    return (orig_head != quicklist->head);  
}

/* Add new entry to tail node of quicklist.
 * push到尾節(jié)點,返回0表示尾節(jié)點指針沒有改變,返回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é)點push到新創(chuàng)建的quicklistNode節(jié)點中
        node->zl = ziplistPush(ziplistNew(), value, sz, ZIPLIST_TAIL);
        quicklistNodeUpdateSz(node);
        //將剛剛新創(chuàng)建的節(jié)點插入到尾節(jié)點后
        _quicklistInsertNodeAfter(quicklist, quicklist->tail, node);
    }
    quicklist->count++;
    quicklist->tail->count++;
    return (orig_tail != quicklist->tail); 
}
7.5 POP

從quicklist的頭節(jié)點或尾節(jié)點的ziplist中pop出一個entry，分2種情況,主要看entry保存的是字符串還是整數(shù)枫绅。如果字符串的話泉孩，需要傳入一個函數(shù)指針硼端，這個函數(shù)叫_quicklistSaver()并淋，真正的pop操作還是在這兩個函數(shù)基礎(chǔ)上在封裝了一次，來操作拷貝字符串的操作珍昨。如下：

//從quicklist的頭節(jié)點或尾節(jié)點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é)點或尾quicklistNode節(jié)點
    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;
}
最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 人面猴
    序言：七十年代末兔毙，一起剝皮案震驚了整個濱河市，隨后出現(xiàn)的幾起案子兄春，更是在濱河造成了極大的恐慌澎剥，老刑警劉巖，帶你破解...
    沈念sama閱讀 216,919評論 6贊 502
  • 死咒
    序言：濱河連續(xù)發(fā)生了三起死亡事件赶舆，死亡現(xiàn)場離奇詭異哑姚，居然都是意外死亡，警方通過查閱死者的電腦和手機芜茵，發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 92,567評論 3贊 392
  • 救了他兩次的神仙讓他今天三更去死
    文/潘曉璐 我一進(jìn)店門叙量，熙熙樓的掌柜王于貴愁眉苦臉地迎上來，“玉大人九串，你說我怎么就攤上這事绞佩。” “怎么了猪钮？”我有些...
    開封第一講書人閱讀 163,316評論 0贊 353
  • 道士緝兇錄：失蹤的賣姜人
    文/不壞的土叔 我叫張陵品山，是天一觀的道長。 經(jīng)常有香客問我烤低，道長谆奥，這世上最難降的妖魔是什么？ 我笑而不...
    開封第一講書人閱讀 58,294評論 1贊 292
  • ?港島之戀（遺憾婚禮）
    正文 為了忘掉前任拂玻，我火速辦了婚禮酸些，結(jié)果婚禮上，老公的妹妹穿的比我還像新娘檐蚜。我一直安慰自己魄懂，他們只是感情好，可當(dāng)我...
    茶點故事閱讀 67,318評論 6贊 390
  • 惡毒庶女頂嫁案：這布局不是一般人想出來的
    文/花漫 我一把揭開白布闯第。 她就那樣靜靜地躺著市栗，像睡著了一般。 火紅的嫁衣襯著肌膚如雪。 梳的紋絲不亂的頭發(fā)上填帽，一...
    開封第一講書人閱讀 51,245評論 1贊 299
  • 城市分裂傳說
    那天蛛淋，我揣著相機與錄音，去河邊找鬼篡腌。 笑死褐荷，一個胖子當(dāng)著我的面吹牛，可吹牛的內(nèi)容都是我干的嘹悼。 我是一名探鬼主播叛甫，決...
    沈念sama閱讀 40,120評論 3贊 418
  • 雙鴛鴦連環(huán)套：你想象不到人心有多黑
    文/蒼蘭香墨 我猛地睜開眼，長吁一口氣：“原來是場噩夢啊……” “哼杨伙！你這毒婦竟也來了其监？” 一聲冷哼從身側(cè)響起，我...
    開封第一講書人閱讀 38,964評論 0贊 275
  • 萬榮殺人案實錄
    序言：老撾萬榮一對情侶失蹤限匣，失蹤者是張志新（化名）和其女友劉穎抖苦，沒想到半個月后，有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體米死，經(jīng)...
    沈念sama閱讀 45,376評論 1贊 313
  • ?護(hù)林員之死
    正文 獨居荒郊野嶺守林人離奇死亡锌历，尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點故事閱讀 37,592評論 2贊 333
  • ?白月光啟示錄
    正文 我和宋清朗相戀三年，在試婚紗的時候發(fā)現(xiàn)自己被綠了哲身。 大學(xué)時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片辩涝。...
    茶點故事閱讀 39,764評論 1贊 348
  • 活死人
    序言：一個原本活蹦亂跳的男人離奇死亡，死狀恐怖勘天，靈堂內(nèi)的尸體忽然破棺而出怔揩，到底是詐尸還是另有隱情，我是刑警寧澤脯丝，帶...
    沈念sama閱讀 35,460評論 5贊 344
  • ?日本核電站爆炸內(nèi)幕
    正文 年R本政府宣布商膊，位于F島的核電站，受9級特大地震影響宠进，放射性物質(zhì)發(fā)生泄漏晕拆。R本人自食惡果不足惜，卻給世界環(huán)境...
    茶點故事閱讀 41,070評論 3贊 327
  • 男人毒藥：我在死后第九天來索命
    文/蒙蒙 一材蹬、第九天 我趴在偏房一處隱蔽的房頂上張望实幕。 院中可真熱鬧，春花似錦堤器、人聲如沸昆庇。這莊子的主人今日做“春日...
    開封第一講書人閱讀 31,697評論 0贊 22
  • 一樁弒父案闸溃，背后竟有這般陰謀
    文/蒼蘭香墨 我抬頭看了看天上的太陽整吆。三九已至拱撵，卻和暖如春，著一層夾襖步出監(jiān)牢的瞬間表蝙，已是汗流浹背拴测。 一陣腳步聲響...
    開封第一講書人閱讀 32,846評論 1贊 269
  • 情欲美人皮
    我被黑心中介騙來泰國打工， 沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留府蛇，地道東北人集索。 一個月前我還...
    沈念sama閱讀 47,819評論 2贊 370
  • 代替公主和親
    正文 我出身青樓，卻偏偏與公主長得像欲诺，于是被迫代替她去往敵國和親抄谐。 傳聞我的和親對象是個殘疾皇子渺鹦，可洞房花燭夜當(dāng)晚...
    茶點故事閱讀 44,665評論 2贊 354