天天看點
傳回

Redis源碼剖析--雙端連結清單sdlistRedis源碼剖析--雙端連結清單sdlistsdlist的資料結構sdlist疊代器結構sdlist基本操作sdlist小結

class="primary">

Redis源碼剖析--雙端連結清單sdlist

  • sdlist的資料結構
  • sdlist疊代器結構
  • sdlist基本操作
    • sdlist建立
    • sdlist釋放
    • 插入節點
      • 向頭部插入節點
      • 向尾部添加節點
      • 向任意位置插入節點
    • 删除節點
    • 疊代器相關操作
      • 擷取疊代器
      • 釋放疊代器
      • 重置疊代器
      • 擷取下一個疊代器
    • 連結清單複制函數
    • 查找函數
    • 連結清單旋轉函數
  • sdlist小結

今天來分析Redis的一個基本資料結構–雙端連結清單，其定義和實作主要在sdlist.h和sdlist.c檔案中。其主要用在實作清單鍵、事務子產品儲存輸入指令和伺服器子產品，訂閱子產品儲存多個用戶端等。

sdlist的資料結構

Redis為雙端連結清單的每一個節點定義了如下的結構體。

// 連結清單節點定義
typedef struct listNode {
    struct listNode *prev;  // 指向前一個節點
    struct listNode *next;  // 指向後一個節點
    void *value; // 節點值
} listNode;

與一般的雙端連結清單無異，定義了連結清單節點的結構體之後，下面就定義連結清單的結構體，用來友善管理連結清單節點，其結構體定義如下：

typedef struct list {
    listNode *head;  // 指向連結清單頭節點
    listNode *tail;  // 指向連結清單尾節點
    void *(*dup)(void *ptr); // 自定義節點值複制函數
    void (*free)(void *ptr); // 自定義節點值釋放函數
    int (*match)(void *ptr, void *key); // 自定義節點值比對函數
    unsigned long len; // 連結清單長度
} list;

Redis在實作連結清單的時候，定義其為雙端無環連結清單，其示意圖如下：

Redis源碼剖析--雙端連結清單sdlistRedis源碼剖析--雙端連結清單sdlistsdlist的資料結構sdlist疊代器結構sdlist基本操作sdlist小結

此外，Redis對其結構體提供了一系列的宏定義函數，友善操作其結構體參數

#define listLength(l) ((l)->len)  // 擷取list長度
#define listFirst(l) ((l)->head)  // 擷取list頭節點指針
#define listLast(l) ((l)->tail)   // 擷取list尾節點指針
#define listPrevNode(n) ((n)->prev)  // 擷取目前節點前一個節點
#define listNextNode(n) ((n)->next)  // 擷取目前節點後一個節點
#define listNodeValue(n) ((n)->value) // 擷取目前節點的值

#define listSetDupMethod(l,m) ((l)->dup = (m))  // 設定節點值複制函數
#define listSetFreeMethod(l,m) ((l)->free = (m))  // 設定節點值釋放函數
#define listSetMatchMethod(l,m) ((l)->match = (m))  // 設定節點值比對函數

#define listGetDupMethod(l) ((l)->dup) // 擷取節點值指派函數
#define listGetFree(l) ((l)->free)  // 擷取節點值釋放函數
#define listGetMatchMethod(l) ((l)->match)  // 擷取節點值比對函數

sdlist疊代器結構

Redis為sdlist定義了一個疊代器結構，其能正序和逆序的通路list結構。

typedef struct listIter {
    listNode *next; // 指向下一個節點
    int direction; // 方向參數，正序和逆序
} listIter;

對于direction參數，Redis提供了兩個宏定義

#define AL_START_HEAD 0  // 從頭到尾
#define AL_START_TAIL 1  // 從尾到頭

sdlist基本操作

sdlist建立

sdlist提供了listCreate函數來建立一個空的連結清單。

list *listCreate(void)
{
    struct list *list; // 定義一個連結清單指針

    if ((list = zmalloc(sizeof(*list))) == NULL) // 申請記憶體
        return NULL; 
    list->head = list->tail = NULL;  // 空連結清單的頭指針和尾指針均為空
    list->len = 0;  // 設定長度
    list->dup = NULL;    // 自定義複制函數初始化
    list->free = NULL;   // 自定義釋放函數初始化
    list->match = NULL;  // 自定義比對函數初始化
    return list;
}

sdlist釋放

sdlist提供了listRelease函數來釋放整個連結清單

void listRelease(list *list)
{
    unsigned long len;
    listNode *current, *next;
            
current <span style="color:#f92672">=</span> list<span style="color:#f92672">-&gt;</span>head;
len <span style="color:#f92672">=</span> list<span style="color:#f92672">-&gt;</span>len;
<span style="color:#66d9ef">while</span>(len<span style="color:#f92672">--</span>) {
    next <span style="color:#f92672">=</span> current<span style="color:#f92672">-&gt;</span>next;
    <span style="color:#75715e">// 如果定義了節點值釋放函數，需要調用

if (list->free) list->free(current->value);

zfree(current); // 釋放目前節點

current = next;

}

zfree(list); // 釋放連結清單頭

}

插入節點

sdlist提供了三個函數來完成向list中插入一個節點的功能。

向頭部插入節點 

// 該函數向list的頭部插入一個節點
list *listAddNodeHead(list *list, void *value)
{
    listNode *node;
            
<span style="color:#66d9ef">if</span> ((node <span style="color:#f92672">=</span> zmalloc(<span style="color:#66d9ef">sizeof</span>(<span style="color:#f92672">*</span>node))) <span style="color:#f92672">==</span> NULL)
    <span style="color:#66d9ef">return</span> NULL;
node<span style="color:#f92672">-&gt;</span>value <span style="color:#f92672">=</span> value;
<span style="color:#66d9ef">if</span> (list<span style="color:#f92672">-&gt;</span>len <span style="color:#f92672">==</span> <span style="color:#ae81ff">0</span>) { <span style="color:#75715e">// 如果連結清單為空

list->head = list->tail = node;

node->prev = node->next = NULL;

} else { // 如果連結清單非空

node->prev = NULL;

node->next = list->head;

list->head->prev = node;

list->head = node;

}

list->len++; // 長度+1

return list;

}

向尾部添加節點 

// 該函數可以在list的尾部添加一個節點
list *listAddNodeTail(list *list, void *value)
{
    listNode *node;
            
<span style="color:#66d9ef">if</span> ((node <span style="color:#f92672">=</span> zmalloc(<span style="color:#66d9ef">sizeof</span>(<span style="color:#f92672">*</span>node))) <span style="color:#f92672">==</span> NULL)
    <span style="color:#66d9ef">return</span> NULL;
node<span style="color:#f92672">-&gt;</span>value <span style="color:#f92672">=</span> value;
<span style="color:#66d9ef">if</span> (list<span style="color:#f92672">-&gt;</span>len <span style="color:#f92672">==</span> <span style="color:#ae81ff">0</span>) { <span style="color:#75715e">// 如果連結清單為空

list->head = list->tail = node;

node->prev = node->next = NULL;

} else { // 如果連結清單非空

node->prev = list->tail;

node->next = NULL;

list->tail->next = node;

list->tail = node;

}

list->len++; // 長度+1

return list;

}

向任意位置插入節點 

// 向任意位置插入節點
// 其中，old_node為插入位置
//      value為插入節點的值
//      after為0時表示插在old_node前面，為1時表示插在old_node後面
list *listInsertNode(list *list, listNode *old_node, void *value, int after) {
    listNode *node;
            
<span style="color:#66d9ef">if</span> ((node <span style="color:#f92672">=</span> zmalloc(<span style="color:#66d9ef">sizeof</span>(<span style="color:#f92672">*</span>node))) <span style="color:#f92672">==</span> NULL)
    <span style="color:#66d9ef">return</span> NULL;
node<span style="color:#f92672">-&gt;</span>value <span style="color:#f92672">=</span> value;
<span style="color:#66d9ef">if</span> (after) { <span style="color:#75715e">// 向後插入

node->prev = old_node;

node->next = old_node->next;

// 如果old_node為尾節點的話需要改變tail

if (list->tail old_node) {

list->tail = node;

}

} else { // 向前插入

node->next = old_node;

node->prev = old_node->prev;

// 如果old_node為頭節點的話需要改變head

if (list->head old_node) {

list->head = node;

}

}

if (node->prev != NULL) {

node->prev->next = node;

}

if (node->next != NULL) {

node->next->prev = node;

}

list->len++;

return list;

}

删除節點 

void listDelNode(list *list, listNode *node)
{
    if (node->prev) // 删除節點不為頭節點
        node->prev->next = node->next;
    else // 删除節點為頭節點需要改變head的指向
        list->head = node->next;
    if (node->next)  // 删除節點不為尾節點
        node->next->prev = node->prev;
    else // 删除節點為尾節點需要改變tail的指向
        list->tail = node->prev;
    if (list->free) list->free(node->value); // 釋放節點值
    zfree(node);  // 釋放節點
    list->len--;
}

疊代器相關操作

sdlist為其疊代器提供了一些操作，用來完成擷取疊代器，釋放疊代器，重置疊代器，擷取下一個疊代器等操作，具體源碼見如下分析。

擷取疊代器 

listIter *listGetIterator(list *list, int direction)
{
    listIter *iter;  // 聲明疊代器

    if ((iter = zmalloc(sizeof(*iter))) == NULL) return NULL;
    // 根據疊代方向來初始化iter
    if (direction == AL_START_HEAD)
        iter->next = list->head;
    else
        iter->next = list->tail;
    iter->direction = direction;
    return iter;
}

釋放疊代器 

void listReleaseIterator(listIter *iter) {
    zfree(iter); // 直接調用zfree來釋放
}

重置疊代器

重置疊代器分為兩種，一種是重置正向疊代器，一種是重置為逆向疊代器

// 重置為正向疊代器
void listRewind(list *list, listIter *li) {
    li->next = list->head;
    li->direction = AL_START_HEAD;
}
// 重置為逆向疊代器
void listRewindTail(list *list, listIter *li) {
    li->next = list->tail;
    li->direction = AL_START_TAIL;
}

擷取下一個疊代器 

// 根據direction屬性來擷取下一個疊代器
listNode *listNext(listIter *iter)
{
    listNode *current = iter->next;
            
<span style="color:#66d9ef">if</span> (current <span style="color:#f92672">!=</span> NULL) {
    <span style="color:#66d9ef">if</span> (iter<span style="color:#f92672">-&gt;</span>direction <span style="color:#f92672">==</span> AL_START_HEAD)
        iter<span style="color:#f92672">-&gt;</span>next <span style="color:#f92672">=</span> current<span style="color:#f92672">-&gt;</span>next;
    <span style="color:#66d9ef">else</span>
        iter<span style="color:#f92672">-&gt;</span>next <span style="color:#f92672">=</span> current<span style="color:#f92672">-&gt;</span>prev;
}
<span style="color:#66d9ef">return</span> current;

}

連結清單複制函數

sdlist提供了listDup函數，用于複制整個連結清單。

list *listDup(list *orig)
{
    list *copy;
    listIter iter;
    listNode *node;
            
<span style="color:#66d9ef">if</span> ((copy <span style="color:#f92672">=</span> listCreate()) <span style="color:#f92672">==</span> NULL)
    <span style="color:#66d9ef">return</span> NULL;
<span style="color:#75715e">// 複制節點值操作函數

copy->dup = orig->dup;

copy->free = orig->free;

copy->match = orig->match;

// 重置疊代器

listRewind(orig, &iter);

while((node = listNext(&iter)) != NULL) {

void *value;

// 複制節點

// 如果定義了dup函數，則按照dup函數來複制節點值

if (copy->dup) {

value = copy->dup(node->value);

if (value NULL) {

listRelease(copy);

return NULL;

}

} else // 如果沒有則直接指派

value = node->value;

// 依次向尾部添加節點

if (listAddNodeTail(copy, value) NULL) {

listRelease(copy);

return NULL;

}

}

return copy;

}

查找函數

sdlist提供了兩種查找函數。其一是根據給定節點值，在連結清單中查找該節點

listNode *listSearchKey(list *list, void *key)
{
    listIter iter;
    listNode *node;
            
listRewind(list, <span style="color:#f92672">&amp;</span>iter);
<span style="color:#66d9ef">while</span>((node <span style="color:#f92672">=</span> listNext(<span style="color:#f92672">&amp;</span>iter)) <span style="color:#f92672">!=</span> NULL) {
    <span style="color:#66d9ef">if</span> (list<span style="color:#f92672">-&gt;</span>match) { <span style="color:#75715e">// 如果定義了match比對函數，則利用該函數進行節點比對

if (list->match(node->value, key)) {

return node;

}

} else { // 如果沒有定義match，則直接比較節點值

if (key == node->value) { // 找到該節點

return node;

}

}

}

// 沒有找到就傳回NULL

return NULL;

}

其二是根據序号來查找節點

listNode *listIndex(list *list, long index) {
    listNode *n;
            
<span style="color:#66d9ef">if</span> (index <span style="color:#f92672">&lt;</span> <span style="color:#ae81ff">0</span>) {  <span style="color:#75715e">// 序号為負，則倒序查找

index = (-index)-1;

n = list->tail;

while(index– && n) n = n->prev;

} else { // 正序查找

n = list->head;

while(index– && n) n = n->next;

}

return n;

}

連結清單旋轉函數

旋轉操作其實就是講表尾節點移除，然後插入到表頭，成為新的表頭

void listRotate(list *list) {
    listNode *tail = list->tail;
            
<span style="color:#66d9ef">if</span> (listLength(list) <span style="color:#f92672">&lt;=</span> <span style="color:#ae81ff">1</span>) <span style="color:#66d9ef">return</span>;

<span style="color:#75715e">// 取出表尾指針

list->tail = tail->prev;

list->tail->next = NULL;

// 将其移動到表頭并成為新的表頭指針

list->head->prev = tail;

tail->prev = NULL;

tail->next = list->head;

list->head = tail;

}

sdlist小結

分析完sdlist的源碼，着實是把雙向連結清單的基本操作都複習了一遍，Redis的作者還真是喜歡造輪子，不愧是輪子界的鼻祖啊！雖然這些基本操作很簡單，但是可以學到一些優秀的設計，例如：sdlist疊代器的設計等，這些都對了解Redis的相關操作有着很大的幫助作用。

  • Redis
  • SourceCode
Redis源碼剖析--雙端連結清單sdlistRedis源碼剖析--雙端連結清單sdlistsdlist的資料結構sdlist疊代器結構sdlist基本操作sdlist小結

About Zeech Nothing to say « Previous

Redis源碼剖析--動态字元串sds

Next »

Redis源碼剖析--字典dict

Please enable JavaScript to view the comments powered by Disqus.

</div>
Redis設計與實作 redis源碼分析 Redis 雙端連結清單sdlist
上一篇: 淘寶使用者行為統計分析-python一 分析背景二 分析目的三 分析思路四 資料處理五 統計分析六 結論及建議七（個人總結）
下一篇: leetcode第16題（candy）

繼續閱讀