一个用于C的动态FIFO队列库
这是dqueue的第一个草稿，它是一个用C编写的动态队列库，并有一个示例程序来演示它。
这是我第一次编写任何类型的库来作为其他项目的一个通用部分，所以我猜测我应该考虑哪些额外的问题。我所做的唯一主要的事情就是使队列能够接受任何类型的数据，并让队列函数设置一个与队列状态相对应的值，这样即使出了问题，也应该非常清楚它是什么，并且很容易修复。
队列结构queue_t可以保存您希望它的任何数据类型。数据通过queue_push()函数添加到队列中，并使用queue_pop()函数从队列中检索数据。当队列通过调用queue_push()填充时，库尝试为队列分配一个新的内存块，而当一个块由于连续调用queue_pop()而为空时，队列将释放该块。当队列完成时，仍然分配给它的所有内存都可以通过调用queue_destroy()来释放。将来，该函数还可以选择对与队列相关的所有数据进行零化。
我试图在性能和内存使用之间取得一点平衡，方法是让程序分配包含多个数据点的块，而不是根据需要分配单个数据点。这是个很好的解决办法吗？我应该使用固定大小的块，还是让用户定义它是个好主意？如果一个固定的尺寸会更好，我应该如何确定它应该是什么？
这个程序已经用大量的设置进行了测试，我还没有找到任何方法来设置产生非最终用户错误的错误的队列(即告诉库使用错误的数据大小来分配数据，或者要求分配负数块)。
这个代码符合标准吗？它完成了我想要做的事情，但我想知道这是否可以更快地完成，还是以更有效的内存方式完成？这段代码为什么很难被其他人使用，有什么原因吗？它的目的是作为一个图书馆，所以这是相当重要的。
dQuee.h
#ifndef DQUEUE_H
#define DQUEUE_H
#include <stdlib.h>
#define QUEUE_OK 0
#define MEM_ERROR -1 /* Memory allocation error */
#define SIZE_ERROR -2 /* Queue dimension error */
#define INDEX_ERROR -3 /* No data at index */
#define DEFAULT_BLOCK 256 /* By default use 256 bytes per block */
typedef struct {
char ** base_p; /* Base pointer of the queue */
unsigned int cur_block; /* Index of the block containing the first element */
unsigned int cur_block_pos; /* Position of the first element within the block */
unsigned int last_block; /* Index of the block containing the last element */
unsigned int last_block_pos; /* Position of the last element within the block */
unsigned int total_blocks; /* Total number of blocks ever allocated to the queue */
size_t block_size; /* Number of elements in each block */
size_t element_width; /* Size of each element */
int status; /* Status of the queue */
} queue_t;
queue_t * queue_init(unsigned int block_num, size_t block_size, size_t element_size); /* Initialise the queue data structure and return a pointer to the first element */
void * queue_pop(queue_t * queue); /* Pop an element from the front of the queue */
int queue_push(const void * const element, queue_t * queue); /* Push an element to the back of the queue */
int queue_debug(const queue_t * const queue); /* Dump information about the queue */
void queue_destroy(queue_t * queue); /* Destroy the queue data structure */
#endifdQuee.c
/*
* Filename: dqueue.c
* Date: 13/10/17
* Licence: GNU GPL V3
*
* Library for a generic, dynamically allocated queue
*
* Functions:
* queue_t * queue_init(unsigned int block_num, size_t block_size, size_t element_size); - Initialise the queue data structure and return a pointer to the first element
* void * queue_pop(queue_t * queue); - Pop an element from the front of the queue
* int queue_push(const void * const element, queue_t * queue); - Push an element to the back of the queue
* int queue_debug(const queue_t * const queue); - Dump information about the queue
* void queue_destroy(queue_t * queue); - Destroy the queue data structure
*
* Return/exit codes:
* QUEUE_OK - No error
* SIZE_ERROR - Queue size error (invalid block size or number of elements)
* MEM_ERROR - Memory allocation error
* INDEX_ERROR - Couldn't pop data from the queue
*
* Todo:
*
*/
#include "dqueue.h"
#include <stdio.h>
#include <string.h>
queue_t * queue_init(unsigned int block_num, size_t block_size, size_t element_width)
{
queue_t * queue;
unsigned int i, j;
if(block_size == 0)
block_size = DEFAULT_BLOCK;
if(!(queue = malloc(sizeof(queue_t))))
return NULL;
if((queue->block_size = block_size) <= 0 || (queue->total_blocks = block_num) <= 0 || (queue->element_width = element_width) <= 0) {
queue->status = SIZE_ERROR;
return queue;
}
if(!(queue->base_p = malloc(queue->total_blocks * sizeof(char *)))) {
queue->status = MEM_ERROR;
return queue;
}
for(i = 0; i < queue->total_blocks; i++) {
if(!(queue->base_p[i] = malloc(queue->block_size * queue->element_width))) {
fprintf(stderr, "Error: Could not allocate memory!\n");
for(j = 0; j < i; j++)
free(queue->base_p[i]);
free(queue->base_p);
}
}
queue->cur_block = queue->last_block = 0;
queue->cur_block_pos = queue->last_block_pos = 0;
queue->status = QUEUE_OK;
return queue;
}
void queue_destroy(queue_t * queue)
{
while(queue->cur_block < queue->total_blocks)
free(queue->base_p[queue->cur_block++]);
queue->cur_block = 0;
queue->cur_block_pos = 0;
queue->last_block = 0;
queue->last_block_pos = 0;
queue->total_blocks = 0;
queue->block_size = 0;
queue->element_width = 0;
queue->status = 0;
free(queue->base_p);
queue->base_p = NULL;
free(queue);
}
int queue_push(const void * const element, queue_t * queue)
{
memcpy(queue->base_p[queue->last_block] + queue->last_block_pos * queue->element_width, element, queue->element_width);
if(queue->last_block == (queue->total_blocks - queue->cur_block) - 1 && queue->last_block_pos == queue->block_size - 1) {
queue->total_blocks++;
queue->last_block++;
queue->last_block_pos = 0;
if(!(queue->base_p = realloc(queue->base_p, (queue->total_blocks - queue->cur_block) * sizeof(void *)))) {
fprintf(stderr, "Error: Could not reallocate memory!\n");
queue->status = MEM_ERROR;
queue->total_blocks--;
queue->last_block--;
queue->last_block_pos = queue->block_size - 1;
return MEM_ERROR;
}
if(!(queue->base_p[queue->last_block] = malloc(queue->block_size * queue->element_width))) {
fprintf(stderr, "Error: Could not allocate memory!\n");
queue->total_blocks--;
queue->last_block--;
queue->last_block_pos = queue->block_size - 1;
queue->status = MEM_ERROR;
return MEM_ERROR;
}
} else if(queue->last_block_pos == queue->block_size - 1) {
queue->last_block++;
queue->last_block_pos = 0;
} else {
queue->last_block_pos++;
}
return QUEUE_OK;
}
void * queue_pop(queue_t * queue)
{
void * data;
if(queue->last_block == queue->cur_block && queue->cur_block_pos == queue->last_block_pos) {
fprintf(stderr, "Error: Queue empty!\n");
queue->status = INDEX_ERROR;
return NULL;
}
if(!(data = malloc(queue->element_width))) {
fprintf(stderr, "Error: Could not allocate memory!\n");
queue->status = MEM_ERROR;
return NULL;
}
if(queue->cur_block_pos == queue->block_size - 1) {
memcpy(data, queue->base_p[queue->cur_block] + queue->cur_block_pos * queue->element_width, queue->element_width);
free(queue->base_p[queue->cur_block]);
queue->cur_block++;
queue->cur_block_pos = 0;
} else {
memcpy(data, queue->base_p[queue->cur_block] + queue->cur_block_pos * queue->element_width, queue->element_width);
queue->cur_block_pos++;
}
return data;
}
int queue_debug(const queue_t * const queue)
{
if(queue == NULL) {
printf("Error: Invalid queue pointer!\n");
return MEM_ERROR;
}
if(queue->status == QUEUE_OK)
printf("Queue has %d blocks of size %d and each element is %d bytes wide!\n", (queue->total_blocks - queue->cur_block), (int)queue->block_size, (int)queue->element_width);
else if(queue->status == MEM_ERROR)
printf("Memory error in queue!\n");
else if(queue->status == SIZE_ERROR)
printf("Size error in queue");
return queue->status;
}main.c
#include "dqueue.h"
#include <stdio.h>
#include <stdlib.h>
#define EXEC_SUCCESS 0
int main()
{
queue_t * queue = NULL;
unsigned int blocks = 8192;
int block_size = 1024;
int new_element = 0;
int * returned_element;
int i;
if(!(queue = queue_init(blocks, block_size, sizeof(int)))) {
fprintf(stderr, "Error %d: Could not initialise queue!\n", MEM_ERROR);
return MEM_ERROR;
}
if(queue->status != QUEUE_OK) {
fprintf(stderr, "General queue error: %d\n", queue->status);
return queue->status;
}
for(i = 33554432; i > 0; i--, new_element++)
queue_push(&new_element, queue);
for(i = 33554432; i > 0; i--) {
if((returned_element = queue_pop(queue)) == NULL) {
fprintf(stderr, "Error %d: Could not pop queue!\n", queue->status);
break;
}
free(returned_element);
}
queue_destroy(queue);
return EXEC_SUCCESS;
}回答 1
Code Review用户
发布于 2017-12-23 23:16:33
..。通过程序分配包含多个数据点的块来平衡性能和内存的使用，而不是根据需要分配单个数据点。这是个好办法吗.？
不--将多个块分组，而不是所有块，与3) 1块进行分组的想法，是试图超越系统的malloc()。重点设计高级代码，并让分配器处理内存管理。这违背了代码的总体设计目标，因此，下面的代码将试图与目标共存。
我看到最大的浪费是，如果代码使用了许多最初为空的queue_t，这将导致OP block_num <= 0失败，从而不得不创建许多非零内存大小的队列。换句话说，让队列根据需要从0开始增长。
我应该使用固定大小的块，还是让用户定义它是个好主意？
简单地放下块的大小-它-让它是1。
如果一个固定的尺寸会更好，我应该如何确定它应该是什么？
请参见上面的。
这个代码符合标准吗..。可以更快地完成，还是以更有效的内存方式完成？
当然，代码可以更高效的内存，但很少是自己的目标。这是一个平衡。那么，它在平衡范围内有效吗？
最大的反对意见是，如果队列活动大小接近block边界，则可能会出现分配/释放队列的“闲聊”。迟滞可以避免这种情况。只有在25%的最新峰值时才会收缩。在收缩时，将峰值设置为200%当前大小。
这段代码为什么很难使用.有什么原因吗？
这种设置比我一般想要使用的限制要多。唯一需要的参数是对象的大小。对于固定长度的队列，我将对所有队列元素和控件成员使用单个分配。
// queue_init(unsigned int block_num, size_t block_size, size_t element_width)
queue_init(size_t element_width)其他说明：
不错的dqueue.h设置。但我会避免#define MEM_ERROR, SIZE_ERROR, ....的名字太类似于碰撞。也许QUEUE_MEM_ERROR ..。
为什么调用queue_t类型，前缀函数queue_...，然后调用文件dqueue.h. dqueue.c？我希望能保持一致--使用queue.h. queue.c或更改代码。
我希望有一个函数返回当前的队列使用情况。(队列中的注册)
代码看起来对queue_destroy(queue); queue_destroy(queue);是宽容的。这是一个很好的设计，很好地反映了queue_destroy()的设计。
我不太喜欢在函数中嵌入fprintf(stderr, ...，但是应该实现一些错误处理计划，至少这段代码有一个。
https://codereview.stackexchange.com/questions/183518
复制相似问题
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号