redis源码学习之数据结构---双向链表

基本数据结构在adlist.h中定义：

typedef struct listNode {
    struct listNode *prev;
    struct listNode *next;
    void *value;
} listNode;

listNode是链表的节点结构，有向前(prev)和向后 (next)两个指针，双向链表，保存的值是void*类型。

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;

list结构标识一个链表，提供头(head)、尾(tail)两个指针，分别指向头部的结点和尾部的结点；提供三个函数指针，供用户传入自定义函数，用于复制(dup)、释放(free)和 匹配(match)链表中的结点的值(value)；通过无符号整数len，标示链表的长度。由此可见，获取链表长度的时间复杂度为O(1)

typedef struct listIter {
 listNode *next;
 int direction;
} listIter;

listIter是访问链表的迭代器，指针(next)指向链表的某个结点，direction标示迭代访问的方向(宏AL_START_HEAD表示向前，AL_START_TAIL表示向后），宏在adlist.h中定义。

#define AL_START_HEAD 0
#define AL_START_TAIL 1

接下来看一下redis提供的操作链表的方法：

/* 使用宏函数实现的方法 */
//获取长度
#define listLength(l) ((l)->len)
//获取头节点
#define listFirst(l) ((l)->head)
//获取尾结点
#define listLast(l) ((l)->tail)
//获取前一个结点
#define listPrevNode(n) ((n)->prev)
//获取后一个结点
#define listNextNode(n) ((n)->next)
//获取结点的值 是一个void类型指针
#define listNodeValue(n) ((n)->value)

/* 下面3个函数主要用来设置list结构中3个函数指针，参数m为method的意思 */
#define listSetDupMethod(l,m) ((l)->dup = (m))
#define listSetFreeMethod(l,m) ((l)->free = (m))
#define listSetMatchMethod(l,m) ((l)->match = (m))

/* 下面3个函数主要用来获取list结构的单个函数指针 */
#define listGetDupMethod(l) ((l)->dup)
#define listGetFree(l) ((l)->free)
#define listGetMatchMethod(l) ((l)->match)

list *listCreate(void)，申请一个链表节点，初始化一个空链表

list *listCreate(void)
{
    struct list *list;
	//使用redis自己实现的zmalloc()分配空间，申请一个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 listRelease(list *list)，删除整个链表，包括链表本身的节点

/* Remove all the elements from the list without destroying the list itself. */
void listEmpty(list *list)
{
    unsigned long len;
    listNode *current, *next;

    current = list->head;
    len = list->len;
    while(len--) {
        next = current->next;
        //这里如果有自定义的释放函数，调用自定义的，否则调用redis自己实现的释放函数
        if (list->free) list->free(current->value);
        zfree(current);
        current = next;
    }
    list->head = list->tail = NULL;
    list->len = 0;
}

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

list *listAddNodeHead(list *list, void *value) 头插法

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

list *listAddNodeTail(list *list, void *value) 尾插法

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

list *listInsertNode(list *list, listNode *old_node, void *value, int after) 给定值，给定节点，插入给定节点的之前或之后，由参数after决定之前或之后

/*
如果 after 为 0 ，将新节点插入到 old_node 之前
如果 after 不为 0 ，将新节点插入到 old_node 之后
*/
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) {
        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) {
        node->prev->next = node;
    }
    if (node->next != NULL) {
        node->next->prev = node;
    }
    list->len++;
    return list;
}

void listDelNode(list *list, listNode *node) 删除一个节点

/*对节点私有值(private value of the node)的释放工作由调用者进行。该函数一定会成功.
  T = O(1)
*/
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);
    zfree(node);
    list->len--;
}