Redis设计与实现读书笔记—

前言

首先，贴一下参考链接： http://www.redisbook.com/en/latest/internal-datastruct/adlist.html，另外真赞文章的作者，一个90后的小伙真不错，基本功扎实，而且非常乐于助人

概述

链表是Redis的核心数据结构之一，它不仅大量应用在Redis自身内部的实现中，而且它也是Redis的List的结构的底层实现之一

这里分析的是Redis源码里adlist.h和adlist.c

数据结构

Redis的链表结构是一种典型的双端链表doubly linked list实现

除了一个指向值的void指针外，链表中的每个节点都有两个方向指针，一个指向前驱节点，一个指向后继节点

/*

 * 链表节点

 */

typedef struct listNode {

    // 前驱节点

    struct listNode *prev;

    // 后继节点

    struct listNode *next;

    // 值

    void *value;

} listNode;

每个双端链表都被一个list结构包装起来，list结构带有两个指针，一个指向双端链表的表头节点，另一个指向双端链表的表尾节点，这个特性使得Redis可以很方便执行像RPOP LPUSH这样的命令：

/*

 * 链表

 */

typedef struct list {

    // 表头指针

    listNode *head;

    // 表尾指针

    listNode *tail;

    // 节点数量

    unsigned long len;

    // 复制函数

    void *(*dup)(void *ptr);

    // 释放函数

    void (*free)(void *ptr);

    // 比对函数

    int (*match)(void *ptr, void *key);

} list;

链表结构中还有三个函数指针 dup， free 和match，这些指针指向那些用于处理不同类型值的函数

至于len属性，就是链表节点数量计数器了

以下是双端链表和节点的一个示意图：

list结构和listNode结构的API

list和listNode都有它们自己的一族API，这里贴出来学习一下redis的源码(ps:下面的代码都是我仿照redis改写能直接编译运行的代码
)

list *listCreate(void)

/**

 * 创建一个新列表

 *

 * T = O(1)

 */

list *listCreate(void)

{

    struct list *list;

    // 为列表结构分配内存

    list = (struct list *)malloc(sizeof(struct list));

    if (list == NULL)

        return NULL;

    // 初始化属性

    list->head = list->tail = NULL;

    list->len = 0;

    list->dup = NULL;

    list->free = NULL;

    list->match = NULL;

    return list;

}

void listRelease(list *list)

/**

 * 释放整个列表

 *

 * T = O(N), N为列表长度

 */

void listRelease(list *list)

{

    unsigned long len;

    listNode *current, *next;

    current = list->head;

    len = list->len;

    while (len --) {

        next = current->next;

        // 如果列表有自带的free方法，那么先对节点值调用它

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

        // 之后释放节点

        free(current);

        current = next;

    }

    free(list);

}

list listAddNodeHead(list list, void *value)

/**

 * 新建一个包含给定value的节点，并将它加入到列表的表头

 *

 * T = O(1)

 */

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

{

    listNode *node;

    node = (listNode *)malloc(sizeof(listNode));

    if (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)

/**

 * 新建一个包含给定value的节点，并把它加入到列表的表尾

 *

 * T = O(1)

 */

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

{

    listNode *node;

    node = (listNode *)malloc(sizeof(listNode));

    if (node == NULL)

        return NULL;

    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)

/**

 * 创建一个包含值value的节点

 * 并根据after参数的指示，将新节点插入到old_node的之前或者之后

 *

 * T = O(1)

 */

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

{

	listNode *node;

	node = (listNode *)malloc(sizeof(listNode));

	if (node == NULL)

		return NULL;

	if (after) {

		// 插入到old_node之后

		node->prev = old_node;

		node->next = old_node->next;

		// 处理表尾节点

		if (list->tail == old_node) {

			list->tail = node;

		}

	} else {

		// 插入到old_node之前

		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)

/**

 * 释放列表中给定的节点

 *

 * 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);

	// 释放节点

	free(node);

	// 更新列表节点数目

	list->len --;

}

迭代器

其实我对迭代器的概念非常陌生，因为我是纯c程序员，不会c++，这里直接跟着学了！

Redis针对list结构实现了一个迭代器，用于对链表进行遍历

迭代器的结构定义如下：

/**

 * 链表迭代器

 */

typedef struct listIter {

	// 下一节点

	listNode *next;

	// 迭代方向

	int direction;

} listIter;

direction决定了迭代器是沿着next指针向后迭代，还是沿着prev指针向前迭代，这个值可以是adlist.h中的AL_START_HEAD常量或AL_START_TAIL常量：

#define AL_START_HEAD 0

#define AL_START_TAIL 1

学习一下迭代器的api实现：

listIter listGetIterator(list list, int direction)

/**

 * 创建列表list的一个迭代器，迭代方向由参数direction决定

 *

 * 每次对迭代器listNext(),迭代器返回列表的下一个节点

 *

 * T = O(1)

 */

listIter *listGetIterator(list *list, int direction)

{

	listIter *iter;

	iter = (listIter *)malloc(sizeof(listIter));

	if (iter == NULL)

		return NULL;

	// 根据迭代器的方向，将迭代器的指针指向表头或者表尾

	if (direction == AL_START_HEAD) {

		iter->next = list->head;

	} else {

		iter->next = list->tail;

	}

	// 记录方向

	iter->direction = direction;

	return iter;

}

void listRewind(list list, listIter li)

/**

 * 将迭代器iter的迭代指针倒回list的表头

 *

 * T = O(1)

 */

void listRewind(list *list, listIter *li)

{

	li->next = list->head;

	li->direction = AL_START_HEAD;

}

void listRewindTail(list list, listIter li)

/**

 * 将迭代器iter的迭代指针倒回list的表尾

 *

 * T = O(1)

 */

void listRewindTail(list *list, listIter *li)

{

	li->next = list->tail;

	li->direction = AL_START_TAIL;

}

listNode listNext(listIter iter)

/**

 * 函数要么返回当前节点，要么返回NULL，因此，常见的用法是：

 * iter = listGetIterator(list, <direction>);

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

 *     doSomethingWith(listNodeValue(node));

 * }

 *

 * T = O(1)

 */

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;

}

小结

虽然上面的代码我也都能实现，但是不得不概括redis的代码规范，写的真不错！！

巴特西

Redis设计与实现读书笔记——双链表

前言

概述