0. 概述
学习使用一下 linux 内核链表，在实际开发中我们可以高效的使用该链表帮我们做点事，
链表是Linux 内核中常用的最普通的内建数据结构，链表是一种存放和操作可变数据元
素(常称为节点)的数据结构，链表和静态的数组不同之处在于，它所包含的元素都是动
态创建插入链表的，在编译时不必知道具体需要创建多少个元素。 另外也因为链表中
每个元素的创建时间各不相同，所以它们在内存中无须占用连续内存区，正是因为元素
不连续存放，所以各元素需要通过某种方式被连接在一起，于是每个元素都包含一个指
向下一个元素的指针，当有元素加入链表或从链表中删除元素时，简单调整指向下一个
节点的指针就可以了。
Linux 内核链表采用双向循环链表形式实现， 它的经典在于和普通的链表实现方式相比
可谓独树一帜， 我们普通的一个数据(比如一个 struct) 通过在内部添加一个该数据类型
的next或previous指针，才能串联在链表中， Linux 内核方式与众不同，它不是将数据
塞入链表，而是将链表节点塞入数据结构。
// 普通链表节点 - 将数据类型的指针嵌在里面实现串联
typedef int data_t;
typedef struct Node* PNode; typedef struct Node {
data_t value;
PNode next;
PNode prev
}Node; // 使用内核链表
struct person {
int age;
char name[];
struct list_head list; // 将链表内嵌在数据结构中
};
过去，内核中有许多链表的实现，该选一个即简单、 又高效的链表来一统江湖，在2.1内
核开发系列中首次引入了官方内核链表实现，从此内核中的所有链表现在都用官方的链表
实现了，OK 预热就到这里，这一段话选自<LINUX 内核设计与实现> O ^_^ O
1. 两个牛逼的宏（开胃甜点~）
1.1 offsetof 宏
testOffsetof.c 测试代码
#include <stdio.h> // offsetof 宏
/*
图解 TYPE代表整个结构体 |-----|------|
| | |
|TYPE |------|
| |MEMBER|---> TYPE 中的某一个成员
| |------|
| | |
|-----|------| 说明：获得结构体(TYPE)的变量成员(MEMBER)在此结构体中的偏移量 1. ((TYPE *)0) 将0转型为TYPE类型指针,即TYPE类型的指针第地址是0
2. ((TYPE *)0)->MEMBER 访问结构中的数据成员
3. &(((TYPE *)0)->MEMBER) 取出成员的地址, 由于TYPE的地址是0,这里获取到的地址
就是相对MEMBER在TYEP中的偏移量
4. (size_t)(&(((TYPE *)0)->MEMBER)) 结果转换类型,对于32位系统, size_t是unsigned int
对于64位系统,size_t是unsigned long类型 TYPE是结构体，它代表"整体";而MEMBER是成员,它是整体中某一部分。
将offsetof看作一个数学问题看待,问题就相当简单了:已知'整体'和'整体中一部分'，
而计算该部分在整体中的偏移 */
#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER) /*
struct student 是4字节对齐 ------------|
| name |
|-----------|<----- 12
| age |
|-----------|<----- 8
| id |
|-----------|<----- 4
| gender |
|-----------|<----- 0
*/ struct student {
char gender;
int id;
int age;
char name[];
}; int main()
{
int gender_offset, id_offset, age_offset, name_offset; gender_offset = offsetof(struct student, gender);
id_offset = offsetof(struct student, id);
age_offset = offsetof(struct student, age);
name_offset = offsetof(struct student, name); printf("gender_offset = %d\n", gender_offset); //
printf("id_offset = %d\n", id_offset); //
printf("age_offset = %d\n", age_offset); //
printf("name_offset = %d\n", name_offset); // struct student zhao;
printf("sizeof zhao = [%d]\n", sizeof(zhao)); // 32个字节 return ;
}
1.2 container_of 宏
testContainer_of.c 测试代码
#include <stdio.h>
#include <string.h>
#include <stdlib.h> /*
container_of 宏 定义：
#define container_of(ptr, type, member) ({ \
const typeof( ((type *)0)->member )*__mptr = (ptr); \
(type *)( (char *)__mptr - offsetof(type,member));}) 说明：
根据"结构体(type)变量"中的"成员变量(member)的指针(ptr)"来
获取指向整个结构体变量的指针。 1. typeof(((type *)0)->member) 取出member成员的变量类型 2. const typeof(((type *)0)->member)*__mptr = (ptr) 定义
变量__mptr指针,并将ptr赋值给__mptr,经过这一步, __mptr
为member数据类型的常量指针,其指向ptr所指向的地址。 3. (char *)__mptr 将__mptr转换为字符型指针。 4. offsetof(type,member) 就是获取"member"成员在结构体"type"
中的偏移量。 5. ((char *)__mptr - offsetof(type,member)) 就是用来获取
"结构体type"的指针的起始地址(为cha *型指针) 6. (type *)((char *)__mptr - offsetof(type, member)) 就是
将"char *"类型的结构体type的指针转换为"type *"类型的
结构体type 的指针。 */ /* offsetof 宏
*
* 获取结构体(TYPE)的变量成员(MEMBER)在此结构体中的偏移量
*
*/
#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER) /* container_of 宏
*
* 根据结构体(type)变量中的成员变量(member)的指针(ptr),来获取
* 指向整个结构体变量的指针
*/
#define container_of(ptr, type, member) ({ \
const typeof( ((type *))->member) *__mptr = (ptr); \
(type *)( (char *)__mptr - offsetof(type,member)); }) struct student {
char gender;
int id;
int age;
char name[];
}; int main(void)
{
struct student stu;
struct student *pstu; stu.gender = '';
stu.id = ;
stu.age = ;
strcpy(stu.name, "James"); // 根据 'id地址' 获取结构体的地址
// container_of(ptr, type, member)
pstu = container_of(&stu.id, struct student, id); // 根据获取到的结构体student的地址,访问其他成员
printf("gender = %c\n", pstu->gender);
printf("age = %d\n", pstu->age);
printf("name = %s\n", pstu->name); return ;
}
2. Linux 内核链表实现及使用Demo
2.1 内核链表实现 list.h 文件(部分函数，主要在学会怎么用)
#ifndef _LINUX_LIST_H
#define _LINUX_LIST_H /* 双向链表节点*/
struct list_head {
struct list_head *next, *prev;
}; /*
* 初始化节点 -
*
* 设置name节点的前继节点和后继节点都指向name本身
*
* 相当于：
* struct list_head name;
* name->next = &name;
* name->prev = &name;
* 即前驱指针和后继指针都指向自己
*/
#define LIST_HEAD_INIT(name) { &(name), &(name) } /* 定义表头(节点) + 初始化 -
*
* 新建双向循环链表表头name,并设置name的前继节点
* 和后继节点都是指向name本身
*/
#define LIST_HEAD(name) \
struct list_head name = LIST_HEAD_INIT(name) /* 初始化节点 -
*
* 将list节点的前继节点和后继节点都是指向list本身
*/
static inline void INIT_LIST_HEAD(struct list_head *list)
{
list->next = list;
list->prev = list;
} /* 添加节点 -
*
* 将new插入到prev和next之间 在linux中 以'__'开头的函数
* 意味着是内核内部接口，外部不应该调用该接口
*/
static inline __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;
} /* 添加new节点 -
*
* 将new添加到head之后，new称为head的后继节点
*/
static inline void list_add(struct list_head *new, struct list_head *head)
{
__list_add(new, head, head->next);
} /* 添加new节点 -
*
* 将new添加到head之前，即将new添加到双链表的尾部
*/
static inline void list_add_tail(struct list_head *new, struct list_head *head)
{
__list_add(new, head->prev, head);
} /* 从双链表中删除节点 -
*
* 内核的内部接口，作用是从双链表中删除prev和next之间的节点
*/
static inline void __list_del(struct list_head * prev, struct list_head * next)
{
next->prev = prev;
prev->next = next;
} /* 从双链表中删除entry节点 -
*
* 内核对外接口,从链表中删除entry节点
*/
static inline void list_del(struct list_head *entry)
{
__list_del(entry->prev, entry->next);
} /* 从双链表中删除entry节点 -
*
* 在双链表中删除entry节点，内核内部接口
*/
static inline void __list_del_entry(struct list_head *entry)
{
__list_del(entry->prev, entry->next);
} /* 从双链表中删除entry节点 -
*
* 内核对外接口，从双链表中删除entry节点,并将entry节点的前继节点
* 和后继节点都指向entry本身
*/
static inline void list_del_init(struct list_head * entry)
{
__list_del_entry(entry);
INIT_LIST_HEAD(entry);
} /*
* 用new 节点替换old节点 -
*/
static inline void list_replace(struct list_head *old, struct list_head *new)
{
new->next = old->next;
new->next->prev = new;
new->prev = old->prev;
new->prev->next = new;
} /*
* 用new 节点替换old节点 - 将替换的old随即又初始化
*/
static inline void list_replace_init(struct list_head *old,
struct list_head *new)
{
list_replace(old, new);
INIT_LIST_HEAD(old);
} /*
* 判断双链表是否为空 -
*/
static inline list_empty(const struct list_head *head)
{
return head->next == head; // 判读链表头的后继节点是不是头本身
} /* offsetof 宏
*
* 获取'MEMBER'成员在结构体'TYPE'中的偏移量
*/
#define offsetof(TYPE,MEMBER) ((size_t)&((TYPE *)0)->MEMBER) /* container_of 宏
*
* 根据结构体'type'变量中的域成员变量(member)的指针(ptr)
* 来获取指向整个结构体变量的指针
*/
#define container_of(ptr,type,member) ({ \
const typeof( ((type *))->member) *__mptr = (ptr); \
(type *)( (char *)__mptr - offsetof(type,member));}) /*
* 遍历双向循环链表
*
* 通常用于获取节点,而不能用到删除节点的场景
*/
#define list_for_each(pos, head) \
for(pos =(head)->next; pos != (head); pos = pos->next) /*
* 遍历双向循环链表
*
* 通常删除节点的场景
*/
#define list_for_each_safe(pos, n, head) \
for(pos = (head)->next, n = pos->next; pos != (head); \
pos = n, n = pos->next) /*
* 获取节点 -
*
* 调用container_of 宏, 根据结构体(type)变量中的域成员变量(member)
* 的指针(ptr)来获取指向整个结构体变量的指针
*/
#define list_entry(ptr, type, member) \
container_of(ptr, type, member); #endif //_LINUX_LIST_H
2.2 使用内核链表Demo test.c文件
/*
Linux 内核链表使用测试代码
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h> #include "list.h" struct person {
int age;
char name[];
struct list_head list; //将链表嵌入到结构中
}; int main(int argc, char *argv[])
{
struct person *Pperson, *new;
struct person person_head;
struct list_head *pos, *next;
int i; // 初始化双向循环链表头
// INIT_LIST_HEAD(struct list_head *list)
INIT_LIST_HEAD(&person_head.list); // 添加节点
for(i=; i<; i++) {
Pperson = (struct person *)malloc(sizeof(struct person));
Pperson->age = (i+)*;
sprintf(Pperson->name, "%d", i+); // 将节点插入到链表的末尾
// 要插入到头,使用list_add
// list_add(struct list_head *new, struct list_head *head)
// list_add_tail(struct list_head *new, struct list_head *head)
list_add_tail(&(Pperson->list), &(person_head.list));
} // 遍历链表
printf("===== 1st iterator d-link ====\n");
// 判断链表是否为空
// list_empty(const struct list_head *head)
if(!list_empty(&person_head.list)) {
// list_for_each(pos, head)
list_for_each(pos, &person_head.list) {
// list_entry(ptr, type, member)
Pperson = list_entry(pos, struct person, list);
printf("name:%-2s, age:%d\n", Pperson->name, Pperson->age);
}
} // 删除节点为10的节点
printf("==== delete node(age:10) ====\n");
// list_for_each_safe(pos, n, head)
list_for_each_safe(pos, next, &person_head.list) {
Pperson = list_entry(pos, struct person, list);
if(Pperson->age == ) {
// list_del_init(struct list_head * entry)
list_del_init(pos);
free(Pperson);
}
} // 再次遍历链表
printf("==== 2nd iterator d-link ====\n");
list_for_each(pos, &person_head.list) {
Pperson = list_entry(pos, struct person, list);
printf("name:%-2s, age:%d\n", Pperson->name, Pperson->age);
} // 替换节点
printf("==== replace node(age:20) ====\n");
new = (struct person *)malloc(sizeof(struct person));
new->age = ;
list_for_each_safe(pos, next, &person_head.list) {
Pperson = list_entry(pos, struct person, list);
if(Pperson->age == ) {
// list_replace(struct list_head *old, struct list_head *new);
list_replace(&(Pperson->list), &(new->list));
}
} // 再次遍历链表
printf("==== 3rd iterator d-link ====\n");
list_for_each(pos, &person_head.list) {
Pperson = list_entry(pos, struct person, list);
printf("name:%-2s, age:%d\n", Pperson->name, Pperson->age);
} // 释放资源
list_for_each_safe(pos, next, &person_head.list) {
Pperson = list_entry(pos, struct person, list);
list_del_init(pos);
free(Pperson);
} return ;
}
2.3 运行
3. 鸣谢
感谢下面两位博主的分享，祝二位工作开心，期待更多分享~ Thanks again.
http://www.cnblogs.com/skywang12345/p/3562146.html https://blog.csdn.net/viewsky11/article/details/53189372
4. 后记
后天八卦
后天八卦又称文王八卦，是周文王在改造先天八卦而创制的。文王在研究先天
八卦的过程中发现它与实际有不符的地方，于是改变了方位，使其符合自然万
物的变化规律，他在卦中增加了数字九，同时多出了中土的位置。后人在实际
应用中，大多以先天八卦为“体”，后天八卦图为“用”，天干、地支、五行生克等
要素都以后天八卦为依据。
先天八卦之数：
乾为一，兑为二，离为三，震为四，巽为五，坎为六，艮为七，坤为八
后天八卦之数：
坎为一，坤为二，震为三，巽为四，中为五，乾为六，兑为七，艮为八，离为九。