c - Realloc 弄乱了 tsearch 创建的树

Question

我在一个程序中使用 search.h 库中的 tsearch/tfind/twalk 函数，该程序基本上对文档中的唯一单词进行排序和计数。由于我不知道文档中有多少个单词，因此我首先使用 malloc 为保存所有单词的数组分配一定量的内存，然后使用 realloc 使其更大(如果我已填满) 。然而，realloc 显然破坏了 tsearch 维护的树，并且 twalk 开始返回垃圾节点或者节点的内容被破坏。

结构体定义:

struct word {
    char word[MAX_MTEXT];
    int occur;
};

struct mymsg {
    long mtype;
    char mtext[MAX_MTEXT];
    int occur;
};

下面的代码是整个子进程代码，还有一些其他处理从消息队列获取单词的内容:

f = 1;
i = 0;
words_entered = 0;
entry = (struct word *) malloc(words_allocated * sizeof(struct word));
while(f) {
    if (msgrcv(m_key, &mymsg, sizeof(struct mymsg), (long) getpid(), 0) == -1) {
        perror("recieve");
        exit(EXIT_FAILURE);
    }
    //printf("%s recieved\n",mymsg.mtext);
    if (mymsg.mtext[0] == '\0') {
        //printf("term recv\n");
        f = 0;
    }
    else {
            //printf("mtext = %s\n",mymsg.mtext);
        memcpy(&entry[i].word,&mymsg.mtext,MAX_MTEXT);
        //printf("entry = %s\n",entry[i].word);
        entry[i].occur = 1;
        //printf("%s entered\n",entry[i].word);
        words_entered++;
        if (words_entered == words_allocated) {
            printf("About to realloc\n\n");
            twalk (root, action);
            words_allocated = words_allocated *2;
            entry = (struct word *) realloc(entry,(size_t) words_allocated * sizeof(struct word));
            printf("After realloc\n\n");
            twalk (root, action);
        }
        ptr = tfind(&entry[i],&root,compare);
        if (ptr == NULL) {
            //printf("null\n");
            ptr = tsearch(&entry[i],&root,compare);
            //printf("%s added to tree\n",(*ptr)->word);
        }
        else {
            (*ptr)->occur++;
        }
        i++;
        //printf("check\n");
    }
}
twalk (root, action);
mymsg.mtype = ret_id;
mymsg.mtext[0] = '\0';
mymsg.occur = 0;
if (msgsnd(m_key, &mymsg, sizeof(mymsg)-sizeof(long), 0) == -1) {
    perror("send");
    exit(EXIT_FAILURE);
}
exit(EXIT_SUCCESS);

这是 walk 调用的操作代码:

void action(const void *nodep, VISIT value, int level) {
    struct word *w = *((struct word **) nodep);
    struct mymsg mymsg;
    switch (value) {
    case leaf:
    case postorder:
        printf("%s: %i, level %i\n",w->word, w->occur, level);
        mymsg.mtype = ret_id;
        strcpy(mymsg.mtext,w->word);
        //printf("%s vs %s\n",w->word,mymsg.mtext);
        mymsg.occur = w->occur;
        if (msgsnd(m_key, &mymsg, sizeof(mymsg)-sizeof(long), 0) == -1) {
            perror("send");
            exit(EXIT_FAILURE);
        }
        break;
    default:
        break;
    }
    return;
}

这是运行初始分配 5 的结果:

About to realloc

each: 1, level 1
is: 1, level 0
therefore: 1, level 2
translator: 1, level 1

After realloc

Ð3³: 1, level 1
is: 1, level 0
therefore: 1, level 2
translator: 1, level 1

About to realloc

for: 1, level 2
his: 1, level 1
$p  : 158343352, level 2
is: 1, level 0
own: 1, level 3
portion;: 1, level 2
responsible: 1, level 3
therefore: 1, level 1
p p rlator: 1, level 2

After realloc

for: 1, level 2
his: 1, level 1
$p  : 158343352, level 2
is: 1, level 0
own: 1, level 3
portion;: 1, level 2
responsible: 1, level 3
therefore: 1, level 1
p p rlator: 1, level 2

Answer 1

免责声明:我以前从未使用过 GNU C 的树搜索功能。

现在，如果我查看相应的文档:

—函数:void * tsearch(const void *key, void **rootp, Comparison_fn_t compar)

如果树不包含匹配的条目，则键值将添加到树中。 tsearch 不会不复制 key 指向的对象(因为大小未知，怎么可能呢)。相反，它添加一个引用到该对象，这意味着只要使用树数据结构，该对象就必须可用。

每次 realloc 需要移动内存时，都会使树节点指针无效。另外，您预计 tsearch 不会返回 NULL。

最简单的解决方案是只分配单个字元素，而不是将它们缓冲在数组中。这可能会造成一些速度损失。

如果您确实需要将单词条目排列在 block 中，那么为什么不直接遍历根并在 realloc(entry, ...) !=entry 的情况下更新所有元素指针呢？编辑:根据描述，您可能会在那里遇到 UB。但是，并不能 100% 清楚他们谈论的是一般案例还是 MT 案例。