linux 应用层编程之内核链表list的使用

100 阅读 0 评论 66 点赞

我是靠谱客的博主淡定大船，这篇文章主要介绍linux 应用层编程之内核链表list的使用，现在分享给大家，希望可以做个参考。

linux内核提供了一个经典通用的双向循环链表list的实现，任何模块都可以借助该接口实现自己的内部循环链表。因为是通用的，可以直接移植到用户态中使用，下面介绍相关的接口与一个简单操作例子，包括链表的插入、查询、修改和删除操作。想深入了解的话直接阅读内核list源代码，代码不是很多，只有list.h 和 types.h。内核源码可以直接下载也可以使用下文给出的链接。

内核定义了链表的结构体，任何链表的实现只要在相关结构体中包含下面这个结构体就可以使用。

复制代码

1
2
3
struct list_head {
	struct list_head *next, *prev;
};

链表组织成如下：

相关API接口：

1. 链表头的初始化有两种，初始化完成就相当于创建了一个链表，接下来就可以进行对链表的增删查改操作。

复制代码

1
LIST_HEAD(name)  //name就是链表头的名字，该宏会自动定义一个名字为name 的 list_head 结构体。

第二种如下，先声明一个list_head变量，然后使用该宏初始化

复制代码

1
2
    struct list_head head;    //声明链表头
    INIT_LIST_HEAD(&head);    //链表头初始化

2. 插入链表：

复制代码

1
list_add(struct list_head *new, struct list_head *head)        //加入链表头部

复制代码

1
2
list_add_tail(struct list_head *new, struct list_head *head)   //加入到链表尾部

3. 查询链表：

复制代码

1
list_for_each(pos, head)    //遍历链表，可以结合list_entry()接口对数据操作

复制代码

1
list_for_each_safe(pos, n, head)    //如果在遍历过程中涉及结点删除操作，则需要使用这个接口

4. 删除结点

复制代码

1
list_del(struct list_head *entry)

5.在内核list源码中还定义了很多其它的链表操作，这里不再一一列举：

复制代码

1
list_empty(const struct list_head *head)     //判断链表是否为空

下面是一个使用链表的例子，包括常见的增加、删除、修改、查询等操作。

复制代码

/*
 *  Description : linux应用层编程之内核链表list的使用
 *  Date        ：20180610
 *  Author      ：mason
 *  Mail        : mrsonko@126.com
 *
 */

#include <stddef.h>
#include <stdio.h>
#include <string.h>
#include <unistd.h>
#include <stdlib.h>
#include "listdemo.h"

#define log(fmt, arg...) printf(""fmt,##arg)

void main() {
    int quit = 0;
    int flag = 0;
    int opt, key;
    struct list_head msg_head, *pos, *n;    //声明链表首部，注意这pos, n的定义，遍历链表会使用
    struct msg msg1, msg2, *pmsg;           //自定义的链表结点，结构体中嵌套list_head结构体

INIT_LIST_HEAD(&msg_head);     //链表初始化

log("*********************nn"
        "input options:n"
        "1: insertn"           //插入
        "2: serachn"           //查询
        "3: search all n"      //查询所有
        "4: modifyn"           //修改
        "5: deleten"           //删除
        "6: delete alln"       //删除全部
        "0: quitn"
        "n*********************n");
    while(!quit) {
        log("ninput options:");
        scanf("%d",  &opt);
        switch(opt){
        
            //插入链表，相同结点可重复插入，也可以在加入前比较判断防止插入重复
            case 1:
                pmsg = calloc(1, sizeof(struct msg));
                if(!pmsg){
                    log("insert fail n");
                    break;
                }
                log("input msgid : ");
                scanf("%d", &pmsg->msgid);
                log("input msg info:");
                getchar();
                gets(pmsg->msginfo);
                log("[Your have input : msgid : %d, msginfo : %s ]n", pmsg->msgid, pmsg->msginfo);
                list_add_tail(&pmsg->list, &msg_head);  //插入尾部，list_add()插入首部
                break;

//查询
             case 2:
             flag = 0 ;
             log("input msg id:");
             scanf("%d", &key);

//遍历查询
             list_for_each_entry(pmsg, &msg_head, list) {
                if(pmsg->msgid == key){ 
                    log("[msgid: %d, msginfo: %s ]n", key, pmsg->msginfo);
                    flag = 1;
                    break;
                }
             }
             if(!flag)  
                log("%d not found! n", key);
             break;

//查询所有
             case 3:
                 log("n***** msg start *****nn");
                 list_for_each_entry(pmsg, &msg_head, list){
                     log("[msgid: %d, msginfo: %s ]n", key, pmsg->msginfo);
                 }
                 log("n***** msg end   *****n");
                break;

//修改结点
             case 4:
                  flag = 0;
                  log("input msg id:");
                  scanf("%d", &key);   
                  //修改
                  list_for_each_entry(pmsg, &msg_head, list) {
                     if(pmsg->msgid == key){ 
                         log("[msgid: %d, msginfo: %s ]n", key, pmsg->msginfo);
                         log("input msg you want to set:");        
                         memset(pmsg->msginfo, 0, sizeof(pmsg->msginfo));
                         getchar();
                         gets(pmsg->msginfo);
                         flag = 1;
                     }
                  }
                  if(!flag){
                      log("msgid : %d not fount !n", key);
                  }
                  flag = 0;
                  break;

//删除结点     
             case 5:
                  flag = 0;
                  log("input msg id:");
                  scanf("%d", &key);  
                  //遍历链表并且执行删除操作需要使用这个接口 _safe
                  list_for_each_safe(pos, n, &msg_head){
                      pmsg = list_entry(pos, struct msg, list);
                      if(pmsg->msgid == key){
                          log("[delete msg, msgid:%d, msginfo:%s]n", pmsg->msgid, pmsg->msginfo);
                          list_del(pos);
                          free(pmsg);
                          flag = 1;
                      }
                  }
                  if(!flag)
                     log("msgid : %d not found!n", key);
                  flag = 0;
                  break;

//删除所有
             case 6:
                  list_for_each_safe(pos, n, &msg_head){
                      pmsg = list_entry(pos, struct msg, list);
                      log("[delete msg, msgid:%d, msginfo:%s]n", pmsg->msgid, pmsg->msginfo);
                      list_del(pos);
                      free(pmsg);
                  }
                  break;  
                  
             default:
                  //退出前释放资源
                  list_for_each_safe(pos, n, &msg_head){
                      pmsg = list_entry(pos, struct msg, list);
                      list_del(pos);
                      free(pmsg);
                  }
                  
                  quit = 1;
                break;
        }
    }
    return ;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
/*
 *  Description : linux应用层编程之内核链表list的使用
 *  Date        ：20180610
 *  Author      ：mason
 *  Mail        : mrsonko@126.com
 *
 */


#include <stddef.h>
#include <stdio.h>
#include <string.h>
#include <unistd.h>
#include <stdlib.h>
#include "listdemo.h"

#define log(fmt, arg...) printf(""fmt,##arg)

void main() {
    int quit = 0;
    int flag = 0;
    int opt, key;
    struct list_head msg_head, *pos, *n;    //声明链表首部，注意这pos, n的定义，遍历链表会使用
    struct msg msg1, msg2, *pmsg;           //自定义的链表结点，结构体中嵌套list_head结构体

    INIT_LIST_HEAD(&msg_head);     //链表初始化


    log("*********************nn"
        "input options:n"
        "1: insertn"           //插入
        "2: serachn"           //查询
        "3: search all n"      //查询所有
        "4: modifyn"           //修改
        "5: deleten"           //删除
        "6: delete alln"       //删除全部
        "0: quitn"
        "n*********************n");
    while(!quit) {
        log("ninput options:");
        scanf("%d",  &opt);
        switch(opt){
        
            //插入链表，相同结点可重复插入，也可以在加入前比较判断防止插入重复
            case 1:
                pmsg = calloc(1, sizeof(struct msg));
                if(!pmsg){
                    log("insert fail n");
                    break;
                }
                log("input msgid : ");
                scanf("%d", &pmsg->msgid);
                log("input msg info:");
                getchar();
                gets(pmsg->msginfo);
                log("[Your have input : msgid : %d, msginfo : %s ]n", pmsg->msgid, pmsg->msginfo);
                list_add_tail(&pmsg->list, &msg_head);  //插入尾部，list_add()插入首部
                break;

             //查询
             case 2:
             flag = 0 ;
             log("input msg id:");
             scanf("%d", &key);   

             //遍历查询
             list_for_each_entry(pmsg, &msg_head, list) {
                if(pmsg->msgid == key){ 
                    log("[msgid: %d, msginfo: %s ]n", key, pmsg->msginfo);
                    flag = 1;
                    break;
                }
             }
             if(!flag)  
                log("%d not found! n", key);
             break;             

             //查询所有
             case 3:
                 log("n***** msg start *****nn");
                 list_for_each_entry(pmsg, &msg_head, list){
                     log("[msgid: %d, msginfo: %s ]n", key, pmsg->msginfo);
                 }
                 log("n***** msg end   *****n");
                break;

             //修改结点
             case 4:
                  flag = 0;
                  log("input msg id:");
                  scanf("%d", &key);   
                  //修改
                  list_for_each_entry(pmsg, &msg_head, list) {
                     if(pmsg->msgid == key){ 
                         log("[msgid: %d, msginfo: %s ]n", key, pmsg->msginfo);
                         log("input msg you want to set:");        
                         memset(pmsg->msginfo, 0, sizeof(pmsg->msginfo));
                         getchar();
                         gets(pmsg->msginfo);
                         flag = 1;
                     }
                  }
                  if(!flag){
                      log("msgid : %d not fount !n", key);
                  }
                  flag = 0;
                  break;

             //删除结点     
             case 5:
                  flag = 0;
                  log("input msg id:");
                  scanf("%d", &key);  
                  //遍历链表并且执行删除操作需要使用这个接口 _safe
                  list_for_each_safe(pos, n, &msg_head){
                      pmsg = list_entry(pos, struct msg, list);
                      if(pmsg->msgid == key){
                          log("[delete msg, msgid:%d, msginfo:%s]n", pmsg->msgid, pmsg->msginfo);
                          list_del(pos);
                          free(pmsg);
                          flag = 1;
                      }
                  }
                  if(!flag)
                     log("msgid : %d not found!n", key);
                  flag = 0;
                  break;

             //删除所有
             case 6:
                  list_for_each_safe(pos, n, &msg_head){
                      pmsg = list_entry(pos, struct msg, list);
                      log("[delete msg, msgid:%d, msginfo:%s]n", pmsg->msgid, pmsg->msginfo);
                      list_del(pos);
                      free(pmsg);
                  }
                  break;  
                  
             default:
                  //退出前释放资源
                  list_for_each_safe(pos, n, &msg_head){
                      pmsg = list_entry(pos, struct msg, list);
                      list_del(pos);
                      free(pmsg);
                  }
                  
                  quit = 1;
                break;
        }
    }
    return ;
}

使用截图，查询、修改和删除操作。

头文件如下，宏定义直接从内核list.h文件中移植过来，这里只取了用到的部分，list.h还定义了很多其它的操作。

复制代码

#ifndef _LISTDEMO_H
#define _LISTDEMO_H

//通过结构体成员指针获取结构体指针位置
#define container_of(ptr, type, member) ({			
	const typeof( ((type *)0)->member ) *__mptr = (ptr);	
	(type *)( (char *)__mptr - offsetof(type,member) );})

//链表结构体
struct list_head {
	struct list_head *next, *prev;
};

//链表初始化
static inline void INIT_LIST_HEAD(struct list_head *list)
{
	list->next = list;
	list->prev = list;
}

#ifndef CONFIG_DEBUG_LIST
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;
}
#else
extern void __list_add(struct list_head *new,
			      struct list_head *prev,
			      struct list_head *next);
#endif

//添加至链表首部
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);
}

//判断链表是否为空
/**
 * list_empty - tests whether a list is empty
 * @head: the list to test.
 */
 /* if empty return 1,else 0 */
static inline int list_empty(const struct list_head *head)
{
	return head->next == head;
}

/*
 * Delete a list entry by making the prev/next entries
 * point to each other.
 *
 * This is only for internal list manipulation where we know
 * the prev/next entries already!
 */
static inline void __list_del(struct list_head * prev, struct list_head * next)
{
	next->prev = prev;
	prev->next = next;
}

//删除操作
static inline void list_del(struct list_head *entry)
{
	__list_del(entry->prev, entry->next);
	entry->next = NULL;
	entry->prev = NULL;
}

//获取链表的数据指针
#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_entry((head)->next, typeof(*pos), member);	
	     &pos->member != (head); 	
	     pos = list_entry(pos->member.next, typeof(*pos), member))
	     
#define list_for_each_entry_safe(pos, n, head, member)			
	for (pos = list_entry((head)->next, typeof(*pos), member),	
		n = list_entry(pos->member.next, typeof(*pos), member);	
	     &pos->member != (head); 					
	     pos = n, n = list_entry(n->member.next, typeof(*n), member))
	     
//取第一个元素
#define list_first_entry(ptr, type, member) 
        list_entry((ptr)->next, type, member)

//自定义消息结构体
struct msg {
    int msgid;
    char msginfo[50];
    struct list_head list;
};

#endif

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
#ifndef _LISTDEMO_H
#define _LISTDEMO_H

//通过结构体成员指针获取结构体指针位置
#define container_of(ptr, type, member) ({			
	const typeof( ((type *)0)->member ) *__mptr = (ptr);	
	(type *)( (char *)__mptr - offsetof(type,member) );})


//链表结构体
struct list_head {
	struct list_head *next, *prev;
};

//链表初始化
static inline void INIT_LIST_HEAD(struct list_head *list)
{
	list->next = list;
	list->prev = list;
}

#ifndef CONFIG_DEBUG_LIST
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;
}
#else
extern void __list_add(struct list_head *new,
			      struct list_head *prev,
			      struct list_head *next);
#endif


//添加至链表首部
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);
}

//判断链表是否为空
/**
 * list_empty - tests whether a list is empty
 * @head: the list to test.
 */
 /* if empty return 1,else 0 */
static inline int list_empty(const struct list_head *head)
{
	return head->next == head;
}

/*
 * Delete a list entry by making the prev/next entries
 * point to each other.
 *
 * This is only for internal list manipulation where we know
 * the prev/next entries already!
 */
static inline void __list_del(struct list_head * prev, struct list_head * next)
{
	next->prev = prev;
	prev->next = next;
}


//删除操作
static inline void list_del(struct list_head *entry)
{
	__list_del(entry->prev, entry->next);
	entry->next = NULL;
	entry->prev = NULL;
}

//获取链表的数据指针
#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_entry((head)->next, typeof(*pos), member);	
	     &pos->member != (head); 	
	     pos = list_entry(pos->member.next, typeof(*pos), member))
	     
#define list_for_each_entry_safe(pos, n, head, member)			
	for (pos = list_entry((head)->next, typeof(*pos), member),	
		n = list_entry(pos->member.next, typeof(*pos), member);	
	     &pos->member != (head); 					
	     pos = n, n = list_entry(n->member.next, typeof(*n), member))
	     
//取第一个元素
#define list_first_entry(ptr, type, member) 
        list_entry((ptr)->next, type, member)

//自定义消息结构体
struct msg {
    int msgid;
    char msginfo[50];
    struct list_head list;
};

#endif

代码可以直接从github上克隆下来编译运行，其中包含了内核list源码可做参考：

复制代码

1
git clone git@github.com:FuYuanDe/list.git    //下载源码后进入目录make后运行

参考资料：

https://www.ibm.com/developerworks/cn/linux/kernel/l-chain/

最后

以上就是淡定大船最近收集整理的关于linux 应用层编程之内核链表list的使用的全部内容，更多相关linux内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。

本文分类：Linux 应用程序开发
浏览次数：100 次浏览
发布日期：2023-05-18 12:40:01
本文链接：https://www.kaopuke.com/article/k-p-k_14_ujocfw_13__23__14_z.html

linux 应用层编程之内核链表list的使用

最后

评论列表共有 0 条评论

发表评论取消回复

linux 应用层编程之内核链表list的使用

最后

相关文章

评论列表共有 0 条评论

发表评论 取消回复

微信扫一扫：分享

发表评论取消回复