大理网站建设网站建设,下载的asp网站怎么打开,建设网站是什么样的,wix和wordpress简介#xff1a; 链表是linux内核中最简单#xff0c;同时也是应用最广泛的数据结构。内核中定义的是双向链表。 linux的链表不是将用户数据保存在链表节点中#xff0c;而是将链表节点保存在用户数据中。linux的链表节点只有2个指针(pre和next)#xff0c;这样的话#x…简介 链表是linux内核中最简单同时也是应用最广泛的数据结构。内核中定义的是双向链表。 linux的链表不是将用户数据保存在链表节点中而是将链表节点保存在用户数据中。linux的链表节点只有2个指针(pre和next)这样的话链表的节点将独立于用户数据之外便于实现链表的共同操作。 一、链表函数介绍
Linux内核链表源码路径 include/linux/list.h
常用函数、宏介绍
宏函数作用备注初始化LIST_HEAD_INITINTI_LIST_HEAD初始化链表头常用LIST_HEAD添加list_add头部添加常用list_add_tail尾部添加删除list_del删除节点指向特定的位置常用list_del_init删除节点后反初始化遍历list_entry根据list倒推宿主结构体的首地址常用list_for_each正向遍历获取listlist_for_each_entry正向遍历获取list数组结构list_for_each_prev反向遍历获取listlist_for_each_entry_reverse反向遍历获取list数组结构搬移list_move将链表的某个节点插入到新的链表上list_move_tail合并list_splice将2条链表合并list_splice_init合并后原有的list反初始化list_splice_taillist_splice_tail_init替换list_replace将新节点和链表上某位置的节点替换list_replace_init将新节点和链表上某位置的节点替换替换后将旧节点反初始化 定义链表结构体
struct list_head {struct list_head *next, *prev;
}; 1、初始化
1.1 创建链表头 并用 INIT_LIST_HEAD 初始化
struct list_head listHead;static inline void INIT_LIST_HEAD(struct list_head *list)
{list-next list;list-prev list;
}
1.2 也可以直接用 LIST_HEAD 创建并初始化链表头
/* 初始化 */
#define LIST_HEAD_INIT(name) { (name), (name) }#define LIST_HEAD(name) \struct list_head name LIST_HEAD_INIT(name) 2、添加
list_add list_add(struct list_head *new, struct list_head *head) 功能将new添加到链表头head的下一个位置 参数 new添加的链表节点 head链表头 list_add_tail list_add_tail(struct list_head *new, struct list_head *head) 功能将new添加到链表头head的尾部 参数 new添加的链表节点 head链表头 函数原型
/* 添加 */
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);
}3、删除
list_del list_del(struct list_head *entry) 功能删除某节点 参数 entryentry所在的链表头中将entry节点删除 list_del_init
函数原型
/* 删除 */
static inline void __list_del(struct list_head *prev, struct list_head *next)
{next-prev prev;prev-next next;
}static inline void __list_del_entry(struct list_head *entry)
{__list_del(entry-prev, entry-next);
}static inline void list_del(struct list_head *entry)
{__list_del(entry-prev, entry-next);entry-next NULL;entry-prev NULL;
}static inline void list_del_init(struct list_head *entry)
{__list_del_entry(entry);INIT_LIST_HEAD(entry);
} 4、遍历
4.1 container_of 解析
list.h文件中最复杂的就是获取用户数据的宏定义list_entry其功能是根据结构体中已知的list链表成员变量的地址来倒推宿主结构体的首地址。
#define list_entry(ptr, type, member) \container_of(ptr, type, member)
调用container_of这个宏
#define container_of(ptr, type, member) ({ \const typeof(((type *)0)-member)*__mptr (ptr); \(type *)((char *)__mptr - offsetof(type, member)); })
分析一下container_of宏
// 步骤1将数字0强制转型为type*然后取得其中的member元素
((type *)0)-member // 相当于((struct student *)0)-list// 步骤2定义一个临时变量__mptr并将其也指向ptr所指向的链表节点
const typeof(((type *)0)-member)*__mptr (ptr);// 步骤3计算member字段距离type中第一个字段的距离也就是type地址和member地址之间的差
// offset(type, member)也是一个宏定义如下
#define offsetof(TYPE, MEMBER) ((size_t) ((TYPE *)0)-MEMBER)// 步骤4将__mptr的地址 - type地址和member地址之间的差
// 其实也就是获取type的地址 4.2 遍历宏原型
/* 遍历 */
#define list_entry(ptr, type, member) \container_of(ptr, type, member) //根据结构体中的已知的成员变量的地址来寻求该结构体的首地址#define list_for_each(pos, head) \for (pos (head)-next; pos ! (head); pos pos-next)#define list_for_each_safe(pos, n, head) \for (pos (head)-next, n pos-next; pos ! (head); \pos n, n pos-next)#define list_for_each_entry(pos, head, member) \for (pos list_first_entry(head, typeof(*pos), member); \pos-member ! (head); \pos list_next_entry(pos, member))#define list_for_each_prev(pos, head) \for (pos (head)-prev; pos ! (head); pos pos-prev)#define list_for_each_entry_reverse(pos, head, member) \for (pos list_last_entry(head, typeof(*pos), member); \pos-member ! (head); \pos list_prev_entry(pos, member))
list_for_each 和 list_for_each_safe 差异 list_for_each_safe 可防止删除链表条目。如list_for_each执行的for循环中如果删除条目会导致段错误Segmentation fault (core dumped)报错。而 list_for_each_safe就可以解决此问题。 5、判断链表为空
list_empty
static inline int list_empty(const struct list_head *head)
{return head-next head;
} 二、使用方法
链表数据结构在内核态和用户态都能使用使用方法如下
1、定义 struct list_head 链表头 head
2、初始化 LIST_HEAD(head)
3、添加entry到链表 list_add_tail(entry, head)
4、遍历链表头
struct list_head *cursor, *next;list_for_each_safe(cursor, next, tx_req_list) {stpHead_Addr list_entry(cursor, struct ipcl_req, list); //根据我们结构体中的已知的成员变量的地址来寻求该结构体的首地址... //我们自己定义功能list_del_init(cursor); //链表删除cursor并初始化 cursor}
示例
代码下载路径https://download.csdn.net/download/hinewcc/89522091
#include stdio.h
#include stdlib.h
#include string.h
#include list.hstruct list_head listHead; //定义链表头//LIST_HEAD(listHead); /* 含链表的结构体 */
struct list_member {char name[32];struct list_head entry;
};#define MEMBER_NUM 5int main(int argc, char **argv)
{int i;if (argc ! 2) {printf(usage: ./app name);return -1;}printf(search name: %s\n, argv[1]);/* 1.初始化listHead链表 */INIT_LIST_HEAD(listHead); struct list_member stMember[MEMBER_NUM] {0};struct list_head *cursor, *next;/* 2.listHead链表添加 */for (i 0; i MEMBER_NUM; i) {printf(addr[%d]: %p\n, i, stMember[i]);sprintf(stMember[i].name, name%d, i);list_add_tail(stMember[i].entry, listHead); //listHead链表添加成员}/* 3.listHead链表轮询并比较 */list_for_each_safe(cursor, next, listHead) { //轮询listHead链表头/* 功能根据结构体中的已知的 entry 成员变量的地址来寻求该结构体的首地址参数1: entry成员指针参数2: 结构体类型参数3: 结构体中entry的成员名*/struct list_member *member list_entry(cursor, struct list_member, entry);if (strcmp(member-name, argv[1]) 0) { //比较printf(search OK: addr: %p\n, member);break;}}/* 4.测试 list_del 删除, list_empty 检测链表空 */list_for_each_safe(cursor, next, listHead) {struct list_member *member list_entry(cursor, struct list_member, entry);printf(del %s\n, member-name);list_del(cursor);if (list_empty(listHead)) {printf(list empty!!!\n);}}return -1;
}
编译$ gcc -o test_app -I ./ main.c
运行 $ ./test_app name1
