linux内核中一些常用的数据结构和操作

1. 前言 本文介绍linux内核中一些常用的数据结构和操作。2. 双向链表(liST)linux内核中的双向链表通过结构 struct list_head来将各个节点连接起来，此结构会作为链表元素结构中的一个参数：struct list_head {

struct list_head *next, *prev;

};链表头的初始化，注意，结构中的指针为NULL并不是初始化，而是指向自身才是初始化，如果只是按普通情况下的置为NULL，而不是指向自身，系统会崩溃，这是一个容易犯的错误：#define LIST_HEAD_INIT(name) { (nAME), (name) }#define LIST_HEAD(name)

struct list_head name = LIST_HEAD_INIT(name)#define INIT_LIST_HEAD(ptr) do {

(ptr)->next = (ptr); (ptr)->prev = (ptr);

} while (0)最常用的链表操作：插入到链表头:

void list_add(struct list_head *new, struct list_head *head);插入到链表尾:

void list_add_tail(struct list_head *new, struct list_head *head);删除链表节点:

void list_del(struct list_head *entry);将节点移动到另一链表:

void list_move(struct list_head *list, struct list_head *head);将节点移动到链表尾:

void list_move_tail(struct list_head *list,struct list_head *head);判断链表是否为空，返回1为空，0非空

int list_empty(struct list_head *head);把两个链表拼接起来：

void list_splice(struct list_head *list, struct list_head *head);取得节点指针：

#define list_entry(ptr, type, member)

((type *)((char *)(ptr)-(unsigned lONg)(((type *)0)->member)))遍历链表中每个节点：

#define list_for_each(pos, head)

for (pos = (head)->next, prefetch(pos->next); pos != (head);

pos = pos->next, prefetch(pos->next))逆向循环链表中每个节点：

#define list_for_each_prev(pos, head)

for (pos = (head)->prev, prefetch(pos->prev); pos != (head);

pos = pos->prev, prefetch(pos->prev))举例：LISH_HEAD(mylist);struct my_list{

struct list_head list;

int data;

};stATIc int ini_list(void)

{

struct my_list *p;

int i;

for(i=0; i100; i++){

p=kmalloc(sizeof(struct my_list), GFP_KERNEL);

list_add(p->list, mylist);

}

}

在内存中形成如下结构的一个双向链表：+---------------------------------------------------------------+

| |

| mylist 99 98 0 |

| +----+ +---------+ +---------+ +---------+ |

+->|next|--->|list.next|--->|list.next|--->...--->|list.next|---+

|----| |---------| |---------| |---------|

+--|prev|---|list.prev|---|list.prev|---...---|list.prev|--+

| +----+ |---------| |---------| |---------| |

| | data | | data | | data | |

| +---------+ +---------+ +---------+ |

| |

+---------------------------------------------------------------+知道了链表头就能遍历整个链表，如果是用list_add()插入新节点的话，从链表头的next方向看是一个堆栈型。从链表中删除节点很容易：staTIc void del_item(struct my_list *p)

{

list_del(p->list, mylist);

kfree(p);

}最重要的宏是list_entry，这个宏的思路是根据链表元素结构中链表头结构list_head的地址推算出链表元素结构的实际地址：#define list_entry(ptr, type, member)

((type *)((char *)(ptr)-(unsigned long)(((type *)0)->member)))ptr是链表元素结构(如struct my_list)中链表头结构list_head的地址

member是链表元素结构(如struct my_list)中链表头结构list_head参数的名称

type是链表元素结构类型(如struct my_list)计算原理是根据链表头结构list_head的地址减去其在链表元素结构中的偏移位置而得到链表元素结构的地址。例如：static void print_list(void)

{

struct list_head *cur;

struct my_list *p;list_for_each(cur, mylist){

p=list_entry(cur, struct my_list, list);

printk(data=%dn, p->data);

}

}优点：这样就可以用相同的数据处理方式来描述所有双向链表，不用再单独为各个链表编写各种编辑函数。缺点：

1) 链表头中元素置为NULL不是初始化，与普通习惯不同;

2) 仍然需要单独编写各自的删除整个链表的函数，不能统一处理，因为不能保证所有链表元素结构中链表头结构list_head的偏移地址都是相同的，当然如果把链表头结构list_head都作为链表元素结构的第一个参数，就可以用统一的删除整个链表的函数。

3. HASH表HA