【Linux高級(jí)編譯】list.h的高效應(yīng)用—雙向鏈表的實(shí)現(xiàn)
Linux內(nèi)核中，有許許多多的精妙設(shè)計(jì)，比如在內(nèi)核代碼中，運(yùn)用到了大量的【鏈表】這種數(shù)據(jù)結(jié)構(gòu)，而在Linux內(nèi)核中，針對(duì)如此多的鏈表要進(jìn)行操作，他們分別是如何定義和管理的呢？本文將給你展示，Linux內(nèi)核中l(wèi)ist.h的高效應(yīng)用。
在上一篇文章中，我們已經(jīng)介紹過(guò)了lish.h在 單向鏈表 中的應(yīng)用，本文乘勝追擊，再次介紹一下lish.h在 雙向鏈表 中的應(yīng)用。
通過(guò)本文的閱讀，你將了解到以下內(nèi)容：
- list.h的全貌（上篇文章已經(jīng)介紹過(guò)了）
- 如何使用list.h創(chuàng)建雙向鏈表并實(shí)現(xiàn)鏈表的基本操作？
如何使用list.h創(chuàng)建雙向鏈表并實(shí)現(xiàn)鏈表的基本操作？
單向鏈表與雙向鏈表的最大區(qū)別就是：雙向鏈表可以同時(shí)從表頭和表尾操作，即【雙向】。我們將上面單向鏈表的實(shí)現(xiàn)代碼，稍微改改，配合list.h提供的接口，即可實(shí)現(xiàn)雙向鏈表的基本操作。示例代碼如下：
/******************************************************************
本文件借助linux_list.h實(shí)現(xiàn)【雙向鏈表】的基本操作：
創(chuàng)建、添加、查找、修改、刪除、銷毀、打印等
******************************************************************/
#include
#include
#include
#include
#include "linux_list.h"
/** 查找鏈表的方向 */
#define LIST_FROM_HEAD_TO_TAIL 1
#define LIST_FROM_TAIL_TO_HEAD 0
/** 鏈表節(jié)點(diǎn)中存儲(chǔ)的實(shí)際內(nèi)容 */
typedef struct _data_node_t {
int index;
char msg[128];
} node_data_t;
/** 鏈表節(jié)點(diǎn)的對(duì)外數(shù)據(jù)類型定義 */
typedef struct _my_list_node_t {
node_data_t data;
struct list_head list;
} my_list_node_t ;
/** 定義鏈表的表頭 */
static my_list_node_t g_list_head;
/** 定義鏈表當(dāng)前的節(jié)點(diǎn)個(gè)數(shù) */
static int g_list_node_cnt = 0;
/** 鏈表創(chuàng)建 */
int my_list_create(void)
{
INIT_LIST_HEAD(&g_list_head.list);
return 0;
}
/** 鏈表增加節(jié)點(diǎn)到鏈表尾部 */
int my_list_add_tail_node(const node_data_t *data)
{
my_list_node_t *node;
node = (my_list_node_t *)malloc(sizeof(my_list_node_t));
if (!node) {
printf("memory error !\n");
return -1;
}
node->data.index = data->index;
snprintf(node->data.msg, sizeof(node->data.msg), "%s", data->msg);
list_add_tail(&node->list, &g_list_head.list);
g_list_node_cnt ++;
return 0;
}
/** 鏈表增加節(jié)點(diǎn)到鏈表頭部 */
int my_list_add_head_node(const node_data_t *data)
{
my_list_node_t *node;
node = (my_list_node_t *)malloc(sizeof(my_list_node_t));
if (!node) {
printf("memory error !\n");
return -1;
}
node->data.index = data->index;
snprintf(node->data.msg, sizeof(node->data.msg), "%s", data->msg);
list_add(&node->list, &g_list_head.list);
g_list_node_cnt ++;
return 0;
}
/** 鏈表查找節(jié)點(diǎn)(從頭往尾查找) */
my_list_node_t * my_list_query_node_from_head(const node_data_t *data)
{
struct list_head *pos,*n;
my_list_node_t *p;
list_for_each_safe(pos, n, &g_list_head.list)
{
p = list_entry(pos, my_list_node_t, list);
if((p->data.index == data->index) && (!strcmp((char*)p->data.msg, data->msg)))
{
//printf("found index=%d, msg=%s\n", data->index, data->msg);
return p;
}
}
return NULL;
}
/** 鏈表查找節(jié)點(diǎn)(從尾往頭查找) */
my_list_node_t * my_list_query_node_from_tail(const node_data_t *data)
{
struct list_head *pos,*n;
my_list_node_t *p;
list_for_each_prev_safe(pos, n, &g_list_head.list)
{
p = list_entry(pos, my_list_node_t, list);
if((p->data.index == data->index) && (!strcmp((char*)p->data.msg, data->msg)))
{
//printf("found index=%d, msg=%s\n", data->index, data->msg);
return p;
}
}
return NULL;
}
/** 鏈表查找節(jié)點(diǎn)(dir, 為1表示從頭往尾查找, 為0表示從尾往頭查找) */
my_list_node_t * my_list_query_node(const node_data_t *data, int dir)
{
if (dir) {
return my_list_query_node_from_head(data);
} else {
return my_list_query_node_from_tail(data);
}
}
/** 鏈表將一個(gè)節(jié)點(diǎn)的內(nèi)容進(jìn)行修改 */
int my_list_modify_node(const node_data_t *old_data, const node_data_t *new_data)
{
my_list_node_t *p = my_list_query_node(old_data, LIST_FROM_HEAD_TO_TAIL);
if (p)
{
p->data.index = new_data->index;
snprintf(p->data.msg, sizeof(p->data.msg), "%s", new_data->msg);
return 0;
}
else
{
printf("Node index=%d, msg=%s, not found !\n", old_data->index, old_data->msg);
return -1;
}
}
/** 鏈表刪除一個(gè)節(jié)點(diǎn) */
int my_list_delete_node(const node_data_t *data)
{
my_list_node_t *p = my_list_query_node(data, LIST_FROM_HEAD_TO_TAIL); //默認(rèn)從頭部開始查找節(jié)點(diǎn)
if (p)
{
struct list_head *pos = &p->list;
list_del(pos);
free(p);
g_list_node_cnt --;
return 0;
}
else
{
printf("Node index=%d, msg=%s, not found !\n", data->index, data->msg);
return -1;
}
}
/** 鏈表刪除所有節(jié)點(diǎn) */
int my_list_delete_all_node(void)
{
struct list_head *pos,*n;
my_list_node_t *p;
list_for_each_safe(pos, n, &g_list_head.list)
{
p = list_entry(pos, my_list_node_t, list);
list_del(pos);
free(p);
}
g_list_node_cnt = 0;
return 0;
}
/** 鏈表銷毀 */
int my_list_destory(void)
{
/** do nothing here ! */
return 0;
}
/** 鏈表內(nèi)容打印 */
int my_list_print(int print_index)
{
int i = 1;
struct list_head * pos,*n;
my_list_node_t * node;
printf("==================== %d ===========================\n", print_index);
printf("cur list data : g_list_node_cnt = %d \n", g_list_node_cnt);
list_for_each_safe(pos, n, &g_list_head.list) //調(diào)用linux_list.h中的list_for_each函數(shù)進(jìn)行遍歷
{
node = list_entry(pos, my_list_node_t, list); //調(diào)用list_entry函數(shù)得到相對(duì)應(yīng)的節(jié)點(diǎn)
printf("Node %2d's : index=%-3d, msg=%-20s\n",
i++, node->data.index, node->data.msg);
}
printf("==================================================\n");
return 0;
}
int main(int argc, const char *argv[])
{
int retval = -1;
my_list_node_t *p;
const node_data_t data1 = {1, "a1bcde"};
const node_data_t data2 = {2, "ab2cde"};
const node_data_t data3 = {3, "abc3de"};
const node_data_t data4 = {4, "abcd4e"};
const node_data_t data5 = {5, "abcde5"};
const node_data_t data6 = {6, "abcde5666"}; // 定義一個(gè)不添加到鏈表的節(jié)點(diǎn)信息
const node_data_t data7 = {7, "abcde5777"}; // 定義一個(gè)被修改的節(jié)點(diǎn)信息
const node_data_t data8 = {8, "abcde5888"}; // 定義一個(gè)修改后的節(jié)點(diǎn)信息
/** 創(chuàng)建一個(gè)空鏈表 */
retval = my_list_create();
if (!retval) {
printf("list create ok !!!\n");
}
printf("\n\n\n");
/** 往鏈表的尾部添加6個(gè)節(jié)點(diǎn) */
retval = my_list_add_head_node(&data1);
if (!retval) {
printf("node1 add ok !\n");
}
retval = my_list_add_tail_node(&data2);
if (!retval) {
printf("node2 add ok !\n");
}
retval = my_list_add_head_node(&data3);
if (!retval) {
printf("node3 add ok !\n");
}
retval = my_list_add_tail_node(&data4);
if (!retval) {
printf("node4 add ok !\n");
}
retval = my_list_add_head_node(&data5);
if (!retval) {
printf("node5 add ok !\n");
}
retval = my_list_add_tail_node(&data7);
if (!retval) {
printf("node7 add ok !\n");
}
printf("\n\n\n");
/** 分別查詢剛剛添加的前5個(gè)節(jié)點(diǎn) */
p = my_list_query_node(&data1, LIST_FROM_HEAD_TO_TAIL);
if (p) {
printf("node %d,%s, found !!!\n", data1.index, data1.msg);
}
p = my_list_query_node(&data2, LIST_FROM_TAIL_TO_HEAD);
if (p) {
printf("node %d,%s, found !!!\n", data2.index, data2.msg);
}
p = my_list_query_node(&data3, LIST_FROM_HEAD_TO_TAIL);
if (p) {
printf("node %d,%s, found !!!\n", data3.index, data3.msg);
}
p = my_list_query_node(&data4, LIST_FROM_TAIL_TO_HEAD);
if (p) {
printf("node %d,%s, found !!!\n", data4.index, data4.msg);
}
p = my_list_query_node(&data5, LIST_FROM_HEAD_TO_TAIL);
if (p) {
printf("node %d,%s, found !!!\n", data5.index, data5.msg);
}
/** 查詢一個(gè)沒(méi)有添加到鏈表中的節(jié)點(diǎn)，即不存在的節(jié)點(diǎn) */
p = my_list_query_node(&data6, LIST_FROM_HEAD_TO_TAIL);
if (!p) {
printf("node %d,%s, found fail !!!\n", data6.index, data6.msg);
}
p = my_list_query_node(&data6, LIST_FROM_TAIL_TO_HEAD);
if (!p) {
printf("node %d,%s, found fail !!!\n", data6.index, data6.msg);
}
/** 打印當(dāng)前鏈表的節(jié)點(diǎn)信息 */
printf("\n\n\n");
my_list_print(1);
printf("\n\n\n");
/** 將data7的信息修改為data8的內(nèi)容 */
retval = my_list_modify_node(&data7, &data8);
if (!retval) {
printf("node %d,%s => %d,%s, modify ok !!!\n", data7.index, data7.msg, data8.index, data8.msg);
} else {
printf("node %d,%s => %d,%s, modify fail !!!\n", data7.index, data7.msg, data8.index, data8.msg);
}
/** 查詢剛剛被修改了的節(jié)點(diǎn)data7，即不存在的節(jié)點(diǎn) */
p = my_list_query_node(&data7, LIST_FROM_HEAD_TO_TAIL);
if (!p) {
printf("node %d,%s, found fail !!!\n", data7.index, data7.msg);
}
/** 查詢剛剛被修改后的節(jié)點(diǎn)data8，即存在的節(jié)點(diǎn) */
p = my_list_query_node(&data8, LIST_FROM_TAIL_TO_HEAD);
if (p) {
printf("node %d,%s, found ok !!!\n", data8.index, data8.msg);
}
/** 打印當(dāng)前鏈表的節(jié)點(diǎn)信息 */
printf("\n\n\n");
my_list_print(2);
printf("\n\n\n");
/** 刪除一個(gè)存在于鏈表中的節(jié)點(diǎn) */
retval = my_list_delete_node(&data4);
if (!retval) {
printf("node %d,%s, delete ok !!!\n", data4.index, data4.msg);
}
printf("\n\n\n");
/** 再次查詢剛剛已刪除的節(jié)點(diǎn) */
p = my_list_query_node(&data4, LIST_FROM_HEAD_TO_TAIL);
if (p) {
printf("node %d,%s, found ok !!!\n", data4.index, data4.msg);
} else {
printf("node %d,%s, found fail !!!\n", data4.index, data4.msg);
}
printf("\n\n\n");
/** 刪除一個(gè)不存在于鏈表中的節(jié)點(diǎn) */
retval = my_list_delete_node(&data6);
if (retval) {
printf("node %d,%s, delete fail !!!\n", data6.index, data6.msg);
}
/** 打印當(dāng)前鏈表的節(jié)點(diǎn)信息 */
printf("\n\n\n");
my_list_print(3);
printf("\n\n\n");
/** 刪除鏈表的所有節(jié)點(diǎn) */
retval = my_list_delete_all_node();
if (!retval) {
printf("all list notes delete done !\n");
}
/** 打印當(dāng)前鏈表的節(jié)點(diǎn)信息 */
printf("\n\n\n");
my_list_print(4);
printf("\n\n\n");
/** 銷毀鏈表 */
retval = my_list_destory();
if (!retval) {
printf("list destory done !\n");
}
/** 打印當(dāng)前鏈表的節(jié)點(diǎn)信息 */
printf("\n\n\n");
my_list_print(5);
printf("\n\n\n");
return retval;
}
[外鏈圖片轉(zhuǎn)存失敗,源站可能有防盜鏈機(jī)制,建議將圖片保存下來(lái)直接上傳(img-BAOzFCxb-1662955522821)(data:image/gif;base64,R0lGODlhAQABAPABAP///wAAACH5BAEKAAAALAAAAAABAAEAAAICRAEAOw==)]
在main函數(shù)中，我們使用了與單向鏈表一樣的測(cè)試案例，運(yùn)行結(jié)果如下：
root@liluchang-ubuntu:/share/llc/linux_list# ./linux_double_list
list create ok !!!
node1 add ok !
node2 add ok !
node3 add ok !
node4 add ok !
node5 add ok !
node7 add ok !
node 1,a1bcde, found !!!
node 2,ab2cde, found !!!
node 3,abc3de, found !!!
node 4,abcd4e, found !!!
node 5,abcde5, found !!!
node 6,abcde5666, found fail !!!
node 6,abcde5666, found fail !!!
==================== 1 ===========================
cur list data : g_list_node_cnt = 6
Node 1's : index=5 , msg=abcde5
Node 2's : index=3 , msg=abc3de
Node 3's : index=1 , msg=a1bcde
Node 4's : index=2 , msg=ab2cde
Node 5's : index=4 , msg=abcd4e
Node 6's : index=7 , msg=abcde5777
==================================================
node 7,abcde5777 => 8,abcde5888, modify ok !!!
node 7,abcde5777, found fail !!!
node 8,abcde5888, found ok !!!
==================== 2 ===========================
cur list data : g_list_node_cnt = 6
Node 1's : index=5 , msg=abcde5
Node 2's : index=3 , msg=abc3de
Node 3's : index=1 , msg=a1bcde
Node 4's : index=2 , msg=ab2cde
Node 5's : index=4 , msg=abcd4e
Node 6's : index=8 , msg=abcde5888
==================================================
node 4,abcd4e, delete ok !!!
node 4,abcd4e, found fail !!!
Node index=6, msg=abcde5666, not found !
node 6,abcde5666, delete fail !!!
==================== 3 ===========================
cur list data : g_list_node_cnt = 5
Node 1's : index=5 , msg=abcde5
Node 2's : index=3 , msg=abc3de
Node 3's : index=1 , msg=a1bcde
Node 4's : index=2 , msg=ab2cde
Node 5's : index=8 , msg=abcde5888
==================================================
all list notes delete done !
==================== 4 ===========================
cur list data : g_list_node_cnt = 0
==================================================
list destory done !
==================== 5 ===========================
cur list data : g_list_node_cnt = 0
==================================================
對(duì)比運(yùn)行的結(jié)果，發(fā)現(xiàn)與單向鏈表的測(cè)試結(jié)果一致，證明2者的實(shí)現(xiàn)功能是一致。
那么在實(shí)際項(xiàng)目過(guò)程中，究竟使用單向鏈表還是雙向鏈表呢？這就要根據(jù)具體的項(xiàng)目需求，靈活使用，不同的應(yīng)用場(chǎng)景使用不同的鏈表實(shí)現(xiàn)，也許能達(dá)到事半功倍的效果。
好了，本次關(guān)于Linux內(nèi)核的list.h的應(yīng)用，就介紹到這里，如果有疑問(wèn)，歡迎在評(píng)論席提出。感謝您的閱讀。
聲明：本文內(nèi)容及配圖由入駐作者撰寫或者入駐合作網(wǎng)站授權(quán)轉(zhuǎn)載。文章觀點(diǎn)僅代表作者本人，不代表電子發(fā)燒友網(wǎng)立場(chǎng)。文章及其配圖僅供工程師學(xué)習(xí)之用，如有內(nèi)容侵權(quán)或者其他違規(guī)問(wèn)題，請(qǐng)聯(lián)系本站處理。
舉報(bào)投訴
-
Linux
+關(guān)注
關(guān)注
87文章
11232瀏覽量
208952 -
鏈表
+關(guān)注
關(guān)注
0文章
80瀏覽量
10547
發(fā)布評(píng)論請(qǐng)先 登錄
相關(guān)推薦
【Linux高級(jí)編譯】list.h的高效應(yīng)用—單向鏈表的實(shí)現(xiàn)
【Linux高級(jí)編譯】Linux內(nèi)核的list.h的高效應(yīng)用——單向
c++之list容器
list是序列容器，允許在序列中的任何位置執(zhí)行固定O(1)時(shí)間復(fù)雜度的插入和刪除操作，并在兩個(gè)方向進(jìn)行迭代。list容器是一個(gè)雙向循環(huán)鏈表。
Linux內(nèi)核的鏈表操作
大量的鏈表結(jié)構(gòu)來(lái)組織數(shù)據(jù)，包括設(shè)備列表以及各種功能模塊中的數(shù)據(jù)組織。這些鏈表大多采用在[include/linux/list.h]實(shí)現(xiàn)的一個(gè)
發(fā)表于 08-29 11:13
Linux Kernel數(shù)據(jù)結(jié)構(gòu):鏈表
; WRITE_ONCE(prev->next, next);}當(dāng)然鏈表還提供了很多相關(guān)的接口，實(shí)現(xiàn)在kernelxx/include/linux/list.h中，可以參閱。
發(fā)表于 09-25 16:41
【HarmonyOS】雙向循環(huán)鏈表篇
)從頭部插入鏈表LOS_ListTailInsertList(LOS_DL_LIST *oldList, LOS_DL_LIST *newList)鴻蒙使用了雙向循環(huán)
發(fā)表于 10-20 15:39
Linux內(nèi)核中的數(shù)據(jù)結(jié)構(gòu)的一點(diǎn)認(rèn)識(shí)
/linux/list.h頭文件，就可以看到內(nèi)核中聲明的一些與鏈表操作相關(guān)的結(jié)構(gòu)體定義和函數(shù)接口。內(nèi)核中使用更多的是雙向循環(huán)鏈表。我們就看一
發(fā)表于 04-20 16:42
深入淺出linux內(nèi)核源代碼之雙向鏈表list_head說(shuō)明文檔
深入淺出linux內(nèi)核源代碼之雙向鏈表list_head說(shuō)明文檔以及源碼，可以移植到單片機(jī)中來(lái)。
發(fā)表于 07-20 17:21
?6次下載
FreeRTOS代碼剖析之5：鏈表管理list.c
鏈表是操作系統(tǒng)中常用的數(shù)據(jù)結(jié)構(gòu)，其結(jié)構(gòu)比較簡(jiǎn)單，因此在剖析FreeRTOS的內(nèi)核時(shí)先從這里開始入手。 鏈表是由眾多鏈表節(jié)點(diǎn)組成的，在FreeRTOS中，鏈表節(jié)點(diǎn)有兩種定義，分別是xLI
發(fā)表于 02-09 02:57
?694次閱讀
了解Linux通用的雙向循環(huán)鏈表
在linux內(nèi)核中，有一種通用的雙向循環(huán)鏈表，構(gòu)成了各種隊(duì)列的基礎(chǔ)。鏈表的結(jié)構(gòu)定義和相關(guān)函數(shù)均在include/linux/
發(fā)表于 05-07 10:44
?670次閱讀
你知道Linux內(nèi)核數(shù)據(jù)結(jié)構(gòu)中雙向鏈表的作用？
Linux 內(nèi)核提供一套雙向鏈表的實(shí)現(xiàn)，你可以在 include/linux/list.h 中找
發(fā)表于 05-14 17:27
?1869次閱讀
雙向循環(huán)鏈表函數(shù)是什么？如何去實(shí)現(xiàn)它？
雙向循環(huán)鏈表結(jié)點(diǎn)內(nèi)部有2個(gè)指針prev和next分別指向前后的結(jié)點(diǎn)，結(jié)點(diǎn)定義代碼如下。
linux內(nèi)核中l(wèi)list.h文件中的鏈表宏講解
鏈表宏在linux內(nèi)核、鴻蒙內(nèi)核、rtos和一些開源代碼中用的非常多。鏈表宏是雙向鏈表的經(jīng)典實(shí)現(xiàn)
雙向循環(huán)鏈表的創(chuàng)建
需要注意的是，雖然雙向循環(huán)鏈表成環(huán)狀，但本質(zhì)上還是雙向鏈表，因此在雙向循環(huán)鏈表中，依然能夠找到頭
關(guān)于llist.h文件中的鏈表宏講解
鏈表宏在linux內(nèi)核、鴻蒙內(nèi)核、rtos和一些開源代碼中用的非常多。鏈表宏是雙向鏈表的經(jīng)典實(shí)現(xiàn)
工商網(wǎng)監(jiān)
評(píng)論