在實際的工作中街立，我們可能會經(jīng)常使用鏈表結(jié)構(gòu)來存儲數(shù)據(jù)，特別是嵌入式開發(fā)埠通，經(jīng)常會使用linux內(nèi)核最經(jīng)典的雙向鏈表 list_head赎离。本篇文章詳細(xì)介紹了Linux內(nèi)核的通用鏈表是如何實現(xiàn)的，對于經(jīng)常使用的函數(shù)都給出了詳細(xì)的說明和測試用例端辱，并且移植了Linux內(nèi)核的鏈表結(jié)構(gòu)梁剔，在任意平臺都可以方便的調(diào)用內(nèi)核已經(jīng)寫好的函數(shù)。建議收藏舞蔽，以備不時之需荣病！
@[TOC]
鏈表簡介
??鏈表是一種常用的組織有序數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)，它通過指針將一系列數(shù)據(jù)節(jié)點連接成一條數(shù)據(jù)鏈渗柿，是線性表的一種重要實現(xiàn)方式个盆。相對于數(shù)組脖岛，鏈表具有更好的動態(tài)性，建立鏈表時無需預(yù)先知道數(shù)據(jù)總量颊亮，可以隨機分配空間柴梆，可以高效地在鏈表中的任意位置實時插入或刪除數(shù)據(jù)。
??通常鏈表數(shù)據(jù)結(jié)構(gòu)至少應(yīng)包含兩個域：數(shù)據(jù)域和指針域终惑，數(shù)據(jù)域用于存儲數(shù)據(jù)绍在，指針域用于建立與下一個節(jié)點的聯(lián)系。按照指針域的組織以及各個節(jié)點之間的聯(lián)系形式雹有，鏈表又可以分為單鏈表偿渡、雙鏈表、循環(huán)鏈表等多種類型霸奕，下面分別給出這幾類常見鏈表類型的示意圖：
單鏈表
??單鏈表是最簡單的一類鏈表溜宽，它的特點是僅有一個指針域指向后繼節(jié)點（next），因此铅祸，對單鏈表的遍歷只能從頭至尾（通常是NULL空指針）順序進(jìn)行坑质。
雙鏈表
??通過設(shè)計前驅(qū)和后繼兩個指針域，雙鏈表可以從兩個方向遍歷临梗，這是它區(qū)別于單鏈表的地方涡扼。如果打亂前驅(qū)、后繼的依賴關(guān)系盟庞，就可以構(gòu)成"二叉樹"吃沪；如果再讓首節(jié)點的前驅(qū)指向鏈表尾節(jié)點、尾節(jié)點的后繼指向首節(jié)點什猖，就構(gòu)成了循環(huán)鏈表票彪；如果設(shè)計更多的指針域，就可以構(gòu)成各種復(fù)雜的樹狀數(shù)據(jù)結(jié)構(gòu)不狮。
循環(huán)鏈表
??循環(huán)鏈表的特點是尾節(jié)點的后繼指向首節(jié)點降铸。前面已經(jīng)給出了雙鏈表的示意圖，它的特點是從任意一個節(jié)點出發(fā)摇零，沿兩個方向的任何一個推掸，都能找到鏈表中的任意一個數(shù)據(jù)。如果去掉前驅(qū)指針驻仅，就是單循環(huán)鏈表谅畅。
??關(guān)于鏈表的更詳細(xì)的內(nèi)容可以看這兩篇博客
史上最全單鏈表的增刪改查反轉(zhuǎn)等操作匯總以及5種排序算法
詳解雙向鏈表的基本操作.
Linux內(nèi)核中的鏈表
??上面介紹了普通鏈表的實現(xiàn)方式，可以看到數(shù)據(jù)域都是包裹在節(jié)點指針中的噪服，通過節(jié)點指針訪問下一組數(shù)據(jù)毡泻。但是 Linux內(nèi)核的鏈表實現(xiàn)可以說比較特殊，只有前驅(qū)和后繼指針粘优，而沒有數(shù)據(jù)域仇味。鏈表的頭文件是在include/list.h（Linux2.6內(nèi)核）下呻顽。在實際工作中，也可以將內(nèi)核中的鏈表拷貝出來供我們使用邪铲，就需不要造輪子了芬位。
鏈表的定義
??內(nèi)核鏈表只有前驅(qū)和后繼指針，并不包含數(shù)據(jù)域带到，這個鏈表具備通用性昧碉，使用非常方便。因此可以很容易的將內(nèi)核鏈表結(jié)構(gòu)體包含在任意數(shù)據(jù)的結(jié)構(gòu)體中揽惹，非常容易擴展被饿。我們只需要將鏈表結(jié)構(gòu)體包括在數(shù)據(jù)結(jié)構(gòu)體中就可以。下面看具體的代碼搪搏。
??內(nèi)核鏈表的結(jié)構(gòu)
//鏈表結(jié)構(gòu)
struct list_head
{
struct list_head *prev;
struct list_head *next;
};
??當(dāng)需要用內(nèi)核的鏈表結(jié)構(gòu)時狭握，只需要在數(shù)據(jù)結(jié)構(gòu)體中定義一個struct list_head{}類型的結(jié)構(gòu)體成員對象就可以。這樣疯溺，我們就可以很方便地使用內(nèi)核提供給我們的一組標(biāo)準(zhǔn)接口來對鏈表進(jìn)行各種操作论颅。我們定義一個學(xué)生結(jié)構(gòu)體，里面包含學(xué)號和數(shù)學(xué)成績囱嫩。結(jié)構(gòu)體如下：
struct student
{
struct list_head list;//暫且將鏈表放在結(jié)構(gòu)體的第一位
int ID;
int math;
};
鏈表的初始化
內(nèi)核實現(xiàn)
#define LIST_HEAD_INIT(name) { &(name), &(name) }
#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;
}
說明
??INIT_LIST_HEAD 和LIST_HEAD都可以初始化鏈表恃疯，二者的區(qū)別如下：
??LIST_HEAD（stu_list） 初始化鏈表時會順便創(chuàng)建鏈表對象。
//LIST_HEAD（stu_list）展開如下
struct list_head stu_list= { &(stu_list), &(stu_list) };
??INIT_LIST_HEAD(&stu1.stu_list) 初始化鏈表時需要我們已經(jīng)有了一個鏈表對象stu1_list墨闲。
??`我們可以看到鏈表的初始化其實非常簡單今妄，就是讓鏈表的前驅(qū)和后繼都指向了自己。
舉例
INIT_LIST_HEAD(&stu1.stu_list);
鏈表增加節(jié)點
內(nèi)核實現(xiàn)
/*
* Insert a new entry between two known consecutive entries.
*
* This is only for internal list manipulation where we know
* the prev/next entries already!
*/
#ifndef CONFIG_DEBUG_LIST
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;
}
#else
extern void __list_add(struct list_head *new,
struct list_head *prev,
struct list_head *next);
#endif
/**
* list_add - add a new entry
* @new: new entry to be added
* @head: list head to add it after
*
* Insert a new entry after the specified head.
* This is good for implementing stacks.
*/
#ifndef CONFIG_DEBUG_LIST
static inline void list_add(struct list_head *new, struct list_head *head)
{
__list_add(new, head, head->next);
}
#else
extern void list_add(struct list_head *new, struct list_head *head);
#endif
/**
* list_add_tail - add a new entry
* @new: new entry to be added
* @head: list head to add it before
*
* Insert a new entry before the specified head.
* This is useful for implementing queues.
*/
static inline void list_add_tail(struct list_head *new, struct list_head *head)
{
__list_add(new, head->prev, head);
}
說明
??list_add為頭插法鸳碧，即在鏈表頭部（head節(jié)點）前插入節(jié)點盾鳞。最后打印的時候，先插入的先打印瞻离，后插入的后打印腾仅。例如原鏈表為1->2->3,使用list_add插入4后變?yōu)椋?->1->2->3。因為鏈表時循環(huán)的套利，而且通常沒有首尾節(jié)點的概念攒砖，所以可以把任何一個節(jié)點當(dāng)成head。
??同理日裙，list_add_tail為尾插法，即在鏈表尾部（head節(jié)點）插入節(jié)點惰蜜。最后打印的時候昂拂，先插入的后打印，后插入的先打印抛猖。例如原鏈表為1->2->3,使用list_add_tail插入4后變?yōu)椋?->2->3->4格侯。
舉例
#include "mylist.h"
#include <stdio.h>
#include <stdlib.h>
struct student
{
struct list_head stu_list;
int ID;
int math;
};
int main()
{
struct student *p;
struct student *q;
struct student stu1;
struct student stu2;
struct list_head *pos;
//鏈表的初始化
INIT_LIST_HEAD(&stu1.stu_list);
INIT_LIST_HEAD(&stu2.stu_list);
//頭插法創(chuàng)建stu stu1鏈表
for (int i = 0;i < 6;i++) {
p = (struct student *)malloc(sizeof(struct student));
p->ID=i;
p->math = i+80;
//頭插法
list_add(&p->stu_list,&stu1.stu_list);
//尾插法
//list_add_tail(&p->list,&stu.list);
}
printf("list_add: \r\n");
list_for_each(pos, &stu1.stu_list) {
printf("ID = %d,math = %d\n",((struct student*)pos)->ID,((struct student*)pos)->math);
}
//尾插法創(chuàng)建stu stu1鏈表
for (int i = 0;i < 6;i++) {
p = (struct student *)malloc(sizeof(struct student));
p->ID=i;
p->math = i+80;
//頭插法
//list_add(&p->stu_list,&stu1.stu_list);
//尾插法
list_add_tail(&p->stu_list,&stu2.stu_list);
}
printf("list_add_tail: \r\n");
list_for_each(pos, &stu2.stu_list) {
printf("ID = %d,math = %d\n",((struct student*)pos)->ID,((struct student*)pos)->math);
}
return 0;
}
鏈表刪除節(jié)點
內(nèi)核實現(xiàn)
//原來內(nèi)核設(shè)置的刪除鏈表后的指向位置
// # define POISON_POINTER_DELTA 0
// #define LIST_POISON1 ((void *) 0x00100100 + POISON_POINTER_DELTA)
// #define LIST_POISON2 ((void *) 0x00200200 + POISON_POINTER_DELTA)
//這里我們設(shè)置為NULL 內(nèi)核中定義NULL 為0
#define NULL ((void *)0)
#define LIST_POISON1 NULL
#define LIST_POISON2 NULL
/*
* Delete a list entry by making the prev/next entries
* point to each other.
*
* This is only for internal list manipulation where we know
* the prev/next entries already!
*/
static inline void __list_del(struct list_head * prev, struct list_head * next)
{
next->prev = prev;
prev->next = next;
}
/**
* list_del - deletes entry from list.
* @entry: the element to delete from the list.
* Note: list_empty() on entry does not return true after this, the entry is
* in an undefined state.
*/
#ifndef CONFIG_DEBUG_LIST
static inline void list_del(struct list_head *entry)
{
__list_del(entry->prev, entry->next);
entry->next = LIST_POISON1;
entry->prev = LIST_POISON2;
}
#else
extern void list_del(struct list_head *entry);
#endif
說明
??鏈表刪除之后鼻听，entry的前驅(qū)和后繼會分別指向LIST_POISON1和LIST_POISON2，這個是內(nèi)核設(shè)置的一個區(qū)域联四，但是在本例中將其置為了NULL撑碴。
舉例
#include "mylist.h"
#include <stdio.h>
#include <stdlib.h>
struct student
{
struct list_head stu_list;
int ID;
int math;
};
int main()
{
struct student *p;
struct student *q;
struct student stu1;
struct student stu2;
struct list_head *pos1;
//注意這里的pos2，后面會解釋為什么定義為
struct student *pos2;
//stu = (struct student*)malloc(sizeof(struct student));
//鏈表的初始化
INIT_LIST_HEAD(&stu1.stu_list);
INIT_LIST_HEAD(&stu2.stu_list);
LIST_HEAD(stu);
//頭插法創(chuàng)建stu stu1鏈表
for (int i = 0;i < 6;i++) {
p = (struct student *)malloc(sizeof(struct student));
p->ID=i;
p->math = i+80;
//頭插法
list_add(&p->stu_list,&stu1.stu_list);
//尾插法
//list_add_tail(&p->list,&stu.list);
}
printf("list_add: \r\n");
list_for_each(pos1, &stu1.stu_list) {
printf("ID = %d,math = %d\n",((struct student*)pos1)->ID,((struct student*)pos1)->math);
}
//刪除
list_for_each_entry(pos2,&stu1.stu_list,stu_list) {
if (pos2->ID == 4) {
list_del(&pos2->stu_list);
break;
}
}
printf("list_del\r\n");
list_for_each_entry(pos2,&stu1.stu_list,stu_list) {
printf("ID = %d,math = %d\n",pos2->ID,pos2->math);
}
return 0;
}
鏈表替換節(jié)點
內(nèi)核實現(xiàn)
/**
* list_replace - replace old entry by new one
* @old : the element to be replaced
* @new : the new element to insert
*
* If @old was empty, it will be overwritten.
*/
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);//重新初始化
}
說明
??list_replace使用新的節(jié)點替換舊的節(jié)點朝墩。
??list_replace_init與list_replace不同之處在于醉拓，list_replace_init會將舊的節(jié)點重新初始化，讓前驅(qū)和后繼指向自己收苏。
舉例
#include "mylist.h"
#include <stdio.h>
#include <stdlib.h>
struct student
{
struct list_head stu_list;
int ID;
int math;
};
int main()
{
struct student *p;
struct student *q;
struct student stu1;
struct student stu2;
struct list_head *pos1;
struct student *pos2;
struct student new_obj={.ID=100,.math=100};
//stu = (struct student*)malloc(sizeof(struct student));
//鏈表的初始化
INIT_LIST_HEAD(&stu1.stu_list);
INIT_LIST_HEAD(&stu2.stu_list);
LIST_HEAD(stu);
//頭插法創(chuàng)建stu stu1鏈表
for (int i = 0;i < 6;i++) {
p = (struct student *)malloc(sizeof(struct student));
p->ID=i;
p->math = i+80;
//頭插法
list_add(&p->stu_list,&stu1.stu_list);
//尾插法
//list_add_tail(&p->list,&stu.list);
}
printf("list_add: \r\n");
list_for_each(pos1, &stu1.stu_list) {
printf("ID = %d,math = %d\n",((struct student*)pos1)->ID,((struct student*)pos1)->math);
}
//替換
list_for_each_entry(pos2,&stu1.stu_list,stu_list) {
if (pos2->ID == 4) {
list_replace(&pos2->stu_list,&new_obj.stu_list);
break;
}
}
printf("list_replace\r\n");
list_for_each_entry(pos2,&stu1.stu_list,stu_list) {
printf("ID = %d,math = %d\n",pos2->ID,pos2->math);
}
return 0;
}
鏈表刪除并插入節(jié)點
內(nèi)核實現(xiàn)
/**
* list_move - delete from one list and add as another's head
* @list: the entry to move
* @head: the head that will precede our entry
*/
static inline void list_move(struct list_head *list, struct list_head *head)
{
__list_del(list->prev, list->next);
list_add(list, head);
}
/**
* list_move_tail - delete from one list and add as another's tail
* @list: the entry to move
* @head: the head that will follow our entry
*/
static inline void list_move_tail(struct list_head *list,
struct list_head *head)
{
__list_del(list->prev, list->next);
list_add_tail(list, head);
}
說明
??list_move函數(shù)實現(xiàn)的功能是刪除list指向的節(jié)點亿卤，同時將其以頭插法插入到head中。list_move_tail和list_move功能類似鹿霸，只不過是將list節(jié)點插入到了head的尾部排吴。
舉例
#include "mylist.h"
#include <stdio.h>
#include <stdlib.h>
struct student
{
struct list_head stu_list;
int ID;
int math;
};
int main()
{
struct student *p;
struct student *q;
struct student stu1;
struct student stu2;
struct list_head *pos1;
struct student *pos2;
struct student new_obj={.ID=100,.math=100};
//stu = (struct student*)malloc(sizeof(struct student));
//鏈表的初始化
INIT_LIST_HEAD(&stu1.stu_list);
INIT_LIST_HEAD(&stu2.stu_list);
LIST_HEAD(stu);
//頭插法創(chuàng)建stu stu1鏈表
for (int i = 0;i < 6;i++) {
p = (struct student *)malloc(sizeof(struct student));
p->ID=i;
p->math = i+80;
//頭插法
list_add(&p->stu_list,&stu1.stu_list);
//尾插法
//list_add_tail(&p->list,&stu.list);
}
printf("list_add: \r\n");
list_for_each(pos1, &stu1.stu_list) {
printf("ID = %d,math = %d\n",((struct student*)pos1)->ID,((struct student*)pos1)->math);
}
//移位替換
list_for_each_entry(pos2,&stu1.stu_list,stu_list) {
if (pos2->ID == 0) {
list_move(&pos2->stu_list,&stu1.stu_list);
break;
}
}
printf("list_move\r\n");
list_for_each_entry(pos2,&stu1.stu_list,stu_list) {
printf("ID = %d,math = %d\n",pos2->ID,pos2->math);
}
return 0;
}
鏈表的合并
內(nèi)核實現(xiàn)
static inline void __list_splice(struct list_head *list,
struct list_head *head)
{
struct list_head *first = list->next;
struct list_head *last = list->prev;
struct list_head *at = head->next;
first->prev = head;
head->next = first;
last->next = at;
at->prev = last;
}
/**
* list_splice - join two lists
* @list: the new list to add.
* @head: the place to add it in the first list.
*/
static inline void list_splice(struct list_head *list, struct list_head *head)
{
if (!list_empty(list))
__list_splice(list, head);
}
/**
* list_splice_init - join two lists and reinitialise the emptied list.
* @list: the new list to add.
* @head: the place to add it in the first list.
*
* The list at @list is reinitialised
*/
static inline void list_splice_init(struct list_head *list,
struct list_head *head)
{
if (!list_empty(list)) {
__list_splice(list, head);
INIT_LIST_HEAD(list);//置空
}
}
說明
??list_splice完成的功能是合并兩個鏈表。假設(shè)當(dāng)前有兩個鏈表懦鼠，表頭分別是stu_list1和stu_list2（都是struct list_head變量）钻哩，當(dāng)調(diào)用list_splice(&stu_list1,&stu_list2)時，只要stu_list1非空肛冶，stu_list1鏈表的內(nèi)容將被掛接在stu_list2鏈表上街氢，位于stu_list2和stu_list2.next（原stu_list2表的第一個節(jié)點）之間。新stu_list2鏈表將以原stu_list1表的第一個節(jié)點為首節(jié)點淑趾，而尾節(jié)點不變阳仔。
??list_splice_init和list_splice類似，只不過在合并完之后扣泊，調(diào)用INIT_LIST_HEAD(list)將list設(shè)置為空鏈近范。
用例
#include "mylist.h"
#include <stdio.h>
#include <stdlib.h>
struct student
{
struct list_head stu_list;
int ID;
int math;
};
int main()
{
struct student *p;
struct student *q;
struct student stu1;
struct student stu2;
struct list_head *pos1;
struct student *pos2;
struct student new_obj={.ID=100,.math=100};
//stu = (struct student*)malloc(sizeof(struct student));
//鏈表的初始化
INIT_LIST_HEAD(&stu1.stu_list);
INIT_LIST_HEAD(&stu2.stu_list);
LIST_HEAD(stu);
//頭插法創(chuàng)建stu1 list鏈表
for (int i = 0;i < 6;i++) {
p = (struct student *)malloc(sizeof(struct student));
p->ID=i;
p->math = i+80;
//頭插法
list_add(&p->stu_list,&stu1.stu_list);
//尾插法
//list_add_tail(&p->list,&stu.list);
}
printf("stu1: \r\n");
list_for_each(pos1, &stu1.stu_list) {
printf("ID = %d,math = %d\n",((struct student*)pos1)->ID,((struct student*)pos1)->math);
}
//頭插法創(chuàng)建stu2 list 鏈表
for (int i = 0;i < 3;i++) {
q = (struct student *)malloc(sizeof(struct student));
q->ID=i;
q->math = i+80;
//頭插法
list_add(&q->stu_list,&stu2.stu_list);
//尾插法
//list_add_tail(&p->list,&stu.list);
}
printf("stu2: \r\n");
list_for_each(pos1, &stu2.stu_list) {
printf("ID = %d,math = %d\n",((struct student*)pos1)->ID,((struct student*)pos1)->math);
}
//合并
list_splice(&stu1.stu_list,&stu2.stu_list);
printf("list_splice\r\n");
list_for_each(pos1, &stu2.stu_list) {
printf("stu2 ID = %d,math = %d\n",((struct student*)pos1)->ID,((struct student*)pos1)->math);
}
return 0;
}
鏈表的遍歷
內(nèi)核實現(xiàn)
//計算member在type中的位置
#define offsetof(type, member) (size_t)(&((type*)0)->member)
//根據(jù)member的地址獲取type的起始地址
#define container_of(ptr, type, member) ({ \
const typeof(((type *)0)->member)*__mptr = (ptr); \
(type *)((char *)__mptr - offsetof(type, member)); })
/**
* list_entry - get the struct for this entry
* @ptr: the &struct list_head pointer.
* @type: the type of the struct this is embedded in.
* @member: the name of the list_struct within the struct.
*/
#define list_entry(ptr, type, member) \
container_of(ptr, type, member)
/**
* list_first_entry - get the first element from a list
* @ptr: the list head to take the element from.
* @type: the type of the struct this is embedded in.
* @member: the name of the list_struct within the struct.
*
* Note, that list is expected to be not empty.
*/
#define list_first_entry(ptr, type, member) \
list_entry((ptr)->next, type, member)
/**
* list_for_each - iterate over a list
* @pos: the &struct list_head to use as a loop cursor.
* @head: the head for your list.
*/
#define list_for_each(pos, head) \
for (pos = (head)->next; prefetch(pos->next), pos != (head); \
pos = pos->next)
/**
* __list_for_each - iterate over a list
* @pos: the &struct list_head to use as a loop cursor.
* @head: the head for your list.
*
* This variant differs from list_for_each() in that it's the
* simplest possible list iteration code, no prefetching is done.
* Use this for code that knows the list to be very short (empty
* or 1 entry) most of the time.
*/
#define __list_for_each(pos, head) \
for (pos = (head)->next; pos != (head); pos = pos->next)
/**
* list_for_each_prev - iterate over a list backwards
* @pos: the &struct list_head to use as a loop cursor.
* @head: the head for your list.
*/
#define list_for_each_prev(pos, head) \
for (pos = (head)->prev; prefetch(pos->prev), pos != (head); \
pos = pos->prev)
/**
* list_for_each_safe - iterate over a list safe against removal of list entry
* @pos: the &struct list_head to use as a loop cursor.
* @n: another &struct list_head to use as temporary storage
* @head: the head for your list.
*/
#define list_for_each_safe(pos, n, head) \
for (pos = (head)->next, n = pos->next; pos != (head); \
pos = n, n = pos->next)
/**
* list_for_each_entry - iterate over list of given type
* @pos: the type * to use as a loop cursor.
* @head: the head for your list.
* @member: the name of the list_struct within the struct.
*/
#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_entry_reverse - iterate backwards over list of given type.
* @pos: the type * to use as a loop cursor.
* @head: the head for your list.
* @member: the name of the list_struct within the struct.
*/
#define list_for_each_entry_reverse(pos, head, member) \
for (pos = list_entry((head)->prev, typeof(*pos), member); \
prefetch(pos->member.prev), &pos->member != (head); \
pos = list_entry(pos->member.prev, typeof(*pos), member))
/**
* list_prepare_entry - prepare a pos entry for use in list_for_each_entry_continue()
* @pos: the type * to use as a start point
* @head: the head of the list
* @member: the name of the list_struct within the struct.
*
* Prepares a pos entry for use as a start point in list_for_each_entry_continue().
*/
#define list_prepare_entry(pos, head, member) \
((pos) ? : list_entry(head, typeof(*pos), member))
/**
* list_for_each_entry_continue - continue iteration over list of given type
* @pos: the type * to use as a loop cursor.
* @head: the head for your list.
* @member: the name of the list_struct within the struct.
*
* Continue to iterate over list of given type, continuing after
* the current position.
*/
#define list_for_each_entry_continue(pos, head, member) \
for (pos = list_entry(pos->member.next, typeof(*pos), member); \
prefetch(pos->member.next), &pos->member != (head); \
pos = list_entry(pos->member.next, typeof(*pos), member))
/**
* list_for_each_entry_from - iterate over list of given type from the current point
* @pos: the type * to use as a loop cursor.
* @head: the head for your list.
* @member: the name of the list_struct within the struct.
*
* Iterate over list of given type, continuing from current position.
*/
#define list_for_each_entry_from(pos, head, member) \
for (; prefetch(pos->member.next), &pos->member != (head); \
pos = list_entry(pos->member.next, typeof(*pos), member))
/**
* list_for_each_entry_safe - iterate over list of given type safe against removal of list entry
* @pos: the type * to use as a loop cursor.
* @n: another type * to use as temporary storage
* @head: the head for your list.
* @member: the name of the list_struct within the struct.
*/
#define list_for_each_entry_safe(pos, n, head, member) \
for (pos = list_entry((head)->next, typeof(*pos), member), \
n = list_entry(pos->member.next, typeof(*pos), member); \
&pos->member != (head); \
pos = n, n = list_entry(n->member.next, typeof(*n), member))
/**
* list_for_each_entry_safe_continue
* @pos: the type * to use as a loop cursor.
* @n: another type * to use as temporary storage
* @head: the head for your list.
* @member: the name of the list_struct within the struct.
*
* Iterate over list of given type, continuing after current point,
* safe against removal of list entry.
*/
#define list_for_each_entry_safe_continue(pos, n, head, member) \
for (pos = list_entry(pos->member.next, typeof(*pos), member), \
n = list_entry(pos->member.next, typeof(*pos), member); \
&pos->member != (head); \
pos = n, n = list_entry(n->member.next, typeof(*n), member))
/**
* list_for_each_entry_safe_from
* @pos: the type * to use as a loop cursor.
* @n: another type * to use as temporary storage
* @head: the head for your list.
* @member: the name of the list_struct within the struct.
*
* Iterate over list of given type from current point, safe against
* removal of list entry.
*/
#define list_for_each_entry_safe_from(pos, n, head, member) \
for (n = list_entry(pos->member.next, typeof(*pos), member); \
&pos->member != (head); \
pos = n, n = list_entry(n->member.next, typeof(*n), member))
/**
* list_for_each_entry_safe_reverse
* @pos: the type * to use as a loop cursor.
* @n: another type * to use as temporary storage
* @head: the head for your list.
* @member: the name of the list_struct within the struct.
*
* Iterate backwards over list of given type, safe against removal
* of list entry.
*/
#define list_for_each_entry_safe_reverse(pos, n, head, member) \
for (pos = list_entry((head)->prev, typeof(*pos), member), \
n = list_entry(pos->member.prev, typeof(*pos), member); \
&pos->member != (head); \
pos = n, n = list_entry(n->member.prev, typeof(*n), member))
說明
??list_entry(ptr, type, member)可以得到節(jié)點結(jié)構(gòu)體的地址，得到地址后就可以對結(jié)構(gòu)體中的元素進(jìn)行操作了延蟹。依靠list_entry(ptr, type, member)函數(shù)评矩，內(nèi)核鏈表的增刪查改都不需要知道list_head結(jié)構(gòu)體所嵌入式的對象，就可以完成各種操作阱飘。（為什么這里使用container_of來定義list_entry(ptr, type, member)結(jié)構(gòu)體呢斥杜，下面會詳細(xì)解釋）
??list_first_entry(ptr, type, member)得到的是結(jié)構(gòu)體中第一個元素的地址
??list_for_each(pos, head)是用來正向遍歷鏈表的，pos相當(dāng)于一個臨時的節(jié)點沥匈，用來不斷指向下一個節(jié)點蔗喂。
??list_for_each_prev(pos, head)和list_for_each_entry_reverse(pos, head, member)是用來倒著遍歷鏈表的
??list_for_each_safe(pos, n, head)和list_for_each_entry_safe(pos, n, head, member)，這兩個函數(shù)是為了避免在遍歷鏈表的過程中因pos節(jié)點被釋放而造成的斷鏈這個時候就要求我們另外提供一個與pos同類型的指針n高帖，在for循環(huán)中暫存pos下一個節(jié)點的地址缰儿。（內(nèi)核的設(shè)計者考慮的真是全面！）
??list_prepare_entry(pos, head, member)用于準(zhǔn)備一個結(jié)構(gòu)體的首地址散址，用在list_for_each_entry_contine()中
??list_for_each_entry_continue(pos, head, member)從當(dāng)前pos的下一個節(jié)點開始繼續(xù)遍歷剩余的鏈表乖阵，不包括pos.如果我們將pos宣赔、head、member傳入list_for_each_entry瞪浸，此宏將會從鏈表的頭節(jié)點開始遍歷儒将。
??list_for_each_entry_continue_reverse(pos, head, member)從當(dāng)前的pos的前一個節(jié)點開始繼續(xù)反向遍歷剩余的鏈表，不包括pos对蒲。
??list_for_each_entry_from(pos, head, member)從pos開始遍歷剩余的鏈表钩蚊。
??list_for_each_entry_safe_continue(pos, n, head, member)從pos節(jié)點的下一個節(jié)點開始遍歷剩余的鏈表，并防止因刪除鏈表節(jié)點而導(dǎo)致的遍歷出錯齐蔽。
??list_for_each_entry_safe_from(pos, n, head, member)從pos節(jié)點開始繼續(xù)遍歷剩余的鏈表两疚，并防止因刪除鏈表節(jié)點而導(dǎo)致的遍歷出錯。其與list_for_each_entry_safe_continue(pos, n, head, member)的不同在于在第一次遍歷時含滴，pos沒有指向它的下一個節(jié)點诱渤，而是從pos開始遍歷。
??list_for_each_entry_safe_reverse(pos, n, head, member)從pos的前一個節(jié)點開始反向遍歷一個鏈表谈况，并防止因刪除鏈表節(jié)點而導(dǎo)致的遍歷出錯勺美。
??list_safe_reset_next(pos, n, member)返回當(dāng)前pos節(jié)點的下一個節(jié)點的type結(jié)構(gòu)體首地址。
舉例
#include "mylist.h"
#include <stdio.h>
#include <stdlib.h>
struct student
{
struct list_head stu_list;
int ID;
int math;
};
int main()
{
struct student *p;
struct student *q;
struct student stu1;
struct student stu2;
struct list_head *pos1;
struct student *pos2;
struct student new_obj={.ID=100,.math=100};
//stu = (struct student*)malloc(sizeof(struct student));
//鏈表的初始化
INIT_LIST_HEAD(&stu1.stu_list);
INIT_LIST_HEAD(&stu2.stu_list);
LIST_HEAD(stu);
//頭插法創(chuàng)建stu stu1鏈表
for (int i = 0;i < 6;i++) {
p = (struct student *)malloc(sizeof(struct student));
p->ID=i;
p->math = i+80;
//頭插法
list_add(&p->stu_list,&stu1.stu_list);
//尾插法
//list_add_tail(&p->list,&stu.list);
}
printf("stu1: \r\n");
list_for_each(pos1, &stu1.stu_list) {
printf("ID = %d,math = %d\n",((struct student*)pos1)->ID,((struct student*)pos1)->math);
}
printf("list_for_each_prev\r\n");
list_for_each_prev(pos1, &stu1.stu_list){
printf("stu2 ID = %d,math = %d\n",((struct student*)pos1)->ID,((struct student*)pos1)->math);
}
return 0;
}
??例子就不都寫出來了碑韵，感興趣的可以自己試試赡茸。
疑惑解答
??之前我們定義結(jié)構(gòu)體的時候是把 struct list_head放在首位的，當(dāng)使用list_for_each遍歷的時候祝闻，pos獲取的位置就是結(jié)構(gòu)體的位置占卧，也就是鏈表的位置。如下所示
struct student
{
struct list_head list;//暫且將鏈表放在結(jié)構(gòu)體的第一位
int ID;
int math;
};
list_for_each(pos, &stu1.stu_list) {
printf("ID = %d,math = %d\n",((struct student*)pos)->ID,((struct student*)pos)->math);
}
??但是當(dāng)我們把struct list_head list;放在最后時联喘，pos獲取的顯然就已經(jīng)不是鏈表的位置了华蜒，那么當(dāng)我們再次調(diào)用list_for_each時就會出錯。
struct student
{
int ID;
int math;
struct list_head list;//暫且將鏈表放在結(jié)構(gòu)體的第一位
};
??list_for_each_entry這個函數(shù)表示在遍歷的時候獲取entry豁遭，該宏中的pos類型為容器結(jié)構(gòu)類型的指針叭喜，這與前面list_for_each中的使用的類型不再相同（這也就是為什么我們上面會分別定義pos1和pos2的原因了），不過這也是情理之中的事蓖谢，畢竟現(xiàn)在的pos捂蕴，我要使用該指針去訪問數(shù)據(jù)域的成員age了；head是你使用INIT_LIST_HEAD初始化的那個對象闪幽，即頭指針啥辨，注意，不是頭結(jié)點盯腌；member就是容器結(jié)構(gòu)中的鏈表元素對象溉知。使用該宏替代前面的方法。這個時候就要用到container_of這個宏了。（再一次感嘆內(nèi)核設(shè)計者的偉大）着倾。
??關(guān)于container_of宏將在下一篇文章詳細(xì)介紹，這里先知道如何使用就可以燕少。
list.h移植源碼
??這里需要注意一點卡者，如果是在GNU中使用GCC進(jìn)行程序開發(fā)，可以不做更改客们，直接使用上面的函數(shù)即可崇决；但如果你想把其移植到Windows環(huán)境中進(jìn)行使用，可以直接將prefetch語句刪除即可底挫，因為prefetch函數(shù)它通過對數(shù)據(jù)手工預(yù)取的方法恒傻，減少了讀取延遲，從而提高了性能建邓，也就是prefetch是GCC用來提高效率的函數(shù)盈厘，如果要移植到非GNU環(huán)境，可以換成相應(yīng)環(huán)境的預(yù)取函數(shù)或者直接刪除也可官边，它并不影響鏈表的功能沸手。
/*
* @Description: 移植Linux2.6內(nèi)核list.h
* @Version: V1.0
* @Autor: https://blog.csdn.net/qq_16933601
* @Date: 2020-09-12 22:54:51
* @LastEditors: Carlos
* @LastEditTime: 2020-09-16 00:35:17
*/
#ifndef _MYLIST_H
#define _MYLIST_H
//原來鏈表刪除后指向的位置，這里我們修改成 0
// # define POISON_POINTER_DELTA 0
// #define LIST_POISON1 ((void *) 0x00100100 + POISON_POINTER_DELTA)
// #define LIST_POISON2 ((void *) 0x00200200 + POISON_POINTER_DELTA)
#define NULL ((void *)0)
#define LIST_POISON1 NULL
#define LIST_POISON2 NULL
//計算member在type中的位置
#define offsetof(type, member) (size_t)(&((type*)0)->member)
//根據(jù)member的地址獲取type的起始地址
#define container_of(ptr, type, member) ({ \
const typeof(((type *)0)->member)*__mptr = (ptr); \
(type *)((char *)__mptr - offsetof(type, member)); })
//鏈表結(jié)構(gòu)
struct list_head
{
struct list_head *prev;
struct list_head *next;
};
#define LIST_HEAD_INIT(name) { &(name), &(name) }
#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;
}
static inline void init_list_head(struct list_head *list)
{
list->prev = list;
list->next = list;
}
#ifndef CONFIG_DEBUG_LIST
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;
}
#else
extern void __list_add(struct list_head *new,
struct list_head *prev,
struct list_head *next);
#endif
//從頭部添加
/**
* list_add - add a new entry
* @new: new entry to be added
* @head: list head to add it after
*
* Insert a new entry after the specified head.
* This is good for implementing stacks.
*/
#ifndef CONFIG_DEBUG_LIST
static inline void list_add(struct list_head *new, struct list_head *head)
{
__list_add(new, head, head->next);
}
#else
extern void list_add(struct list_head *new, struct list_head *head);
#endif
//從尾部添加
static inline void list_add_tail(struct list_head *new, struct list_head *head)
{
__list_add(new, head->prev, head);
}
static inline void __list_del(struct list_head *prev, struct list_head *next)
{
prev->next = next;
next->prev = prev;
}
static inline void list_del(struct list_head *entry)
{
__list_del(entry->prev, entry->next);
entry->next = LIST_POISON1;
entry->prev = LIST_POISON2;
}
static inline void __list_splice(struct list_head *list,
struct list_head *head)
{
struct list_head *first = list->next;
struct list_head *last = list->prev;
struct list_head *at = head->next;
first->prev = head;
head->next = first;
last->next = at;
at->prev = last;
}
/**
* list_empty - tests whether a list is empty
* @head: the list to test.
*/
static inline int list_empty(const struct list_head *head)
{
return head->next == head;
}
/**
* list_splice - join two lists
* @list: the new list to add.
* @head: the place to add it in the first list.
*/
static inline void list_splice(struct list_head *list, struct list_head *head)
{
if (!list_empty(list))
__list_splice(list, head);
}
/**
* list_replace - replace old entry by new one
* @old : the element to be replaced
* @new : the new element to insert
*
* If @old was empty, it will be overwritten.
*/
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);
}
/**
* list_move - delete from one list and add as another's head
* @list: the entry to move
* @head: the head that will precede our entry
*/
static inline void list_move(struct list_head *list, struct list_head *head)
{
__list_del(list->prev, list->next);
list_add(list, head);
}
/**
* list_move_tail - delete from one list and add as another's tail
* @list: the entry to move
* @head: the head that will follow our entry
*/
static inline void list_move_tail(struct list_head *list,
struct list_head *head)
{
__list_del(list->prev, list->next);
list_add_tail(list, head);
}
#define list_entry(ptr, type, member) \
container_of(ptr, type, member)
#define list_first_entry(ptr, type, member) \
list_entry((ptr)->next, type, member)
#define list_for_each(pos, head) \
for (pos = (head)->next; pos != (head); pos = pos->next)
/**
* list_for_each_entry - iterate over list of given type
* @pos: the type * to use as a loop cursor.
* @head: the head for your list.
* @member: the name of the list_struct within the struct.
*/
#define list_for_each_entry(pos, head, member) \
for (pos = list_entry((head)->next, typeof(*pos), member); \
&pos->member != (head); \
pos = list_entry(pos->member.next, typeof(*pos), member))
/**
* list_for_each_prev - iterate over a list backwards
* @pos: the &struct list_head to use as a loop cursor.
* @head: the head for your list.
*/
#define list_for_each_prev(pos, head) \
for (pos = (head)->prev; pos != (head); \
pos = pos->prev)
??養(yǎng)成習(xí)慣注簿，先贊后看契吉！如果覺得寫的不錯，歡迎關(guān)注诡渴，點贊捐晶，收藏，轉(zhuǎn)發(fā)妄辩，謝謝惑灵！
??以上代碼均為測試后的代碼。如有錯誤和不妥的地方恩袱，歡迎指出泣棋。
如遇到排版錯亂的問題，可以通過以下鏈接訪問我的CSDN畔塔。
CSDN:CSDN搜索“嵌入式與Linux那些事
我的GZH：嵌入式與Linux那些事潭辈，領(lǐng)取秋招筆試面試大禮包（華為小米等大廠面經(jīng)，嵌入式知識點總結(jié)澈吨，筆試題目把敢，簡歷模版等）和2000G學(xué)習(xí)資料。
