redis源代码分析1–链表

先简单介绍下redis中用到的链表,是在文件adlist.c和adlist.h中实现的。

实现中主要用到listNode、list、listIter三个结构,listNode代表链表中的每个节点,list指向整个链表,listIter是为了迭代访问整个list,内部其实就是个listNode指针。

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 int len;
} list;


listNode提供的prev、next指针将整个list链接成一个双向链表,保存的值是void *类型,对值的复制、释放、匹配操作是用在list中注册的三个函数指针dup、free、match完成的。

在list结构中,除提供对listNode中的值进行操作的三个函数指针外,还提供了head、tail指针,以指向list的头部和尾部。另外list的len保存了整个list的长度,方便对list是否为空的判断(纯属多余吧)。

listIter是为了遍历list,可以从头部、尾部开始遍历。用法可用如下伪代码表示:

iter=listGetIterotr(list, <direction>);
while ((node=listNext(iter)) !=NULL)
{
	DoSomethingWith(listNodeValue(node));
}

另外注意:在提供的增加、删除节点的api(listAddNodeHead、listAddNodeTail、listDelNode)中,并没有分配、释放节点 内部的value所用内存,需要调用者自己分配或者释放value所占的内存(除了分配和释放节点本身的内存外)。

乍一看没有提供修改某个节点的值的方法,但是由于listSearchKey、listIndex等方法返回了节点指针,故可以直接修改节点的value。

 

此条目发表在 redis 分类目录,贴了 , , 标签。将固定链接加入收藏夹。

redis源代码分析1–链表》有 7 条评论

  1. 测试List 说:

    大哥,你有没有测试这个链表,我进行了一下测试,但是出现了问题。
    我插入数据后,进行递归输出数据的时候,都是同一个数据,且是最后一个插进去的数据。(插入的数据我是随机的,肯定各个不同)
    我使用了 “迭代器和指针移动” 两种方法都不行。而且迭代器的方向也是没有起作用。
    求解。。。。。

  2. anon 说:

    redis是如何实现各种数据结构的原子操作呢 ?

    • peter 说:

      redis的核心是单进程单线程,无须同步与复杂的加锁机制。关于hash表的设计,有点意思,有兴趣可以看看我的blog介绍。

  3. Pingback 引用通告: redis源码分析1-链表 - 向东有岸

petermao 发表评论 取消回复

电子邮件地址不会被公开。 必填项已被标记为 *

*

您可以使用这些 HTML 标签和属性: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>