Redis链表实现

wheat

　　链表在 Redis 中的应用非常广泛， 比如列表键的底层实现之一就是链表： 当一个列表键包含了数量比较多的元素， 又或者列表中包含的元素都是比较长的字符串时， Redis 就会使用链表作为列表键的底层实现。除了链表键之外， 发布与订阅、慢查询、监视器等功能也用到了链表， Redis 服务器本身还使用链表来保存多个客户端的状态信息， 以及使用链表来构建客户端输出缓冲区（output buffer）。
　　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);  //dup函数指针
void (*free)(void *ptr);  //free函数指针
int (*match)(void *ptr, void *key);  //match函数指针
unsigned long len;  //表的长度
} list;
　　由上面的数据结构可以知道多个listnode可以组成一个list双向链表，这和数据结构中所学的一样。

　　list结构中的三个函数指针是用来实现c++中的“多态”，由于listnode中的value指针指向的内容不同，导致对应的dup，free，match也会有所不同，这三个函数的作为分别如下：

• dup 函数用于复制链表节点所保存的值；
  
• free 函数用于释放链表节点所保存的值；
  
• match 函数则用于对比链表节点所保存的值和另一个输入值是否相等。
  

　　上面实现的双向链表和我们在数据结构中学习的双向链表本质是一致的，但这个链表更加的通用。listnode保存的内容是没有要求的，它只负责执行内容的地址，至于内容是用什么数据结构保存的并不关心，真正需要关系内容数据机构的是dup，free和match函数，这样就很类似于c++中的“多态”。