free() does not work in Dynamic Stack code

Question

The dynamic stack works normally, but when I try to use the free() method to de-locate the memory of the removed elements and reboot the structure, the compiler does not return as expected. Actually, nothing appears, no error, but it doesn’t work. The code only works normally after commenting on the free function().

I already looked for the possible error, but I did not find it. I’m pretty sure it’s a flaw in the code structure. However, as I said above, it apparently works except when I try to shift memory and I don’t know where the error is.

Functions where apparently the problem happens (pop and restartStack):

int pop (STACK *stack) {

    if (stack->top != NULL) {
        ELEMENT *aux = stack->top;
        stack->top = stack->top->next;
        free(aux);

        return TRUE;
    }

    return FALSE;
}

void restartStack (STACK *stack) {
    ELEMENT *position = stack->top;

    while (position != NULL) {
        ELEMENT *remove = position;
        position = position->next;
        free(remove);
    }

    stack->top = NULL;

}

The structure as a whole:

#include <stdio.h>
#include <malloc.h>

#define TRUE 0
#define FALSE 1
#define DEBUG
#undef DEBUG
typedef int TYPEKEY;


typedef struct {
    TYPEKEY key;
    struct ELEMENT* next;
} ELEMENT;

typedef struct {
    ELEMENT *top;
} STACK;

void startStack (STACK *stack) {
    stack->top = NULL;
}

int stackLenght (STACK *stack) {
    ELEMENT *element = stack->top;
    int lenght = 0;

    while (element != NULL) {
        element = element->next;
        lenght++;
    }

    return lenght;
}

int isEmpty (STACK *stack) {
    return stack->top == NULL ? TRUE : FALSE;
}

void showElements (STACK *stack) {
    ELEMENT *element = stack->top;

    while (element != NULL) {
        printf("%d ", element->key);
        element = element->next;
    }

    printf("\n");
}

void push (STACK *stack, ELEMENT *elementToInsert) {

    /* Aloca memória */
    ELEMENT *aux = (ELEMENT*) malloc(sizeof(ELEMENT));
    /* Guarda o antigo topo */
    aux = stack->top;

    /* O novo elemento é o topo*/
    stack->top = elementToInsert;

    /* O antigo topo é o next */
    elementToInsert->next = aux;

}

int pop (STACK *stack) {

    if (stack->top != NULL) {
        ELEMENT *aux = stack->top;
        stack->top = stack->top->next;
        free(aux);

        return TRUE;
    }

    return FALSE;
}

ELEMENT* topStack (STACK *stack) {
    return stack->top != NULL ? stack->top : NULL;
}

void restartStack (STACK *stack) {
    ELEMENT *position = stack->top;

    while (position != NULL) {
        ELEMENT *remove = position;
        position = position->next;
        free(remove);
    }

    stack->top = NULL;

}

main:

int main () {
        ELEMENT ELEMENT, ELEMENT2, ELEMENT3;

        STACK stack;

        ELEMENT.key = 5;
        ELEMENT2.key = 7;
        ELEMENT3.key = 2;

        startStack(&stack);
        push(&stack, &ELEMENT);
        push(&stack, &ELEMENT2);
        push(&stack, &ELEMENT3);
        //pop(&stack); - ERRO, COMPILADOR FICAR EM LOOPING OU RETORNA UM EXIT CODE != 0
        //restartStack(&stack); - ERRO, COMPILADOR FICAR EM LOOPING OU RETORNA UM EXIT CODE != 0

        printf("%d\n", stackLenght(&stack));

        showElements(&stack);
}

Answer 1

You see, you’re letting the compiler do the allocation, and then you try to release that memory (if I’m not mistaken, the behavior of that is undefined, which can give you a lot of headaches).

int pop (STACK *stack) {

    if (stack->top != NULL) {
        ELEMENT *aux = stack->top;
        stack->top = stack->top->next;

        // irá funcionar porque tenho certeza que aloquei memória na heap
        free(aux);

        return TRUE;
    }

    return FALSE;
}

/**
* Apenas espero a chave, a memória irei alocar internamente
 sendo assim, tenho controle de quando devo desalocar
*/ 
void push (STACK *stack, int key) {

    // aloca memória no heap
    ELEMENT *element = malloc(sizeof(ELEMENT));
    element->key = key;
    element->next = stack->top;
    stack->top = element;
}

int main () {

        STACK stack;

        startStack(&stack);
        push(&stack, 5);
        push(&stack, 10);
        push(&stack, 15);
        
        printf("%d\n", stackLenght(&stack));

        showElements(&stack);
        pop(&stack);
        showElements(&stack);
        push(&stack, 900);
        showElements(&stack);
}

When compiling with the gcc you will see some compiler warnings like "assignment from incompatible Pointer type" because you defined the struct as ELEMENT and not struct ELEMENT and within the ELEMENT struct itself, you are using struct ELEMENT.

To correct:

typedef struct ELEMENT {
    TYPEKEY key;
    struct ELEMENT *next;
} ELEMENT;

Answer 2

Structures like this stack are called C++ containers or java collections, and in the literature they appear as ADT, abstract data structures. And you have to bring your program closer to that, on the abstract side. I’ll show you an example below.

Overall the container is a set S possibly empty of records X, and each record has a content that usually contains a key k. And so you write all functions in terms of pointers to nodes and nodes in general have only one pointer to the record, which in turn contains the key.

In programs for study often the registration is the only key itself, as a letter or in your case a simple int:

typedef int TYPEKEY;

You did not use a pointer but a key allocated INSIDE the record.

In the first version you were allocating the wrong size in push(). Now it feels right. But understand that when inserting something into the stack or returning you should copy the data into the stack and when removing you should return a copy of them.

The problem is that the stack user can pass multiple times the same record, or pass a key to key from a pointer that came from I don’t know where. If you put that in the pile a pop() will later cancel your program. Or a restart() or delete(). There can be no hands loose by the program referring to areas within the stack. And vice versa.

Another point, and what you can see in an answer just above, is that access to the stack elements is done in terms of the key, not in terms of the node itself: the node structure is an internal thing to the stack.

In your case, you make a push() of a TYPEKEY, not of a ELEMENT. And top() returns a pointer to key, not for a knot.

EXAMPLE

I changed your program a little and can compare the functions. First of all the structures

typedef int Key;

typedef struct aux_
{
    Key             key;
    struct aux_*    next;

}   Element;

typedef struct
{
    Element*    top;
    unsigned    size;

}   Stack;

I used the common convention to reserve names with the first letter capitalized for the typedef and although it is not common, I kept in Ode the key and not the pointer to it, which is the most common. size is a practical question: it is good to have an updated counter. it is normal to implement the stack using a vector dynamically allocated and there would also be the value of capacity, and everything would be much faster, using pointers as indexes and not Element*

The functions

int         empty (Stack*);
int         pop   (Stack*);
int         push  (Key*,Stack*);
int         size  (Stack*);
Key*        top   (Stack*); 

These are the names as used in C++, for example. But note that

• there is no void: always returns a status, negative for error, 0 for success, as is common in C.
• push() receives a pointer to Key and not to Element: Element is something internal
• top() returns a pointer to the key, but a pointer to a copy from the registry, and it’s important to understand this: you don’t know what the user will do with the key, and so you have to return a copy, and the API user is responsible --- Owner --- by the pointer and must free the memory when no longer using the record. Several calls to top() followed return pointers to copies of the same record and if the API user releases one will not mock the other. It is important to understand this. See in the example program.

The other functions

Stack*      deleteStack  (Stack*);
int         restartStack (Stack*); // empties
int         showStack    (Stack*,const char*); // list all
Stack*      startStack   (unsigned); // return new

deleteStack() returns NULL. Only to be used in an expression and invalidate the stack pointer itself in the program. See in the example.

• restartStack() it does not need but it can and has been written here in terms of pop() to avoid repeating code
• showStack() is a test function. It does not exist on a normal stack and makes no sense: on a stack you only see one element at a time. I added a parameter, a const char*, to show an optional title, because it is a "hand on the wheel" in the tests.

The sample program

The program creates a stack with a certain number of records, shows, deletes half of them and lists the rest. Then tests the restart(), the delete() and closes. I have not tested much but it can serve.

Here’s the code:

int main(void)
{
    const int tamanho = 10;
    Stack* nova = startStack(tamanho);
    showStack(nova,"teste: pilha vazia ainda...");
    printf("Vai inserir 1..10\n");
    for( int i = 1; i<=tamanho; i+=1) push(&i,nova);
    showStack(nova,"teste: pilha agora");
    printf("Tenta remover metade dos elementos\n");
    Key* p = NULL;
    int n = nova->size/2;
    for ( int i = 0; i<n; i+= 1)
    {
        printf("Vai remover '%d'\n", *(p = top(nova)));
        free(p); // nao vai usar mais
        pop(nova);
    };  // for()
    showStack(nova,"teste: pilha agora:");
    printf("Usando restart() na pilha\n");
    restartStack(nova);
    showStack(nova,"teste: depois do restart()");
    printf("Apagando a pilha\n");
    nova = deleteStack(nova);
    printf("Apagando a pilha\n");
    showStack(nova,"vazia?");
    showStack(nova,NULL);
    return 0;
}

The output of the example

toninho@DSK-2009:~/projects/triangle$ ./build/stan
teste: pilha vazia ainda...
Pilha com 0 elementos


Vai inserir 1..10
teste: pilha agora
Pilha com 10 elementos
10 9 8 7 6 5 4 3 2 1 

Tenta remover metade dos elementos
Vai remover '10'
Vai remover '9'
Vai remover '8'
Vai remover '7'
Vai remover '6'
teste: pilha agora:
Pilha com 5 elementos
5 4 3 2 1 

Usando restart() na pilha
teste: depois do restart()
Pilha com 0 elementos


Apagando a pilha
Apagando a pilha
Pilha nao construida!
Pilha nao construida!

push()

int         push (Key* k, Stack* s)
{
    // cria um elemento e coloca na pilha.
    // retorna o tamanho se ok, ou algo negativo
    if ( s == NULL ) return -1;
    if ( k == NULL ) return -2;
    Element* el = (Element*) malloc(sizeof(Element));
    if ( el == NULL ) return -3;
    el->key = *k; // shallow copy here!!
    el->next = s->top; // new at the TOP
    s->top = el;
    s->size += 1;
    return s->size;
}

Just note that an element is created and the key is copied inside. So if the API user releases the pointer then it will not destroy the stack...

re-start()

int         restartStack(Stack* s)
{
    if ( s == NULL ) return -1;
    while ( s->size > 0 ) pop(s);
    return 0;
}

Note that it is simpler to write Restart() from pop(), besides being one less place to test :)

The whole program

#include <stdio.h>
#include <malloc.h>

typedef int Key;

typedef struct aux_
{
    Key             key;
    struct aux_*    next;

}   Element;

typedef struct
{
    Element*    top;
    unsigned    size;

}   Stack;
// classic
int         empty (Stack*);
int         pop   (Stack*);
int         push  (Key*,Stack*);
int         size  (Stack*);
Key*        top   (Stack*); 
// support
Stack*      deleteStack  (Stack*);
int         restartStack (Stack*); // empties
int         showStack    (Stack*,const char*); // list all
Stack*      startStack   (unsigned); // return new

int main(void)
{
    const int tamanho = 10;
    Stack* nova = startStack(tamanho);
    showStack(nova,"teste: pilha vazia ainda...");
    printf("Vai inserir 1..10\n");
    for( int i = 1; i<=tamanho; i+=1) push(&i,nova);
    showStack(nova,"teste: pilha agora");
    printf("Tenta remover metade dos elementos\n");
    Key* p = NULL;
    int n = nova->size/2;
    for ( int i = 0; i<n; i+= 1)
    {
        printf("Vai remover '%d'\n", *(p = top(nova)));
        free(p); // nao vai usar mais
        pop(nova);
    };  // for()
    showStack(nova,"teste: pilha agora:");
    printf("Usando restart() na pilha\n");
    restartStack(nova);
    showStack(nova,"teste: depois do restart()");
    printf("Apagando a pilha\n");
    nova = deleteStack(nova);
    printf("Apagando a pilha\n");
    showStack(nova,"vazia?");
    showStack(nova,NULL);
    return 0;
}

int         empty (Stack* S)
{
    return S->size == 0;
}

int         pop (Stack* S)
{
    if ( S == NULL ) return -1;
    if ( empty(S) )  return -2;
    Element* to_delete = S->top;
    S->top = S->top->next;
    S->size -= 1;
    free(to_delete);
    return S->size;
}

int         push (Key* k, Stack* s)
{
    // cria um elemento e coloca na pilha.
    // retorna o tamanho se ok, ou algo negativo
    if ( s == NULL ) return -1;
    if ( k == NULL ) return -2;
    Element* el = (Element*) malloc(sizeof(Element));
    if ( el == NULL ) return -3;
    el->key = *k; // shallow copy here!!
    el->next = s->top; // new at the TOP
    s->top = el;
    s->size += 1;
    return s->size;
}

int         size(Stack* s)
{
    if ( s == NULL ) return -1;
    return s->size;
}

Key*        top(Stack* s)
{
    if ( s == NULL ) return NULL;
    Key* k = (Key*) malloc(sizeof(k));
    *k = s->top->key;
    return k;
}

Stack*      deleteStack(Stack* s)
{
    if ( s == NULL ) return NULL;
    while ( s->size > 0 ) pop(s);
    return NULL;
}

int         restartStack(Stack* s)
{
    if ( s == NULL ) return -1;
    while ( s->size > 0 ) pop(s);
    return 0;
}


int         showStack (Stack* s, const char* msg)
{   
    // prints stack nodes along with optional message
    if ( s == NULL )
    {
        printf("Pilha nao construida!\n");
        return -1;
    };
    if ( msg != NULL )
    {
        printf("%s\n", msg);
    }
    printf("Pilha com %d elementos\n", s->size);
    Element* p = s->top;
    while ( p != NULL )
    {
        printf( "%d ", p->key );
        p = p->next;
    }
    printf("\n\n");
    return s->size;
}

Stack*      startStack (unsigned sz)
{
    const unsigned dflt = 1000;  // default size
    Stack*      stack = (Stack*) malloc(sizeof(Stack));
    if ( stack == NULL ) return NULL;
    stack->top = NULL;
    stack->size = 0;
    return stack;
}