打印

通用队列及其应用

[复制链接]
1411|15
手机看帖
扫描二维码
随时随地手机跟帖
跳转到指定楼层
楼主
会笑的星星|  楼主 | 2020-1-8 18:37 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
本帖最后由 会笑的星星 于 2020-1-8 20:09 编辑

队列在我们编程的过程中经常会使用到,有时候一个项目中可能会使用多个不同的队列,为此我们可能需要编写多个针对不同队列的代码。虽然不同队列的数据内容、数据长度各不相同,但是出队与入队之类的操作却是一模一样的。因此,如果我们只是因为存储的内容或者长度不一样而编写多个不同的队列操作代码就会出现很多重复代码。为此,我设计了一个通用队列,仅使用一组接口就能操作多个不同的队列,而且具有比较好的适用性。

先上代码,再举几个例子。由于代码并不复杂,我只做了一些简单的注释,如果有不明白请提问。
//app_queue.h

#ifndef _APP_QUEUE_
#define _APP_QUEUE_

//#include "stdint.h"

typedef unsigned char uint8_t;
typedef unsigned int uint16_t;

typedef enum
{
  Q_NONE,
  Q_NON_NONE,
  Q_S_NONE,
  Q_S_OK,
}Q_status_t;

//如果你的队列很长,或者队列中每个元素占用的字节较多,最好把q_t的类型改为uint16_t.
//原则上:当队列长度*队列中一个元素所占用的字节数量 小于 256时,q_t的类型使用uint8_t即可.
//             当队列长度*队列中一个元素所占用的字节数量 大于 255时,q_t的类型必须使用uint16_t.
typedef uint8_t q_t;
typedef q_t *pq_t;

typedef uint8_t *pq_data_t;

typedef struct
{
  q_t head;
  q_t end;
  q_t q_len;
}pos_t;

//函数功能:初始化队列.
//p_q      : 队列指针
//q_max    : 队列元素个数
//a_size   : 队列中一个元素的字节数量
void app_queue_init(pq_t p_q, q_t q_max,uint8_t a_size);

//函数功能:入队操作,将p_src指向的数据以及其后a_size个字节数据入队.
void app_enqueue(pq_t p_q, pq_data_t p_src, uint8_t a_size);

//函数功能:出队操作,从p_q指向的队列弹出一个元素,这个元素的首地址
//         保存在p_des中,这个元素的字节数量为a_size.
void app_dequeue(pq_t p_q, pq_data_t p_des, uint8_t a_size);

//函数功能:判断队列是否为空.

//函数返回: Q_NONE      --- 表示队列为空
//          Q_NON_NONE  --- 表示队列非空
uint8_t app_queue_none(pq_t p_q);

//函数功能:判断p_q指向的队列中是否存在与目标元素相同的元素,如果有
//         返回Q_S_OK,否则返回Q_S_NONE.
//         所谓的目标元素,指的是p_src指向,大小为a_size的一个数据块

//函数返回:Q_S_NONE --- 不相同
//         Q_S_OK --- 相同
uint8_t app_queue_search(pq_t p_q, pq_data_t p_src, uint8_t a_size);

//函数功能:清空队列.
void app_queue_clr(pq_t p_q);


#endif
//app_queue.c

#include "app_queue.h"
#include "string.h"

void app_queue_init(pq_t p_q, q_t q_max,uint8_t a_size)
{
  pos_t p;
  uint8_t len;

  len = sizeof(pos_t);
  
  memcpy(&p, p_q, len);
  p.q_len = a_size * q_max;
  memcpy(p_q, &p, len);
}

void app_queue_clr(pq_t p_q)
{
  pos_t p;
  uint8_t len;

  len = sizeof(pos_t);
  
  memcpy(&p, p_q, len);
  p.end = 0;
  p.head = 0;
  memcpy(p_q, &p, len);
}

unsigned char app_queue_none(pq_t p_q)
{
  pos_t p;

  memcpy(&p, p_q, sizeof(pos_t));

  if(p.head == p.end)
  {
    return Q_NONE;
  }
  
  return Q_NON_NONE;
}

void app_enqueue(pq_t p_q, pq_data_t p_src, uint8_t a_size)
{
  pos_t p;
  uint8_t len;

  len = sizeof(pos_t);

  memcpy(&p, p_q, len);
  
  if(p.head == (p.end + a_size) % p.q_len)
  {
    return ;
  }

  memcpy((uint8_t *)(p_q+3)+p.end, p_src, a_size);
  p.end = (p.end + a_size) % p.q_len;

  memcpy(p_q, &p, len);
}

void app_dequeue(pq_t p_q, pq_data_t p_des, uint8_t a_size)
{
  pos_t p;
  uint8_t len;

  len = sizeof(pos_t);
  memcpy(&p, p_q, len);
   
  if(p.head == p.end)
  {
    return ;
  }

  memcpy(p_des, (uint8_t *)(p_q+3)+p.head, a_size);
  p.head = (p.head + a_size) % p.q_len;   
  
  memcpy(p_q, &p, len);
}

uint8_t app_queue_search(pq_t p_q, pq_data_t p_src, uint8_t a_size)
{
  pos_t p;
  uint8_t *ps,*pt,*pm;
  uint8_t i;

  memcpy(&p, p_q, sizeof(pos_t));
  
  ps = (uint8_t *)(p_q+3);

  while(p.head != p.end)
  {
    pt = ps + p.head;
    pm = p_src;
        
    for(i = 0; i < a_size; i++)
    {
       if(*pt++ != *pm++) break;
    }
        
    if(i == a_size)
    {
      return Q_S_OK;
    }
    else
    {
       p.head += a_size;
       if(p.head >= p.q_len)
       {
         p.head = 0;               
       }
    }
  }
  
  return Q_S_NONE;
}
应用例子:
#include "app_queue.h"

#define D_Q_MAX 10
#define R_Q_MAX 20

typedef struct
{
   uint8_t mac[4];
   uint8_t type;
  uint8_t event;
  uint8_t extend1;
}dev_evt_t;

typedef struct
{
//注意:在定义队列时,首先需要定义一个pos_t类型的变量,这个变量是一个占位变量,
//应用者只需要定义它,不需要对它操作。pos_t定义好后,紧接着定义你的队列。
  pos_t pos;
  dev_evt_t d_q[D_Q_MAX];
}dev_q_t;

typedef struct
{
  pos_t pos;
  uint16_t h_q[R_Q_MAX];
}rx_q_t;

dev_q_t dev_q;
rx_q_t rx_q;

main()
{
  //初始化队列dev_q
  app_queue_init((pq_t)&dev_q, D_Q_MAX, sizeof(dev_evt_t));

  //数据
  dev_evt_t dev,dev_read;
  dev.mac[0] = 0x01;
  dev.mac[1] = 0x02;
  dev.mac[2] = 0x03;
  dev.mac[3] = 0x04;
  dev.type = 0x06;
  dev.event = 0x07;

  //搜索队列中是否有重复数据,如果有,新的数据不会压入队列
  if(app_queue_search((pq_t)&dev_q,(pq_data_t)&dev, sizeof(dev_evt_t)) == Q_S_NONE)
  {
    dev_evt_t dev;
    dev.mac[0] = 0x01;
    dev.mac[1] = 0x02;
    dev.mac[2] = 0x03;
    dev.mac[3] = 0x04;
    dev.type = 0x06;
    dev.event = 0x07;
    //把数据压入队列。注意,不要忘记了地址符。
    app_enqueue((pq_t)&dev_q, (pq_data_t)&dev, sizeof(dev_evt_t));
  }
  
  //出队
  app_dequeue((pq_t)&dev_q, (pq_data_t)&dev_read, sizeof(dev_evt_t));
  if(dev_read.type == 0x06 && dev_read.event == 0x07)
  {
    //这样做没有任何意义,这里只做为例子展示
  }
  
  //同理,针对队列rx_q的操作与上述类似
  //初始化队列rx_q
  app_queue_init((pq_t)&rx_q, R_Q_MAX, sizeof(uint16_t));  
  
  uint16_t rx_evt,evt_read;
  rx_evt = 0xff01;
  //入队
  app_enqueue((pq_t)&rx_q, (pq_data_t)&rx_evt, sizeof(uint16_t));
  //出队
  app_dequeue((pq_t)&rx_q, (pq_data_t)&evt_read, sizeof(uint16_t));
  
  if(evt_read == 0xff01)
  {
     
  }
}
这个队列是经过实际检验的,所以如果你想用在自己的项目中,请放心使用,最后附上源码文件。

app_queue.zip (1.46 KB)


使用特权

评论回复

相关帖子

沙发
会笑的星星|  楼主 | 2020-1-8 18:39 | 只看该作者
沙发

使用特权

评论回复
板凳
tdh03z| | 2020-1-8 21:59 | 只看该作者
为啥要 搜索队列中是否有重复数据,队列只管压入和弹出吧,业务逻辑还是不用放在队列这块

使用特权

评论回复
地板
会笑的星星|  楼主 | 2020-1-8 23:10 | 只看该作者
tdh03z 发表于 2020-1-8 21:59
为啥要 搜索队列中是否有重复数据,队列只管压入和弹出吧,业务逻辑还是不用放在队列这块 ...

他们是一组相关的操作,就像操作链表一样,有添加,有删除,有查询。

使用特权

评论回复
5
yklstudent| | 2020-1-8 23:43 | 只看该作者
最好搞个队列用于串口的范例,不然新人不容易理解

使用特权

评论回复
6
llllll008| | 2020-1-9 08:11 | 只看该作者
有什么项目,是会用到队列的,我几乎没有遇到过要用队列的项目

使用特权

评论回复
7
会笑的星星|  楼主 | 2020-1-9 09:38 | 只看该作者
本帖最后由 会笑的星星 于 2020-1-9 09:50 编辑
llllll008 发表于 2020-1-9 08:11
有什么项目,是会用到队列的,我几乎没有遇到过要用队列的项目

需要处理非常多的并行事件的项目基本都用得着。比如一个主控设备管理者几十个甚至上百个从设备的项目就需要。

使用特权

评论回复
8
llllll008| | 2020-1-9 10:51 | 只看该作者
会笑的星星 发表于 2020-1-9 09:38
需要处理非常多的并行事件的项目基本都用得着。比如一个主控设备管理者几十个甚至上百个从设备的项目就需 ...

比如有那些比较常见的项目,在生活中,要用到队列

使用特权

评论回复
9
airwill| | 2020-1-11 14:17 | 只看该作者
队列是个比较常用的数据结构。 有各种操作方式。添加,删除,插入,排序等

使用特权

评论回复
10
wsnsyy| | 2020-1-13 14:42 | 只看该作者
初始化里面的取p.q_len做什么用了

使用特权

评论回复
11
lihui567| | 2020-1-31 16:51 | 只看该作者
可以参考一下

使用特权

评论回复
12
foxpro2005| | 2020-5-15 22:24 | 只看该作者
本帖最后由 foxpro2005 于 2020-5-15 22:27 编辑

实质就是把队列缓冲区数据类型变为字节类型,以支持任意类型的数据入队,从而实现队列通用(数据类型)目的
这样的好处是能通用, 有一点小弊端就是全部当作u8字节处理,在32位机上效率略降低了一点

见过"傻孩子"大神写的通用队列模板, 是以宏的方式实现模板, 以宏代码自己去生成用户需要的每种数据类型的全套队列代码, 这样的不好之处就是会有大量的重复(冗余)代码 (当然估计编译器会作适当优化吧,本来这个宏代码就是生成写给编译器去看的^|^...)

使用特权

评论回复
13
叶春勇| | 2020-5-15 22:36 | 只看该作者
foxpro2005 发表于 2020-5-15 22:24
实质就是把队列缓冲区数据类型变为字节类型,以支持任意类型的数据入队,从而实现队列通用(数据类型)目的
...

foxpro好熟悉的名字,还有foxbase

使用特权

评论回复
14
aerwa| | 2020-5-15 23:22 | 只看该作者
谢谢星星,能分享下您对状态机的独到见解不。我看到状态机用的最多的是Switch + if 组合。

使用特权

评论回复
15
andy520520| | 2020-12-8 09:01 | 只看该作者
memcpy(&p, p_q, len);
  p.q_len = a_size * q_max;
  memcpy(p_q, &p, len);
你看下网上的通用队列是怎么写的,创新?

使用特权

评论回复
16
diweo| | 2020-12-8 14:55 | 只看该作者
要说队列的话,就不要重复发明轮子了。直接C++标准库走起。

使用特权

评论回复
发新帖 我要提问
您需要登录后才可以回帖 登录 | 注册

本版积分规则

31

主题

96

帖子

16

粉丝