flyonok

统计

留言簿(8)

ACE

book

boost

bsd

c study

c++

code download

codeblock

computer clound

Eclipse

embed system

erlang

ET++

gtk

ic card

java

KDE

libevent

linux

linux--MM

mysql

network education

one card

oracle

pcap relation

php

powerbuilder

python

QT

software config

software test

SQL server

UML

wireless

wxwidgets

陈宾

阅读排行榜

评论排行榜

Sys/queue.h-howto(转载)

引言

链表是最常用的数据结构,而且具有多种变种,比较常见的包括:单链表,双向链表,双向循环俩表,队列。在使用 C 语言编程的时候,一般会使用第三方的函数库提供的链表实现,而使用 C++ 和 Java 等语言的时候则使用标准的函数库提供的链表。

单向与双向链表之间的最大差别是删除元素操作的性能,在单向链表中删除一个元素需要遍历链表,复杂度为 O(n),而在双向链表中则只需要直接删除,复杂度为 O(1)。但是,这只是理论上的结果,实际使用中能否达到 O(1) 性能依赖于链表的实现方法以及使用链表的方法。例如,在 GLib 的双向链表实现中,就提供了两种从链表中删除一个元素的方法:

typedef struct {
gpointer data;
GList 
*next;
GList 
*prev;
} GList;
 
GList
*              g_list_remove                       (GList *list,
gconstpointer data);
GList
*              g_list_remove_link                  (GList *list,
GList 
*llink);

第一个函数从链表中删除包含 data 这个指针的链表元素,这个操作需要首先遍历链表,找到包含这个指针的元素,然后删除,因此依然需要 O(n) 时间;第二个函数直接删除一个链表元素,因此只需要 O(1) 时间。在多数情况下,链表的用户只会保存 data 指针,而不保存链表元素指针,所以多数情况下第一个函数会被使用,这样就降低了删除的效率。

其实操作系统已经为我们提供了优化的链表实现,它避免了上述的性能问题,不过使用起来稍微复杂一点,这些数据结构是作为宏是现在 sys/queue.h 头文件的。

sys/queue.h 的实现与应用

由于 sys/queue.h 提供的链表实现与一般课本上的不同,所以先了解它的实现会更容易理解如何去使用它。这个头文件提供了单链表,双向链表,单向队列,双向队列和双向循环队列,下面只以双向链表为例,其他的从原理上讲都是一样的。

双向链表的实现如下:

/*
* List definitions.
*/
#define    LIST_HEAD(name, type)                        \
struct name {                                \
struct type *lh_first;    /* first element */            \
}
 
#define    LIST_HEAD_INITIALIZER(head)                    \
{ NULL }
 
#define    LIST_ENTRY(type)                        \
struct {                                \
struct type *le_next;    /* next element */            \
struct type **le_prev;    /* address of previous next element */    \
}
 
/*
* List functions.
*/
#define    LIST_INIT(head) do {                        \
(head)
->lh_first = NULL;                    \
while (/*CONSTCOND*/0)
 
#define    LIST_INSERT_AFTER(listelm, elm, field) do {            \
if (((elm)->field.le_next = (listelm)->field.le_next) != NULL)    \
(listelm)
->field.le_next->field.le_prev =        \
&(elm)->field.le_next;                \
(listelm)
->field.le_next = (elm);                \
(elm)
->field.le_prev = &(listelm)->field.le_next;        \
while (/*CONSTCOND*/0)
 
#define    LIST_INSERT_BEFORE(listelm, elm, field) do {            \
(elm)
->field.le_prev = (listelm)->field.le_prev;        \
(elm)
->field.le_next = (listelm);                \
*(listelm)->field.le_prev = (elm);                \
(listelm)
->field.le_prev = &(elm)->field.le_next;        \
while (/*CONSTCOND*/0)
 
#define    LIST_INSERT_HEAD(head, elm, field) do {                \
if (((elm)->field.le_next = (head)->lh_first) != NULL)        \
(head)
->lh_first->field.le_prev = &(elm)->field.le_next;\
(head)
->lh_first = (elm);                    \
(elm)
->field.le_prev = &(head)->lh_first;            \
while (/*CONSTCOND*/0)
 
#define    LIST_REMOVE(elm, field) do {                    \
if ((elm)->field.le_next != NULL)                \
(elm)
->field.le_next->field.le_prev =             \
(elm)
->field.le_prev;                \
*(elm)->field.le_prev = (elm)->field.le_next;            \
while (/*CONSTCOND*/0)
 
#define    LIST_FOREACH(var, head, field)                    \
for ((var) = ((head)->lh_first);                \
(var);                            \
(var) 
= ((var)->field.le_next))
 
/*
* List access methods.
*/
#define    LIST_EMPTY(head)        ((head)->lh_first == NULL)
#define    LIST_FIRST(head)        ((head)->lh_first)
#define    LIST_NEXT(elm, field)        ((elm)->field.le_next)

这种链表实现与上面 GList 的实现的根本区别在于,queue.h 的链表是用户数据结构里面包含链表元素,而 GList 是链表元素包含用户数据结构。也就是说,为了使用 queue.h 提供的链表,用户数据结构 data 必须定义成

struct data {

LIST_ENTRY (data) list_entry;

};

经过宏展开之后,就变成

struct data {

struct {
struct data *le_next;    /* next element */
struct data **le_prev;    /* address of previous next element */
} list_entry;

};

通过仔细分析 queue.h 中的源代码,可以发现链表中相邻的两个用户数据之间形成了右图所示的关系。需要特别注意的是,le_prev 指针指向的是前一个元素的 le_next 指针,而不是前一个元素,所以链表各种操作的实现与我们在课本上学到的也有所不同。

下面简要说明一下各个宏的含义:

  • LIST_HEAD 宏定义一个链表头结构,里面包含一个指向第一个链表元素的指针,name 是头结构的名字,type 是用户数据结构的类型名。在使用这个链表之前,需要 LIST_INIT 宏初始化链表头,注意参数是到链表头结构的指针。
  • 各种链表操作都以到用户数据的指针为参数,还需要提供用户数据结构中链表元素域的名字,例如在上面的例子中,data 结构里面链表元素域为 list_entry。

正是因为链表元素是包含在用户数据结构中的,所以用户只需要提供用户数据的指针就能以 O(1) 的复杂度删除一个元素了,如果一个用户数据结构同时在多个链表中,就需要在用户数据结构里面定义多个链表元素域。事实上,Linux 内核中的链表就是用类似的方法定义的。

下面是一个使用 sys/queue.h 中双向链表的简单例子(修改自 man 文档)

LIST_HEAD(listhead, data) head;
struct data {

LIST_ENTRY(data) list_entry;          
/* List. */

*n1, *n2, *np;
 
LIST_INIT(
&head);                       /* Initialize the list. */
 
n1 
= malloc(sizeof(struct data));      /* Insert at the head. */
LIST_INSERT_HEAD(
&head, n1, list_entry);
 
n2 
= malloc(sizeof(struct data));      /* Insert after. */
LIST_INSERT_AFTER(n1, n2, list_entry);
/* Forward traversal. */
LIST_FOREACH(np, 
&head, list_entry)
np
-> 
 
while (head.lh_first != NULL)           /* Delete. */
LIST_REMOVE(head.lh_first, list_entry);

posted on 2010-09-11 00:23 flyonok 阅读(2856) 评论(0)  编辑 收藏 引用 所属分类: linux


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理