0

此代码使用 realloc() 实现了一个可扩展队列，这只是原始代码的一部分。

当我运行这个得到一个错误：

typedef uint32_t u32;
typedef uint64_t u64;

typedef struct _queue_t *queue_t;

struct _queue_t {
    u32 *array;
    u32 FirstElem;
    u32 LastElem;
    u32 memory_allocated;
    u32 Size;
};

queue_t queue_empty() {
    queue_t queue = calloc (1, sizeof (struct _queue_t));

    assert(queue != NULL);

    queue->array = (u32 *) calloc(16, sizeof(u32));
    queue->FirstElem = 0;
    queue->LastElem = 0;
    queue->memory_allocated = 16*sizeof(u32);
    queue->Size = 0;

    return queue;
}

void increment_queue(queue_t queue) {

    queue->memory_allocated += 16;
    queue->array = realloc (queue->array, queue->memory_allocated);
    assert(queue->array != NULL);
}

queue_t enqueue(queue_t queue, u32 vertex) {

    assert(queue != NULL);
    assert(queue->array != NULL);

    if ((queue->memory_allocated)/sizeof(u32) == queue->Size) {
        increment_queue(queue);
    }

    if (queue->Size == 0) {
    queue->array[queue->LastElem] = vertex;
    } else {
        queue->LastElem += 1;
        queue->array[queue->LastElem] = vertex;
    }

    queue->Size = queue->Size + 1;

    return queue;
}

queue_t dequeue(queue_t queue) {

    assert (queue != NULL);
    assert (queue_size(queue) != 0);

    queue->FirstElem += 1;
    queue->Size -= 1;
    queue->memory_allocated -= sizeof(u32);

    return queue;
}

int main() {
    queue_t newq = queue_empty();

    for (u32 i = 0; i < 20; i++) {
        enqueue(newq, i);
    }
    for (u32 i = 0; i < 10; i++) {
        dequeue(newq);
    }
    for (u32 i = 0; i < 100; i++) {
        enqueue(newq, i);
    }

    return 0;
}

错误是：

* 检测到 glibc./mini: realloc(): 无效的下一个大小：0x0000000001782030 * *
======= 回溯：======== ..... ............

4

2 回答 2

1

问题出在 dequeue 你减量的地方queue->memory_allocated。正在发生的事情是这样的：您创建了一个 empty_queue。您开始向数组添加元素 - 这会将大小增加 16。我们一直输入元素直到第 16 次，然后我们将大小增加到 32。并完成使用其中的前 20 个。

此时内存中的数组用于前 20 个，后 12 个未使用。然后我们开始调用 dequeue 并删除 10 个项目。大小现在等于 10 并且 memory_allocated/u32 等于 22。您开始添加更多元素并添加 12 个更多元素（在我们在数字 20 和 32 之间的 12 个可用空间中）此时 size == memory_allocated/u32 所以我们将 memory_allocated 增加 16。分配的内存现在等于 38。

内存中的数组看起来像这样：大小为 22。

我们开始添加更多元素，在第 6 个元素中，我们将其写入数组末尾。现在发生的任何事情都是公平的游戏。你已经破坏了记忆，显然最终会写下一些重要的东西。

于 2013-06-19T04:13:39.427 回答
0

戴夫是正确的，但我真的认为你想重新考虑这段代码。在添加 20 个值，然后减去 10 后，您将获得如下所示的内存（未按比例缩放）：

queue->array             beginning of queue         end of queue          end of buffer
|  |  |   |   |   |   |  |  |   |  |   |   |   |   |   |   |   |   |   |   | |   |   | 
0                        10                           20                   32

所以'Size'是10，memory_allocated真的很奇怪，因为你首先将它增加16 * sizeof（u32），然后在increment_queue（）中增加16，这被认为是一个错误）..

但最重要的是，然后您调用 realloc() 并使用 queue->array 作为指针...如果您当时真的想将队列大小调整为 10 个元素，那么您实际上要做的是将缓冲区截断为 10从 0 开始的元素.. 丢弃队列有效部分（10 到 20 之间）中的所有值。

如果这个例子没有帮助..想想当你添加 20 个元素时会发生什么，然后将 20 个元素出队。FirstElem 和 LastElem = 20, size = 0, first 和 last 永远不会被重置.. 如果您继续添加 16 个元素，您将在 queue->array 上调用 realloc，大小为 16，但没有新的 16 个元素添加将在重新分配的缓冲区中。realloc 可能会从 queue->array 截断为 queue->array+16*sizeof(u32).. 但您的元素将位于 queue->array+20，现在位于未分配的内存中。

我认为你需要重新考虑你的整个算法。或者，如果您只是在 unix 系统上寻找一个简单的队列实现，请查看“man queue”（或查看 /usr/include/sys/queue.h）。

于 2013-06-19T04:30:56.373 回答