基于C語言實現(xiàn)環(huán)形緩沖區(qū)/循環(huán)隊列

這里分享一個自己用純C實現(xiàn)的環(huán)形緩沖區(qū)。

環(huán)形緩沖區(qū)有很多作用，比如嵌入式中的通信可以用環(huán)形緩沖區(qū)作為信道，一個線程往里放字節(jié)，一個線程取字節(jié)進行處理，只要保證取的速度大于讀的速度，就可以保證通信順暢進行，不丟一個字節(jié)。

簡要介紹：

環(huán)形緩沖區(qū)其實就是一個隊列，里頭的元素是先入先出的，但是因為其(邏輯上)是環(huán)形的，所以不需要像很多隊列的實現(xiàn)那樣在內(nèi)部元素變動的時候需要移動內(nèi)部剩下的元素。這樣就使元素出隊入隊的時間復(fù)雜度只有O(1)。具體實現(xiàn)一般有鏈表和數(shù)組兩種方法，當不能確定需要的緩沖區(qū)大小時使用鏈表較好，能確定時使用數(shù)組可以節(jié)省很多動態(tài)分配內(nèi)存的開銷。

在嵌入式開發(fā)中，一般不動態(tài)分配內(nèi)存，而是使用靜態(tài)分配的數(shù)組。所以這里我使用數(shù)組實現(xiàn)了環(huán)形緩沖區(qū)，為了能夠在不同的程序中復(fù)用代碼，使用結(jié)構(gòu)體模擬了面向?qū)ο?a target="_blank">編程，這樣就可以用一套代碼管理不同的緩沖區(qū)了。

廢話不多說，直接上代碼。以下是.h 文件：

/*
*********************************************************************************************************
*
*
*RingQueueStruct
*環(huán)形隊列結(jié)構(gòu)
*
*File:RingQueue.h
*By:LinShijun(http://blog.csdn.net/lin_strong)
*Date:2018/02/23
*version:V1.2
*NOTE(s):這段程序用來對一個給定的緩沖區(qū)進行模擬環(huán)形隊列的管理
*程序本身不會自動分配緩沖區(qū)空間,用戶需要自己負責分配空間,并且要保證不直接訪問緩存區(qū)
*//在某處分配內(nèi)存空間
*RQTYPEbuffer[BUFFER_SIZE];
*RING_QUEUEque,*ptr_que;
*unsignedcharerr;
*//初始化
*ptr_que=RingQueueInit(&que,buffer,BUFFER_SIZE,&err);
*if(err==RQ_ERR_NONE){
*//初始化成功,使用其他函數(shù)
*}
*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.
//ifyoudon'tunderstand.Justusetheextendedaddressingmode
//取消對應(yīng)行的注釋以選擇環(huán)形緩沖區(qū)模塊訪問緩沖區(qū)時使用的尋址方式
//如果你不知道這是什么意思的話，那就用擴展尋址就行了，這是默認的方式

//extendedaddressingmode擴展區(qū)尋址(默認)
#defineRQ_ADDRESSING_MODE
//bankedRAMaddressingmodeRAM分頁區(qū)尋址
//#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數(shù)據(jù)類型
*********************************************************************************************************
*/

//definethedatatypethatstoresintheRingQueue.定義存在環(huán)形緩沖區(qū)內(nèi)的數(shù)據(jù)的類型
typedefunsignedcharRQTYPE;
typedefRQTYPE*RQ_ADDRESSING_MODEpRQTYPE;
typedefstruct{
unsignedshortRingBufCtr;/*Numberofcharactersintheringbuffer*/
unsignedshortRingBufSize;/*RingbufferSize*/
pRQTYPERingBufInPtr;/*Pointertowherenextcharacterwillbeinserted*/
pRQTYPERingBufOutPtr;/*Pointerfromwherenextcharacterwillbeextracted*/
pRQTYPERingBuf;/*Ringbufferarray*/
pRQTYPERingBufEnd;/*Pointtotheendofthebuffer*/
}RING_QUEUE;

/*
*********************************************************************************************************
*FUNCTIONPROTOTYPES函數(shù)原型
*********************************************************************************************************
*/

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.環(huán)形隊列是否為空
*
*Arguments:pQueuepointertotheringqueuecontrolblock;指向環(huán)形隊列控制塊的指針
*
*Return:TRUEtheRingQueueisempty.
*FALSEtheRingQueueisnotempty.
*Note(s):
*********************************************************************************************************
*/

#defineRingQueueIsEmpty(pQueue)((pQueue)->RingBufCtr==0)

/*
*********************************************************************************************************
*RingQueueIsFull()
*
*Description:whethertheRingQueueisfull.環(huán)形隊列是否為空
*
*Arguments:pQueuepointertotheringqueuecontrolblock;指向環(huán)形隊列控制塊的指針
*
*Return:TRUEtheRingQueueisfull.
*FALSEtheRingQueueisnotfull.
*Note(s):
*********************************************************************************************************
*/

#defineRingQueueIsFull(pQueue)((pQueue)->RingBufCtr>=(pQueue)->RingBufSize)

#endif

然后下面是.c文件。

/*
*********************************************************************************************************
*
*
*RingQueueStruct
*環(huán)形隊列結(jié)構(gòu)
*
*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
//內(nèi)部使用，給定將給定指針在環(huán)形緩沖區(qū)內(nèi)向前移動一步(到尾了會移回頭)
staticvoid_forwardPointer(RING_QUEUE*pQueue,pRQTYPE*pPointer);
#pragmaCODE_SEGDEFAULT
/*
*********************************************************************************************************
*RingQueueInit()
*
*Description:Toinitializetheringqueue.初始化環(huán)形隊列
*
*Arguments:pQueuepointertotheringqueuecontrolblock;指向環(huán)形隊列控制塊的指針
*pbufpointertothebuffer(anarray);指向自定義的緩沖區(qū)(實際就是個數(shù)組)
*bufSizetheSizeofthebuffer;緩沖區(qū)的大小;
*perrapointertoavariablecontaininganerrormessagewhichwillbesetbythis
*functiontoeither:
*
*RQ_ERR_NONE
*RQ_ERR_SIZE_ZERO
*RQ_ERR_POINTER_NULL
*
*Return:thepointertotheringqueuecontrolblock;返回指向環(huán)形隊列控制塊的指針
*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;指向環(huán)形隊列控制塊的指針
*datathedatatoenqueue;要入隊的數(shù)據(jù)
*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
*調(diào)用函數(shù)后隊列中的元素個數(shù)
*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;指向環(huán)形隊列控制塊的指針
*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在環(huán)形隊列中匹配給定緩沖區(qū)
*
*Arguments:pQueuepointertotheringqueuecontrolblock;指向環(huán)形隊列控制塊的指針
*pbufpointertothecharsneedtomatch;
*lenthelengthofthechars
*Return:-1Don'tmatch-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)orsomeonedon'tmatch
_forwardPointer(pQueue,&pCurQ);
pCurB++;
}
if(pCurB==pEndB)//ifmatchall
returnCnt;
Cnt++;
_forwardPointer(pQueue,&pPosQ);
}
return-1;
}

/*
*********************************************************************************************************
*RingQueueClear()
*
*Description:CleartheRingQueue.清空環(huán)形隊列
*
*Arguments:pQueuepointertotheringqueuecontrolblock;指向環(huán)形隊列控制塊的指針
*
*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文件中定義了一個環(huán)形緩沖區(qū)的控制塊，當然也可以當其為一個環(huán)形緩沖區(qū)對象，用戶需要為每個環(huán)形緩沖區(qū)分配一個控制塊和其緩沖區(qū)(也就是一個數(shù)組)。理想情況下，雖然用戶知道控制塊的結(jié)構(gòu)，但也不應(yīng)該直接訪問內(nèi)部字段，而應(yīng)該通過提供的函數(shù)來訪問。

隊列中默認的元素是無符號字符，如果要改成緩存其他類型的話改下.h文件中的typedef unsigned char RQTYPE;這行就行了。

使用示例：

#include"RingQueue.h"
#defineRX_BUF_MAX_SIZE200//定義緩沖區(qū)的最大大小為200
staticunsignedcharRxBuffer[RX_BUF_MAX_SIZE];//定義緩沖區(qū)
staticRING_QUEUERxRingQ;//定義環(huán)形緩沖區(qū)的控制塊
voidmain(){
unsignedcharerr;
//初始化緩沖區(qū)
RingQueueInit(&RxRingQ,RxBuffer,RX_BUF_MAX_SIZE,&err);
if(err!=RQ_ERR_NONE){
//初始化緩沖區(qū)失敗的處理
}
……
}

然后調(diào)用所有方法都需要傳遞環(huán)形緩沖區(qū)控制塊的指針。如入隊就像：

//往RxRingQ緩沖區(qū)內(nèi)入隊一個元素c，如果滿的話丟棄第一個元素
RingQueueIn(&RxRingQ,c,RQ_OPTION_WHEN_FULL_DISCARD_FIRST,&err);

出隊就像：

//從RxRingQ緩沖區(qū)內(nèi)提取一個字符
c=RingQueueOut(&RxRingQ,&err);

其他就不一 一舉例了。要特別說明下的是RingQueueMatch()這個方法并不是隊列應(yīng)該有的方法，這是為了比如我需要在緩沖區(qū)中匹配到某一串字符后做某些事情而特別加上的，不需要的話刪掉即可。比如我需要一旦出現(xiàn)“abc”就做某些事情，那我代碼可以類似這么寫：

staticconstunsignedchar*StringsWait="abc";
……
while(true){
//比如從某處獲得了下一個字符c
……
//將字符c入隊
RingQueueIn(&RxRingQ,c,RQ_OPTION_WHEN_FULL_DISCARD_FIRST,&err);
if(RingQueueMatch(&RxRingQ,StringsWait,3)>=0){//如果在緩沖區(qū)內(nèi)找到"abc"
//RingQueueClear(&RxRingQ);//可能需要清空緩沖區(qū)
//做想要做的事
……
}
}

有什么建議或意見請留言，謝謝！

審核編輯：湯梓紅