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部分结束~