realloc(): недействительный следующий размер и двойной бесплатный

Question

Как домашнее задание, я должен создать 2 функции, которые позволят вам нажимать и выталкивать элементы в массив, который действует как очередь. Мы должны делать это, динамически выделяя память. Моя программа почти работает, но иногда, когда вы добавляете и удаляете слишком много элементов, я получаю такие ошибки, как «realloc(): недопустимый следующий размер», double free (когда я только вызывал свободную функцию один раз), а некоторые из элементов в начало очереди установлено на 0. Например, если я сначала добавлю 100 элементов, а затем удаляю 90 и пытаюсь добавить еще 20, я получаю «free(): недопустимый следующий размер (быстрый): 0x0000000001ea6010». Что я здесь делаю неправильно?

В соответствии с предложениями ниже я изменил свои функции, чтобы использовать двойной указатель как вход для массива. Это, однако, теперь дает мне ошибку Сегментация - это значит, теперь я не знаю, что искать на всех ...

#include <stdio.h> 
#include <stdlib.h> 

void enqueue(int **arr, int* lastElementIdx, size_t* totalElements, int element) { 
    if (*lastElementIdx >= *totalElements) {  // check if memorry is sufficient, otherwise double 
     *totalElements *= 2; 

     int* temp = realloc(arr, (*totalElements * sizeof(int))); 

     if (temp == NULL) {   // just in case realloc fails 
      printf("Allocation error\n"); 
     } else { 
      *arr = temp; 
     } 
    } 

    if (*lastElementIdx <= *totalElements) { 
     *lastElementIdx += 1;  // once everything is done: add element 
     *arr[*lastElementIdx] = element; 
    } 
} 

int dequeue(int **arr, int* lastElementIdx, size_t* totalElements) { 
    if (*lastElementIdx > -1) {  // if queue is not empty... 
     int deleted = *arr[0];  // save deleted value first (in case it's still needed) 
     for (int i = 0; i <= *lastElementIdx; i++) { // shift all elements 
      *arr[i] = *arr[i + 1]; 
     } 
     *lastElementIdx -= 1; // index is now decreased by 1 

     if (((*totalElements/2) >= 10) && ((*lastElementIdx + 1) < (*totalElements/2))) { // cut memory in half if not needed 
      *totalElements /= 2; 

      *arr = realloc(arr, (*totalElements * sizeof(int))); 
      int* temp = realloc(arr, (*totalElements * sizeof(int))); 
      if (temp == NULL) {  // in case realloc fails 
       printf("Allocation error\n"); 
       return 0; 
      } else { 
       *arr = temp; 
      } 
     } 

     return deleted; 
    } else {  // if queue is empty, print that there's nothing to dequeue 
     printf("There are no elements inside the queue\n"); 
     return 0; 
    } 
} 

void printQueue(int arr[], int lastElementIdx) { 
    for (int i = 0; i <= lastElementIdx; i++) {  // print entire queue 
     printf("[%d] = %d\n", i, arr[i]); 
    } 
    printf("\n"); 
} 

int main (void) { 

    size_t totalElements = 10;  // number of needed elements at the time 
    int lastElementIdx = -1;  // index of last element in queue at the time 
    int *arr = calloc(totalElements, sizeof(int)); 
    int **arrpointer = &arr; 

    for (int i = 1; i < 101; i++) { 
     enqueue(arrpointer, &lastElementIdx, &totalElements, i); 
    } 

    printQueue(arr, lastElementIdx); 

    for (int i = 0; i < 90; i++) { 
     dequeue(arrpointer, &lastElementIdx, &totalElements); 
    } 

    printQueue(arr, lastElementIdx); 

    for (int i = 1; i < 21; i++) { 
     enqueue(arrpointer, &lastElementIdx, &totalElements, i); 
    } 

    printQueue(arr, lastElementIdx); 

    free(arr); 

    return EXIT_SUCCESS; 

} 

Answer 1

Может быть, это не единственная проблема, но, по крайней мере, следующая строка не что вы, кажется, ожидать:

*temp = *arr;

Это выглядит так, как будто вы хотите заменить обр с результатом перераспределить, доставляя его обратно в вызывающую функцию (как с другими аргументами INOUT). Но, arr не является аргументом inout: это массив целых чисел, а не указатель на массив целых чисел. То, что вы на самом деле делаете с приведенной выше строкой кода, - это скопировать первый элемент arr в недавно выделенный диапазон памяти. Тем не менее, этот недавно выделенный временной диапазон памяти, тем не менее, забыт, создавая утечку памяти.

Answer 2

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

Ваше использование переменной temp дает представление о том, что вы знаете об этой проблеме, но поскольку @DerkHermann впервые наблюдал, вы неправильно обрабатываете полученный указатель. Возможно, вы хотели написать что-то по линиям

arr = temp; 

вместо этого. Однако этого недостаточно. C имеет только пропускную способность, поэтому, если вы изменяете значение параметра функции arr, эта модификация видна только в функции (которая получает в arr копию значения, которое проходит вызывающий абонент). В случае, если realloc() выделяет новый блок, который оставляет вызывающего абонента с недопустимым указателем.

Если вы хотите, чтобы ваши enqueue() и dequeue() функции, чтобы иметь возможность изменить размер для хранения очереди, то вы должны передать указатель на это хранилище косвенно. Самый простой способ сделать это, учитывая, где вы сейчас, будет проходить двойной указатель, так что вы можете изменить его referrent:

void enqueue(int **arr, int* lastElementIdx, size_t* totalElements, int element) { 
    /* ... */ 
    *arr = temp; 
    /* ... */ 
} 

Заметим, однако, что вы передаете три отдельные указатели, что среди они представляют состояние очереди.Было бы чище создать struct тип, который сочетает в себе эти детали в одном пакете, и передать указатель на объект этого типа:

struct queue { 
    int *arr; 
    size_t capacity; 
    size_t last_element_index; 
}; 

void enqueue(struct queue *queue, int element) { 
    /* ... */ 
    queue->arr = temp; 
    /* ... */ 
} 

Answer 3

Добавление двойной указатель перераспределить пространство, в нужных местах, изменение функция сравнения с size_t totalElements и исправление нескольких дополнительных ошибок, наконец, сделали трюк.

#include <stdio.h> 
#include <stdlib.h> 

void enqueue(int **arr, int* lastElementIdx, size_t* totalElements, int element) { 
    if (*lastElementIdx + 1 >= (int)(*totalElements) - 1) {  // check if memorry is sufficient, otherwise double 
     *totalElements *= 2; 

     int* temp = realloc(*arr, (*totalElements * sizeof(int))); 
     if (temp == NULL) {   // just in case realloc fails 
      printf("Allocation error\n"); 
     } else { 
      *arr = temp; 
     } 
    } 

    if (*lastElementIdx + 1 <= (int)(*totalElements) - 1) { 
     *lastElementIdx += 1;  // once everything is done and if there is now enough space: add element 
     (*arr)[*lastElementIdx] = element; 
    } 
} 

int dequeue(int **arr, int* lastElementIdx, size_t* totalElements) { 
    if (*lastElementIdx > -1) {  // if queue is not empty... 
     int deleted = (*arr)[0];  // save deleted value first (in case it's still needed) 
     for (int i = 0; i <= *lastElementIdx; i++) { // shift all elements 
      (*arr)[i] = (*arr)[i + 1]; 
     } 
     *lastElementIdx -= 1; // index is now decreased by 1 

     if (((*totalElements/2) >= 10) && ((*lastElementIdx + 1) < (*totalElements/2))) { // cut memory in half if not needed 
      *totalElements /= 2; 

      int* temp = realloc(*arr, (*totalElements * sizeof(int))); 
      if (temp == NULL) {  // in case realloc fails 
       printf("Allocation error\n"); 
       return 0; 
      } else { 
       *arr = temp; 
      } 
     } 

     return deleted; 
    } else {  // if queue is empty, print that there's nothing to dequeue 
     printf("There are no elements inside the queue\n"); 
     return 0; 
    } 
} 

void printQueue(int arr[], int lastElementIdx) { 
    for (int i = 0; i <= lastElementIdx; i++) {  // print entire queue 
     printf("[%d] = %d\n", i, arr[i]); 
    } 
    printf("\n"); 
} 

int main (void) { 

    size_t totalElements = 10;  // number of needed elements at the time 
    int lastElementIdx = -1;  // index of last element in queue at the time 
    int *arr = calloc(totalElements, sizeof(int)); 
    int **arrpointer = &arr; 

    for (int i = 1; i < 101; i++) { 
     enqueue(arrpointer, &lastElementIdx, &totalElements, i); 
    } 

    printQueue(arr, lastElementIdx); 

    for (int i = 0; i < 102; i++) { 
     dequeue(arrpointer, &lastElementIdx, &totalElements); 
    } 

    printQueue(arr, lastElementIdx); 

    for (int i = 1; i < 21; i++) { 
     enqueue(arrpointer, &lastElementIdx, &totalElements, i); 
    } 

    printQueue(arr, lastElementIdx); 

    free(arr); 

    return EXIT_SUCCESS; 

}