Why do i lost access to the Heap struct in the middle of the for loop?

Question

Look there, I had access to the struct heap when i = 34, but when i = 37 I lost it

I'm doing the Prim Algorithm to calculate the MST in c, but my heap is causing me problems, for no reason a lost the acces to Heap->Data[Origin] when i is bigger than 34.

I know it maybe is caused by the memory use, because it may not happen to small inputs.

    #ifndef MST_H
#define MST_H

#include <stdio.h>
#include <stdlib.h>
#include <sys/time.h>
#include <stdint.h>
#include <inttypes.h>
#include <limits.h>
#include "Heap.h"
#include "Graphs.h"

void InitializePrim(int32_t *Fathers, PriorityQueue *Heap,uint32_t NumberVertex, uint32_t Origin);

void PutInTree(Graph *Graph,
    int32_t *Parent,
    PriorityQueue *Heap,
    uint32_t Origin);

void Prim(Graph *Graph, uint32_t Origin, int32_t *Fathers);

#endif
#include "AlgorithmsMST.h"

    void InitializePrim(int32_t *Parent, PriorityQueue *Heap,uint32_t NumberVertex, uint32_t Origin)
    {
        if (&Heap->Data[Origin] == NULL)
        {
            printf("There was some problem\n");
            return;
        }
        for (int i = 1; i <= NumberVertex; ++i)
        {
            Parent[i] = -1;
            InsertItem(Heap,i,INT_MAX);
        }
        Parent[Origin] = 0;
        Heap->Data[Heap->Index[Origin]].Priority = 0;
        PromoveElement(Heap, Heap->Index[Origin]);
    }

    void PutInTree(Graph *Graph,
        int32_t *Parent,
        PriorityQueue *Heap,
        uint32_t Origin)
    {
        ListNode *Aux = Graph->Nodes[Origin].Head;
        while (Aux != NULL)
        {
            if ((Heap->Data[Heap->Index[Aux->Vertex]].Priority > Aux->Weigth) && (Heap->InHeap[Aux->Vertex] == 1 ))
            {
                Parent[Aux->Vertex] = Origin;
                Heap->Data[Heap->Index[Aux->Vertex]].Priority = Aux->Weigth;
                PromoveElement(Heap,Heap->Index[Aux->Vertex]);
            }
            Aux = Aux->Next;
        }
    }

    void Prim(Graph *Graph, uint32_t Origin, int32_t *Parent)
    {
        int i;
        uint32_t Smallest;
        PriorityQueue *Heap = MakeEmptyHeap(Graph->NumberVertex);
        InitializePrim(Parent,Heap,Graph->NumberVertex,Origin);
        for (i = 1; i <= Graph->NumberVertex; ++i)
        {
            Smallest = Heap->Data[0].Key;
            RemoveItem(Heap);
            PutInTree(Graph,Parent,Heap,Smallest);

        }
        DestroyHeap(Heap);
    }

Here is a copy of the gdb feedback for the error summary.

    (gdb) p i
$9 = 31
(gdb) p Heap->Data[Origin]
$10 = {Key = 2, Priority = 2.14748365e+09}
(gdb) c
Continuing.

Breakpoint 2, Prim (Graph=0x605250, Origin=1, Parent=0x60c1d0) at AlgorithmsMST.c:45
45          Parent[i] = -1;
(gdb) 
Continuing.

Breakpoint 2, Prim (Graph=0x605250, Origin=1, Parent=0x60c1d0) at AlgorithmsMST.c:45
45          Parent[i] = -1;
(gdb) 
Continuing.

Breakpoint 2, Prim (Graph=0x605250, Origin=1, Parent=0x60c1d0) at AlgorithmsMST.c:45
45          Parent[i] = -1;
(gdb) p i
$11 = 34
(gdb) p Heap->Data[Origin]
$12 = {Key = 2, Priority = 2.14748365e+09}
(gdb) c
Continuing.

Breakpoint 2, Prim (Graph=0x605250, Origin=1, Parent=0x60c1d0) at AlgorithmsMST.c:45
45          Parent[i] = -1;
(gdb) p Heap->Data[Origin]
Cannot access memory at address 0x100000007
(gdb) c
Continuing.

Breakpoint 2, Prim (Graph=0x605250, Origin=1, Parent=0x60c1d0) at AlgorithmsMST.c:45
45          Parent[i] = -1;
(gdb) p i
$13 = 36
(gdb) p Heap->Data[Origin]
Cannot access memory at address 0x7
(gdb)

I cannot research your header files, but in `InitializePrim` the line `if (&Heap->Data[Origin] == NULL)` looks like it should be `if (Heap->Data[Origin] == NULL)`. Do you enable all compiler warnings? — Weather Vane, Nov 11 '17 at 00:03
Look the image, it says i cannot access Heap->Data[Origin], i cannot access that memory adress. — Ariel Serafim, Nov 11 '17 at 00:11
"Look the image" - no: I am not going to look at images: we want text here, and only text please. — Weather Vane, Nov 11 '17 at 00:14
`for (int i = 1; i <= NumberVertex; ++i) { Parent[i] = -1; ...` looks like you don't understand that arrays are indexed from `0`. And again in `for (i = 1; i <= Graph->NumberVertex; ++i)` although in this loop, you ignore `i` and index by `0`. — Weather Vane, Nov 11 '17 at 00:17
i do understand, but use like that is good for my Graph problem, its easier to access and operate in some Vertex. — Ariel Serafim, Nov 11 '17 at 00:19
But it is undefined behavior in C. You are accessing and destroying memory outside your data. — Aganju, Nov 11 '17 at 04:03
I update the question with the error message from gdb, you dont have to look at the image anymore, please check that. — Ariel Serafim, Nov 12 '17 at 01:49

score 0 · Accepted Answer · answered Nov 13 '17 at 03:07

0

I just had forgotten an parentheses
    int32_t *Parent = (int32_t*)malloc((Graph->NumberVertex+1)*sizeof(int32_t));
    InitializePrim(Parent,Graph->NumberVertex,Origin);
    PriorityQueue *Heap = MakeEmptyHeap((Graph->NumberVertex));

That was enought to solve the question.

REMEMBER, DONT YOU NEVER, EVER FORGOT AN PARENTHESES.

answered Nov 13 '17 at 03:07

Ariel Serafim

11
5

[Don't cast the result of `malloc` in C](http://stackoverflow.com/q/605845/995714) – phuclv Nov 13 '17 at 03:13

Why do i lost access to the Heap struct in the middle of the for loop?

1 Answers1