天天看點
傳回

Redis源碼學習簡記（二） adlist原理與個人了解

redis中的adlist實質上是一個雙向連結清單。裡面實作了自己的iterator（包含正負方向）。作者對于連結清單寫的真的是流暢，看得賞心悅目。沒有一句多餘的，很值得學習。

資料結構

總體來說分為三個資料類型。

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;

listNode結構體。每個節點的資料結構

typedef struct listNode {
    struct listNode *prev;//前指正
    struct listNode *next;//後指針
    void *value;//存儲的資料
} listNode;

iterator結構體

typedef struct listIter {
    listNode *next;//下一個節點
    int direction;//方向 利用宏定義來判斷
} listIter;
           
/* Directions for iterators */
#define AL_START_HEAD 0 //從前往後即為0
#define AL_START_TAIL 1//從後往前

垃圾字型畫出來的圖

Redis源碼學習簡記（二） adlist原理與個人了解

在所提供的實作函數中，個人認為建立，插入，删除，複制，查找以及疊代器的操作比較重要。

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;
}

listEmpty清空連結清單元素，但是沒有釋放連結清單

void listEmpty(list *list)
{
    unsigned long len;
    listNode *current, *next;

    current = list->head;//連結清單頭結點
    len = list->len;//擷取長度
    while(len--) {
        next = current->next;
        if (list->free) list->free(current->value);//若有free函數則使用free清理value
        zfree(current);//删除節點
        current = next;//循環
    }
    list->head = list->tail = NULL;//連結清單初始化
    list->len = 0;
}

listRelease清空連結清單元素及自身，調用listEmpty

/* Free the whole list.
 *
 * This function can't fail. */
void listRelease(list *list)
{
    listEmpty(list);
    zfree(list);
}

listAddNodeHead頭插法

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;
}

listAddNodeTail尾插法  與頭插法基本一緻

list *listAddNodeTail(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 = list->tail;
        node->next = NULL;
        list->tail->next = node;
        list->tail = node;
    }
    list->len++;
    return list;
}

listInsertNode 至指定的節點前插入或後面插入新節點傳回插入後的連結清單

list *listInsertNode(list *list, listNode *old_node, void *value, int after) {
    listNode *node;

    if ((node = zmalloc(sizeof(*node))) == NULL)//配置設定新的空間
        return NULL;
    node->value = value;
    if (after) {//若after為真則表示新節點插在old_node後否則插在其前面
        node->prev = old_node;
        node->next = old_node->next;
        if (list->tail == old_node) {//判斷為尾節點的情況
            list->tail = node;
        }
    } else {
        node->next = old_node;
        node->prev = old_node->prev;
        if (list->head == old_node) {//判斷為頭節點的情況
            list->head = node;
        }
    }
    if (node->prev != NULL) {//若不是頭節點，要調整前面節點的next指針
        node->prev->next = node;
    }
    if (node->next != NULL) {//若不是尾節點，要調整後面節點的pre指針
        node->next->prev = node;
    }
    list->len++;//長度加一
    return list;
}

listDelNode 删除指定的節點

void listDelNode(list *list, listNode *node)
{
    if (node->prev)
        node->prev->next = node->next;//若存在前節點
    else
        list->head = node->next;//否則該節點為頭結點
    if (node->next)
        node->next->prev = node->prev;//若存在後面的節點
    else
        list->tail = node->prev;//否則該節點為尾節點
    if (list->free) list->free(node->value);//若定義了free 釋放value空間
    zfree(node);//釋放節點
    list->len--;//長度減1
}

listGetIterator 擷取疊代器

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;
    else
        iter->next = list->tail;
    iter->direction = direction;/指派方向
    return iter;
}

listNext 疊代器傳回目前值，并且向後移

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;
}

listDup 複制一個相同的連結清單，傳回為新的連結清單 (dup  dup2為linux中 檔案描述符的複制的函數名)

list *listDup(list *orig)
{
    list *copy;
    listIter iter;
    listNode *node;

    if ((copy = listCreate()) == NULL) //
        return NULL;
    copy->dup = orig->dup; //拷貝相應的api函數
    copy->free = orig->free;
    copy->match = orig->match;
    listRewind(orig, &iter);//擷取一個從後往前的疊代器。這裡疊代器不是指針，省去了釋放空間的操作。申請的空間在棧中。(這個小細節真是贊)
    while((node = listNext(&iter)) != NULL) {
        void *value;

        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);//失敗則調用釋放記憶體的函數釋放，并傳回NULL
            return NULL;
        }
    }
    return copy;
}

listSearchKey 根據可以key值找節點

listNode *listSearchKey(list *list, void *key)
{
    listIter iter; //同樣使用的不是指針，省去釋放煩惱。
    listNode *node;

    listRewind(list, &iter);//取得反向疊代器 與c++類似
    while((node = listNext(&iter)) != NULL) {
        if (list->match) {//若有math函數則調用
            if (list->match(node->value, key)) {
                return node;
            }
        } else {
            if (key == node->value) {//否則直接判等
                return node;
            }
        }
    }
    return NULL;//若找不到則傳回空
}

對于這一資料結構的學習，複習了對連結清單的基本操作。

Reids源碼學習
上一篇: Redis源碼學習簡記（六）intset原理與個人了解
下一篇: windows下 redis安裝

繼續閱讀