Redis源码阅读:Redis里的链表

Redis源码阅读:Redis里的链表

链表的数据结构

链表在Redis中应用广泛,adlis.h/c中定义了相关的数据结构与基本的函数
基本的数据结构定义如下:

typedef struct listNode {
    struct listNode *prev;
    struct listNode *next;
    void *value;
} listNode;

typedef struct listIter {
    listNode *next;
    int direction;
} listIter;

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;

listnode是链表的节点数据结构,可以看出来是一个双向的节点,listIter是指向链表节点的迭代器,熟悉C++和Java的人对迭代器应该不会陌生,这里listIter是一种双向的迭代器,list则是链表本身的数据结构,其中head和tail分别指向首尾节点,dup、free、match分别是可以自定义的拷贝函数、节点析构函数、节点匹配函数,len表示的是链表的长度

相关的Method

Redis由C语言写成,很多方法都是用宏来完成

用宏来实现的方法

#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 *listCreate(void);
void listRelease(list *list);
void listEmpty(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);
void listJoin(list *l, list *o);

熟悉《数据结构与算法 C语言实现》的应该不难理解相关的代码,链表的实现还是很基础的。

Comments are closed.