Разработка функции изменения размера очереди - PullRequest
Новая
       15

Разработка функции изменения размера очереди

2 голосов
/ 20 апреля 2019

В настоящее время я пытаюсь спроектировать общедоступный 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, и это было следующим:

Функция realloc возвращает указатель на новый объект (который может иметь то же значение, что и указатель на старый объект), или нулевой указатель, если новый объект не может быть выделен.

Является ли распространенным подходом для функций перераспределения возвращать новый объект и возвращать старый? Так что в таком случае я должен был изменить int queue_resize(queue *queue_ptr, size_t);, чтобы сделать queue * queue_resize(queue *queue_ptr, size_t); с соответствующими изменениями контракта.

Ответы [ 2 ]

3 голосов
/ 20 апреля 2019

realloc должен иметь возможность перемещать выделенное пространство на другой адрес, чтобы он мог работать. Представьте себе память сразу после того, как выделенная в данный момент память уже используется. Без перемещения вы не могли бы создать непрерывную последовательность.

Обычно ваша очередь будет выглядеть примерно так 

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

Таким образом, когда у вас есть функция queue_resize, вы можете просто передать queue* и новый размер. То, что вы передаете realloc, это не queue*, а data_member. Поскольку у вас уже есть указатель на объект queue, вы можете просто обновить указатель на data_member, если realloc решит изменить его.

В этом случае возвращать новый объект queue* не нужно, поскольку объем памяти queue никогда не изменяется. Вам также не нужно передавать queue** или что-либо в этом роде.

2 голосов
/ 20 апреля 2019

Предыдущие ответы / комментарии не касаются того, что делать с данными. Рассмотрим, что делается в Java, когда среда выполнения Java обнаруживает, что массив должен быть больше. Например. вы пытаетесь добавить элемент к уже заполненному массиву.

  • новый массив выделяется с нужным размером; это включает настройку метаданных
  • необходимо установить блокировку, чтобы старый массив не изменился
  • все данные копируются из существующего массива в новый массив; включает в себя обновление метаданных; обратите внимание, что оба массива должны существовать одновременно для этого
  • оригинальный Массив удален (не уверен в правильном слове здесь.)
  • замок снят
  • Если вы просто возитесь с указателями, вы потеряете данные.
  • Вы можете легко скопировать данные, используя стандартные методы, такие как Add () и Remove ()
...