双向链表
1、 数据结构分析
在litLib.h中定义了操作双向链表的基类
typedef struct _Vx_node /* Node of a linked list. */
{
struct _Vx_node *next; /* Points at the next node in the list */
struct _Vx_node *previous; /* Points at the previous node in the list */
} _Vx_NODE;
只有一个指向上一个和指向下一个的指针,数据内容会继承该类。
typedef struct /* Header for a linked list. */
{
_Vx_NODE node; /* Header list node */
int count; /* Number of nodes in list */
} _Vx_LIST;
LIST是一个指向当前操作的数据头一个指针,包含一个计数器成员。
以下是操作链表的API:
extern void lstLibInit (void);
extern NODE * lstFirst (LIST *pList);
extern NODE * lstGet (LIST *pList);
extern NODE * lstLast (LIST *pList);
extern NODE * lstNStep (NODE *pNode, int nStep);
extern NODE * lstNext (NODE *pNode);
extern NODE * lstNth (LIST *pList, int nodenum);
extern NODE * lstPrevious (NODE *pNode);
extern int lstCount (LIST *pList);
extern int lstFind (LIST *pList, NODE *pNode);
extern void lstAdd (LIST *pList, NODE *pNode);即可
extern void lstConcat (LIST *pDstList, LIST *pAddList);
extern void lstDelete (LIST *pList, NODE *pNode);
extern void lstExtract (LIST *pSrcList, NODE *pStartNode, NODE *pEndNode,
LIST *pDstList);
extern void lstFree (LIST *pList);
extern void lstInit (LIST *pList);
extern void lstInsert (LIST *pList, NODE *pPrev, NODE *pNode);
2、双向链表的使用实例
- 首先需要定义用户数据,每个用户数据是一个节点,需要继承自node类。
struct USER_DATA{
_Vx_NODE LIST;
user_data; //用户数据
}
- 定义好用户数据以后,需要对链表进行初始化,使用Vxworks为我们提供的 void lstInit (LIST *pList);该函数需要传入一个头节点,直接传入我们定义的用户数据即可。
- 接下来接可以使用API进行数据的添加,删除等操作。下面是具体的实例:
#include<stdio.h>
#include "vxWorks.h"
#include "taskLib.h"
#include "sysLib.h"
#include "stdlib.h"
#include "string.h"
#include "lstLib.h"
typedef struct buf_D{
NODE node;
int buf[2];
}BUF_D;
typedef BUF_D BUF;
LIST *mylist()
{
LIST *buf_drps = (LIST*)malloc(sizeof(LIST*)); //初始化链表
lstInit(buf_drps);
BUF *buf=(BUF *)malloc(sizeof(BUF)); //给链表添加一个节点
buf->buf[0]=1;
buf->buf[1]=2;
lstAdd(buf_drps,buf);
BUF *buf2=(BUF *)malloc(sizeof(BUF)); //给链表添加一个节点
buf2->buf[0]=3;
buf2->buf[1]=4;
lstAdd(buf_drps,buf2);
BUF *buf3=(BUF *)malloc(sizeof(BUF)); //给链表添加一个节点
buf3->buf[0]=5;
buf3->buf[1]=6;
lstAdd(buf_drps,buf3);
return buf_drps;
}
#define TASK_PR 90
int taskid;
int buf[10];
void test_task(void) //新任务
{
BUF *buf_drps=mylist();
printf("%d",lstCount(buf_drps));
while(buf_drps->node.next)
printf("%d",((BUF *)lstGet(buf_drps))->buf[1]);
taskDelay(sysClkRateGet()/2);
printf("%d",lstCount(buf_drps));
}
int main()
{
taskid = taskSpawn("tDemo",TASK_PR,VX_NO_STACK_FILL,4000,(FUNCPTR)test_task,0,0,0,0,0,0,0,0,0,0);
taskDelay(sysClkRateGet());
return 0;
}
环形缓冲
数据结构
在rngLib.h中定义了环形缓冲区的数据结构:
typedef struct /* RING - ring buffer */
{
size_t pToBuf; /* offset from start of buffer where to write next */
size_t pFromBuf; /* offset from start of buffer where to read next */
size_t bufSize; /* size of ring in bytes */
char *buf; /* pointer to start of buffer */
} RING;
从以上代码可以看出,环形缓冲区的使用需要直接定义缓冲区的大小,该缓冲区以字节为单位进行数据的存储。通过两个位置指针来确定当前的数据状态。
在RING_ID rngCreate ( size_t nbytes )中做了以下几步:
-
RING_ID ringId = (RING_ID) malloc (sizeof (RING)); //为环形缓冲区分配了数据空间
-
buffer = (char *) malloc (++nbytes); //为数据分配空间(注意在buffer被定义成指针,因此需要为其分配内存空间。这看起来有点像C++拷贝构造的意思)。
ringId->bufSize = nbytes;
ringId->buf = buffer;
rngFlush (ringId); //这个函数是给缓冲区数据清零,我们知道当怕P->read=P->write=0时,是环形缓冲区为空的条件。也就是把缓冲区清空。
return (ringId); //返回一个操作句柄
VXworks为我们提供了缓冲区的一些常用的API函数:
extern BOOL rngIsEmpty (RING_ID ringId);
extern BOOL rngIsFull (RING_ID ringId);
extern RING_ID rngCreate (size_t nbytes);
extern size_t rngBufGet (RING_ID rngId, char *buffer, size_t maxbytes);
extern size_t rngBufPut (RING_ID rngId, char *buffer, size_t nbytes);
extern size_t rngFreeBytes (RING_ID ringId);
extern size_t rngNBytes (RING_ID ringId);
extern void rngDelete (RING_ID ringId);
extern void rngFlush (RING_ID ringId);
extern void rngMoveAhead (RING_ID ringId, size_t n);
extern void rngPutAhead (RING_ID ringId, char byte, size_t offset);
有这些函数我们就能够轻松的操作环形缓冲区了。
环形缓冲区操作实例
void ring_test()
{
RING_ID *buf_id;
size_t num=0;
char read_buf[3];
buf_id = rngCreate(64); //分配64字节空间
const char *const str = "hello ring";
rngBufPut(buf_id,str,(strlen(str)+1)); //写入缓冲区
num = rngNBytes(buf_id);
printf("%d\n",num);
rngBufGet(buf_id,read_buf,2); //读取两个字符
read_buf[2]='\0';
printf("%s\n",read_buf);
num = rngNBytes(buf_id);
printf("%d\n",num);
}
可以看到,把11个字符放入缓冲区,”读走两个以后“,还剩下9个。