listhead数据结构.doc

1. 双向链表(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_liststruct list_head list;int data;static int ini_list(void)struct my_list *p;int i;for(i=0; ilist, &mylist);在内存中形成如下结构的一个双向链表：+-+| | mylist 99 98 0 | +-+ +-+ +-+ +-+ |+-|next|-|list.next|-|list.next|-.-|list.next|-+|-| |-| |-| |-|+-|prev|-|list.prev|-|list.prev|-.-|list.prev|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) 仍然需要单独