3.双向链表遍历器,  对于释放链表的操作

2020-04-25 15:06 来源:未知

list *listInsertNode(list *list, listNode *old_node, void *value, int after)

 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 }
 /** * 将迭代器iter的迭代指针倒回list的表尾 * * T = O(1) */ void listRewindTail(list *list, listIter *li) { li-next = list-tail; li-direction = AL_START_TAIL; } 
 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 }
typedef struct listIter { listNode *next; //下一个节点 int direction;} listIter; 方向定义 #define AL_START_HEAD 0 //向前查找 #define AL_START_TAIL 1 //向后查找
  1. API实现:
 /** * 链表迭代器 */ typedef struct listIter { // 下一节点 listNode *next; // 迭代方向 int direction; } listIter; 
 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 }

void listRelease(list *list)

  1. 通用链表实现

list *listAddNodeHead(list *list, void *value)

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

Redis中双链表实现的基本结构:1.节点结构

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

 /** * 释放列表中给定的节点 * * T = O(1) */ void listDelNode(list *list, listNode *node) { // 处理前驱节点指针 if (node-prev) { node-prev-next = node-next; } else { list-head = node-next; } // 处理后继节点 if (node-next) { node-next-prev = node-prev; } else { list-tail = node-prev; } // 释放节点值 if (list-free) list-free(node-value); // 释放节点 free(node); // 更新列表节点数目 list-len --; } 

 

list结构和listNode结构的APIlist和listNode都有它们自己的一族API,这里贴出来学习一下redis的源码(ps:下面的代码都是我仿照redis改写能直接编译运行的代码)

 

list *listAddNodeTail(list *list, void *value)

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

 /** * 创建一个包含值value的节点 * 并根据after参数的指示,将新节点插入到old_node的之前或者之后 * * T = O(1) */ list *listInsertNode(list *list, listNode *old_node, void *value, int after) { listNode *node; node = (listNode *)malloc(sizeof(listNode)); if (node == NULL) return NULL; if (after) { // 插入到old_node之后 node-prev = old_node; node-next = old_node-next; // 处理表尾节点 if (list-tail == old_node) { list-tail = node; } } else { // 插入到old_node之前 node-next = old_node; node-prev = old_node-prev; // 处理表头节点 if (list-head == old_node) { list-head = node; } } // 更新前置节点和后继节点的指针(这个地方很经典,节约代码) if (node-prev != NULL) { node-prev-next = node; } if (node-next != NULL) { node-next-prev = node; } // 更新列表节点 list-len ++; return list; } 
1 void free(void * value)2 {3   if( value )4     free( (char *)value );5 }
#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)

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

 /** * 释放整个列表 * * T = O(N), N为列表长度 */ void listRelease(list *list) { unsigned long len; listNode *current, *next; current = list-head; len = list-len; while (len --) { next = current-next; // 如果列表有自带的free方法,那么先对节点值调用它 if (list-free) list-free(current-value); // 之后释放节点 free(current); current = next; } free(list); } 

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

 /** * 将迭代器iter的迭代指针倒回list的表头 * * T = O(1) */ void listRewind(list *list, listIter *li) { li-next = list-head; li-direction = AL_START_HEAD; } 

对于free可以实现为:

4.宏定义函数

 

 /** * 新建一个包含给定value的节点,并把它加入到列表的表尾 * * T = O(1) */ list *listAddNodeTail(list *list, void *value) { listNode *node; node = (listNode *)malloc(sizeof(listNode)); if (node == NULL) return NULL; if (list-len == 0) { // 第一个节点 list-head = list-tail = node; node-prev = node-next = NULL; } else { // 不是第一节点 node-prev = list-tail; node-next = NULL; list-tail-next = node; list-tail = node; } list-len ++; return list; } 

c. listSearchKey

typedef struct listNode { struct listNode *prev; //前向节点 struct listNode *next; //后向节点 void *value; //该节点的值} listNode;
  1. 前言

5.定义函数

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

listIter *listGetIterator(list *list, int direction)

  1. 总结
TAG标签:
版权声明:本文由www.129028.com-澳门金沙唯一官网www129028com发布于编程新闻,转载请注明出处:3.双向链表遍历器,  对于释放链表的操作