Skip to content

Latest commit

 

History

History
94 lines (89 loc) · 3.34 KB

list.md

File metadata and controls

94 lines (89 loc) · 3.34 KB
Raw

基于resis源码分支5.0

链表

在adlist.h中，链表节点的定义如下：

typedef struct listNode {
    struct listNode *prev;
    struct listNode *next;
    void *value;
} listNode;

使用多个listNode可以组成双端链表。redis也定义了如下链表数据结构：

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;

其中list结构各个字段含义如下：

  • head：链表的头指针；
  • tail：链表的尾指针；
  • len：链表的长度，即链表中节点的个数；
  • dup：复制链表节点的值；
  • free：释放链表节点的值；
  • match：对比链表节点值和另一个值是否相等；

其中dup、free和match需要显示设置，redis提供了如下的宏定义支持设置list结构元素：

/* Functions implemented as macros */
#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)

redis实现的链表具有如下特点：

  • 双端链表：链表节点有pre和next指针，可以获取当前节点前置和后置节点，时间复杂度O(1)；
  • 无环：list的head节点的prev指针和tail节点的next指针都是null；
  • 链表长度计数器：list结构有len属性，记录链表节点数，所以可以O(1)时间获取链表节点数；
  • 链表头尾指针：list结构有head和tail指针，分别指向链表头节点和尾节点，所以可以O(1)时间获取链表头尾指针；
  • 多态值：链表节点的值value是void*类型，可以保存任意类型数据，并可通过list的dup、free和match属性设置每个节点的特定的函数；

resis也提供了listIter链表迭代器用于遍历链表，结构如下：

typedef struct listIter {
    listNode *next;
    int direction;
} listIter;
  • next：指向链表中下一个节点的指针；
  • direction：迭代器遍历的方向，取值AL_START_HEAD表示从链表头开始，取值AL_START_TAIL表示从链表尾开始；

下面给出使用迭代器listNext实现：

/* Return the next element of an iterator.
 * It's valid to remove the currently returned element using
 * listDelNode(), but not to remove other elements.
 *
 * The function returns a pointer to the next element of the list,
 * or NULL if there are no more elements, so the classical usage patter
 * is:
 *
 * 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;
}