易截截图软件、单文件、免安装、纯绿色、仅160KB

Linux内核中的双循环链表

Linux内核中的双循环链表
2006-11-27 19:14
双循环链表传统实现
在传统的双循环链表实现中,如果创建某种数据结构的双循环链表,通常采用的办法是在这个数据结构的类型定义中加入两个(指向该类型对象的)指针next和prev。例如:
typedef struct foo {
    …
    struct foo *prev;
    struct foo *next;
    …
} foo_t;
这里给出了对应的节点结构、空的双循环链表和非空的双循环链表示意图。
Linux内核中双循环链表实现
在linux内核中,有大量的数据结构需要用到双循环链表,例如进程、文件、模块、页面等。若采用双循环链表的传统实现方式,需要为这些数据结构维护各自的链表,并且为每个链表都要设计插入、删除等操作函数。(由于用来维持链表的next和prev指针指向对应类型的对象,因此一种数据结构的链表操作函数不能用于操作其它数据结构的链表。)
在Linux源代码树的include/linux/list.h文件中,采用了一种(数据结构)类型无关的双循环链表实现方式。其思想是将指针prev和next从具体的数据结构中提取处理构成一种通用的"双链表"数据结构list_head,而list_head被作为一个成员嵌入到要拉链的数据结构(被称为宿主数据结构)中。这样,只需要一套通用的链表操作函数就可以将list_head成员作为"连接件",把宿主数据结构链接起来。如下图所示:
在Linux内核中的双循环链表实现方式下:
1. 链表结构作为一个成员嵌入到宿主数据结构内;
2. 可以将链表结构放在宿主结构内的任何地方;
3. 可以为链表结构取任何名字;
4. 宿主结构可以有多个链表结构。
下面我们将基于Linux 2.4.21分析Linux内核双循环链表的实现及应用。
声明和初始化
链表结构定义如下:
struct list_head {
    struct list_head *next, *prev;
};
我们可以用struct list_head声明一个链表节点。需要注意的是,Linux 的每个双循环链表都有一个链表头,链表头也是一个节点,只不过它不嵌入到宿主数据结构中,即不能利用链表头定位到对应的宿主结构。
我们可以调用INIT_LIST_HEAD()宏初始化链表节点,将next和prev指针都指向其自身。如果这个节点是链表头,我们就构造了一个空的双循环链表。
#define INIT_LIST_HEAD(ptr) do { \
    (ptr)->next = (ptr); (ptr)->prev = (ptr); \
} while (0)
LIST_HEAD()宏


相关文档:

linux环境下jdk的安装及配置

1.    去http://java.sun.com/j2se/1.4.2/download.html 下载一个Linux Platform的JDK,建议下载RPM自解压格式的(RPM in self-extracting file,j2sdk-1_4_2_06-linux-i586-rpm.bin);
2.    上载到Linux服务器上,在shell下执行命令:
[root@LinuxServer rpm]# chmod 755 j2s ......

Linux中通过locale来设置字符集


在Linux
中通过locale
来设置程序运行的不同语言环境,locale
由ANSI C
提供支持。locale
的命名规则为<
语言>_<
地区>.<
字符集编码>
,如zh_CN.UTF-8
,zh
代表中文,CN
代表大陆地区,UTF-8
表示字符集。在locale
环境中,有一组变量,代表国际化环境中的不同设置:
1.  & ......

Linux中Makefile介绍

 Linux Makefile文件的介绍
1.   Makefile介绍
    注意是“Makefile”,第一个字母大写,其余的都是小写。Makefile关系到了整个工程的编译规则,一个工程中的源文件不计数,其按类型、功能、模块分别放在若干个目录中,Makefile定义了一系列的规则来指定,哪些文件需要先编译, ......

用devhelp查看linux下的开发文档

在找GTK的开发文档,发现在 /usr/share/doc/libgtk2.0-doc/里有个 tutorial的目录,里边有个gtk-tutorial.devhelp的文件,于是试试有没有devhelp这个工具,原来真的有,而且已经安装过了!
于是用它来打开这个开发文档,非常好用。而且里边还有其他库的帮助文档呢! ......

linux 下编辑 vi /etc/bash.bashrc

通过编辑linux的/etc/bash.bashrc文件来快速定位各个目录
alias mysqlw="mysql -uroot -p123456"
alias usr="cd /usr/local"
alias src="cd /usr/src"
alias sphinx="cd /usr/local/sphinx"
alias apahce="cd /usr/local/apache"
alias home="cd /home/data/dev_test_com"
alias php="/usr/local/php5/bin/php" ......
© 2009 ej38.com All Rights Reserved. 关于E健网联系我们 | 站点地图 | 赣ICP备09004571号