Redis实现 – 链表
一、链表的特点
链表作为一种常用的数据结构,链表内置在许多的高级语言中,比如Java中:LinkedList
等集合类工具。
链表是一种线性表,和数组不同的是,他不能随机访问结点,只能顺序的访问。同时它可以通过增删结点来灵活地调整链表的长度。
链表结构
二、Redis中的链表
C语言中没有设计这种数据结构,因此Redis构建了自己的链表实现。
1、链表的实现
源代码在adlist.h
中
1 2 3 4 5 6 7 8 9
| typedef struct listNode { struct listNode *prev; struct listNode *next; void *value; } listNode;
C
|
可以看到,这是一个双向链表。
image-20210705134653786
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
| 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;
C
|
同时,Redis还设计了一个list
结构,为链表提供了表头指针head
,表尾指针tail
,链表长度len
,还提供了一些特定的函数。
dup
:用于复制链表结点所保存的值
free
:用于释放链表结点所保存的值
match
:用于对比链表结点所保存的值和另一个输入值是否相等
链表结构
Redis中定义了一些宏函数,这些函数都是Redis中链表的核心操作。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35
| #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)
C
|
2、Redis中的链表特点
- 双向链表:结点中带有
prev
和next
指针。
- 不是循环链表:表头指针的
prev
指向null
,表尾指针的next
指向null
。
- List结构:list结构中有len,head,tail等属性。
- 多态:链表结点使用
void*
指针来保存节点值,并且可以通过list结构的dup、free、match
三个属性为结点值设置类型特定函数,所以链表可以用于保存各种不同类型的值。
三、Redis中链表源码
1、创建一个新的链表
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
| 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; }
C
|
2、添加结点到表尾
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29
| 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; }
C
|
3、添加结点到表头
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29
| 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; }
C
|
4、释放整个链表
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
| 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); }
C
|
5、删除给定结点
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
| 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--; }
C
|
6、创建一个迭代器
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
|
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; }
C
|
7、返回迭代器当前所指向的节点
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
|
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; }
C
|
8、复制整个链表
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49
|
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;
iter = listGetIterator(orig, AL_START_HEAD); while((node = listNext(iter)) != NULL) { void *value;
if (copy->dup) { value = copy->dup(node->value); if (value == NULL) { listRelease(copy); listReleaseIterator(iter); return NULL; } } else value = node->value;
if (listAddNodeTail(copy, value) == NULL) { listRelease(copy); listReleaseIterator(iter); return NULL; } }
listReleaseIterator(iter);
return copy; }
C
|