进阶循环队列
大家好，好久不见，没更新的日子里都在躺平，从几年前的精通C语言，到现在的只是熟悉C语言，对C越来越不熟悉了，最近有用到循环队列，本文不再介绍简单的实现队列，而是进阶的循环队列，废话不多说。
队列是什么
队列就是FIFO（First Input First Output）的一种线性表，当然也可以通过链表进行实现。允许从一端放入数据，从另一端取出数据。
上图中展示了普通队列的方式，本文主要讲解循环队列，如果不理解本文的实现方式，可以从网上查看其他博主写的循环队列实现方式，网上一般主要是一个front和一个rear，当入队时，rear指针向尾部移动，front指针则依旧指向首元素，当出队时，front指针向下一个元素移动，释放出队元素，尾指针不变。
但是在实际的应用中，并不适用，比如系统中的IO读写需要读写循环队列，来一个写的命令，当资源不足的时候可以挂到写队列中，系统从队头取写命令，归根结底就是提高性能，所以队列用链表实现就比较拉胯，不推荐。
要注意的是本文实现方式队头队尾都是自加，当队列中有数据的时候，input数值比output数值大。
本文将使用上文提到的类似方式实现，本质上也是用线性表实现循环队列，一种带头的循环队列，欢迎大家一起交流，本文代码已经经过简单的测试，如有错误欢迎指正，一起共同学习。
循环队列结构定义
typedef struct _FIFO_{
u32_t input; //input
u32_t output; //output
u32_t length; //fifo length
u32_t element_size; //data size
u64_t address; // fifo start address
}fifo_t;
常用操作
初始化
/**
* @brief init fifo
* @param fifo pointer , fifo len , per variable size in fifo
* @return SUCCESS/FAILURE
*/
u32_t FIFO_INIT(fifo_t* fifo, u32_t length, u32_t element_size){
//intialize variables
fifo->input = 0;
fifo->output = 0;
fifo->element_size = element_size;
//save fifo head address
fifo->address = ((u64_t)fifo) + sizeof(fifo_t);
//This defines that the queue capacity can only be a power of two.
if(!(is_power_of_two(length)) || length < 2){
fifo->length = 0;
return FAILURE;
}
fifo->length = length - 1;
memset((void*)fifo->address, 0, length * element_size);
return SUCCESS;
}
入队
/**
* @brief input data to fifo
* @param fifo pointer , data , len
* @return len
*/
u32_t FIFO_INPUT(fifo_t* fifo, const void* data, u32_t length){
u32_t balance_fifo_num = FIFO_UNUSED(fifo) ;
if(!balance_fifo_num)
return FAILURE;
if(length > balance_fifo_num)
length = balance_fifo_num;
FIFO_COPY(fifo, data, length, fifo->input, _INPUT);
fifo->input += length;
return length;
}
出队
/**
* @brief output data to buff
* @param fifo pointer , buf , len
* @return
*/
u32_t FIFO_OUTPUT(fifo_t* fifo, void* buf , u32_t length){
u32_t used_fifo_num = FIFO_USED(fifo);
if(!used_fifo_num)
return FAILURE;
if(length > used_fifo_num)
length = used_fifo_num;
FIFO_COPY(fifo, buf, length, fifo->output, _OUTPUT);
fifo->output += length;
return length;
}
队列剩余空间
/**
* @brief Free space in queue
* @param fifo pointer
* @return number
*/
u32_t FIFO_UNUSED(fifo_t* fifo){
return ((fifo->length + 1) - (fifo->input - fifo->output));
}
队列已使用空间
/**
* @brief Used space in queue
* @param fifo pointer
* @return number
*/
u32_t FIFO_USED(fifo_t* fifo){
return (fifo->input - fifo->output);
}
获取头结点
/**
* @brief get queue head
* @param fifo pointer
* @return head address
*/
void* FIFO_GET_HEAD(fifo_t* fifo){
// fifo->address
u32_t offset = 0;
offset &= fifo->length;
offset *= fifo->element_size;
return (void*)fifo->address + offset;
}
结
本文介绍了一种循环队列的实现方式，使用此种方式的主要原因就是提高性能，而不是简单的理解循环队列，在底层系统中，资源比较紧张，循环队列是一种很好的结构，性能高，资源固定，实现也很简单。
最后很抱歉没有在代码中进行注释，阅读可能比较吃力。
附全部代码
Makefile
CC = gcc
CFLAGS = -I.
DEPS = fifo.h
OBJ = main.o fifo.o
%.o: %.c $(DEPS)
$(CC) -c -o $@ $< $(CFLAGS)
fifo: $(OBJ)
$(CC) -o $@ $^ $(CFLAGS)
.PHONY: clean
clean:
rm -f fifo *.o
fifo.h
/****************************************************************
*@file : fifo.h
*@description:
*@time : 2023/08/21 20:26:50
*@author : Nick Xia
*@blog : https://aeneag.xyz
*****************************************************************/
#ifndef _FIFO_H
#define _FIFO_H
#include <memory.h>
typedef unsigned char u8_t;
typedef unsigned short u16_t;
typedef unsigned int u32_t;
typedef unsigned long long u64_t;
typedef struct _FIFO_{
u32_t input;
u32_t output;
u32_t length;
u32_t element_size;
u64_t address;
}fifo_t;
#define is_power_of_two(x) ((x) != 0 && (((x) & ((x)-1)) == 0))
#define MIN(a, b) (((a) < (b)) ? (a) : (b))
#define fifo_total_size(length, element_size) ((length)*(element_size)+(sizeof(fifo_t)))
#define SUCCESS 0
#define FAILURE 1
#define _INPUT 0
#define _OUTPUT 1
u32_t FIFO_UNUSED(fifo_t* fifo);
u32_t FIFO_USED(fifo_t* fifo);
u32_t FIFO_INIT(fifo_t* fifo, u32_t length, u32_t element_size);
u32_t FIFO_INPUT(fifo_t* fifo, const void* data, u32_t length);
u32_t FIFO_OUTPUT(fifo_t* fifo, void* data, u32_t length);
void* FIFO_GET_HEAD(fifo_t* fifo);
#endif // !_FIFO_H
fifo.c
/****************************************************************
*@file : fifo.c
*@description:
*@time : 2023/08/21 20:27:06
*@author : Nick Xia
*@blog : https://aeneag.xyz
*****************************************************************/
#include "fifo.h"
/**
* @brief init fifo
* @param fifo pointer , fifo len , per variable size in fifo
* @return SUCCESS/FAILURE
*/
u32_t FIFO_INIT(fifo_t* fifo, u32_t length, u32_t element_size){
//intialize variables
fifo->input = 0;
fifo->output = 0;
fifo->element_size = element_size;
//save fifo head address
fifo->address = ((u64_t)fifo) + sizeof(fifo_t);
//This defines that the queue capacity can only be a power of two.
if(!(is_power_of_two(length)) || length < 2){
fifo->length = 0;
return FAILURE;
}
fifo->length = length - 1;
memset((void*)fifo->address, 0, length * element_size);
return SUCCESS;
}
/**
* @brief Free space in queue
* @param fifo pointer
* @return number
*/
u32_t FIFO_UNUSED(fifo_t* fifo){
return ((fifo->length + 1) - (fifo->input - fifo->output));
}
/**
* @brief Used space in queue
* @param fifo pointer
* @return number
*/
u32_t FIFO_USED(fifo_t* fifo){
return (fifo->input - fifo->output);
}
/**
* @brief get data or copy data
* @param fifo pointer , data or buff , numbers , address , flag
* @return
*/
static void FIFO_COPY(fifo_t* fifo, const void* src_or_dst, u32_t length, u32_t offset, u32_t FLAG){
u32_t fifo_length = fifo->length + 1;
u32_t fifo_element_size = fifo->element_size;
offset &= fifo->length;
length *= fifo_element_size;
fifo_length *= fifo_element_size;
offset *= fifo_element_size;
u32_t tmp = MIN(length, fifo_length - offset);
if(FLAG == _INPUT){
memcpy((void *)fifo->address + offset, src_or_dst, tmp);
memcpy((void *)fifo->address, src_or_dst + tmp, length - tmp);
}else if(FLAG == _OUTPUT){
memcpy((void *)src_or_dst, (const void *)fifo->address + offset, tmp);
memcpy( (void *)src_or_dst + tmp, (const void *)fifo->address, length - tmp);
}
}
/**
* @brief input data to fifo
* @param fifo pointer , data , len
* @return len
*/
u32_t FIFO_INPUT(fifo_t* fifo, const void* data, u32_t length){
u32_t balance_fifo_num = FIFO_UNUSED(fifo) ;
if(!balance_fifo_num)
return FAILURE;
if(length > balance_fifo_num)
length = balance_fifo_num;
FIFO_COPY(fifo, data, length, fifo->input, _INPUT);
fifo->input += length;
return length;
}
/**
* @brief output data to buff
* @param fifo pointer , buf , len
* @return
*/
u32_t FIFO_OUTPUT(fifo_t* fifo, void* buf , u32_t length){
u32_t used_fifo_num = FIFO_USED(fifo);
if(!used_fifo_num)
return FAILURE;
if(length > used_fifo_num)
length = used_fifo_num;
FIFO_COPY(fifo, buf, length, fifo->output, _OUTPUT);
fifo->output += length;
return length;
}
/**
* @brief get queue head
* @param fifo pointer
* @return head address
*/
void* FIFO_GET_HEAD(fifo_t* fifo){
// fifo->address
u32_t offset = 0;
offset &= fifo->length;
offset *= fifo->element_size;
return (void*)fifo->address + offset;
}
Main.c
/****************************************************************
*@file : main.c
*@description:
*@time : 2023/08/21 20:27:14
*@author : Nick Xia
*@blog : https://aeneag.xyz
*****************************************************************/
#include "fifo.h"
#include <stdio.h>
//Defines a queue type
typedef struct _fifo_struct_{
u8_t data1;
u8_t data2;
u16_t data3;
u32_t data4;
u64_t data5;
}__attribute__((packed)) data_t;
//Declaring a circular queue
u8_t g_fifo[fifo_total_size(64,sizeof(data_t))];
/**
* @brief main function
* @param
* @return 0
*/
int main(void){
u32_t ret = FIFO_INIT((fifo_t*)g_fifo,64,sizeof(data_t));
data_t data[3];
int j = 1;
for(int i= 0; i < 3; ++i){
data[i].data1 = (u8_t)j;++j;
data[i].data2 = (u8_t)j;++j;
data[i].data3 = (u16_t)++j;
data[i].data4 = (u32_t)j;++j;
data[i].data5 = (u64_t)j;++j;
}
FIFO_INPUT((fifo_t*)g_fifo, (void*)data,3);
FIFO_INPUT((fifo_t*)g_fifo, (void*)data,3);
printf("used %d\n",FIFO_USED((fifo_t*)g_fifo));
printf("unused %d\n",FIFO_UNUSED((fifo_t*)g_fifo));
data_t get_buff;
FIFO_OUTPUT((fifo_t*)g_fifo, (void*)&get_buff,1);
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);
printf("used %d\n",FIFO_USED((fifo_t*)g_fifo));
data_t buff[4] = {0};
FIFO_OUTPUT((fifo_t*)g_fifo, (void*)buff,4);
for(int i = 0 ; i < 4 ; ++i){
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);
}
printf("used %d\n",FIFO_USED((fifo_t*)g_fifo));
printf("unused %d\n", FIFO_UNUSED((fifo_t*)g_fifo));
FIFO_INPUT((fifo_t*)g_fifo, (void*)data,3);
printf("used %d\n",FIFO_USED((fifo_t*)g_fifo));
printf("unused %d\n", FIFO_UNUSED((fifo_t*)g_fifo));
return 0;
}
运行测试
吾心信其可行，
则移山填海之难，
终有成功之日！
——孙文
则移山填海之难，
终有成功之日！
——孙文
评论
0 评论
