CODEWITHSUNDEEP
cstackfree
Liu
Liu

Reputation: 433

Free the stack implemented in C

I implement a stack and its functions in C. Now after all the functions were called, I wanted to free the stack.

My question is should I free the base pointer of stack "st" first or just directly free the stack "st"? Both seems work in my code.

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

#define init_size 10
#define increment 1

typedef struct sqStack
{
    int* top;
    int* base;
    int stack_size;
}sqStack;

int init_stack(sqStack* sq)
{
    if(sq->base==NULL)
    {
       sq->base = (int*)malloc(init_size*sizeof(int));
    }
    if(sq->base==NULL) exit(-1);
    sq->stack_size=init_size;
    sq->top=sq->base;
    return 1;
}
int push(sqStack* sq, int e)
{
    if(sq==NULL) exit(-1);

    if(sq->top-sq->base==sq->stack_size-1)//pointer top reaches the top of the stack
    {
        int* q = (int*)realloc(sq->base,(sq->stack_size+increment)*sizeof(int));
        if(q==NULL)  exit(-1);
            sq->base=q;
        sq->top=sq->base+sq->stack_size-1;
            sq->stack_size += increment;

    }
    *sq->top++=e;
    return 1;
}
int pop(sqStack* sq,int* e)
{
    if(sq==NULL) exit(-1);
    if(sq->base==sq->top)  exit(-1);
    sq->top--;
    *e=*sq->top;
    sq->stack_size--;
    return *e;
}
int top(sqStack* sq,int* e)
{
    if(sq==NULL) exit(-1);
    if(sq->base==sq->top)  exit(-1);
    *e=*(sq->top-1);
    return *e;
}
int empty(sqStack* sq)
{
    if(sq->base==sq->top) return 1;
    else return 0;
}

int main() {
    sqStack* st= (sqStack*)calloc(1,sizeof(sqStack))  ;
    int e;
    init_stack(st);
    for(int i=0;i<12;i++)
    {
        push(st,i+1);

    }
    for(int i=0;i<12;i++)
    {
        printf("%d\n",top(st,&e));
        printf("%d\n",pop(st,&e));
    }
    free(st->base);
    free(st);
    return 0;
}

The result is: 12 12 11 11 10 10 9 9 8 8 7 7 6 6 5 5 4 4 3 3 2 2 1 1 each number locates on a single line.

Upvotes: 2

Views: 580

Answers (3)

thb
thb

Reputation: 14454

Your code is correct. The reverse sequence might work but, if it did, this would be accidental.

The reason is that free(st) deallocates the memory in which the object *st is stored. The pointer st->base is stored in a part of this very memory. Suppose that some other task, or thread, acquired the same memory as soon as it had been freed. What then? That is, what would happen when free(st->base) were eventually called?

Answer: what would happen is undefined.

Even if it were still possible to retrieve an address from st->base (and it might not be possible), that address might have been overwritten by arbitrary data, in which case free(st->base)—interpreting the arbitrary data as an address—would ask the operating system to deallocate ... well, you don't know what it would ask the operating system to deallocate. One should hardly expect good results in this case.

You have done well. Your sequencing is correct.

ADDITIONAL CONSIDERATIONS

For security, modern operating system kernels sometimes automatically overwrite deallocated memory with null or random data. Also, they sometimes revoke a program's access to the hardware page via which deallocated memory had been (virtually) addressed, or tighten the bounds within which access is allowed. Some of these are more likely than others but I have seen at least two of the three occur. The point is that the kernel is free to do such things immediately, sooner, later or not at all, as the kernel prefers, according to the kernel's latest memory management and security algorithms, because your program is not supposed to care what happens to deallocated memory after the program has deallocated it.

Upvotes: 1

John Bollinger
John Bollinger

Reputation: 180998

Every allocation should be paired with a corresponding free, so in your case that means freeing both st->base and st (in that order). But your program performs its frees only immediately prior to termination, and anything it does not free will be reclaimed by the OS when the program does terminate. A memory usage analyzer such as Valgrind could detect the difference for you, but in practice it does not matter.

Upvotes: 1

dbush
dbush

Reputation: 224387

What you have is correct in terms of malloc and free.

You should only pass to free what was returned from malloc or realloc. You allocate space for the struct and for the stack and you free both, so you're not leaking any memory.

You don't want to free(st) first because after doing so the memory that st was pointing to is no longer valid and you can't subsequently free(st->base) safely. Also, because free knows nothing about the contents of the given memory, it doesn't attempt to free any pointers that the memory might contain. So just calling free(st) leaks the memory in st->base.

Upvotes: 3

Related Questions