企业网站怎么收录,网站开发与网站制作,seo网站推广的主要目的,图片交易网站如何建设1、前言 最近写代码需用到链表结构#xff0c;正好公共库有关于链表的。第一眼看时#xff0c;觉得有点新鲜#xff0c;和我之前见到的链表结构不一样#xff0c;只有前驱和后继指针#xff0c;而没有数据域。后来看代码注释发现该代码来自linux内核#xff0c;在linux源… 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 anothers 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 anothers 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 02 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/ 深入分析 Linux 内核链表 一、 链表数据结构简介 链表是一种常用的组织有序数据的数据结构它通过指针将一系列数据节点连接成一条数据链是线性表的一种重要实现方式。相对于数组链表具有更好的动态性建立链表时无需预先知道数据总量可以随机分配空间可以高效地在链表中的任意位置实时插入或删除数据。链表的开销主要是访问的顺序性和组织链的空间损失。 通常链表数据结构至少应包含两个域数据域和指针域数据域用于存储数据指针域用于建立与下一个节点的联系。按照指针域的组织以及各个节点之间的联系形式链表又可以分为单链表、双链表、循环链表等多种类型下面分别给出这几类常见链表类型的示意图 1 单链表 图1 单链表 单链表是最简单的一类链表它的特点是仅有一个指针域指向后继节点next因此对单链表的遍历只能从头至尾通常是NULL空指针顺序进行。 2 双链表 图2 双链表 通过设计前驱和后继两个指针域双链表可以从两个方向遍历这是它区别于单链表的地方。如果打乱前驱、后继的依赖关系就可以构成二叉树如果再让首节点的前驱指向链表尾节点、尾节点的后继指向首节点如图2中虚线部分就构成了循环链表如果设计更多的指针域就可以构成各种复杂的树状数据结构。 3 循环链表 循环链表的特点是尾节点的后继指向首节点。前面已经给出了双循环链表的示意图它的特点是从任意一个节点出发沿两个方向的任何一个都能找到链表中的任意一个数据。如果去掉前驱指针就是单循环链表。 在Linux内核中使用了大量的链表结构来组织数据包括设备列表以及各种功能模块中的数据组织。这些链表大多采用在[include/linux/list.h]实现的一个相当精彩的链表数据结构。本文的后继部分就将通过示例详细介绍这一数据结构的组织和使用。 二、 Linux 2.6内核链表数据结构的实现 尽管这里使用2.6内核作为讲解的基础但实际上2.4内核中的链表结构和2.6并没有什么区别。不同之处在于2.6扩充了两种链表数据结构链表的读拷贝更新rcu和HASH链表hlist。这两种扩展都是基于最基本的list结构因此本文主要介绍基本链表结构然后再简要介绍一下rcu和hlist。 链表数据结构的定义很简单节选自[include/linux/list.h]以下所有代码除非加以说明其余均取自该文件 struct list_head { struct list_head *next, *prev; }; list_head结构包含两个指向list_head结构的指针prev和next由此可见内核的链表具备双链表功能实际上通常它都组织成双循环链表。 和第一节介绍的双链表结构模型不同这里的list_head没有数据域。在Linux内核链表中不是在链表结构中包含数据而是在数据结构中包含链表节点。 在数据结构课本中链表的经典定义方式通常是这样的以单链表为例 struct list_node { struct list_node *next; ElemType data; }; 因为ElemType的缘故对每一种数据项类型都需要定义各自的链表结构。有经验的C程序员应该知道标准模板库中的list采用的是C Template利用模板抽象出和数据项类型无关的链表操作接口。 在Linux内核链表中需要用链表组织起来的数据通常会包含一个struct list_head成员例如在[include/linux/netfilter.h]中定义了一个nf_sockopt_ops结构来描述Netfilter为某一协议族准备的getsockopt/setsockopt接口其中就有一个struct list_head list成员各个协议族的nf_sockopt_ops结构都通过这个list成员组织在一个链表中表头是定义在[net/core/netfilter.c]中的nf_sockoptsstruct list_head。从下图中我们可以看到这种通用的链表结构避免了为每个数据项类型定义自己的链表的麻烦。Linux的简捷实用、不求完美和标准的风格在这里体现得相当充分。 图3 nf_sockopts链表示意图 三、 链表操作接口 1. 声明和初始化 实际上Linux只定义了链表节点并没有专门定义链表头那么一个链表结构是如何建立起来的呢让我们来看看LIST_HEAD()这个宏 #define LIST_HEAD_INIT(name) { (name), (name) } #define LIST_HEAD(name) struct list_head name LIST_HEAD_INIT(name) 当我们用LIST_HEAD(nf_sockopts)声明一个名为nf_sockopts的链表头时它的next、prev指针都初始化为指向自己这样我们就有了一个空链表因为Linux用头指针的next是否指向自己来判断链表是否为空 static inline int list_empty(const struct list_head *head) { return head-next head; } 除了用LIST_HEAD()宏在声明的时候初始化一个链表以外Linux还提供了一个INIT_LIST_HEAD宏用于运行时初始化链表 #define INIT_LIST_HEAD(ptr) do { \ (ptr)-next (ptr); (ptr)-prev (ptr); \ } while (0) 我们用INIT_LIST_HEAD(nf_sockopts)来使用它。 2. 插入/删除/合并 a) 插入 对链表的插入操作有两种在表头插入和在表尾插入。Linux为此提供了两个接口 static inline void list_add(struct list_head *new, struct list_head *head); static inline void list_add_tail(struct list_head *new, struct list_head *head); 因为Linux链表是循环表且表头的next、prev分别指向链表中的第一个和最末一个节点所以list_add和list_add_tail的区别并不大实际上Linux分别用 __list_add(new, head, head-next); 和 __list_add(new, head-prev, head); 来实现两个接口可见在表头插入是插入在head之后而在表尾插入是插入在head-prev之后。 假设有一个新nf_sockopt_ops结构变量new_sockopt需要添加到nf_sockopts链表头我们应当这样操作 list_add(new_sockopt.list, nf_sockopts); 从这里我们看出nf_sockopts链表中记录的并不是new_sockopt的地址而是其中的list元素的地址。如何通过链表访问到new_sockopt呢下面会有详细介绍。 b) 删除 static inline void list_del(struct list_head *entry); 当我们需要删除nf_sockopts链表中添加的new_sockopt项时我们这么操作 list_del(new_sockopt.list); 被剔除下来的new_sockopt.listprev、next指针分别被设为LIST_POSITION2和LIST_POSITION1两个特殊值这样设置是为了保证不在链表中的节点项不可访问--对LIST_POSITION1和LIST_POSITION2的访问都将引起页故障。与之相对应list_del_init()函数将节点从链表中解下来之后调用LIST_INIT_HEAD()将节点置为空链状态。 c) 搬移 Linux提供了将原本属于一个链表的节点移动到另一个链表的操作并根据插入到新链表的位置分为两类 static inline void list_move(struct list_head *list, struct list_head *head); static inline void list_move_tail(struct list_head *list, struct list_head *head); 例如list_move(new_sockopt.list,nf_sockopts)会把new_sockopt从它所在的链表上删除并将其再链入nf_sockopts的表头。 d) 合并 除了针对节点的插入、删除操作Linux链表还提供了整个链表的插入功能 static inline void list_splice(struct list_head *list, struct list_head *head); 假设当前有两个链表表头分别是list1和list2都是struct list_head变量当调用list_splice(list1,list2)时只要list1非空list1链表的内容将被挂接在list2链表上位于list2和list2.next原list2表的第一个节点之间。新list2链表将以原list1表的第一个节点为首节点而尾节点不变。如图虚箭头为next指针 图4 链表合并list_splice(list1,list2) 当list1被挂接到list2之后作为原表头指针的list1的next、prev仍然指向原来的节点为了避免引起混乱Linux提供了一个list_splice_init()函数 static inline void list_splice_init(struct list_head *list, struct list_head *head); 该函数在将list合并到head链表的基础上调用INIT_LIST_HEAD(list)将list设置为空链。 3. 遍历 遍历是链表最经常的操作之一为了方便核心应用遍历链表Linux链表将遍历操作抽象成几个宏。在介绍遍历宏之前我们先看看如何从链表中访问到我们真正需要的数据项。 a) 由链表节点到数据项变量 我们知道Linux链表中仅保存了数据项结构中list_head成员变量的地址那么我们如何通过这个list_head成员访问到作为它的所有者的节点数据呢Linux为此提供了一个list_entry(ptr,type,member)宏其中ptr是指向该数据中list_head成员的指针也就是存储在链表中的地址值type是数据项的类型member则是数据项类型定义中list_head成员的变量名例如我们要访问nf_sockopts链表中首个nf_sockopt_ops变量则如此调用 list_entry(nf_sockopts-next, struct nf_sockopt_ops, list); 这里list正是nf_sockopt_ops结构中定义的用于链表操作的节点成员变量名。 list_entry的使用相当简单相比之下它的实现则有一些难懂 #define list_entry(ptr, type, member) container_of(ptr, type, member) container_of宏定义在[include/linux/kernel.h]中 #define container_of(ptr, type, member) ({ \ const typeof( ((type *)0)-member ) *__mptr (ptr); \ (type *)( (char *)__mptr - offsetof(type,member) );}) offsetof宏定义在[include/linux/stddef.h]中 #define offsetof(TYPE, MEMBER) ((size_t) ((TYPE *)0)-MEMBER) size_t最终定义为unsigned inti386。 这里使用的是一个利用编译器技术的小技巧即先求得结构成员在与结构中的偏移量然后根据成员变量的地址反过来得出属主结构变量的地址。 container_of()和offsetof()并不仅用于链表操作这里最有趣的地方是((type *)0)-member它将0地址强制转换为type结构的指针再访问到type结构中的member成员。在container_of宏中它用来给typeof()提供参数typeof()是gcc的扩展和sizeof()类似以获得member成员的数据类型在offsetof()中这个member成员的地址实际上就是type数据结构中member成员相对于结构变量的偏移量。 如果这么说还不好理解的话不妨看看下面这张图 图5 offsetof()宏的原理 对于给定一个结构offsetof(type,member)是一个常量list_entry()正是利用这个不变的偏移量来求得链表数据项的变量地址。 b) 遍历宏 在[net/core/netfilter.c]的nf_register_sockopt()函数中有这么一段话 …… struct list_head *i; …… list_for_each(i, nf_sockopts) { struct nf_sockopt_ops *ops (struct nf_sockopt_ops *)i; …… } …… 函数首先定义一个(struct list_head *)指针变量i然后调用list_for_each(i,nf_sockopts)进行遍历。在[include/linux/list.h]中list_for_each()宏是这么定义的 #define list_for_each(pos, head) \ for (pos (head)-next, prefetch(pos-next); pos ! (head); \ pos pos-next, prefetch(pos-next)) 它实际上是一个for循环利用传入的pos作为循环变量从表头head开始逐项向后next方向移动pos直至又回到headprefetch()可以不考虑用于预取以提高遍历速度。 那么在nf_register_sockopt()中实际上就是遍历nf_sockopts链表。为什么能直接将获得的list_head成员变量地址当成struct nf_sockopt_ops数据项变量的地址呢我们注意到在struct nf_sockopt_ops结构中list是其中的第一项成员因此它的地址也就是结构变量的地址。更规范的获得数据变量地址的用法应该是 struct nf_sockopt_ops *ops list_entry(i, struct nf_sockopt_ops, list); 大多数情况下遍历链表的时候都需要获得链表节点数据项也就是说list_for_each()和list_entry()总是同时使用。对此Linux给出了一个list_for_each_entry()宏 #define list_for_each_entry(pos, head, member) …… 与list_for_each()不同这里的pos是数据项结构指针类型而不是(struct list_head *)。nf_register_sockopt()函数可以利用这个宏而设计得更简单 …… struct nf_sockopt_ops *ops; list_for_each_entry(ops,nf_sockopts,list){ …… } …… 某些应用需要反向遍历链表Linux提供了list_for_each_prev()和list_for_each_entry_reverse()来完成这一操作使用方法和上面介绍的list_for_each()、list_for_each_entry()完全相同。 如果遍历不是从链表头开始而是从已知的某个节点pos开始则可以使用list_for_each_entry_continue(pos,head,member)。有时还会出现这种需求即经过一系列计算后如果pos有值则从pos开始遍历如果没有则从链表头开始为此Linux专门提供了一个list_prepare_entry(pos,head,member)宏将它的返回值作为list_for_each_entry_continue()的pos参数就可以满足这一要求。 4. 安全性考虑 在并发执行的环境下链表操作通常都应该考虑同步安全性问题为了方便Linux将这一操作留给应用自己处理。Linux链表自己考虑的安全性主要有两个方面 a) list_empty()判断 基本的list_empty()仅以头指针的next是否指向自己来判断链表是否为空Linux链表另行提供了一个list_empty_careful()宏它同时判断头指针的next和prev仅当两者都指向自己时才返回真。这主要是为了应付另一个cpu正在处理同一个链表而造成next、prev不一致的情况。但代码注释也承认这一安全保障能力有限除非其他cpu的链表操作只有list_del_init()否则仍然不能保证安全也就是说还是需要加锁保护。 b) 遍历时节点删除 前面介绍了用于链表遍历的几个宏它们都是通过移动pos指针来达到遍历的目的。但如果遍历的操作中包含删除pos指针所指向的节点pos指针的移动就会被中断因为list_del(pos)将把pos的next、prev置成LIST_POSITION2和LIST_POSITION1的特殊值。 当然调用者完全可以自己缓存next指针使遍历操作能够连贯起来但为了编程的一致性Linux链表仍然提供了两个对应于基本遍历操作的_safe接口list_for_each_safe(pos, n, head)、list_for_each_entry_safe(pos, n, head, member)它们要求调用者另外提供一个与pos同类型的指针n在for循环中暂存pos下一个节点的地址避免因pos节点被释放而造成的断链。 四、 扩展 1. hlist 图6 list和hlist 精益求精的Linux链表设计者因为list.h没有署名所以很可能就是Linus Torvalds认为双头next、prev的双链表对于HASH表来说过于浪费因而另行设计了一套用于HASH表应用的hlist数据结构--单指针表头双循环链表从上图可以看出hlist的表头仅有一个指向首节点的指针而没有指向尾节点的指针这样在可能是海量的HASH表中存储的表头就能减少一半的空间消耗。 因为表头和节点的数据结构不同插入操作如果发生在表头和首节点之间以往的方法就行不通了表头的first指针必须修改指向新插入的节点却不能使用类似list_add()这样统一的描述。为此hlist节点的prev不再是指向前一个节点的指针而是指向前一个节点可能是表头中的next对于表头则是first指针struct list_head **pprev从而在表头插入的操作可以通过一致的*(node-pprev)访问和修改前驱节点的next或first指针。 2. read-copy update 在Linux链表功能接口中还有一系列以_rcu结尾的宏与以上介绍的很多函数一一对应。RCURead-Copy Update是2.5/2.6内核中引入的新技术它通过延迟写操作来提高同步性能。 我们知道系统中数据读取操作远多于写操作而rwlock机制在smp环境下随着处理机增多性能会迅速下降见参考资料4。针对这一应用背景IBM Linux技术中心的Paul E. McKenney提出了读拷贝更新的技术并将其应用于Linux内核中。RCU技术的核心是写操作分为写-更新两步允许读操作在任何时候无阻访问当系统有写操作时更新动作一直延迟到对该数据的所有读操作完成为止。Linux链表中的RCU功能只是Linux RCU的很小一部分对于RCU的实现分析已超出了本文所及有兴趣的读者可以自行参阅本文的参考资料而对RCU链表的使用和基本链表的使用方法基本相同。 五、 示例 附件中的程序除了能正向、反向输出文件以外并无实际作用仅用于演示Linux链表的使用。 为了简便例子采用的是用户态程序模板如果需要运行可采用如下命令编译 gcc -D__KERNEL__ -I/usr/src/linux-2.6.7/include pfile.c -o pfile 因为内核链表限制在内核态使用但实际上对于数据结构本身而言并非只能在核态运行因此在笔者的编译中使用-D__KERNEL__开关欺骗编译器。转载于:https://www.cnblogs.com/alantu2018/p/8468939.html
