Community Learn Tools Library Leisure
search
English
Home > Database > Mysql Tutorial > body text

【Redis】对通用双向链表实现的理解

WBOY
Release： 2016-06-07 15:54:10
Original
960 people have browsed it

Redis实现的双向链表还是比较容易看得懂的，其实现的原理很经典, 代码很整洁清晰。 以下是对其源码注释的翻译及本人见解的部分说明，如有偏颇欢迎指正: /* adlist.h - 通用双向链表的实现*/#ifndef __ADLIST_H__#define __ADLIST_H__/* 目前的数据结构只使用

Redis实现的双向链表还是比较容易看得懂的，其实现的原理很经典, 代码很整洁清晰。

以下是对其源码注释的翻译及本人见解的部分说明，如有偏颇欢迎指正:

/* adlist.h - 通用双向链表的实现*/

#ifndef __ADLIST_H__
#define __ADLIST_H__

/* 目前的数据结构只使用了Node, List, and Iterator. */

/* list节点*/
typedef struct listNode {
    struct listNode *prev;        // 前向指针
    struct listNode *next;        // 后向指针
    void *value;                  // 当前节点值
} listNode;

/* list迭代器*/
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;

/* 函数宏定义 */
#define listLength(l) ((l)->len)                       // 链表长度
#define listFirst(l) ((l)->head)                       // 链表头节点
#define listLast(l) ((l)->tail)                        // 链表末节点
#define listPrevNode(n) ((n)->prev)                    // 指定节点的前驱节点
#define listNextNode(n) ((n)->next)                    // 指定节点的后继节点
#define listNodeValue(n) ((n)->value)                  // 指定节点的值

/* 函数指针, 设置外部调用模块的自定义的方法 */
#define listSetDupMethod(l,m) ((l)->dup = (m))         // 复制链表
#define listSetFreeMethod(l,m) ((l)->free = (m))       // 释放链表
#define listSetMatchMethod(l,m) ((l)->match = (m))     // 匹配

/* 函数指针, 获取外部调用模块的自定义的方法 */
#define listGetDupMethod(l) ((l)->dup)                      // 获取复制的自定义方法
#define listGetFree(l) ((l)->free)                          // 获取释放的自定义方法
#define listGetMatchMethod(l) ((l)->match)                  // 获取匹配的自定义方法

/* 函数原型 */
list *listCreate(void);                                                               // 创建链表
void listRelease(list *list);                                                         // 释放链表
list *listAddNodeHead(list *list, void *value);                                       // 在表头添加节点
list *listAddNodeTail(list *list, void *value);                                       // 在表尾添加节点
list *listInsertNode(list *list, listNode *old_node, void *value, int after);         // 在指定位置之后添加节点
void listDelNode(list *list, listNode *node);                                         // 删除节点
listIter *listGetIterator(list *list, int direction);                                 // 获取列表迭代器
listNode *listNext(listIter *iter);                                                   // 获取下一个节点
void listReleaseIterator(listIter *iter);                                             // 释放列表迭代器
list *listDup(list *orig);                                                            // 复制链表
listNode *listSearchKey(list *list, void *key);                                       // 给定key查找节点
listNode *listIndex(list *list, long index);                                          // 给定index查找节点
void listRewind(list *list, listIter *li);                                            // 迭代器指针重新指向头节点
void listRewindTail(list *list, listIter *li);                                        // 迭代器指针重新指向末节点
void listRotate(list *list);                                                          // 链表翻转, 末节点移动成为头节点

/* 迭代器的迭代方向 */
#define AL_START_HEAD 0
#define AL_START_TAIL 1

#endif /* __ADLIST_H__ */
Copy after login
/* adlist.c - 通用双向链表的实现 */

#include <stdlib.h>
#include "adlist.h"
#include "zmalloc.h"

/* 创建新链表. 新建的链表可以用函数
* AlFreeList()来释放, 但调用此函数之前需要要应用手动释放对每个节点的私有值空间
*
* 出现错误则返回NULL，否则返回指向该list的指针*/
list *listCreate(void)
{
    struct list *list;

    if ((list = zmalloc(sizeof(*list))) == NULL)       // 用了在malloc之上封装的zmalloc来申请内存
        return NULL;
    list->head = list->tail = NULL;
    list->len = 0;
    list->dup = NULL;
    list->free = NULL;
    list->match = NULL;
    return list;
}

/* 释放链表，该方法不能失败.
*
 */
void listRelease(list *list)
{
    unsigned long len;
    listNode *current, *next;

    current = list->head;
    len = list->len;
    while(len--) {
        next = current->next;
        if (list->free) list->free(current->value);   // 每个节点指向的空间都会被释放
        zfree(current);       // zfree基于系统函数free上的封装                                
        current = next;
    }
    zfree(list);
}

/* 把包含指针指向的值的节点插入链表头部
*
* 如发生错误,将返回NULL并且不对链表进行任何操作,
*
* 如成功则返回该链表指针.*/
list *listAddNodeHead(list *list, void *value)
{
    listNode *node;
    if ((node = zmalloc(sizeof(*node))) == NULL)
        return NULL;
    node->value = value;
    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;
}

/* 把包含指针指向的值的节点插入链表尾部，

* 如发生错误,将返回NULL并且不对链表进行任何操作,
*
* 如成功则返回该链表指针.*/
list *listAddNodeTail(list *list, void *value)
{
    listNode *node;
    if ((node = zmalloc(sizeof(*node))) == NULL)
        return NULL;
    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;
    }
    list->len++;
    return list;
}

/* 把新节点插入链表某个节点的前或后，
* 如发生错误,将返回NULL并且不对链表进行任何操作,
*
* 如成功则返回该链表指针.*/
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) {                          // after!=0则表示节点插入的位置在旧节点之后，否则在其之前
        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;
}

/* 从链表中删除某个节点.
* 会调用底层函数把节点的空间释放.
*
* 该方法不能失败. */
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--;
}

/* 获取迭代器对象&#39;iter&#39;. 在初始化之后
*每次调用listNext()都会返回链表的下一个元素.
*
* 该方法不能失败. */
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;
}

/* 释放迭代器对象的空间 */
void listReleaseIterator(listIter *iter) {
    zfree(iter);
}

/* 将迭代器指针重新指向表头 */
void listRewind(list *list, listIter *li) {
    li->next = list->head;
    li->direction = AL_START_HEAD;
}

/* 将迭代器指针重新指向表尾 */

void listRewindTail(list *list, listIter *li){
    li->next = list->tail;
    li->direction = AL_START_TAIL;
}

/* 获取迭代器的下一个元素.
* 可以通过listDelNode()方法来删除当前返回的节点,但不能删除其他的节点。
*
* 如果成功则返回迭代器的下一个元素,否则返回NULL;
* 因此推荐以下这样使用:
*
* iter = listGetIterator(list,<direction>);
* while ((node = listNext(iter)) != NULL) {
* doSomethingWith(listNodeValue(node));
* }
*
* */
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;
}

/* 复制整个链表. 
* 成功则返回复制的链表指针，否则返回NULL.
*
* 复制的方法通过listSetDupMethod()来指定，
* 如果没有指定dup方法则会完整拷贝原始节点的值.
*
* 原始链表不会给更改. */
list *listDup(list *orig)       // 有个疑问: 既然需要保持原始链表的不被修改，为什么不加const修饰?
{
    list *copy;
    listIter *iter;
    listNode *node;

    if ((copy = listCreate()) == NULL)
        return NULL;
    copy->dup = orig->dup;
    copy->free = orig->free;
    copy->match = orig->match;
    iter = listGetIterator(orig, AL_START_HEAD);
    while((node = listNext(iter)) != NULL) {
        void *value;

        if (copy->dup) {
            value = copy->dup(node->value);
            if (value == NULL) {
                listRelease(copy);
                listReleaseIterator(iter);
                return NULL;
            }
        } else
            value = node->value;
        if (listAddNodeTail(copy, value) == NULL) {
            listRelease(copy);
            listReleaseIterator(iter);
            return NULL;
        }
    }

    listReleaseIterator(iter);

    return copy;
}

/* 通过指定key来查找节点.
* 查找节点的匹配方法可以通过listSetMatchMethod()来指定. 
* 如果外部调用模块没有指定匹配方法, 则直接比较key值和链表中节点指针指向的值.
*
* 如果正常将返回第一个匹配的节点指针，如果找不到匹配元素则返回NULL. */
listNode *listSearchKey(list *list, void *key)
{
    listIter *iter;
    listNode *node;

    iter = listGetIterator(list, AL_START_HEAD);
    while((node = listNext(iter)) != NULL) {
        if (list->match) {                                       // 使用自定义的match方法
            if (list->match(node->value, key)) {
                listReleaseIterator(iter);
                return node;
            }
        } else {                                                     // 直接比较值
            if (key == node->value) {
                listReleaseIterator(iter);
                return node;
            }
        }
    }
    listReleaseIterator(iter);   // 释放iter对象
    return NULL;
}

/* 根据index来获取元素。
* 如果传入index为非负值，说明为正向迭代： 0为头节点,1为下一个节点，以此类推.
* 如果为负值，则说明为反向迭代: -1为尾节点, -2为倒数第二个节点, 以此类推
* 如果index越界则返回NULL. */
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;
}

/* 翻转链表, 将尾节点插入到链表头. */
void listRotate(list *list) {
    listNode *tail = list->tail;

    if (listLength(list) <= 1) return;

    /* 将当前末节点从链表中摘除 */
    list->tail = tail->prev;
    list->tail->next = NULL;
    /* 将末节点插入链表头 */
    list->head->prev = tail;
    tail->prev = NULL;
    tail->next = list->head;
    list->head = tail;
}
Copy after login
有两点还需要继续了解:

1)既然源码中list空间的创建及销毁是通过zmalloc模块的zmalloc和zfree来完成, zmalloc又是怎么实现的呢?

2)很好奇这么多对象指针都没有const作为限制, 是什么原因可以省略了它呢?

Related labels：
redis accomplish understand Universal linked list
source：php.cn
Previous article：【fk_index】外键中有无索引的区别 Next article：OCM_Session3_3_FlashbackDatabase
Statement of this Website
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn
Latest Articles by Author
Latest Issues
Symfony Redis cannot connect to the host defined in the env file, which defaults to localhost We have a new Symfony setup with Redis as the caching mechanism. We want to connect to a s...
From 2024-04-06 10:53:02
0
1
375
Related Topics
More>
Popular Recommendations
Popular Tutorials
More>
Related Tutorials
Popular Recommendations
Latest courses
Latest Downloads
More>
Web Effects
Website Source Code
Website Materials
Front End Template