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

Question

Я пытаюсь реализовать двоичную кучу с динамически выделяемой и свободной памятью, когда новые узлы вставляются или удаляются.Поэтому, когда вызывается узел вставки / удаления, я использую 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;
}

Answer 1

У вас есть скрытая ошибка при использовании 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/.

Answer 2

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

#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;
}

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

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

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

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