C 链表 - linux 如何实现

2019-11-11 03:15:00

字体：大中小

来源：转载

供稿：网友

链表是基本数据结构，一开始学习数据结构时，我一般这么定义，对应实现从头或尾插入的处理函数，

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 代码，程序员的自我修养。

上一篇：关于mfc线程的退出问题、同步问题

下一篇：POI遍历Excle表