【redis6.0.6】redis原始碼慢慢學，慢慢看 -- 第五天：adlist

前言：

先附上人家的著作權：

Copyright ? 2009 Salvatore Sanfilippo
This file is released under the BSD license, see the COPYING file

考試差不多考完了，我又回來了，
今天起，我們就進入到redis的資料結構模塊，
其實吧，這些資料結構我們都寫過的，不過看看大佬們寫的，也是能識訓很多東西的，

先來最基礎的鏈表，它這個是雙端鏈表，

第一次寫，有點緊張，我也不知道要怎么排版，嗯，多包涵，

頭檔案

那就先來個頭檔案吧，

//結構體：
/*
listNode：節點結構體
listIter：迭代器結構體
list：鏈表結構體

我也不知道為啥要有這么多結構體，我平時吧，也就倆結構體，一個節點資訊，一個資料資訊，放這里看，就是那個listNode里面了
不急，看到后面的函式實作就知道了，

字面意思我就不注釋了啊，看著亂糟糟
*/

typedef struct listNode {
    struct listNode *prev;
    struct listNode *next;
    void *value;	//通用鏈表
} listNode;

typedef struct listIter {
    listNode *next;	//迭代器當前指向的節點，起了這么個好名字
    int direction;	//可以取以下兩個值：AL_START_HEAD和AL_START_TAIL
} listIter;

typedef struct list {
    listNode *head;
    listNode *tail;

	//這種寫法應該不陌生吧，總有人吹牛說用結構體實作類的功能，進去一看就是這個，我時間、流量都花了，就給我看這個？
    void *(*dup)(void *ptr);			//復制鏈表節點保存的值,dup和dup2陌生不？
    void (*free)(void *ptr);	
    int (*match)(void *ptr, void *key);	//比較鏈表節點所保存的節點值和另一個輸入的值是否相等
    unsigned long len;
} list;

//函式宏
#define listLength(l) ((l)->len)	//回傳鏈表l節點數量
#define listFirst(l) ((l)->head)	//后面都懂吧：懂得懂得
#define listLast(l) ((l)->tail)
#define listPrevNode(n) ((n)->prev)
#define listNextNode(n) ((n)->next)
#define listNodeValue(n) ((n)->value)

#define listSetDupMethod(l,m) ((l)->dup = (m))		//設定鏈表l的復制函式為m方法
#define listSetFreeMethod(l,m) ((l)->free = (m))	
#define listSetMatchMethod(l,m) ((l)->match = (m))	

#define listGetDupMethod(l) ((l)->dup)		//回傳鏈表l的賦值函式
#define listGetFreeMethod(l) ((l)->free)
#define listGetMatchMethod(l) ((l)->match)

/* Prototypes */
list *listCreate(void);
void listRelease(list *list);
void listEmpty(list *list);
list *listAddNodeHead(list *list, void *value);
list *listAddNodeTail(list *list, void *value);
list *listInsertNode(list *list, listNode *old_node, void *value, int after);	//在list中，根據after在old_node節點前后插入值為value的節點，
void listDelNode(list *list, listNode *node);
listIter *listGetIterator(list *list, int direction);	//為list創建一個迭代器iterator
listNode *listNext(listIter *iter);		//回傳迭代器iter指向的當前節點并更新iter
void listReleaseIterator(listIter *iter);	
list *listDup(list *orig);	//拷貝表頭為orig的鏈表并回傳
listNode *listSearchKey(list *list, void *key);
listNode *listIndex(list *list, long index);	//回傳下標為index的節點地址
void listRewind(list *list, listIter *li);		//將迭代器li重置為list的頭結點并且設定為正向迭代
void listRewindTail(list *list, listIter *li);	//將迭代器li重置為list的尾結點并且設定為反向迭代
void listRotateTailToHead(list *list);			//將尾節點插到頭結點
void listRotateHeadToTail(list *list);
void listJoin(list *l, list *o);		//把o接在l后面

/* Directions for iterators */
#define AL_START_HEAD 0     //正向迭代：從表頭向表尾進行迭代
#define AL_START_TAIL 1     //反向迭代：從表尾到表頭進行迭代

源檔案

關于空間配置器的問題，在這里：【redis6.0.6】redis原始碼慢慢學，慢慢看 – 第二天：空間配置（zmalloc）

list *listCreate(void);

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

看這個沒什么問題吧，大家都這么寫，

void listEmpty(list *list);

清空鏈表，但是不刪掉

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); //如果設定了list結構的釋放函式，則呼叫該函式釋放節點值
        zfree(current);
        current = next;
    }
    list->head = list->tail = NULL;
    list->len = 0;
}

void listRelease(list *list);

想了想，還是“斬草除根”吧，

void listRelease(list *list)    //釋放list表頭和鏈表
{
	listEmpty(list);
    zfree(list);
}

list *listAddNodeHead(list *list, void *value);

list *listAddNodeHead(list *list, void *value)  //將value添加到list鏈表的頭部
{
    listNode *node;

    if ((node = zmalloc(sizeof(*node))) == NULL)    //為新節點分配空間
        return NULL;
    node->value = value;    //設定node的value值

    if (list->len == 0) {   //將node頭插到空鏈表
        list->head = list->tail = node;
        node->prev = node->next = NULL;
    } else {                //將node頭插到非空鏈表
        node->prev = NULL;
        node->next = list->head;
        list->head->prev = node;
        list->head = node;
    }

    list->len++;    //鏈表元素計數器加1

    return list;
}

沒什么好說的啊

list *listAddNodeTail(list *list, void *value);

list *listAddNodeTail(list *list, void *value)  //將value添加到list鏈表的尾部
{
    listNode *node;

    if ((node = zmalloc(sizeof(*node))) == NULL)    //為新節點分配空間
        return NULL;
    node->value = value;    //設定node的value值
    if (list->len == 0) {   //將node尾插到空鏈表
        list->head = list->tail = node;
        node->prev = node->next = NULL;
    } else {                //將node頭插到非空鏈表
        node->prev = list->tail;
        node->next = NULL;
        list->tail->next = node;
        list->tail = node;
    }
    list->len++;    //更新鏈表節點計數器

    return list;
}

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

list *listInsertNode(list *list, listNode *old_node, void *value, int after)    //在list中，根據after在old_node節點前后插入值為value的節點，
{
    listNode *node;

    if ((node = zmalloc(sizeof(*node))) == NULL) //為新節點分配空間
        return NULL;
    node->value = value;    //設定node的value值

    if (after) {    //after 非零，則將節點插入到old_node的后面
        node->prev = old_node;
        node->next = old_node->next;
        if (list->tail == old_node) {   //目標節點如果是鏈表的尾節點，更新list的tail指標
            list->tail = node;
        }
    } else {        //after 為零，則將節點插入到old_node的前面
        node->next = old_node;
        node->prev = old_node->prev;
        if (list->head == old_node) {   //如果節點如果是鏈表的頭節點，更新list的head指標
            list->head = node;
        }
    }
    if (node->prev != NULL) {   //如果有，則更新node的前驅節點的指標
        node->prev->next = node;
    }
    if (node->next != NULL) {   //如果有，則更新node的后繼節點的指標
        node->next->prev = node;
    }
    list->len++;    //更新鏈表節點計數器
    return list;
}

void listDelNode(list *list, listNode *node);

void listDelNode(list *list, listNode *node)    //從list洗掉node節點
{
    if (node->prev) //更新node的前驅節點的指標
        node->prev->next = node->next;
    else
        list->head = node->next;
    if (node->next) //更新node的后繼節點的指標
        node->next->prev = node->prev;
    else
        list->tail = node->prev;

    if (list->free) list->free(node->value);    //如果設定了list結構的釋放函式，則呼叫該函式釋放節點值
    zfree(node);    //釋放節點
    list->len--;    //更新鏈表節點計數器
}

咱也不知道該說點啥，咱自個兒也是這么寫的，

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

listIter *listGetIterator(list *list, int direction)    //為list創建一個迭代器iterator
{
    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;
}

listNode *listNext(listIter *iter);

listNode *listNext(listIter *iter)  //回傳迭代器iter指向的當前節點并更新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;     //回傳備份的當前節點地址
}

void listReleaseIterator(listIter *iter);

void listReleaseIterator(listIter *iter) {
    zfree(iter);
}

void listRewind(list *list, listIter *li);

void listRewind(list *list, listIter *li) {
    li->next = list->head;
    li->direction = AL_START_HEAD;
}

void listRewindTail(list *list, listIter *li);

void listRewindTail(list *list, listIter *li) {
    li->next = list->tail;
    li->direction = AL_START_TAIL;
}

list *listDup(list *orig); //拷貝表頭為orig的鏈表并回傳

內啥，看一下人家的注釋吧，雖然是英文，但是不難看懂，

/* Duplicate the whole list. On out of memory NULL is returned.
 * On success a copy of the original list is returned.
 *
 * The 'Dup' method set with listSetDupMethod() function is used
 * to copy the node value. Otherwise the same pointer value of
 * the original node is used as value of the copied node.
 *
 * The original list both on success or error is never modified. */

list *listDup(list *orig)   //拷貝表頭為orig的鏈表并回傳
{
    list *copy;
    listIter iter;
    listNode *node;

    if ((copy = listCreate()) == NULL)  //創建一個表頭
        return NULL;

    //設定新建表頭的處理函式
    copy->dup = orig->dup;
    copy->free = orig->free;
    copy->match = orig->match;
    //迭代整個orig的鏈表
    listRewind(orig, &iter);    //為orig定義一個迭代器并設定迭代方向
    while((node = listNext(&iter)) != NULL) {    //迭代器根據迭代方向不停迭代
        void *value;

        //復制節點值到新節點
        if (copy->dup) {
            value = copy->dup(node->value); //如果定義了list結構中的dup指標，則使用該方法拷貝節點值，
            if (value == NULL) {
                listRelease(copy);
                return NULL;
            }
        } else
            value = node->value;    //獲得當前node的value值

        if (listAddNodeTail(copy, value) == NULL) { //將node節點尾插到copy表頭的鏈表中
            listRelease(copy);
            return NULL;
        }
    }
    return copy;    //回傳拷貝副本
}

改版之后，把迭代器變成了變數，不再是指標，

listNode *listSearchKey(list *list, void *key);

listNode *listSearchKey(list *list, void *key)  //在list中查找value為key的節點并回傳
{
    listIter iter;
    listNode *node;

    listRewind(list, &iter);    //創建迭代器
    while((node = listNext(&iter)) != NULL) {        //迭代整個鏈表
        if (list->match) {                          //如果設定list結構中的match方法，則用該方法比較
            if (list->match(node->value, key)) {
                return node;
            }
        } else {
            if (key == node->value) {
                return node;
            }
        }
    }
    return NULL;
}

listNode *listIndex(list *list, long index);

listNode *listIndex(list *list, long index) {   //回傳下標為index的節點地址
    listNode *n;

    if (index < 0) {
        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 listRotateTailToHead(list *list);

void listRotateTailToHead(list *list) {       //將尾節點插到頭結點

    if (listLength(list) <= 1) return;  //只有一個節點或空鏈表直接回傳

    listNode *tail = list->tail;
    
    /* Detach current tail */
    list->tail = tail->prev;        //取出尾節點，更新list的tail指標
    list->tail->next = NULL;
    /* Move it as head */
    list->head->prev = tail;        //將節點插到表頭，更新list的head指標
    tail->prev = NULL;
    tail->next = list->head;
    list->head = tail;
}

void listRotateHeadToTail(list *list);

void listRotateHeadToTail(list *list) {
    if (listLength(list) <= 1) return;

    listNode *head = list->head;
    /* Detach current head */
    list->head = head->next;
    list->head->prev = NULL;
    /* Move it as tail */
    list->tail->next = head;
    head->next = NULL;
    head->prev = list->tail;
    list->tail = head;
}

void listJoin(list *l, list *o);

/* Add all the elements of the list 'o' at the end of the
 * list 'l'. The list 'other' remains empty but otherwise valid. */

void listJoin(list *l, list *o) {
    if (o->head)
        o->head->prev = l->tail;

    if (l->tail)
        l->tail->next = o->head;
    else
        l->head = o->head;

    if (o->tail) l->tail = o->tail;
    l->len += o->len;

    /* Setup other as an empty list. */
    o->head = o->tail = NULL;
    o->len = 0;
}

整體感覺

挺好，大家都可以寫這個資料結構，

不過嘛，寫的也不容易，咱分析的也不容易，

建議收藏，不然刷著刷著就可能找不到了，