Chinaunix首页 | 论坛 | 博客
  • 博客访问: 1048787
  • 博文数量: 326
  • 博客积分: 10135
  • 博客等级: 上将
  • 技术积分: 2490
  • 用 户 组: 普通用户
  • 注册时间: 2006-04-22 23:53
文章分类

全部博文(326)

文章存档

2014年(1)

2012年(4)

2011年(1)

2010年(4)

2009年(41)

2008年(44)

2007年(63)

2006年(168)

我的朋友

分类: LINUX

2008-10-31 11:56:06

操作系统内核经常需要维护数据结构。内核有标准的循环链表、双向链表的实现。在文件中定义了一个list_head类型简单结构;
struct list_head {
    struct list_head *next,*prev;
}
    通用链表的常用用途是将某一个数据结构本身串成链表,或将某些链表与一个数据结构联系起来,这两种请况实质上都是由结构list_head组成链表,只是list_head所“背负”的负载不一样。下面分别举例说明这两种用途。
    以下实例说明了如何将某一个数据结构本身串成链表,并对链表进行操作,同时还说明list_head结构的实现与使用。
    实例:将某一个数据结构本身串成链表。
    (1)加入list_head结构成员。
    假设有一个example_struct结构需连接成链表,因而在其结构里面加上list_head成员,就组成了结构链表,如下:
struct example_struct {
    struct list_head list;
    int priority;
    .../*其他成员*/
}
    在example_struct结构中的list成员,用来将example_struct结构串成链表。可理解为list_head“背负”的负载是example_struct结构。
    (2)创建list_head结构。
    使用前必须申请链表头并用INIT_LIST_HEAD宏初始化链表头。可使用两种方法。
    方法1:
struct list_head example_list;
INIT_LIST_HEAD(&example_list);
    方法2:
LIST_HEAD(example_list);
    其中,这两个宏include/Linux/list.h中定义如下:
#define LIST_HEAD(name) \
    struct list_head name = LIST_HEAD_INIT(name)
#define INIT_LIST_HEAD(ptr) do { \
    (prt)->next = (ptr); (ptr)->prev = (prt); \
} while(0)
    宏定义INIT_LIST_HEAD初始化了链表,即向前、向后的指针都指向链表头。这样,就已初始化了一个example_list的链表头,以后就可以向链表中增加链表元素了。
    (3)链表与用户结构连接。
    list_entry宏将example_list链表与example_struct结构类型连接起来。
    下面这个代码行就是从example_list链表中得到的结点对应的example_struct结构指针,其中ptr是example_list链表中的指针,如ptr=example_list->next。
struct example_struct *node =
    list_entry(ptr,struct example_struct,list);
    在上面代码行中的宏定义list_entry将一个list_head结构指针映射回一个指向结构example_struct的指针,即得到list_head的宿主结构。下面分析这个宏定义(在include/Linux/list.h中):
#define list_entry(prt,type,member) \
    container_of(ptr,type,member)
    list_entry的功能是得到链表中结点的结构,它的参数含义为:
        ptr是链表中的一个struct list_head结构元素指针。
        type是用户定义的结构类型,其中,包含struct list_head结构成员。
        member用户定义结构中的struct list_head结构成员名字。
    在include/Linux/kernel.h中有container_of的定义,参数含义与list_entry中一致,container_of得到list的容器结构,即含有list成员的结构type。container_of的定义如下:
#define container_of(prt,type,member) ({ \
    /*将链表中的元素prt转换成结构type中成员member的类型*/
    const typeof( ((type *)0)->member ) *__mptr = (prt); \
    /*__mptr减去member成员偏移地址正好是type结构地址*/
    (type *) ( (char *)__mptr - offsetof(type,member) );})
    在include/Linux/stddef.h中有宏offsetof的定义,列出如下:
#define offsetof(TYPE,MEMBER) ((size_t) &((TYPE *)0)->MEMBER)
    offsetof宏对于上述示例的展开及分析是:&((struct example_struct *)0)->list 表示当结构example_struct正好在地址0上时其成员list的地址,即成员位移。
    (4)遍历链表
    下面使用list_entry宏遍历链表得到链表指针,再从链表指针映射回对应结构example_struct的指针。然后,对其成员priority进行操作。函数example_add_entry的功能是给链表加入新的结构成员。
void example_add_entry(struct example_struct *new)
{
    struct list_head *ptr;
    struct example_struct *entry;
    /*遍历链表*/
    for (prt=exmple_list.next; ptr != &exmple_list; prt = prt->next)
    {
        /*映射回对应结构example_struct的指针*/
        entry = list_entry(ptr,struct todo_struct,list);
        if (entry->priority < new->priority)
        {
            list_add_tail(&new->list,ptr);
            return;
        }
    }
    list_add_tail(&new->list,&exmple_struct)
}
    实例:将某些链表与一个数据结构联系起来。
    函数new_inode 为给定的超级块分配一个新的结点,并将新的结点加到链表inode_in_use和sb->s_inodes中,从而在两个链表中链接了新的结点。 一个是以inode_in_use为链表头的全局的结点链表:一个是超级块结构为链表头的结点链表。
fs/inode.c
extern struct list_head inode_in_use;
struct inode *new_inode(struct super_block *sb)
{
    static unsigned long last_ino;
    struct inode *inode;
    spin_lock_prefetch(&inode_lock);
    inode = alloc_inode(sb);
    if (inode)
    {
        spin_lock(&inode_lock);
        inodes_stat.nr_inodes++;
        /*将inode加到inode_in_use链表中*/
        list_add(&inode->i_list,&inode_in_use);
        list_add(&inode->i_sb_list,&sb->s_inodes); /*将inode加到超级块的节点链表中*/
        inode->i_ino = ++last_ino;
        inode->i_state = 0;
        spin_unlock(&inode_lock);
    }
    return inode;
}
    在include/Linux/list.h中还定义了下面操作链表的函数。
    list_add(struct list_head *new,struct list_head *head); 这个函数在链表头后面添加新的元素。如果是在链表的头部添加元素,就可以用来建立栈。还需要注意的是,head并不一定非得是链表的第一项,如果传递了一 个恰巧位于链表中间某处的list_head结构,新入口会立即排在它的后面。因为Linux链表是循环的,链表头通常与其他入口没有本质区别。
    list_add_tail(struct list_head *new,struct list_head *head);在给定链表头的前面增加一个新的元素,即在链表的末尾添加。可使用list_add_tail建立“先入先出”    队列。
    list_del(struct list_head *entry); 从链表中将给定的入口删除。
    list_empty(struct list_head *head); 如果给定的链表是空的,就返回一个非零值。
    list_splice(struct list_head *list,struct list_head *head);这个函数通过在head的后面插入list来合并两个链表。
阅读(1013) | 评论(0) | 转发(2) |
给主人留下些什么吧!~~