Linux双向链表相关API的使用及事例Demo

一、相关宏函数功能的使用与介绍
1、offset

定义:offsetof的定义在linux内核include/linux/stddef.h中。
宏功能:获取结构体(TYPE)的成员变量(MEMBER)在此结构体中的偏移量

#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)
宏功能:获取结构体(TYPE)的成员变量(MEMBER)在此结构体中的偏移量
宏解析:
1((TYPE *)0)0强转为TYPE类型的指针,即TYPE类型的指针的地址为02((TYPE *)0)->MEMBER 访问结构体中的成员变量MEMBER
3&((TYPE *)0)->MEMBER 获取成员变量MEMBER的地址,由于TYPE的地址是0,这里获取的地址就是MEMBER在TYPE中的偏移。
4((size_t) &((TYPE *)0)->MEMBER) 结果转换类型,对于32位系统,size_t是unsigned int类型;对于64位系统,size_t是unsigned long类型
2、container_of

定义:container_of的定义在linux内核include/linux/kernel.h中
宏功能:根据结构体(TYPE)的成员变量(MEMBER)的指针(ptr)来获取整个结构体的指针。

#define container_of(ptr, type, member) ({			\
	const typeof( ((type *)0)->member ) *__mptr = (ptr);	\
	(type *)( (char *)__mptr - offsetof(type,member) );})
宏功能:根据结构体(TYPE)的成员变量(MEMBER)的指针(ptr)来获取整个结构体的指针。
宏解析:
1typeof( ((type *)0)->member ) 获取member成员变量的类型。
2const typeof( ((type *)0)->member ) *__mptr = (ptr) 定义与member类型相同的指针__mptr,并将ptr赋值给__mptr。
3(char *)__mptr 将__mptr转化为字节型指针。
4offsetof(type,member) 获取member在结构体中的偏移量。
5(char *)__mptr - offsetof(type,member) 用__mptr的地址来减去member在结构体中的偏移量,即可获取结构体的首地址。
6(type *)( (char *)__mptr - offsetof(type,member) ) 将结构体指针转化为type类型。
3、LIST_HEAD(header)

宏功能:创建一个链表头

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

#define LIST_HEAD_INIT(name) { &(name), &(name) }

#define LIST_HEAD(name) \
	struct list_head name = LIST_HEAD_INIT(name)
4、list_for_each_entry_safe

作用:list_for_each_entry_safe 是 Linux 内核中用于遍历双向链表的宏,它提供了一种安全的方式来遍历链表,即在遍历过程中可以安全地删除链表节点。这个宏特别有用,因为在遍历链表时直接删除节点可能会导致迭代器失效,从而引发错误。
使用方式:

#include <stdio.h>  
#include <stdlib.h>
#include <linux/list.h>  

list_for_each_entry_safe(pos, n, head, member)
pos:当前遍历到的节点指针的变量。
n:下一个节点指针的临时变量,用于在删除当前节点后继续遍历。
head:链表的头指针。
member:链表中节点结构体中 list_head 类型的成员名。
在遍历过程中,如果需要删除当前节点,可以使用 list_del 宏,然后安全地继续遍历,因为 n 保存了下一个节点的地址。

API内部的实现:

#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))
list_for_each_entry_safe,用指针n来对下一个结构体进行临时存储,如果删除链表中的当前项,使用list_for_each_entry_safe可以安全的删除,不会影响遍历过程。
5、list_del

作用:list_del 通常是用于从链表中删除一个指定节点的函数。这个函数会处理节点的前后指针,确保链表在删除节点后仍然保持正确的结构。在 Linux 内核或类似的环境中,list_del 函数对于管理链表数据结构是非常有用的。

使用方式:

void list_del(struct list_head *entry);

API的内部实现:

static inline void list_del(struct list_head *entry)
{
	__list_del(entry->prev, entry->next);
	entry->next = NULL;
	entry->prev = NULL;
}
static inline void __list_del(struct list_head * prev, struct list_head * next)
{
	next->prev = prev;
	prev->next = next;
}

6、插入相关API
6.1、 list_add–在表头插入

作用:list_add 是一个在 Linux 内核中常用的链表操作函数,用于将一个新元素添加到链表的头部。这个函数将新元素插入到链表的开始位置,并更新链表中的节点指针。
list_add的使用

void list_add(struct list_head *new, struct list_head *head);

API的内部实现:

static inline void list_add(struct list_head *new, struct list_head *head) // new:要添加的新的链表的首地址,head:链表的中的位置
{
	__list_add(new, head, head->next);
}

static INLINE void __list_add(struct list_head *newptr,
			      struct list_head *prev,
			      struct list_head *next)
{
	next->prev = newptr;
	newptr->next = next;
	newptr->prev = prev;
	prev->next = newptr;
}
6.2、 list_add_tail–在表尾插入

作用:list_add_tail 是一个常用于 Linux 内核链表操作的函数,它用于将一个新元素添加到链表的尾部。与 list_add 函数不同,list_add_tail 将新元素插入到链表的末尾,而不是头部。

void list_add_tail(struct list_head *new, struct list_head *head);
new 是指向要插入的新节点的指针。
head 是指向链表头节点的指针。

API的内部实现:

static inline void list_add_tail(struct list_head *n, struct list_head *head)
{
	__list_add(n, head->prev, head);
}
static INLINE void __list_add(struct list_head *newptr,
			      struct list_head *prev,
			      struct list_head *next)
{
	next->prev = newptr;
	newptr->next = next;
	newptr->prev = prev;
	prev->next = newptr;
}
7、LIST_HEAD_INIT

作用:LIST_HEAD_INIT 是 Linux 内核中用于初始化双向循环链表的宏。这个宏会创建一个静态的链表头,并初始化它,使得链表一开始就是空的。使用 LIST_HEAD_INIT 可以避免在运行时调用 INIT_LIST_HEAD 函数进行初始化,因为它在编译时就已经完成了初始化。
API的内部实现

#define LIST_HEAD_INIT(name) { &(name), &(name) }

#define LIST_HEAD(name) \
	struct list_head name = LIST_HEAD_INIT(name)
8、list_empty

作用:list_empty是一个常用于检查链表是否为空的函数。它可以帮助我们判断链表中是否有数据,是检测链表是否为空的基本要素。如果链表为空,返回true(或整数值1);否则,返回false(或整数值0)。

API的内部实现

static inline int list_empty(const struct list_head *head)
{
	return head->next == head;
}
二、事例Demo

用双向链表相关API实现对数据增删改查的功能。

#include <stdio.h>  
#include <stdlib.h>
#include <linux/list.h>  
  
// 定义链表节点结构体  
typedef struct{  
    int data;  
    int sn;
    struct list_head list;  
}my_list_node;  

static struct list_head my_list_head;
static mutex_t gMutex = PTHREAD_MUTEX_INITIALIZER;  // 对 gJT1078_PlayHead 进行操作时,需要加锁
static pthread_cond_t gCond = PTHREAD_COND_INITIALIZER;

void addNode(const my_list_node *newData) 
{  
	 if(NULL == my_list_head.next)
	{
		printf("it is not init\n");
		return ;
	}

	bool isExist = false;
	my_list_node *node = NULL, *tmp = NULL;
    my_list_node *new_node = (my_list_node *)malloc(sizeof(my_list_node),);  
    if (!new_node) {  
    	printf("malloc failed");
        return;  
    }  
    pthread_mutex_lock(&gMutex); //加上线程锁,防止资源竞争
    list_for_each_entry_safe(node,tmp,&my_list_head,list)
    {
		if(node->sn== newData->sn)
		{
			isExist = true;//该组数据存在不添加到链表
		}
	}
	if(!isExist)
	{
	    new_node->data = newData->data;  
    	list_add_tail(&new_node->list, &my_list_head); 
    	pthread_cond_signal(&gCond); //告知有新的任务,唤醒线程 
	}
    pthread_mutex_unlock(&gMutex);
	if(new_node) //申请的堆空间及时释放
	{
		free(new_node);
		new_node = NULL;
	}
}

void delNode(const my_list_node *delNodeData) 
{
    if(NULL == my_list_head.next)
	{
		printf("it is not init\n");
		return ;
	}
	
	my_list_node *node = NULL, *tmp = NULL;
	pthread_mutex_lock(&gMutex);
	list_for_each_entry_safe(node,tmp,&my_list_head,list)
	{
		if(delNodeData->sn == node->sn)
		{
			list_del(&node->list);  
			free(node);
		}
	}
	pthread_mutex_unlock(&gMutex);
}

void updateNode(const my_list_node *updtaNodeData) 
{
    if(NULL == my_list_head.next)
	{
		printf("it is not init\n");
		return ;
	}
	
	my_list_node *node = NULL, *tmp = NULL;
	pthread_mutex_lock(&gMutex);
	list_for_each_entry_safe(node,tmp,&my_list_head,list)
	{
		if(updtaNodeData->sn == node->sn)
		{
			node->data = updtaNodeData->data;
		}
	}
	pthread_mutex_unlock(&gMutex);
}

my_list_node *findNode(const my_list_node *findNodeData) 
{
    if(NULL == my_list_head.next)
	{
		printf("it is not init\n");
		return ;
	}
	
	my_list_node *node = NULL, *tmp = NULL;
	pthread_mutex_lock(&gMutex);
	list_for_each_entry_safe(node,tmp,&my_list_head,list)
	{
		if(findNodeData->sn == node->sn)
		{
			return node;
		}
	}
	pthread_mutex_unlock(&gMutex);
}

int main()
{
	int iRet= -1;
	my_list_head = LIST_HEAD_INIT(my_list_head);
	my_list_node *node = NULL, *tmp = NULL;

	while (1) {

		//等待数据
	    pthread_mutex_lock(&gMutex);
        iRet = list_empty(&my_list_head);
        if (iRet) {
            pthread_cond_wait(&gCond, &gMutex);
        }
        pthread_mutex_unlock(&gMutex);
        if (iRet) {
            continue;
        }

	    pthread_mutex_lock(&gMutex);
		list_for_each_entry_safe(node,tmp,&my_list_head,list)
		{
			//数据处理。。。
		}
		pthread_mutex_unlock(&gMutex);
	
	}
}

上一篇:父类子类构造方法调用示例


下一篇:再次度过我的创作纪念日-日常