redis源码学习-adlist篇
0 条评论redis源码学习-adlist篇
adlist介绍
redis中的adlist(A generic doubly linked list implementation)是redis自身实现的双端链表,结构较为简单,无特殊优化,仅作代码说明
adlist分析
adlit数据结构如下
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是adlist的节点,其中的prev指向上一个节点,next指向下一个节点。
listIter是redis自实现的迭代器,其中的next指向了某个具体的list节点,direction指的是某具体迭代的顺序,需要结合宏来看
/* Directions for iterators */
#define AL_START_HEAD 0
#define AL_START_TAIL 1
宏定义的AL_START_HEAD AL_START_TAIL 是listIter中direction字段的值,AL_START_HEAD代表着此次迭代向前,AL_START_TAIL 代表着此次迭代向后。迭代部分源码如下
if (direction == AL_START_HEAD)
iter->next = list->head;
else
iter->next = list->tail;
list为链表的结构了,head为某一链表的头节点,tail为尾节点。之后的三个方法,dup为拷贝,free为释放,match为匹配。len为list自维护的链表长度。
和大家平时所使用的一样,adlist也是实现了增(头插法),删,改,查,复制,拼接。不过redis在新增是使用zmalloc分配堆空间,详情可以看/src/zmalloc.c
部分adlist源码:
初始化:
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;
}
len为0,其余全部为null
释放链表:
/* Free the whole list.
*
* This function can't fail. */
void listRelease(list *list)
{
listEmpty(list);
zfree(list);
}
listempty首先遍历移除所有节点,
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;
}
zfree释放堆空间,详情可以看/src/zmalloc.c
头插法:
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;
}
更多的源码就不放这里了,都是常规操作,头插尾插,next遍历等等,只放实现好的方法名,按需自己看源码即可
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 listRotateTailToHead(list *list);
void listRotateHeadToTail(list *list);
void listJoin(list *l, list *o);
其中不少类似listReleaseIterator的方法,只是释放iter的内存,但是没有看到引用,可能之前的写法,在6之后被废弃掉了
adlist使用场景
adlist在整个redis内部使用较多也广,从history cmd到sub/pub的客户端等等都在使用
至此,redis的adlist部分结束~