c - C 中此通用堆栈实现的 "free"函数有什么问题？

Question

我有以下通用堆栈的实现，即堆栈可以存储用户指定的数据。

#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 );
}

但是，我在运行代码时得到了以下输出。

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

代码中的“freefnc”似乎有问题，但我不确定。任何人都可以解释代码中的错误以及如何修复它吗？

附言该代码是从另一个 SO 帖子中采用的 Generic Stacks in C .我试图了解代码的工作原理。如果有人可以提供带有测试用例的代码的工作版本，我们将不胜感激。

提前致谢!

Answer 1

让我们弄清楚堆栈是如何存储在内存中的:您有一个 Stack 对象(其内存实际上并不由 stack 函数管理，而是由任何“拥有“堆栈”)和一个包含所有元素(和一些空白空间)的大内存块。

以 ASCII 艺术形式:

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

Stack 对象中的

elems 包含指向数据数组开头的指针。

要销毁这个堆栈，您需要做的就是销毁数据数组(它是 malloc-ed，所以使用 free)和 Stack 对象(它是局部变量，因此当包含它的函数返回时它会被销毁)。

无需释放所有单个元素。它们将作为数据数组的一部分被销毁。对单个元素调用 free 是错误的；如果您尝试释放第一个元素，您最终会释放整个数组，如果您尝试释放其他元​​素，您最终会导致未定义的行为。

---

那么您可能想知道为什么 freefnc 很有用。如果堆栈元素本身是指针(或包含指针的结构)，则 freefnc 很有用。比方说，如果您要存储使用 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)
        +------------+

在这种情况下，您需要设置freefnc 来释放 字符串本身(但仍然不是实际的堆栈元素)。当然，您目前没有这种情况，因为您只是将 int 存储在堆栈中。