您可以使用以下问题来指导您的评论。
API是否经过深思熟虑和习惯用法?
代码是否看起来“现代”(即使用现代约定等)?
代码在内存使用方面是否有效?
测试是否有效?
代码是否没有未定义的行为,内存泄漏等?
我的程序分为3个文件:
queue.h
#pragma once
#include <stddef.h>
typedef enum queue_ret
{
QUEUE_RET_Success,
QUEUE_RET_FailedMemoryAlloc,
QUEUE_RET_QueueIsEmpty,
} queue_ret_t;
typedef struct node
{
void* data;
struct node* next;
} node_t;
typedef struct queue
{
node_t* front;
node_t* back;
size_t size;
} queue_t;
queue_ret_t QUEUE_initialize(queue_t** queue);
size_t QUEUE_size(queue_t* queue);
queue_ret_t QUEUE_enqueue(queue_t* queue, void* data);
queue_ret_t QUEUE_peek(queue_t* queue, void* data, size_t size);
queue_ret_t QUEUE_dequeue(queue_t* queue, void* data, size_t size);
void QUEUE_free(queue_t* queue);
queue.c
-override“> #include <stdlib.h>
#include <string.h>
#include "queue.h"
queue_ret_t QUEUE_initialize(queue_t** queue)
{
*queue = (queue_t*)calloc(1, sizeof(queue_t));
if ((*queue) == NULL)
{
return QUEUE_RET_FailedMemoryAlloc;
}
(*queue)->front = NULL;
(*queue)->back = NULL;
(*queue)->size = 0;
return QUEUE_RET_Success;
}
size_t QUEUE_size(queue_t* queue)
{
return queue->size;
}
queue_ret_t QUEUE_enqueue(queue_t* queue, void* data)
{
node_t* node = (node_t*)calloc(1, sizeof(node_t));
if (node == NULL)
{
return QUEUE_RET_FailedMemoryAlloc;
}
node->data = data;
node->next = NULL;
if (queue->size == 0)
{
queue->front = node;
queue->back = node;
}
else
{
queue->back->next = node;
queue->back = node;
}
(queue->size)++;
return QUEUE_RET_Success;
}
queue_ret_t QUEUE_peek(queue_t* queue, void* data, size_t size)
{
if (queue->size == 0)
{
return QUEUE_RET_QueueIsEmpty;
}
memcpy(data, queue->front->data, size);
return QUEUE_RET_Success;
}
queue_ret_t QUEUE_dequeue(queue_t* queue, void* data, size_t size)
{
queue_ret_t ret = QUEUE_peek(queue, data, size);
if (ret != QUEUE_RET_Success)
{
return ret;
}
if (queue->front == queue->back)
{
free(queue->front);
queue->front = NULL;
queue->back = NULL;
}
else
{
node_t* temp = queue->front;
queue->front = temp->next;
free(temp);
}
(queue->size)--;
return QUEUE_RET_Success;
}
void QUEUE_free(queue_t* queue)
{
node_t* current = queue->front;
while (current != NULL)
{
node_t* next = current->next;
free(current);
current = next;
}
free(queue);
}
queue_test.c
#include "greatest.h"
#include "queue.h"
TEST dequeue_empty_queue_should_return_QueueIsEmpty()
{
queue_t* queue;
queue_ret_t ret;
ret = QUEUE_initialize(&queue);
ASSERT_EQ(QUEUE_RET_Success, ret);
ret = QUEUE_dequeue(queue, NULL, 0);
ASSERT_EQ(QUEUE_RET_QueueIsEmpty, ret);
QUEUE_free(queue);
PASS();
}
TEST peek_empty_queue_should_return_QueueIsEmpty()
{
queue_t* queue;
queue_ret_t ret;
ret = QUEUE_initialize(&queue);
ASSERT_EQ(QUEUE_RET_Success, ret);
ret = QUEUE_peek(queue, NULL, 0);
ASSERT_EQ(QUEUE_RET_QueueIsEmpty, ret);
QUEUE_free(queue);
PASS();
}
TEST size_of_empty_queue_should_be_0()
{
queue_t* queue;
queue_ret_t ret;
size_t actual;
ret = QUEUE_initialize(&queue);
ASSERT_EQ(QUEUE_RET_Success, ret);
actual = QUEUE_size(queue);
ASSERT_EQ(0, actual);
QUEUE_free(queue);
PASS();
}
TEST enqueue_should_make_size_grow()
{
queue_t* queue;
queue_ret_t ret;
int dummy = 0;
size_t actual;
ret = QUEUE_initialize(&queue);
ASSERT_EQ(QUEUE_RET_Success, ret);
ret = QUEUE_enqueue(queue, &dummy);
ASSERT_EQ(QUEUE_RET_Success, ret);
ret = QUEUE_enqueue(queue, &dummy);
ASSERT_EQ(QUEUE_RET_Success, ret);
ret = QUEUE_enqueue(queue, &dummy);
ASSERT_EQ(QUEUE_RET_Success, ret);
actual = QUEUE_size(queue);
ASSERT_EQ(3, actual);
QUEUE_free(queue);
PASS();
}
TEST peek_should_return_next_dequeue_item()
{
queue_t* queue;
queue_ret_t ret;
int expected = 1;
int dummy = 2;
int actual = 0;
ret = QUEUE_initialize(&queue);
ASSERT_EQ(QUEUE_RET_Success, ret);
ret = QUEUE_enqueue(queue, &expected);
ASSERT_EQ(QUEUE_RET_Success, ret);
ret = QUEUE_peek(queue, &actual, sizeof(actual));
ASSERT_EQ(QUEUE_RET_Success, ret);
ASSERT_EQ(expected, actual);
ret = QUEUE_enqueue(queue, &dummy);
ASSERT_EQ(QUEUE_RET_Success, ret);
ret = QUEUE_peek(queue, &actual, sizeof(actual));
ASSERT_EQ(QUEUE_RET_Success, ret);
ASSERT_EQ(expected, actual);
QUEUE_free(queue);
PASS();
}
TEST dequeue_all_items_should_left_queue_empty()
{
queue_t* queue;
queue_ret_t ret;
int dummy = 0;
size_t actual;
ret = QUEUE_initialize(&queue);
ASSERT_EQ(QUEUE_RET_Success, ret);
ret = QUEUE_enqueue(queue, &dummy);
ASSERT_EQ(QUEUE_RET_Success, ret);
ret = QUEUE_enqueue(queue, &dummy);
ASSERT_EQ(QUEUE_RET_Success, ret);
ret = QUEUE_dequeue(queue, &dummy, sizeof(dummy));
ASSERT_EQ(QUEUE_RET_Success, ret);
ret = QUEUE_dequeue(queue, &dummy, sizeof(dummy));
ASSERT_EQ(QUEUE_RET_Success, ret);
actual = QUEUE_size(queue);
ASSERT_EQ(0, actual);
QUEUE_free(queue);
PASS();
}
TEST first_item_in_should_be_first_item_out()
{
queue_t* queue;
int expected_1 = 1;
int expected_2 = 2;
int actual;
queue_ret_t ret;
ret = QUEUE_initialize(&queue);
ASSERT_EQ(QUEUE_RET_Success, ret);
ret = QUEUE_enqueue(queue, &expected_1);
ASSERT_EQ(QUEUE_RET_Success, ret);
ret = QUEUE_enqueue(queue, &expected_2);
ASSERT_EQ(QUEUE_RET_Success, ret);
ret = QUEUE_dequeue(queue, &actual, sizeof(actual));
ASSERT_EQ(QUEUE_RET_Success, ret);
ASSERT_EQ(expected_1, actual);
ret = QUEUE_dequeue(queue, &actual, sizeof(actual));
ASSERT_EQ(QUEUE_RET_Success, ret);
ASSERT_EQ(expected_2, actual);
QUEUE_free(queue);
PASS();
}
GREATEST_MAIN_DEFS();
int main(int argc, char **argv) {
GREATEST_MAIN_BEGIN();
RUN_TEST(dequeue_empty_queue_should_return_QueueIsEmpty);
RUN_TEST(peek_empty_queue_should_return_QueueIsEmpty);
RUN_TEST(size_of_empty_queue_should_be_0);
RUN_TEST(enqueue_should_make_size_grow);
RUN_TEST(peek_should_return_next_dequeue_item);
RUN_TEST(dequeue_all_items_should_left_queue_empty);
RUN_TEST(first_item_in_should_be_first_item_out);
GREATEST_MAIN_END();
}
如何运行
将上面显示的所有文件放在同一文件夹中。然后,您需要将测试库复制到此文件夹,该文件夹只是一个名为great.h的头文件。
因此,假设您的文件夹如下所示:
> ls
> greatest.h queue.c queue.h queue_test.c
您使用以下命令运行测试:
gcc queue.c queue_test.c -o queue_test && queue_test
#1 楼
您的QUEUE_*
函数均未在使用前验证其输入参数。 NULL
指针将是一个问题,尤其是对于指向指针的参数。C的内存分配函数返回void*
,该函数隐式转换为任何其他指针类型。这意味着您无需强制转换calloc
的结果。这样做实际上可以掩盖编译器否则可能捕获的某些错误。您的
node_t
结构缺少一条至关重要的信息:目标对象的大小。如果您的队列仅处理指针,这将是可以的。但是,您可以在几个地方访问该指针后面的实际数据。在不知道数据大小的情况下,您面临大量的缓冲区溢出问题。例如,如果我将一个字符排队,然后调用大小为1 MB的QUEUE_peek()
,则会发生不良情况。信任呼叫者来跟踪此问题是有问题的。首先,您不应该信任用户做正确的事。更重要的是,需要第二个队列来跟踪第一个队列中的对象大小会使您的实现难以使用。您有两种解决方案。如果队列仅包含相同类型的对象,则将void* data
替换为指向特定类型的指针(聪明的宏甚至可以像C ++模板一样使该类型的用户可配置)。另一种选择是将size_t size
成员添加到struct node
。如果使用后者,则需要重新设计peek
/ dequeue
在内部分配输出缓冲区,或者添加一个函数,该函数返回队列顶部的对象大小。您的代码很容易受到我有时称为“管闲用户”的攻击。也就是说,一个在您的实现内部进行四处查看的用户。如果用户决定更改队列的
size
成员的值(通过恶意或无能),则您的代码将在许多地方中断。我建议向用户隐藏实施细节。最简单的方法是将struct queue
和struct node
的定义移到.c文件中。然后,将struct queue;
行添加到标题的顶部(向前声明)。这样一来,用户就可以创建指向队列对象的指针(这是使用API所需的全部内容),但不允许它们在内部使用。这类似于stdio.h
实现FILE
类型的方式。旁注:关于Clean API的出色工作,只需要用户知道单个指针类型。多数首遍泄漏的实现细节要多得多。通过扩展上面提到的棘手怪胎,您的API是不对称的。您使指向对象的指针入队,但使该对象内容的副本出队。当您对已动态分配的对象进行排队时,这可能会导致问题。一旦使该对象出队并想要释放它,就没有真正的办法找出原始指针,以便可以将其传递给
free()
。如果出队函数返回了指针,则调用者将拥有他们需要的所有信息。仅使入队/出队处理指针将同样避免另一个问题。当前的出队实现会对排队对象进行完整复制,这可能会导致严重的性能损失。在队列中使用大对象将导致大量内存流失,并且不必要地浪费了很多时间来复制位。用户始终可以将指向这些对象的指针而不是对象本身排队,但这是解决方案,而不是解决方案。
可移植性问题:
POSIX标准保留以
_t
结尾的类型名称。为了可移植性,最好避免在自定义类型上使用该后缀。当您具有基本的通用名称(例如queue_t
和node_t
)时,名称冲突的风险特别高。#pragma once
不是标准C。这是一个相对常见的扩展名,但是如果您要确保代码可以使用任何编译器/平台,请改用基于#define
的传统include防护。次要问题:
通常,我通常建议避免使用typedef-ing结构类型。它掩盖了您正在处理的实际上是结构的事实。另外,您现在具有相同类型的两个名称(
struct node
和node_t
),这可能引起混乱并使得重构更加困难。甚至在某些上下文中(例如前向声明),您都可以使用struct
的名称,但是使用typedef
-ed的名称将不起作用。我可以看到
queue->size
的名称可能会引起混淆。 “大小”通常是指某种东西需要占用多少存储空间。像“计数”或“长度”之类的名称可以使该字段的测量值更加明显。评论
\ $ \ begingroup \ $
您如何看待删除枚举queue_ret?我最初的意图是提供一种类似于异常的机制,但是...现在看代码,对我而言似乎增加了不必要的复杂性。我可以使QUEUE_initialize,QUEUE_peek和QUEUE_dequeue返回实际的指针(失败时返回NULL),而QUEUE_enqueue返回布尔值。它也大大简化了测试。
\ $ \ endgroup \ $
–加百列
19年5月16日在14:03
\ $ \ begingroup \ $
@Gabriel我认为最好删除该枚举,因为如果其中一个函数失败,则可以返回空指针。
\ $ \ endgroup \ $
–hsdfhsdal
19年5月16日在14:41
\ $ \ begingroup \ $
@Gabriel如果函数可能由于多种原因而失败,并且调用者需要知道确切的失败原因才能恢复,则您实际上仅需要自定义错误代码。我认为您目前的API并非如此。
\ $ \ endgroup \ $
– bta
19年5月16日在16:39
\ $ \ begingroup \ $
@Gabriel即使有多个失败原因,您仍然可以使用errno或类似的东西。
\ $ \ endgroup \ $
–hsdfhsdal
19年5月16日在16:49
\ $ \ begingroup \ $
我接受这个答案,因为我认为它提供了最有见地的反馈,但是所有其他答案都受到赞赏,我希望其他成员如果愿意的话,不要在将来提交新评论。
\ $ \ endgroup \ $
–加百列
19年5月20日在11:53
#2 楼
这看起来真的很好!我们去了:该API是否经过深思熟虑和惯用?
大多。对于这样简单的库,您可能希望避免在返回错误时返回
NULL
时创建一个特殊的枚举。为此,您可以使
QUEUE_initialize()
函数返回一个指向queue_t
而不是传递queue_t**
作为参数。如果分配失败,它可以简单地返回NULL
(您甚至可以考虑让最终用户分配该结构,并使该函数仅对其进行初始化)。例如:queue_t *QUEUE_initialize()
{
queue_t *queue = (queue_t*)calloc(1, sizeof(queue_t));
if (queue == NULL) return NULL;
queue->front = NULL;
queue->back = NULL;
queue->size = 0;
return queue;
}
或者,在分配内存的方式上提供“机制而非策略”:
void QUEUE_initialize(queue_t *queue)
{
queue->front = NULL;
queue->back = NULL;
queue->size = 0;
}
如您所见,除了为用户提供更大的灵活性之外,这还大大简化了实现。
如果
QUEUE_peek()
返回成功的指针参数,而NULL
返回失败的指针,则您可以摆脱枚举并减少代码行:void *QUEUE_peek(queue_t* queue, void* data, size_t size)
{
if (queue->size == 0) return NULL;
memcpy(data, queue->front->data, size);
return data;
}
通常,您希望代码行尽可能少,因为每一行都是
代码看起来是否“现代”(即使用现代约定等)?
是的,除了非
#pragma once
中的标准queue.h
。就我个人而言,我会使用小写的函数名(queue_size()
而不是QUEUE_size()
等),但这只是个人喜好。代码在内存使用方面是否有效?
测试是否经过深思熟虑?
是
代码是否没有未定义的行为,内存泄漏等?
通过让用户指定大小与数据分开,某些功能(
QUEUE_peek()
,QUEUE_dequeue
)有可能使用户犯错。您可能应该将用户的指针视为不透明数据,或者将size_t
添加到node_t
结构中。同时,我认为您的库不应该负责检查例如初始化函数。如果用户尝试对一个结构进行malloc()
运算,但没有检查它是否成功,则他们可能已经将指针传递给了程序的其他部分,从而使该检查变得多余。但是,正如@bta所提到的那样,您的实现容易受到爱管闲事的用户的欢迎,因此不应将_t
后缀用于结构。用作QUEUE_size()
或将其定义为宏。尽管有些人可能会认为inline
是多余的,应该将其删除,但库用户不必知道该结构的内部。如果您想忠于C,那么我将尽可能地删除typedef,仅将结构引用为QUEUE_size()
。我还将避免向该结构添加任何函数指针,因为这会导致不必要的复杂性(阅读:膨胀)。如果API需要面向对象,则只需使用C ++。要具有与内存分配无关的
struct foo
函数,您可能需要使用回调函数。此外,您的库不需要知道用户将指针用于什么类型的事情(如果他们只是想发布消息ID而不是实际的指针),用户也不需要知道队列的方式。已实施。为避免污染用户的名称空间,您可能希望将某些标头定义放置在c文件中,以防止其在该翻译单元之外可见。总体而言,经过改进的库可能看起来像这样(省略了标题防护,因为它们被某些人认为是不好的样式):
#include <stdbool.h>
struct queue;
/* Required behavior: node_alloc returns NULL on failure */
typedef void *(*node_alloc_fn)(size_t size);
typedef void (*node_free_fn)(void *node);
void queue_initialize(struct queue *queue);
inline size_t queue_size(struct queue *queue);
bool queue_enqueue(struct queue *queue, void *data, node_alloc_fn node_alloc);
void *queue_peek(struct queue *queue);
void *queue_dequeue(struct queue *queue, node_free_fn node_free);
void queue_free_nodes(struct queue *queue, node_free_fn node_free);
queue.c
#include "queue.h"
struct node
{
void *data;
struct node *next;
};
struct queue
{
struct node *front;
struct node *back;
size_t numitems;
};
void queue_initialize(struct queue *queue)
{
queue->front = NULL;
queue->back = NULL;
queue->numitems = 0;
}
inline size_t queue_size(struct queue *queue)
{
return queue->numitems;
}
bool queue_enqueue(struct queue *queue, void *data, node_alloc_fn node_alloc)
{
/* Not including a default value for node_alloc since malloc() might not exist */
struct node *node = (struct node*)node_alloc(sizeof(struct node));
if (!node) return false;
node->data = data;
node->next = NULL;
if (queue->size == 0)
{
queue->front = node;
queue->back = node;
}
else
{
queue->back->next = node;
queue->back = node;
}
(queue->numitems)++;
return true;
}
/* Just get the first value in the queue, the user chooses if it gets copied */
void *queue_peek(struct queue *queue)
{
if (queue->numitems == 0) return NULL;
return queue->front->data;
}
/* Instead of a data parameter, just return the value */
void *queue_dequeue(struct queue *queue, node_free_fn node_free)
{
/* Not including a default value for node_free since free() might not exist */
if (!queue_peek(queue)) return NULL;
/* All this function needs to do is unlink the first member.
Leave it up to the user to decide if it needs to be freed */
struct node *front = queue->front;
if (front == queue->back)
{
queue->front = NULL;
queue->back = NULL;
}
else
{
queue->front = front->next;
}
(queue->numitems)--;
return front;
}
void queue_free_nodes(struct queue *queue, node_free_fn node_free)
{
/* Not including a default value for node_free since free() might not exist */
struct node *current = queue->front;
while (current)
{
struct node *next = current->next;
node_free(current);
current = next;
}
}
```
评论
\ $ \ begingroup \ $
+1,用于将已分配的队列传递给init函数。这样,调用方就可以将自动或静态存储用于队列的控制块,而不必强制使用动态存储。
\ $ \ endgroup \ $
– Peter Cordes
19年5月16日在10:27
\ $ \ begingroup \ $
如果我从QUEUE_initialize中删除队列分配,我仍然必须提供QUEUE_free函数才能释放节点。不会释放队列的QUEUE_free函数看起来有点尴尬吗?您的观点确实有道理,我喜欢它,我只是想找出一个无误导,自我解释的API。
\ $ \ endgroup \ $
–加百列
19年5月16日在12:17
\ $ \ begingroup \ $
@Gabriel您可以只要求用户手动调用free()。如果用户最初通过malloc()构造了该结构,则释放它就变得很容易了。它还允许您将库用于可能没有堆的嵌入式系统。
\ $ \ endgroup \ $
–hsdfhsdal
19年5月16日在14:37
\ $ \ begingroup \ $
@hsdfhsdal是的,用户将负责释放队列,但是我仍然需要提供QUEUE_free函数来释放我在QUEUE_enqueue中分配的节点。因此,用户将需要在每次调用free(queue)之前放置一个QUEUE_free(queue),否则节点将泄漏,对吗?
\ $ \ endgroup \ $
–加百列
19年5月16日在14:44
\ $ \ begingroup \ $
@Gabriel根据用户存储在队列中的内容,您可能只希望具有回调函数。
\ $ \ endgroup \ $
–hsdfhsdal
19年5月16日在14:46
#3 楼
将指针排入队列后,您将永远无法再获得该指针。很难知道该指针何时已出队。这是泄漏的秘诀。最好返回指针本身而不是包含的数据。或批发存储整个对象。
评论
\ $ \ begingroup \ $
对不起,我不明白你的意思。。你能进一步解释一下吗?
\ $ \ endgroup \ $
–加百列
19年5月15日在16:53
\ $ \ begingroup \ $
@Gabriel:在您的API中,enqueue()通过引用存储数据,迫使调用者在从队列中删除之前不要释放包含它的内存。但是peek()和dequeue()返回数据的副本,而不是指向它的指针,这不仅感觉不一致,而且阻止了调用者从队列中获取原始指针,以便可以释放它。让enqueue()分配自己的内存并复制数据并让dequeue()释放它,或者只是让peek()和dequeue()都返回原始指针,然后让调用者管理数据内存。
\ $ \ endgroup \ $
–伊尔马里(Ilmari Karonen)
19年5月16日在4:53
#4 楼
总体上做得很好!代码是否看起来“现代”(即使用现代约定等)?
我经常看到的一件事建议在代码审查中根据对象所指向的大小而不是对象类型本身分配内存:
*queue = calloc(1, sizeof(*queue));
和
node_t* node = calloc(1, sizeof(*node));
通过删除必要的更改来简化可维护性,在这种情况下只需更改
queue
或node
的类型。代码在技术上是正确的,我个人将在这些情况下使用
malloc()
,并且仅在创建数组时使用calloc()
。如果目标是将内存分配为零,则可以使用memset()
。性能不会有任何变化,calloc()
比malloc()
需要更长的时间,因为它确实清除了内存。尚不清楚calloc()
是否需要node
,因为执行了所有必要的分配。代码在内存使用方面是否有效? >是的。
测试是否经过深思熟虑?
据我所知,所有内容均已涵盖。测试库似乎没有提供有关代码覆盖率的任何信息,这也将很有趣并且很有帮助。
评论
\ $ \ begingroup \ $
sizeof(* data)与指向数据的实际大小无关。除非使用GCC扩展名,否则它是sizeof(void),这是编译错误。
\ $ \ endgroup \ $
–vnp
19年5月15日在16:49
\ $ \ begingroup \ $
@vnp谢谢,我已经删除了该部分。
\ $ \ endgroup \ $
–pacmaninbw
19年5月15日在16:53
\ $ \ begingroup \ $
我可以将函数指针放在queue_t中,但是我不知道如何实现不需要队列作为参数的queue-> size()(即queue-> size(queue))。函数指针不提供this(例如在Java中),并且C没有闭包afaik。
\ $ \ endgroup \ $
–加百列
19年5月15日在17:52
\ $ \ begingroup \ $
将函数指针放到结构中也会增加队列对象本身的大小。如果API具有N个功能,则队列的每个实例将增加N * sizeof(void *)个字节。
\ $ \ endgroup \ $
–Paul Belanger
19年5月15日在20:15
\ $ \ begingroup \ $
不好意思,因为面向对象是C的API真正不好的主意。C不是面向对象的语言。不要试图做到这一点。
\ $ \ endgroup \ $
–奥斯卡·史密斯(Oscar Smith)
19年5月16日,3:10
评论
所发布的代码缺少great.h的头文件内容。请编辑问题以包括缺少的头文件@ user3629249我包括了指向它的链接,它是:raw.githubusercontent.com/silentbicycle/greatest/master / ...
@ user3629249您似乎没有复制great.h的内容。我要做的就是用上一个链接中的内容创建一个great.h文件,所以我想这也是您要做的所有事情。
复制链接文件后:great.h干净地编译。不要引用外部文件的链接。发布的代码应独立存在
这看起来像一个试图摆脱的链表!我将提取出链表代码(然后可以直接使用它,或者将其用作堆栈或其他数据结构的一部分),然后将其包装以创建队列,并仅公开那些对队列合法的操作。 >