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倒数第二个节点
//如果超过链表的索引，则返回null
void 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);
}
/**
* 新建一个包含给定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的实现方法（奇淫技巧操作）
网友评论