Linux内核链表的探索与应用
发布时间：2021-11-21 21:38:54 所属栏目：教程 来源：互联网
导读：前言： 在Linux内核中使用了大量的链表来组织其数据，其采用了双向链表作为其基本的数据结构。但是与我们传统的数据结构中所学的双向链表又有着本质的一些不同（其不包含数据域）。其主要是Linux内核链表在设计时给出了一种抽象的定义。 采用这种定义有以下
|
前言： 在Linux内核中使用了大量的链表来组织其数据，其采用了双向链表作为其基本的数据结构。但是与我们传统的数据结构中所学的双向链表又有着本质的一些不同（其不包含数据域）。其主要是Linux内核链表在设计时给出了一种抽象的定义。 采用这种定义有以下两种好处：1是可扩展性，2是封装。可扩展性肯定是必须的，内核一直都是在发展中的，所以代码都不能写成死代码，要方便修改和追加。将链表常见的操作都进行封装，使用者只关注接口，不需关注实现。 分析内核中的链表我们可以做些什么呢？ 个人认为我们可以将其复用到用户态编程中，以后在用户态下编程就不需要写一些关于链表的代码了，直接将内核中list.h中的代码拷贝过来用。也可以整理出my_list.h，在以后的用户态编程中直接将其包含到C文件中。 一.Linux 内核链表数据结构 1.其代码位于include/linux/list.h中，3.0内核中将其数据结构定义放在了include/linux/types.h中 链表的数据定义： struct list_head{ struct list_head * next,*prev; } 这个不含数据域的链表，可以嵌入到任何结构中，例如可以按如下方式定义含有数据域的链表： struct test_list{ void *testdata; structlist_head list; }; 说明： 1>list 域隐蔽了链表的指针特性 2>struct list_head 可以位于结构的任何位置，可以给其起任何名字。 3>在一个结构体中可以有多个list域。 以struct list_head 为基本对象，对链表进行插入、删除、合并以及遍历等各种操作。 2.内核链表数据结构的设计思想是： 尽可能的代码重用，化大堆的链表设计为单个链表。 3.使用循环链表的好处： 双向循环链表的效率是最高的，找头节点，尾节点，直接前驱，直接后继时间复杂度都是O (1) ，而使用单链表，单向循环链表或其他形式的链表是不能完成的。 4.链表的构造： 如果需要构造某类对象的特定列表，则在其结构中定义一个类型为list_head 指针的成员（例如上面所说的struct test_list），通过这个成员将这类对象连接起来，形成所需列表，并通过通用链表函数对其进行操作。其优点是只需编写通用链表函数，即可构造和操作不同对象的列表，而无需为每类对象的每种列表编写专用函数，实现了代码的重用。 5.如何内核链表使用： 如果想对某种类型创建链表，就把一个list_head类型的变量嵌入到该类型中，用list_head中的成员和相对应的处理函数来对链表进行遍历。如果想得到相应的结构的指针，使用list_entry可以算出来。 二.链表的声明和初始化宏 实际上，struct list_head 只定义了链表结点，并没有专门定义链表头,可以 使用以下两个宏 #define LIST_HEAD_INIT(name) { &(name), &(name) } #define LIST_HEAD(name) struct list_head name = LIST_HEAD_INIT(name) 1>name 为结构体struct list_head{}的一个结构体变量，&(name)为该结构体变量的地址。用name结构体变量的始地址将改结构体变量进行初始化。 2>LIST_HEAD_INIT(name)函数宏只进行初始化 3>LIST_HEAD(name)函数宏声明并进行初始化 4>如果要声明并初始化自己的链表头mylist_head,则直接调用LIST_HEAD: LIST_HEAD（mylist_head） 调用之后，mylist_head的next,prev指针都初始化为指向自己，这样就有了一个空链表。因此可以得知在Linux中用头指针的next是否指向自己来判断链表是否为空。 5>除了LIST_HEAD宏在编译时静态初始化，还可以使用内嵌函数INIT_LIST_HEAD(struct list_head *list)在运行时进行初始化。 例如：调用INIT_LIST_HEAD(&mylist_head)对mylist_head链表进行初始化。 static inline void INIT_LIST_HEAD(struct list_head *list) { list->next = list; list->prev = list; } 注无论是采用哪种方式，新生成的链表头的指针next,prev都初始化为指向自己  （编辑：江门站长网） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |
