Linux内核当中的数据结构之链表

6400阅读 0评论2020-06-18 stolennnxb
分类:LINUX

和很多其他大型项目一样,linux内核实现了一些通用的数据结构,供开发者在开发的过程中重用。今天先来给大家介绍以下linux当中的链表

1. 链表

链表是linux内核当中最简单、最普遍的数据结构。它是一种存放和操作可变数量元素的数据结构,其和静态数组不同的地方在于,它所包含的元素都是动态创建并插入的,在编译时不需要指导具体创建多少个元素,也正是由于这样,链表在内存中不需要占用连续的内存。

通常情况下,我们的链表大概长这样:

点击(此处)折叠或打开

  1. struct list_entry{
  2.     void *data;
  3.     struct list_entry *next;
  4. };
双链表的话就是在结构体当中多了一个prev指针,之后的什么循环链表等都是围绕着指针进行操作

但是,linux内核当中的链表却根上面的结构不一样,它采用的是内嵌式的结构,其定义如下:

点击(此处)折叠或打开

  1. struct list_head {
  2.     struct list_head *next, *prev;
  3. };

要使用这个链表只需要把它嵌入到要使用链表的结构体当中即可,如下:

点击(此处)折叠或打开

  1. struct list_entry{
  2.     /*
  3.      * some other datas
  4.     */
  5.     struct list_head list;
  6. };
遍历链表可以从每一个链表当中的节点开始,也可以从名以上的头节点,这个头节点的相关定义方式如下, 其实就是建立了一个空结构:

点击(此处)折叠或打开

  1. #define LIST_HEAD(name) \
  2.     struct list_head name = LIST_HEAD_INIT(name)
  3. #define (name) { &(name), &(name) } 
整个链表对应的相关api如下:

点击(此处)折叠或打开

  1. void list_add(struct list_head *new, struct list_head *head)
  2. void list_del(struct list_head *entry)
  3. void list_move(struct list_head *list, struct list_head *head)
其中list_move 是将list移动到head后面

关于遍历链表
当时觉得最困扰自己的就是遍历这块,看了好久才回味过来,自己总结如下:按照嵌入式的方式,我们先不管外层,理论上一路next可以遍历完整个链表,可以拿到每个元素中list_head的首地址、next、prev指针,那剩下的问题就转化为:
已知一个结构体的结构,和一个指向其中固定成员的指针,求这个结构体的首地址,其所有遍历汉书都依赖的函数调用链为:list_entry---->container_of---->offsetof

点击(此处)折叠或打开

  1. // include/linux/list.h
  2. /**
  3.  * list_entry - get the struct for this entry
  4.  * @ptr:    the &struct list_head pointer.
  5.  * @type:    the type of the struct this is embedded in.
  6.  * @member:    the name of the list_head within the struct.
  7.  */
  8. #define list_entry(ptr, type, member) \
  9.     container_of(ptr, type, member)



  10. // include/linux/kernel.h
  11. #define container_of(ptr, type, member) ({                \
  12.     void *__mptr = (void *)(ptr);                    \
  13.     BUILD_BUG_ON_MSG(!__same_type(*(ptr), ((type *)0)->member) &&    \
  14.              !__same_type(*(ptr), void),            \
  15.              "pointer type mismatch in container_of()");    \
  16.     ((type *)(__mptr - offsetof(type, member))); })

  17. // include/linux/stddef.h
  18. #ifdef __compiler_offsetof
  19. #define offsetof(TYPE, MEMBER)    __compiler_offsetof(TYPE, MEMBER)
  20. #else
  21. #define offsetof(TYPE, MEMBER)    ((size_t)&((TYPE *)0)->MEMBER)
  22. #endif

以上,就是linux内核当中的链表结构的简介了


上一篇:电脑从按下电源键,到BIOS发生了啥?
下一篇:动态链接共享库以及其函数解析过程