Implémentation d'une liste chaînée double dans Redis

adlist, en tant que liste chaînée à double extrémité dans Redis, est largement utilisée à de nombreux endroits dans Redis, comme le stockage de slowlog, le client de rapport d'erreurs dans la réplication maître-esclave et la mise en œuvre d'une structure de données de liste, etc., beaucoup sont liées à cela, c'est donc aussi une structure de données très importante.

1), la structure de données de la liste chaînée double dans Redis

(recommandé : tutoriel vidéo Redis)

liste chaînée double (le code suivant est défini dans src/adlist.h) :

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;

Nœud de liste chaînée double (le code suivant est défini dans src/adlist.h) :

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

list through head Les deux pointeurs et tail pointent respectivement vers la tête et la queue de la liste chaînée, de sorte que la liste chaînée puisse être parcourue dans les ordres positif et négatif. La valeur void * de listNode peut. enregistre toutes les données et peut être personnalisé via dup, free et match Comment gérer la valeur de listNode.

2. Opération simple de liste chaînée double

Créer une liste chaînée (le code suivant est défini dans src/adlist.c) :

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

Ajouter à la fin de la liste chaînée (ci-dessous Le code est défini dans src/adlist.c) :

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

Parcours de la liste chaînée :

Il existe deux manières couramment utilisées pour parcourir la liste chaînée list, l'une consiste à parcourir manuellement la liste chaînée à travers une boucle while en fonction de la longueur de la liste chaînée, et l'autre est Elle est parcourue à l'aide de l'itérateur fourni par la liste chaînée à double extrémité Redis.

Parcours manuel (le code suivant est défini dans la fonction de libération de mémoire dans src/adlist.c) :

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

Veuillez voir ci-dessous pour le parcours en mode itérateur.

3) Itérateur de liste chaînée double

Afin de faciliter l'itération de la liste chaînée, Redis encapsule l'itérateur de la liste chaînée La structure de l'itérateur est la suivante (la suivante. le code est défini dans src/adlist .h) :

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

Exemples d'utilisation d'itérateur :

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

Pour plus de connaissances sur Redis, veuillez faire attention à la colonne Tutoriel d'introduction à Redis.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!