阅读Linux源码，心得：

1.抽象，不要把问题想得复杂，Less Is More!

2.关注函数的参数的类型

1.Linux内核中的双链表结构

Linux内核对双链表的实现(在list.h中)方式与众不同，在链表中并不会包含数据，具体定义如下:

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

为什么不包含数据域？

这体现了Linux内核的抽象的思想

这个结构常常被嵌入到其他结构中使用，比如:

struct my_list{
	void *mydata;
	struct list_head list;
	// list域隐藏了链表的指针特性，以struct list_head为基本对象，
    // 可以对链表进行插入、删除、合并、遍历等操作
};

由该双向链表可以衍生出各种不同的复杂数据结构。

1.1 Linux内核链表的声明、初始化

// 仅初始化链表
#define LIST_HEAD_INIT(name) { &(name), &(name) }
	
// 声明并初始化 
#define LIST_HEAD(name) \
	struct list_head name = LIST_HEAD_INIT(name)

1.2 Linux内核链表之插入

Linux内核中两个插入函数

static inline void list_add() // 在链表头插入，实现了栈功能

static inline void list_add_tail() // 在尾部插入，实现了队列功能

Linux内核又对上述两个函数进行了抽象,编写了static inline void __list_add(struct list_head* new, struct list_head* prev, struct list_head* next)

static inline void __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;
}


static inline void list_add(struct list_head* new, struct list_head* head)
{
    __list_add(new,head,head->next);
}

static inline void list_add_tail()
{
    __list_add(new,head->prev,head);
}

1.3 Linux内核链表之删除

来看Linux内核的设计，请关注函数的参数，为什么要这么设计？

static inline void __list_del(struct list_head*prev, struct list_head* next)
{
    next->prev = prev;
    prev->next = next;
}

static inline void list_del(struct list_head *entry)
{
	__list_del(entry->prev, entry->next);
	entry->next = LIST_POISON1;
	entry->prev = LIST_POISON2;
}

注意:使用Iist_del()时,会将所要删除的节点(假设此时是pos节点)的next和prev指向一个固定的值,所以想要通过pos = pos->next访问下一个链表节点是不可能的,就会导致页错误,因为LIST_POISON1(2)是宏定义的一个不可访问的地址。

1.4 Linux内核链表之遍历

#define __list_for_each(pos, head) \
	for (pos = (head)->next; pos != (head); pos = pos->next)

pos是定义的一个struct list_head结构的指针，head是所要遍历的链表头，如何通过pos找到链表中每个节点的起始位置,从而访问节点中的每个元素?

struct mylist{
	int data;
	struct list_head list_member;
};

2.Linux内核中的哈希表

对比双链表，哈希表有两种节点，一种是hlist_head、另一种是hlist_node

struct hlist_head {
	struct hlist_node *first;
};
struct hlist_node {
	struct hlist_node *next, **pprev;
};