基于C语言实现环形缓冲区/循环队列-c语言中循环队列是什么意思

这里分享一个自己用纯C实现的环形缓冲区。

环形缓冲区有很多作用，比如嵌入式中的通信可以用环形缓冲区作为信道，一个线程往里放字节，一个线程取字节进行处理，只要保证取的速度大于读的速度，就可以保证通信顺畅进行，不丢一个字节。

简要介绍：

环形缓冲区其实就是一个队列，里头的元素是先入先出的，但是因为其(逻辑上)是环形的，所以不需要像很多队列的实现那样在内部元素变动的时候需要移动内部剩下的元素。这样就使元素出队入队的时间复杂度只有O(1)。具体实现一般有链表和数组两种方法，当不能确定需要的缓冲区大小时使用链表较好，能确定时使用数组可以节省很多动态分配内存的开销。

在嵌入式开发中，一般不动态分配内存，而是使用静态分配的数组。所以这里我使用数组实现了环形缓冲区，为了能够在不同的程序中复用代码，使用结构体模拟了面向对象编程，这样就可以用一套代码管理不同的缓冲区了。

废话不多说，直接上代码。以下是.h 文件：

/* ********************************************************************************************************* * * *RingQueueStruct *环形队列结构 * *File:RingQueue.h *By:LinShijun(http://blog.csdn.net/lin_strong) *Date:2018/02/23 *version:V1.2 *NOTE(s):这段程序用来对一个给定的缓冲区进行模拟环形队列的管理 *程序本身不会自动分配缓冲区空间,用户需要自己负责分配空间,并且要保证不直接访问缓存区 *//在某处分配内存空间 *RQTYPEbuffer[BUFFER_SIZE]; *RING_QUEUEque,*ptr_que; *unsignedcharerr; *//初始化 *ptr_que=RingQueueInit(&que,buffer,BUFFER_SIZE,&err); *if(err==RQ_ERR_NONE){ *//初始化成功,使用其他函数 *} *History:2017/04/25theoriginalversionofRingQueueStruct. *2017/10/16putfunctionsusedfrequently,RingQueueInandRingQueueOut,innon-bankedaddress; *modifysinglelinefunctionRingQueueIsEmptyandRingQueueIsFulltomarcofunction; *togetbetterefficiency. *2018/02/231.addthemarco(RQ_ARGUMENT_CHECK_EN)tocontrollargumentchecksousercansave *morecode. *2.addtheADDRESSINGMODEsothebuffercanbedefinedinbankedaddressingarea. ********************************************************************************************************* */ #ifndefRING_QUEUE_H #defineRING_QUEUE_H /* ******************************************************************************************** *MISCELLANEOUS ******************************************************************************************** */ #ifndefFALSE #defineFALSE0 #endif #ifndefTRUE #defineTRUE1 #endif /* ********************************************************************************************************* *ADDRESSINGMODE寻址模式 ********************************************************************************************************* */ //uncommentthecorrespondinglinetoselecttheaddressingmodetothebufferofRingQueuemodule. //ifyoudontunderstand.Justusetheextendedaddressingmode //取消对应行的注释以选择环形缓冲区模块访问缓冲区时使用的寻址方式 //如果你不知道这是什么意思的话，那就用扩展寻址就行了，这是默认的方式 //extendedaddressingmode扩展区寻址(默认) #defineRQ_ADDRESSING_MODE //bankedRAMaddressingmodeRAM分页区寻址 //#defineRQ_ADDRESSING_MODE__rptr //globaladdressingmode全局寻址 //#defineRQ_ADDRESSING_MODE__far /* ********************************************************************************************************* *CONFIGURATION配置 ********************************************************************************************************* */ #defineRQ_ARGUMENT_CHECK_ENTRUE//TRUE:argumentswillbechecked,however,thiswill //costalittlecodevolume. /* ********************************************************************************************************* *CONSTANTS常量 ********************************************************************************************************* */ #defineRQ_ERR_NONE0u #defineRQ_ERR_POINTER_NULL1u #defineRQ_ERR_SIZE_ZERO2u #defineRQ_ERR_BUFFER_FULL3u #defineRQ_ERR_BUFFER_EMPTY4u #defineRQ_OPTION_WHEN_FULL_DISCARD_FIRST0u//discardthefirstelementwhenringbufferisfull #defineRQ_OPTION_WHEN_FULL_DONT_IN1u//discardnewelementwhenringbufferisfull /* ********************************************************************************************************* *DATATYPE数据类型 ********************************************************************************************************* */ //definethedatatypethatstoresintheRingQueue.定义存在环形缓冲区内的数据的类型 typedefunsignedcharRQTYPE; typedefRQTYPE*RQ_ADDRESSING_MODEpRQTYPE; typedefstruct{ unsignedshortRingBufCtr;/*Numberofcharactersintheringbuffer*/ unsignedshortRingBufSize;/*RingbufferSize*/ pRQTYPERingBufInPtr;/*Pointertowherenextcharacterwillbeinserted*/ pRQTYPERingBufOutPtr;/*Pointerfromwherenextcharacterwillbeextracted*/ pRQTYPERingBuf;/*Ringbufferarray*/ pRQTYPERingBufEnd;/*Pointtotheendofthebuffer*/ }RING_QUEUE; /* ********************************************************************************************************* *FUNCTIONPROTOTYPES函数原型 ********************************************************************************************************* */ RING_QUEUE*RingQueueInit(RING_QUEUE*pQueue,pRQTYPEpbuf,unsignedshortbufSize,unsignedchar*perr); #pragmaCODE_SEG__NEAR_SEGNON_BANKED unsignedshortRingQueueIn(RING_QUEUE*pQueue,RQTYPEdata,unsignedcharoption,unsignedchar*perr); RQTYPERingQueueOut(RING_QUEUE*pQueue,unsignedchar*perr); #pragmaCODE_SEGDEFAULT shortRingQueueMatch(RING_QUEUE*pQueue,pRQTYPEpbuf,unsignedshortlen); voidRingQueueClear(RING_QUEUE*pQueue); /* ********************************************************************************************************* *RingQueueIsEmpty() * *Description:whethertheRingQueueisempty.环形队列是否为空 * *Arguments:pQueuepointertotheringqueuecontrolblock;指向环形队列控制块的指针 * *Return:TRUEtheRingQueueisempty. *FALSEtheRingQueueisnotempty. *Note(s): ********************************************************************************************************* */ #defineRingQueueIsEmpty(pQueue)((pQueue)->RingBufCtr==0) /* ********************************************************************************************************* *RingQueueIsFull() * *Description:whethertheRingQueueisfull.环形队列是否为空 * *Arguments:pQueuepointertotheringqueuecontrolblock;指向环形队列控制块的指针 * *Return:TRUEtheRingQueueisfull. *FALSEtheRingQueueisnotfull. *Note(s): ********************************************************************************************************* */ #defineRingQueueIsFull(pQueue)((pQueue)->RingBufCtr>=(pQueue)->RingBufSize) #endif

然后下面是.c文件。

/* ********************************************************************************************************* * * *RingQueueStruct *环形队列结构 * *File:RingQueue.c *By:LinShijun(http://blog.csdn.net/lin_strong) *Date:2018/02/23 *version:V1.2 *NOTE(s): * *History:2017/04/25theoriginalversionofRingQueueStruct. *2017/10/16putfunctionsusedfrequently,RingQueueInandRingQueueOut,innon-bankedaddress; *modifysinglelinefunctionRingQueueIsEmptyandRingQueueIsFulltomarcofunction; *togetbetterefficiency. *2018/02/231.addthemarco(RQ_ARGUMENT_CHECK_EN)tocontrollargumentchecksousercansave *morecode. *2.addtheADDRESSINGMODEsothebuffercanbedefinedinbankedaddressingarea. ********************************************************************************************************* */ /* ********************************************************************************************************* *INCLUDES ********************************************************************************************************* */ #include”RingQueue.h” /* ********************************************************************************************************* *LOCALFUNCTIONDECLARATION ********************************************************************************************************* */ #if(RQ_ARGUMENT_CHECK_EN==TRUE) #defineargCheck(cond,err,rVal)if(cond){*perr=(err);return(rVal);} #else #defineargCheck(cond,err,rVal) #endif//of(SPI_ARGUMENT_CHECK_EN==TRUE) /* ********************************************************************************************************* *LOCALFUNCTIONDECLARE ********************************************************************************************************* */ #pragmaCODE_SEG__NEAR_SEGNON_BANKED //内部使用，给定将给定指针在环形缓冲区内向前移动一步(到尾了会移回头) staticvoid_forwardPointer(RING_QUEUE*pQueue,pRQTYPE*pPointer); #pragmaCODE_SEGDEFAULT /* ********************************************************************************************************* *RingQueueInit() * *Description:Toinitializetheringqueue.初始化环形队列 * *Arguments:pQueuepointertotheringqueuecontrolblock;指向环形队列控制块的指针 *pbufpointertothebuffer(anarray);指向自定义的缓冲区(实际就是个数组) *bufSizetheSizeofthebuffer;缓冲区的大小; *perrapointertoavariablecontaininganerrormessagewhichwillbesetbythis *functiontoeither: * *RQ_ERR_NONE *RQ_ERR_SIZE_ZERO *RQ_ERR_POINTER_NULL * *Return:thepointertotheringqueuecontrolblock;返回指向环形队列控制块的指针 *0x00ifanyerror;如果出错了则返回NULL * *Note(s): ********************************************************************************************************* */ RING_QUEUE*RingQueueInit(RING_QUEUE*pQueue,pRQTYPEpbuf,unsignedshortbufSize,unsignedchar*perr){ argCheck(pQueue==0x00||pbuf==0x00,RQ_ERR_POINTER_NULL,0x00); argCheck(bufSize==0,RQ_ERR_SIZE_ZERO,0x00); pQueue->RingBufCtr=0; pQueue->RingBuf=pbuf; pQueue->RingBufInPtr=pbuf; pQueue->RingBufOutPtr=pbuf; pQueue->RingBufSize=bufSize; pQueue->RingBufEnd=pbuf+bufSize; *perr=RQ_ERR_NONE; returnpQueue; } /* ********************************************************************************************************* *RingQueueIn() * *Description:Enqueueanelement.入队一个元素 * *Arguments:pQueuepointertotheringqueuecontrolblock;指向环形队列控制块的指针 *datathedatatoenqueue;要入队的数据 *optionoptionwhenqueueisfull,youcanchoose:当队列满的时候的选项,你可以选择: *RQ_OPTION_WHEN_FULL_DISCARD_FIRST抛弃队头的元素来填进去新的元素 *RQ_OPTION_WHEN_FULL_DONT_IN不入队新给的元素 *perrapointertoavariablecontaininganerrormessagewhichwillbesetbythis *functiontoeither: * *RQ_ERR_NONEifnoerrhappen *RQ_ERR_POINTER_NULLifpointeris0x00 *RQ_ERR_BUFFER_FULLifbufferisfull * *Return:theElementsCountafterenqueuetheelement *调用函数后队列中的元素个数 *Note(s): ********************************************************************************************************* */ #pragmaCODE_SEG__NEAR_SEGNON_BANKED unsignedshortRingQueueIn(RING_QUEUE*pQueue,RQTYPEdata,unsignedcharoption,unsignedchar*perr){ argCheck(pQueue==0x00,RQ_ERR_POINTER_NULL,0x00); if(pQueue->RingBufCtr>=pQueue->RingBufSize){ *perr=RQ_ERR_BUFFER_FULL; if(option==RQ_OPTION_WHEN_FULL_DISCARD_FIRST){ _forwardPointer(pQueue,&pQueue->RingBufOutPtr);/*WrapOUTpointer*/ }else{//option==RQ_OPTION_WHEN_FULL_DONT_IN returnpQueue->RingBufCtr; } }else{ pQueue->RingBufCtr++;/*No,incrementcharactercount*/ *perr=RQ_ERR_NONE; } *pQueue->RingBufInPtr=data;/*Putcharacterintobuffer*/ _forwardPointer(pQueue,&pQueue->RingBufInPtr);/*WrapINpointer*/ returnpQueue->RingBufCtr; } /* ********************************************************************************************************* *RingQueueOut() * *Description:Dequeueanelement.出队一个元素 * *Arguments:pQueuepointertotheringqueuecontrolblock;指向环形队列控制块的指针 *perrapointertoavariablecontaininganerrormessagewhichwillbesetbythis *functiontoeither: * *RQ_ERR_NONEifnoerrhappen *RQ_ERR_POINTER_NULLifpointeris0x00 *RQ_ERR_BUFFER_EMPTYifbufferisempty * *Return:0ifanyerrororthedatais0; *othersthedata * *Note(s): ********************************************************************************************************* */ RQTYPERingQueueOut(RING_QUEUE*pQueue,unsignedchar*perr){ RQTYPEdata; argCheck(pQueue==0x00,RQ_ERR_POINTER_NULL,0x00); if(pQueue->RingBufCtr==0){ *perr=RQ_ERR_BUFFER_EMPTY; return0; } pQueue->RingBufCtr–;/*decrementcharactercount*/ data=*pQueue->RingBufOutPtr;/*Getcharacterfrombuffer*/ _forwardPointer(pQueue,&pQueue->RingBufOutPtr);/*WrapOUTpointer*/ *perr=RQ_ERR_NONE; returndata; } #pragmaCODE_SEGDEFAULT /* ********************************************************************************************************* *RingQueueMatch() * *Description:MatchthegivenbufferinRingQueue在环形队列中匹配给定缓冲区 * *Arguments:pQueuepointertotheringqueuecontrolblock;指向环形队列控制块的指针 *pbufpointertothecharsneedtomatch; *lenthelengthofthechars *Return:-1Dontmatch-1则没有匹配到 *>=0match>=0则匹配到了 * *Note(s): ********************************************************************************************************* */ shortRingQueueMatch(RING_QUEUE*pQueue,pRQTYPEpbuf,unsignedshortlen){ pRQTYPEpPosQ,pCurQ,pCurB,pEndB; unsignedshortrLen,Cnt; if(len>pQueue->RingBufCtr) return-1; pPosQ=pQueue->RingBufOutPtr; pEndB=pbuf+len; Cnt=0; rLen=pQueue->RingBufCtr; while(rLen–>=len){//ifremianlengthofqueuebiggerthanbuffer.continue pCurQ=pPosQ; pCurB=pbuf; while(pCurB!=pEndB&&*pCurQ==*pCurB){//compareonebyone,untilmatchall(pCurB==pEndB)orsomeonedontmatch _forwardPointer(pQueue,&pCurQ); pCurB++; } if(pCurB==pEndB)//ifmatchall returnCnt; Cnt++; _forwardPointer(pQueue,&pPosQ); } return-1; } /* ********************************************************************************************************* *RingQueueClear() * *Description:CleartheRingQueue.清空环形队列 * *Arguments:pQueuepointertotheringqueuecontrolblock;指向环形队列控制块的指针 * *Return: * *Note(s): ********************************************************************************************************* */ voidRingQueueClear(RING_QUEUE*pQueue){ #if(RQ_ARGUMENT_CHECK_EN==TRUE) if(pQueue==0x00) return; #endif pQueue->RingBufCtr=0; pQueue->RingBufInPtr=pQueue->RingBufOutPtr; } /* ********************************************************************************************************* *LOCALFUNCTION ********************************************************************************************************* */ #pragmaCODE_SEG__NEAR_SEGNON_BANKED staticvoid_forwardPointer(RING_QUEUE*pQueue,pRQTYPE*pPointer){ if(++*pPointer==pQueue->RingBufEnd) *pPointer=pQueue->RingBuf;/*WrapOUTpointer*/ } #pragmaCODE_SEGDEFAULT

简单解释下。

在.h文件中定义了一个环形缓冲区的控制块，当然也可以当其为一个环形缓冲区对象，用户需要为每个环形缓冲区分配一个控制块和其缓冲区(也就是一个数组)。理想情况下，虽然用户知道控制块的结构，但也不应该直接访问内部字段，而应该通过提供的函数来访问。

队列中默认的元素是无符号字符，如果要改成缓存其他类型的话改下.h文件中的typedef unsigned char RQTYPE;这行就行了。

使用示例：

#include”RingQueue.h” #defineRX_BUF_MAX_SIZE200//定义缓冲区的最大大小为200 staticunsignedcharRxBuffer[RX_BUF_MAX_SIZE];//定义缓冲区 staticRING_QUEUERxRingQ;//定义环形缓冲区的控制块 voidmain(){ unsignedcharerr; //初始化缓冲区 RingQueueInit(&RxRingQ,RxBuffer,RX_BUF_MAX_SIZE,&err); if(err!=RQ_ERR_NONE){ //初始化缓冲区失败的处理 } …… }

然后调用所有方法都需要传递环形缓冲区控制块的指针。如入队就像：

//往RxRingQ缓冲区内入队一个元素c，如果满的话丢弃第一个元素 RingQueueIn(&RxRingQ,c,RQ_OPTION_WHEN_FULL_DISCARD_FIRST,&err);

出队就像：

//从RxRingQ缓冲区内提取一个字符 c=RingQueueOut(&RxRingQ,&err);

其他就不一 一举例了。要特别说明下的是RingQueueMatch()这个方法并不是队列应该有的方法，这是为了比如我需要在缓冲区中匹配到某一串字符后做某些事情而特别加上的，不需要的话删掉即可。比如我需要一旦出现“abc”就做某些事情，那我代码可以类似这么写：

staticconstunsignedchar*StringsWait=”abc”; …… while(true){ //比如从某处获得了下一个字符c …… //将字符c入队 RingQueueIn(&RxRingQ,c,RQ_OPTION_WHEN_FULL_DISCARD_FIRST,&err); if(RingQueueMatch(&RxRingQ,StringsWait,3)>=0){//如果在缓冲区内找到”abc” //RingQueueClear(&RxRingQ);//可能需要清空缓冲区 //做想要做的事 …… } }

有什么建议或意见请留言，谢谢！

审核编辑：汤梓红