Chinaunix首页 | 论坛 | 博客
  • 博客访问: 1019762
  • 博文数量: 297
  • 博客积分: 11721
  • 博客等级: 上将
  • 技术积分: 3431
  • 用 户 组: 普通用户
  • 注册时间: 2009-05-25 10:21
文章分类

全部博文(297)

文章存档

2016年(9)

2011年(71)

2010年(137)

2009年(80)

分类: LINUX

2011-07-04 15:38:21

List_Head

操作系统内核经常需要维护数据结构。内核有标准的循环链表、双向链表的实现。在文件中定义了一个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 { /

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

} while (0)

 

宏定义INIT_LIST_HEAD初始化了链表头,即向前、向后的指针都指向链表头。这样,就已初始化了一个example_list的链表头,以后就可以向链表中增加链表元素了。

3)链表与用户结构连接。

list_entry宏将exmplelist链表与exmple_struct结构类型连接起来。

有两项链表的链表头

List_entry宏的效果

list_head的定制结构

next

prev

list_head结构

空链表

中的链表

下面这个代码行就是从examplelist链表中得到节点对应的example_struct结构指针,其中ptrexamplelist链表中的指针,如ptr = examplelist->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(ptr, 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成员的结构typecontainer_of的定义如下:

#define container_of(ptr, type, member) ({                  /

    //将链表中的元素ptr转换成结构type中成员member的类型

        const typeof( ((type *)0)->member ) *__mptr = (ptr);     /

    //__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 (ptr = exmple_list.next; ptr != &exmple_list; ptr = ptr->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_usesb->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;

……

 

……

 

……

 

s_inodes

 

 

i_sb_list

 

 

i_sb_list

 

 

list_head

 

 

list_head

 

 

list_head

 

 

*next

 

 

*prev

 

 

*prev

 

 

*prev

 

 

*next

 

 

*next

 

 

Super_block

 

inode

 

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来合并两个链表。

 

Hlist

include/Linux/list.h中有list链表与hlist哈希链表结构的定义,下面都列出它们的定义,可以对比一下:

 

struct list_head {struct list_head *next, *prev; };

struct hlist_head { struct hlist_node *first; };

struct hlist_node { struct hlist_node *next, **pprev; };

 

 

双头(nextprev)的双链表对于Hash表来说过于浪费,因而另行设计了一套Hash表专用的hlist数据结构——单指针表头双循环链表,hlist的表头仅有一个指向首节点的指针,而没有指向尾节点的指针,这样在可能是海量的Hash表中存储的表头就能减少一半的空间消耗。

pprev因为hlist不是一个完整的循环链表而不得不使用。在list中,表头和节点是同一个数据结构,直接用prev没问题;在hlist中,表头没有prev,也没有next,只有一个first。为了能统一地修改表头的first指针,即表头的first指针必须修改指向新插入的节点,hlist就设计了pprevhlist节点的pprev不再是指向前一个节点的指针,而是指向前一个节点(可能是表头)中的next(对于表头则是first)指针(struct list_head **pprev),从而在表头插入的操作可以通过一致的“*(node->pprev)”访问和修改前节点的next(或first)指针。

下面是hlist中常用的几个宏:

 

#define HLIST_HEAD_INIT { .first = NULL }

#define HLIST_HEAD(name) struct hlist_head name = {  .first = NULL }

#define INIT_HLIST_HEAD(ptr) ((ptr)->first = NULL)

#define INIT_HLIST_NODE(ptr) ((ptr)->next = NULL, (ptr)->pprev = NULL)

 

下面只列出hlist_add_before操作函数,其他hlist链表操作函数操作方法类似。这个函数中的参数next不能为空。它在next前面加入了n节点。函数的实现与list中对应函数类似。

 

static inline void hlist_add_before(struct hlist_node *n, struct hlist_node *next)

{

       n->pprev = next->pprev;

       n->next = next;

       next->pprev = &n->next;

       *(n->pprev) = n;

}

阅读(1336) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~