*linux中的头文件list.h
在Linux的源码中有一个自己为建立链表而写的链表头文件,以后可以直接调用里面的函数来使用链表。
list.h在linux中的路径为/usr/src/kernels/include/linux。不同的版本可能不一样。
list.h中有两个宏定义:
#define LIST_HEAD_INIT(name) {&(name),&(name)}
#define LIST_HEAD(name) \
struct list_head name=LSIT_HEAD_INIT(name)
其实写成一行就是:
struct list_head name={&(name),&(name)};
也就是表头的建立以及初始化。注意这里的struct_head结构体建立的不是单链表,而是双链表。在这贴出struct list_head的定义:
struct list_head{
struct list_head *next,*prev;
}
INIT_LIST_HEAD()函数的操作和这两个宏定义的操作是一样的。
接下来是_ _list_add()函数,这是把一个新的节点插入链表中。插入的方法用图来表示:
其他的插入函数都是调用该函数来完成。
_ _list_del()函数是用来删除链表中的一个节点。删除的方法很明了。
注意,这里虽然改变了前后节点指针指向的地址,但是中间的节点的指针指向的地址并没有改变,所以这个节点是可以用来做位置记录的。
其他的删除函数同样的是调用这个函数来完成。
list_replace()函数是用新的节点替换掉旧的节点。替换的顺序按图示:
这里被替换掉的节点的空间也没有被释放掉,它的指针指向的地址也没有改变,所以节点可以记录位置。
list_move()函数是把节点取出来,然后在插入到自己想移动的地方。它移动的过程是先用__list_del()函数把节点取出来,但不释放。然后在用list_add()把节点插入想去的地方。
注意,节点的插入有两种方法,一个是头插:list_add(),一个是尾插:list_add_tail(),所以调用函数的时候要看清。
__list_cut_position()函数是把原来的表分割成两个新表。截取出来的表构成新的循环链表。函数操作如图所示:
__list_splice()函数的功能是将两个表整合到一起,成为一个链表。这个函数是为了栈写的,但是感觉上加入一个节点却带进去两个节点,不知道是什么意思。
上边这些函数算是下边的函数,其余的都是通过调用他们来实现的。
list.h中还有哈希表的功能函数。和上边的函数没有什么大的区别,可以对照着搞清他们的操作。
以上就是我对list.h文件的分析,那个__list_splice()希望有大神说明。