Linux 内核 链表 的简单模拟(1)

时间:2021-07-17 14:52:54

  第零章:扯扯淡

  出一个有意思的题目:用一个宏定义FIND求一个结构体struct里某个变量相对struc的编移量,如

struct student
{
int a; //FIND(struct student,a) 等于0
char b; //FIND(struct student,b)等于4
double c;
};

参考答案:#define FIND(type,member) ((size_t)&((type*)0)->member)

我这样理解(可能不太正确):

(type*)0,0在编译过程中会用一个int临时变量装一下,现在把这个临时变量转化成了指针,指向假想的在地址0处存在的结构体,其实是没有的。

((type*)0)->member就访问这个结构体的变量了,

&((type*)0)->member就取得了这个变量的地址了,因为假想这个结构体放在0地址处嘛,所以这个变量的地址就是相对于结构体的偏移,

(size_t)&((type*)0)->member再把这个地址转化成size_t类型(typedef unsigned int size_t),因为地址是0x00000004这样形式的,转化成无符号整形,即得偏移。

测试如下:

#include <iostream>

#define FIND(type,member) ((size_t)&((type*)0)->member)

struct student
{
int a; //FIND(struct student,a) 等于0
char b; //FIND(struct student,b)等于4
double c;
}; using namespace std; int main(void)
{
cout << sizeof(size_t) << endl;
cout << FIND(struct student, a) << endl << FIND(struct student, b)<<endl<< FIND(struct student, c) << endl;
cin.get();
}

输出为 4 0 4 8

---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

  第一章:普通链表

  正常的的链表不是这样嘛:

/*表示书的结构体*/
struct Book
{
int bkId;
string bkName; struct Book *prev; //指向链表中前一个节点
struct Book *next; //指向链表中后一个节点
};

然后再具体写对struct Book结构体的具体操作,如添加一个节点啊,删除一个啊等等。设想:如果有几十个甚至上百个链表,那不是搞死了嘛!要为每一个特定类型的链表写一个具体的操作,程序员怎么会做这么愚蠢的事情呢?于是就有了帅帅的Linux内核链表管理法。

---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

  第二章:Linux内核链表

  Linux内核链表数据结构如下:(在我的M:\linux-3.14.5\include\linux下types.h文件中)

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

正常的链表是把指向前后节点的指针放到链表节点中,但Linux内核不是这么干的,它把上面的struct list_head塞到数据结构中,这样每一个struct list_head就成为了链表节点,其中next指向下一个struct list_hand,prev指向前一个struct list_hand,这样是不是很帅?但关键是要看它怎么使用。现在来看我的struct Book,如果要弄一个它的链表,只要这样:

struct list_head {
struct list_head *next, *prev;
}; /*表示书的结构体*/
struct Book
{
int bkId;
string bkName; struct list_head list; //所有的Book结构体形成链表
};

我这是在抄袭哈!最关键的是要看到底怎么才能组成链表以及到底怎么样才能操作链表。

---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

  第三章:Linux内核链表创建与初始化

  

  创建一个链表也就是创建一个链表头,这个头也是一个struct list_head,源代码有些宏就省去了。(在我的M:\linux-3.14.5\include\linux下list.h文件中)

/*初始化链表*/
static inline void INIT_LIST_HEAD(struct list_head *list)
{
list->next = list;
list->prev = list;
}

其实就是让头的前后指针都指向自己啦。目前我的代码如下:

#include <string>

using std::string;

/*链表节点*/
struct list_head {
struct list_head *next, *prev;
}; /*表示书的结构体*/
struct Book
{
int bkId;
string bkName;
struct list_head list; //所有的Book结构体形成链表
}; /*初始化链表*/
static inline void INIT_LIST_HEAD(struct list_head *list)
{
list->next = list;
list->prev = list;
}

myHead.h

#include <iostream>
#include "myList.h" using namespace std; int main(void)
{
struct list_head MyBkList; //创建我的链表头
INIT_LIST_HEAD(&MyBkList); //初始化这个链表 cin.get();
}

main.cpp

---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

  第四章:Linux内核链表插入

  (1)插入节点

  上面只是建立了一个空链表,现在要插入数据了。

  内核提供了把一个新struct list_head节点插入到两个节点之间的方法:

/*
* Insert a new entry between two known consecutive entries.
*
* This is only for internal list manipulation where we know
* the prev/next entries already!
*/
static inline void __list_add(struct list_head *new1,struct list_head * prev,struct list_head * next)
{
next->prev = new1;
new1->next = next;
new1->prev = prev;
prev->next = new1;
}

这里很抱歉啊,我的是C++项目,new是语言的关键词,所以把new换成了new1,内核源代码中上面的都是new。这个函数是其他插入函数都要调用的,其实就是提取了前插、后插的共同点啦,这个真美!

  (2)尾插节点

/**
* list_add_tail - add a new entry
* @new: new entry to be added
* @head: list head to add it before
*
* Insert a new entry before the specified head.
* This is useful for implementing queues.
*/
static inline void list_add_tail(struct list_head *new, struct list_head *head)
{
__list_add(new, head->prev, head);
}

尾插这个方法其实就是在head节点之前插入一个节点啦,最终调用__list_add(new, head->prev, head);表明是在head前一个节点和head节点之间插入一个节点。

  设想:刚开始只有一个链表头结点struct list_head head,head的前后都是指向自己的,现在调用 list_add_tail(struct list_head *new, struct list_head *head),即__list_add(new, head->prev, head);链表成了两个节点,并且都是各自的相互指向对方:

Linux 内核 链表 的简单模拟(1)

因为这是个双向链表,可以看做new1加到了head后面。再调用一个这个函数 list_add_tail(struct list_head *new, struct list_head *head):

Linux 内核 链表 的简单模拟(1)

所以可以看做:把head当队头,每次修改的都是head的prev指针,每次都在队尾添加,相当于队列啦!现在代码是:

#include <iostream>
#include "myList.h" using namespace std; int main(void)
{
struct list_head MyBkList; //创建我的链表头
INIT_LIST_HEAD(&MyBkList); //初始化这个链表 /*创建新书结构体*/
struct Book bk1;
bk1.bkId = ;
bk1.bkName = "book1"; list_add_tail(&bk1.list, &MyBkList); //把新书1加到头结点MyBkList后面 struct Book bk2;
bk2.bkId = ;
bk2.bkName = "book2"; list_add_tail(&bk2.list,&MyBkList); //把书2加到bk1与MyBkList之间,把MyBkList看做头,则为MyBkList->bk1->bk2(按照节点next指针,MyBkList的next指针是没有变的,MyBkList的prev指针变了) cin.get();
}

链表添加了2节点

  (3)头插

  内核还有个头插,相当于每次都插在了head的后面了,即每次都修改了head的next指针,每次都在前面插,相当于栈啦!和上面的基本差不多,不多写了。

/**
* list_add - add a new entry
* @new: new entry to be added
* @head: list head to add it after
*
* Insert a new entry after the specified head.
* This is good for implementing stacks.
*/
static inline void list_add(struct list_head *new, struct list_head *head)
{
__list_add(new, head, head->next);
}

其实这个更好理解,每次都在head节点和head节点后面一个节点之前插入一个节点。

---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

  第四章:从list_head结构体到包含它的给定数据结构

  上面的都是针对struct list_head操作的,插入也只是把给定结构体的的struct list_head成员传递给函数,但如何才能获得包含struct list_head的结构体呢?毕竟真正要访问的时候我们想访问到我们真正关心的数据。好了,下面一步一步来

  container_of()(在我的M:\linux-3.14.5\include\linux下kernel.h文件中)

/**
* container_of - cast a member of a structure out to the containing structure
* @ptr: the pointer to the member.
* @type: the type of the container struct this is embedded in.
* @member: the name of the member within the struct.
*
*/
#define container_of(ptr, type, member) ({ \
const typeof( ((type *))->member ) *__mptr = (ptr); \
(type *)( (char *)__mptr - offsetof(type,member) );})

它已经描述很清楚,由结构体包含的成员获得包含这个成员的结构体,ptr是指向结构体成员的指针,type是包含给定成员的结构体名称,member是结构体所含指定成员的的在结构体中的名字。

typeof:是g++对c / c++语法的一个扩展,用来静态获取参数类型,在windows下面一直报错,我就迁徙到linux,用g++就ok比如:

int a = 3;

typeof(a) b = 4; // 相当于 int b = 4;

offsetof:如下,是内核源代码定义的宏(在我的M:\linux-3.14.5\include\linux下stddef.h文件中)

#undef offsetof
#ifdef __compiler_offsetof
#define offsetof(TYPE,MEMBER) __compiler_offsetof(TYPE,MEMBER)
#else
#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)
#endif

offsetoff(struct_t, member)宏的作用就是获得成员member在类型struct_t中的偏移量。是不是第零章扯扯淡差不多???

好了,其实理解了第零章的扯扯淡就大概知道怎么做了:获得member相对于type的偏移,再拿给定的member地址减去这个便宜不就是这个结构体的地址吗?这里主要注意一些参数类型,因为这个宏针对各种结构体类型都可以的:

typeof(((type *)0)->member):获得type结构体中member成员名所对应的具体类型,是int呢还是struct list_head呢等等,如果对应我的程序,type是struct Book,member是struct list_head类型的list,则这里获得的是struct list_head;

const typeof(((type *)0)->member) *__mptr = (ptr);看看对应我的程序就懂了,即 const struct list_head  *__mptr = ptr ,就是定义了一个结构体中member所对应的类型的指针,并把ptr赋给它,因为在使用这个宏的时候传递的ptr只是一个大概0xffffffff形式的member的地址,不知道具体类型,member也只是自己起的名字。现在 __mptr是有身份的地址啦!

(type *)((char *)__mptr - offsetof(type, member)):对应我的程序就是那struct Book里面的list变量地址减去struct Book里面list的偏移,得到的就是这个结构体的地址,再强制转换成struct Book类型。搞定!但还是不明白为什么要进行ptr到__mptr的转换......

这里利用编译器技术的小技巧,即先求得结构成员在与结构中的偏移量,然后根据成员变量的地址反过来得出属主结构变量的地址。

下接:Linux 内核 链表 的简单模拟(2)

Linux 内核 链表 的简单模拟(1)的更多相关文章

  1. Linux 内核 链表 的简单模拟(2)

    接上一篇Linux 内核 链表 的简单模拟(1) 第五章:Linux内核链表的遍历 /** * list_for_each - iterate over a list * @pos: the &amp ...

  2. C语言 Linux内核链表(企业级链表)

    //Linux内核链表(企业级链表) #define _CRT_SECURE_NO_WARNINGS #include<stdio.h> #include<stdlib.h> ...

  3. 深入分析 Linux 内核链表--转

    引用地址:http://www.ibm.com/developerworks/cn/linux/kernel/l-chain/index.html 一. 链表数据结构简介 链表是一种常用的组织有序数据 ...

  4. linux内核链表分析

    一.常用的链表和内核链表的区别 1.1  常规链表结构        通常链表数据结构至少应包含两个域:数据域和指针域,数据域用于存储数据,指针域用于建立与下一个节点的联系.按照指针域的组织以及各个节 ...

  5. 深入分析 Linux 内核链表

    转载:http://www.ibm.com/developerworks/cn/linux/kernel/l-chain/   一. 链表数据结构简介 链表是一种常用的组织有序数据的数据结构,它通过指 ...

  6. Linux 内核链表实现和使用&lpar;一阴一阳,太极生两仪~&rpar;

    0. 概述 学习使用一下 linux 内核链表,在实际开发中我们可以高效的使用该链表帮我们做点事, 链表是Linux 内核中常用的最普通的内建数据结构,链表是一种存放和操作可变数据元 素(常称为节点) ...

  7. Linux 内核链表的使用及深入分析【转】

    转自:http://blog.csdn.net/BoArmy/article/details/8652776 1.内核链表和普通链表的区别 内核链表是一个双向链表,但是与普通的双向链表又有所区别.内核 ...

  8. 链表的艺术——Linux内核链表分析

    引言: 链表是数据结构中的重要成员之中的一个.因为其结构简单且动态插入.删除节点用时少的长处,链表在开发中的应用场景许多.仅次于数组(越简单应用越广). 可是.正如其长处一样,链表的缺点也是显而易见的 ...

  9. Linux 内核链表 list&period;h 的使用

    Linux 内核链表 list.h 的使用 C 语言本身并不自带集合(Collection)工具,当我们需要把结构体(struct)实例串联起来时,就需要在结构体内声明指向下一实例的指针,构成所谓的& ...

随机推荐

  1. Mac下python初学之Image库(PIL&rpar;

    Mac下python 使用Image库 安装PIL,下载http://www.pythonware.com/products/pil/ 解压PIL源码包,阅读README知道需要使用python se ...

  2. 40、dom以xml结尾的文件

    1.student.xml文件 <?xml version="1.0" encoding="utf-8" ?> <!-- 1.书写根元素(因为 ...

  3. Jquery属性获取——attr&lpar;&rpar;与prop&lpar;&rpar;

    今天在项目中使用<select></select>下拉菜单时,使用juery操作,使页面加载完菜单默认选中的值为2,我一开始的操作如下: <!--html部分--> ...

  4. ural 1306&period; Sequence Median

    1306. Sequence Median Time limit: 1.0 secondMemory limit: 1 MBLanguage limit: C, C++, Pascal Given a ...

  5. Beginning SDL 2&period;0&lpar;1&rpar; SDL功能简介

    原文链接为 http://wiki.libsdl.org/Introduction. 由于近期整理音视频可视化的技术,发现好久不更新的SDL发布了2.0版本,以前也没有过于关注,这里准备尝试下.了解S ...

  6. C&plus;&plus;11原子操作性能测试

    测试结论是发现C++11原子操作在性能上,比以往用到的InterlockedIncrement或__sync_add_and_fetch性能上慢了1倍左右. 另外补充一点,在对原子变量进行比较的时候, ...

  7. C&plus;&plus;&lowbar;nullptr

    C++_nullptr null 0 nullptr 的区别

  8. Spring【AOP模块】就是这么简单

    前言 到目前为止,已经简单学习了Spring的Core模块.....于是我们就开启了Spring的AOP模块了...在讲解AOP模块之前,首先我们来讲解一下cglib代理.以及怎么手动实现AOP编程 ...

  9. Vue2&period;0的三种常用传值方式、父传子、子传父、非父子组件传值

    参考链接:https://blog.csdn.net/lander_xiong/article/details/79018737

  10. H5离线缓存技术Application Cache

    H5离线缓存技术Application Cache 1.离线缓存技术:是浏览器本身的一种机制 HTML5引入Application Cache(应用程序缓存)技术,离线存储可以将站点的一些文件存储在本 ...