linux内核数据结构之链表【转】

简介:

转自:http://www.cnblogs.com/Anker/p/3475643.html

1、前言

   最近写代码需用到链表结构,正好公共库有关于链表的。第一眼看时,觉得有点新鲜,和我之前见到的链表结构不一样,只有前驱和后继指针,而没有数据域。后来看代码注释发现该代码来自linux内核,在linux源代码下include/Lish.h下。这个链表具备通用性,使用非常方便。只需要在结构定义一个链表结构就可以使用。

2、链表介绍

  链表是非常基本的数据结构,根据链个数分为单链表、双链表,根据是否循环分为单向链表和循环链表。通常定义定义链表结构如下:

typedef struct node
{
     ElemType data;      //数据域
     struct node *next; //指针域 }node, *list;

链表中包含数据域和指针域。链表通常包含一个头结点,不存放数据,方便链表操作。单向循环链表结构如下图所示:

双向循环链表结构如下图所示:

  这样带数据域的链表降低了链表的通用性,不容易扩展。linux内核定义的链表结构不带数据域,只需要两个指针完成链表的操作。将链表节点加入数据结构,具备非常高的扩展性,通用性。链表结构定义如下所示:

struct list_head {
    struct list_head *next, *prev;
};

链表结构如下所示:

  需要用链表结构时,只需要在结构体中定义一个链表类型的数据即可。例如定义一个app_info链表,

复制代码
复制代码
1 typedef struct application_info
2 { 3  uint32_t app_id; 4  uint32_t up_flow; 5  uint32_t down_flow; 6 struct list_head app_info_head; //链表节点 7 }app_info;
复制代码
复制代码

定义一个app_info链表,app_info app_info_list;通过app_info_head进行链表操作。根据C语言指针操作,通过container_of和offsetof,可以根据app_info_head的地址找出app_info的起始地址,即一个完整ap_info结构的起始地址。可以参考:http://www.cnblogs.com/Anker/p/3472271.html

3、linux内核链表实现

  内核实现的是双向循环链表,提供了链表操作的基本功能。

(1)初始化链表头结点

复制代码
复制代码
#define LIST_HEAD_INIT(name) { &(name), &(name) }

#define LIST_HEAD(name) \
    struct list_head name = LIST_HEAD_INIT(name)

static inline void INIT_LIST_HEAD(struct list_head *list) { list->next = list; list->prev = list; }
复制代码
复制代码

LIST_HEAD宏创建一个链表头结点,并用LIST_HEAD_INIT宏对头结点进行赋值,使得头结点的前驱和后继指向自己。

INIT_LIST_HEAD函数对链表进行初始化,使得前驱和后继指针指针指向头结点。

(2)插入节点

复制代码
复制代码
 1 static inline void __list_add(struct list_head *new,  2 struct list_head *prev,  3 struct list_head *next)  4 {  5 next->prev = new;  6 new->next = next;  7 new->prev = prev;  8 prev->next = new;  9 } 10 11 static inline void list_add(struct list_head *new, struct list_head *head) 12 { 13 __list_add(new, head, head->next); 14 } 15 16 static inline void list_add_tail(struct list_head *new, struct list_head *head) 17 { 18 __list_add(new, head->prev, head); 19 }
复制代码
复制代码

  插入节点分为从链表头部插入list_add和链表尾部插入list_add_tail,通过调用__list_add函数进行实现,head->next指向之一个节点,head->prev指向尾部节点。

(3)删除节点

复制代码
复制代码
 1 static inline void __list_del(struct list_head * prev, struct list_head * next)  2 {  3 next->prev = prev;  4 prev->next = next;  5 }  6  7 static inline void list_del(struct list_head *entry)  8 {  9 __list_del(entry->prev, entry->next); 10 entry->next = LIST_POISON1; 11 entry->prev = LIST_POISON2; 12 }
复制代码
复制代码

  从链表中删除一个节点,需要改变该节点前驱节点的后继结点和后继结点的前驱节点。最后设置该节点的前驱节点和后继结点指向LIST_POSITION1和LIST_POSITION2两个特殊值,这样设置是为了保证不在链表中的节点项不可访问,对LIST_POSITION1和LIST_POSITION2的访问都将引起页故障

复制代码
复制代码
/*
 * These are non-NULL pointers that will result in page faults
 * under normal circumstances, used to verify that nobody uses
 * non-initialized list entries.
 */
#define LIST_POISON1  ((void *) 0x00100100 + POISON_POINTER_DELTA)
#define LIST_POISON2 ((void *) 0x00200200 + POISON_POINTER_DELTA)
复制代码
复制代码

(4)移动节点

复制代码
复制代码
 1 /**
 2  * list_move - delete from one list and add as another's head  3  * @list: the entry to move  4  * @head: the head that will precede our entry  5 */  6 static inline void list_move(struct list_head *list, struct list_head *head)  7 {  8 __list_del(list->prev, list->next);  9  list_add(list, head); 10 } 11 12 /** 13  * list_move_tail - delete from one list and add as another's tail 14  * @list: the entry to move 15  * @head: the head that will follow our entry 16 */ 17 static inline void list_move_tail(struct list_head *list, 18 struct list_head *head) 19 { 20 __list_del(list->prev, list->next); 21  list_add_tail(list, head); 22 }
复制代码
复制代码

move将一个节点移动到头部或者尾部。

(5)判断链表

复制代码
复制代码
 1 /**
 2  * list_is_last - tests whether @list is the last entry in list @head  3  * @list: the entry to test  4  * @head: the head of the list  5 */  6 static inline int list_is_last(const struct list_head *list,  7 const struct list_head *head)  8 {  9 return list->next == head; 10 } 11 12 /** 13  * list_empty - tests whether a list is empty 14  * @head: the list to test. 15 */ 16 static inline int list_empty(const struct list_head *head) 17 { 18 return head->next == head; 19 }
复制代码
复制代码

list_is_last函数判断节点是否为末尾节点,list_empty判断链表是否为空。

(6)遍历链表

复制代码
复制代码
 1 /**
 2  * list_entry - get the struct for this entry  3  * @ptr: the &struct list_head pointer.  4  * @type: the type of the struct this is embedded in.  5  * @member: the name of the list_struct within the struct.  6 */  7 #define list_entry(ptr, type, member) \  8  container_of(ptr, type, member)  9 10 /** 11  * list_first_entry - get the first element from a list 12  * @ptr: the list head to take the element from. 13  * @type: the type of the struct this is embedded in. 14  * @member: the name of the list_struct within the struct. 15  * 16  * Note, that list is expected to be not empty. 17 */ 18 #define list_first_entry(ptr, type, member) \ 19 list_entry((ptr)->next, type, member) 20 21 /** 22  * list_for_each - iterate over a list 23  * @pos: the &struct list_head to use as a loop cursor. 24  * @head: the head for your list. 25 */ 26 #define list_for_each(pos, head) \ 27 for (pos = (head)->next; prefetch(pos->next), pos != (head); \ 28 pos = pos->next)
复制代码
复制代码

宏list_entity获取链表的结构,包括数据域。list_first_entry获取链表第一个节点,包括数据源。list_for_each宏对链表节点进行遍历。

4、测试例子

编写一个简单使用链表的程序,从而掌握链表的使用。

自定义个类似的list结构如下所示:mylist.h

复制代码
复制代码
 1 # define POISON_POINTER_DELTA 0
 2 
 3 #define LIST_POISON1 ((void *) 0x00100100 + POISON_POINTER_DELTA)  4 #define LIST_POISON2 ((void *) 0x00200200 + POISON_POINTER_DELTA)  5  6 //计算member在type中的位置  7 #define offsetof(type, member) (size_t)(&((type*)0)->member)  8 //根据member的地址获取type的起始地址  9 #define container_of(ptr, type, member) ({ \ 10 const typeof(((type *)0)->member)*__mptr = (ptr); \ 11 (type *)((char *)__mptr - offsetof(type, member)); }) 12 13 //链表结构 14 struct list_head 15 { 16 struct list_head *prev; 17 struct list_head *next; 18 }; 19 20 static inline void init_list_head(struct list_head *list) 21 { 22 list->prev = list; 23 list->next = list; 24 } 25 26 static inline void __list_add(struct list_head *new, 27 struct list_head *prev, struct list_head *next) 28 { 29 prev->next = new; 30 new->prev = prev; 31 new->next = next; 32 next->prev = new; 33 } 34 35 //从头部添加 36 static inline void list_add(struct list_head *new , struct list_head *head) 37 { 38 __list_add(new, head, head->next); 39 } 40 //从尾部添加 41 static inline void list_add_tail(struct list_head *new, struct list_head *head) 42 { 43 __list_add(new, head->prev, head); 44 } 45 46 static inline void __list_del(struct list_head *prev, struct list_head *next) 47 { 48 prev->next = next; 49 next->prev = prev; 50 } 51 52 static inline void list_del(struct list_head *entry) 53 { 54 __list_del(entry->prev, entry->next); 55 entry->next = LIST_POISON1; 56 entry->prev = LIST_POISON2; 57 } 58 59 static inline void list_move(struct list_head *list, struct list_head *head) 60 { 61 __list_del(list->prev, list->next); 62  list_add(list, head); 63 } 64 65 static inline void list_move_tail(struct list_head *list, 66 struct list_head *head) 67 { 68 __list_del(list->prev, list->next); 69  list_add_tail(list, head); 70 } 71 #define list_entry(ptr, type, member) \ 72  container_of(ptr, type, member) 73 74 #define list_first_entry(ptr, type, member) \ 75 list_entry((ptr)->next, type, member) 76 77 #define list_for_each(pos, head) \ 78 for (pos = (head)->next; pos != (head); pos = pos->next)
复制代码
复制代码

mylist.c如下所示:

复制代码
复制代码
 1 /**@brief 练习使用linux内核链表,功能包括:
 2  * 定义链表结构,创建链表、插入节点、删除节点、移动节点、遍历节点  3  *  4  *@auther Anker @date 2013-12-15  5  **/  6 #include <stdio.h>  7 #include <inttypes.h>  8 #include <stdlib.h>  9 #include <errno.h> 10 #include "mylist.h" 11 //定义app_info链表结构 12 typedef struct application_info 13 { 14  uint32_t app_id; 15  uint32_t up_flow; 16  uint32_t down_flow; 17 struct list_head app_info_node;//链表节点 18 }app_info; 19 20 21 app_info* get_app_info(uint32_t app_id, uint32_t up_flow, uint32_t down_flow) 22 { 23 app_info *app = (app_info*)malloc(sizeof(app_info)); 24 if (app == NULL) 25  { 26 fprintf(stderr, "Failed to malloc memory, errno:%u, reason:%s\n", 27  errno, strerror(errno)); 28 return NULL; 29  } 30 app->app_id = app_id; 31 app->up_flow = up_flow; 32 app->down_flow = down_flow; 33 return app; 34 } 35 static void for_each_app(const struct list_head *head) 36 { 37 struct list_head *pos; 38 app_info *app; 39 //遍历链表 40  list_for_each(pos, head) 41  { 42 app = list_entry(pos, app_info, app_info_node); 43 printf("ap_id: %u\tup_flow: %u\tdown_flow: %u\n", 44 app->app_id, app->up_flow, app->down_flow); 45 46  } 47 } 48 49 void destroy_app_list(struct list_head *head) 50 { 51 struct list_head *pos = head->next; 52 struct list_head *tmp = NULL; 53 while (pos != head) 54  { 55 tmp = pos->next; 56  list_del(pos); 57 pos = tmp; 58  } 59 } 60 61 62 int main() 63 { 64 //创建一个app_info 65 app_info * app_info_list = (app_info*)malloc(sizeof(app_info)); 66 app_info *app; 67 if (app_info_list == NULL) 68  { 69 fprintf(stderr, "Failed to malloc memory, errno:%u, reason:%s\n", 70  errno, strerror(errno)); 71 return -1; 72  } 73 //初始化链表头部 74 struct list_head *head = &app_info_list->app_info_node; 75  init_list_head(head); 76 //插入三个app_info 77 app = get_app_info(1001, 100, 200); 78 list_add_tail(&app->app_info_node, head); 79 app = get_app_info(1002, 80, 100); 80 list_add_tail(&app->app_info_node, head); 81 app = get_app_info(1003, 90, 120); 82 list_add_tail(&app->app_info_node, head); 83 printf("After insert three app_info: \n"); 84 for_each_app(head); 85 //将第一个节点移到末尾 86 printf("Move first node to tail:\n"); 87 list_move_tail(head->next, head); 88 for_each_app(head); 89 //删除最后一个节点 90 printf("Delete the last node:\n"); 91 list_del(head->prev); 92 for_each_app(head); 93 destroy_app_list(head); 94 free(app_info_list); 95 return 0; 96 }
复制代码
复制代码

测试结果如下所示:

参考网址:

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

相关文章
|
3天前
|
存储 关系型数据库 分布式数据库
PostgreSQL 18 发布,快来 PolarDB 尝鲜!
PostgreSQL 18 发布,PolarDB for PostgreSQL 全面兼容。新版本支持异步I/O、UUIDv7、虚拟生成列、逻辑复制增强及OAuth认证,显著提升性能与安全。PolarDB-PG 18 支持存算分离架构,融合海量弹性存储与极致计算性能,搭配丰富插件生态,为企业提供高效、稳定、灵活的云数据库解决方案,助力企业数字化转型如虎添翼!
|
14天前
|
弹性计算 关系型数据库 微服务
基于 Docker 与 Kubernetes(K3s)的微服务:阿里云生产环境扩容实践
在微服务架构中,如何实现“稳定扩容”与“成本可控”是企业面临的核心挑战。本文结合 Python FastAPI 微服务实战,详解如何基于阿里云基础设施,利用 Docker 封装服务、K3s 实现容器编排,构建生产级微服务架构。内容涵盖容器构建、集群部署、自动扩缩容、可观测性等关键环节,适配阿里云资源特性与服务生态,助力企业打造低成本、高可靠、易扩展的微服务解决方案。
1305 5
|
13天前
|
机器学习/深度学习 人工智能 前端开发
通义DeepResearch全面开源!同步分享可落地的高阶Agent构建方法论
通义研究团队开源发布通义 DeepResearch —— 首个在性能上可与 OpenAI DeepResearch 相媲美、并在多项权威基准测试中取得领先表现的全开源 Web Agent。
1334 87
|
3天前
|
弹性计算 安全 数据安全/隐私保护
2025年阿里云域名备案流程(新手图文详细流程)
本文图文详解阿里云账号注册、服务器租赁、域名购买及备案全流程,涵盖企业实名认证、信息模板创建、域名备案提交与管局审核等关键步骤,助您快速完成网站上线前的准备工作。
185 82
2025年阿里云域名备案流程(新手图文详细流程)
|
7天前
|
前端开发
Promise的then方法返回的新Promise对象的状态为“失败(Rejected)”时,链式调用会如何执行?
Promise的then方法返回的新Promise对象的状态为“失败(Rejected)”时,链式调用会如何执行?
244 127