C - Who is responsible for memory allocation when memory is allocated inside a function?

user_14959891 0
Viewed 81

I am trying to up my C-game. I am currently using the book "Mastering Algorithms with C" by Kyle Loudon. Currently I am looking into data structures, specifically Stacks. The code example I will use here is not straight from the book but is slightly modified for readibility. I have looked online but have not found any answer to my questions.

A common rule I often hear about in C-programming is "whoever allocated memory is responsible for freeing it". This seems like a simple rule to follow. However, when I tried to create a function to push a new stack element on top of the stack, I got a bit unsure.

The code

StackElmt is the element to reside in a Stack. Before any operation can be performed on a Stack, stack_init needs to be run. After that stack_push pushes new elements on the top of the stack and stack_pop pops them from the stack.

typedef struct StackElmt_ {
    void *data;
    struct StackElmt_ *next;
}StackElmt;

typedef struct Stack_
{
    int size;
    StackElmt *top;
}Stack;

void stack_init(Stack *stack)
{
    stack->size = 0;
    stack->top = NULL;
}

void stack_push(Stack *stack, void *data)
{

    StackElmt *element = calloc(1, sizeof(StackElmt));
    element->data = data;
    element->next = stack->top;
    stack->top = element;
    stack->size++;
}

void stack_pop(Stack *stack, StackElmt **element)
{
    *element = stack->top;
    stack->top = (*element)->next;
    stack->size--;
}

Problem description

I find it very odd that stack_push allocates memory to the heap but the stack_pop does not free it. I feel like if stack_push allocates the memory, memory management becomes the responsibility of the developer of these Stack functions and not the user.

Instead, I would like to do something like this:

void stack_push(Stack *stack, StackElmt *element, void *data)
{
    element->data = data;
    element->next = stack->top;
    stack->top = element;
    stack->size++;
}

where a pointer to a StackElmt is input and users can choose themselves how to allocate it.

Summary

My questions are:

  1. Is the code where memory is allocated in stack_push() but not freed in stack_pop() considered good design? Would having a clear comment in stack_pop() that the user is responsible for the StackElmt memory make the design better?
  2. In the book, there is also a function called "destroy_stack" that destroys the stack. In it, "stack_pop" and a user-defined function pointed to by a pointer (recommended to be free) are run for every element in the Stack. Does this "destroy"-function make it clearer from a user perspective who is responsible for memory management?
  3. Is it better to have memory allocation completely by the user (see my modified stack_push) or completelt by the program?

Thank you all in advance!

memory-management c
2 Answers

stack_pop() shouldn't return the StackElmt, it should return the data in the element. This mirrors the action of stack_push().

Then it can free the element.

void stack_pop(Stack *stack, void **data)
{
    if (!stack->top) {
        // report stack underflow error somehow
        return;
    }
    *data = stack->top->data;
    StackElmt *temp = stack->top;
    stack->top = temp->next;
    stack->size--;
    free(temp);
}
user_14918950

The function stack_pop should not expose the node type but instead return the data. With this approach the node can be freed in the function. We should also make sure that the stack is not empty before popping an element. Here is a modified version:

void stack_pop(Stack *stack, void **data)
{
    StackElmt *oldTop;

    assert(stack != NULL);
    assert(stack->size > 0);

    *data = stack->top->data;
    oldTop = stack->top;
    stack->top = stack->top->next;
    free(oldTop);
    stack->size--;
}

You probably also want to define a stack_size function so the client can check if the stack is empty or not before calling stack_pop.

user_3371490
Related