realloc을 내가 사용하고 tsearch

Question

에 의해 생성 된 트리를 엉망으로되어있는 tsearch/tfind/twalk 기본적으로 정렬하고 문서에 고유 한 단어를 계산하는 프로그램에서 search.h 라이브러리 기능을합니다. 이후 문서에 얼마나 많은 단어가 있는지 모르겠으므로 malloc을 사용하여 처음에는 모든 단어를 담고있는 배열에 일정량의 메모리를 할당 한 다음 realloc을 사용하여 그것을 채운다면 더 크게 만듭니다. . 그러나 realloc은 tsearch에 의해 관리되는 트리를 손상시키고 명백히 정크 노드를 반환하기 시작하거나 노드의 내용이 손상됩니다.

구조체 정의 :

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

다음은 초기 할당량을 실행 한 결과입니다. on of 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를 사용해 본 적이 없습니다.

지금, 나는 해당 문서를 보면 :

- 기능 : 무효 * tsearch (const를 무효 * 키 무효 ** rootp, comparison_fn_t 비교 예)

나무는 일치를 포함하지 않는 경우 항목 키 값이 트리에 추가됩니다. tsearch는 는 객체의 복사본 키가 가리키는하지 않습니다 (어떻게 크기를 알 수 있기 때문에 수). 대신 은이 개체에 참조 번호을 추가합니다. 즉 트리 데이터 구조가 사용되는 동안 개체를 사용할 수 있어야합니다.

당신은 당신의 트리 노드 포인터 메모리를 이동해야 realloc을 때마다 무효로합니다. 또한, tsearch가 NULL을 반환 할 것으로 예상하지 않습니다.

가장 쉬운 해결책은 대신 배열에 버퍼링의 단어 요소를 할당하는 것입니다. 이로 인해 속도 위반이 발생할 수 있습니다. 당신이 블록으로 배열 된 단어 항목을해야하는 경우

, 왜 그냥 경우 realloc을 (항목, ...)! = 항목 모든 요소 포인터를 루트를 twalk 및 업데이트? 편집 : 설명에 따라 거기 UB로 실행할 수 있습니다. 그러나 일반 또는 MT 사건에 대해 이야기하는 것이 100 % 명확하지 않습니다.