前言 - 关于 list 思考
list 是最基础的数据结构也是数据结构的基础. 高级 C 代码纽带也是 list.
扯一点, 当你走进了 C 的殿堂, 那么你和 list 增删改查那就是一辈子丫 ~
这里不妨分享一下作者对于 list 认知经历的几个阶段 (比心)
i) 原生链表
struct list { struct list * next; ... }
链表结构和业务数据绑定在一起. 朴实无华丽, 重剑可破军
ii) 万能链表
struct list { struct list * next; void * node; }
所有业务结点抽象为 void * 万能指针. 瑕疵是存在 sizeof (void *) 内存浪费.
像一杯甜酒喝起来还挺爽, 只是热量有点高.
iii) 内核链表
struct $list { struct $list * next; }; #define $LIST_HEAD struct $list $node
$LIST_HEAD 宏放在需要实现的链式结构的头位置. 有点继承味道, 例如下面这样
struct list { $LIST_HEAD; ... }
住用利用隐含条件 &list = &(list.$node) => list->next = &(list.$node)->next.
链表结点首地址和业务结点首地址值相等. 瞟内核的时候看挺常见.
四两拨千斤 ~
iv) 注册链表
struct $list { struct $list * next; }; #define $LIST struct $list $node; typedef struct { struct $list * root; // 存储链表的头节点 icmp_f fadd; // 链表中插入数据执行的方法 icmp_f fget; // 链表中查找数据执行的方法 node_f fdie; // 链表中删除数据执行的方法 } * list_t; // // list_next - 获取结点n的下一个结点. // n : 当前结点 // #define list_next(n) ((void *)((struct $list *)(n))->next) // // list_create - 构建 list 对象 // fadd : 插入数据方法 // fget : 获取数据方法 // return : 创建好的链表对象 // #define list_create(fadd, fget) \ list_create_((icmp_f)fadd, (icmp_f)fget) inline list_t list_create_(icmp_f fadd, icmp_f fget) { list_t list = malloc(sizeof *list); list->root = NULL; list->fadd = fadd; list->fget = fget; list->fdie = NULL; return list; }
注册行为定义如下
// // icmp_f - 比较行为的类型 // : int add_cmp(const void * now, const void * node) // typedef int (* icmp_f)(); // // node_f - 销毁当前对象节点 // : void list_die(void * node); // typedef void (* node_f)(void * node);
当时产生这个想法是太迷恋基于函数注册的方式. 希望一次注册终身受用.
但在实战中发现, C 很多时候只用到局部部分. 功能越强大, 考虑的越全面,
代码写起来就越难受. 等同于衣服太多, 搬家就会很麻烦.
领证还要房子车子票子, 这么麻烦, 那结个 pi 呀. 必须要整改 :)
v) 取舍链表
struct list { struct list * next; ... } or // // list.h 通用的单链表库 // void * list = NULL; // struct $list { struct $list * next; }; #define $LIST struct $list $node;
简单业务上使用第一个原生链表, 在特定场合(顺序有要求)使用内核链表.
成熟在于取舍, 渣往往是抉择的时候不定, 遇到的时候不克制.
有感情那 OK, 有票子 那 OK, else 自己玩毛 ~
说了这么多没用的, 希望读者能够理解作者关于链表结构的思考心路.
本文后续重点就是讲解 $LIST ~
正文 - 接口设计
list 首先从总体接口设计感受此中气息
// // list.h 通用的单链表库 // void * list = NULL; // struct $list { struct $list * next; }; #define $LIST struct $list $node; // // list_next - 获取结点n的下一个结点. // n : 当前结点 // #define list_next(n) ((void *)((struct $list *)(n))->next) // // list_delete - 链表数据销毁操作 // list : 基础的链表结构 // pist : 指向基础的链表结构 // fdie : 链表中删除数据执行的方法 // return : void // #define list_delete(list, fdie) \ list_delete_((void **)&(list), (node_f)(fdie)) extern void list_delete_(void ** pist, node_f fdie); // // list_get - 匹配得到链表中指定值 // list : 基础的链表结构 // fget : 链表中查找数据执行的方法 // left : 待查找的结点内容 // return : 查找到的节点, NULL 表示没有查到 // #define list_get(list, fget, left) \ list_get_((list), (icmp_f)(fget), (const void *)(intptr_t)(left)) extern void * list_get_(void * list, icmp_f fget, const void * left); // // list_pop - 匹配弹出链表中指定值 // list : 基础的链表结构 // pist : 指向基础的链表结构 // fget : 链表中查找数据执行的方法 // left : 待查找的结点内容 // return : 查找到的节点, NULL 表示没有查到 // #define list_pop(list, fget, left) \ list_pop_((void **)&(list), (icmp_f)(fget), (const void *)(intptr_t)(left)) extern void * list_pop_(void ** pist, icmp_f fget, const void * left);