Redis—数据结构之list
Redis的列表对象底层所使⽤的数据结构其中之⼀就是list。
list
Redis的list是⼀个双端链表，其由3部分构成：链表节点、链表迭代器、链表。这⼀设计思想和STL的list是⼀样的，STL的list也是由这三部分组成。需要特别说明的是Redis⽤C语⾔实现了list的迭代器，⽐较巧妙，下⾯就来分析list源码。
list节点
节点的值为void*类型，从⽽可以保存不同类型的值，甚⾄是另⼀种类型的对象。
// 双端链表的节点
typedef struct listNode {
struct listNode *prev; // 指向上⼀个节点
struct listNode *next; // 指向下⼀个节点
void *value; // 指向节点的值, void*类型，使得节点可以保存不同类型的值
} listNode;
list迭代器
c语⾔实现c++中的迭代器；双端链表的迭代器，⽅便了遍历链表的操作；根据direction，可设置为前向/反向迭代器
typedef struct listIter {
listNode *next;    // 指向迭代器⽅向上下⼀个链表结点
int direction; // AL_START_HEAD=0：从头部往尾部⽅向移动；AL_START_TAIL=1：往尾部往头部⽅向移动
} listIter;
其中direction的取值有：
/* Directions for iterators */
// 迭代器⽅向的宏定义
#define AL_START_HEAD 0
#define AL_START_TAIL 1
list
与⼀般设计类似，list中有指向头尾节点的指针，以及链表节点数量的计数。不同的是，由于链表节点为void*类型，被设计为可以存储不同类型的数据，甚⾄是另⼀种类型的对象，所以添加了与节点相关的3个函数，作⽤分别是复制、释放、⽐较节点的值。
// 双端链表
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的操作函数
Redis⽤宏定义实现了⼀些复杂度为O(1)的链表操作，以提⾼list操作的效率。
/* Functions implemented as macros */
// 通过宏来实现⼀些O(1)时间复杂度的函数
#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)
list的源码⽐较好理解，本⼈对其已经做了详细的注释，就不仔细介绍了，下⾯附上源码及注释。list相关的⽂件有两个：adlist.h, adlist.c
#ifndef __ADLIST_H__
#define __ADLIST_H__
/* Node, List, and Iterator are the only data structures used currently. */
// redis的链表为双端链表
// 节点的值为void*类型，从⽽可以保存不同类型的值
// 结合dup,free,match函数实现链表的多态
// 双端链表的节点
typedef struct listNode {
struct listNode *prev; // 指向上⼀个节点
struct listNode *next; // 指向下⼀个节点
void *value; // 指向节点的值, void*类型，使得节点可以保存不同类型的值
} listNode;
// c语⾔实现c++中的迭代器
// 双端链表的迭代器，⽅便了遍历链表的操作
// 根据direction，可设置为前向/反向迭代器
typedef struct listIter {
listNode *next;    // 指向迭代器⽅向上下⼀个链表结点
int direction; // AL_START_HEAD=0：从头部往尾部⽅向移动；AL_START_TAIL=1：往尾部往头部⽅向移动} listIter;
// 双端链表
typedef struct list {
listNode *head; // 指向链表头节点
listNode *tail; // 指向链表尾节点
void *(*dup)(void *ptr); // 复制链表节点所保存的值redis八种数据结构
void (*free)(void *ptr); // 释放链表节点所保存的值
int (*match)(void *ptr, void *key); // 节点值⽐较函数
unsigned long len; // 链表的节点数⽬
} list;
/* Functions implemented as macros */
// 通过宏来实现⼀些O(1)时间复杂度的函数
#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)
/* Prototypes */
// list数据结构相关的函数
// 具体含义见adlist.c
list *listCreate(void);
void listRelease(list *list);
list *listAddNodeHead(list *list, void *value);
list *listAddNodeTail(list *list, void *value);
list *listInsertNode(list *list, listNode *old_node, void *value, int after);
void listDelNode(list *list, listNode *node);
listIter *listGetIterator(list *list, int direction);
listNode *listNext(listIter *iter);
void listReleaseIterator(listIter *iter);
list *listDup(list *orig);
listNode *listSearchKey(list *list, void *key);
listNode *listIndex(list *list, long index);
void listRewind(list *list, listIter *li);
void listRewindTail(list *list, listIter *li);
void listRotate(list *list);
/* Directions for iterators */
// 迭代器⽅向的宏定义
#define AL_START_HEAD 0
#define AL_START_TAIL 1
#endif /* __ADLIST_H__ */
View Code
/
* adlist.c - A generic doubly linked list implementation
*/
#include <stdlib.h>
#include "adlist.h"
#include "zmalloc.h"
/* Create a new list. The created list can be freed with
* AlFreeList(), but private value of every node need to be freed
* by the user before to call AlFreeList().
*
* On error, NULL is returned. Otherwise the pointer to the new list. */ // 创建⼀个链表
// 返回值：list/NULL
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; // 返回为新链表分配的内存的起始地址
}
/* Free the whole list.
*
* This function can't fail. */
// 释放链表及链表节点
void listRelease(list *list)
{
unsigned long len;
listNode *current, *next;
current = list->head;
len = list->len;
while(len--) {
next = current->next;
if (list->free) list->free(current->value); // 释放链表节点的值
zfree(current); // 释放链表节点
current = next;
}
zfree(list); // 释放链表
}
/* 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/NULL
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;
}
/
* 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/NULL
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的节点old_node的前或后插⼊新节点
// after为0，则在old_node之前插⼊；否则，在old_node之后插⼊
// 返回值：list/NULL
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) { // 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;
}
/* Remove the specified node from the specified list.
* It's up to the caller to free the private value of the node.
*
* This function can't fail. */
// 删除链表list中节点node
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--;
}
/* Returns a list iterator 'iter'. After the initialization every
* call to listNext() will return the next element of the list.
*
* This function can't fail. */
// 返回链表的迭代器
// 返回值：list/NULL
listIter *listGetIterator(list *list, int direction)
{
listIter *iter;
if ((iter = zmalloc(sizeof(*iter))) == NULL) return NULL;
if (direction == AL_START_HEAD)
iter->next = list->head; // 设置为前向迭代器
else
iter->next = list->tail; // 设置为反向迭代器
iter->direction = direction;
return iter;
}
/
* Release the iterator memory */
// 释放迭代器的内存
void listReleaseIterator(listIter *iter) {
zfree(iter);
}
/* Create an iterator in the list private iterator structure */
// 回绕迭代器到链表头部
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;
}
/* Return the next element of an iterator.
* It's valid to remove the currently returned element using
* listDelNode(), but not to remove other elements.
*
* The function returns a pointer to the next element of the list,
* or NULL if there are no more elements, so the classical usage patter  * is:
*
* iter = listGetIterator(list,<direction>);
* while ((node = listNext(iter)) != NULL) {
*    doSomethingWith(listNodeValue(node));
* }
*
* */
// 返回迭代器所指向的元素，并将迭代器往其⽅向上移动⼀步
// 返回值：指向当前节点的指针/NULL
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;
}
/* Duplicate the whole list. On out of memory NULL is returned.
* On success a copy of the original list is returned.
*
* The 'Dup' method set with listSetDupMethod() function is used
* to copy the node value. Otherwise the same pointer value of
* the original node is used as value of the copied node.
*
* The original list both on success or error is never modified. */
// 复制输⼊链表
// list*/NULL
list *listDup(list *orig)
{

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。