linux內(nèi)核雙向鏈表源碼分析

1. 雙向鏈表定義:

在內(nèi)核include/linux/types.h里定義了雙向鏈表結(jié)構(gòu)體類型:

Struct list_head

{

Struct list_head *next,*prev;

};

2. 鏈表處理

2.1:鏈表初始化:

#define LIST_HEAD_INIT(name) { &(name), &(name) }

#define LIST_HEAD(name)

struct list_head name = LIST_HEAD_INIT(name)

通過LIST_HEAD(list_name)宏申明并初始化

2.2:添加元素:

2.2.1:list_add(struct list_head *new, struct list_head *head)

在現(xiàn)存的head元素之后，緊接著插入new元素

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;

}

static inline void list_add(struct list_head *new, struct list_head *head)

{

__list_add(new, head, head->next);

}

2.2.2：list_add_tail(struct list_head *new, struct list_head *head)

在現(xiàn)存數(shù)據(jù)之前添加數(shù)據(jù)

static inline void list_add_tail(struct list_head *new, struct list_head *head)

{

__list_add(new, head->prev, head);

}

2.3刪除數(shù)據(jù):

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 = LIST_POISON1;

entry->prev = LIST_POISON2;

}

2.4．檢測鏈表是否為空

static inline int list_empty(const struct list_head *head)

{

return head->next == head;

}

2.5. 合并兩個(gè)鏈表

static inline void __list_splice(const struct list_head *list,

struct list_head *prev,

struct list_head *next)

{

struct list_head *first = list->next;

struct list_head *last = list->prev;

first->prev = prev;

prev->next = first;

last->next = next;

next->prev = last;

}

static inline void list_splice(const struct list_head *list,

struct list_head *head)

{

if (!list_empty(list))

__list_splice(list, head, head->next);

}

2.6:查找鏈表元素:

#define list_entry(ptr, type, member)

container_of(ptr, type, member)