关于循环队列的应用

懒猫爱飞

关于循环队列的应用 [复制链接]

关于循环队列的应用

                                               Author : Mark Xu

关于循环队列的应用.pdf (605.59 KB, 下载次数: 10)

2018-11-29 16:04 上传

点击文件名下载附件

开发的USB项目中会用到连续的存取数据，于是在写了个简单的循环队列，循环队列的好处就是首尾相连节省空间，关于循环队列的概念课本上已说的很清楚，网上也有大量的博客文档，图文并茂，这里就不在赘述了，下面仅把代码做一下整理，相当于备份吧^_^

总共有两个源文件Xc_CircleQueue.c 与Xc_CircleQueue.h

1)       Xc_CircleQueue.c源代码

/******************************************************************************************
* Copyright(c) 2018, Mark Xu WorK Studio. Allrights reserved.
*
*  FileName :  Xc_CircleQueue.c
*
*  Brief    :  aboutthe circle queue application
*
*  Author : Mark Xu
*
*  Date   : 2018年10月12日
*
*  Version: V1.0
*
*  Remark : None
*
*-----------------------------------------------------------------------------------------------------------------------------------------------
*  History:
*
*   1) Author: xx xx
*
*     ModifyDate : xx xx xx
*
*     Modifycontents : xx xx xx xx xx
******************************************************************************************/
#define XC_CIRCLEQUEUE_IMPLEMENT

#include
#include
#include
#include
#include "Xc_CircleQueue.h"

/************************************************************************************
* 函数名称 : Circle_Queue_Init
*
* 函数描述 : Initial the queue
*
* 入口参数 : *rbuf - the queue
*
*          *array - the data buffer
*
*          len - the depth of the queue
*
* 出口参数 : TRUE - initial successful
*
* 函数备注 : None
*************************************************************************************/
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;
}

/************************************************************************************
* 函数名称 : RingBuf_Clear
*
* 函数描述 : clear the queue
*
* 入口参数 : *rbuf - the queue
*
* 出口参数 : None
*
* 函数备注 : None
*************************************************************************************/
voidRingBuf_Clear(RingBuf_T *rbuf)
{
         rbuf->fillCnt =  0;
         rbuf->Head =  0;
         rbuf->Tail  =  0;
}


/************************************************************************************
* 函数名称 : RingBuf_Chk_Full
*
* 函数描述 : clear the queue
*
* 入口参数 : *rbuf - the queue
*
* 出口参数 : true - full     false - not full
*
* 函数备注 : judging condition -(tail+1) % buf_size_max == head
*************************************************************************************/
uint16_tRingBuf_Chk_Full(RingBuf_T *rbuf)
{
         return((rbuf->Tail + 1)%rbuf->Depth ==  rbuf->Head);
}

/************************************************************************************
* 函数名称 : RingBuf_Chk_Empty
*
* 函数描述 : check the queue empty ornot
*
* 入口参数 : *rbuf - the queue
*
* 出口参数 : true - empty    false - not empty
*
* 函数备注 : judging condition - tail ==head
*************************************************************************************/
uint16_tRingBuf_Chk_Empty(RingBuf_T *rbuf)
{
         return(rbuf->Tail  ==  rbuf->Head);
}


/************************************************************************************
* 函数名称 : RingBuf_Write_Bytes
*
* 函数描述 : push the data to queue
*
* 入口参数 : *rbuf - the queue
*
*          *pValue - the value to be push
*
*          size  - the bytes of the valuebuffer
*
* 出口参数 : size  - the bytes of be write bytes
*
* 函数备注 : none
*************************************************************************************/
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))
                return 0;

         if((ringBuf_bw+ size) <= ringBuf_len)
         {
                   memcpy((uint8_t*)&ringBuf_source[ringBuf_bw],pValue,size);
         }
         else
         {
                   len = ringBuf_len -ringBuf_bw;

                   memcpy(ringBuf_source+ringBuf_bw,pValue,len);
                   memcpy(ringBuf_source,pValue+ringBuf_bw,(size-len));
         }
         
         // 计算Tail 的位置
         rbuf->Tail = (rbuf->Tail + size)% rbuf->Depth;
         rbuf->fillCnt += size;
         
         returnsize;
}

/************************************************************************************
* 函数名称 : RingBuf_Write_Bytes
*
* 函数描述 : Read the data from thequeue
*
* 入口参数 : *rbuf - the queue
*
*          *pValue - the data buffer to store the read data
*
*          size  - the bytes of the valuebuffer
*
* 出口参数 : size  - the bytes of be read
*
* 函数备注 : none
*************************************************************************************/
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;
         
         // 如果为空则返回0
         if(RingBuf_Chk_Empty(rbuf))
                return 0;

         // 当tial等于head时，说明队列为空
         if(rbuf->fillCnt== 0)
         {
//               printf("Buffer isempty,nothing to be read \r\n");
                   return 0;   
         }
         
         // 只读取有效数据
         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)       Xc_CircleQueue.h源代码

/******************************************************************************************    * Copyright(c) 2018, Mark Xu Work Studio.  All rights reserved.    *    * 文件名称 : Xc_Queue.h    *    * 文件描述 : 关于队列模块的一些声明与定义    *    * 文件作者 : Mark Xu    *    * 创建日期 : 2018年10月10日    *    * 当前版本 : V1.0    *    * 文件备注 : None    *    *----------------------------------------------------------------------------------------    * 修改记录 :    *    *   1)  修改人员 : xx xx    *    *       修改日期 : xx xx xx    *    *       修改内容 : xx xx xx xx xx   ******************************************************************************************/   #ifndef __XC_CIRCLEQUEUE_H__   #define __XC_CIRCLEQUEUE_H__      //------------------------------------------------------------------------------------------------------------------------------------------------   //  Precompile   //-----------------------------------------------------------------------------------------------------------------------------------------------   #ifdef XC_CIRCLEQUEUE_IMPLEMENT       #define CIRCLEQUEUE_EXTERN   #else       #define CIRCLEQUEUE_EXTERN       extern   #endif /* XC_CIRCLEQUEUE_IMPLEMENT */         #include "stdio.h"   #include "stdlib.h"   #include "stdint.h"   #include "string.h"      //------------------------------------------------------------------------------------------------------------------------------------------------   //  数据类型声明   //------------------------------------------------------------------------------------------------------------------------------------------------   /*     说明：       1. fillCnt 是计数队列中的元素个数       2. 当向队列中插入元素时，fillCnt 要增加       3. 当从队列中读取元素时，fillCnt 要减少       4. 当fillCnt为0时说明队列中没有元素，不可读取   */   #pragma pack(4)   typedef struct RingBuf_t{       uint8_t *Buf;     /* 指向队列数组的指针 */       uint16_t Depth;   /* 可存储的元素的个数 */       uint16_t Head;    /* 队头,也是读取的指针 */       uint16_t Tail;     /* 队尾,也是写的指针 */       uint16_t fillCnt;   /* 元素计数  */   }RingBuf_T;   #pragma pack()      // 指针形式   typedef RingBuf_T*   RingBuf_Tp;      //------------------------------------------------------------------------------------------------------------------------------------------------   //  函数声明   //------------------------------------------------------------------------------------------------------------------------------------------------   CIRCLEQUEUE_EXTERN  uint8_t Circle_Queue_Init(RingBuf_T *rbuf, uint8_t *array, uint16_t len);      CIRCLEQUEUE_EXTERN  void RingBuf_Clear(RingBuf_T  *rbuf);      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);         #endif /* __XC_CIRCLEQUEUE_H__ */

此内容由EEWORLD论坛网友懒猫爱飞原创，如需转载或用于商业用途需征得作者同意并注明出处

懒猫爱飞

吸取上一贴教训，这一贴的代码单独粘贴，果真效果好很多

btty038

看不懂，来支持哈

RCSN

谢谢分享。不过有几点不算建议的给楼主
1、建议加入一个接口，可以查询当前队列的有效空间大小，也就是查询队列的剩余空间大小
2、队列的出列、检查队列是否空或者满，接口建议加上临界保护，防止队列首尾在数据收发比较快的时候乱了，导致出列不对。不过这个可以在对外接口上写。
3、楼主的注释与源码不符吧。比如出列接口，返回参数是读出来的实际长度，并不是你的True或者False吧

懒猫爱飞

RCSN 发表于 2018-11-29 20:35
谢谢分享。不过有几点不算建议的给楼主
1、建议加入一个接口，可以查询当前队列的有效空间大小，也就是查 ...

谢谢大神指点，看的仔细，指导的到位！非常感谢！
1） 这只是一个简单的测试，没有添加复杂的功能
2） 注释是拷贝上面的，确实没有注意到
3）我下次注意一些

tiankai001

不错，帖子整理的很好，让人看着舒服，当然，最主要还是内容足够好

懒猫爱飞

tiankai001 发表于 2018-12-9 13:29
不错，帖子整理的很好，让人看着舒服，当然，最主要还是内容足够好

记录一下代码，同时做一下分享，独乐乐不如与众乐^_^