《LKD3粗读笔记》(6)内核数据结构

`json
{
"article": [
{
"intro": "今天我们来聊聊数据结构中的链表。首先，什么是链表呢？简单概括，链表是一种动态数据结构，它的元素可以在运行时增删，不需要提前预估大小。就像一群小松鼠在树林里跳来跳去，每只小松鼠都可以自由地加入或离开队伍。",
"question": "链表有哪些类型？",
"answer": {
"single": "单向链表，就是你只能顺着找下一个松鼠，不能逆着找。",
"double": "双向链表，就像能双向跳跃的小松鼠，既能顺着找下一个，也能逆着找上一个。"
}
},
{
"question": "什么是环形链表？",
"answer": "环形链表就像是大家都手拉手形成一个圈，头尾相连，没有固定的开头和结尾，就像大家围成一个圈一起玩一样。"
},
{
"question": "链表在Linux内核中是怎么用的？",
"answer": "在Linux内核中，链表被广泛使用，比如进程管理、设备驱动等。它们通过一个叫list_head的结构体把数据结构串联起来，就像一条项链把小珍珠串起来一样。"
},
{
"question": "内核提供的链表操作有什么特别的吗？",
"answer": {
"uniformity": "所有的链表操作方法都统一地接受list_head结构体作为参数，这样设计非常统一和方便。",
"container_of": "特别要提一下container_of宏，它能从链表指针找到包含该链表的父结构体中的任何变量，就像你知道小珍珠在哪条项链上一样。"
}
},
{
"question": "能详细说说container_of宏是怎么工作的吗？",
"answer": {
"explanation": "container_of宏通过已知的结构体成员变量的地址，找到该结构体的起始地址。这个宏的实现有点复杂，但是它的基本思想是通过成员变量的地址减去它在结构体中的偏移量，就能得到结构体的起始地址。"
}
},
{
"conclusion": "通过这篇文章，我们了解了链表的基本概念，以及它在Linux内核中的具体实现和应用。希望大家在阅读后，能对链表有更深入的理解，并能在实际编程中灵活运用。"
}
]
}
`

1、链表

1. 单向链表和双向链表
   这里涉及到了对void关键字的理解：C高级编程——关于void类型的解释
   • 链表的特点
     • 链表是一种存放和操作可变数量元素（常称为结点）的数据结构
     • 与静态数组不同的是，链表所包含的元素都是动态创建并插入链表的，在编译时不必知道具体创建多少个元素。
     • 链表中每个元素创建时间不同，它们在内存中无需占用连续内存区。
   • 简单的单向链表结构

     /*一个链表中的某个结点*/
     struct list_element {void *data; 				/*有效数据*/struct list_element* next;	/*指向后一个元素的指针*/
     }
     

   • 简单的双向链表

     /*一个链表中的某个结点*/
     struct list_element {void *data; 				/*有效数据*/struct list_element* next;	/*指向前一个元素的指针*/struct list_element* prev;	/*指向后一个元素的指针*/
     }
     

2. 环形链表
   • 链表首尾相连。
   • Linux内核的标准链表采用的环形双向链表，因为环形双向链表提供最大的灵活性。
3. 沿链表移动
4. Linux内核中的实现
   1. 链表数据结构

      • Linux内核中链表的实现方式是什么样的？
        它不是将数据结构塞入链表，而是将链表结点塞入数据结构。
        eg：举个小狐狸的例子
        官方提供的链表代码在头文件<linux/list.h>中声明：

        struct list_head{struct list_head* next;struct list_head* prev;
        };
        

        现在，将这个链表结点塞入小狐狸这个数据结构：

        struct fox{unsigned long tail_length; 	/*狐狸尾巴长度*/unsigned long weight;     	/*狐狸重量*/  bool sex;					/*狐狸性别*/struct list_head list;      /*所有fox结构体形成链表*/
        };
        

        那么，整个链表大概就是这个样子（画的真丑）：
        

      • 内核提供的链表操作例程有什么特点，是如何实现的？

        • 链表操作方法统一的特点是：只接受list_head结构作为参数
        • 使用container_of宏可以很方便地从链表指针找到父结构中包含地任何变量。
        • container_of宏要实现什么功能？
          已知结构体type的成员member的地址ptr，求解结构体type的起始地址。
        • container of函数的具体实现？

          #define container_of(ptr, type, member) ({              \\        
          const typeof( ((type *)0)->member ) *__mptr = (ptr);    \\  //自行思考该行的作用       
          (type *)( (char *)__mptr - offsetof(type,member) );})  //type的起始地址 = ptr - size
          

          其中offsetof函数原型为：

          #define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)
          

          详解请看：container of()函数简介、Linux内核中的container_of函数简要介绍、C语言高级用法—typeof()关键字

        • 依靠list_entry()方法，内核提供了创建、操作以及其他链表管理的各种例程。list_entry()方法本质上就是container_of宏的套壳：

          #define list_entry(ptr, type, member) \\
          
          container_of(ptr,<