嵌入式常用模块之——环形队列（1）

简单聊聊

在嵌入式开发时候，有很对模块是经常会使用到的。从这篇文字开始，将我觉得一些常用的模块逐一做一个整理。梳理一下自己的思路，也顺便方便大家，如果可以给初学者一点帮助和启发，那也是再好不过了。
环形队列在异步接收数据上感觉不能更爽。关于环形队列详细讲解说明网上也很多了，我就简单说一下了。为了减少动态分配回收内存开销。我写的队列使用的是线性存储方式。所谓环形队列不过把线性表利用指针等方式模拟成一个环形结构。让人在使用上看起来是一个环形的。简单说就是到达数组尾部后回溯到头部重新开始。

对我实现方式的介绍

1. 首先要说的一点。加入队列到尾部还有20字节，这时候要存21字节数据的话，有两种方式，第一种是前20字节存尾部20字节，最后1字节存到队头。这种方式实现是真正的环形队列。第二种方式是浪费掉这尾部20字节，数据全部从头开始存，占用头部21字节空间。这样的话浪费了一定空间，也就是说如果头部没有21字节空闲，数据就放不下了。我使用的是第二种方式，虽然浪费一点空间，但是实现和管理上比较简单。(PS:这里有必要提一下，我所描述的头部和尾部，特指实际数据的头尾，不是所实现的队列的头尾)。
2. 这种方式实现的队列适合存取一些长度变化较大的数据。至于存取长度基本等长的数据，这样实现也是可以的，下篇我会用另一种方式实现队列，那种方式个人认为更适合一点存取等长数据。我也是这么做的。
3. 不排除我的代码有遗漏的边界测试。如果要用于项目请自行检查一下。

代码部分

初始化是必须的,毕竟用了指针。必须初始化一下，不能让他撒野。万一野指针搞出个bug简直想哭。

void ringInit(pTest t)
{

    int i;
    t->putCount = 0;
    t->getCount = 0;
    t->head = t->buff;
    t->tail = t->buff;
    for(i = 0; i < MAX_LEN; i++)
    {
        t->size[i] = 0;
    }
}

其他部分突然觉得没啥可说的，那就这样吧。

完整代码

#include <stdio.h>

#define TEST 1

#define MAX_BUFF (1024) // 队列数据段总的长度
#define MAX_LEN (10) // 队列中数据段个数

typedef struct __test
{
    unsigned char *head; //头指针(进队列指针)
    unsigned char *tail; //尾指针(出队列指针)
    unsigned int size[MAX_LEN]; //保存每个数据段的长度
    unsigned char putCount; //进队列个数
    unsigned char getCount; //出队列个数
    unsigned char buff[MAX_BUFF]; //数据buff
}Test,*pTest;
/******************************
* @funcation: 初始化队列
* @auther: main_h_
* @time: 2018/9/6
* @param:  pTest[in]
* @return: None
******************************/
void ringInit(pTest t)
{

    int i;
    t->putCount = 0;
    t->getCount = 0;
    t->head = t->buff;
    t->tail = t->buff;
    for(i = 0; i < MAX_LEN; i++)
    {
        t->size[i] = 0;
    }
}
/******************************
* @funcation: 返回一个进队列指针
* @auther: main_h_
* @time: 2018/9/6
* @param:  t[in]  len[in]
* @return: 如果buff有空闲则返回
    一个进队列指针，否则返回NULL
******************************/
unsigned char* ringPut(pTest t,int len)
{
    unsigned char *ret = t->head;
    t->head += len;
    if(t->head >= t->buff+MAX_BUFF)
    {
        if(t->tail - t->buff > len)
        {
            t->head = t->buff+len;
            t->size[t->putCount%MAX_LEN] = len;
            t->putCount++;
            return t->buff;
        }
        return NULL;
    }
    else
    {
        t->size[t->putCount%MAX_LEN] = len;
        t->putCount++;
        return ret;
    }
}
/******************************
* @funcation: 返回一个出队列指针
* @auther: main_h_
* @time: 2018/9/6
* @param:  t[in]  len[out]
* @return: 如果buff有数据则返回
    一个出队列指针，否则返回NULL
******************************/
unsigned char* ringGet(pTest t,int *len)
{
    unsigned char *ret = t->tail;
    if(t->getCount >= t->putCount)
    {
        return NULL;
    }
    t->tail += t->size[t->getCount%MAX_LEN];
    *len = t->size[t->getCount%MAX_LEN];
    if(t->tail >= t->buff + MAX_BUFF)
    {
        t->tail = t->buff + t->size[t->getCount%MAX_LEN];
        ret = t->buff;
    }
    t->getCount++;
    return ret;
}
/******************************
* @funcation: 返回队列状态
* @auther: main_h_
* @time: 2018/9/6
* @param:  t[in]
* @return: 队列为空返回1，否则返回0
******************************/
unsigned char ringEmpty(const pTest t)
{
    if(t->tail != t->head)
        return 0;
    return 1;
}
int main()
{
#ifdef TEST
    int i = 0,len = 0;
    unsigned char *ptr = NULL;
    Test t;
    ringInit(&t);
    printf("isEmpty:%d\n",ringEmpty(&t));
    ptr = ringPut(&t,1020);
    if(ptr != NULL)
    {
        for(i = 0; i < 100; i++)
        {
            ptr[i] = i%256;
        }
    }
    ptr = ringGet(&t,&len);
    printf("isEmpty:%d",ringEmpty(&t));
    ptr = ringPut(&t,4);
    printf("\n\nNULL............ :%x\n\n",ptr);
    if(ptr != NULL)
    {
        for(i = 0; i < 4; i++)
        {
            ptr[i] = i+20;
        }
    }
    ptr = ringGet(&t,&len);
    if(ptr != NULL)
    {
        printf("len:%d\n",len);
        for(i = 0; i < len; i++)
        {
            printf("%2d ",ptr[i]);
        }
    }
    printf("isEmpty:%d\n",ringEmpty(&t));
    printf("\n");
    ptr = ringPut(&t,20);
    printf("\n\n\n%x\n",ptr);
    if(ptr != NULL)
    {
        //
        for(i = 0; i < 20; i++)
        {
            ptr[i] = i+30;
        }
    }
    printf("\n");
    ptr = ringGet(&t,&len);
    if(ptr != NULL)
    {
        printf("len:%d\n",len);
        for(i = 0; i < len; i++)
        {
            printf("%2d ",ptr[i]);
        }
    }
    printf("\n");
    ptr = ringGet(&t,&len);
    if(ptr != NULL)
    {
        printf("len:%d\n",len);
        for(i = 0; i < len; i++)
        {
            printf("%2d ",ptr[i]);
        }
    }
    ptr = ringPut(&t,20);
    printf("\n\nNULL :%x\n\n",ptr);
    if(ptr != NULL)
    {
        for(i = 0; i < 20; i++)
        {
            ptr[i] = i*3;
        }
    }
    ptr = ringPut(&t,210);
    printf("\n\nNULL :%x\n\n",ptr);
    if(ptr != NULL)
    {
        for(i = 0; i < 210; i++)
        {
            ptr[i] = i+3;
        }
    }
    printf("\nisEmpty:%d\n",ringEmpty(&t));
    ptr = ringGet(&t,&len);
    if(ptr != NULL)
    {
        printf("len:%d\n",len);
        for(i = 0; i < len; i++)
        {
            printf("%2d ",ptr[i]);
        }
    }
    printf("\n");
    printf("\nisEmpty:%d\n",ringEmpty(&t));
        ptr = ringGet(&t,&len);
    if(ptr != NULL)
    {
        printf("len:%d\n",len);
        for(i = 0; i < len; i++)
        {
            printf("%2x ",ptr[i]);
        }
    }
    printf("\nisEmpty:%d\n",ringEmpty(&t));
    printf("\n");
    ptr = ringPut(&t,21);
    ptr = ringPut(&t,21);
    ptr = ringPut(&t,21);
    ptr = ringPut(&t,210);
    ptr = ringPut(&t,210);
    ptr = ringPut(&t,210);
    ptr = ringPut(&t,210);
    ptr = ringPut(&t,210);
    ptr = ringPut(&t,210);
    ptr = ringGet(&t,&len);
    ptr = ringGet(&t,&len);
    ptr = ringGet(&t,&len);
    ptr = ringGet(&t,&len);
    ptr = ringGet(&t,&len);
    ptr = ringGet(&t,&len);
    ptr = ringGet(&t,&len);
    ptr = ringGet(&t,&len);
    ptr = ringGet(&t,&len);
//  ptr = ringGet(&t,&len);
    printf("\nisEmpty:%d\n",ringEmpty(&t));
    printf("%x\n",ptr);
#endif
    return 0;
}