C 链表 - linux 如何实现
链表是基本数据结构， 一开始学习数据结构时， 我一般这么定义， 对应实现从头或尾插入的处理函数，
struct int_node_old {
int val;
struct int_node_old *next;
};
void old_list_insert(struct int_node_old *head, struct int_node_old *new)
{
new->next = head->next;
head->next = new;
}
void old_list_insert_tail(struct int_node_old *head, struct int_node_old *new)
{
struct int_node_old *list = head;
for (; list->next != NULL; list = list->next);
list->next = new;
new->next = NULL;
}但是发现， 如果这么定义的话，每次实现一个list的结构， 都需要重新对应编写处理函数， 重复轮子。
想起前段时间， 看到FreeRTOS提供的链表处理方式（《 FreeRTOS 任务调度 List 组织 》）， 将链表结构定义和实际使用时具体节点数据内容分开定义， 供系统各个模块使用。
查看linux的源码， 发现linux中也为我们提供了相似的实现（源码）, 把一些共性统一起来。 类是 python 中for_each处理，有些意思。
linux 下的链表定义在文件 include/linux/types.h， 采用的是双向列表
struct list_head {
struct list_head *next, *prev;
};在文件list.h, 提供了一常用的接口，
根据自己的需求， 定义节点node， 建立 list 并添加节点后， 看到的组织如图所示 ：
list
利用这个定义， 我定义了一个自己的list数据结构， 并copy了一些接口实现，感受下，linux 是如何管理链表的。
// list 节点结构定义
struct int_node {
int val;
struct list_head list;
};
// 新建一个list head， 初始化其指针指向自身
#define LIST_HEAD(name) \
struct list_head name = {&(name), &(name)};
// 将新节点插入到指定两个节点之间
static inline void __list_add(struct list_head *new,
struct list_head *prev,
struct list_head *next)
{
next->prev = new;
new->next = next;
new->prev = prev;
prev->next = new;
}
// 将新节点插入到链表头
static inline void list_add(struct list_head *new, struct list_head *head)
{
__list_add(new, head, head->next);
}
// 将新节点插入到链表尾
static inline void list_add_tail(struct list_head *new, struct list_head *head)
{
__list_add(new, head->prev, head);
}
// 正序遍历宏，
#define list_for_each(pos, head) \
for ((pos) = (head)->next; (pos) != (head); (pos) = (pos)->next)
// 逆序遍历宏
#define list_for_each_prev(pos, head) \
for ((pos) = (head)->prev; (pos) != (head); (pos) = (pos)->prev)
// 已知一个结构的成员，获取该成员所属结构体地址
#define container_of(ptr, type, menber) \
(type *)((char*)ptr - (char*) &(((type *)0)->menber))
#define list_entry(ptr, type, menber) container_of(ptr, type, menber)通过 container_of， 可以取得我们当前正在操作链表所属结构体地址，进而对具体数据进行处理， 利用c语言的一个小技巧， 把结构体投影到地址为0的地方，那么成员的绝对地址就是偏移量， 得到偏移量后，根据成员的p指针反算出结构体的首地址。 另外一种做法是定义list_head中， 包含一个成员变量，指向其所属，FreeRTOS是如此做的。
int main(void)
{
LIST_HEAD(my_list);
struct int_node a, b, c;
a.val = 1;
b.val = 2;
c.val = 3;
list_add(&(a.list), &my_list);
list_add(&(b.list), &my_list);
list_add_tail(&(c.list), &my_list);
struct list_head *plist;
struct int_node *pnode;
list_for_each(plist, &my_list) {
pnode = list_entry(plist, struct int_node, list);
printf("%d ", pnode->val);
}
printf("\n");
list_for_each_prev(plist, &my_list) {
pnode = list_entry(plist, struct int_node, list);
printf("%d ", pnode->val);
}
printf("\n");
return 0;
}虽然比较简单，记录下，学习linux 代码， 程序员的自我修养。
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2017.02.07 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读