• Redis——双端链表

    数据结构

    //每个节点，有一个数据指针，一个指向之前和之后节点的指针
typedef struct listNode {
    struct listNode *prev;
    struct listNode *next;
    void *value;
} listNode;
//迭代器，用来遍历各个节点
typedef struct listIter {
    listNode *next;
    int direction;
} listIter;
//链表的相关信息，头节点、尾节点、长度以及相关的函数指针
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
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21

    相关函数

    创建空链表listCreate

    list *listCreate(void)
{
    struct list *list;
    //申请一个struct list大小的内存
    if ((list = zmalloc(sizeof(*list))) == NULL)
        return NULL;
    //相关成员都设置为NULL
    list->head = list->tail = NULL;
    list->len = 0;
    list->dup = NULL;
    list->free = NULL;
    list->match = NULL;
    return list;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14

    移除链表的所有节点

    void listEmpty(list *list)
{
    unsigned long len;
    listNode *current, *next;

    current = list->head;
    len = list->len;
    //从头节点依次释放
    while(len--) {
        next = current->next;
        //因为每个节点指向的value也是一个指针，因此需要先释放value
        if (list->free) list->free(current->value);
        //再释放当前的节点
        zfree(current);
        current = next;
    }
    list->head = list->tail = NULL;
    list->len = 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19

    释放整个链表listRelease

    除了移除所有节点之外，还把链表的相关成员都释放

    void listRelease(list *list)
{
    listEmpty(list);
    zfree(list);
}

    • 1
    • 2
    • 3
    • 4
    • 5

    头插法插入节点listAddNodeHead

    list *listAddNodeHead(list *list, void *value)
{
    listNode *node;
	//申请节点的内存
    if ((node = zmalloc(sizeof(*node))) == NULL)
        return NULL;
    node->value = value;
    //长度为0的话，头尾都是当前节点并且没有前后节点
    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;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21

    至于尾插法，这里不再赘述

    插入中间节点listInsertNode

    list *listInsertNode(list *list, listNode *old_node, void *value, int after) {
	//after参数是用来判断是插入节点之前还是之后
    listNode *node;

    if ((node = zmalloc(sizeof(*node))) == NULL)
        return NULL;
    node->value = value;
    if (after) {
        node->prev = old_node;
        node->next = old_node->next;
        if (list->tail == old_node) {
            list->tail = node;
        }
    } else {
        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;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29

    删除节点listDelNode

    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;
    if (list->free) list->free(node->value);
    zfree(node);
    list->len--;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14

    迭代器

    获取list的迭代器listGetIterator

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

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13

    让迭代器指向下一个节点listNext

    这个函数比较有意思，返回的是迭代器指向的节点，然而函数内部迭代器指向了下一个节点

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

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12

    list的复制

    所有的内存都是在堆中申请，因此复制起来也必须一个节点一个节点来申请内存

    list *listDup(list *orig)
{
    list *copy;
    listIter iter;
    listNode *node;

    if ((copy = listCreate()) == NULL)
        return NULL;
    //创建空链表后将之前的三个成员函数指针拷贝一下
    copy->dup = orig->dup;
    copy->free = orig->free;
    copy->match = orig->match;
    listRewind(orig, &iter);
    while((node = listNext(&iter)) != NULL) {
        void *value;
		//区分浅拷贝还是深拷贝，node内部的value实际上是一个指针
        if (copy->dup) {
            value = copy->dup(node->value);
            if (value == NULL) {
                listRelease(copy);//一旦复制过程中发生错误就释放已经申请的内存后返回NULL
                return NULL;
            }
        } else {
            value = node->value;
        }
        
        if (listAddNodeTail(copy, value) == NULL) {
            /* Free value if dup succeed but listAddNodeTail failed. */
            if (copy->free) copy->free(value);

            listRelease(copy);
            return NULL;
        }
    }
    return copy;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36

    搜索键

    这里就类似于list的遍历，找到符合要求的键

    listNode *listSearchKey(list *list, void *key)
{
    listIter iter;
    listNode *node;

    listRewind(list, &iter);
    while((node = listNext(&iter)) != NULL) {
        //如果定义了match函数，就调用match函数判断，不然就直接判断value指针的值一不一样
        if (list->match) {
            if (list->match(node->value, key)) {
                return node;
            }
        } else {
            if (key == node->value) {
                return node;
            }
        }
    }
    return NULL;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20

    至此，list的所有成员意义我们都已经知晓：

    1. listNode *head ： list的头节点
    2. listNode *tail ： list的尾节点
    3. void *(*dup)(void *ptr) : 拷贝的函数指针
    4. void (*free)(void *ptr)：value释放的函数指针
    5. int (*match)(void *ptr, void *key)：value是否匹配的函数指针
    6. unsigned long len ： 链表的长度

    获取list索引的节点

    index为0是指的是head，-1时指的是尾部

    listNode *listIndex(list *list, long index) {
    listNode *n;

    if (index < 0) {
        index = (-index)-1;
        n = list->tail;
        while(index-- && n) n = n->prev;
    } else {
        n = list->head;
        while(index-- && n) n = n->next;
    }
    return n;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13

    将list的尾节点移到头部

    void listRotateTailToHead(list *list) {
    if (listLength(list) <= 1) return;

    /* Detach current tail */
    listNode *tail = list->tail;
    list->tail = tail->prev;
    list->tail->next = NULL;
    /* Move it as head */
    list->head->prev = tail;
    tail->prev = NULL;
    tail->next = list->head;
    list->head = tail;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
  • 相关阅读:
    Numpy 笔记——数组创建
    SQL 常见函数整理 _ PATINDEX
    Python3 下载、安装教程，附详细图解
    OpenCV学习笔记(6)_由例程学习高斯图像金字塔和拉普拉斯金字塔
    野火A7学习第三次(组合逻辑相关)
    亚马逊哪些因素会影响转化率，如何才能做得更好（测评）
    notepad++ 如何去除换行
    zabbix agent 6.0安装脚本
    前端动画的另一种方式 json动画
    鸿鹄工程项目管理系统em Spring Cloud+Spring Boot+前后端分离构建工程项目管理系统
  • 原文地址：https://blog.csdn.net/qq_36763031/article/details/125429536