Removal item in chained list C

Question

Guys I’m having a very annoying little problem, I’m implementing a simple A* . When I move the already checked item to the closed list and move the item from the open list, it is giving undeclared pointer error... That is the mistake pointer being freed was not allocated, but I already checked my logic and also checked if I was dislocating a pointer that had actually been declared with malloc and it really was! I even use it in the same code, another displacement code. I practically copied and pasted on each other and what was already done and no problem, but in the new gives... Look:

This is the code that’s working (I use this code to animate as well):

void anima(Lista* li, int frame, int agFramex, int agFramey){
    Elem* no = (Elem*) malloc(sizeof(Elem));
    Elem* ant = (Elem*) malloc(sizeof(Elem));
    no = (*li);
    ant = no;
    while(no != NULL){
        if(no->dados.y > ALT+200){
            if(no == *li){
                *li = no->Prox;
                free(no);
                no = *li;
            } else if(no->Prox == NULL){
                ant->Prox = no->Prox;
                free(no);
                no = ant->Prox;
            } else {
                ant->Prox = no->Prox;
                free(no);
                no = ant->Prox;
            }
        } else {
            no->dados.y += no->dados.vel;
            al_draw_bitmap_region(no->dados.Img, agFramex*frame, agFramey*frame, frame, frame, no->dados.x, no->dados.y, 0);
            ant = no;
            no = no->Prox;
        }
    }
}

That’s the code that’s not: (atual and AbList exist, are as function parameter up there, as the function was very extensive I chose not to put it whole here, in the previous moments of the function I put elements in the list just that):

Elc* rem = (Elc*) malloc(sizeof(Elc));
Elc* mer = (Elc*) malloc(sizeof(Elc));

rem = (*AbList);
mer = rem;
while(rem != NULL){
    if(rem->dados.x == atual.dados.x && rem->dados.y == atual.dados.y){
        if(rem == *AbList){
            *AbList = rem->Prox;
            free(rem);
            rem = *AbList;
        } else if(rem->Prox == NULL){
            mer->Prox = rem->Prox;
            free(rem);
            rem = mer->Prox;
        } else {
            mer->Prox = rem->Prox;
            free(rem);
            rem = mer->Prox;
        }
    } else {
        mer = rem;
        rem = rem->Prox;
    }
}

As you can see, the codes are very much the same, but for some reason in this I get the error and in the other...

Obs: Usage Macbook Pro I am coding in C using Allegro.

Answer 1

I suppose that Lista be a Elem* and that Lista* be a Elem**. Correct?

Let’s see the start of the first function:

Elem* no = (Elem*) malloc(sizeof(Elem));  // Aloca um elemento
Elem* ant = (Elem*) malloc(sizeof(Elem)); // Aloca outro elemento
no = (*li);                               // Perde a referência do no alocado. Memory leak.
ant = no;                                 // Perde a outra referência também. Memory leak.
// Neste ponto no == ant == *li

Now the second:

Elc* rem = (Elc*) malloc(sizeof(Elc)); // Aloca um elemento.
Elc* mer = (Elc*) malloc(sizeof(Elc)); // Aloca um elemento.

rem = (*AbList);                       // Perde a referência. Memory leak.
mer = rem;                             // Perde outra referência. Memory leak.
// Neste ponto mer == rem == *AbList

Let’s take a closer look at your first job:

            if(no == *li){
                *li = no->Prox;
                free(no);
                no = *li;
                // Esquece que ant pode ser igual a no.
                // Se for igual, agora ant é um ponteiro inválido!
                // Se for diferente, então ant->Prox é um ponteiro inválido!

And also:

            } else if(no->Prox == NULL){
                ant->Prox = no->Prox; // Ou seja, ant->Prox = NULL;
                free(no);
                no = ant->Prox; // Ou seja, no = NULL;
            } else {
                // Este bloco é idêntico ao anterior!
                ant->Prox = no->Prox;
                free(no);
                no = ant->Prox;
            }

So never let the ant point to anything other than the previous node of no. And in the case of no be the first, who ant be it NULL. Either he has to point to something valid or to NULL, never let it point to something invalid! The same can be stated about ant->Prox.

Also, every code in the form } else if (x) { A; } else { A; }, where the evaluation of x has no side effects, can be replaced simply by } else { A; }.

void anima(Lista* li, int frame, int agFramex, int agFramey){
    Elem *no = *li;
    Elem *ant = NULL;
    while (no != NULL) {
        if (no->dados.y > ALT + 200) {
            if (no == *li) {
                *li = no->Prox;
                free(no);
                no = *li;
                // Aqui ant era NULL e continua sendo NULL.
            } else {
                // Se entrou aqui, então ant não é NULL.
                // Isso funciona mesmo se no->Prox for NULL.
                ant->Prox = no->Prox;
                free(no);
                no = ant->Prox;
            }
        } else {
            no->dados.y += no->dados.vel;
            al_draw_bitmap_region(no->dados.Img, agFramex * frame, agFramey * frame, frame, frame, no->dados.x, no->dados.y, 0);
            ant = no;
            no = no->Prox;
        }
    }
}

What really changes in the behavior in this code above compared to the previous one is only that the memory Leaks have been eliminated and ant = no; was replaced by Elem *ant = NULL;.

We can apply the same transformations to its second function, which has the same structure. This is the result:

Elc* rem = *AbList;
Elc* mer = NULL;

while(rem != NULL){
    if (rem->dados.x == atual.dados.x && rem->dados.y == atual.dados.y) {
        if (rem == *AbList) {
            *AbList = rem->Prox;
            free(rem);
            rem = *AbList;
            // Aqui mer era NULL e continua sendo NULL.
        } else {
            // Se entrou aqui, então mer não é NULL.
            // Isso funciona mesmo se rem->Prox for NULL.
            mer->Prox = rem->Prox;
            free(rem);
            rem = mer->Prox;
        }
    } else {
        mer = rem;
        rem = rem->Prox;
    }
}

Oh yes, I almost forgot. If the address of atual is something that may appear on the list started by *AbList, this second code will always give a blow if you arrive in a case where rem == &atual and the free(rem); is executed and then you try to access atual.dados.x or atual.dados.y. If this happens, make a copy somewhere else that is off the list and access only the copy. If this does not happen (or if atual is already exactly that copy), so it’s all quiet on that.