redis-adlist

2021-11-08

redis

简介：

链表作为一种常用的数据结构，链表内置在很多高级的编程语言里面，但C语言没有，所以Redis构建了自己的链表实现。链表在redis中的应用非常广泛，比如列表键包含了比较多元素，或者列表中包含的元素都是比较长的字符串时，redis就会用链表作为列表键的底层实现。Redis中的链表叫adlist（A generic doubly linked list implementation 一个通用的双端链表实现）,和普通单链表相比，它的方向可以向前或者向后，这是由于数据结构中定义了next和prev两个指针决定的，下面看下它的数据结构实现。

数据结构：

节点:

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

多个节点通过prev和next指针组成双端链表

链表：

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;

特性：

1.双端：节点都带有prev和next指针，获取某个节点的前置节点和后置节点的负责度都是O(1)

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;
}

2.无环：表头节点的prev指针和表尾节点指针的next都指向NULL，对链表的访问以NULL为终点

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;
}

3.带表头和表尾指针：获取链表表头表尾复杂度为O(1)

/* 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;
}

4.带链表长度计数器：获取数量的负责度为O(1)

#define AL_START_HEAD 0
#define AL_START_TAIL 1

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

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;
}

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;
}

ohye3166's blog