這篇文章主要介紹了linux中的內(nèi)核鏈表實例詳解的相關(guān)資料,鏈表中一般都要進行初始化、插入、刪除、顯示、釋放鏈表，尋找節(jié)點這幾個操作，需要的朋友可以參考下
linux中的內(nèi)核鏈表實例詳解
鏈表中一般都要進行初始化、插入、刪除、顯示、釋放鏈表，尋找節(jié)點這幾個操作，下面我對這幾個操作進行簡單的介紹，因為我的能力不足，可能有些東西理解的不夠深入，造成一定的錯誤，請各位博友指出。
A、Linux內(nèi)核鏈表中的幾個主要函數(shù)(下面是內(nèi)核中的源碼拿出來給大家分析一下)
1）初始化：
#define?INIT_LIST_HEAD(ptr)?do?{? (ptr)->next?=?(ptr);?(ptr)->prev?=?(ptr);? }?while?(0)??//?ptr為struct?list_head，其中包括兩個指針next和prev，這里已經(jīng)可以看出內(nèi)核鏈表是雙向循環(huán)鏈表
2）尾部插入：
static?inline?void?list_add_tail(struct?list_head?*new,?struct?list_head?*head) { __list_add(new,?head->prev,?head); }?//尾部插入,傳入的參數(shù)是新節(jié)點中的兩個指針和頭結(jié)點中的兩個指針
3）頭部插入函數(shù)
static?inline?void?list_add(struct?list_head?*new,?struct?list_head?*head) { __list_add(new,?head,?head->next); }?//頭插入函數(shù),傳入的參數(shù)是新節(jié)點中的兩個指針和頭結(jié)點中的兩個指針
4）刪除節(jié)點函數(shù)
static?inline?void?list_del(struct?list_head?*entry)??//傳入要刪除節(jié)點中的指針域 { __list_del(entry->prev,?entry->next);//兩個參數(shù)分別為所刪除節(jié)點前一個節(jié)點和后一個節(jié)點 entry->next?=?(void?*)?0;//刪除節(jié)點后置為空 entry->prev?=?(void?*)?0; }
5）顯示函數(shù)（如果要打印出鏈表中的信息的話要自己寫成打印的函數(shù)，比如printf，因為這個其實是一個遍歷的函數(shù)，沒有顯示的功能）
#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)) /*?這個函數(shù)用于遍歷鏈表 pos為節(jié)點指針， head是頭結(jié)點中的兩個指針的地址 member為各節(jié)點中的指針域 */
6）刪除鏈表
#define?list_for_each_safe(pos,?n,?head)? for?(pos?=?(head)->next,?n?=?pos->next;?pos?!=?(head);? pos?=?n,?n?=?pos->next) //這里面的pos和n都是list_head指針，n指針是用于在刪除時不讓鏈表斷鏈
7）尋找節(jié)點（這也是用的內(nèi)核中的遍歷函數(shù)）
#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))
B.下面來段代碼給大家看看具體的運用方法
#include"kernel.h" #include<errno.h> #include<stdio.h> #include<stdlib.h> typedef?struct?list_node { int?data; struct?list_head?list;//節(jié)點的指針域是被封裝在struct?list_head這個結(jié)構(gòu)體內(nèi) //這個結(jié)構(gòu)體中包括struct?list_head?*next,*prev }*node,node1; node?init_head(node?head)//初始化空鏈表 { head?=?(node)malloc(sizeof(node1));//為節(jié)點分配空間 if(head?==?NULL) { perror("head"); return?NULL; } INIT_LIST_HEAD(&(head->list));//#define?INIT_LIST_HEAD(ptr)?do?{? (ptr)->next?=?(ptr);?(ptr)->prev?=?(ptr);? }?while?(0)//調(diào)用內(nèi)核中的初始化函數(shù)，傳入的參數(shù)是 //節(jié)點的中兩個指針，即struct?list_head結(jié)構(gòu)體中的兩個指針 return?head; } node?insert_tail(node?head,int?data)//尾部插入函數(shù) { node?new?=?(node)malloc(sizeof(node1));//為新節(jié)點分配空間 if(new?==?NULL)//判斷一下分配空間是否成功 { perror("new:"); return?NULL; } new->data?=?data; list_add_tail(&(new->list),&(head->list));//調(diào)用內(nèi)核中的從尾部插入的函數(shù)，傳入的參數(shù)為新節(jié)點中的兩個指針 //和頭結(jié)點中的兩個指針 return?0; } ? head_insert_node(node?head,int?data)//頭插入函數(shù) { node?new;//創(chuàng)建一個新節(jié)點 new?=?(node)malloc(sizeof(node1));//為新節(jié)點分配空間 if(new?==?NULL)//判斷一下分配空間是否成功 { perror("new:"); return?0; } new->data?=?data; list_add(&(new->list),&(head->list));//調(diào)用內(nèi)核中從頭插入的函數(shù)，傳入的參數(shù)為新節(jié)點的兩個指針和頭結(jié)點的兩個指針 return?0; } node?search_node(node?head,int?data)//尋找節(jié)點函數(shù) { node?p?=?NULL; list_for_each_entry(p,&(head->list),list)?//內(nèi)核中的遍歷函數(shù) { if(p->data?==?data)?//p即為需要找的節(jié)點 { printf("found?the?data:%dn",p->data); goto?OK; } } puts("not?found?the?data!"); return?NULL; OK: return?p; } int?show_node(node?tmp) { if(tmp?==?NULL) { puts("tmp?is?NULL!"); return?-1; } printf("the?data?is?%dn",tmp->data); return?0; } int?delete_node(node?head,int?data) { node?p?=?NULL; list_for_each_entry(p,&(head->list),list) { if(p->data?==?data) { printf("found?the?data?which?you?want?to?delete!n"); goto?f; } } f: list_del(&(p->list)); free(p); return?0; } int?show_list(node?head) { node?p?=?NULL; list_for_each_entry(p,&(head->list),list) { printf("data:%dn",p->data); } return?0; } int?delete_list(node?head)//刪除鏈表函數(shù) { node?p,q; list_for_each_entry_safe(p,q,&(head->list),list)//這是內(nèi)核中的安全刪除函數(shù) { list_del(&(p->list)); free(p); } list_del(&(head->list)); free(head); return?0; } int?main(int?argc,char?**argv) { node?head; node?tmp; head?=?init_head(head);//初始化空鏈表函數(shù) insert_tail(head,45);//從末尾插入函數(shù) insert_tail(head,55); insert_tail(head,65); head_insert_node(head,75);//從頭插入函數(shù) show_list(head);?//顯示鏈表函數(shù)? tmp?=?search_node(head,55);//尋找結(jié)點函數(shù) show_node(head); delete_node(head,55); //show_list(head); delete_list(head);//刪除鏈表函數(shù) return?0; }</stdlib.h></stdio.h></errno.h>
? 版權(quán)聲明
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載。
THE END
