你的位置:首页 > 数据库

[数据库]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     } else28       //浅复制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 node12         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 }

 

3. 总结

  1. 通用链表实现

  2. 对外提供扩展,用户可以自定义查找,复制,释放的功能。