«значение по умолчанию» выделенного указателя структуры в C

Question

Я храню входные данные, которые включают в себя определенный порядок, поэтому я решил использовать массив для их сортировки:

struct Node** array = (struct Node**)malloc(sizeof(Node**) * DEFAULT_SIZE);

int i;
int size = DEFAULT_SIZE;
while(/* reading input */) {
    // do something
    int index = token;    // token is part of an input line, which specifies the order
    struct Node* node = (struct Node*)malloc(sizeof(struct Node));
    *node = (struct Node){value, index};
    // do something

    if (index >= size) {
        array = realloc(array, index + 1);
        size = index + 1;
    }

    array[index] = node;
}

Я пытаюсь перебрать массив и что-то сделать, когда узел существует с индексом

int i;
for (i = 0; i < size; i++) {
    if (/* node at array[i] exists */) {
        // do something
    }
}

Как я могу проверить, существует ли узел по определенному индексу массива? (Или каково «значение по умолчанию» узла struct после того, как я выделил его память?) Я только знаю, что это не NULL ...

Должен ли я использовать calloc и попробовать if ((int)array[index] != 0)? Или есть лучшая структура данных, которую я могу использовать?

Answer 1

Когда вы realloc (или malloc) ваш список указателей, система изменяет размер / перемещает массив, копируя ваши данные, если это необходимо, и резервируя больше места вперед без изменения данных , поэтому Вы получаете то, что было раньше. Вы не можете полагаться на значения.

Только calloc инициализирует ноль, но вы не можете calloc, когда вы realloc.

Для начала вы, вероятно, должны использовать calloc:

struct Node** array = calloc(DEFAULT_SIZE,sizeof(*array));

В вашем цикле просто используйте realloc и установите новую память на NULL, чтобы вы могли проверить нулевые указатели

Обратите внимание, что ваш realloc размер указан неверно, вы должны умножиться на размер элемента. Также обновите size после перераспределения, иначе это не сработает более одного раза.

Обратите внимание на хитрый memset, который обнуляет только нераспределенные данные без изменения допустимых данных указателя. array+size вычисляет правильный размер адреса из-за арифметики указателя, но параметр size указан в байтах, поэтому вам нужно умножить на sizeof(*array) (размер элемента)

if (index >= size)
   {
      array = realloc(array, (index + 1)*sizeof(*array));  // fixed size
      memset(array+size,0,(index+1-size) * sizeof(*array));  // zero the rest of elements
      size = index+1;  // update size
   }

в сторону

• realloc для каждого элемента неэффективно, вы должны перераспределять по частям, чтобы избежать слишком большого количества системных вызовов / копий
• Я упростил вызовы malloc, нет необходимости приводить возвращаемое значение malloc, а также лучше передавать sizeof(*array) вместо sizeof(Node **). В случае изменения типа array, на который вы распространяется (также защищает вас от одноразовых ошибок с помеченными типами)

Answer 2

Недавно выделенная память содержит мусор, и чтение указателя из неинициализированной памяти является ошибкой.

Если вместо этого вы используете calloc( DEFAULT_SIZE, sizeof(Node*) ), содержимое массива будет определено: все биты будут установлены в ноль. Во многих реализациях это указатель NULL, хотя стандарт не гарантирует этого. Технически, это мог бы быть стандартный компилятор, который приводит к аварийному завершению программы, если вы пытаетесь прочитать указатель со всеми битами, установленными в ноль.

(Об этом должны беспокоиться только языковые юристы. На практике даже пятидесятилетние мэйнфреймы приводят в качестве примера машины, где NULL не был двоичным 0, обновлял свой компилятор C для распознавания 0 как указатель NULL, потому что это сломало слишком много кода.)

Безопасный, переносимый способ сделать то, что вы хотите, это инициализировать каждый указатель в массиве на NULL:

struct Node** const array = malloc(sizeof(Node**) * DEFAULT_SIZE);
// Check for out-of-memory error if you really want to.
for ( ptrdiff_t i = 0; i < DEFAULT_SIZE; ++i )
  array[i] = NULL;

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

Вызов realloc() ошибочен. Если вы хотите сделать это таким образом, аргумент size должен быть новым числом элементов, умноженным на размер элемента. Этот код с радостью сделает его четверть или восьмой желаемого размера. Даже без этой ошибки, связанной с повреждением памяти, вы будете слишком часто перераспределяться, что может потребовать копирования всего массива в новое место в памяти.

Классическим решением для этого является создание связанного списка страниц массива, но если вы собираетесь realloc(), было бы лучше каждый раз умножать размер массива на константу.

Точно так же, когда вы создаете каждый Node, вы хотите инициализировать его поля указателя, если вы заботитесь о переносимости. Ни один компилятор в этом веке не будет генерировать менее эффективный код, если вы это сделаете.

Если вы размещаете узлы только в последовательном порядке, альтернативой является создание массива Node вместо Node* и ведение счетчика количества используемых узлов. Современная настольная ОС будет отображать только столько страниц физической памяти для массива, сколько записывает ваш процесс, поэтому простое выделение и не инициализация большого динамического массива не приводит к потере реальных ресурсов в большинстве сред.

Еще одна ошибка, которая, вероятно, является доброкачественной: элементы вашего массива имеют тип struct Node*, но вы выделяете sizeof(Node**), а не sizeof(Node*) байт для каждого. Однако компилятор этого не проверяет, и я не знаю ни одного компилятора, где размеры этих двух типов указателей на объекты могли бы быть разными.

Answer 3

Вам может понадобиться что-то вроде этого

unsigned long i;
for (i = 0; i < size; i++) {
    if (array[i]->someValidationMember==yourIntValue) {
        // do something
    }
}

Редактировать. Выделенная память должна быть пустой. Или, если элемент удален, просто измените элемент Node на ноль или любой другой по вашему выбору.