c - 为什么释放 trie 中的字符串会导致 malloc 错误？

Question

我需要帮助来理解从 malloc 获得的调试消息。我编写了一个函数，通过递归遍历 trie 上的该字符串并释放未被另一个字符串使用的所有内容，从 trie 中删除指定的字符串。这涉及到下到最后一个节点并释放它，然后返回堆栈并检查每个级别以查看该级别是否也未被其他字符串使用，如果是，则释放它们。一旦它到达第一个被其他东西使用的，它就会停止。

当我只删除一个字符串时，该函数似乎工作正常，但当我删除第二个字符串时，我开始遇到问题。到目前为止，这是我的程序的完整代码(请注意，其中一些行用于测试/调试目的，而不是程序的组成部分):

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

struct node {
    char chr;
    bool end;
    struct node *children[128];
};

void add( struct node *, char * );
void del( struct node *, char * );
bool isMember( struct node *, char * );

bool recursiveDel( struct node *, char * );
// del is really just a dummy function that calls recursiveDel.

int main( int argc, char **argv ){
    struct node *trie = (struct node *) malloc( sizeof( struct node ) );
    for( int i = 1; i < argc; i++ ){
        add( trie, argv[i] );
    }
    del( trie, argv[1] );
    del( trie, argv[2] );
    for( int i = 1; i < argc; i++ ){
        printf( "%d\n", isMember( trie, argv[i] ) );
    }
    return 0;
}

void add( struct node *trie, char *str ){
    int i = 0;
    while( str[i] ){
        // Check/goto next node
        // If NULL, create next node
        if( trie->children[str[i]] == NULL )
            trie->children[str[i]] = (struct node *) malloc( sizeof( struct node ) );
        trie = trie->children[str[i++]];
    }
    trie->end = true;
}

void del( struct node *trie, char *str ){
    if( isMember( trie, str ) ){
        recursiveDel( trie, str );
    }
}

bool isMember( struct node *trie, char *str ){
    int i = 0;
    struct node *cur = trie;
    while( str[i] ){
        if( trie->children[str[i]] == NULL ) return false;
        else trie = trie->children[str[i++]];
    }
    return trie->end;
}

// Features of this function:
// When it gets to the leaf, it deletes that node and then starts going back up the call stack
// Each call passes a Boolean value back up the call stack.
// This boolean value indicates whether or not the node was deleted.
// If the value returned from the lower node is true, then that means check the next node up to see if it should be deleted.
// If false do nothing, because there are other strings using this node.
bool recursiveDel( struct node *trie, char *str ){
    printf( "%p, %d, %s\n", trie, trie->end, str );
    if( trie->end ){
        free( trie );
        return true;
    }
    bool deleted = recursiveDel( trie->children[str[0]], str+1 );
    if( deleted ){
        int used = 0;
        // Loop checks to see if the node
        // is used by any other strings.
        for( int i = 0; i < 128; i++ ){
            if( trie->children[i] ){
                used++;
                break;
            }
        }
        if( used <= 1 ){
            free( trie );
            return true;
        }
    }
    return false;
}

问题似乎出现在这个 block 中，我试图释放字符串的终止节点:

    if( trie->end ){
        free( trie );
        return true;
    }

我收到一条消息说该节点不存在，因此无法释放...

bash-3.2$ ./trie hello world
0x7fd370802000, 0, hello
0x7fd370800600, 0, ello
0x7fd370802600, 0, llo
0x7fd370802c00, 0, lo
0x7fd370803200, 0, o
0x7fd370803800, 1,
0x7fd370802000, 0, world
0x7fd370803e00, 0, orld
0x7fd370804400, 0, rld
0x7fd370804a00, 0, ld
0x7fd370805000, 0, d
0x7fd370805600, 1,
trie(43216,0x7fff7818e000) malloc: *** error for object 0x7fd370802000: pointer being freed was not allocated
*** set a breakpoint in malloc_error_break to debug
Abort trap: 6
bash-3.2$

似乎是这样的情况，当我尝试删除第二个字符串时，它会按预期转到最后一个节点，但它不会返回堆栈，而是继续并尝试释放之后的下一个节点，显然它不能这样做，因为这是一个叶节点。

这似乎是未定义的行为，但与此同时，程序会以一种非常可预测的方式失败——第一次字符串删除总是成功，而第二次字符串删除总是不成功。我对此一头雾水。

此外，malloc 失败时给出的地址似乎有点不对劲。最后几个地址都相差0x600，但是这个地址和最后一个地址相差0xa00。我知道堆内存分配是不可预测的，但我只是想指出这一点。

比这更奇怪的是 malloc 给出的地址与最后打印的地址不同，尽管失败的 free 操作紧跟在最后一个之后打印。这似乎表明编译器正在 printf 行和 if(trie->end) free(trie) 部分之间插入一个指针前进操作。常识表明这是荒谬的，但我不知道还有什么其他解释。

Answer 1

代码的相关部分:

int main( int argc, char **argv ){
    struct node *trie = (struct node *) malloc( sizeof( struct node ) );
    for( int i = 1; i < argc; i++ ){
        add( trie, argv[i] );
    }
    …
}

void add( struct node *trie, char *str ){
    int i = 0;
    while( str[i] ){
        if( trie->children[str[i]] == NULL )
//          ^^^^^^^^^^^^^^^^^^^^^^

您正在分配一个struct node，然后访问它的.children[...] 指针而不初始化它。未定义的行为。

您需要在分配后初始化您的节点。