Redis中双链表实现的基本结构：
1.节点结构
typedef struct listNode {
struct listNode *prev;
//前向节点 struct listNode *next;
//后向节点 void *value;
//该节点的值}
listNode;
2.双向链表结构
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;
3.双向链表遍历器
typedef struct listIter {
listNode *next;
//下一个节点 int direction;
}
listIter;
方向定义 #define AL_START_HEAD 0 //向前查找 #define AL_START_TAIL 1 //向后查找
4.宏定义函数
#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)#define listNodeValue(n) ((n)->value)#define listSetDupMethod(l,m) ((l)->dup = (m))#define listSetFreeMethod(l,m) ((l)->free = (m))#define listSetMatchMethod(l,m) ((l)->match = (m))#define listGetDupMethod(l) ((l)->dup)#define listGetFree(l) ((l)->free)#define listGetMatchMethod(l) ((l)->match)
5.定义函数
list *listCreate(void);
//创建一个新的链表。该链表可以使用AlFree（）方法释放。 //但使用AlFree（）方法前需要释放用户释放私有节点的值。 //如果没有创建成功，返回null；创建成功则返回指向新链表的指针。void listRelease(list *list);
//释放整个链表，此函数不会执行失败。调用zfree(list *list)方法,定义在Zmalloc.c中。list *listAddNodeHead(list *list, void *value);
//向链表头部中增加一个节点list *listAddNodeTail(list *list, void *value);
//向链表尾部增加一个节点list *listInsertNode(list *list, listNode *old_node, void *value, int after);
//向某个节点位置插入节点 after为方向void listDelNode(list *list, listNode *node);
//从链表上删除特定节点，调用者释放特定私用节点的值。 //该函数不会执行失败listIter *listGetIterator(list *list, int direction);
//返回某个链表的迭代器。 //迭代器的listNext（）方法会返回链表的下个节点。direction是方向 //该函数不会执行失败。listNode *listNext(listIter *iter);
void listReleaseIterator(listIter *iter);
//释放迭代器的内存。list *listDup(list *orig);
//复制整个链表。当内存溢出时返回null，成功时返回原链表的一个备份 //不管该方法是否执行成功，原链表不会改变。listNode *listSearchKey(list *list, void *key);
//从特定的链表查找key。成功则返回第一个匹配节点的指针 //如果没有匹配，则返回null。listNode *listIndex(list *list, long index);
//序号从0开始，链表的头的索引为0.1为头节点的下个节点。一次类推。 //负整数用来表示从尾部开始计数。-1表示最后一个节点，-2倒数第二个节点 //如果超过链表的索引，则返回nullvoid listRewind(list *list, listIter *li) {
li->next = list->head;
li->direction = AL_START_HEAD;
}
void listRewindTail(list *list, listIter *li) {
li->next = list->tail;
li->direction = AL_START_TAIL;
}
void listRotate(list *list);
//旋转链表，移除尾节点并插入头部。
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;
}
