Linux内核中链表的实现与应用【转】

简介:

转自:http://blog.chinaunix.net/uid-27037833-id-3237153.html

链表(循环双向链表)是Linux内核中最简单、最常用的一种数据结构。

       
       1、链表的定义
            struct list_head {
                struct list_head *next, *prev;
            }
           这个不含数据域的链表,可以嵌入到任何数据结构中,例如可按如下方式定义含有数据域的链表:
            struct my_list {
                void  * mydata;
                struct list_head  list;
            } ;
 
       2、链表的声明和初始化宏
            struct list_head 只定义了链表结点,并没有专门定义链表头.那么一个链表结点是如何建立起来的?
内核代码 list.h 中定义了两个宏:
            #defind  LIST_HEAD_INIT(name)    { &(name), &(name) }      //仅初始化
            #defind  LIST_HEAD(name)     struct list_head  name = LIST_HEAD_INIT(name)  //声明并初始化
           
            如果要声明并初始化链表头mylist_head,则直接调用:LIST_HEAD(mylist_head),之后,
mylist_head的next、prev指针都初始化为指向自己。这样,就有了一个带头结点的空链表。
 
             判断链表是否为空的函数:
             static inline int list_empty(const struct list_head  * head) {
                  return head->next  ==  head;
              }    //返回1表示链表为空,0表示不空
 
      3、在链表中增加一个结点
          (内核代码中,函数名前加两个下划线表示内部函数)
            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 ;
            }  
          
            list.h 中增加结点的两个函数为:
           (链表是循环的,可以将任何结点传递给head,调用这个内部函数以分别在链表头和尾增加结点)
            static inline void list_add(struct list_head *new, struct llist_head *head)
            {
                    __list_add(new, head, head -> next) ;
            }
            static inline void list_add_tail(struct list_head 8new, struct list_head *head)
            {
                     __list_add(new, head -> prev, head) ;
            }
            附:给head传递第一个结点,可以用来实现一个队列,传递最后一个结点,可以实现一个栈。
            static 加在函数前,表示这个函数是静态函数,其实际上是对作用域的限制,指该函数作用域仅局限
           于本文件。所以说,static 具有信息隐蔽的作用。而函数前加 inline 关键字的函数,叫内联函数,表
           示编译程序在调用这个函数时,立即将该函数展开。
            
    4、 遍历链表
           list.h 中定义了如下遍历链表的宏:
           #define   list_for_each(pos, head)    for(pos = (head)-> next ;  pos != (head) ;  pos = pos -> next)  
           这种遍历仅仅是找到一个个结点的当前位置,那如何通过pos获得起始结点的地址,从而可以引用结
点的域?list.h 中定义了 list_entry 宏:
           #define   list_entry( ptr, type, member )  \
              ( (type *) ( (char *) (ptr)  - (unsigned long) ( &( (type *)0 )  ->  member ) ) )
          分析:(unsigned long) ( &( (type *)0 )  ->  member ) 把 0 地址转化为 type 结构的指针,然后获取该
          结构中 member 域的指针,也就是获得了 member 在type 结构中的偏移量。其中  (char *) (ptr) 求
         出的是 ptr 的绝对地址,二者相减,于是得到 type 类型结构体的起始地址,即起始结点的地址。
 
   5、链表的应用
         一个用以创建、增加、删除和遍历一个双向链表的Linux内核模块

点击(此处)折叠或打开

  1. #include <linux/kernel.h>
  2. #include <linux/module.h>
  3. #include <linux/slab.h>
  4. #include <linux/list.h>
  5. MODULE_LICENCE("GPL");
  6. MODULE_AUTHOR("LUOTAIJIA");
  7. #define N 10
  8. struct numlist {
  9.     int num;
  10.     struct list_head list;
  11. };
  12. struct numlist numhead;
  13. static int __init doublelist_init(void)
  14. {
  15.     //初始化头结点
  16.     struct numlist * listnode//每次申请链表结点时所用的指针
  17.     struct list_head * pos;
  18.     struct numlist * p;
  19.     int i;
  20.     printk("doublelist is starting...\n");
  21.     INIT_LIST_HEAD(&numhead.list);
  22.     /
  23.      * static inline void INIT_LIST_HEAD(struct list_head *list)
  24.      {
  25.      * list->next = list;
  26.      * list->prev = list;
  27.      }
  28.      */
  29.     //建立N个结点,依次加入到链表当中
  30.     for (i=0; i<N; i++{
  31.         listnode (struct numlist *)kmalloc(sizeof(struct numlist), GFP_KERNEL);
  32.         //void *kmalloc(size_t sizeint flages
  33.         //分配内存,size 要分配内存大小,flags 内存类型
  34.         listnode->num = i+1;
  35.         list_add_tail(&listnode->list&numhead.list);
  36.         printk("Node %d has added to the doublelist...\n", i+1);
  37.     }
  38.     //遍历链表
  39.     i = 1;
  40.     list_for_each(pos&numhead.list{
  41.         p = list_entry(pos, struct numlist, list);
  42.         printk("Node %d's data: %d\n", i, p->num);
  43.         i++;
  44.     }
  45.     return 0;
  46. }
  47. static void __exit doublelist_exit(void)
  48. {
  49.     struct list_head *pos*n;
  50.     struct numlist *p;
  51.     int i;
  52.     //依次删除N个结点
  53.     i = 1;
  54.     list_for_each_safe(pos, n&numhead.list{
  55.         //为了安全删除结点而进行的遍历
  56.         list_del(pos)//从链表中删除当前结点
  57.         p = list_entry(pos, struct numlist, llist)
  58.         //得到当前数据结点的首地址,即指针
  59.         kfree(p)//释放该数据结点所占空间
  60.         printk("Node %d has removed from the doublelist...\n", i++);
  61.     }
  62.     printk("doublelist is exiting...\n");
  63. }
  64. module_init(doublelist_init);
  65. module_exit(doublelist_exit);
  66.  
 
参考资料:Linux操作系统原理与应用(第2版)    陈莉君、康华 编著



本文转自张昺华-sky博客园博客,原文链接:http://www.cnblogs.com/sky-heaven/p/7130882.html,如需转载请自行联系原作者

目录
打赏
0
0
0
0
64
分享
相关文章
理解Linux操作系统内核中物理设备驱动(phy driver)的功能。
综合来看,物理设备驱动在Linux系统中的作用是至关重要的,它通过与硬件设备的紧密配合,为上层应用提供稳定可靠的通信基础设施。开发一款优秀的物理设备驱动需要开发者具备深厚的硬件知识、熟练的编程技能以及对Linux内核架构的深入理解,以确保驱动程序能在不同的硬件平台和网络条件下都能提供最优的性能。
40 0
Linux内核中的线程和进程实现详解
了解进程和线程如何工作,可以帮助我们更好地编写程序,充分利用多核CPU,实现并行计算,提高系统的响应速度和计算效能。记住,适当平衡进程和线程的使用,既要拥有独立空间的'兄弟',也需要在'家庭'中分享和并行的成员。对于这个世界,现在,你应该有一个全新的认识。
195 67
Linux2.6内核进程调度队列
本篇文章是Linux进程系列中的最后一篇文章,本来是想放在上一篇文章的结尾的,但是想了想还是单独写一篇文章吧,虽然说这部分内容是比较难的,所有一般来说是简单的提及带过的,但是为了让大家对进程有更深的理解与认识,还是看了一些别人的文章,然后学习了学习,然后对此做了总结,尽可能详细的介绍明白。最后推荐一篇文章Linux的进程优先级 NI 和 PR - 简书。
43 0
|
3月前
|
Linux内核中的current机制解析
总的来说,current机制是Linux内核中进程管理的基础,它通过获取当前进程的task_struct结构的地址,可以方便地获取和修改进程的信息。这个机制在内核中的使用非常广泛,对于理解Linux内核的工作原理有着重要的意义。
149 11
Linux 内核源码分析---proc 文件系统
`proc`文件系统是Linux内核中一个灵活而强大的工具,提供了一个与内核数据结构交互的接口。通过本文的分析,我们深入探讨了 `proc`文件系统的实现原理,包括其初始化、文件的创建与操作、动态内容生成等方面。通过对这些内容的理解,开发者可以更好地利用 `proc`文件系统来监控和调试内核,同时也为系统管理提供了便利的工具。
177 16
Linux 主要应用领域的归纳
服务器领域 Linux在服务器领域的应用是其最为广泛和成熟的领域之一。由于其开源、稳定、高效和安全的特性,Linux成为许多企业服务器的首选操作系统。 Web服务器:Linux是Web服务器的理想选择,因为它支持Apache、Nginx等流行的Web服务器软件,这些软件在Linux上运行稳定且性能卓越。Linux服务器可以高效地处理大量并发请求,提供快速、可靠的Web服务。 数据库服务器:Linux也广泛用于数据库服务器,如MySQL、PostgreSQL和Oracle等数据库管理系统在Linux上运行良好。Linux的稳定性和安全性使得它成为存储和管理敏感数据的理想平台。 邮件服务器:Lin
226 5
Intel Linux 内核测试套件-LKVS介绍 | 龙蜥大讲堂104期
《Intel Linux内核测试套件-LKVS介绍》(龙蜥大讲堂104期)主要介绍了LKVS的定义、使用方法、测试范围、典型案例及其优势。LKVS是轻量级、低耦合且高代码覆盖率的测试工具,涵盖20多个硬件和内核属性,已开源并集成到多个社区CICD系统中。课程详细讲解了如何使用LKVS进行CPU、电源管理和安全特性(如TDX、CET)的测试,并展示了其在实际应用中的价值。
146 4
Ubuntu20.04搭建嵌入式linux网络加载内核、设备树和根文件系统
使用上述U-Boot命令配置并启动嵌入式设备。如果配置正确,设备将通过TFTP加载内核和设备树,并通过NFS挂载根文件系统。
355 15
深入探索Linux内核调度器:公平与效率的平衡####
本文通过剖析Linux内核调度器的工作机制,揭示了其在多任务处理环境中如何实现时间片轮转、优先级调整及完全公平调度算法(CFS),以达到既公平又高效地分配CPU资源的目标。通过对比FIFO和RR等传统调度策略,本文展示了Linux调度器如何在复杂的计算场景下优化性能,为系统设计师和开发者提供了宝贵的设计思路。 ####
136 26
深入解析Linux操作系统的内核优化策略
本文旨在探讨Linux操作系统内核的优化策略,包括内核参数调整、内存管理、CPU调度以及文件系统性能提升等方面。通过对这些关键领域的分析,我们可以理解如何有效地提高Linux系统的性能和稳定性,从而为用户提供更加流畅和高效的计算体验。
296 24
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等

登录插画

登录以查看您的控制台资源

管理云资源
状态一览
快捷访问