基本队列设计与实现
通常，我希望使用动态分配对这个基本队列进行一些评论。特别是，我想要评论这个队列在嵌入式系统中是否很好，例如，一个传感器网络网关，它必须对要在例如UART上转发的数据包排队。
我通常听说，对嵌入式系统来说，恶意代码是个坏主意，那么在这种情况下，有哪些缺陷呢？
有一件事是，malloc可能返回它无法分配所需的内存。但我想的是，如果我做了计算，并且相当肯定我肯定有MAX_QSIZE的内存量可供MAX_DATSIZE使用，那么实际上，我不应该看到malloc失败。这是正确的假设吗？
我正在为带有静态数组的版本重写相同的代码，并且也没有错误，所以我将尝试分析两者的行为。
谢谢您抽时间见我。
#include <stdio.h>
#include <stdint.h>
#include <string.h>
#include <stdlib.h>
#define MAX_QSIZE 100
#define MAX_DATSIZE 128
struct node{
void *data;
struct node *next;
};
typedef struct node node_t;
typedef struct queue_t {
node_t *head;
node_t *tail;
int size;
} queue_t;
queue_t *q_init(void)
{
queue_t *q = malloc(sizeof (*q));
q->size = 0;
q->head = q->tail = NULL;
}
int q_push(queue_t *q, const void *pdata, int bsize)
{
if (q == NULL)
return -1;
if (q->size == MAX_QSIZE)
return -2;
if (bsize > MAX_DATSIZE)
return -3;
node_t *new = malloc(sizeof (*new));
new->next = NULL;
new->data = malloc(bsize);
bzero(new->data, bsize);
memcpy(new->data, pdata, bsize);
if (q->size == 0) {
q->head = new;
} else {
q->tail->next = new;
}
q->tail = new;
q->size++;
return 0;
}
node_t *q_peek(queue_t *q)
{
return q->head;
}
void q_pop(queue_t *q)
{
if (q->size == 0)
return;
node_t *this = q->head;
q->head = this->next;
free(this);
q->size--;
if (q->size == 0)
q->tail = NULL;
}
void freeq(queue_t *q)
{
while (q->head != NULL) {
node_t *t = q->head;
q->head = t->next;
free(t);
}
free(q);
}
void printq(queue_t *q)
{
int i = 0;
for (node_t *h = q->head; h != NULL; h = h->next) {
printf("[%d] %s\n", i++, (char*)h->data);
}
}
int main()
{
char *test[] =
{
"January",
"February",
"Random"
};
int numtest = sizeof test / sizeof test[0];
queue_t *nameq = q_init();
for (int i = 0; i < numtest; i++) {
q_push(nameq, test[i], strlen(test[i]));
}
printq(nameq);
q_pop(nameq);
printq(nameq);
char *hname = (char*)(q_peek(nameq)->data);
printf("head name = %s\n", hname);
freeq(nameq);
return 0;
}回答 1
Code Review用户
发布于 2021-01-17 00:24:10
BUG：q_init()不返回值。您的编译器应该捕捉到这一点；也许您正在运行时没有打开足够的诊断信息？(我认为这需要一个诊断，所以您可能需要一个更好的编译器)。
错误:我们忘记复制终止空字符！
(int i= 0；i< numtest；i++) { q_push(nameq，test我，strlen(test我))；}
那应该是strlen(test[i])+1。这件事很快就被瓦伦发现了。
虽然您从来没有想过malloc()会失败，但我认为最好养成防御性编码的习惯。例如，“可用内存”可能是支离破碎的，而不是以足够大的块可用。添加必要的测试并不难，而且它使您的代码更易于重用，从而节省了更长时间的时间。
queue_t *q_init(void)
{
queue_t *q = malloc(sizeof *q);
if (q) {
q->size = 0;
q->head = q->tail = NULL;
}
return q;
}bzero()不是标准的(即便携的) C.使用memset()代替。实际上，只需完全删除该调用，因为它紧接着是一个完全覆盖它的memcpy()，使bzero()成为一个死存储。
我们不需要在这里投：
printf("[%d] %s\n", i++, (char\*)h->data); char *hname = (char*)(q_peek(nameq)->data)；
data是一个指向void的指针，它可以分配给C中的任何指针类型：
printf("[%d] %s\n", i++, h->data);const char *hname = q_peek(nameq)->data;我们已经包括了<stdint.h>，但似乎忽略了它。我通常会使用size_t来表示队列长度和元素大小。我当然不会使用有符号的类型，比如int。
命名:为什么freeq()而不是q_free()来匹配其他函数？
当推送一个值时，我们分配两次，但是q_pop()和freeq()不释放值存储，只释放队列节点。所以我们有个内存泄漏：
==4943==
==4943== 21 bytes in 3 blocks are definitely lost in loss record 1 of 1
==4943== at 0x480B77F: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==4943== by 0x10922B: q_push (254594.c:40)
==4943== by 0x10942E: main (254594.c:100)我们可以通过在释放节点对象的free()之前添加另一个来解决这个问题。但是，更优雅的解决方法是只为节点和存储的值一起分配一次：
node_t *new = malloc(sizeof *new + bsize);
if (!new) {
return ENOMEM;
}
new->next = NULL;
new->data = (char*)(new + 1);
memcpy(new->data, pdata, bsize);我们不再需要data成员了--该值总是与节点指针的偏移量相同。
界面可以改进--用户不需要了解node_t。相反，只返回指向数据成员的指针。
修改代码
#include <stdio.h>
#include <stdint.h>
#include <string.h>
#include <stdlib.h>
#define MAX_QSIZE 100
#define MAX_DATSIZE 128
typedef struct node {
struct node *next;
char data[]; /* flexible array member */
} node_t;
typedef struct queue_t {
node_t *head;
node_t *tail;
size_t size; /* element count */
} queue_t;
queue_t *q_init(void)
{
queue_t *q = malloc(sizeof *q);
if (q) {
q->size = 0;
q->head = q->tail = NULL;
}
return q;
}
void *q_push(queue_t *q, const void *pdata, size_t bsize)
{
if (!q || q->size == MAX_QSIZE || bsize > MAX_DATSIZE) {
return NULL;
}
node_t *new = malloc(sizeof *new + bsize);
if (!new) {
return NULL;
}
new->next = NULL;
memcpy(&new->data, pdata, bsize);
if (q->head) {
q->tail->next = new;
} else {
q->head = new;
}
q->tail = new;
q->size++;
return &new->data;
}
const void *q_peek(queue_t *q)
{
if (!q || !q->head) { return NULL; }
return &q->head->data;
}
void q_pop(queue_t *q)
{
if (!q || !q->size) { return; }
node_t *this = q->head;
q->head = this->next;
free(this);
if (!--q->size) {
q->tail = NULL;
}
}
void q_free(queue_t *q)
{
if (!q) { return; }
node_t *h = q->head;
while (h) {
node_t *t = h;
h = t->next;
free(t);
}
free(q);
}
static void printq(queue_t *q)
{
int i = 0;
for (const node_t *h = q->head; h; h = h->next) {
printf("[%d] %s\n", i++, &h->data[0]);
}
}
int main(void)
{
const char *test[] =
{
"January",
"February",
"Random"
};
int numtest = sizeof test / sizeof test[0];
queue_t *nameq = q_init();
if (!nameq) {
fprintf(stderr, "Failed to create queue\n");
return EXIT_FAILURE;
}
for (int i = 0; i < numtest; i++) {
if (!q_push(nameq, test[i], strlen(test[i]) + 1)) {
fprintf(stderr, "Failed to create element %i\n", i);
return EXIT_FAILURE;
}
}
printq(nameq);
q_pop(nameq);
printq(nameq);
const char *hname = q_peek(nameq);
printf("head name = %s\n", hname);
q_free(nameq);
}此版本在由gcc -std=c17 -Wall -Wextra -Wwrite-strings -Wno-parentheses -Wpedantic -Warray-bounds -Wstrict-prototypes -Wconversion编译时没有错误，也没有由瓦伦报告的问题。
https://codereview.stackexchange.com/questions/254594
复制相似问题
腾讯云开发者
