Redis 設計與實作（第三章） -- 連結清單adlist

Redis 設計與實作（第三章） -- 連結清單adlist

概述

1.連結清單介紹

2.連結清單API

連結清單介紹

連結清單在Redis中的應用非常廣泛，比如清單鍵list的底層實作就是使用的連結清單。除了清單鍵外，Redis的釋出與訂閱、慢查詢、螢幕等功能也用到了連結清單，Redis伺服器本身還使用了連結清單來儲存用戶端連接配接狀态，以後使用連結清單來建構用戶端輸出緩沖區。

連結清單在Redis的資料結構如下：

typedef struct listNode {
    struct listNode *prev;  //前一個節點
    struct listNode *next;  //後一個節點，可以看對外連結表為雙向連結清單
    void *value;  //節點值
} listNode;      

其實可以通過多個listNode連結起來，就是一個雙向連結清單，但是使用list結構來持有連結清單會更友善，如下：

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中連結清單的特點：

1.雙向，有prev和next指針指向前/後一個節點；

2.無環，header的prev和tail的next都指向null；

3.帶表頭和表尾指針，快速擷取表頭/尾；

4.帶連結清單長度值；

5.多态，通過void* 來儲存節點值，可以通過函數為節點值設定類型特定函數，是以連結清單能夠儲存各種不同類型的值。

連結清單API

添加頭部節點，和基本連結清單操作類似

list *listAddNodeHead(list *list, void *value)
{
    listNode *node;

    if ((node = zmalloc(sizeof(*node))) == NULL)
        return NULL;
    node->value = value;
    if (list->len == 0) {
        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++;
    return list;
}      

search節點

listNode *listSearchKey(list *list, void *key)
{
    listIter *iter;
    listNode *node;

    iter = listGetIterator(list, AL_START_HEAD); //擷取周遊器
    while((node = listNext(iter)) != NULL) {  //周遊節點
        if (list->match) { //match函數不為空，即設定了連結清單的值比較函數
            if (list->match(node->value, key)) {  //根據match函數來比較
                listReleaseIterator(iter);
                return node;
            }
        } else {  //沒設定，直接比較
            if (key == node->value) {
                listReleaseIterator(iter);
                return node;
            }
        }
    }
    listReleaseIterator(iter);
    return NULL;
}      

周遊器

typedef struct listIter {  //設定一個listIter周遊器
    listNode *next;
    int direction; //direction值為AL_START_HEAD（0）頭部節點開始，AL_START_TAIL（1）尾部節點開始
} listIter;      

擷取疊代器的方法：

listIter *listGetIterator(list *list, int direction)
{
    listIter *iter;

    if ((iter = zmalloc(sizeof(*iter))) == NULL) return NULL;
    if (direction == AL_START_HEAD)  //從頭部節點開始
        iter->next = list->head; //設定next節點為head
    else
        iter->next = list->tail;
    iter->direction = direction;
    return iter;
}      

然後通過next函數通過疊代器周遊：

/* Return the next element of an iterator.
 * It's valid to remove the currently returned element using
 * listDelNode(), but not to remove other elements.
 *
 * The function returns a pointer to the next element of the list,
 * or NULL if there are no more elements, so the classical usage patter
 * is:
 *使用方法
 * iter = listGetIterator(list,<direction>);
 * while ((node = listNext(iter)) != NULL) {
 *     doSomethingWith(listNodeValue(node));
 * }
 *
 * */
listNode *listNext(listIter *iter)
{
    listNode *current = iter->next;

    if (current != NULL) {
        if (iter->direction == AL_START_HEAD)
            iter->next = current->next;
        else
            iter->next = current->prev;
    }
    return current;
}      

posted on 2017-09-26 22:46  qiezijiajia 閱讀( ...) 評論( ...) 編輯 收藏

轉載于:https://www.cnblogs.com/dpains/p/7599441.html