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

此代碼對於步行所謂的動作：

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's。現在

，如果我看相應的文檔：

- 功能：void *的TSEARCH（常量無效*鍵，無效** rootp，comparison_fn_t COMPAR）

如果樹不包含匹配輸入鍵值將被添加到樹。 tsearch確實沒有將key指向的對象拷貝到（它怎麼可能，因爲大小是未知的）。相反，爲該對象添加了參考，這意味着只要使用樹數據結構，該對象就必須可用。

每次realloc需要移動內存時，都會使樹節點指針無效。另外，你不會預期tsearch返回NULL。

最簡單的解決方案是隻分配單個單詞元素，而不是將它們緩存在數組中。這可能會造成一些速度損失。

如果您確實需要將單詞條目排列成塊，那麼爲什麼不只是纏繞根目錄並更新所有元素指針（如果realloc（entry，...）！= entry？編輯：你可能遇到UB那裏，根據描述。但是，如果他們談論一般或MT案例，並不是100％清楚。