Linux中的內(nèi)核鏈表實(shí)例詳解

更新時間：2017年08月07日 08:30:54 作者：菜頭大大

這篇文章主要介紹了Linux中的內(nèi)核鏈表實(shí)例詳解的相關(guān)資料,鏈表中一般都要進(jìn)行初始化、插入、刪除、顯示、釋放鏈表，尋找節(jié)點(diǎn)這幾個操作，需要的朋友可以參考下

Linux中的內(nèi)核鏈表實(shí)例詳解

鏈表中一般都要進(jìn)行初始化、插入、刪除、顯示、釋放鏈表，尋找節(jié)點(diǎn)這幾個操作，下面我對這幾個操作進(jìn)行簡單的介紹，因?yàn)槲业哪芰Σ蛔悖赡苡行〇|西理解的不夠深入，造成一定的錯誤，請各位博友指出。

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é)點(diǎn)中的兩個指針和頭結(jié)點(diǎn)中的兩個指針

3）頭部插入函數(shù)

static inline void list_add(struct list_head *new, struct list_head *head)
{
__list_add(new, head, head->next);
} //頭插入函數(shù),傳入的參數(shù)是新節(jié)點(diǎn)中的兩個指針和頭結(jié)點(diǎn)中的兩個指針

4）刪除節(jié)點(diǎn)函數(shù)

static inline void list_del(struct list_head *entry)  //傳入要刪除節(jié)點(diǎn)中的指針域
{
__list_del(entry->prev, entry->next);//兩個參數(shù)分別為所刪除節(jié)點(diǎn)前一個節(jié)點(diǎn)和后一個節(jié)點(diǎn)
entry->next = (void *) 0;//刪除節(jié)點(diǎn)后置為空
entry->prev = (void *) 0;
}

5）顯示函數(shù)（如果要打印出鏈表中的信息的話要自己寫成打印的函數(shù)，比如printf，因?yàn)檫@個其實(shí)是一個遍歷的函數(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é)點(diǎn)指針，
head是頭結(jié)點(diǎn)中的兩個指針的地址
member為各節(jié)點(diǎn)中的指針域
*/

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é)點(diǎn)（這也是用的內(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.下面來段代碼給大家看看具體的運(yùn)用方法


#include"kernel.h"
#include<errno.h>
#include<stdio.h>
#include<stdlib.h>

typedef struct list_node
{
int data;
struct list_head list;//節(jié)點(diǎn)的指針域是被封裝在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é)點(diǎn)分配空間
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é)點(diǎn)的中兩個指針，即struct list_head結(jié)構(gòu)體中的兩個指針
return head;
}

node insert_tail(node head,int data)//尾部插入函數(shù)
{
node new = (node)malloc(sizeof(node1));//為新節(jié)點(diǎn)分配空間
if(new == NULL)//判斷一下分配空間是否成功
{
perror("new:");
return NULL;
}
new->data = data;
list_add_tail(&(new->list),&(head->list));//調(diào)用內(nèi)核中的從尾部插入的函數(shù)，傳入的參數(shù)為新節(jié)點(diǎn)中的兩個指針
//和頭結(jié)點(diǎn)中的兩個指針
return 0;
}

 

head_insert_node(node head,int data)//頭插入函數(shù)
{
node new;//創(chuàng)建一個新節(jié)點(diǎn)
new = (node)malloc(sizeof(node1));//為新節(jié)點(diǎn)分配空間
if(new == NULL)//判斷一下分配空間是否成功
{
perror("new:");
return 0;
}
new->data = data;
list_add(&(new->list),&(head->list));//調(diào)用內(nèi)核中從頭插入的函數(shù)，傳入的參數(shù)為新節(jié)點(diǎn)的兩個指針和頭結(jié)點(diǎn)的兩個指針
return 0;
}

node search_node(node head,int data)//尋找節(jié)點(diǎn)函數(shù)
{
node p = NULL;
list_for_each_entry(p,&(head->list),list) //內(nèi)核中的遍歷函數(shù)
{
if(p->data == data) //p即為需要找的節(jié)點(diǎn)
{
printf("found the data:%d\n",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 %d\n",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:%d\n",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é)點(diǎn)函數(shù)
show_node(head);
delete_node(head,55);
//show_list(head);
delete_list(head);//刪除鏈表函數(shù)
return 0;
}

以上就是Linux中的內(nèi)核鏈表實(shí)例詳解的實(shí)例如有疑問請留言或者到本站社區(qū)交流討論，感謝閱讀，希望能幫助到大家，謝謝大家對本站的支持！

您可能感興趣的文章: