struct list_head {
struct list_head *next, *prev;
};
#define LIST_HEAD_INIT(name) { &(name), &(name) }
//初始化next , prev 指向自己
#define LIST_HEAD(name) \
struct list_head name = LIST_HEAD_INIT(name)
static inline void INIT_LIST_HEAD(struct list_head *list)
{
list->next = list;
list->prev = list;
}
需要注意的一点是，头结点head是不使用的，这点需要注意。
没有数据域！所以看到这个结构的人第一反应就是我们怎么访问数据？
其实list_head不是拿来单独用的，它一般被嵌到其它结构中，如：
struct file_node{
char c;
struct list_head node;
};
此时list_head就作为它的父结构中的一个成员了，当我们知道list_head的地址（指针）时，我们可以通过list.c提供的宏 list_entry 来获得它的父结构的地址。下面我们来看看list_entry的实现:
list_entry
#define list_entry(ptr,type,member)\
container_of(ptr,type,member)
#define offsetof(TYPE,MEMBER) ((size_t)&((TYPE *)0)->MEMBER)
#define container_of(ptr,type,member) ( {\
const typeof( ((type*)0)->member ) *__mptr=(ptr);\
(type*)( (char*)__mptr - offsetof(type,member) );} )
#define offsetof(TYPE,MEMBER) ( (size_t)& ((TYPE *)0）-> MEMBER )
这里用到一个取址运算符
(TYPE *)0 它表示将 0地址强制转换为TYPE类型，((TYPE *)0）-> MEMBER 也就是从0址址找到TYPE 的成员MEMBER 。
将实参代入
offset( struct file_node, node )；
( (size_t) & ((struct file_node*)0）-> node )；
struct file_node *p = NULL;
&p->node;
即求 p 的成员 node的地址，只不过p 为0地址，从0地址开始算成员node的地址，也就是 成员 node 在结构体 struct file_node中的偏移量。offset宏就是算MEMBER在TYPE中的偏移量的。
#define container_of(ptr,type,member) ( {\
const typeof( ((type*)0)->member ) *__mptr=(ptr);\
(type*)( (char*)__mptr - offsetof(type,member) );} )
这个宏是由两个语句组成，最后container_of返回的结果就是第二个表达式的值。
这里__mptr为中间变量，这就是list_head指针类型，它被初始化为ptr的值，而ptr就是当前所求的结构体中list_head节点的地址。为什么要用中间变量，这是考虑到安全性因素，如果传进来一个ptr++，所有ptr++放在一个表达式中会有副作用，像 (p++)+(p++)之类。
(char*)__mptr 之所以要强制类型转化为char是因为地址是以字节为单位的，而char的长度就是一个字节。
container_of的值是两个地址相减，
刚说了__mptr是结构体中list_head节点的地址，offset宏求的是list_head节点MEMBER在结构体TYPE中的偏移量，那么__mptr减去它所在结构体中的偏移量，就是结构体的地址。
所以list_entry(ptr,type,member)宏的功能就是，由结构体成员地址求结构体地址。其中ptr 是所求结构体中list_head成员指针，type是所求结构体类型，member是结构体list_head成员名。
双向链表操作
list_add()
双向链表的插入操作 --
__list_add这个函数, 只能是用于知道前后结点, 插入在这两个中间.
static inline void __list_add(struct list_head *new,
struct list_head *prev,
struct list_head *next)
{
next->prev = new;
new->next = next;
new->prev = prev;
prev->next = new;
}
list_add() 这个就是将新添加的链表放在new这里. 要注意的是, new必须是list_head的结构, head是头部, head->next就是下一个, 那么这个函数的用法就是, 将新元素, 放到了链表的头端.
static inline void list_add(struct list_head *new, struct list_head *head)
{
__list_add(new, head, head->next);
}
添加到尾部, 就是使用head->prev, 然后head作为下一个.
static inline void list_add_tail(struct list_head *new, struct list_head *head)
{
__list_add(new, head->prev, head);
}
list_del()
从list中删除结点——
static inline void __list_del(struct list_head *prev, struct list_head *next)
{
next->prev = prev;
prev->next = next;
}
删除一个链表的尸体, 只要把前和后相连接起来就好了. 这里也是只用于知道内部的结点的时候才能用
static inline void list_del(struct list_head *entry)
{
__list_del(entry->prev, entry->next);
entry->next = (void *) 0;
entry->prev = (void *) 0;
}
list_empty()
判断链表是否为空（如果双向链表head为空则返回真，否则为假）—
list_for_each()
list_for_each_safe()
因此之遍历链表不删除结点时，可以使用list_for_each()，而当由删除结点操作时，则要使用list_for_each_safe()。
#define list_for_each(pos, head) \
for (pos = (head)->next; pos != (head); pos = pos->next)
#define list_for_each_safe(pos, n, head) \
for (pos = (head)->next, n = pos->next; pos != (head); \
pos = n, n = pos->next)
你能够在循环结构里面安全的删除所遍历的元素
链表是在你的数据项里面的一个成员.
你可以将struct list_head 这个结构体放在任何地方
你可以将struct list_head 变量命名为任意的名字
你可以有多个list
struct file_node{
char c;
struct list_head node;
};
struct file_node mylist;
INIT_LIST_HEAD(&mylist.node);
tmp= (struct file_node *)malloc(sizeof(struct file_node));
list_add(&(tmp->node), &(mylist.node));
list_for_each(pos, &mylist.node){
tmp= list_entry(pos, struct file_node, node);
printf("c= %d \n", tmp->c);
}
clipboard.png
clipboard1.png
clipboard2.png
网友评论