1.初始化
struct list_head{
struct list_head *next, *prev;
}
/*不含数据项的结构体*/
#define LIST_HEAD_INIT(name) {&(name), &(name)}
#define LIST_HEAD \
struct list_head(name) = LIST_HEAD_INIT(name)
/*这个宏可以初始化一个循环链表*/
2.增加结点
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;
}
/*头插法， new为新结点 head为头结点*/
static inline void list_add(struct list_head *new, struct list_head *head)
{
__list_add(new, head, head->next);
}
/*尾插法，new为新结点 head为头结点*/
static inline void list_add_tail(struct list_head *new, struct list_head *head)
{
__list_add(new, head->prev, head);
}
3.删除
/*删除prev和next之间的结点*/
static inline void __list_del(struct list_head * prev, struct list_head * next)
{
next->prev = prev;
prev->next = next;
}
/*删除entry所在链表的entry结点*/
static inline void list_del_entry(struct list_head *entry)
{
__list_del(entry->prev, entry->next);
}
static inline void list_del(struct list_head *entry)
{
__list_del(entry->prev, entry->next);
entry->next = LIST_POISON1;
entry->prev = LIST_POISON2;
}
/*LIST_POISON1和LIST_POISON2这两个宏定义在 /linux/include/linux/poison.h 下：
* #define LIST_POISON1 ((void *) 0x00100100)
* #define LIST_POISON2 ((void *) 0x00200200)
* These are non-NULL pointers that will result in page faults
* under normal circumstances, used to verify that nobody uses
* non-initialized list entries.
*/
4.替换
static inline void list_replace(struct list_head *old,
struct list_head *new)
{
new->next = old->next;
new->next->prev = new;
new->prev = old->prev;
new->prev->next = new;
}
static inline void list_replace_init(struct list_head *old,
struct list_head *new)
{
list_replace(old, new);
INIT_LIST_HEAD(old); /*替换掉的old结点重新初始化*/
}
/*删除掉entry并重新初始化*/
static inline void list_del_init(struct list_head *entry)
{
__list_del_entry(entry);
INIT_LIST_HEAD(entry);
}
/*移除到另外一个list*/
static inline void list_move(struct list_head *list, struct list_head *head)
{
__list_del_entry(list);
list_add(list, head);
}
/*list是不是head链的最后一个？*/
static inline int list_is_last(const struct list_head *list,
const struct list_head *head)
{
return list->next == head;
}
/*链表是否为空*/
static inline int list_empty(const struct list_head *head)
{
return head->next == head;
}
static inline int list_empty_careful(const struct list_head *head)
{
struct list_head *next = head->next;
return (next == head) && (next == head->prev);
}
/*两者都是判断链表是否为空
*第二种方法主要是了应付另外一个cpu同时处理链表而造成的next,prev不一致的情况，但是注释也承认这一保 *障的能力有限，除非其他的cpu的链表只有list_del_init(),否则仍然能保证安全
*/
/*旋转结点,head的next与head本身交换,即把first搬到head的末尾*/
static inline void list_rotate_left(struct list_head *head)
{
struct list_head *first;
if (!list_empty(head)) {
first = head->next;
list_move_tail(first, head);
}
}
/*判断链表是否只有一个结点除过头结点head*/
static inline int list_is_singular(const struct list_head *head)
{
return !list_empty(head) && (head->next == head->prev);
}
链表的宏遍历
阅读(1283) | 评论(5) | 转发(0) |
