這里分享一個自己用純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.
//ifyoudon'tunderstand.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:-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.清空環形隊列
*
*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);//可能需要清空緩沖區
//做想要做的事
……
}
}

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

審核編輯：湯梓紅