3

编辑：我添加了所有文件（.c、.h 和 Makefile）。该程序有效，但有许多内存泄漏。

http://dl.dropbox.com/u/21926200/Ngrams.tar.gz

你如何遍历一个哈希表来调用 free()？我想知道是否需要创建一个单独的函数来在 htable 和结果上调用 free() 或者我可以在这段代码中执行它。有任何想法吗？我只需要在 htable 和结果上调用 free()。

h_ptr *htable;
int tsize;

void new_table(int size)
{
    tsize = size;
    htable = (h_ptr *) calloc(size, sizeof(h_ptr));
    if (!htable) {
    fprintf(stderr, "Couldn't allocate hash array, exiting\n");
    exit(1);
    }

    // At the beginning, each element in the hash table
    // is a NULL pointer
    for(int i=0; i<size; i++)
      {
    htable[i]=NULL;
      }
}

// Allocate new element to store in hash table
h_ptr new_element(char *s)
{
    h_ptr result = (h_ptr) malloc(sizeof(h_rec));
    int wlen = strlen(s);
    if (wlen > llen) {
    lstring = s;
    llen = wlen;
    lcnt = 1;
    } else if (wlen == llen)
    lcnt++;
    if (!result) {
    fprintf(stderr, "Couldn't allocate hash element, exiting\n");
    exit(1);
    }

    result->word = s;
    result->freq = 1;
    result->next = NULL; 
    return result;
}

谢谢

4

2 回答 2

3

在提供“整个程序”之前

给定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;

但是，当我们添加它时出现的一个问题是：

 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（简短、独立、正确的示例），这样我们就不必猜测了。

我使用以下代码编译代码：

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]

对于最后四个名称，链接器无法找到它们。我们需要不使用不可用代码的代码。将您的代码简化为 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

看起来不错......但是运行优化的构建valgrind并出现另一个故事......但我已经得出结论，问题出strlen()在我正在使用的特定版本的 GCC 的优化实现中（部分原因是，在相同的代码上使用不同版本的 GCC 会使错误消失，并且因为错误发生在strlen()没有业务的调用中，从偏移量 4 开始读取 4 个字节，分配 5 个字节）。

我添加了一个功能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;
}

在这个程序中，将指针和计数重置为空/零并不重要。此外，lstringandmstring指针被 无效free_hashlist()，因此可以说那些应该在该函数中清零/归零。

这对我来说是无泄漏的，最后只有系统分配的内存仍在使用中。

于 2013-03-09T18:21:19.057 回答
0

首先，您不需要htable[i]在分配后htable清除每个人calloc（因为calloc给您一个清除的内存区域或失败）。我建议calloc也使用 in new_elementfor result。

然后，您可能希望有一些功能来删除您的htable. 就像是

void delete_htable(void) {      
  if (!htable) return;
  for (int i=0; i<tsize; i++)
    free (htable[i]);
  free (htable);
  htable = NULL;
}

请记住，您可以free使用NULL指针（不会发生任何有害的事情）。

你可能想delete_htable在你之前打电话exit（只是为了避免内存泄漏，让valgrind高兴）。

最后，您可能会考虑在现有库中使用现有的散列函数。以Glib为例（在 GTk 中，但您可以在任何 GTK 应用程序之外使用Glib ）。它已经为您提供了哈希表（并且鉴于这些经常使用，您可能对它们充满信心）。不要忘记 GTK（因此是 Glib）是LGPL2.1 许可下的免费软件库，因此您可以下载其源代码，学习和改进它。您想查看glib/ghash.h头文件和glib/ghash.c代码源文件（以及其他一些文件）。

于 2013-03-09T17:59:52.497 回答