欢迎关注我的公众号 [极智视界]，获取我的更多笔记分享

  O_o   >_<   o_O   O_o   ~_~   o_O

  本文介绍一下 darknet 中链表的实现。

  链表是 C 语言中一种基本数据结构，逻辑上一个个挨着的数据，实际存储却不是一个个挨着的，而是节点数据随机的分布在内存中的各个位置。由于数据是分散存储的，所以在每个节点都需要有个指针指向紧挨着的后面的节点，这样衔接起来串成一条链，最后一个节点的指针指向 NULL，示意图就像这样：

  darknet 是个纯 C 的推理框架，里面有很多地方用到了链表的数据结构，这里从 darknet 框架中的链表操作展开，包括链表实现、查找、插入等基于链表的方法，其中关于链表的声明和实现主要在 lish.h 和 list.c 中，下面进行介绍分析。

1、list.h

  直接在代码中注释了：

#ifndef LIST_H#define LIST_H/// 定义节点结构体typedef struct node{    void *val;                       // 存放当前节点的值，空指针    struct node *next;               // 下一节点    struct node *prev;               // 上一节点} node;/// 定义链表结构体typedef struct list{    int size;                        // 链表长度     node *front;                     // 该链表的第一个节点    node *back;                      // 该链表的最后一个节点} list;#ifdef __cplusplusextern "C" {#endif/// 声明链表方法list *make_list();                   // 初始化链表int list_find(list *l, void *val);   // 查找链表void list_insert(list *, void *);    // 插入链表void **list_to_array(list *l);       // 链表转数组    /// 释放空间void free_list_val(list *l);void free_list(list *l);void free_list_contents(list *l);void free_list_contents_kvp(list *l);#ifdef __cplusplus}#endif#endif

2、list.c

  list.c 是 list.h 对应的实现部分。要说 list.c 首先需要说一下 xmalloc 和 xcalloc，这两个函数会在 list.c 中用到。

  其实 xmalloc 就是把 malloc 包了一层，看下 xmalloc 的实现：

/// utils.h#define xmalloc(s) xmalloc_location(s, DARKNET_LOC)

  这个宏会把 xmalloc 用 xmalloc_location 替换，xmalloc_location 的实现如下。可以看到里面最关键的就是一个 malloc 的方法，我们知道 malloc 的作用是在内存的动态存储中分配一块长度为 size 大小的连续存储空间，所以 xmalloc_location 的作用同样如此。

void *xmalloc_location(const size_t size, const char * const filename, const char * const funcname, const int line) {    void *ptr=malloc(size);    if(!ptr) {        malloc_error(size, filename, funcname, line);    }    return ptr;}

  同样来看一下 xcalloc：

/// utils.h#define xcalloc(m, s) xcalloc_location(m, s, DARKNET_LOC)

  这个宏会把 xcalloc 用 xmalloc_location 替换，xcalloc_location 的实现如下。可以看到里面最关键的就是一个 calloc 的方法，我们知道 calloc 的作用是动态申请 nmemb 个 size 大小的内存空间，并把分配的内存空间全部初始化为零，返回该区域的首地址。

void *xcalloc_location(const size_t nmemb, const size_t size, const char * const filename, const char * const funcname, const int line) {    void *ptr=calloc(nmemb, size);    if(!ptr) {        calloc_error(nmemb *size, filename, funcname, line);    }    return ptr;}

  上面说到了 malloc 和 calloc，两者有一些相似之处，都是用于动态申请内存，但也有明显区别：malloc 不初始化分配的内存，calloc 初始化已分配的内存空间为零。既然都说到 malloc 和 calloc 了，就顺便说一下 realloc，realloc 是将指针 p 所指向的已分配的内存空间大小修改为 size 大小，如下：

(void *)realloc(void *p,unsigned size)

  darknet 中也有关于 realloc 的封装：

void *xrealloc_location(void *ptr, const size_t size, const char * const filename, const char * const funcname, const int line) {    ptr=realloc(ptr,size);    if(!ptr) {        realloc_error(size, filename, funcname, line);    }    return ptr;}

  好了，说完了 malloc、calloc、realloc 后，就可以开始说 lish.c 了，还是直接注释了：

#include <stdlib.h>#include <string.h>#include "list.h"#include "utils.h"#include "option_list.h"/// 初始化列表list *make_list(){    list* l = (list*)xmalloc(sizeof(list));           // 开辟链表所需空间    l->size = 0;                                      // 初始化链表长度    l->front = 0;                                     // 初始化链表头指针    l->back = 0;                                      // 初始化链表尾指针    return l;}/*void transfer_node(list *s, list *d, node *n){    node *prev, *next;    prev = n->prev;    next = n->next;    if(prev) prev->next = next;    if(next) next->prev = prev;    --s->size;    if(s->front == n) s->front = next;    if(s->back == n) s->back = prev;}*//// 删除链表尾节点void *list_pop(list *l){    if(!l->back) return 0;                           // 判断该链表是否为空    node *b = l->back;                               // 令 b 指向尾节点    void *val = b->val;                              // 获取尾节点的值    l->back = b->prev;                               // 将链接尾节点指向链表倒数第二节点    if(l->back) l->back->next = 0;                   // 将尾节点的下一节点置为NULL，即删除原链表尾节点    free(b);                                         // 释放节点b    --l->size;                                       // 链表长度减1    return val;                                      // 返回被删除的尾节点的值}/// 链表中插入，按顺序插入在尾void list_insert(list *l, void *val){    node* newnode = (node*)xmalloc(sizeof(node));    // 创建一个节点newnode    newnode->val = val;                              // 给newnode赋值    newnode->next = 0;                               // newnode为尾节点，它的下一个节点为NULL    if(!l->back){                                    // 若链表为空        l->front = newnode;                          // 则将链表的头节点置为newnode        newnode->prev = 0;                           // 则该节点的上一节点为NULL    }else{                                           // 若链表不为空        l->back->next = newnode;                     // 则链表尾节点的下一个节点即为插入节点        newnode->prev = l->back;                     // newnode的上一节点为原链表尾节点    }    l->back = newnode;                               // 新链表的尾节点为新插入的节点    ++l->size;                                       // 链表长度加1}/// 释放节点存储空间// 从传入节点n开始，后面的节点依次释放void free_node(node *n){    node *next;    while(n) {        next = n->next;                              // 偏移至下一节点        free(n);                                     // 释放当前节点        n = next;                                    // 循环更新    }}/// 释放链表值存储空间// 从链表头节点开始，依次释放void free_list_val(list *l){    node *n = l->front;                              // 指向链表头节点    node *next;    while (n) {        next = n->next;                              // 偏移至下一节点        free(n->val);                                // 释放当前节点值存储空间        n = next;                                    // 循环更新    }}/// 释放整个链表存储空间void free_list(list *l){    free_node(l->front);                             // 调用free_node，从头节点开始释放指针域    free(l);                                         // 释放链表空间}/// 和free_list_val功能类似void free_list_contents(list *l){    node *n = l->front;    while(n){        free(n->val);        n = n->next;    }}/// 释放链表存储空间// 先来看一下结构体kvp，定义在option_list.h头文件中/*typedef struct{    char *key;    char *val;    int used;} kvp;*/void free_list_contents_kvp(list *l){    node *n = l->front;                                  // 指向链表头节点    while (n) {        kvp* p = (kvp*)n->val;                           // 此时节点值域为指向kvp结构体的指针        free(p->key);                                    // 释放kvp内层存储        free(n->val);                                    // 释放指向kvp指针外层存储        n = n->next;                                     // 循环更新    }}/// 链表中所有节点的值存数组void **list_to_array(list *l){    void** a = (void**)xcalloc(l->size, sizeof(void*));   // xcalloc l->size 个void*大小的空间    int count = 0;    node *n = l->front;                                   // 指向链表头节点    while(n){        a[count++] = n->val;                              // 赋值        n = n->next;                                      // 循环更新    }    return a;}

  以上剖析分享了 darknet 中关于 C 链表的一些操作方法，也可以帮助温固 C 语言基础知识。

【公众号传送】

《【编程艺术】剖析 darknet C 链表实现》