What Is Wrong in the "free" Function for this Generic Stack Implementation in C?

Question

I have the following implementation of a generic stack, i.e, the stack can store user-specified data.

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

typedef struct{
    void *elems;
    int elemSize;
    int allocLength;
    int logLength;
    void (*freefnc) ( void* );
} Stack;

void stackNew( Stack* s, int elemSize, void (*freefnc) (void*) ){
    s->allocLength = 4;
    s->logLength = 0;
    s->elemSize = elemSize;
    s->elems = malloc( s->allocLength * elemSize );
    s->freefnc = freefnc;
}

void stackDispose( Stack* s ){
    if( s->freefnc ){
        int i;
        for( i = 0; i < s->logLength; i++ ){
            s->freefnc( ( char* ) s->elems + i * s->elemSize   );
        }
    }
    free( s->elems );
}

void stackGrow( Stack* s){
    s->allocLength *= 2;
    s->elems = realloc( s->elems, s->allocLength * s->elemSize );
    assert( s->elems != NULL );
}

void stackPush( Stack* s, void* elemAddr ){
    if( s->allocLength == s->logLength ){
        stackGrow( s );
    }
    void *target = (char*) s->elems + s->logLength * s->elemSize;
    memcpy( target, elemAddr, s->elemSize );
    s->logLength++;
}

void* stackPop( Stack* s ){
    void* source = (char*) s->elems + ( s->logLength - 1 ) * s->elemSize;
    void* elemAddr = malloc( s->elemSize );
    assert( elemAddr != NULL );
    memcpy( elemAddr, source, s->elemSize );
    s->logLength--;
    return elemAddr;
}

void freeInt( void* p ){
    char* q = p;
    free( q );
}

void stackPrint( Stack* s ){
    printf( "elemSize: %d\n", s->elemSize );
    printf( "allocLength: %d\n", s->allocLength );
    printf( "logLength: %d\n", s->logLength );

    int i;
    for( i=0; i < s->logLength; i++ ){
        printf("%d\n", *( (char*) s->elems + i * s->elemSize ) );
    }
}

int main(){
    Stack st;
    stackNew( &st, 4, &freeInt );
    int elem = 5;
    int elem2 = 9;
    stackPush( &st, &elem );
    stackPush( &st, &elem2);
    stackPrint( &st );
    stackDispose( &st );
}

However, I got the output below when running the code.

elemSize: 4
allocLength: 4
logLength: 2
5
9
*** Error in `./a.out': free(): invalid pointer: 0x00000000014b9014 ***
Aborted

It seems something wrong in the "freefnc" in the code but I am not sure. Can anybody explain what is wrong in the code and how to fix it?

P.S. The code is adopted from another SO post Generic Stacks in C. I am trying to understand how the code works. It will be highly appreciated if anybody can give a working version of the code with test cases.

Thanks a lot in advance!

Answer 1

Let's be clear on how your stack is stored in memory: You have a Stack object (whose memory isn't actually managed by the stack functions but by whatever "owns" the stack), and a single big memory block holding all of the elements (and some empty space).

In ASCII art form:

+-----------------------+
| elems | ............. |    <- Stack object
+---|-------------------+
    |
    V
    +---------------------------------+
    | elem1 | elem2 | unused | unused |    <- Data array
    +---------------------------------+

elems in the Stack object holds a pointer to the start of the data array.

To destroy this stack, all you need to do is destroy the data array (which was malloc-ed, so use free), and the Stack object (which is a local variable, so it's destroyed when the function that contains it returns).

There is no need to free all the individual elements. They will be destroyed as part of the data array. Calling free on the individual elements is wrong; if you try to free the first element you end up freeing the whole array, and if you try to free the other elements you end up causing undefined behaviour.

---

You might be wondering why freefnc is useful, then. freefnc is useful if the stack elements are themselves pointers (or structs that contain pointers). Say, if you were storing strings allocated with malloc:

+-----------------------+
| elems | ............. |    <- Stack object
+---|-------------------+
    |
    V
    +---------------------------------+
    | elem1 | elem2 | unused | unused |    <- Data array
    +---|-------|---------------------+
        |       |
        |       V
        |       +------------+
        |       |w|o|r|l|d|\0|    <- second string
        |       +------------+       (allocated with malloc)
        V
        +------------+
        |H|e|l|l|o|\0|    <- first string (allocated with malloc)
        +------------+

In that case, you'd want to set up freefnc to free the strings themselves (but still not the actual stack elements). Of course, you currently don't have this situation, since you're just storing ints in your stack.