Chinaunix首页 | 论坛 | 博客
  • 博客访问: 20442
  • 博文数量: 5
  • 博客积分: 308
  • 博客等级: 二等列兵
  • 技术积分: 40
  • 用 户 组: 普通用户
  • 注册时间: 2010-05-27 12:30
文章分类
文章存档

2012年(4)

2010年(1)

最近访客

分类:

2012-08-10 10:43:28

原文地址:linux内核链表 作者:leon_yu

操作系统内核常需要维护数据结构的链表。Linux 内核已经同时有几个链表实现。为减少复制代码的数量, 内核已经创建了一个标准环形双向链表,并鼓励需要操作链表的人使用这个设施.

使用链表接口时,应当记住列表函数没做加锁。若驱动可能同一个列表并发操作,就必须实现一个锁方案。

为使用链表机制,驱动必须包含文件  ,它定义了一个简单的list_head 类型 结构:

点击(此处)折叠或打开

  1. struct list_head {
  2.     struct list_head *next,*prev;
  3. }

 用于实际代码的链表几乎总是由某种结构类型构成,每个接口描述链表的一项。要在代码中使用链表设施,只要在构成链表的结构里嵌入一个list_head

点击(此处)折叠或打开

  1. struct my_struct {
  2.     struct list_head list;
  3.     int private;//其他特定数据类型    

  4. }

链表头通常是一个独立的list_head结构

在使用链表之前,必须用INIT_LIST_HEAD宏来初始化链表头。

  1. struct list_head my_list;

  2. INIT_LIST_HEAD(&my_list);

也可在编译时用下面宏初始化链表

  1. LIST_HEAD(my_list);

在头文件中声明了下列操作链表函数:

  1. static inline void list_add(struct list_head *new, struct list_head *head)

在链表头后面添加新项---通常在链表头部,这样,可以被用来建栈。注意:head不一定链表名义上的头,链表头本质上与其他项无任何区别。

  1. static inline void list_add_tail(struct list_head *new, struct list_head *head)

在链表头前面添加新项--即在链表的末尾处添加。可用list_add_tail建立FIFO队列

  1. static inline void list_del(struct list_head *entry)

  2. static inline void list_del_init(struct list_head *entry)

删除链表中的给定项,如果该项还可能被重新插入到另一个链表中的话,应该使用list_del_init,它会重新初始化链表的指针。

  1. static inline void list_move(struct list_head *list, struct list_head *head);

  2. static inline void list_move_tail(struct list_head *list, struct list_head *head);

吧给定项移动到链表的开始处,如果要把给定项放到新链表的末尾,使用list_move_tail 

  1. static inline int list_empty(const struct list_head *head);

如果给定的链表为空,返回一个非零值。

  1. static inline void list_splice(struct list_head *list, struct list_head *head);

通过在head之后插入list来合并两个链表。

List_head结构体有利于实现具有类似结构的链表,但调用程序通常对组成链表的大结构更感兴趣,因此定义了一些宏来方便操作大结构体。

点击(此处)折叠或打开

  1. list_entry(struct list_head *ptr,type_of_struct,field_name);
  2. ptr---指向正被使用的struct list_head的指针,
  3. type_of_struct---是包含ptr的结构类型
  4. field_name---是结构体中链表字段的名字
  5. 该宏返回当前所操作的链表项的大结构指针。

struct my_struct * my_ptr =

List_entry(listptr,struct my_struct,list)

这样,遍历链表就很容易了,只需跟随prevnext指针。作为例子,假设我们想让my_struct链表中的项按照优先级降序排列,则增加新项的函数如下:

点击(此处)折叠或打开

  1. struct list_head my_list;

  2. struct my_struct{
  3.     struct list_head list;
  4.     int priority;
  5. } my_list;
  6. void my_add_entry(struct my_struct *new)
  7. {
  8.     struct list_head *ptr;
  9.     struct my_struct * entry;

  10.     for (ptr = my_list.next; ptr != &my_list; ptr = ptr->next){
  11.         entry = list_entry(ptr,struct my_struct,list);
  12.         if (entry->priority < new->priority){
  13.             list_add_tail(&new->list,ptr);
  14.             return ;
  15.         }
  16.     }
  17.     list_add_tail(&new->list,&my_struct)
  18. }

改进版

点击(此处)折叠或打开

  1. void my_add_entry(struct my_struct *new)
  2. {
  3.     struct list_head *ptr;
  4.     struct my_struct *entry;

  5.     list_for_each(ptr,&my_list){
  6.         entry = list_entry(ptr,struct my_struct,list);
  7.         if (entry->priority < new->priority){
  8.             list_add_tail(&new->list,ptr);
  9.             return;
  10.         }
  11.     }
  12.     list_add_tail(&new->list,&my_struct);
  13. }

list_for_each(struct list_head *cursor,struct list_head *list);

创建一个for循环,每当游标指向链表中的下一项时执行一次

list_for_each_prev(struct list_head *cursor,struct list_head *list);

该版本向后遍历

list_for_each_safe(struct list_head *cursor, struct list_head *next,struct list_head *list);

当循环可能会删除链表中的项,就用该版本,它只是简单地在循环的开始出吧链表中的下一项存储在next中,这样如果cursor所指的项被删除也不会造成混乱。

用这两个宏处理链表更容易

  1. list_for_each_entry(type *cursor,struct list_head *list,member);

  2. list_for_each_entry_safe(type *cursor,type *next,struct list_head *list,member);

  3. cursor是所指向包含结构体类型的指针,

  4. member是包含结构体内list_head结构体的名字

  5. 用这两个宏就不用再在循环里地用list_entry了。
阅读(794) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~