为队列设计一个调整大小的函数

Question

我目前正在尝试为队列数据结构设计一个 public API 和调整大小函数来改变它的大小。我的初衷是按以下方式进行：

typedef struct queue queue;

/**
 * Resizes a given queue.
 *
 * Changes the size of the queue passed as a parameter. 
 * The content of the resized queue prior to the lesser
 * of new and old sizes is left unchanged. 
 *
 * Returns:
 *  0 - on success
 * -1 - on error and the content of the original queue is left unchanged
 */
int queue_resize(queue * queue_ptr, size_t new_size);

问题是我阅读了 realloc 的合同，内容如下：

The realloc function returns a pointer to the new object (which may have the same value as a pointer to the old object), or a null pointer if the new object could not be allocated.

重新分配函数 return 新对象并回收旧对象是否是一种常见的方法？因此，在这种情况下，我应该重新设计 int queue_resize(queue *queue_ptr, size_t); 以使 queue * queue_resize(queue *queue_ptr, size_t); 具有相应的合同更改。

Answer 1

realloc 必须能够将分配的 space 移动到不同的地址才能工作。想象一下当前分配的内存已经被使用之后的内存。如果没有重定位，您将无法创建连续序列。

通常您的队列看起来像这样

typedef struct queue {
  some_type* data_member;
  size_t size;
  size_t capacity;
  // .. perhaps more
} queue;

所以当你有一个 queue_resize 函数时，你可以只传递一个 queue* 和新的大小。您传递给 realloc 的不是 queue*，而是它的 data_member。由于您已经有一个指向 queue 对象的指针，如果 realloc 选择更改它，您可以只更新 data_member 的指针。

在这种情况下，不需要返回一个新的 queue* 对象，因为 queue 的内存占用量永远不会改变。您也不必传递 queue** 或任何类似的东西。

Answer 2

上一个answers/comments不解决数据怎么办。考虑一下当 Java 运行时间发现数组需要更大时在 Java 中做了什么。例如。您尝试将一个元素附加到一个已经满的数组。

一个新的数组被分配了所需的大小；这包括设置元数据
必须设置一个锁，这样旧数组就不会改变
所有数据从现有数组复制到新数组；包括更新元数据；请注意，这两个数组需要同时存在
原来的数组被删除了（不确定这里的词是否正确。）
锁被移除
如果你只是 fiddle 使用指针，你会丢失数据。
您可以使用 Add() 和 Remove() 等标准方法轻松复制数据

为队列设计一个调整大小的函数

Designing a resize function for a queue

c

api-design

software-design

memory-reallocation