进阶循环队列
大家好，好久不见，没更新的日子里都在躺平，从几年前的精通C语言，到现在的只是熟悉C语言，对C越来越不熟悉了，最近有用到循环队列，本文不再介绍简单的实现队列，而是进阶的循环队列，废话不多说。
队列是什么
队列就是FIFO（First Input First Output）的一种线性表，当然也可以通过链表进行实现。允许从一端放入数据，从另一端取出数据。
上图中展示了普通队列的方式，本文主要讲解循环队列，如果不理解本文的实现方式，可以从网上查看其他博主写的循环队列实现方式，网上一般主要是一个front和一个rear，当入队时，rear指针向尾部移动，front指针则依旧指向首元素，当出队时，front指针向下一个元素移动，释放出队元素，尾指针不变。
但是在实际的应用中，并不适用，比如系统中的IO读写需要读写循环队列，来一个写的命令，当资源不足的时候可以挂到写队列中，系统从队头取写命令，归根结底就是提高性能，所以队列用链表实现就比较拉胯，不推荐。
要注意的是本文实现方式队头队尾都是自加，当队列中有数据的时候，input数值比output数值大。
本文将使用上文提到的类似方式实现，本质上也是用线性表实现循环队列，一种带头的循环队列，欢迎大家一起交流，本文代码已经经过简单的测试，如有错误欢迎指正，一起共同学习。
循环队列结构定义
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 }
运行测试
吾心信其可行，
则移山填海之难，
终有成功之日！
——孙文
则移山填海之难，
终有成功之日！
——孙文
评论
0 评论
