Valgrindの空きメモリが不足しています。

Question

空きがなく、メモリリークが発生します。ここに私のコードは次のとおりです。

/*============================================================================= 
    | 
    | Assignment: Test #2 

    |  Class: Programming Basics 
    |   Date: December 20th, 2017 
    | 
    |  Language: GNU C (using gcc), OS: Arch Linux x86_64) 
    |  Version: 0.0 
    | To Compile: gcc -Wall -xc -g -std=c99 kontrolinis2.c -o kontrolinis_2 
    | 
    +----------------------------------------------------------------------------- 
    | 
    | Description: The program which gets the input number, which indicates how 
    |    many words there will be, then prompts the user to enter 
    |    those words, and then displays a histogram in descending 
    |    order by times the word is repeated. The words with the 
    |    same duplicate count are sorted in lexicographical order 
    | 
    +===========================================================================*/ 

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

#include "dbg.h" 
#include "lib_riddle.h" 

#define MAX_STRING 50 

// Frequency structure. Contains the word and the times 
// it is repeated 
typedef struct Freq { 
    char* word; 
    int times; 
} Freq; 

// Histogram structure. Contains the list of frequencies (struct) 
// and the size of the list. 
typedef struct Histogram { 
    Freq** freqs; 
    int size; 
} Histogram; 

// sort the portion of the given array of frequency structs 
// in lexicographically reverse order (from z to a) by Freq->word attribute. 
// 
// ::params: target - array continaing frequency structs 
// ::params: first - first index of the portion of the array 
// ::params: last - last index of the portion of the array 
// ::return: Array of frequency structs (portion of which is 
// sorted in lexicographically reverse order) 
Freq** sort_rlexicographical(Freq** target, int first, int last); 

// sort the frequency structs array by their Freq->times 
// attribute, using quicksort 
// 
// ::params: target - the frequency array 
// ::params: first - first index of the array 
// ::params: first - last index of the array 
// ::return: Sorted array of frequency structs 
Freq** quicksort_freqs(Freq** target, int first, int last); 

// print Frequency array in reverse order, which displays 
// the data as in historgram (from bigger to smaller) 
// 
// ::params: target - the frequency array 
// ::params: size - size of the array 
void print_reverse(Freq** target, int size); 



int main(int argc, char* argv[]) 
{ 

    // get number from the user 
    int size = get_pos_num("Please enter a number of words > ", 0); 

    Histogram* histogram = malloc(sizeof(Histogram)); 
    histogram->freqs = malloc(size * sizeof(Freq*)); 
    histogram->size = 0; 

    char** words = (char**)malloc(size * sizeof(char*)); 
    for (int i = 0; i < size; i++) { 
     words[i] = (char*)malloc(MAX_STRING * sizeof(char)); 
    } 

    // get words from the user 
    for (int i = 0; i < size; i++) { 
     words[i] = get_word("Enter word > ", words[i]); 
    } 

    int duplicates; 
    int is_duplicate; 
    int hist_size = 0; 

    // initialize the array of duplicates 
    char** duplicated = (char**)malloc(size * sizeof(char*)); 
    for (int i = 0; i < size; i++) { 
     duplicated[i] = (char*)calloc(MAX_STRING+1, sizeof(char)); 
     /*duplicated[i] = (char*)malloc(MAX_STRING);*/ 
     /*duplicated[i] = (char*)calloc(MAX_STRING + 1, sizeof(char));*/ 
    } 

    // count the duplicates of each word and add the word with its duplicate count 
    // to the frequency array, and then - to the histogram struct. Each word is 
    // writtern once, without duplication. 
    for (int i = 0; i < size; i++) { 
     is_duplicate = 0; 

     // if the word is already added to the duplicate list, 
     // it means that its duplicates are already counted, 
     // so the loop iteration is skipped 
     for (int k = 0; k < size; k++) { 
      if (strcmp(duplicated[k], words[i]) == 0) { 
       is_duplicate = 1; 
      } 
     } 

     // skipping the loop iteration 
     if (is_duplicate) { 
      continue; 
     } 

     // found the word about which we are not yet sure 
     // whether it has any duplicates. 
     duplicates = 1; 
     Freq* freq = malloc(sizeof(Freq)); 
     freq->word = (char*)malloc(sizeof(MAX_STRING * sizeof(char))); 
     freq->word = words[i]; 
     // searching for the duplicates 
     for (int j = i + 1; j < size; j++) { 
      if (strcmp(words[i], words[j]) == 0) { 
       // in case of a duplicate 
       // put word in duplicates array 
       // and increase its duplicates count 
       duplicated[i] = words[i]; 
       duplicates++; 
      } 
     } 
     freq->times = duplicates; 
     histogram->freqs[histogram->size++] = freq; 
     hist_size++; 
    } 

    debug("Frequency table:"); 
    for (int i = 0; i < hist_size; i++) { 
     debug("%s %d", histogram->freqs[i]->word, histogram->freqs[i]->times); 
    } 
    debug("-----------------------"); 

    histogram->freqs = quicksort_freqs(histogram->freqs, 0, hist_size - 1); 

    debug("Sorted frequency table:"); 
    for (int i = hist_size - 1; i >= 0; i--) { 
     debug("%s %d", histogram->freqs[i]->word, histogram->freqs[i]->times); 
    } 
    debug("-----------------------"); 

    int max_count = histogram->freqs[hist_size - 1]->times; 
    int index = hist_size - 1; 
    int index_max; 

    // partition the frequency array by the same duplicate times, and 
    // pass the partitioned array to reverse lexicographical sort 
    // on the go. 
    for (int i = max_count; i > 0 && index >= 0; i--) { 
     index_max = index; 
     if (histogram->freqs[index]->times == i) { 
      while (index - 1 >= 0 && histogram->freqs[index - 1]->times == i) { 
       index--; 
      } 
      if (index != index_max) { 
       histogram->freqs = sort_rlexicographical(
        histogram->freqs, index, index_max); 
      } 
      index--; 
     } 
    } 

    printf("\nLexicographically sorted frequency table:\n"); 
    print_reverse(histogram->freqs, hist_size); 




    for (int i = 0; i < size; i++) { 
     free(duplicated[i]); 
    } 
    free(duplicated); 

    for (int i = 0; i < size; i++) { 
     free(words[i]); 
    } 
    free(words); 

    for (int i = 0; i < hist_size; i++) { 
     free(histogram->freqs[i]->word); 
    } 

    for (int i = 0; i < hist_size; i++) { 
     free(histogram->freqs[i]); 
    } 
    free(histogram->freqs); 
    free(histogram); 


    return 0; 
} 

Freq** quicksort_freqs(Freq** target, int first, int last) 
{ 
    Freq* temp; 
    int pivot, j, i; 

    if (first < last) { 
     pivot = first; 
     i = first; 
     j = last; 

     while (i < j) { 
      while (target[i]->times <= target[pivot]->times && i < last) { 
       i++; 
      } 
      while (target[j]->times > target[pivot]->times) { 
       j--; 
      } 
      if (i < j) { 
       temp = target[i]; 
       target[i] = target[j]; 
       target[j] = temp; 
      } 
     } 
     temp = target[pivot]; 
     target[pivot] = target[j]; 
     target[j] = temp; 

     quicksort_freqs(target, first, j - 1); 
     quicksort_freqs(target, j + 1, last); 
    } 
    return target; 
} 

Freq** sort_rlexicographical(Freq** target, int first, int last) 
{ 
    int i, j; 
    Freq* temp; 

    for (i = first; i < last; ++i) 

     for (j = i + 1; j < last + 1; ++j) { 

      if (strcmp(target[i]->word, target[j]->word) < 0) { 
       temp = target[i]; 
       target[i] = target[j]; 
       target[j] = temp; 
      } 
     } 

    debug("In lexicographical reverse order:"); 
    for (i = 0; i < last + 1; ++i) { 
     debug("%s", target[i]->word); 
    } 
    debug("-----------------------"); 

    return target; 
} 

void print_reverse(Freq** target, int size) { 
    for (int i = size - 1; i >= 0; i--) { 
     printf("%s ", target[i]->word); 
     printf("%d \n", target[i]->times); 
    } 
} 

点で自由無効

：

196 for (int i = 0; i < size; i++) { 
197  free(words[i]); 
198 } 

と：

アクションで

201 for (int i = 0; i < hist_size; i++) { 
202  free(histogram->freqs[i]->word); 
203 } 

私のプログラム：

➜ tmp1 ./kontrolinis2 
Please enter a number of words > 4 
Enter word > test1 
Enter word > test1 
Enter word > test2 
Enter word > test2 
DEBUG kontrolinis2.c:150: Frequency table: 
DEBUG kontrolinis2.c:152: test1 2 
DEBUG kontrolinis2.c:152: test2 2 
DEBUG kontrolinis2.c:154: ----------------------- 
DEBUG kontrolinis2.c:158: Sorted frequency table: 
DEBUG kontrolinis2.c:160: test1 2 
DEBUG kontrolinis2.c:160: test2 2 
DEBUG kontrolinis2.c:162: ----------------------- 
DEBUG kontrolinis2.c:264: In lexicographical reverse order: 
DEBUG kontrolinis2.c:266: test2 
DEBUG kontrolinis2.c:266: test1 
DEBUG kontrolinis2.c:268: ----------------------- 

Lexicographically sorted frequency table: 
test1 2 
test2 2 

Valgrindの出力（と同じ「ユーザ」入力）：

Lexicographically sorted frequency table: 
test1 2 
test2 2 
==9430== Invalid free()/delete/delete[]/realloc() 
==9430== at 0x4C2E14B: free (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so) 
==9430== by 0x1091D4: main (kontrolinis2.c:197) 
==9430== Address 0x51f19d0 is 0 bytes inside a block of size 50 free'd 
==9430== at 0x4C2E14B: free (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so) 
==9430== by 0x109194: main (kontrolinis2.c:192) 
==9430== Block was alloc'd at 
==9430== at 0x4C2CE5F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so) 
==9430== by 0x108C77: main (kontrolinis2.c:89) 
==9430== 
==9430== Invalid free()/delete/delete[]/realloc() 
==9430== at 0x4C2E14B: free (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so) 
==9430== by 0x109217: main (kontrolinis2.c:202) 
==9430== Address 0x51f1ad0 is 0 bytes inside a block of size 50 free'd 
==9430== at 0x4C2E14B: free (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so) 
==9430== by 0x109194: main (kontrolinis2.c:192) 
==9430== Block was alloc'd at 
==9430== at 0x4C2CE5F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so) 
==9430== by 0x108C77: main (kontrolinis2.c:89) 
==9430== 
==9430== 
==9430== HEAP SUMMARY: 
==9430==  in use at exit: 118 bytes in 4 blocks 
==9430== total heap usage: 18 allocs, 18 frees, 2,612 bytes allocated 
==9430== 
==9430== 16 bytes in 2 blocks are definitely lost in loss record 1 of 2 
==9430== at 0x4C2CE5F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so) 
==9430== by 0x108DC7: main (kontrolinis2.c:133) 
==9430== 
==9430== 102 bytes in 2 blocks are definitely lost in loss record 2 of 2 
==9430== at 0x4C2EF35: calloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so) 
==9430== by 0x108D23: main (kontrolinis2.c:104) 
==9430== 
==9430== LEAK SUMMARY: 
==9430== definitely lost: 118 bytes in 4 blocks 
==9430== indirectly lost: 0 bytes in 0 blocks 
==9430==  possibly lost: 0 bytes in 0 blocks 
==9430== still reachable: 0 bytes in 0 blocks 
==9430==   suppressed: 0 bytes in 0 blocks 
==9430== 
==9430== For counts of detected and suppressed errors, rerun with: -v 
==9430== ERROR SUMMARY: 6 errors from 4 contexts (suppressed: 0 from 0) 

プログラム全体ではなく、その主要部分、または何らかのプロトタイプを貼り付ける必要があるかどうかを修正します。しかし、ここでの主な細部 は、キーワード "malloc"と "free"を含む行です。 "get_pos_num" と "get_word"：

UPDATE：ここで使用されているライブラリから、二つの機能追加は

char* get_word(char* message, char* output) 
{ 

    while (1) { 
     printf("%s", message); 
     if (scanf("%s", output) == 1 && getchar() == '\n') { 
      break; 
     } else { 
      while (getchar() != '\n') 
       ; 
      printf("Error: not a string, or too many arguments\n"); 
     } 
    } 

    return output; 
} 

int get_pos_num(char* message, int zero_allowed) 
{ 
    int num; 
    int margin; 

    if (zero_allowed) { 
     margin = 0; 
    } else { 
     margin = 1; 
    } 

    while (1) { 
     printf("%s", message); 
     if (scanf("%d", &num) == 1 && getchar() == '\n') { 
      if (num >= margin) { 
       break; 
      } else { 
       printf("Error: number is not positive"); 
       if (zero_allowed) { 
        printf(" or zero"); 
       } 
       printf("\n"); 
      } 
     } else { 
      while (getchar() != '\n') 
       ; 
      printf("Error: not a number\n"); 
     } 
    } 

    return num; 
} 

Answer 1

はまあ明らかな問題はここにある：

freq->word = (char*)malloc(sizeof(MAX_STRING * sizeof(char))); 
freq->word = words[i]; 

あなたが割り当てfreq->wordのメモリとそれをwords[i]で上書きします。

wordsを無料で無料にしてから構造に割り当てた多くのfreqを解放します。あなたがwords[i]をコピーしたい場合は

あなたが使用する必要がありますいずれか

freq->word = strdup(words[i]); 

または

freq->word = malloc(strlen(words[i])+1); 
strcpy(freq->word,words[i]); 

また、両方があなたを引き起こしますあなたもここに

duplicated[i] = words[i]; 

を同じことを行う気づきましたあなたが割り当てられたメモリのトラックを失っているので、メモリがリークします。

そしてもう一つは、（私は今日コロンボように見える）あなただけのMAX_STRING * sizeof(char)であるべき、上記mallocに

sizeof(MAX_STRING * sizeof(char))を持っているということです。どのような結果が得られるかは完全には分かりませんが、4バイトまたは8バイトのいずれかになります。