Application of circular queue

懒猫爱飞

Application of circular queue [Copy link]

About the Application of Circular Queue

Author : Mark Xu

关于循环队列的应用.pdf (605.59 KB, downloads: 10)

2018-11-29 16:04 上传

点击文件名下载附件

In the USB project developed, continuous access to data will be used, so I wrote a simple circular queue. The advantage of a circular queue is that it is connected end to end to save space. The concept of circular queue has been explained very clearly in the textbook, and there are also a large number of blog documents on the Internet with both pictures and texts. I will not go into details here. The following is just a summary of the code, which is equivalent to a backup^_^

There are two source files Xc_CircleQueue.c and Xc_CircleQueue.h

1) Source code of 9.0pt] * * FileName : * * Author : Mark Xu * * Date : 2018 year10month12[color=#00B05 0]日 * * Version: V1.0 * * Remark : None * *----------------------------------------------------------------------------------------------------------------------------------------------- * History: * * 1) Author: xx xx * * ModifyDate : xx xx xx * * Modifycontents: xx xx xx xx xx ******************************************************************************************/ #define[size=9.0pt ] XC_CIRCLEQUEUE_IMPLEMENT #include #include #include #include #include "Xc_CircleQueue.h" [color =#00B050]/****************************************** *********************************************[ /color] * Function name[ size=9.0pt] : Circle_Queue_Init * * Function description : Initial the queue * * Entry parameters : *rbuf - the queue[/ size] * * *array - the data buffer * * len - the depth of the queue [ color=#00B050] * * Export parameters : TRUE - initial successful[/size ] * * Function remarks : None[/ color] ************************************ *************************************************/ uint8_t Circle_Queue_Init(RingBuf_T*rbuf, uint8_t *array, uint16_t len) { if( (len<2)||(array== NULL)) return FALSE; rbuf->Buf = array; rbuf->Depth = len; rbuf->fillCnt = 0 ; rbuf->Head = 0; rbuf->Tail = 0; return TRUE; [size=9.0 pt]} /**************************************** *************************************************[/size ] * Function name[ size=9.0pt] : RingBuf_Clear * * Function description[/ color] : clear the queue * * Entry parameters : *rbuf - the queue[/ size] * * Export parameters : None * * Function notes*****************************************************************************/ voidRingBuf_Clear(RingBuf_T *rbuf) { rbuf->fillCnt = 0; rbuf->Head = 0; rbuf ->Tail = 0; } /****************************************************************************************** * Function Name : RingBuf_Chk_Full * * Function Description : clear the queue * * Entry parameters : *rbuf - the queue * * [/size ]Export parameters : true - full false - not full * * Function remarks : judging condition -(tail+1) % buf_size_max == head ******************************************************************************/[/size ] uint16_tRingBuf_Chk_Full(RingBuf_T *rbuf) { return((rbuf->Tail + 1)%rbuf->Depth == rbuf->Head); [ size=9.0pt]} /************************************************************************************ * Function Name : RingBuf_Chk_Empty * * Function Description : check the queue empty ornot * * Entry parameters : *rbuf - the queue * * Export parameters : true - empty false - not empty * * Function remarks[ size=9.0pt] : judging condition - tail ==head ****************************************** *************************************************/[/ size] uint16_tRingBuf_Chk_Empty(RingBuf_T *rbuf) { return(rbuf->Tail == rbuf- >Head); } /****************************** *************************************************** ************* * Function name: RingBuf_Write_Bytes * * Function description : push the data to queue[/ size] * * Entry parameters : *rbuf - the queue[/ size] * * *pValue - the value to be push * * size - the bytes of the valuebuffer * * Export parameters : [/color ]size - the bytes of be write bytes[/color ] * * Function remarks : none[/ color] ************************************ *************************************************/ uint16_tRingBuf_Write_Bytes(RingBuf_T *rbuf,uint8_t *pValue, uint16_t size) { uint16_t len = 0; uint16_t ringBuf_bw = rbuf ->Tail; uint16_t ringBuf_len = rbuf->Depth; uint8_t *ringBuf_source = rbuf->Buf; if(RingBuf_Chk_Full(rbuf))[/ size] return 0; if((ringBuf_bw+ size) <= ringBuf_len) { memcpy((uint8_t*)&ringBuf_source[ringBuf_bw],pValue,size); } else { [ size=9.0pt] len = ringBuf_len -ringBuf_bw; memcpy(ringBuf_source+ringBuf_bw,pValue,len);[ /size] memcpy(ringBuf_source,pValue+ringBuf_bw,(size-len)); } [size=9.0 pt] // CalculateTail [color=# 00B050] position rbuf->Tail = (rbuf->Tail + size)% rbuf->Depth; [size= 9.0pt] rbuf->fillCnt += size; returnsize; [size=9.0pt ]} /**************************************** *************************************************[/size ] * Function name[color =#00B050] : RingBuf_Write_Bytes * [size= 9.0pt] * Function description : Read the data from thequeue * * [size =9.0pt]Entry parameter : *rbuf - the queue [size=9.0 pt] * * *pValue - the data buffer to store the read data [ size=9.0pt] * * size - the bytes of the valuebuffer * * [size =9.0pt]Export parameters : size - the bytes[color=# 0b050] of be read * [size=9.0pt ] * Function remarks : none[/ color] ************************************ *************************************************/ uint16_tRingBuf_Read_Bytes(RingBuf_T *rbuf,uint8_t *pValue,uint16_t size) { uint16_t len = 0; uint16_t ringBuf_br = rbuf->Head; uint16_t ringBuf_len = rbuf->Depth; char*ringBuf_src = rbuf->Buf; [size= 9.0pt] // If it is empty, return0 if(RingBuf_Chk_Empty(rbuf)) return 0; // Whentialequalshead, it means the queue is empty if(rbuf->fillCnt== 0) { // printf("Buffer isempty,nothing to be read \r\n"); return 0; } // Only read valid data if(size> rbuf->fillCnt) size = rbuf->fillCnt; if((ringBuf_br+ size) <= ringBuf_len) { memcpy(pValue,ringBuf_src +ringBuf_br,size); } else { len = ringBuf_len -ringBuf_br; memcpy(pValue,ringBuf_src +ringBuf_br,len); memcpy(pValue+len, ringBuf_src,(size-len)); } rbuf->Head = (rbuf->Head + size)% rbuf->Depth; rbuf->fillCnt -= size; returnsize; }

2) Source code of reserved. * * File Name : Xc_Queue.h * * File Description : Some declarations and definitions about the queue module * * Author : Mark Xu * * Creation date : 2018Year10month10[ /color]日 * * [size =9.0pt]Current version : V1.0 * * File Notes : None[/ color] * *-------------- -------------------------------------------------- ------------------------ * [ /color]Modification record : [color=# 00B050] * * 1) Editor: xx xx[ /color] * * ]Modification date : xx xx xx [size= 9.0pt] * * Modify content : xx xx xx xx xx[/ size] ****************************************** *************************************************** **/ #ifndef __XC_CIRCLEQUEUE_H__ #define __XC_CIRCLEQUEUE_H__ //------------------------------------------------ -------------------------------------------------- -------------------------------------------------- -------- // Precompile [size=9.0pt ]//-------------------------------------------------- -------------------------------------------------- -------------------------------------------------- #ifdef XC_CIRCLEQUEUE_IMPLEMENT #define CIRCLEQUEUE_EXTERN [size=9.0 pt]#else #define CIRCLEQUEUE_EXTERN extern #endif /* XC_CIRCLEQUEUE_IMPLEMENT */ #include "stdio.h" #include "stdlib.h" #include[ /b] "stdint.h" #include "string.h" //------------------------------------------------------------------------------------------------------------------------------------------------ // Data type declaration //------------------------------------------------------------------------------------------------------------------------------------------------ /* Description: 1. fillCnt is the number of elements in the counting queue 2. When inserting elements into the queue,fillCnt is increased 3. When reading elements from the queue,fillCnt To reduce 4. WhenfillCntis0, it means that there are no elements in the queue and cannot be read */ #pragma pack(4) typedef struct RingBuf_t{ uint8_t *Buf; /* Pointer to the queue array */ uint16_t Depth; /* Number of elements that can be stored */ uint16_t Head; /* The head of the team, is also a read pointer */ uint16_t Tail; /* The tail of the team, is also a write pointer */ uint16_t fillCnt; /* Element count */ }RingBuf_T; #pragma pack() // Pointer form typedef RingBuf_T* RingBuf_Tp; //---------------------------------------------------------------------------------------------------------------------------------------------------------------- // Function declaration //--------------------- -------------------------------------------------- -------------------------------------------------- -------------------- CIRCLEQUEUE_EXTERN uint8_t Circle_Queue_Init(RingBuf_T *rbuf, uint8_t *array, uint16_t len); CIRCLEQUEUE_EXTERN void RingBuf_Clear(RingBuf_T *rbuf); [ /size] CIRCLEQUEUE_EXTERN uint16_t RingBuf_Chk_Full(RingBuf_T *rbuf); CIRCLEQUEUE_EXTERN uint16_t RingBuf_Chk_Empty(RingBuf_T *rbuf); CIRCLEQUEUE_EXTERN uint16_t RingBuf_Write_Bytes(RingBuf_T *rbuf,uint8_t *pValue, uint16_t size); CIRCLEQUEUE_EXTERN uint16_t RingBuf_Read_Bytes(RingBuf_T *rbuf,uint8_t *pValue,uint16_t size); [size= 9.0pt] /* __XC_CIRCLEQUEUE_H__ */ [/td][/ tr] [/table] This content is originally created by 懒猫爱飞, a user of EEWORLD forum. If you want to reprint or use it for commercial purposes, you must obtain the author's consent and Please indicate the source

懒猫爱飞

Learning from the previous post, the code of this post is pasted separately, and the effect is much better

btty038

I don't understand, come and support

RCSN

Thanks for sharing. But there are a few things that are not really suggestions for the original poster. 1. It is recommended to add an interface to query the effective space size of the current queue, that is, to query the remaining space size of the queue. 2. When dequeuing a queue and checking whether the queue is empty or full, it is recommended to add critical protection to the interface to prevent the head and tail of the queue from being messed up when data is sent and received quickly, resulting in incorrect dequeuing. But this can be written on the external interface. 3. The original poster's comments are inconsistent with the source code. For example, the return parameter of the dequeue interface is the actual length read, not your True or False.

懒猫爱飞

RCSN posted on 2018-11-29 20:35 Thank you for sharing. However, there are a few points that are not really suggestions for the OP. 1. It is recommended to add an interface to query the effective space size of the current queue, that is, to check...

Thank you for your guidance, I read it carefully and the guidance is in place! Thank you very much! 1) This is just a simple test, no complex functions are added 2) The comments are copied from the above, and I really didn't notice them 3) I will pay attention to some things next time

tiankai001

Yes, the post is well organized and comfortable to read. Of course, the most important thing is that the content is good enough.

懒猫爱飞

tiankai001 posted on 2018-12-9 13:29 Not bad, the post is well organized and comfortable to read. Of course, the most important thing is that the content is good enough

Record the code and share it at the same time. It is better to share the joy with others than to enjoy it alone^_^