基于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. //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);//可能需要清空緩沖區
//做想要做的事
……
}
}
有什么建議或意見請留言，謝謝！
審核編輯：湯梓紅
聲明：本文內容及配圖由入駐作者撰寫或者入駐合作網站授權轉載。文章觀點僅代表作者本人，不代表電子發燒友網立場。文章及其配圖僅供工程師學習之用，如有內容侵權或者其他違規問題，請聯系本站處理。
舉報投訴
-
緩沖區
+關注
關注
0文章
36瀏覽量
9324 -
嵌入式
+關注
關注
5141文章
19542瀏覽量
315184 -
C語言
+關注
關注
180文章
7630瀏覽量
140478 -
隊列
+關注
關注
1文章
46瀏覽量
11043 -
數組
+關注
關注
1文章
419瀏覽量
26376
原文標題：[嵌入式開發模塊]環形緩沖區/循環隊列 C語言實現
文章出處：【微信號：玩點嵌入式，微信公眾號：玩點嵌入式】歡迎添加關注！文章轉載請注明出處。
發布評論請先 登錄
相關推薦
熱點推薦
基于宏高效實現環形緩沖區教程
來源 | 小麥大叔 循環緩沖區是嵌入式軟件工程師在日常開發過程中的關鍵組件。 多年來，互聯網上出現了許多不同的循環緩沖區實現和示例。我非常喜
STM32進階之串口環形緩沖區實現
完了數據，‘0’地址空間的數據進行釋放掉，列隊頭指向下一個可以處理數據的地址‘1’。從而實現整個環形緩沖區的數據讀寫。看圖，隊列頭就是指向已經存儲的數據，并且這個數據是待處理的。下一個
發表于 06-08 14:03
MCU進階之串口環形緩沖區實現
是列隊頭的數據，處理完了數據，‘0’地址空間的數據進行釋放掉，列隊頭指向下一個可以處理數據的地址‘1’。從而實現整個環形緩沖區的數據讀寫。看圖，隊列頭就是指向已經存儲的數據，并且這個數
發表于 08-17 13:11
STM32串口環形緩沖區的實現
是列隊頭的數據，處理完了數據，‘0’地址空間的數據進行釋放掉，列隊頭指向下一個可以處理數據的地址‘1’。從而實現整個環形緩沖區的數據讀寫。看圖，隊列頭就是指向已經存儲的數據，并且這個數
發表于 10-16 11:40
請問串口的DMA接收緩沖區是不是環形緩沖區
大家好！請問串口的DMA接收緩沖區是不是環形緩沖區？通過閱讀串口部分的代碼，我了解到這樣幾點：1、串口的DMA接收時循環接收，當緩沖區滿了會
發表于 08-30 14:27
環形緩沖區讀寫操作的分析與實現
環形緩沖區是嵌入式系統中一種重要的常用數據結構。在多任務環境下實現時，如果有多個讀寫任務，一般需要用信號量來保護多個任務共享的環形緩沖區。但
發表于 04-15 11:35
?40次下載
STM32進階之串口環形緩沖區實現
碼代碼的應該學數據結構都學過隊列。環形隊列是隊列的一種特殊形式，應用挺廣泛的。因為有太多文章關于這方面的內容，理論知識可以看別人的，下面寫得挺好的：STM32進階之串口
發表于 12-06 10:00
?3353次閱讀
環形緩沖區的實現思路
單片機程序開發一般都會用到UART串口通信，通過通信來實現上位機和單片機程序的數據交互。通信中為了實現正常的收發，一般都會有對應的發送和接收緩存來暫存通信數據。這里使用環形緩沖區的方式
基于C語言的循環隊列緩沖區原理、設計與實現
在FPGA中，FIFO一般是使用RAM存儲器作為緩沖區，可以分為同步FIFO或異步FIO，一般用于數據緩沖，或者不同時鐘域之間的數據傳遞。
發表于 04-10 09:30
?1392次閱讀
工商網監
評論