Chinaunix首页 | 论坛 | 博客
  • 博客访问: 715207
  • 博文数量: 130
  • 博客积分: 10
  • 博客等级: 民兵
  • 技术积分: 2198
  • 用 户 组: 普通用户
  • 注册时间: 2011-11-29 12:48
个人简介

每一个“丑得人神共愤”的泡妞高 手都有一颗坚忍的心,这证明了人类 在绝境中毫不妥协的求生精神,反正丑都丑了,索性放开手脚大干一场,这就叫“无产阶级失去的是锁链,得到的是全世界”

文章分类

全部博文(130)

文章存档

2013年(130)

我的朋友

分类: LINUX

2013-04-19 11:39:31

内核链表

概述

就像许多其他程序一样,操作系统内核经常需要维护数据结构的列表。有时,linux内核中同时存在多个链表的实现代码。为了减少重复代码的数量,内核开发者已经建立了一套标准的双向循环链表。如果你需要操作链表,那么建议你使用这一内核设施。内核链表的好主要体现为两点,一是可扩展性,内核一直都是在发展中的,所以代码都不能写成死代码,要方便修改和追加,内核链表和其他结构集合十分容易;二是封装,将链表常见的操作都进行封装,使用者只关注接口,不需关注实现。当使用这些链表接口时,应该始终牢记这些链表函数不进行任何锁定。如果你的程序有可能试图对同一个链表执行并发操作的话,则有责任实现一个锁方案。

源码

学习内核最好的方法就是阅读源码,我将源码贴在这里,方便大家在遇到不理解或者不赞同的时候考究。源码摘自2.6.34.14版本内核源码的include/linux/list.h文件,文件包含list_head和hlist_head两部分,本文只分析list_head部分。list.zip

链表的使用

内核链表结构定义如下:
  1. struct list_head {
  2.     struct list_head *next, *prev;
  3. };
为了在代码中使用内核链表设施,只需在构成链表的结构里面嵌入一个list_head。如:
  1. struct todo_struct {
  2.         struct list_head list;
  3.         .... other members ....
  4. }
注意list_head的成员prev,next指向的是list_head而不是包含list_head的结构体,我们的链表是通过list_head链起来的。第一次接触内核链表的同学可能会产生这样的疑问:得到list_head的地址有什么用,我们需要操作的是包含list_head的结构体,如何才能得到包含list_head的结构体的指针?这是list_entry将要完成的工作,相关源码如下
  1. #define list_entry(ptr, type, member) \
  2.     container_of(ptr, type, member)

  3. #define container_of(ptr, type, member) ({ \
  4.     const typeof( ((type *)0)->member ) *__mptr = (ptr); \
  5.     (type *)( (char *)__mptr - offsetof(type,member) );})
  6. 注:container_of定义于include/linux/kernel.h中

  7. #ifdef __compiler_offsetof
  8. #define offsetof(TYPE,MEMBER) __compiler_offsetof(TYPE,MEMBER)
  9. #else
  10. #define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)
  11. #endif
  12. 注:offsetof定义于include/linux/stddef.h中
举个例子来说明,我们获得了一个指向list_head的指针p,该list_head包含于todo_struct结构中并且其对应的成员名为list,那么list_entry(p, struct todo_struct, list)将返回该todo_struct的地址。从上面源码可以看出,offsetof计算成员在结构中的偏移,todo_struct的地址的计算方式就是用p的值减去list在todo_struct中的偏移。
list_head使用示例图:

在使用链表时我们通常会定义一个链表头,链表头通常是一个独立的list_head结构,在使用链表前需初始化链表头。从上图可以看出,我们的链表几乎可以说是独立于包含它的结构的,任何保含list_head成员的结构都可以添加到链表中来(当然我们只会将相同的结构组合成一个链表),针对整个链表的插入,删除、和并等操作完全是在list_head上进行的,而链表的遍历也是在list_head上移动。由此,内核有一套通用的专门用于处理链表的函数和宏,我们不必针对每一个链表都写一套操作函数。
下面将列出对链表进行操作的函数和宏(head指向为链表头):

初始化:

LIST_HEAD_INIT(name)
    在编译阶段初始化链表头
LIST_HEAD(name)
    在编译阶段定义并初始化链表头
INIT_LIST_HEAD(struct list_head *head)
    在运行阶段初始化链表头

增加、删除、替换、移动元素:

list_add(struct list_head *new, struct list_head *head)
list_add_tail(struct list_head *new, struct list_head *head)
    将new插入到链表开始/末尾
list_del(struct list_head *entry)
list_del_init(struct list_head *entry)
    从链表中删除entry
list_replace(struct list_head *old, struct list_head *new)
list_replace_init(struct list_head *old, struct list_head *new)
    在链表中用new替换old
list_move(struct list_head *list, struct list_head *head)
list_move_tail(struct list_head *list, struct list_head *head)
    将list从其所在链表删除,再插入到head链表的开始/末尾
list_rotate_left(struct list_head *head)
    将链表第一元素移动到最后

链表判定:

list_is_last(const struct list_head *list, const struct list_head *head)
    判定list为是否链表最后一个元素
list_empty(const struct list_head *head)
list_empty_careful(const struct list_head *head)
    判定链表是否为空
list_is_singular(const struct list_head *head)
    判定链表是否只包含一个元素

合并、分割链表:

list_cut_position(struct list_head *head1, struct list_head *head2, struct list_head *entry)
    将head链表一分为二

list_splice(const struct list_head *head1, struct list_head *head2)
list_splice_init(struct list_head *head1, struct list_head *head2)
    合并两个链表(这是为栈设计的)

list_splice_tail(struct list_head *head1, struct list_head *head2)
list_splice_tail_init(struct list_head *list, struct list_head *head)
    合并两个链表(这是为队列设计的)

访问包含list_head的结构体:

list_entry(entry, type, member)
    将一个list_head结构指针映射回指向包含它的大结构的指针
list_first_entry(head, type, member)
    返回链表第一项(包含list_entry的结构体)

遍历:

list_for_each(pos, head)
list_for_each_safe(pos, n, head)
    顺序遍历链表,遍历过程中,pos指向list_head结构体
list_for_each_prev(pos, head)
list_for_each_prev_safe(pos, n, head)
    逆序遍历链表,遍历过程中,pos指向list_head结构体
list_for_each_entry(pos, head, member)
    顺序遍历链表,遍历过程中,pos指向包含list_head的大结构体
list_for_each_entry_reverse(pos, head, member)
    逆序遍历链表,遍历过程中,pos指向包含list_head的大结构体
list_prepare_entry(pos, head, member)
list_for_each_entry_continue(pos, head, member)
list_for_each_entry_continue_reverse(pos, head, member)
list_for_each_entry_from(pos, head, member)
list_for_each_entry_safe(pos, n, head, member)
list_for_each_entry_safe_continue(pos, n, head, member)
list_for_each_entry_safe_reverse(pos, n, head, member)
原文链接:http://blog.chinaunix.net/uid-26497520-id-3601869.html,看着作者熬夜工作的份上转载请注明出处
阅读(3154) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~