Implementierung einer doppelendigen verknüpften Liste in Redis

adlist wird als doppelendige verknüpfte Liste in Redis an vielen Stellen in Redis häufig verwendet, z. B. zum Speichern von Slowlog, als Fehlerberichtsclient bei der Master-Slave-Replikation usw Die Implementierung von Listendatenstrukturen usw. hängt damit zusammen, daher handelt es sich auch um eine sehr wichtige Datenstruktur.

1), die Datenstruktur einer doppelendigen verknüpften Liste in Redis

(empfohlen: Redis-Video-Tutorial)

doppelend verknüpfte Liste (Der folgende Code ist in src/adlist.h definiert):

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;

Knoten einer doppelendigen verknüpften Liste (der folgende Code ist in src/adlist.h definiert):

typedef struct listNode {
    struct listNode *prev;   //当前节点的上一个节点
    struct listNode *next;   //当前节点的下一个节点
    void *value;     //当前节点存储的值，可以任意类型
} listNode;

Liste durch Kopf Die beiden Zeiger und der Schwanz zeigen jeweils auf den Kopf und das Ende der verknüpften Liste, sodass die verknüpfte Liste sowohl in positiver als auch in negativer Reihenfolge durchlaufen werden kann. Der void *-Wert von listNode kann Speichern Sie alle Daten und können Sie sie über dup, free und match anpassen. So gehen Sie mit dem Wert von listNode um.

2. Einfache Bedienung einer doppelendigen verknüpften Liste

Erstellen Sie eine verknüpfte Liste (der folgende Code ist in src/adlist.c definiert):

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

An das Ende der verknüpften Liste anhängen (unten). Der Code ist in src/adlist.c definiert:

list *listAddNodeTail(list *list, void *value)
{
    listNode *node;    //初始化node节点

    //为新的node节点分配内存
    if ((node = zmalloc(sizeof(*node))) == NULL)
        return NULL;
    //为node节点设置值
    node->value = value;
    
    if (list->len == 0) {
        //如果空链表则 将头尾指向 新节点 并后继前驱节点设置为NULL
        list->head = list->tail = node;
        node->prev = node->next = NULL;
    } else {
        //否则将节点的前驱节点设置为原来的尾部节点
        node->prev = list->tail;
        //由于追加到尾部，后继节点为NULL
        node->next = NULL;
        //之前的尾部节点的后继节点设置为新增的节点
        list->tail->next = node;
        //将列表的尾部节点指针指向新增的节点
        list->tail = node;
    }
    //增加链表长度
    list->len++;
    return list;
}

Durchlaufen der verknüpften Liste:

Es gibt zwei häufig verwendete Methoden zum Durchlaufen der verknüpften Liste Die eine besteht darin, die verknüpfte Liste entsprechend der Länge der verknüpften Liste manuell durch eine While-Schleife zu durchlaufen, und die andere darin, sie mithilfe des Iterators zu durchlaufen, der von der doppelendigen verknüpften Liste von Redis bereitgestellt wird.

Manuelle Durchquerung (der folgende Code ist in der Speicherfreigabefunktion in src/adlist.c definiert):

void listRelease(list *list)
{
    unsigned long len;
    //current表示当前遍历的游标指针，next表示下次遍历的游标指针（next作为临时变量用于保存下一个节点）
    listNode *current, *next;
    //将current指向头部节点
    current = list->head;
    //计算长度（其实就是 listLength(list)）
    len = list->len;
    //通过长度递减的方式进行遍历，便利到长度为0的时候，遍历结束
    while(len--) {
        //保存下次循环的节点指针
        next = current->next;
        //释放掉当前节点，如果设置释放节点的回调函数，则执行用户自定义的函数
        if (list->free) list->free(current->value);
        zfree(current);
        //将游标指向下个节点
        current = next;
    }
    zfree(list);
}

Informationen zur Durchquerung im Iteratormodus finden Sie weiter unten.

3) Iterator einer doppelendigen verknüpften Liste

Um die Iterierung der verknüpften Liste zu erleichtern, kapselt Redis den Iterator der verknüpften Liste. Die Iteratorstruktur ist wie folgt (die folgende). Der Code ist in src/adlist .h definiert):

typedef struct listIter {
    listNode *next;    //迭代器指向的下一个节点
    //迭代方向，由于双端链表保存了head和tail的值，所以可以进行两个方向的迭代
    //AL_START_HEAD表示从头向后遍历，AL_START_TAIL表示从尾部向前遍历
    int direction;
} listIter;

Iterator-Verwendungsbeispiele:

//l表示list结构，n表示listNode结构，listNode的值保存的是sds字符串
//创建迭代器对象
iter = listGetIterator(l, AL_START_HEAD);
//循环获取下一个需要遍历的节点
while ((n = listNext(iter))) {
    //输出返回的节点n的value值
    printf("Node Value: %s\n", listNodeValue(n));
}

Weitere Redis-Kenntnisse finden Sie in der Spalte Redis-Einführungs-Tutorial.

Das obige ist der detaillierte Inhalt vonImplementierung einer doppelendigen verknüpften Liste in Redis. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!