3

也许没有办法以我喜欢的方式解决这个问题，但我不知道一切，所以我最好问问......

我已经实现了一个带有动态数组的简单队列，因此用户可以使用它想要的任意数量的项目进行初始化。我也在尝试使用void指针来允许任何数据类型，但这就是问题所在。

这是我的代码：

typedef void * QueueValue;

typedef struct sQueueItem {
    QueueValue value;
} QueueItem;

typedef struct sQueue {
    QueueItem *items;

    int first;
    int last;
    int size;
    int count;
} Queue;

void queueInitialize(Queue **queue, size_t size) {
    *queue = xmalloc(sizeof(Queue));

    QueueItem *items = xmalloc(sizeof(QueueItem) * size);

    (*queue)->items = items;
    (*queue)->first = 0;
    (*queue)->last = 0;
    (*queue)->size = size;
    (*queue)->count = 0;
}

Bool queuePush(Queue * const queue, QueueValue value, size_t val_sz) {
    if(isNull(queue) || isFull(queue)) return FALSE;

    queue->items[queue->last].value = xmalloc(val_sz);
    memcpy(queue->items[queue->last].value, value, val_sz);

    queue->last = (queue->last+1) % queue->size;
    queue->count += 1;

    return TRUE;
}

Bool queuePop(Queue * const queue, QueueValue *value) {
    if(isEmpty(queue)) return FALSE;

    *value = queue->items[queue->first].value;

    free(queue->items[queue->first].value);

    queue->first = (queue->first+1) % queue->size;
    queue->count -= 1;

    return TRUE;
}

问题出在queuePop功能上。当我调用它时，我失去了价值，因为我立即释放了它。我似乎无法解决这个困境。我希望我的库是通用的和模块化的。用户不应该关心分配和释放内存，这是图书馆的工作。

用户如何仍能从中获取值queuePop并让库处理所有内存分配/释放？

4

3 回答 3

2

我想你想改变你对存储什么的想法。一个用户给你一个指向她分配的内存的指针，所以她应该期望释放它。您不需要 memcpy 或释放该值，您只需要跟踪指针。推入队列应该将所有权转移给队列，从队列中弹出应该将所有权转移回用户。所以你需要做的就是复制'val'指针。

此外，要在完成后清理队列存储，您可能需要一个queueDestroy(Queue* q)函数。

编辑：

  • 请注意，您不需要 QueueItem，您可以存储一个 QueueValues 数组。
  • 另外，我意识到您明确表示内存管理是库的工作，但那是您遇到问题的时候（就像您遇到的问题一样）。库应该负责自己的内存管理（队列）。但是项目的分配和解除分配应该是用户的工作。
  • 另一种选择是提供一个 queueFront(Queue *q)，它传回该值，但随后它被 queuePop(Queue *q) 释放。不过我更喜欢你目前的方法:)
  • 要求用户定义队列的最大大小有点限制。如果您希望它是通用++、模块化++，那么您应该使用预定义的常量，然后在 queuePush() 上增长，如果它已满。或者，您可以使用链表实现（但连续内存通常要快得多）。
于 2010-04-18T02:18:15.913 回答
2

您的queuePop()功能需要以相同的方式工作queuePush()- 获取位置的大小并memcpy()对其进行处理。

Bool queuePop(Queue * const queue, QueueValue value, size_t val_sz)
{
    if (isEmpty(queue)) return FALSE;

    memcpy(value, queue->items[queue->first].value, val_sz);

    free(queue->items[queue->first].value);

    queue->first = (queue->first+1) % queue->size;
    queue->count -= 1;

    return TRUE;
}
于 2010-04-18T09:16:06.620 回答
1

其他人（正确地）指出了您设计的严重限制，但这将解决您所拥有的问题。它假设调用者知道什么大小的对象被推送和弹出。

从理论上讲，这些更改中只有两个是绝对必要的，但其他更改用于将崩溃的可能性（由于程序员错误）从 ~100% 降低到 ~80%。

typedef struct sQueueItem {
    QueueValue value;
    size_t     item_size;               // <-- you'll need this for the Pop
} QueueItem;

Bool queuePush(Queue * const queue, QueueValue value, size_t val_sz) {
    if(isNull(queue) || isFull(queue)) return FALSE;

    queue->items[queue->last].value = xmalloc(val_sz);
    memcpy(queue->items[queue->last].value, value, val_sz);
    queue->items[queue->last].item_size = val_sz;        // <-- save the size

    queue->last = (queue->last+1) % queue->size;
    queue->count += 1;

    return TRUE;
}

Bool queuePop(Queue * const queue, 
               QueueValue **value, // ESSENTIAL: now char **
               size_t item_size)   // so we can ensure enough room
{                                         
    if(isEmpty(queue)) return FALSE;

     // just for readability
    QueueItem *p = queue->items[queue->first];

    // watch for programmer error (maybe you should throw() something)
    assert(p->item_size == item_size);       

    // ESSENTIAL: copy the item to the caller's memory
    memcpy(*value, p->value, p->item_size); 

    free(queue->items[queue->first].value);

    queue->first = (queue->first+1) % queue->size;
    queue->count -= 1;

    return TRUE;
}

编辑：

有人指出我本可以queuePop离开

Bool queuePop(Queue * const queue, 
               QueueValue *value,  // stet
               size_t item_size)   // so we can ensure enough room

and changed the `memcpy` to 

    // ESSENTIAL: copy the item to the caller's memory
    memcpy(value, p->value, p->item_size);

我曾经在某个时候写过它，所以如果调用者在 中传递了一个 NULL item_size，queuePop将执行 amalloc()并将指针通过 传递回调用者**value。我改变了主意，以为我完全恢复了，但 SO 没有版本控制 :)

于 2010-04-18T04:04:08.233 回答