揭秘Redis列表底层实现

Redis的列表数据结构是使用双向链表实现的，这使得在列表的两端进行插入和删除操作都可以在常数时间内完成。

在Redis内部，列表的每个节点使用一个listNode结构表示：

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

而整个列表由一个list结构体来维护：

typedef struct list {
    listNode *head;
    listNode *tail;
    void (*free)(void *ptr);
    unsigned long len;
} list;

其中：

• head 指向列表的头节点。
• tail 指向列表的尾节点。
• free 是一个函数指针，用于释放列表节点的值所占用的内存。
• len 记录了列表的长度。

以下是一个简单的Redis列表结构的实现示例：

#include <stdio.h>
#include <stdlib.h>
 
typedef struct listNode {
    struct listNode *prev;
    struct listNode *next;
    void *value;
} listNode;
 
typedef struct list {
    listNode *head;
    listNode *tail;
    void (*free)(void *ptr);
    unsigned long len;
} list;
 
list *listCreate() {
    list *l = malloc(sizeof(list));
    l->head = NULL;
    l->tail = NULL;
    l->len = 0;
    l->free = NULL;
    return l;
}
 
listNode *listNodeCreate(void *value) {
    listNode *node = malloc(sizeof(listNode));
    node->prev = NULL;
    node->next = NULL;
    node->value = value;
    return node;
}
 
int listAddNodeHead(list *l, void *value) {
    listNode *node = listNodeCreate(value);
    if (l->len == 0) {
        l->head = node;
        l->tail = node;
    } else {
        node->next = l->head;
        l->head->prev = node;
        l->head = node;
    }
    l->len++;
    return 1;
}
 
int listAddNodeTail(list *l, void *value) {
    listNode *node = listNodeCreate(value);
    if (l->len == 0) {
        l->head = node;
        l->tail = node;
    } else {
        node->prev = l->tail;
        l->tail->next = node;
        l->tail = node;
    }
    l->len++;
    return 1;
}
 
void listFree(list *l) {
    listNode *current = l->head;
    listNode *next = NULL;
    while(current != NULL) {
        next = current->next;
        if (l->free) l->free(current->value);
        free(current);
        current = next;
    }
    free(l);
}
 
int main() {
    list *myList = listCreate();
    listAddNodeHead(myList, "Hello");
    listAddNodeTail(myList, "World");
    // 现在myList包含两个节点，分别保存"Hello"和"World"
 
    // 清理资源
    listFree(myList);
    return 0;
}

这个示例展示了如何创建一个列表，如何添加节点到列表的头部和尾部，以及如何释放整个列表所占用的内存。这里的代码仅为示例，并未包含完整的错误检查和处理。