linux內(nèi)核提供了一個(gè)經(jīng)典通用的雙向循環(huán)鏈表list的實(shí)現(xiàn)，任何模塊都可以借助該接口實(shí)現(xiàn)自己的內(nèi)部循環(huán)鏈表。因?yàn)槭峭ㄓ玫?#xff0c;可以直接移植到用戶(hù)態(tài)中使用，下面介紹相關(guān)的接口與一個(gè)簡(jiǎn)單操作例子，包括鏈表的插入、查詢(xún)、修改和刪除操作。想深入了解的話直接閱讀內(nèi)核list源代碼，代碼不是很多，只有l(wèi)ist.h 和 types.h。內(nèi)核源碼可以直接下載也可以使用下文給出的鏈接。

內(nèi)核定義了鏈表的結(jié)構(gòu)體，任何鏈表的實(shí)現(xiàn)只要在相關(guān)結(jié)構(gòu)體中包含下面這個(gè)結(jié)構(gòu)體就可以使用。

struct list_head {struct list_head *next, *prev; };

鏈表組織成如下：

相關(guān)API接口：

1. 鏈表頭的初始化有兩種， 初始化完成就相當(dāng)于創(chuàng)建了一個(gè)鏈表，接下來(lái)就可以進(jìn)行對(duì)鏈表的增刪查改操作。

LIST_HEAD(name) //name就是鏈表頭的名字，該宏會(huì)自動(dòng)定義一個(gè)名字為name 的 list_head 結(jié)構(gòu)體。

第二種如下，先聲明一個(gè)list_head變量，然后使用該宏初始化

struct list_head head;????//聲明鏈表頭INIT_LIST_HEAD(&head); ???//鏈表頭初始化

2. 插入鏈表：

list_add(struct list_head *new, struct list_head *head)????????//加入鏈表頭部 list_add_tail(struct list_head *new, struct list_head *head)???//加入到鏈表尾部

3. 查詢(xún)鏈表：

list_for_each(pos, head)????//遍歷鏈表，可以結(jié)合list_entry()接口對(duì)數(shù)據(jù)操作 list_for_each_safe(pos, n, head)????//如果在遍歷過(guò)程中涉及結(jié)點(diǎn)刪除操作，則需要使用這個(gè)接口

4. 刪除結(jié)點(diǎn)

list_del(struct list_head *entry)

5.在內(nèi)核list源碼中還定義了很多其它的鏈表操作，這里不再一一列舉：

list_empty(const struct list_head *head) ????//判斷鏈表是否為空

下面是一個(gè)使用鏈表的例子，包括常見(jiàn)的增加、刪除、修改、查詢(xún)等操作。

/** Description : linux應(yīng)用層編程之內(nèi)核鏈表list的使用* Date ：20180610* Author ：mason* Mail : mrsonko@126.com**/#include <stddef.h> #include <stdio.h> #include <string.h> #include <unistd.h> #include <stdlib.h> #include "listdemo.h"#define log(fmt, arg...) printf(""fmt,##arg)void main() {int quit = 0;int flag = 0;int opt, key;struct list_head msg_head, *pos, *n;????//聲明鏈表首部，注意這pos, n的定義，遍歷鏈表會(huì)使用struct msg msg1, msg2, *pmsg;???????????//自定義的鏈表結(jié)點(diǎn)，結(jié)構(gòu)體中嵌套list_head結(jié)構(gòu)體INIT_LIST_HEAD(&msg_head);??? //鏈表初始化log("*********************\n\n""input options:\n""1: insert\n" //插入"2: serach\n" //查詢(xún)"3: search all \n" //查詢(xún)所有"4: modify\n" //修改"5: delete\n" //刪除"6: delete all\n" //刪除全部"0: quit\n""\n*********************\n");while(!quit) {log("\ninput options:");scanf("%d", &opt);switch(opt){//插入鏈表，相同結(jié)點(diǎn)可重復(fù)插入，也可以在加入前比較判斷防止插入重復(fù)case 1:pmsg = calloc(1, sizeof(struct msg));if(!pmsg){log("insert fail \n");break;}log("input msgid : ");scanf("%d", &pmsg->msgid);log("input msg info:");getchar();gets(pmsg->msginfo);log("[Your have input : msgid : %d, msginfo : %s ]\n", pmsg->msgid, pmsg->msginfo);list_add_tail(&pmsg->list, &msg_head); //插入尾部，list_add()插入首部break;//查詢(xún)case 2:flag = 0 ;log("input msg id:");scanf("%d", &key); //遍歷查詢(xún)list_for_each_entry(pmsg, &msg_head, list) {if(pmsg->msgid == key){ log("[msgid: %d, msginfo: %s ]\n", key, pmsg->msginfo);flag = 1;break;}}if(!flag) log("%d not found! \n", key);break; //查詢(xún)所有case 3:log("\n***** msg start *****\n\n");list_for_each_entry(pmsg, &msg_head, list){log("[msgid: %d, msginfo: %s ]\n", key, pmsg->msginfo);}log("\n***** msg end *****\n");break;//修改結(jié)點(diǎn)case 4:flag = 0;log("input msg id:");scanf("%d", &key); //修改list_for_each_entry(pmsg, &msg_head, list) {if(pmsg->msgid == key){ log("[msgid: %d, msginfo: %s ]\n", key, pmsg->msginfo);log("input msg you want to set:"); memset(pmsg->msginfo, 0, sizeof(pmsg->msginfo));getchar();gets(pmsg->msginfo);flag = 1;}}if(!flag){log("msgid : %d not fount !\n", key);}flag = 0;break;//刪除結(jié)點(diǎn) case 5:flag = 0;log("input msg id:");scanf("%d", &key); //遍歷鏈表并且執(zhí)行刪除操作需要使用這個(gè)接口 _safelist_for_each_safe(pos, n, &msg_head){pmsg = list_entry(pos, struct msg, list);if(pmsg->msgid == key){log("[delete msg, msgid:%d, msginfo:%s]\n", pmsg->msgid, pmsg->msginfo);list_del(pos);free(pmsg);flag = 1;}}if(!flag)log("msgid : %d not found!\n", key);flag = 0;break;//刪除所有case 6:list_for_each_safe(pos, n, &msg_head){pmsg = list_entry(pos, struct msg, list);log("[delete msg, msgid:%d, msginfo:%s]\n", pmsg->msgid, pmsg->msginfo);list_del(pos);free(pmsg);}break; default://退出前釋放資源list_for_each_safe(pos, n, &msg_head){pmsg = list_entry(pos, struct msg, list);list_del(pos);free(pmsg);}quit = 1;break;}}return ; }

使用截圖，查詢(xún)、修改和刪除操作。

頭文件如下，宏定義直接從內(nèi)核list.h文件中移植過(guò)來(lái)，這里只取了用到的部分，list.h還定義了很多其它的操作。

#ifndef _LISTDEMO_H #define _LISTDEMO_H//通過(guò)結(jié)構(gòu)體成員指針獲取結(jié)構(gòu)體指針位置 #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 *next, *prev; };//鏈表初始化 static inline void INIT_LIST_HEAD(struct list_head *list) {list->next = list;list->prev = 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//添加至鏈表首部 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); }//判斷鏈表是否為空 /*** list_empty - tests whether a list is empty* @head: the list to test.*//* if empty return 1,else 0 */ static inline int list_empty(const struct list_head *head) {return head->next == head; }/** 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; }//刪除操作 static inline void list_del(struct list_head *entry) {__list_del(entry->prev, entry->next);entry->next = NULL;entry->prev = NULL; }//獲取鏈表的數(shù)據(jù)指針 #define list_entry(ptr, type, member) \container_of(ptr, type, member)//遍歷鏈表 #define list_for_each(pos, head) \for (pos = (head)->next; pos != (head); pos = pos->next)//遍歷過(guò)程中如果對(duì)鏈表有刪除操作需要使用這個(gè)接口 #define list_for_each_safe(pos, n, head) \for (pos = (head)->next, n = pos->next; pos != (head); \pos = n, n = pos->next)//遍歷鏈表元素 #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))#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))//取第一個(gè)元素 #define list_first_entry(ptr, type, member) \list_entry((ptr)->next, type, member)//自定義消息結(jié)構(gòu)體 struct msg {int msgid;char msginfo[50];struct list_head list; };#endif

代碼可以直接從github上克隆下來(lái)編譯運(yùn)行，其中包含了內(nèi)核list源碼可做參考：

git clone git@github.com:FuYuanDe/list.git????//下載源碼后進(jìn)入目錄make后運(yùn)行

參考資料： https://www.ibm.com/developerworks/cn/linux/kernel/l-chain/

總結(jié)

以上是生活随笔為你收集整理的linux 应用层编程之内核链表list的使用的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。