当前位置:   article > 正文

linux——list.h

list.h

Linux内核中,为了提供统一的链表操作,减少结构体的额外开支,提供了 list.h 文件,绝对路径为 /usr/src/kernels/include/linux/list.h。

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)};    
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6

另外,INIT_LIST_HEAD() 操作和上述宏定义相同。

list_head 结构体声明如下:

struct list_head {
	struct list_head *next,*prev;	// 双链表结构
}
  • 1
  • 2
  • 3

链表操作如下:

_ _list_add(),将新的节点插入链表中,其他插入接口都间接调用该接口来完成。插入的过程如下图:
插入的顺序

_ _list_del,删除链表中的某一个节点,其他的删除函数调用该函数完成。删除的的过程如下图:
删除的顺序
注意,删除操作虽然改变了前后节点的指针指向,但是被删除节点的指针指向并未改变,因此该节点可用做位置记录。

list_replace(),将新的节点替换掉旧的节点。替换的顺序如图所示:
替换的顺序
被替换掉的节点没有被释放,且指针指向也没有改变,因此可用作位置记录。

list_move(),是将节点取出后,再插入到指定的位置。移动的过程如下:

先用 __list_del() 将节点取出。然后再用 list_add() 将节点插入指定位置。关于节点的插入,提供了两种形式,一种是头插:list_add();另一种是尾插:list_add_tail()。

__list_cut_position(),将链表分割成两个链表。函数操作如图所示:
一分为二的顺序

__list_splice() 则是将两个链表合并成一个链表。

关于链表的遍历,内核提供了list_for_each_entry()来遍历链表中的元素。

#define list_for_each_entry(pos, head, member)				\
	for (pos = list_first_entry(head, typeof(*pos), member);	\
	     &pos->member != (head);					\
	     pos = list_next_entry(pos, member))

#define list_first_entry(ptr, type, member) \
	list_entry((ptr)->next, type, member)

#define list_next_entry(pos, member) \
	list_entry((pos)->member.next, typeof(*(pos)), member)

#define list_entry(ptr, type, member) \
	container_of(ptr, type, member)

#define container_of(ptr, type, member) ({				\
	void *__mptr = (void *)(ptr);					\
	BUILD_BUG_ON_MSG(!__same_type(*(ptr), ((type *)0)->member) &&	\
			 !__same_type(*(ptr), void),			\
			 "pointer type mismatch in container_of()");	\
	((type *)(__mptr - offsetof(type, member))); })

#define offsetof(TYPE, MEMBER)	((size_t)&((TYPE *)0)->MEMBER)
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22

分析 container_of 函数,container_of 函数返回了一个地址。offsetof 函数主要返回结构体中某一成员的相对偏移量。随后,利用成员当前实际的地址减去偏移量,便可以获得当前结构体的首地址。整个计算如下图所示:

|--------struct AAA--------|--- ptr - offsetof(TYPE, MEMBER)
|                          | |  offsetof(TYPE, MEMBER)
|              			   | |
|--struct list_head *head--|--- ptr
|                          |
|--------------------------|
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6

按照上述的计算过程,便可遍历链表中所关联的结构体对象。

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/羊村懒王/article/detail/128116
推荐阅读
相关标签
  

闽ICP备14008679号