我在一个程序中使用了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
最佳答案
免责声明：我以前从未使用过树搜索功能来使用GNUC。
现在，如果我看一下相应的文档：
—函数：void * tsearch（常量void * key，void ** rootp，comparison_fn_t比较）
如果树不包含匹配的条目，则将键值添加到树中。 tsearch不会复制key指向的对象的副本（由于大小未知，怎么办）。相反，它添加了对此对象的引用，这意味着只要使用树数据结构，该对象就必须可用。
每次重新分配需要移动内存时，您都会使树节点指针无效。另外，您不希望tsearch返回NULL。
最简单的解决方案是只分配单个单词元素，而不是将它们缓冲在数组中。这可能会施加一定的速度损失。
如果确实需要将单词条目按块排列，那么如果realloc（entry，...）！= entry，为什么不只是遍历根并更新所有元素指针呢？编辑：根据说明，您可能会在那儿碰到UB。但是，目前尚不清楚他们谈论的是普通案件还是MT案件。