Программа аварийно завершает работу в realloc при прямом запуске, но нормально работает в режиме отладки

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

Мое рассуждение связано с тем, что если я удалю realloc внутри функции удаления (это означает, что я никогда не буду освобождать уже выделенную память), программа будет работать нормально при прямом запуске. В чем может быть проблема в коде?

PS: я использую Eclipse CDT вместе с Cygwin в Windows 10.

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

typedef struct heap
{
    uint32_t size;
    int32_t* heaparray;
}heap;


void insert_max(heap** h1, int32_t value)
{
    uint32_t hole;
    heap* h = *h1;

    if(h->size == 0)
    {
        h->size = 2;
        h->heaparray = (int32_t *)(malloc(sizeof(int32_t) * h->size));
        h->heaparray[0] = 0;
        h->heaparray[1] = value;
        return;
    }

    hole = h->size++;
    h->heaparray[0] = value;
    h->heaparray = (int32_t *)(realloc(h->heaparray , sizeof(int32_t) * h->size));

    //sift up
    for(; value > h->heaparray[hole/2]; hole /= 2)
    {
        h->heaparray[hole] = h->heaparray[hole/2];
    }
    h->heaparray[hole] = value;
}

void printheap(heap* h)
{
    uint32_t index;
    printf("\nHeap: ");
    for(index = 1; index < h->size; index++)
    {
        printf("%3d\t", h->heaparray[index]);
    }
}

void siftDown_max(heap** h1, uint32_t index)
{
    uint32_t rightIndex, leftIndex, maxIndex, temp;
    heap* h = *h1;
    leftIndex = (2 * index);
    rightIndex = (2 * index) + 1;
    if(rightIndex >= h->size)
    {
        if(leftIndex >= h->size)
            return;
        else
        {
            maxIndex = leftIndex;
        }
    }
    else
    {
        if(h->heaparray[rightIndex] >= h->heaparray[leftIndex])
        {
            maxIndex = rightIndex;
        }
        else
        {
            maxIndex = leftIndex;
        }
    }
    if(h->heaparray[index] < h->heaparray[maxIndex])
    {
        temp = h->heaparray[index];
        h->heaparray[index] = h->heaparray[maxIndex];
        h->heaparray[maxIndex] = temp;
        siftDown_max(h1, maxIndex);
    }
}

void siftDown_min(heap** h1, uint32_t index)
{
    uint32_t rightIndex, leftIndex, minIndex, temp;
    heap* h = *h1;
    leftIndex = 2 * index;
    rightIndex = (2 * index) + 1;

    if(rightIndex >= h->size)
    {
        if(leftIndex >= h->size)
        {
            return;
        }
        else
        {
            minIndex = leftIndex;
        }
    }
    else
    {
        if(h->heaparray[leftIndex] <= h->heaparray[rightIndex])
        {
            minIndex = leftIndex;
        }
        else
        {
            minIndex = rightIndex;
        }
    }

    if(h->heaparray[index] > h->heaparray[minIndex])
    {
        temp = h->heaparray[minIndex];
        h->heaparray[minIndex] = h->heaparray[index];
        h->heaparray[index] = temp;
        siftDown_min(h1, minIndex);
    }
}

void Delete(heap** h1, bool maxflag)
{
    uint32_t hole = 0;
    heap* h = *h1;
    if(h->size == 1)
    {
        h = NULL;
        return;
    }
    else
    {
        hole = --h->size;
        h->heaparray[1] = h->heaparray[hole];
        h->heaparray = (int32_t *)(realloc(h->heaparray , sizeof(int32_t) * h->size));
        if(maxflag)
        {
            siftDown_max(h1, 1);
        }
        else
        {
            siftDown_min(h1, 1);
        }
    }
}

void insert_min(heap** h1, int32_t value)
{
    uint32_t hole_index = 0;
    heap* local_heap = *h1;
    if (local_heap->size == 0)
    {
        local_heap->size = 2;
        local_heap->heaparray = (int32_t*)malloc(sizeof(int32_t) * local_heap->size);
        local_heap->heaparray[0] = 0;
        local_heap->heaparray[1] = value;
        return;
    }
    hole_index = local_heap->size++;
    local_heap->heaparray[0] = value;

    for(; value < local_heap->heaparray[hole_index/2]; hole_index /= 2)
    {
        local_heap->heaparray[hole_index] = local_heap->heaparray[hole_index / 2];
    }

    local_heap->heaparray[hole_index] = value;

}


int main(void)
{

    int hy = 0;
    heap *newheap = (heap *)(malloc(sizeof(heap)));
    newheap->size = 0;
    insert_max(&newheap, 5);
    insert_max(&newheap, 3);
    insert_max(&newheap, 8);
    insert_max(&newheap, 2);
    insert_max(&newheap, 10);
    insert_max(&newheap, 13);
    insert_max(&newheap, 7);
    insert_max(&newheap, 26);
    insert_max(&newheap, 11);
    printheap(newheap);
    Delete(&newheap, true);
    printheap(newheap);
    Delete(&newheap, true);
    printheap(newheap);
    Delete(&newheap, true);
    printheap(newheap);
    Delete(&newheap, true);
    printheap(newheap);
    Delete(&newheap, true);
    printheap(newheap);
    Delete(&newheap, true);
    printheap(newheap);
    Delete(&newheap, true);
    printheap(newheap);
    Delete(&newheap, true);
    printheap(newheap);
    Delete(&newheap, true);
    printheap(newheap);
    insert_max(&newheap, 134);
    printheap(newheap);

    heap *minheap = (heap *)(malloc(sizeof(heap)));
    minheap->size = 0;
    insert_min(&minheap, 5);
    printheap(minheap);
    insert_min(&minheap, 3);
    printheap(minheap);
    insert_min(&minheap, 8);
    printheap(minheap);
    insert_min(&minheap, 2);
    printheap(minheap);
    insert_min(&minheap, 10);
    printheap(minheap);
    insert_min(&minheap, 13);
    printheap(minheap);
    insert_min(&minheap, 7);
    printheap(minheap);
    insert_min(&minheap, 26);
    printheap(minheap);
    insert_min(&minheap, 11);
    printheap(minheap);
    Delete(&minheap, false);
    printheap(minheap);
    Delete(&minheap, false);
    printheap(minheap);
    Delete(&minheap, false);
    printheap(minheap);
    Delete(&minheap, false);
    printheap(minheap);
    Delete(&minheap, false);
    printheap(minheap);
    Delete(&minheap, false);
    printheap(minheap);
    Delete(&minheap, false);
    printheap(minheap);
    Delete(&minheap, false);
    printheap(minheap);
    Delete(&minheap, false);
    printheap(minheap);
    insert_min(&minheap, 138);
    printheap(minheap);
    hy = 3;

    return EXIT_SUCCESS;
}

c heap realloc
person Red Devil    schedule 11.12.2018    source источник
comment
сначала прочитайте это   -  person DaBler    schedule 11.12.2018
comment
Delete(&newheap, true); printheap(newheap); и сразу после этого снова Delete(&newheap, true); printheap(newheap); выглядит очень подозрительно....   -  person Jabberwocky    schedule 11.12.2018

Ответы (2)


arrow_upward
0
arrow_downward

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

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

typedef struct heap
{
    uint32_t size;
    int32_t* heaparray;
    // START DEBUG CODE    
    uint32_t debug_allocated_size;   // contains the actual allocated size
    // END DEBUG CODE
}heap;


void insert_min(heap** h1, int32_t value)
{
    uint32_t hole_index = 0;
    heap* local_heap = *h1;
    if (local_heap->size == 0)
    {
        local_heap->size = 2;
        local_heap->heaparray = (int32_t*)malloc(sizeof(int32_t) * local_heap->size);

        // START DEBUG CODE
        local_heap->debug_allocated_size = local_heap->size;
        // END DEBUG CODE

        local_heap->heaparray[0] = 0;
        local_heap->heaparray[1] = value;
        return;
    }
    hole_index = local_heap->size++;
    local_heap->heaparray[0] = value;

    for(; value < local_heap->heaparray[hole_index/2]; hole_index /= 2)
    {
      // START DEBUG CODE
      if (local_heap->debug_allocated_size >= hole_index)
      {
        // if hole_index is larger than the actuallly allocated size there is a problem...
        printf("argh: buffer overflow\n");
        exit(1);
      }
      // END DEBUG CODE

      local_heap->heaparray[hole_index] = local_heap->heaparray[hole_index / 2];
    }

    local_heap->heaparray[hole_index] = value;
}


int main(void)
{
    heap *minheap = (heap *)(malloc(sizeof(heap)));
    minheap->size = 0;
    insert_min(&minheap, 5);
    insert_min(&minheap, 3);
    insert_min(&minheap, 8);
    insert_min(&minheap, 2);

    return EXIT_SUCCESS;
}

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

Отказ от ответственности: в других частях вашего кода могут быть другие ошибки.

Предвосхищая ваш следующий вопрос: Почему мой код нормально работал в режиме отладки?

Ответ: ваша программа продемонстрировала "неопределенное поведение". Как только вы перезаписываете память, которая вам не принадлежит, вы попадаете в область «неопределенного поведения», и с этого момента может произойти что угодно.

person Jabberwocky    schedule 11.12.2018

arrow_upward
0
arrow_downward

У вас есть скрытая ошибка в использовании realloc:

h->heaparray = (int32_t *)(realloc(h->heaparray , sizeof(int32_t) * h->size));

Если realloc по какой-либо причине не работает, возвращается NULL. Когда это произойдет, ваша программа будет ужасно аварийно завершать работу. realloc — это просто уродливая функция, которую вы должны использовать очень осторожно.

У меня нет решения вашей проблемы. Тем не менее, у меня есть несколько общих советов по созданию кучи в частности и структур данных коллекций с изменяемым размером в целом.

Выполняя перераспределение при каждой вставке и удалении, вы создали кучу с O(n) вставкой и O(n) удалением. С тем же успехом вы могли бы использовать неупорядоченный массив, потому что преимущества структуры кучи затмеваются затратами на перераспределение и копирование памяти каждый раз.

Если вы хотите использовать динамический массив, вы должны начать с некоторого минимального размера, скажем, 16 элементов, и следить за свободным пространством в вашем массиве. Когда вы перераспределяете, увеличьте более чем на 1. Вероятно, вам лучше всего удвоить размер массива. Таким образом, вы амортизируете стоимость перераспределения. Ваша вставка и удаление становятся O (log n), а не O (n).

Суть в том, что вашей структуре heap требуется поле count, которое отслеживает текущее количество элементов в куче:

typedef struct heap
{
    uint32_t size;  /* size of the heap array */
    uint32_t count; /* number of items currently in the heap */
    int32_t* heaparray;
}heap;

Поэтому, когда вы вставляете, вы проверяете, не count == size. Если это так, то перераспределите, чтобы удвоить размер. Всегда используйте count (а не size, как в вашем текущем коде) в ваших вычислениях, когда вы вставляете и удаляете.

При удалении элементов перераспределяйте их только в том случае, если size > count*2. Таким образом, вы сведете к минимуму количество обращений к realloc. Вам также может понадобиться функция trimToCount, которую вы можете вызывать, если хотите минимизировать объем памяти, занимаемой кучей.

Кроме того, пересмотрите свой выбор кучи на основе 1. Массивы C основаны на 0, поэтому имеет смысл, чтобы корень кучи находился в индексе 0. Тривиально настроить родительские и дочерние вычисления так, чтобы они работали с кучей, начинающейся с 0. Подробнее о рассуждениях здесь см. https://stackoverflow.com/a/49806133/56778 и http://blog.mischel.com/2016/09/19/but-thats-the-way-weve-always-done-it/.

person Jim Mischel    schedule 11.12.2018
comment
Это все хорошие советы по реализации кучи, но я не думаю, что это имеет какое-то отношение к сбою программы. - person user253751; 12.12.2018
comment
Спасибо, и это имеет смысл, но почему здесь не работает realloc? Я только пытаюсь перераспределить максимум 200 байт - person Red Devil; 13.12.2018