【Linux高級編譯】list.h的高效應用—雙向鏈表的實現(xiàn)

Linux內(nèi)核中，有許許多多的精妙設計，比如在內(nèi)核代碼中，運用到了大量的【鏈表】這種數(shù)據(jù)結構，而在Linux內(nèi)核中，針對如此多的鏈表要進行操作，他們分別是如何定義和管理的呢？本文將給你展示，Linux內(nèi)核中l(wèi)ist.h的高效應用。

在上一篇文章中，我們已經(jīng)介紹過了lish.h在 單向鏈表 中的應用，本文乘勝追擊，再次介紹一下lish.h在 雙向鏈表 中的應用。

通過本文的閱讀，你將了解到以下內(nèi)容：

• list.h的全貌（上篇文章已經(jīng)介紹過了）
• 如何使用list.h創(chuàng)建雙向鏈表并實現(xiàn)鏈表的基本操作？

如何使用list.h創(chuàng)建雙向鏈表并實現(xiàn)鏈表的基本操作？

單向鏈表與雙向鏈表的最大區(qū)別就是：雙向鏈表可以同時從表頭和表尾操作，即【雙向】。我們將上面單向鏈表的實現(xiàn)代碼，稍微改改，配合list.h提供的接口，即可實現(xiàn)雙向鏈表的基本操作。示例代碼如下：

/******************************************************************
本文件借助linux_list.h實現(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é)點中存儲的實際內(nèi)容 */
typedef struct _data_node_t {
	int 				index;
	char 				msg[128];
} node_data_t;

/** 鏈表節(jié)點的對外數(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;
/** 定義鏈表當前的節(jié)點個數(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é)點到鏈表尾部 */
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é)點到鏈表頭部 */
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é)點(從頭往尾查找) */
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é)點(從尾往頭查找) */
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é)點(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);
	}
}

/** 鏈表將一個節(jié)點的內(nèi)容進行修改 */
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;
    }
}

/** 鏈表刪除一個節(jié)點 */
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); //默認從頭部開始查找節(jié)點
    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é)點 */
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ù)進行遍歷
    {
        node = list_entry(pos, my_list_node_t, list); //調(diào)用list_entry函數(shù)得到相對應的節(jié)點
        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"}; // 定義一個不添加到鏈表的節(jié)點信息
	const node_data_t data7 = {7, "abcde5777"}; // 定義一個被修改的節(jié)點信息
	const node_data_t data8 = {8, "abcde5888"}; // 定義一個修改后的節(jié)點信息
	
	/** 創(chuàng)建一個空鏈表 */
	retval = my_list_create();
	if (!retval) {
		printf("list create ok !!!\n");
	}
	printf("\n\n\n");
	
	/** 往鏈表的尾部添加6個節(jié)點 */
	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個節(jié)點 */
	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);
	}
	
	/** 查詢一個沒有添加到鏈表中的節(jié)點，即不存在的節(jié)點 */
	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);
	}
	
	/** 打印當前鏈表的節(jié)點信息 */
	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é)點data7，即不存在的節(jié)點 */
	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é)點data8，即存在的節(jié)點 */
	p = my_list_query_node(&data8, LIST_FROM_TAIL_TO_HEAD);
	if (p) {
		printf("node %d,%s, found ok !!!\n", data8.index, data8.msg);
	}
	
	/** 打印當前鏈表的節(jié)點信息 */
	printf("\n\n\n");
	my_list_print(2);
	printf("\n\n\n");
	
	/** 刪除一個存在于鏈表中的節(jié)點 */
	retval = my_list_delete_node(&data4);
	if (!retval) {
		printf("node %d,%s, delete ok !!!\n", data4.index, data4.msg);
	}	
	printf("\n\n\n");
	
	/** 再次查詢剛剛已刪除的節(jié)點 */
	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");
	
	/** 刪除一個不存在于鏈表中的節(jié)點 */
	retval = my_list_delete_node(&data6);
	if (retval) {
		printf("node %d,%s, delete fail !!!\n", data6.index, data6.msg);
	}	
	
	/** 打印當前鏈表的節(jié)點信息 */
	printf("\n\n\n");
	my_list_print(3);
	printf("\n\n\n");
	
	/** 刪除鏈表的所有節(jié)點 */
	retval = my_list_delete_all_node();
	if (!retval) {
		printf("all list notes delete done !\n");
	}
	
	/** 打印當前鏈表的節(jié)點信息 */
	printf("\n\n\n");
	my_list_print(4);
	printf("\n\n\n");
	
	/** 銷毀鏈表 */
	retval = my_list_destory();
	if (!retval) {
		printf("list destory done !\n");
	}
	
	/** 打印當前鏈表的節(jié)點信息 */
	printf("\n\n\n");
	my_list_print(5);
	printf("\n\n\n");
	
	return retval;
}

[外鏈圖片轉(zhuǎn)存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-BAOzFCxb-1662955522821)(data:image/gif;base64,R0lGODlhAQABAPABAP///wAAACH5BAEKAAAALAAAAAABAAEAAAICRAEAOw==)]

在main函數(shù)中，我們使用了與單向鏈表一樣的測試案例，運行結果如下：

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 
==================================================

對比運行的結果，發(fā)現(xiàn)與單向鏈表的測試結果一致，證明2者的實現(xiàn)功能是一致。

那么在實際項目過程中，究竟使用單向鏈表還是雙向鏈表呢？這就要根據(jù)具體的項目需求，靈活使用，不同的應用場景使用不同的鏈表實現(xiàn)，也許能達到事半功倍的效果。

好了，本次關于Linux內(nèi)核的list.h的應用，就介紹到這里，如果有疑問，歡迎在評論席提出。感謝您的閱讀。