redis当中的list的话是一个双向链表,其结构如下所示
-
typedef struct listNode {
-
struct listNode *prev;
-
struct listNode *next;
-
void *value;
-
} listNode;
-
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;
除了以上两个结构,还定义了一个类似stl当中的迭代器,用于遍历当前链表,并定义了迭代器的方向
-
typedef struct listIter {
-
listNode *next;
-
int direction;
-
} listIter;
-
-
/* Directions for iterators */
-
#define AL_START_HEAD 0
-
#define AL_START_TAIL 1
然后它定义了一堆当做函数来用的宏定义。。。
-
/* Functions implemented as macros */
-
#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 *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;
-
}
-
-
/* Remove all the elements from the list without destroying the list itself. */
-
void listEmpty(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;
-
}
-
list->head = list->tail = NULL;
-
list->len = 0;
-
}
-
-
/* Free the whole list.
-
*
-
* This function can't fail. */
-
void listRelease(list *list)
-
{
-
listEmpty(list);
-
zfree(list);
-
}
分别从头尾两端插入节点
-
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;
-
}
-
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 *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;
-
}
删除节点
-
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--;
-
}
关于迭代器的一些基础操作
-
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;
-
}
-
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;
-
}
list的复制查找
-
list *listDup(list *orig)
-
{
-
list *copy;
-
listIter iter;
-
listNode *node;
-
-
if ((copy = listCreate()) == NULL)
-
return NULL;
-
copy->dup = orig->dup;
-
copy->free = orig->free;
-
copy->match = orig->match;
-
listRewind(orig, &iter);
-
while((node = listNext(&iter)) != NULL) {
-
void *value;
-
-
if (copy->dup) {
-
value = copy->dup(node->value);
-
if (value == NULL) {
-
listRelease(copy);
-
return NULL;
-
}
-
} else
-
value = node->value;
-
if (listAddNodeTail(copy, value) == NULL) {
-
listRelease(copy);
-
return NULL;
-
}
-
}
-
return copy;
-
}
-
listNode *listSearchKey(list *list, void *key)
-
{
-
listIter iter;
-
listNode *node;
-
-
listRewind(list, &iter);
-
while((node = listNext(&iter)) != NULL) {
-
if (list->match) {
-
if (list->match(node->value, key)) {
-
return node;
-
}
-
} else {
-
if (key == node->value) {
-
return node;
-
}
-
}
-
}
-
return NULL;
-
}
-
listNode *listIndex(list *list, long index) {
-
listNode *n;
-
-
if (index < 0) {
-
index = (-index)-1;
-
n = list->tail;
-
while(index-- && n) n = n->prev;
-
} else {
-
n = list->head;
-
while(index-- && n) n = n->next;
-
}
-
return n;
-
}
将最后一个元素插入到列表头
-
/* Rotate the list removing the tail node and inserting it to the head. */
-
void listRotate(list *list) {
-
listNode *tail = list->tail;
-
-
if (listLength(list) <= 1) return;
-
-
/* Detach current tail */
-
list->tail = tail->prev;
-
list->tail->next = NULL;
-
/* Move it as head */
-
list->head->prev = tail;
-
tail->prev = NULL;
-
tail->next = list->head;
-
list->head = tail;
-
}
合并两个列表
-
/* 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->head)
-
o->head->prev = l->tail;
-
-
if (l->tail)
-
l->tail->next = o->head;
-
else
-
l->head = o->head;
-
-
if (o->tail) l->tail = o->tail;
-
l->len += o->len;
-
-
/* Setup other as an empty list. */
-
o->head = o->tail = NULL;
-
o->len = 0;
-
}
总体来开,redis当中的adlist还是跟我们平素里用到的list差不多的,虽然作者有点造轮子之嫌,但是于读者而言,多读一读源代码还是好处多多的,毕竟“源码之前,了无秘密”,与诸位共勉~~~
阅读(4876) | 评论(0) | 转发(0) |