Двусвязный список Redis знает все

Серия статей по анализу исходного кода Redis

Строковая базовая реализация — динамическая строковая SDS

предисловие

привет, увидимся снова. Не спрашивайте почему, спрашивать — это тяжелая работа. Вот-вот откроется режим серийной съемки. Применение списка связанных списков в Redis очень обширно, но Redis написан на языке C, а нижний уровень использует双向链表Реализация (упомяну здесь, если вы студент мейджора или студент, изучавший структуру данных в колледже, можете забрать). Сегодня мы сосредоточимся на двусвязном списке.

​

Использование API

Давайте сначала воспользуемся API. Если вы использовали его раньше, вы можете сразу перейти к следующему разделу.

Вставьте данные слева от lpush

Используйте команду lpush, чтобы вставить три символа a, b и c в левую часть списка. Обратите внимание на порядок. Результатами запроса будут c, b и a. Ниже будет пояснено, почему сначала копают яму.

​

Вставьте данные с правой стороны rpush

Используйте команду rpush, чтобы вставить в список два символа d и e. Порядок запроса такой же, как мы думали. Последние два символа — d и e.

​

удалить часть данных

Используйте команду lrem, чтобы удалить символ a, тогда что означает средний 1? Это count, что означает удалить количество элементов в списке, равное a. То есть, если count>0, это означает поиск от головы к хвосту и удаление элементов count, равных a. Если count

​

изменить некоторые данные

Используйте команду lset, чтобы изменить элемент с индексом 1 в mylist на dd.Исходный список — c,b,d,e, а модифицированный результат — c,dd,d,e.

​

Конкретная логическая схема

Неважно, если вы этого не понимаете, ниже будет подробно объяснен каждый модуль.

​

Определение двусвязного списка

NodeListNode

Включая указатель головы prev, указатель хвоста next и текущее значение value, как показано на следующем рисунке. Каждый узел имеет два указателя, которые могут не только найти хвост от головы по указателю хвоста, но и найти голову по указателю головы prev от хвоста, Если они соединены, то формируется двусвязный список.

​

Конкретный код выглядит следующим образом:

//定义链表节点的结构体 
typedef struct listNode {
	//前面一个节点的指针 
    struct listNode *prev;
    //后面一个节点的指针 
    struct listNode *next;
    //当前节点的值的指针 ，因为值的类型不确定 
    void *value;
} listNode;

Общая структура

Включая голову указателя головы, хвост указателя хвоста, длину всего связанного списка len и некоторые функции (лично я не думаю, что это важно, если у вас есть друг, который знает, добро пожаловать в комментарий), как показано на следующий рисунок. Головной указатель head указывает на первый узел всего связанного списка, а хвостовой указатель tail указывает на последний узел всего связанного списка.

​

Конкретный код выглядит следующим образом:

//定义链表，对链表节点的再封装 
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;

Реализация двусвязного списка

создать заголовок

Чтобы создать структуру таблицы списка, нам сначала нужно определить, есть ли в настоящее время выделенное пространство для создания, и использовать метод zmalloc для выделения пространства. Если оно не может быть выделено, верните NULL. Если оно может быть выделено, продолжайте. Затем присвойте головному узлу и хвостовому узлу списка значение NULL, len — 0 и присвойте связанной функции значение 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;
} 

пустой стол

Передайте указатель списка, сначала определите текущий узел current, сделайте так, чтобы он указывал на указатель головы, определите len, сделайте его равным длине списка. Затем выполняется цикл, каждый раз, когда len уменьшается на единицу, определяется новый узел next, который всегда указывает на следующий узел текущего узла current.Если есть значение, узел освобождается, текущий узел current равен перемещается назад, и следующий узел также перемещается назад. Пока len не равно 0, все узлы освобождаются и цикл завершается. Голова головного узла и хвост хвостового узла окончательного списка назначений равны NULL, а len равен 0.

注意：这边和SDS一样，清空并不是直接删除list，而是删除其数据，外层的list结构仍然存在。这其实上是惰性删除。

void listEmpty(list *list)
{
    unsigned long len;
    //定义两个节点指针current和next
    listNode *current, *next;
    //当前节点指针current指向list的头节点位置，即list的第一个数据
    current = list->head;
    //len为list的长度
    len = list->len;
    //开始循环，每次len减1
    while(len--) {
        //先让下一个指针指向下一个节点，因为底下直接释放当前节点，如果不在此处复制，底下就获取不到了
        next = current->next;
        //释放当前节点的值
        if (list->free) list->free(current->value);
        //释放当前节点
        zfree(current);
        //当前节点等于刚才的下一个节点next，即开始往后移，开始下一轮循环
        current = next;
    }
    //释放完给头指针head,尾指针tail赋值为NULL
    list->head = list->tail = NULL;
    //len赋值0
    list->len = 0;
}

добавить элемент в заголовок

Добавляем элемент в заголовок таблицы, сначала создаем новый узел node, определяем, есть ли выделение памяти, если да, то продолжаем, если нет, возвращаем NULL, и выходим из метода. Новый узел здесь используется для хранения значения входного параметра, поэтому требуется память. Затем назначьте значение нового узла узла в качестве значения входного параметра. Наконец, вам нужно настроить указатель головы и указатель хвоста списка, а также указатель исходного первого узла (см. рисунок ниже, описание немного запутанное, и картинка понятна с первого взгляда). В конце len списка увеличивается на 1, и список возвращается.

Например, если вы хотите вставить узел f в список, сначала назначьте указатель начала узла пустым (соответствует шагу 1), а затем установите следующий указатель хвоста нового узла так, чтобы он указывал на первый узел (соответствующий шагу 1). к шагу 2) и установите первый prev каждого узла, указывающий на новый узел (соответствующий шагу 3), и, наконец, указатель head списка указывает на новый узел (соответствующий шагу 4). Здесь следует отметить, что шаги 2 и 3 должны быть до шага 4, иначе будет найден первый узел.

​

Конкретный код выглядит следующим образом:

//添加一个元素到表头 
list *listAddNodeHead(list *list, void *value)
{
    listNode *node;

    if ((node = zmalloc(sizeof(*node))) == NULL)
        return NULL;
    node->value = value;//为当前节点赋值 
    //如果当前list为空 
    if (list->len == 0) {
        list->head = list->tail = node;//头尾指针都指向改节点 
        node->prev = node->next = NULL;//当前节点的头尾指针都为null 
    } else {//如果当前list不为空 
        node->prev = NULL;//新节点的头指针为null 
        node->next = list->head;//新节点的尾指针指向原来的尾指针 
        list->head->prev = node;//原来的第一个节点的头指针指向新节点 
        list->head = node;//链表的头指针指向新节点 
    }
    list->len++;//list长度+1 
    return list;
}

добавить элемент в футер

Чтобы добавить элемент в конец списка, сначала создайте новый узел node, чтобы определить, есть ли выделение памяти, если да, продолжайте, если нет, верните NULL и выйдите из метода. Новый узел здесь используется для хранения значения входного параметра, поэтому требуется память. Затем назначьте значение нового узла узла в качестве значения входного параметра. Наконец, необходимо настроить указатель головы и указатель хвоста списка, а также указатель исходного последнего узла (см. рисунок ниже, описание немного запутанное, и картинка понятна с первого взгляда). В конце len списка увеличивается на 1, и список возвращается.

Например, если вы хотите вставить узел f в список, сначала назначьте хвостовой указатель узла пустым (соответствует шагу 1), затем установите головной указатель нового узла так, чтобы он указывал на последний узел (соответствующий шагу 1). шаг 2) и установить следующие точки последнего узла на новый узел (соответствующий шагу 3) и, наконец, указывает конец хвостового указателя списка на новый узел (соответствующий шагу 4).

​

Действуйте следующим образом:

//添加元素到表尾
list *listAddNodeTail(list *list, void *value)
{
    //新建节点node
    listNode *node;
    //尝试分配内存
    if ((node = zmalloc(sizeof(*node))) == NULL)
        return NULL;
    //为新节点node赋值
    node->value = value;
    //调整指针
    if (list->len == 0) {
        list->head = list->tail = node;
        node->prev = node->next = NULL;
    } else {
        node->prev = list->tail;
        node->next = NULL;
        list->tail->next = node;
        list->tail = node;
    }
    //len加1
    list->len++;
    return list;
} 

//在list的某个位置old_node的after(前后)插入value值 
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) {//大于0
        node->prev = old_node;
        node->next = old_node->next;
        if (list->tail == old_node) {
            list->tail = node;
        }
    } else {//小于0
        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;
}

//从链表list中删除某个节点node 
void listDelNode(list *list, listNode *node)
{
	//如果该节点的前面存在节点 
    if (node->prev)
        node->prev->next = node->next;
    else
        list->head = node->next;
    //如果该节点的前面存在节点 
   if (node->next)
        node->next->prev = node->prev;
    else
        list->tail = node->prev;
    //释放当前节点node的值
    if (list->free) list->free(node->value);
    //释放内存 
    zfree(node);
     //len-1 
    list->len--;
}

Суммировать

В этой статье в основном рассказывается о базовой реализации двусвязного списка adlist типа данных списка Redis.Во-первых, он используется из некоторых API-интерфейсов списка, и структура данных двусвязного списка выводится, а затем объединяется с исходный код для описания двусвязного списка, включая указатель головы и хвост узла listNode и список, Наконец, в соответствии с методом вставки элементов в заголовок списка, вставки элементов в конец таблицы, удаления, модифицируя и другие методы, исходный код анализируется, так что он имеет более четкое представление о двусвязном списке.

Если вы считаете, что сочинение в порядке, пожалуйста, поставьте лайк 👍, ваше одобрение является движущей силой для моего письма!

Если вы считаете, что что-то не так, пожалуйста, прокомментируйте.

Хорошо, пока.

просить внимания