进阶循环队列

background0001.jpg

大家好,好久不见,没更新的日子里都在躺平,从几年前的精通C语言,到现在的只是熟悉C语言,对C越来越不熟悉了,最近有用到循环队列,本文不再介绍简单的实现队列,而是进阶的循环队列,废话不多说。

队列是什么

队列就是FIFO(First Input First Output)的一种线性表,当然也可以通过链表进行实现。允许从一端放入数据,从另一端取出数据。

001.png

上图中展示了普通队列的方式,本文主要讲解循环队列,如果不理解本文的实现方式,可以从网上查看其他博主写的循环队列实现方式,网上一般主要是一个front和一个rear,当入队时,rear指针向尾部移动,front指针则依旧指向首元素,当出队时,front指针向下一个元素移动,释放出队元素,尾指针不变。

但是在实际的应用中,并不适用,比如系统中的IO读写需要读写循环队列,来一个写的命令,当资源不足的时候可以挂到写队列中,系统从队头取写命令,归根结底就是提高性能,所以队列用链表实现就比较拉胯,不推荐。

要注意的是本文实现方式队头队尾都是自加,当队列中有数据的时候,input数值比output数值大。

本文将使用上文提到的类似方式实现,本质上也是用线性表实现循环队列,一种带头的循环队列,欢迎大家一起交流,本文代码已经经过简单的测试,如有错误欢迎指正,一起共同学习。

002.png

循环队列结构定义

1 typedef struct _FIFO_{
2     u32_t input;      //input 
3     u32_t output; //output
4     u32_t length;      //fifo length
5     u32_t element_size;    //data size
6     u64_t address;   // fifo start address
7 }fifo_t;

常用操作

初始化

 1 /**
 2  * @brief init fifo 
 3  * @param fifo pointer , fifo len , per variable size in fifo
 4  * @return SUCCESS/FAILURE
 5  */
 6 u32_t FIFO_INIT(fifo_t* fifo, u32_t length, u32_t element_size){
 7     //intialize variables
 8     fifo->input = 0;
 9     fifo->output = 0;
10     fifo->element_size = element_size;
11     //save fifo head address
12     fifo->address = ((u64_t)fifo) + sizeof(fifo_t);
13     //This defines that the queue capacity can only be a power of two.
14     if(!(is_power_of_two(length)) || length < 2){
15         fifo->length = 0;
16         return FAILURE;
17     }
18     fifo->length = length - 1;
19     memset((void*)fifo->address, 0, length * element_size);
20     return SUCCESS;
21 }

入队

 1 /**
 2  * @brief input data to fifo
 3  * @param fifo pointer , data , len
 4  * @return  len
 5  */
 6 u32_t FIFO_INPUT(fifo_t* fifo, const void* data, u32_t length){
 7     u32_t balance_fifo_num = FIFO_UNUSED(fifo) ;
 8     if(!balance_fifo_num)
 9         return FAILURE;
10     if(length > balance_fifo_num)
11         length = balance_fifo_num;
12     FIFO_COPY(fifo, data, length, fifo->input, _INPUT);
13     fifo->input += length;
14     return length;
15 }

出队

 1 /**
 2  * @brief output data to buff
 3  * @param fifo pointer , buf , len
 4  * @return 
 5  */
 6 u32_t FIFO_OUTPUT(fifo_t* fifo, void* buf , u32_t length){
 7     u32_t used_fifo_num = FIFO_USED(fifo);
 8     if(!used_fifo_num)
 9         return FAILURE;
10     if(length > used_fifo_num)
11         length = used_fifo_num;
12     FIFO_COPY(fifo, buf, length, fifo->output, _OUTPUT);
13     fifo->output += length;
14     return length;
15 }

队列剩余空间

1 /**
2  * @brief Free space in queue
3  * @param fifo pointer
4  * @return number
5  */
6 u32_t FIFO_UNUSED(fifo_t* fifo){
7     return ((fifo->length + 1) - (fifo->input - fifo->output));
8 }

队列已使用空间

1 /**
2  * @brief Used space in queue
3  * @param fifo pointer
4  * @return number
5  */
6 u32_t FIFO_USED(fifo_t* fifo){
7     return (fifo->input - fifo->output);
8 }

获取头结点

 1 /**
 2  * @brief get queue head
 3  * @param fifo pointer
 4  * @return head address
 5  */
 6 void* FIFO_GET_HEAD(fifo_t* fifo){
 7     // fifo->address
 8     u32_t offset = 0;
 9     offset &= fifo->length;
10     offset *= fifo->element_size;
11     return (void*)fifo->address + offset;
12 }

本文介绍了一种循环队列的实现方式,使用此种方式的主要原因就是提高性能,而不是简单的理解循环队列,在底层系统中,资源比较紧张,循环队列是一种很好的结构,性能高,资源固定,实现也很简单。

最后很抱歉没有在代码中进行注释,阅读可能比较吃力。

附全部代码

Makefile

 1 CC = gcc
 2 CFLAGS = -I.
 3 DEPS = fifo.h
 4 OBJ = main.o fifo.o 
 5 
 6 %.o: %.c $(DEPS)
 7 $(CC) -c -o $@ $< $(CFLAGS)
 8 
 9 fifo: $(OBJ)
10 $(CC) -o $@ $^ $(CFLAGS)
11 
12 .PHONY: clean
13 
14 clean:
15 rm -f fifo *.o

fifo.h

 1 /****************************************************************
 2   *@file       : fifo.h
 3   *@description: 
 4   *@time       : 2023/08/21 20:26:50
 5   *@author     : Nick Xia
 6   *@blog       : https://aeneag.xyz
 7 *****************************************************************/
 8 #ifndef _FIFO_H
 9 #define _FIFO_H
10 
11 #include <memory.h>
12 typedef unsigned char u8_t;
13 typedef unsigned short u16_t;
14 typedef unsigned int u32_t;
15 typedef unsigned long long u64_t;
16 
17 typedef struct _FIFO_{
18     u32_t input;
19     u32_t output;
20     u32_t length;
21     u32_t element_size;
22     u64_t address;
23 }fifo_t;
24 
25 #define is_power_of_two(x) ((x) != 0 && (((x) & ((x)-1)) == 0))
26 #define MIN(a, b) (((a) < (b)) ? (a) : (b))
27 #define fifo_total_size(length, element_size) ((length)*(element_size)+(sizeof(fifo_t)))
28 
29 #define SUCCESS 0
30 #define FAILURE 1
31 #define _INPUT 0
32 #define _OUTPUT 1
33 
34 u32_t FIFO_UNUSED(fifo_t* fifo);
35 u32_t FIFO_USED(fifo_t* fifo);
36 u32_t FIFO_INIT(fifo_t* fifo, u32_t length, u32_t element_size);
37 u32_t FIFO_INPUT(fifo_t* fifo, const void* data, u32_t length);
38 u32_t FIFO_OUTPUT(fifo_t* fifo, void* data, u32_t length);
39 void* FIFO_GET_HEAD(fifo_t* fifo);
40 
41 #endif // !_FIFO_H

fifo.c

  1 /****************************************************************
  2   *@file       : fifo.c
  3   *@description: 
  4   *@time       : 2023/08/21 20:27:06
  5   *@author     : Nick Xia
  6   *@blog       : https://aeneag.xyz
  7 *****************************************************************/
  8 #include "fifo.h"
  9 
 10 /**
 11  * @brief init fifo 
 12  * @param fifo pointer , fifo len , per variable size in fifo
 13  * @return SUCCESS/FAILURE
 14  */
 15 u32_t FIFO_INIT(fifo_t* fifo, u32_t length, u32_t element_size){
 16     //intialize variables
 17     fifo->input = 0;
 18     fifo->output = 0;
 19     fifo->element_size = element_size;
 20     //save fifo head address
 21     fifo->address = ((u64_t)fifo) + sizeof(fifo_t);
 22     //This defines that the queue capacity can only be a power of two.
 23     if(!(is_power_of_two(length)) || length < 2){
 24         fifo->length = 0;
 25         return FAILURE;
 26     }
 27     fifo->length = length - 1;
 28     memset((void*)fifo->address, 0, length * element_size);
 29     return SUCCESS;
 30 }
 31 /**
 32  * @brief Free space in queue
 33  * @param fifo pointer
 34  * @return number
 35  */
 36 u32_t FIFO_UNUSED(fifo_t* fifo){
 37     return ((fifo->length + 1) - (fifo->input - fifo->output));
 38 }
 39 /**
 40  * @brief Used space in queue
 41  * @param fifo pointer
 42  * @return number
 43  */
 44 u32_t FIFO_USED(fifo_t* fifo){
 45     return (fifo->input - fifo->output);
 46 }
 47 /**
 48  * @brief get data or copy data
 49  * @param fifo pointer , data or buff , numbers , address , flag
 50  * @return 
 51  */
 52 static void FIFO_COPY(fifo_t* fifo, const void* src_or_dst, u32_t length, u32_t offset, u32_t FLAG){
 53     u32_t fifo_length = fifo->length + 1;
 54     u32_t fifo_element_size = fifo->element_size;
 55 
 56     offset &= fifo->length;
 57 
 58     length *= fifo_element_size;
 59     fifo_length *= fifo_element_size;
 60     offset *= fifo_element_size;
 61 
 62     u32_t tmp = MIN(length, fifo_length - offset);
 63     if(FLAG == _INPUT){
 64         memcpy((void *)fifo->address + offset, src_or_dst, tmp);
 65         memcpy((void *)fifo->address, src_or_dst + tmp, length - tmp);
 66     }else if(FLAG == _OUTPUT){
 67         memcpy((void *)src_or_dst, (const void *)fifo->address + offset, tmp);
 68         memcpy( (void *)src_or_dst + tmp, (const void *)fifo->address, length - tmp);
 69     }
 70 }
 71 /**
 72  * @brief input data to fifo
 73  * @param fifo pointer , data , len
 74  * @return  len
 75  */
 76 u32_t FIFO_INPUT(fifo_t* fifo, const void* data, u32_t length){
 77     u32_t balance_fifo_num = FIFO_UNUSED(fifo) ;
 78     if(!balance_fifo_num)
 79         return FAILURE;
 80     if(length > balance_fifo_num)
 81         length = balance_fifo_num;
 82     FIFO_COPY(fifo, data, length, fifo->input, _INPUT);
 83     fifo->input += length;
 84     return length;
 85 }
 86 /**
 87  * @brief output data to buff
 88  * @param fifo pointer , buf , len
 89  * @return 
 90  */
 91 u32_t FIFO_OUTPUT(fifo_t* fifo, void* buf , u32_t length){
 92     u32_t used_fifo_num = FIFO_USED(fifo);
 93     if(!used_fifo_num)
 94         return FAILURE;
 95     if(length > used_fifo_num)
 96         length = used_fifo_num;
 97     FIFO_COPY(fifo, buf, length, fifo->output, _OUTPUT);
 98     fifo->output += length;
 99     return length;
100 }
101 /**
102  * @brief get queue head
103  * @param fifo pointer
104  * @return head address
105  */
106 void* FIFO_GET_HEAD(fifo_t* fifo){
107     // fifo->address
108     u32_t offset = 0;
109     offset &= fifo->length;
110     offset *= fifo->element_size;
111     return (void*)fifo->address + offset;
112 }

Main.c

 1 /****************************************************************
 2   *@file       : main.c
 3   *@description: 
 4   *@time       : 2023/08/21 20:27:14
 5   *@author     : Nick Xia
 6   *@blog       : https://aeneag.xyz
 7 *****************************************************************/
 8 #include "fifo.h"
 9 #include <stdio.h>
10 
11 //Defines a queue type
12 typedef struct _fifo_struct_{
13     u8_t data1;
14     u8_t data2;
15     u16_t data3;
16     u32_t data4;
17     u64_t data5;
18 }__attribute__((packed)) data_t;
19 
20 //Declaring a circular queue
21 u8_t g_fifo[fifo_total_size(64,sizeof(data_t))];
22 
23 /**
24  * @brief main function
25  * @param 
26  * @return 0
27  */
28 int main(void){
29     u32_t ret = FIFO_INIT((fifo_t*)g_fifo,64,sizeof(data_t));
30     data_t data[3];
31     int j = 1;
32     for(int i= 0; i < 3; ++i){
33         data[i].data1 = (u8_t)j;++j;
34         data[i].data2 = (u8_t)j;++j;
35         data[i].data3 = (u16_t)++j;
36         data[i].data4 = (u32_t)j;++j;
37         data[i].data5 = (u64_t)j;++j;
38     }
39     FIFO_INPUT((fifo_t*)g_fifo, (void*)data,3);
40     FIFO_INPUT((fifo_t*)g_fifo, (void*)data,3);
41     
42 
43     printf("used %d\n",FIFO_USED((fifo_t*)g_fifo));
44     printf("unused %d\n",FIFO_UNUSED((fifo_t*)g_fifo));
45 
46     data_t get_buff;
47     FIFO_OUTPUT((fifo_t*)g_fifo, (void*)&get_buff,1);
48     printf("data1-%d, data2-%d, data3-%d, data4-%d, data5-%lld\n",get_buff.data1,get_buff.data2,get_buff.data3,get_buff.data4,get_buff.data5);
49     printf("used %d\n",FIFO_USED((fifo_t*)g_fifo));
50 
51     data_t buff[4] = {0};
52     FIFO_OUTPUT((fifo_t*)g_fifo, (void*)buff,4);
53     for(int i = 0 ; i < 4 ; ++i){
54     printf("data1-%d, data2-%d, data3-%d, data4-%d, data5-%lld\n",buff[i].data1,buff[i].data2,buff[i].data3,buff[i].data4,buff[i].data5);
55     }
56     printf("used %d\n",FIFO_USED((fifo_t*)g_fifo));
57     printf("unused %d\n", FIFO_UNUSED((fifo_t*)g_fifo));
58 
59     FIFO_INPUT((fifo_t*)g_fifo, (void*)data,3);
60     printf("used %d\n",FIFO_USED((fifo_t*)g_fifo));
61     printf("unused %d\n", FIFO_UNUSED((fifo_t*)g_fifo));
62     return 0;
63 }

运行测试

003.png


    


公众号'艾恩凝'
个人公众号
个人微信
个人微信
    吾心信其可行,
          则移山填海之难,
                  终有成功之日!
                                  ——孙文
    评论
    0 评论
avatar

取消