linux内核数据结构之链表【转】 - 张昺华

发布时间:2017-7-9 7:16:16编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"linux内核数据结构之链表【转】 - 张昺华",主要涉及到linux内核数据结构之链表【转】 - 张昺华方面的内容,对于linux内核数据结构之链表【转】 - 张昺华感兴趣的同学可以参考一下。

转自:http://www.cnblogs.com/Anker/archive/2013/12/15/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)
复制代码


上一篇:hadoop1.0.4升级到hadoop2.2 具体流程步骤
下一篇:webpack2 项目构建一

相关文章

相关评论

本站评论功能暂时取消,后续此功能例行通知。

一、不得利用本站危害国家安全、泄露国家秘密,不得侵犯国家社会集体的和公民的合法权益,不得利用本站制作、复制和传播不法有害信息!

二、互相尊重,对自己的言论和行为负责。

好贷网好贷款