转载

Redis学习——链表实现

0. 前言

Redis 中的链表是以通用链表的形式实现的，而对于链表的用途来说，主要的功能就是增删改查，所以对于查找来说，redis其提供了一个match函数指针，用户负责实现其具体的匹配操作，从而实现通用化。

涉及的文件：adlist.h/adlist.c

1. 数据结构

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);  //用于复制ptr值，实现深度复制  void (*free)(void *ptr);     //释放对应类型结构的内存  int (*match)(void *ptr, void *key); //自定义匹配key  unsigned long len;      //节点数量 } list;

#define listSetDupMethod(l,m) ((l)->dup = (m)) #define listSetFreeMethod(l,m) ((l)->free = (m)) #define listSetMatchMethod(l,m) ((l)->match = (m))

其中提供了dup,free,match的函数指针，用户可以通过设置该函数指针，来存取特定类型的数据。

2. API实现：

只提取几个主要的API，该文件完整的注释在 GitHud 上(用户名：jabnih)

a. listRelease

对于释放链表的操作，其中对于每个节点的释放会判断用户是否设置了free函数，若有则执行用户的操作，用以释放特定类型数据。例如：value为指向一个从堆分配的字符数组，在释放该节点的时候，就需要先释放value内存

对于free可以实现为：

1 void free(void * value) 2 { 3     if( value ) 4         free( (char *)value ); 5 }

 1  //释放链表  2 void listRelease(list *list)  3 {  4     unsigned long len;  5     listNode *current, *next;  6   7     current = list->head;  8     len = list->len;  9     while(len--) { 10         next = current->next; 11         //若设置了free函数，则调用该自定义free函数 12         if (list->free) list->free(current->value); 13          14         zfree(current); 15         current = next; 16     } 17     zfree(list); 18 }

b. listDup

当执行复制的时候，对于设置了dup函数可以实现深度复制或自定义复制的功能。

 1 //复制链表，若有链表有dup,则调用该函数进行深度复制，否则直接复制节点的值(浅复制)  2 list *listDup(list *orig)  3 {  4     list *copy;  5     listIter *iter;  6     listNode *node;  7   8     if ((copy = listCreate()) == NULL)  9         return NULL; 10     copy->dup = orig->dup; 11     copy->free = orig->free; 12     copy->match = orig->match; 13     iter = listGetIterator(orig, AL_START_HEAD); 14     while((node = listNext(iter)) != NULL) { 15         //遍历整个链表 16         void *value; 17  18         if (copy->dup) { 19             //深度复制 20             value = copy->dup(node->value); 21             if (value == NULL) { 22                 //复制出错 23                 listRelease(copy); 24                 listReleaseIterator(iter); 25                 return NULL; 26             } 27         } else 28             //浅复制 29             value = node->value; 30  31         //将复制后的节点添加的copy链表尾部 32         if (listAddNodeTail(copy, value) == NULL) { 33             listRelease(copy); 34             listReleaseIterator(iter); 35             return NULL; 36         } 37     } 38     listReleaseIterator(iter); 39     return copy; 40 }

c. listSearchKey

 1  //查找节点,如果设置了match方法，则使用match方法比较，否则仅仅比较节点的value值  2 listNode *listSearchKey(list *list, void *key)  3 {  4     listIter *iter;  5     listNode *node;  6   7     iter = listGetIterator(list, AL_START_HEAD);  8     while((node = listNext(iter)) != NULL) {  9         if (list->match) { 10             if (list->match(node->value, key)) { 11                 //这里可以将下面两条语句改为break(下同)，最后return NULL改为 return node 12                 listReleaseIterator(iter); 13                 return node; 14             } 15         } else { 16             if (key == node->value) { 17                 listReleaseIterator(iter); 18                 return node; 19             } 20         } 21     } 22     listReleaseIterator(iter); 23     return NULL; 24 }