struct list_head { struct list_head *next, *prev;
};
#define
LIST_HEAD_INIT(name) { &(name), &(name) }
#define
LIST_HEAD(name) struct list_head name = LIST_HEAD_INIT(name)
static inline int
list_empty(const struct list_head *head) { eturn head->next == head; }
#define
INIT_LIST_HEAD(ptr) do { (ptr)->next = (ptr); (ptr)->prev = (ptr); } while (0)
// 运行时初始化
static inline void
list_add(struct list_head *new, struct list_head *head);
__list_add(new, head, head->next);
static inline void list_add_tail(struct list_head *new, struct list_head *head);
__list_add(new, head->prev, head);
static inline void
__list_add(struct list_head *new, struct list_head *prev, struct list_head *next) {
next->prev = new; //(1) new->next = next; //(2)
new->prev = prev; //(3) prev->next = new; //(4)
}
static inline void
list_del(struct list_head *entry);
被剔除下来的entry,prev、next指针分别被设为LIST_POSITION2和LIST_POSITION1两个特殊值,保证不在链表中的节点项不可访问。对LIST_POSITION1和LIST_POSITION2的访问都将引起页故障。
list_del_init()函数将节点从链表中解下来之后,调用LIST_INIT_HEAD()将节点置为空链状态。
static inline void list_move(struct list_head *list, struct list_head *head);
static inline void
list_move_tail(struct list_head *list, struct list_head *head);
static inline void list_splice(struct list_head *list, struct list_head *head);
static inline void list_splice_init(struct list_head *list, struct list_head *head);
该函数在将list合并到head链表的基础上,调用INIT_LIST_HEAD(list)将list设置为空链。
list_entry(ptr,type,member)宏,其ptr是指向该数据中list_head成员的指针,即存储在链表中的地址值,type是数据项类型,member则是数据项类型定义中list_head成员的变量名。
list_entry
宏作用:通过list_head成员访问到作为它的所有者的节点数据。
#define
list_entry(ptr, type, member) container_of(ptr, type, 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)
typeof(t)
求变量t的类型,gcc扩展。
#define list_for_each(pos, head) \
for (pos = (head)->next, prefetch(pos->next); pos != (head); \
pos = pos->next, prefetch(pos->next))
注意:此宏必要把list_head放在数据结构第一项成员,至此,它的地址也就是结构变量的地址。
#define list_for_each_entry(pos, head, member)
\
for (pos = list_entry((head)->next, typeof(*pos), member);
\
prefetch(pos->member.next), &pos->member != (head);
\
pos = list_entry(pos->member.next, typeof(*pos), member))
与list_for_each()不同,这里的pos是数据项结构指针类型,而不是(struct
list_head *)。
prefetch的含义是告诉cpu那些元素有可能马上就要用到,告诉cpu预取一下,提高速度。
反向遍历链表:list_for_each_prev()和list_for_each_entry_reverse()。
如遍历不是从链表头开始,而是从已知的某个节点pos开始,则用list_for_each_entry_continue(pos,head,member)。
如pos有值,则从pos开始遍历,如无则从链表头开始,专门提供了一个list_prepare_entry(pos,head,member)宏,将它的返回值作为list_for_each_entry_continue()的pos参数,就可满足要求。
list_for_each_safe(pos, n, head)、list_for_each_entry_safe(pos,
n, head, member),要求调用者提供一个与pos同类型的指针n,在for循环中暂存pos下一个节点的地址,避免因pos节点被释放而造成的断链。