linux循环链表学习

ゝ一世哀愁。 2022-06-07 02:23 264阅读 0赞

看了linux循环链表，发现实现真的可以这么巧妙

可以用同样的一些链表函数，去操作不同数据的链表，回想一下，通常我们写的链表结构是否如下？

struct _node1
    {
         void *data;
         struct _node1 *next;
         struct _node1 *prev;
    }NODE1;
    
    struct _node2
    {
         void *data;
         struct _node2 *next;
         struct _node2 *prev;
    }NODE2;

此时要操作链表，例如add结点，函数是否通常定义为：

//将new结点添加到pos的后面（或前面）
     int list_add(NODE1 *pos, NODE1 *new)

ok，此时，如果你要添加的不是NODE1类型的结点，反而是另一种，如NODE2，那么上面的函数是不是就不适用了，你要重新写一个函数接口

int list_add(NODE2 *pos, NODE2 *new)

如果你要操作的再是存储另外类型的链表，那么是不是都要写一整套同样的函数，只是参数不同而已，好麻烦。肯定也很多人在想，我能不能实现一套函数接口，使得可以操作所有类型的链表呢？答案是可以的。linux内核双向循环链表的实现就是如此巧妙。

我们定义链表结点如下：

struct _head_list
    {
         struct _head_list *next;
         struct _head_list *prev;
    }head_list;
    
    
    struct _linux_node
    {
          void *data;
          head_list linux_list;//这个就是巧妙之处1
    }linux_node;

我们添加一个add函数如下，注意参数类型哦，

int list_add(head_list *new, head_list *pos);
    
    //调用方式如下
    struct _linux_node node_new;
    head_list data_list;
    list_add(&node_new, &data_list);

这时有人会奇怪，你添加的并不是struct \_linux\_node类型，那么里面的data添加进去了吗，怎么能够取出来data啊。ok，接着是linux结点的最强大之处了，我们先看几个宏，

#define list_entry(ptr, type, member) \
    		((type *)((char *)(ptr) - (unsigned long)(&((type *)0)->member)))

解释一下这个宏，ptr为指向宿主类型（即struct \_linux\_node)中linux\_list成员的指针，type即struct \_linux\_node，member为struct \_linux\_node中的成员linux\_list.

&(((type \*)0)->member)，将0转为指向type类型的指针，0为内存首地址，那么member的地址就为member偏离宿主结点起始地址的大小，

(char \*)(ptr)-(unsigned long)(&(((type \*)0)->member))即为宿主结构的起始地址了。

struct _linux_node *tmp_data = NULL;
    
    tmp_data = list_entry(pos, linux_node, linux_list);

tmp\_data得到的就是指向linux\_node类型的指针，这个时候我们就可以用tmp\_data->data来取得结点中的数据了。

下面贴上自己学习过程中实现的linux\_list.c, linux\_list.h,test.c代码，test代码写的有点乱，大家将就着看吧。

linux\_list.h

/*
     * linux_list.h
     *
     *  Created on: Jul 30, 2012
     *      Author: Carl
     */
    
    #ifndef LINUX_LIST_H_
    #define LINUX_LIST_H_
    
    struct list_head
    {
    	struct list_head *next;
    	struct list_head *prev;
    };
    
    //这个宏已经在stddef.h中定义了
    //#define offsetof(type, member)		((size_t)&((type *)0)->member)
    
    //通过这个宏可以得到宿主结构体的指针，这个是linux链表的真正强大之处
    #define list_entry(ptr, type, member) \
    		((type *)((char *)(ptr) - (unsigned long)(&((type *)0)->member)))
    
    //pos为struct list_head类型的指针
    #define list_for_each(pos, head) \
    	for (pos = (head)->next; pos != (head); pos = pos->next)
    
    #define __list_for_each(pos, head) \
    	for (pos = (head)->next; pos != (head); pos = pos->next)
    
    #define list_for_each_prev(pos, head) \
    	for (pos = (head)->prev; pos != (head); pos = pos->prev)
    
    #define __list_for_each_prev(pos, head) \
    	for (pos = (head)->prev; pos != (head); pos = pos->prev)
    
    //safe仅仅体现在，可以遍历的同时删除pos结点，但删除非pos结点是unsafe的
    #define list_for_each_safe(pos, n, head) \
    	for (pos = (head)->next, n = pos->next; pos != (head); pos = n, n = pos->next)
    
    //pos为指向宿主类型的指针，head是头结点，即data_list，member是宿主成员struct list_head list
    #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))
    
    #define list_for_each_entry_reverse(pos, head, member)		\
    	for (pos = list_entry((head)->prev, typeof(*pos), member);		\
    		 &pos->member != (head);			\
    		pos = list_entry(pos->mmeber.prev, typeof(*pos), member))
    
    #define list_prepare_entry(pos, head, member) 		\
    	((pos) ? :list_entry(head, typeof(*pos), member))
    
    #define list_for_each_entry_continue(pos, head, member)		\
    	for (pos = list_entry(pos->member.next, typeof(*pos), member);		\
    		 &pos->member != (head);			\
    		pos = list_entry(pos->member.next, typeof(*pos), member))
    
    
    #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(*pos), member))
    
    //链表初始化
    void list_init(struct list_head *list);
    
    //在head之后插入新结点，head不一定是头结点
    void list_add(struct list_head *new, struct list_head *head);
    
    //在head之前插入新结点，如果head为头结点，那么head->prev要指向一个数值，一般指向尾结点，构成循环链表
    void list_add_tail(struct list_head *new, struct list_head *head);
    
    //删除结点entry
    void list_del(struct list_head *entry);
    
    //删除结点entry，并用entry来初始化创建新的链表
    void list_del_init(struct list_head *entry);
    
    //将list结点移动到head和head->next两个结点之间
    void list_move(struct list_head *list, struct list_head *head);
    
    //将list结点移动到head->prev和head两个结点之间
    void list_move_tail(struct list_head *list, struct list_head *head);
    
    //判断链表是否为空
    int list_empty(const struct list_head *head);
    int list_empty_careful(const struct list_head *head);
    
    //将list插入到head中,head和head->next之间，list的链表头被抛弃了
    void list_splice(struct list_head *list, struct list_head *head);
    
    //将list插入到head中，并初始化list被抛弃的链表头
    void list_splice_init(struct list_head *list, struct list_head *head);
    
    #endif /* LINUX_LIST_H_ */

linux\_list.c

/*
     * linux_list.c
     *
     *  Created on: Jul 30, 2012
     *      Author: Carl
     */
    
    
    //#include <stdio.h>
    #include <stdlib.h>
    #include "linux_list.h"
    
    
    
    
    void list_init(struct list_head *list)
    {
    	list->next = list;
    	list->prev = list;
    }
    
    // 在两个非空结点中插入一个结点，new, prev, next均不能为空
    static void __list_add(struct list_head *new, struct list_head *prev, struct list_head *next)
    {
    	next->prev = new;
    	new->next = next;
    	new->prev = prev;
    	prev->next = new;
    }
    
    
    void list_add(struct list_head *new, struct list_head *head)
    {
    	__list_add(new, head, head->next);
    }
    
    
    void list_add_tail(struct list_head *new, struct list_head *head)
    {
    	__list_add(new, head->prev, head);
    }
    
    //删除prev和next之间的结点
    static void __list_del(struct list_head *prev, struct list_head *next)
    {
    	next->prev = prev;
    	prev->next = next;
    }
    
    
    void list_del(struct list_head *entry)
    {
    	__list_del(entry->prev, entry->next);
    	entry->prev = NULL;
    	entry->next = NULL;
    }
    
    
    void list_del_init(struct list_head *entry)
    {
    	__list_del(entry->prev, entry->next);
    	list_init(entry);
    }
    
    
    void list_move(struct list_head *list, struct list_head *head)
    {
    	__list_del(list->prev, list->next);
    	list_add(list, head);
    }
    
    
    void list_move_tail(struct list_head *list, struct list_head *head)
    {
    	__list_del(list->prev, list->next);
    	list_add_tail(list, head);
    }
    
    int list_empty(const struct list_head *head)
    {
    	return head->next == head;
    }
    
    int list_empty_careful(const struct list_head *head)
    {
    	return (head->next == head) && (head->prev == head);
    }
    
    static void __list_splice(struct list_head *list, struct list_head *head)
    {
    	struct list_head *first = list->next;
    	struct list_head *last = list->prev;
    	struct list_head *at = head->next;
    
    	first->prev = head;
    	head->next = first;
    
    	last->next = at;
    	at->prev = last;
    }
    
    void list_splice(struct list_head *list, struct list_head *head)
    {
    	if (!list_empty(list))
    	{
    		__list_splice(list, head);
    	}
    }
    
    void list_splice_init(struct list_head *list, struct list_head *head)
    {
    	if (!list_empty(list))
    	{
    		__list_splice(list, head);
    		list_init(list);
    	}
    }

test.c

/*
     * test.c
     *
     *  Created on: Jul 30, 2012
     *      Author: Carl
     */
    
    
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #include "linux_list.h"
    
    typedef struct _data
    {
    	int version;
    	char str[20];
    	struct list_head list;
    }data;
    
    
    
    int NODE_NUM =	5;
    
    int main()
    {
    	data *pdata = NULL, *pdata2 = NULL;
    	data *tmp_data = NULL;
    	struct list_head data_list, data_list2;
    	struct list_head *pos = NULL, *n = NULL;
    	int i = 0;
    
    	list_init(&data_list);
    	list_init(&data_list2);
    
    	pdata = (data *)malloc(sizeof(data) * 5);
    	if (pdata == NULL)
    	{
    		printf("malloc for pdata error\n");
    		return -1;
    	}
    
    	pdata2 = (data *)malloc(sizeof(data) * 5);
    	if (pdata2 == NULL)
    	{
    		printf("malloc for pdata2 error\n");
    		return -1;
    	}
    
    	memset(pdata, 0, sizeof(data));
    	memset(pdata2, 0, sizeof(data));
    	for (i = 0; i < NODE_NUM; i++)
    	{
    		sprintf(pdata[i].str, "version%d", i+1);
    		sprintf(pdata2[i].str, "version%d", i+4);
    		pdata[i].version = i+1;
    		pdata2[i].version = i+4;
    		list_add(&(pdata[i].list), &data_list);
    		list_add(&(pdata2[i].list), &data_list2);
    	}
    
    	list_for_each_entry(tmp_data, &data_list, list)
    	{
    		printf("version: %d, \tversion str: %s\n", tmp_data->version, tmp_data->str);
    	}
    
    	goto End;
    
    	printf("data_list 链表\n");
    //	for(pos = data_list.next, i = 0; pos != NULL && i < NODE_NUM; pos = pos->next, i++)
    	list_for_each_safe(pos, n, &data_list)
    	{
    		tmp_data = list_entry(pos, data, list);
    		printf("version: %d, \tversion str: %s\n", tmp_data->version, tmp_data->str);
    		list_del(pos);
    	}
    
    	printf("data_list2 链表\n");
    	for(pos = data_list2.next, i = 0; pos != NULL && i < NODE_NUM; pos = pos->next, i++)
    	{
    		tmp_data = list_entry(pos, data, list);
    		printf("version: %d, \tversion str: %s\n", tmp_data->version, tmp_data->str);
    	}
    
    	list_splice(&data_list, &data_list2);
    
    	printf("data_list, data_list2合并以后\n");
    	for(pos = data_list2.next; pos != &data_list2; pos = pos->next)
    	{
    		tmp_data = list_entry(pos, data, list);
    		printf("version: %d, \tversion str: %s\n", tmp_data->version, tmp_data->str);
    	}
    
    	goto End;
    
    	//循环读出list中每个结点的数据部分
    	for(pos = data_list.next, i = 0; pos != NULL && i < NODE_NUM; pos = pos->next, i++)
    	{
    		tmp_data = list_entry(pos, data, list);
    		printf("version: %d, \tversion str: %s\n", tmp_data->version, tmp_data->str);
    	}
    
    	if (list_empty(&data_list))
    	{
    		printf("使用list_empty()检测，链表为空\n");
    	}
    	else
    	{
    		printf("使用list_empty()检测，链表非空\n");
    	}
    
    	if (list_empty_careful(&data_list))
    	{
    		printf("使用list_empty_careful()检测，链表为空\n");
    	}
    	else
    	{
    		printf("使用list_empty_careful()检测，链表非空\n");
    	}
    
    //	list_del(&pdata[3].list);
    //	NODE_NUM--;
    //	printf("pdata[3] is deleted\n");
    
    	list_move(&pdata[3].list, &data_list);
    	printf("将pdata[3]移至head和head->next两个结点之间\n");
    	//循环读出list中每个结点的数据部分
    	for(pos = data_list.next, i = 0; pos != NULL && i < NODE_NUM; pos = pos->next, i++)
    	{
    		tmp_data = list_entry(pos, data, list);
    		printf("version: %d, \tversion str: %s\n", tmp_data->version, tmp_data->str);
    	}
    
    //	list_del_init(&pdata[2].list);
    //	printf("pdata[2] is deleted\n");
    //	NODE_NUM--;
    
    	list_move_tail(&pdata[2].list, &data_list);
    	printf("将pdata[2]移至head->prev和head两个结点之间\n");
    	//循环读出list中每个结点的数据部分
    	for(pos = data_list.next, i = 0; pos != NULL && i < NODE_NUM; pos = pos->next, i++)
    	{
    		tmp_data = list_entry(pos, data, list);
    		printf("version: %d, \tversion str: %s\n", tmp_data->version, tmp_data->str);
    	}
    
    End:
    	free(pdata);
    
    	return 0;
    
    }

建议代码一定要自己写一遍，千万不要直接粘贴复制编译运行。

水平有限，如果有朋友发现错误，欢迎留言交流。

转载请保留本文链接，如果觉得我的文章能帮到您，请顶一下。，谢谢。