Linux内核源码解析-list.h

开头就说明了这里的 list.h 文件来自 Linux Kernel （ */include/linux/list.h ），只是去除了列表项的硬件预加载部分。

进行宏替换后就是

Note: 没搞懂这里为什么加个 osn 前缀，原本是 list_add ，现在是 osn_list_add 。

可以看到就是个简单的链表节点删除过程，同时把删除节点的前后指针设为无法访问。

删除节点后初始化，前后指针都指向自己

从A链表删除后头插法插入B链表

从A链表删除后尾插法插入B链表

先对 list 判空，非空就把 list 链表除头节点外裁剪到 head 头节点在的链表中。函数不安全， list 节点可以继续访问其他节点。

多了一步 list 重新初始化的过程。

(unsigned long)(&((type *)0)->member))) 将0x0地址强制转换为 type * 类型，然后取 type 中的成员 member 地址，因为起始地址为0，得到的 member 的地址就直接是该成员相对于 type 对象的偏移地址了。

所以该语句的功能是：得到 type 类型对象中 member 成员的地址偏移量。

先将 ptr 强制转换为 char * 类型（因为 char * 类型进行加减的话，加减量为 sizeof(char)*offset ， char 占一个字节空间，这样指针加减的步长就是1个字节，实现加一减一。）

整句话的意思就是：得到指向 type 的指针，已知成员的地址，然后减去这个成员相对于整个结构对象的地址偏移量，得到这个数据对象的地址。

就是从前往后，从后往前的区别

Note: 从head节点开始（不包括head节点！）遍历它的每一个节点！它用n先将下一个要遍历的节点保存起来，防止删除本节点后，无法找到下一个节点，而出现错误！

已知指向某个结构体的指针pos，以及指向它中member成员的指针head，从下一个结构体开始向后遍历这个结构体链

Note: 同理，先保存下一个要遍历的节点！从head下一个节点向后遍历链表。

list.h使用说明

linux内核list.h分析(一)

linux内核list.h分析(二)

【Linux内核数据结构】最为经典的链表list

C语言没有类的概念。C++有现成的List类， #include<list>即可。

如果要自己实现可以参考C++数据结构的书籍，是最基本的练习。

这里实现一个简单的例程，请参考：

#include <iostream>

#include <fstream>

#include <stdlib.h>

#include <string.h>

using namespace std

#include<stdio.h>

#include<string>

#include "math.h"

template<class T>class List{

public:

List() //构造函数

{

pFirst = NULL

}

void Add(T&t) //在Link表头添加新结点

{

if(pFirst == NULL)

{

pFirst = new Node

*(pFirst->pT) = t

}

else

{

Node* pNewNode = new Node

*(pNewNode->pT) = t

pNewNode->pNext = pFirst

pFirst = pNewNode

}

}

void Remove(T&t) //在Link中删除含有特定值的元素

{

Node* pNode = pFirst

if(*(pNode->pT) == t)

{

pFirst = pFirst->pNext

delete pNode

return

}

while(pNode != NULL)

{

Node* pNextNode = pNode->pNext

if(pNextNode!=NULL)

{

if(*(pNextNode->pT) == t)

{

pNode->pNext = pNextNode->pNext

delete pNextNode

return

}

}

else

return//没有相同的

pNode = pNode->pNext

}

}

T* Find(T&t) //查找含有特定值的结点

{

Node* pNode = pFirst

while(pNode != NULL)

{

if(*(pNode->pT) == t)

{

return pNode->pT

}

pNode = pNode->pNext

}

return NULL

}

void PrintList() // 打印输出整个链表

{

if(pFirst == NULL)

{

cout<<"列表为空列表！"<<endl

return

}

Node* pNode = pFirst

while(pNode != NULL)

{

cout<<*(pNode->pT)<<endl

pNode = pNode->pNext

}

}

~List()

{

Node* pNode = pFirst

while(pNode != NULL)

{

Node* pNextNode = pNode->pNext

delete pNode

pNode = pNextNode

}

}

protected:

struct Node{

Node* pNext

T* pT

Node()

{

pNext = NULL

pT = new T

}

~Node()

{

delete pT

}

}

Node *pFirst //链首结点指针

}

class Student

{

public:

char id[20] //学号

char name[20] //姓名

int age //年龄

Student()

{

}

~Student()

{

}

Student(const char* pid, const char* pname, int _age)

{

strcpy(id, pid)

strcpy(name, pname)

age = _age

}

bool operator==(const Student&stu)

{

return strcmp(id, stu.id) == 0 &&strcmp(id, stu.id) == 0 &&age==stu.age

}

Student&operator=(const Student&stu)

{

strcpy(id, stu.id)

strcpy(name, stu.name)

age = stu.age

}

friend ostream&operator<<(ostream &out,const Student&stu)

}

ostream &operator<<(ostream &out,const Student&stu)

{

out<<"id:"<<stu.id<<"\tname:"<<stu.name<<"\tage:"<<stu.age<<endl

}

int main()

{

List<Student>stuList

cout<<"添加学生前："<<endl

stuList.PrintList()

Student stu1("1", "张三", 18)

Student stu2("2", "李四", 18)

Student stu3("3", "王五", 18)

Student stu4("4", "至尊宝", 18)

Student stu5("5", "猪八戒", 18)

Student stu6("6", "唐僧", 18)

Student stu7("7", "沙和尚", 18)

Student stu8("8", "观音", 18)

stuList.Add(stu1)

stuList.Add(stu2)

stuList.Add(stu3)

stuList.Add(stu4)

stuList.Add(stu5)

stuList.Add(stu6)

stuList.Add(stu7)

stuList.Add(stu8)

cout<<"添加学生后："<<endl

stuList.PrintList()

Student stu11("1", "张三", 18)

Student* pStu = stuList.Find(stu11)

cout<<"查找到的同学是："<<*pStu

stuList.Remove(stu11)

cout<<"\n\n删除第一个后："<<endl

stuList.PrintList()

return 0

}

---