Redis源码中广泛使用 **adlist(A generic doubly linked list)**,作为一种通用的双向链表,用于简单的数据集合操作.adlist提供了基本的增删改查能力,并支持用户自定义深拷贝、释放和匹配操作来维护数据集合中的泛化数据 ◆value◆.
Redis源码中广泛使用 adlist(A generic doubly linked list),作为一种通用的双向链表,用于简单的数据集合操作.adlist提供了基本的增删改查能力,并支持用户自定义深拷贝、释放和匹配操作来维护数据集合中的泛化数据 value.
链表节点 listNode, 作为双向链表, prev, next 指针分别指向前序和后序节点.void* 指针类型的 value 用于存放泛化的数据类型(如果数据类型的 size 小于 sizeof(void*), 则可直接存放在 value中. 否则 value 存放指向该泛化类型的指针).
// in adlist.h
typedef struct listNode {
struct listNode *prev;
struct listNode *next;
void *value;
} listNode;
链表迭代器 listIter, 其中 next 指针指向下一次访问的链表节点.direction 标识当前迭代器的方向是 AL_START_HEAD(从头到尾遍历) 还是 AL_START_TAIL(从尾到头遍历).
// in adlist.h
typedef struct listIter {
listNode *next;
int direction;
} listIter;
/* Directions for iterators */
#define AL_START_HEAD 0
#define AL_START_TAIL 1
双向链表结构 list. 其中, head 和 tail 指针分别指向链表的首节点和尾节点.len 记录当前链表的长度.函数指针 dup, free 和 match 分别代表业务注册的对泛化类型 value 进行深拷贝,释放和匹配操作的函数.(如果没有注册 dup, 则默认进行浅拷贝. 如果没有注册 free, 则不对 value 进行释放.如果没有注册 match 则直接比较 value 的字面值)
// in adlist.h
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;
创建: listCreate 初始化相关字段为零值.可以通过 listSetDupMethod, listSetFreeMethod, listSetMatchMethod来注册该链表泛化类型 value 的 dup, free 和 match 函数.
/* Create a new list. The created list can be freed with
* listRelease(), but private value of every node need to be freed
* by the user before to call listRelease(), or by setting a free method using
* listSetFreeMethod.
*
* On error, NULL is returned. Otherwise the pointer to the new list. */
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;
}
#define listSetDupMethod(l,m) ((l)->dup = (m))
#define listSetFreeMethod(l,m) ((l)->free = (m))
#define listSetMatchMethod(l,m) ((l)->match = (m))
在链表首插入新节点: listAddNodeHead
/* Add a new node to the list, to head, containing the specified 'value'
* pointer as value.
*
* On error, NULL is returned and no operation is performed (i.e. the
* list remains unaltered).
* On success the 'list' pointer you pass to the function is returned. */
list *listAddNodeHead(list *list, void *value)
{
listNode *node;
if ((node = zmalloc(sizeof(*node))) == NULL)
return NULL;
node->value = value;
listLinkNodeHead(list, node);
return list;
}
/*
* Add a node that has already been allocated to the head of list
*/
void listLinkNodeHead(list* list, listNode *node) {
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◆◆;
}
在链表尾插入新节点: listAddNodeTail
在空链表插入新节点: 逻辑与 listAddNodeHead 实现一致.
/* Add a new node to the list, to tail, containing the specified 'value'
* pointer as value.
*
* On error, NULL is returned and no operation is performed (i.e. the
* list remains unaltered).
* On success the 'list' pointer you pass to the function is returned. */
list *listAddNodeTail(list *list, void *value)
{
listNode *node;
if ((node = zmalloc(sizeof(*node))) == NULL)
return NULL;
node->value = value;
listLinkNodeTail(list, node);
return list;
}
/*
* Add a node that has already been allocated to the tail of list
*/
void listLinkNodeTail(list *list, listNode *node) {
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◆◆;
}
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;
}
/* Remove the specified node from the specified list.
* The node is freed. If free callback is provided the value is freed as well.
*
* This function can't fail. */
void listDelNode(list *list, listNode *node)
{
listUnlinkNode(list, node);
if (list->free) list->free(node->value);
zfree(node);
}
/*
* Remove the specified node from the list without freeing it.
*/
void listUnlinkNode(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;
node->next = NULL;
node->prev = NULL;
list->len--;
}
/* 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->len == 0) return;
o->head->prev = l->tail;
if (l->tail)
l->tail->next = o->head;
else
l->head = o->head;
l->tail = o->tail;
l->len ◆= o->len;
/* Setup other as an empty list. */
o->head = o->tail = NULL;
o->len = 0;
}
其他函数: 其他函数实现较为简单,这里简单罗列一下,感兴趣的可以去看下源码.
// 获取 list 的迭代器
listIter *listGetIterator(list *list, int direction);
// 返回迭代器的下一个元素,并将迭代器移动一位.如果已遍历完成, 则返回 NULL
listNode *listNext(listIter *iter);
// 释放迭代器资源
void listReleaseIterator(listIter *iter);
// 拷贝链表
list *listDup(list *orig);
// 在链表中查找与 key 匹配的 value 所在的第一个节点.
// 如果不存在,则返回 NULL.
// 匹配操作由 list->match 函数提供.
// 如果没有注册 match 函数, 则直接比较 key 是否与 value 相等.
listNode *listSearchKey(list *list, void *key);
// 返回指定的索引的元素. 如果超过了链表范围, 则返回 NULL.
// 正整数表示从首部开始计算.
// 0 表示第一个元素, 1 表示第二个元素, 以此类推.
// 负整数表示从尾部开始计算.
// -1 表示倒数第一个元素, -2 表示倒数第二个元素,以此类推.
listNode *listIndex(list *list, long index);
// 返回链表初始化的正向迭代器
void listRewind(list *list, listIter *li);
// 返回链表初始化的反向迭代器
void listRewindTail(list *list, listIter *li);
// 将链表尾部节点移到首部
void listRotateTailToHead(list *list);
// 将链表首部节点移到尾部
void listRotateHeadToTail(list *list);
// 用 value 初始化节点
void listInitNode(listNode *node, void *value);
git@github.com:younglionwell/redis-adlist-example.git
关注公众号了解更多 redis 源码细节和其他技术内容. 你的关注是我最大的动力.
以上就是土嘎嘎小编为大家整理的Redis 源码解析之通用双向链表_adlist)相关主题介绍,如果您觉得小编更新的文章只要能对粉丝们有用,就是我们最大的鼓励和动力,不要忘记讲本站分享给您身边的朋友哦！！