「プログラム全体」が提供される前
関数内の情報が与えられたnew_element()場合:
result->word = s;
result->freq = 1;
result->next = NULL;
（実際の情報が含まれていないため）ハッシュテーブルは、要素が、割り当てられた名前、頻度、および次の項目へのポインターを含む個別に割り当てられた要素のリンクリストである配列であると推測する必要があります。したがって、ハッシュ テーブルを解放するには、配列の各要素に順番にアクセスし、リンクされたリストを追跡して、名前と要素を解放する必要があります。
void free_hashtable(void)
{
if (htable != 0)
{
for (int i = 0; i < tsize; i++)
{
h_ptr next = 0;
for (h_ptr curr = htable[i]; curr != 0; curr = next)
{
next = curr->next;
free(curr->word);
free(curr);
}
}
free(htable);
htable = 0;
tsize = 0;
}
}
「プログラム全体」が提供された後
まだデータ構造がないので、何が起こっているのかまだわかりません。したがって、これをコードの先頭に追加できます。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct hash_table_entry
{
int freq;
struct hash_table_entry *next;
char *word;
} *h_ptr;
ただし、それを追加すると発生する1つの問題は次のとおりです。
h_ptr result = (h_ptr) malloc(sizeof(h_rec));
コンパイラは次のように述べています。
error: 'h_rec' undeclared (first use in this function)
その行を識別します。さて、次のような typedef があるかもしれません。
typedef struct hash_table_entry h_rec;
しかし、推測する必要はありません。推測する必要がないように、SSCCE ( Short, Self-Contained, Correct Example ) を作成してください。
次を使用してコードをコンパイルします。
gcc -O3 -g -std=c99 -Wall -Wextra -Wmissing-prototypes -Wstrict-prototypes -Wold-style-definition ht.c -o ht
コンパイラは次のことを警告します。
ht.c:27:6: warning: no previous prototype for ‘lowercase’ [-Wmissing-prototypes]
ht.c:41:6: warning: no previous prototype for ‘new_table’ [-Wmissing-prototypes]
ht.c:59:7: warning: no previous prototype for ‘new_element’ [-Wmissing-prototypes]
ht.c:82:10: warning: no previous prototype for ‘hash_function’ [-Wmissing-prototypes]
ht.c:103:7: warning: no previous prototype for ‘save_string’ [-Wmissing-prototypes]
ht.c:116:7: warning: no previous prototype for ‘find_element’ [-Wmissing-prototypes]
ht.c:142:7: warning: no previous prototype for ‘sort_words’ [-Wmissing-prototypes]
ht.c:176:6: warning: no previous prototype for ‘insert_string’ [-Wmissing-prototypes]
ht.c:191:6: warning: no previous prototype for ‘init_token’ [-Wmissing-prototypes]
ht.c:201:7: warning: no previous prototype for ‘get_word’ [-Wmissing-prototypes]
ht.c:224:7: warning: no previous prototype for ‘get_token’ [-Wmissing-prototypes]
ht.c:276:6: warning: no previous prototype for ‘word_freq’ [-Wmissing-prototypes]
ht.c: In function ‘main’:
ht.c:322:5: warning: implicit declaration of function ‘add_string_option’ [-Wimplicit-function-declaration]
ht.c:323:5: warning: implicit declaration of function ‘add_int_option’ [-Wimplicit-function-declaration]
ht.c:328:5: warning: implicit declaration of function ‘parse_options’ [-Wimplicit-function-declaration]
ht.c:329:5: warning: implicit declaration of function ‘show_options’ [-Wimplicit-function-declaration]
また、最後の 4 つの名前については、リンカーはそれらを見つけることができません。利用できないコードを使用しないコードが必要です。コードを SSCCE に減らします (自己完結型に注意してください!)。
これらの関数の呼び出しをハッキングし、それに応じて main を単純化しました。独自のソース ( ./ht < ht.c) で実行すると、以下が生成されます。
N-gram size 1
Running analysis... (This can take several minutes or more!)
Initializing hash table...
Inserting all n-grams into hash table in lowercase form...
Sorting all hash table elements according to frequency...
Analysis Details:
(Top 10 list of n-grams)
82 '='
30 'int'
27 '0'
23 'if'
23 'char'
22 's'
16 '1'
16 'i'
14 'ls'
14 'h_ptr'
Analysis Summary:
817 total n-grams
211 unique n-grams
94 singleton n-grams (occur only once)
Most common n-gram (with 82 occurrences) is '='
Longest n-gram (1 have length 16) is 'hash_table_entry'
Total time = 0.002225 seconds
問題ないように見えます...しかし、最適化されたビルドを実行すると、別のストーリーが表示されます...しかし、問題は、使用しているGCCの特定のバージョンでvalgrindの最適化された実装にあると結論付けました(部分的に、まったく同じコードで異なるバージョンの GCC を使用すると、エラーが解消されます。これは、5 バイトの割り当てでオフセット 4 から始まる 4 バイトを読み取るビジネスがないstrlen()呼び出しにエラーがあったためです)。strlen()
機能を追加しましたprint_hashtable()。ほとんどすべての自明でない構造では、このように「印刷」または「ダンプ」機能を利用できるようにする価値があると思います。
static void print_hashtable(FILE *fp, const char *tag)
{
fprintf(fp, "Print hash table: %s\n", tag);
fprintf(fp, "Size = %d; Address: %p\n", tsize, htable);
if (htable != 0)
{
for (int i = 0; i < tsize; i++)
{
printf("Entry %d (%p)\n", i, htable[i]);
h_ptr next = 0;
for (h_ptr curr = htable[i]; curr != 0; curr = next)
{
next = curr->next;
printf("Word: %s (freq %d; next %p)\n", curr->word, curr->freq, next);
}
}
}
}
の直前にこれへの呼び出しを挿入しましたsort_words()。これは、それほど効果的ではないハッシュ アルゴリズムにもかかわらず、データ構造が損なわれていないことを示しています。
print_hashtable()また、 afterへの呼び出しを挿入したsort_words()ところ、ソート プロセスによってハッシュ テーブルが完全に破棄されたことがわかりました。ソート フェーズでは、ハッシュ テーブルがハッシュ テーブルとして削除されます。唯一できることは、テーブル全体を解放することです ( free(htable))。すべてのテーブル エントリの解放は、関数の最下部で行う必要がありますword_freq()。
static void free_hashlist(h_ptr head)
{
while (head != 0)
{
h_ptr next = head->next;
printf("Free: %d (%s) %p -> %p\n", head->freq, head->word, (void *)head, (void *)next);
free(head->word);
free(head);
head = next;
}
}
static void word_freq(FILE *src, int details, int size)
{
char *s;
h_ptr list_head, ptr;
printf(" Initializing hash table...\n");
init_token(src);
new_table(size);
printf(" Inserting all n-grams into hash table in lowercase form...\n");
while ((s = get_word()))
insert_string(s);
print_hashtable(stdout, "After reading data");
printf(" Sorting all hash table elements according to frequency...\n");
list_head = sort_words();
if (details > 0)
{
printf("\nAnalysis Details:\n(Top %i list of n-grams)\n", details);
ptr = list_head;
while (ptr && details--)
{
printf("%d\t'%s'\n", ptr->freq, ptr->word);
ptr = ptr->next;
}
}
printf("\nAnalysis Summary:\n");
printf("%d total n-grams\n", wcnt);
printf("%d unique n-grams\n", ucnt);
printf("%d singleton n-grams (occur only once)\n", scnt);
printf("Most common n-gram (with %d occurrences) is '%s'\nLongest n-gram (%d have length %d) is '%s'\n",
mcnt, mstring, lcnt, llen, lstring);
free_hashlist(list_head);
}
また、free_hashtable() コードを単純化する必要があります。
static void free_hashtable(void)
{
if (htable != 0)
{
free(htable);
htable = 0;
lcnt = 0;
lstring = 0;
mcnt = 0;
mstring = 0;
scnt = 0;
tsize = 0;
wcnt = 0;
ucnt = 0;
}
}
int main(void)
{
printf("\nRunning analysis... (This can take several minutes or more!)\n");
word_freq(stdin, 10, 1024);
printf("Total time = %f seconds\n", (double) clock() / CLOCKS_PER_SEC);
free_hashtable();
return 0;
}
このプログラムでは、ポインターとカウントをヌル/ゼロにリセットすることは重要ではありません。また、lstringおよびmstringポインターは によって無効にされるfree_hashlist()ため、おそらくその関数でそれらを null にするかゼロにする必要があります。
これは私にとってはリークなしで実行され、最後にシステムに割り当てられたメモリのみが使用されます。