实时系统vxWorks - 双向链表（含源码分析）

概述

作为一个嵌入式开发人员，每天都在和各种各样的数据打交道，如何高效的管理数据，规划内存，对于我们显得尤为重要。常用的数据结构有链表、栈、队列、二叉树等，如果这些都要依靠程序猿自己实现，这无疑会加大我们的工作量，而且也不是每个程序猿都能很好、很稳定的实现这些结构和功能。

对于单片机等裸机而言，这些结构只能靠开发人员自己来实现，但如果你跟我一样，是基于操作系统来开发项目，由于操作系统的底层同样需要用到数据结构来管理自己的资源、任务等，所以在系统里实现了这些数据结构，而幸运的是，这些接口对于开发者完全透明开放，我们可以直接拿来使用。

vxwroks 双向链表模块主要定义在lstLib.c和lstLib.h中，链表本身属于线性存储，每个链表元素我们简称为节点，每个节点由数据域和指针域两部分构成，数据域用来存储数据，而指针域则用来链接相邻的元素。具体原理感兴趣的小伙伴可以参考小编的文章《也没想象中那么神秘的数据结构-一环扣一环的“链表”（双链表）》。

注意

开发环境：vxWorks6.9.4、workbench3.3.5。

另外，小编所有文章均是自己亲手编写验证，由于文件太多，小编就不在公众号后台一一回复列举了，若需要小编的工程代码，请关注公众号，后台回复需要的工程文件。如想要本文中的工程源文件可回复“实时系统vxWorks - 双向链表应用工程文件”，小编看到后会第一时间回复。

以下为工程目录文件内容。有需要的小伙伴后台发送相关信息给小编获取。

文件内容如下：

obj：存放目标文件，包含vxWorks镜像，应用程序目标文件。

list_test：vxWorks应用工程。

接口

官方提供的关于双向链表的相关接口主要包含在lstLib.h头文件中。

双向链表接口定义

/* 双向链表接口定义 lstLib.h  */

/* 链表节点信息定义 */
typedef struct _Vx_node {
    struct _Vx_node *next;		/* 指向下一个元素 */
    struct _Vx_node *previous;	/* 指向前一个元素 */
}_Vx_NODE;

/* 链表头信息定义 */
typedef struct {
    _Vx_NODE node;		/* 头结点 */
    int count;			/* 链表节点数量 */
}_Vx_LIST;

typedef _Vx_NODE NODE;
typedef _Vx_LIST LIST;


/* 链表端点定义 */
#define	HEAD	node.next		/* 链表头定义，链表的第一个元素 */
#define	TAIL	node.previous	/* 链表尾定义，链表的最后一个元素 */

初始化操作

/* 
 * @ 链表初始化
 * @ pList - 指向整个链表
 */
void lstInit (LIST *pList);

查找操作

/* 
 * @ 获取链表头节点
 * @ pList - 指向整个链表
 * @ 返回节点地址
 */
NODE *lstFirst(LIST *pList);
/* 
 * @ 获取链表尾节点
 * @ pList - 指向整个链表
 * @ 返回节点地址
 */
NODE *lstLast(LIST *pList);
/* 
 * @ 获取指定节点的下一个节点
 * @ pNode - 指定节点
 * @ 返回节点地址
 */
NODE *lstNext(NODE *pNode);
/* 
 * @ 获取指定节点的前一个节点
 * @ pNode - 指定节点
 * @ 返回节点地址
 */
NODE *lstPrevious(NODE *pNode);

/* 
 * @ 获取距离指定节点指定步长的节点地址
 * @ pNode - 指定节点		nStep - 步长，>0向后偏移，<0向前偏移
 * @ 返回节点地址
 */
NODE *lstNStep(NODE *pNode, int nStep);

/* 
 * @ 获取链表中第n个节点地址
 * @ pList - 指向整个链表		nodenum - 节点序号
 * @ 返回节点地址
 */
NODE *lstNth(LIST *pList, int nodenum)
{
    FAST NODE *pNode;

    /* verify node number is in list */
    if ((nodenum < 1) || (nodenum > pList->count))
		return (NULL);

	/* 节点在链表前半段，从前往后找。否则，从后往前找 */
    if (nodenum < (pList->count >> 1)) {
		pNode = pList->HEAD;
		while (--nodenum > 0)
			pNode = pNode->next;
	} else {	
		nodenum -= pList->count;
		pNode = pList->TAIL;
		while (nodenum++ < 0)
			pNode = pNode->previous;
	}
	return (pNode);
}

/* 
 * @ 查找指定节点在链表中的位置（注：头结点序号为1）
 * @ pList - 指向整个链表		pNode - 待查找的节点
 * @ 找到返回节点序号，否则返回ERROR
 */
int lstFind(LIST *pList, NODE *pNode)

/* 
 * @ 获取链表中头结点地址，并从链表中删除
 * @ pList - 指向整个链表
 * @ 返回节点地址
 */
NODE *lstGet(LIST *pList);
/* 
 * @ 获取链表长度（节点个数）
 * @ pList - 指向整个链表
 * @ 返回链表长度
 */
int lstCount(LIST *pList);

插入操作

/* 
 * @ 插入新节点到链表指定节点的后面
 * @ pList - 指向整个链表		pPrev - 指定节点	pNode - 待插入的节点
 */
void lstInsert(LIST *pList, NODE *pPrev, NODE *pNode)
{
	FAST NODE *pNext;

    if (pPrev == NULL) {	/* 插入到头结点 */
		pNext = pList->HEAD;
		pList->HEAD = pNode;
	} else {			
		pNext = pPrev->next;
		pPrev->next = pNode;
	}

    if (pNext == NULL)		/* 插入到尾节点 */
		pList->TAIL = pNode;
    else
		pNext->previous = pNode;


    pNode->next		= pNext;
    pNode->previous	= pPrev;

    pList->count++;	
}
/* 
 * @ 添加指定节点到链表（添加到表尾）
 * @ pList - 指向整个链表		pNode - 待添加的节点
 */
void lstAdd (LIST *pList, NODE *pNode);

删除操作

/* 
 * @ 从链表中删除指定节点	
 * @ pList - 指向整个链表		pNode - 待删除的节点
 */
void lstDelete (LIST *pList, NODE *pNode);

/* 
 * @ 销毁整个链表	
 * @ pList - 指向整个链表		freeFunc - 销毁节点的函数指针（这里主要调用free函数）
 */
void lstFree2(LIST *pList, LST_FREE_RTN freeFunc)
{
	NODE *p1, *p2;

    if (pList->count > 0) {
		p1 = pList->HEAD;

		/* 依次销毁所有节点 */
		while (p1 != NULL) {
			p2 = p1->next;
			freeFunc ((void *)p1);
			p1 = p2;
		}

		pList->count = 0;
		pList->HEAD = pList->TAIL = NULL;
	}
}

/* 
 * @ 销毁链表	
 * @ pList - 指向整个链表
 */
void lstFree (LIST *pList)
{
	lstFree2(pList, (LST_FREE_RTN) free);
}

合并与分离操作

/* 
 * @ 将指定链表到连接到目的链表的末尾	
 * @ pDstList - 目的链表		pAddList - 需要连接的链表
 */
void lstConcat(LIST *pDstList, LIST *pAddList)
{
	if (pAddList->count == 0)	/* 情况1. 待连接链表为空，无需处理 */
		return;

	if (pDstList->count == 0) {	/* 情况2. 目的链表为空，目的链表指向待连接链表即可 */
		*pDstList = *pAddList;
	} else {					/* 情况3. 目的链表和指定链表均不为空，将指定链表连接到目的链表之后 */
		pDstList->TAIL->next     = pAddList->HEAD;
		pAddList->HEAD->previous = pDstList->TAIL;
		pDstList->TAIL           = pAddList->TAIL;

		pDstList->count += pAddList->count;
	}

	lstInit(pAddList);	/* 设置添加链表为空链表 */
}

/* 
 * @ 摘取取指定起始节点之间的所有节点，形成新的链表（提取子链）	
 * @ pSrcList - 源链表		pDstList - 目的链表（新链表）
 * @ pStartNode - 起始节点	pEndNode - 结束节点
 */
void lstExtract (LIST *pSrcList, NODE *pStartNode, NODE *pEndNode, LIST *pDstList)
{
	FAST int i;
    FAST NODE *pNode;

	/* 步骤1. 从原链表中摘取子链，主要分两步实现：
	1). 让待摘取的开始节点的上一个节点的后向指针指向待摘取结束节点的下一个节点 
	2). 让待摘取的结束节点的下一个节点的前向指针指向待摘取起始节点的上一个节点 
	*/
    if (pStartNode->previous == NULL)		/* 从头结点开始截取 */
		pSrcList->HEAD = pEndNode->next;
    else
		pStartNode->previous->next = pEndNode->next;

    if (pEndNode->next == NULL)				/* 截取到尾节点 */
		pSrcList->TAIL = pStartNode->previous;
    else
		pEndNode->next->previous = pStartNode->previous;

	/* 步骤2. 将摘取的子链合成一个新的链表，并存储在pDstList中 */
    pDstList->HEAD = pStartNode;
    pDstList->TAIL = pEndNode;

    pStartNode->previous = NULL;
    pEndNode->next       = NULL;

	/* 步骤3. 计算子链的长度 */
    i = 0;
    for (pNode=pStartNode; pNode!=NULL; pNode=pNode->next)
		i++;

	/* 步骤4. 更新原链表和子链的长度 */
    pSrcList->count -= i;
    pDstList->count = i;
}

示例

★示例通过创建自定义节点，调用系统lstLib.h库里的操作函数，实现双向链表的相关操作验证。

★示例仅用于展示双向链表的应用，代码内容并无实际意义，在实际应用中，用户可以参考小编的代码根据项目需要创建自己的节点属性，再调用系统库函数实现双向链表的相关数据管理。

★包含演示程序main.c（已验证通过）。

?main.c

/**
 * @Filename : main.c
 * @Revision : $Revision: 1.00 $
 * @Author : Feng(更多编程相关的知识和源码见微信公众号：不只会拍照的程序猿，欢迎订阅)
 * @Description : 双向链表使用示例
**/

#include <vxWorks.h>     
#include <math.h>    
#include "stdioLib.h"     
#include "strLib.h"     
#include "feng_type.h"
#include <lstLib.h>

/* 自定义节点信息,注意NODE必须放前面，涉及到面向对象里继承的特点，否则处理会麻烦很多 */
struct t_node {
	NODE fnode;	/* 链表基本节点,用系统提供定义方式，包含前向指针和后向指针 */
	char ch;	/* 存储字符信息 */
};

/**
 * @ 创建一个新的节点
 * @ ch - 节点值
 * @ 成功返回节点地址，失败返回NULL
 */
static struct t_node *_create_node(char ch)
{
	struct t_node *p_node = NULL;
	
	if ((p_node = (struct t_node *)malloc(sizeof(struct t_node))) == NULL) {
		printf("malloc error...\n");
		return NULL;
	}	
	
	p_node->fnode.next = NULL;
	p_node->fnode.previous = NULL;
	p_node->ch = ch;
	
	return p_node;
}

/**
 * @ 输出链表相关信息
 * @ list - 指向整个链表
 */
static void _print_list(LIST *list)
{
	struct t_node *p_node = (struct t_node *)lstFirst(list);

	while (p_node != NULL) {
		printf("%c", p_node->ch);
		p_node = (struct t_node *)lstNext((NODE *)p_node);
	}
	printf("\n");
}


int main(void)
{
	LIST flist, sublist;
	struct t_node *p_node = NULL, *p_node1 = NULL;
	char i, buf[15]={"hello feng!"};

	/* 初始化链表 */
	printf("--------------init-------------\n");
	lstInit(&flist);
	lstInit(&sublist);
	
	printf("flist count: %d\n", lstCount(&flist));
	printf("sublist count: %d\n", lstCount(&sublist));

	/* 插入元素 */
	printf("\n--------------insert-------------\n");
	for (i=0; i<11; i++) {	
		if ((p_node = _create_node(buf[i])) == NULL) {
			printf("create node error...\n");
			return -1;
		}	
		lstAdd(&flist, p_node);	
	}
	/* 打印当前链表内容 */
	printf("flist count[%d]:", lstCount(&flist));
	_print_list(&flist);

	/* 获取链表第四个节点信息 */
	printf("\n--------------find-------------\n");
	p_node = (struct t_node *)lstNth(&flist, 4);
	printf("flist the 4th node: %c\n", p_node->ch);
	
	/* 查找p_node节点在链表中的位置 */
	i = lstFind (&flist, (NODE *)p_node);
	printf("find node is number: %d\n", i);
	
	/* 获取链表第八个节点信息 */
	p_node1 = (struct t_node *)lstNth(&flist, 8);
	printf("flist the 8th node: %c\n", p_node1->ch);
		
	/* 将链表第四个节点到第八个节点截取出来 */
	printf("\n--------------extract-------------\n");
	lstExtract(&flist, (NODE *)p_node, (NODE *)p_node1, &sublist);
	printf("flist count[%d]:", lstCount(&flist));
	_print_list(&flist);
	printf("sublist count[%d]:", lstCount(&sublist));
	_print_list(&sublist);
	
	/* 将sublist链表连接到flist后面 */
	printf("\n--------------concat-------------\n");
	lstConcat(&flist, &sublist);
	printf("flist count[%d]:", lstCount(&flist));
	_print_list(&flist);
	
	/* 删除操作 */
	printf("\n--------------delete-------------\n");
	lstDelete(&flist, p_node);
	printf("flist count[%d]:", lstCount(&flist));
	_print_list(&flist);
	
	/* 销毁操作 */
	printf("\n--------------free-------------\n");
	lstFree(&flist);
	printf("flist count[%d]\n", lstCount(&flist));
	
	return 0;
}

验证

镜像工程

使用环形缓冲之前需要先添加INCLUDE_LSTLIB组件。

打开镜像工程，选择kernel Configuration。按住Ctrl+F，输入lst，找到linked list library，添加组件。

添加完组件后，编译镜像，将镜像拷贝到目标机加载指定目录。

应用工程

创建应用工程list_test，输入相关测试代码，运行后如下图所示。

注意：若不知道工程如何创建以及运行，可参见小编文章《实时系统vxWorks - 任务（重要）》和《实时系统vxWorks - 加载应用程序的方法》。

根据打印信息可以看到我们的双向链表各接口功能正常。

往期?·?推荐

实时系统vxWorks - 任务（重要）

实时系统vxWorks - 加载应用程序的方法

实时系统vxWorks - 在线调试

实时系统vxWorks - 虚拟机环境搭建

浅谈linux - 描述硬件的文件设备树

关注

更多精彩内容，请关注微信公众号：不只会拍照的程序猿，本人致力分享linux、设计模式、C语言、嵌入式、编程相关知识，也会抽空分享些摄影相关内容，同样也分享大量摄影、编程相关视频和源码，另外你若想要获得更多内容教程请关注公众号：不只会拍照的程序猿。