嵌入式C语言那点事（三）Linux中霸道的双向链表源码与应用

C语言作为面向过程的语言，想写出灵活的结构与封装需要很高技巧。

但由于C语言的高效，几乎所有操作系统和面向对象语言的最底层实现都使用了C语言。即，使用C完成面向对象的封装。

这次通过整理与仿写Linux的双向链表让我体会到了一些C语言封装的核心技巧。

这个双向链表的巧妙之处在于1）利用宏将“函数”入参扩展出了“结构类型”； 2）利用纯地址偏移获取结构体指针；

下面是具体实现：链表的实现由于是宏定义，都在libList.h中。

测试程序testList.c与testList.h。

libList.h

#ifndef _LIBLIST_H
#define _LIBLIST_H

#ifdef __cplusplus
extern "C" {
#endif

/* 链表头节点定义 */
typedef struct tagstList_Head {
	struct tagstList_Head *next, *prev;
}stList_Head;

/* 初始化双向链表 */
#define list_init(head) do			\
{						\
	(head)->next = (head)->prev = (head);	\
} while(0)

/* 在指定元素(where)之后插入新元素(item) */
#define list_add(item, towhere) do	\
{					\
	(item)->next = (towhere)->next;	\
	(item)->prev = (towhere);	\
	(towhere)->next = (item);	\
	(item)->next->prev = (item);	\
} while(0)

/* 在指定元素(where)之前插入新元素(item) */
#define list_add_before(item, towhere)  \
	list_add(item,(towhere)->prev)

/* 删除某个元素 */
#define list_remove(item) do			\
{						\
	(item)->prev->next = (item)->next;	\
	(item)->next->prev = (item)->prev;	\
} while(0)

/* 正向遍历链表中所有元素 */
#define list_for_each_item(item, head)\
	for ((item) = (head)->next; (item) != (head); (item) = (item)->next)

/* 反向遍历链表中所有元素 */
#define list_for_each_item_rev(item, head) \
	for ((item) = (head)->prev; (item) != (head); (item) = (item)->prev)

/* 根据本节点(item)获取节点所在结构体(type)的地址 */
/* 节点item地址(member的地址) - 该链表元素member在结构体中的偏移 */
#define list_entry(item, type, member) \
	((type *)((char *)item - (char *)(&((type *)0)->member)))

/* 判断链表是否为空 */
#define list_is_empty(head)	\
	((head)->next == (head))

/* 获取指定位置上一元素 */
#define list_prev_item(item)\
	((head)->prev)

#ifdef __cplusplus
}
#endif

#endif

testList.h

#ifndef _TESTLIST_H
#define _TESTLIST_H

#ifdef __cplusplus
extern "C" {
#endif

#include "libList.h"

typedef struct tagInteger
{
	int idx;
	stList_Head	stListHead;
}stInteger;

extern void testlist();

#ifdef __cplusplus
}
#endif

#endif

这种双向链表的特点在于：在需要链表管理的结构中定义一个链表节点变量，然后所有的操作都是针对这个链表节点进行的。在需要获取该结构时使用list_entry即可。

testList.c

#ifdef __cplusplus
extern "C" {
#endif

#include <malloc.h>
#include <stddef.h>
#include "stdafx.h"
#include "testList.h"

void testlist()
{
	int i = 0;
	stList_Head		stListHead;
	stList_Head		*pstListHead= NULL;

	stInteger		*pstInteger	= NULL;
	stList_Head		*pstTmpList	= NULL;

	/* 链表初始化 */
	pstListHead = &stListHead;
	list_init(pstListHead);

	/* 生成节点并挂入链表 */
	for(i = 0; i < 32; i++)
	{
		pstInteger = (stInteger *)malloc(sizeof(stInteger));
		if (NULL == pstInteger)
		{
			printf("pstInteger malloc fail!");
			return;
		}
		pstInteger->idx = 100 - i;

		/* 挂到头结点之前 */
		list_add_before(&pstInteger->stListHead, pstListHead);

		/* 挂到头结点之后 */
		//list_add(&pstInteger->stListHead, pstListHead);
	}
	
	/* 正向遍历链表中每一个元素并输出 */
	list_for_each_item(pstTmpList, pstListHead)
	{
		if(NULL != pstTmpList)
		{
			pstInteger = list_entry(pstTmpList, stInteger, stListHead);
			printf("%d ",pstInteger->idx);
		}
	}
	
	return;

}

#ifdef __cplusplus
{
#endif