darknet源码阅读笔记-02-list.h和lish.c

1. list.h

#ifndef LIST_H
#define LIST_H

// cfg文件每一个[xxx]代表一个片区(section)，通常表示的是一个 层（layer）
// 链表中的每个node，都是一个section.
// 双向链表的节点定义
typedef struct node{
    void *val;  // 存放的是指向实际值的指针。
    struct node *next;   // 指向当前节点的下一节点
    struct node *prev;  //  指向当前节点的上一节点
} node;

// 网络配置双向链表，存储cfg网络配置文件。
// // 双向链表
typedef struct list{
    int size;  // 配置文件的节点数，即section个数，通常就是layer层数
    node *front;  // 头指针，指针链表第一个节点
    node *back;  // 尾指针，指针链表最后一个节点
} list;

#ifdef __cplusplus
extern "C" {   // 会指示编译器这部分代码按C语言（而不是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.lish.c

 

#include <stdlib.h>
#include <string.h>
#include "list.h"
#include "utils.h"
#include "option_list.h"

/// <summary>
/// 创建双向链表
/// </summary>
/// <returns>返回双向链表</returns>
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;
}
*/

/// <summary>
/// 删，双向链表删除尾节点。
/// </summary>
/// <param name="l"></param>
/// <returns></returns>
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;  // 尾节点的next指针置为空.
    free(b);
    --l->size;  // --(l->size)

    return val;
}

/// <summary>
/// 增，尾插法。
/// </summary>
/// <param name="l"></param>
/// <param name="val">可实现泛型接口，即可以是int *val也char *val</param>
void list_insert(list *l, void *val)
{
    node* newnode = (node*)xmalloc(sizeof(node)); // 首先生成新的节点
    newnode->val = val;
    newnode->next = 0;

    if(!l->back){  // 尾节点为空，则为空链表
        l->front = newnode;  // 此时新节点，则为首节点
        newnode->prev = 0;  // 前后指向。首节点的前指针为空。
    }else{
        l->back->next = newnode;  // 尾节点不为空，则使用尾插法。
        newnode->prev = l->back;  // 前后指向。
    }
    l->back = newnode;  // 更新尾节点指针
    ++l->size;
}

/// <summary>
/// 释放当前节点及后面节点空间
/// </summary>
/// <param name="n">节点的指针</param>
void free_node(node *n)
{
    node *next;
    while(n) {
        next = n->next;  // 先备份后面的节点
        free(n);  // 再释放当前的节点空间
        n = next;  // 遍历下一个节点。
    }
}

/// <summary>
/// 释放链表内存放的值。节点内存放的是指向实际值的指针。
/// </summary>
/// <param name="l"></param>
void free_list_val(list *l)
{
    node *n = l->front;  // 遍历节点，指向链表头节点。
    node *next;  // 临时备份节点
    while (n) {
        next = n->next;  // 备份下一个节点
        free(n->val);  // 释放指向实际值的指针。
        n = next;  // 遍历下一个节点。
    }
}

/// <summary>
/// 释放整个链表空间
/// </summary>
/// <param name="l"></param>
void free_list(list *l)
{
    free_node(l->front);  // 释放当前节点及后面节点空间
    free(l);  
}

/// <summary>
/// 释放整个链表的存储值
/// </summary>
/// <param name="l"></param>
void free_list_contents(list *l)
{
    node *n = l->front;
    while(n){
        free(n->val);  // 实际释放的是存放值的指针。
        n = n->next;
    }
}

/// <summary>
/// ?
/// </summary>
/// <param name="l"></param>
void free_list_contents_kvp(list *l)
{
    node *n = l->front;
    while (n) {
        kvp* p = (kvp*)n->val;  // 强转为kvp结构体指针. ?
        free(p->key);  // ?
        free(n->val);
        n = n->next;
    }
}

/// <summary>
/// 链表转数组，即将链表中所有存储的值，用数组保存
/// </summary>
/// <param name="l"></param>
/// <returns>二维指针，因为每个节点里保存的值是 void类型的指针，故指针的指针，即二维指针</returns>
void **list_to_array(list *l)
{
    // 分配存储空间，长度l-size, 每个空间大小为一个void类型指针。a指向的是void类型指针的指针。
    void** a = (void**)xcalloc(l->size, sizeof(void*));
    int count = 0;
    node *n = l->front;  // 遍历指针n指向头节点。
    while(n){
        a[count++] = n->val;  // 
        n = n->next;
    }
    return a;
}