这段代码有什么问题？ [散列表在C]

Question

我正在实施一个哈希表。以下是我的初始化函数。 我得到一些错误，我不明白为什么。我也引用了valgrind的说法。

typedef struct HashTable 
    { 
    int size ; 
    struct List *head; 
    struct List *tail;  
    }HashTable; 

    typedef struct List 
    { 
    char *number; 
    char *name; 
    int time; 
    struct List *next;  
    }List; 

    #define size_of_table 211 

    HashTable *createHashTable(void) 
    { 
    HashTable *new_table = malloc(sizeof(*new_table)*size_of_table); //line 606 

    if (new_table == NULL) 
    { return NULL; 
    } 

    int i=0; 
    for(i; i<size_of_table; i++) 
    { 
     new_table[i].size=0; 
     new_table[i].head=NULL; 
     new_table[i].tail=NULL; 
    } 
    return NULL; 
    } 

Invalid write of size 8 
==7738== at 0x401707: createHashTable (project2.c:617) 
==7738== by 0x401AF6: main (project.c:739) 
==7738== Address 0x51996e0 is 8 bytes after a block of size 1,688 alloc'd 
==7738== at 0x4C25153: malloc (vg_replace_malloc.c:195) 
==7738== by 0x401698: createHashTable (project2.c:606) 
==7738== by 0x401AF6: main (project.c:739) 
==7738== 
==7738== 
==7738== 141 errors in context 3 of 4: 
==7738== Invalid write of size 8 
==7738== at 0x4016E8: createHashTable (project2.c:616) 
==7738== by 0x401AF6: main (project.c:739) 
==7738== Address 0x51996d8 is 0 bytes after a block of size 1,688 alloc'd 
==7738== at 0x4C25153: malloc (vg_replace_malloc.c:195) 
==7738== by 0x401698: createHashTable (project2.c:606) 
==7738== by 0x401AF6: main (project.c:739) 

Answer 1

工作正常，我。我添加了const int size_of_table = 12并从main调用了createHashTable()。

$ valgrind ./a.out 
==30237== Memcheck, a memory error detector 
==30237== Copyright (C) 2002-2009, and GNU GPL'd, by Julian Seward et al. 
==30237== Using Valgrind-3.6.0.SVN and LibVEX; rerun with -h for copyright info 
==30237== Command: ./a.out 
==30237== 
--30237-- ./a.out: 
--30237-- dSYM directory is missing; consider using --dsymutil=yes 
==30237== 
==30237== HEAP SUMMARY: 
==30237==  in use at exit: 376 bytes in 2 blocks 
==30237== total heap usage: 2 allocs, 0 frees, 376 bytes allocated 
==30237== 
==30237== LEAK SUMMARY: 
==30237== definitely lost: 288 bytes in 1 blocks 
==30237== indirectly lost: 0 bytes in 0 blocks 
==30237==  possibly lost: 0 bytes in 0 blocks 
==30237== still reachable: 88 bytes in 1 blocks 
==30237==   suppressed: 0 bytes in 0 blocks 
==30237== Rerun with --leak-check=full to see details of leaked memory 
==30237== 
==30237== For counts of detected and suppressed errors, rerun with: -v 
==30237== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0) 
$ 

Answer 2

您肯定这是你正在测试的代码？ 1688个字节被分成211个数组元素，每个元素给出8个字节。

现代环境只会给你8字节的结构持有一个int和两个指针是不太可能的。

---

通过测试的方式，下面的代码：

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

typedef struct HashTable { 
    int size ; 
    struct List *head; 
    struct List *tail; 
} HashTable; 

typedef struct List { 
    char *number; 
    char *name; 
    int time; 
    struct List *next; 
} List; 

#define size_of_table 211 

HashTable *createHashTable(void) { 
    HashTable *new_table = malloc(sizeof(*new_table)*size_of_table); //line 606 
    printf ("%d\n", sizeof(*new_table)); 
    printf ("%d\n", sizeof(new_table)); 
    if (new_table == NULL) { 
     return NULL; 
    } 

    int i=0; 
    for(i; i<size_of_table; i++) { 
     new_table[i].size=0; 
     new_table[i].head=NULL; 
     new_table[i].tail=NULL; 
    } 
    return new_table; 
} 

int main(void) { 
    HashTable *x = createHashTable(); 
    free (x); 
    return 0; 
} 

输出：

==3569== Memcheck, a memory error detector 
==3569== Copyright (C) 2002-2009, and GNU GPL'd, by Julian Seward et al. 
==3569== Using Valgrind-3.6.0.SVN-Debian and LibVEX; rerun with -h for copyright info 
==3569== Command: ./qq 
==3569== 
12 
4 
==3569== 
==3569== HEAP SUMMARY: 
==3569==  in use at exit: 0 bytes in 0 blocks 
==3569== total heap usage: 1 allocs, 1 frees, 2,532 bytes allocated 
==3569== 
==3569== All heap blocks were freed -- no leaks are possible 
==3569== 
==3569== For counts of detected and suppressed errors, rerun with: -v 
==3569== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 13 from 8) 

是什么程序给你，当你通过的valgrind您的系统上运行呢？

我上面提供的代码还修复了您在成功返回NULL时出现的问题（明确的内存泄漏）。你在功能最终换来不应该返回NULL，它应该是：

return new_table; 

---

基于从我提供的示例代码你24,8输出，请确保您使用是真的：

HashTable *new_table = malloc(sizeof(*new_table)*size_of_table); //line 606 

而不是：

HashTable *new_table = malloc(sizeof(new_table)*size_of_table); //line 606 

后者将使用8指针的大小，而不是24结构尺寸，当我这样做的，我得到：

==3637== Memcheck, a memory error detector 
==3637== Copyright (C) 2002-2009, and GNU GPL'd, by Julian Seward et al. 
==3637== Using Valgrind-3.6.0.SVN-Debian and LibVEX; rerun with -h for copyright info 
==3637== Command: ./qq 
==3637== 
12 
4 
==3637== Invalid write of size 4 
==3637== at 0x80484CD: createHashTable (in /home/allan/qq) 
==3637== by 0x8048509: main (in /home/allan/qq) 
==3637== Address 0x419a374 is 0 bytes after a block of size 844 alloc'd 
==3637== at 0x4024F20: malloc (vg_replace_malloc.c:236) 
==3637== by 0x8048465: createHashTable (in /home/allan/qq) 
==3637== by 0x8048509: main (in /home/allan/qq) 
==3637== 
==3637== Invalid write of size 4 
==3637== at 0x80484E3: createHashTable (in /home/allan/qq) 
==3637== by 0x8048509: main (in /home/allan/qq) 
==3637== Address 0x419a378 is 4 bytes after a block of size 844 alloc'd 
==3637== at 0x4024F20: malloc (vg_replace_malloc.c:236) 
==3637== by 0x8048465: createHashTable (in /home/allan/qq) 
==3637== by 0x8048509: main (in /home/allan/qq) 
==3637== 
==3637== Invalid write of size 4 
==3637== at 0x80484B8: createHashTable (in /home/allan/qq) 
==3637== by 0x8048509: main (in /home/allan/qq) 
==3637== Address 0x419a37c is 8 bytes after a block of size 844 alloc'd 
==3637== at 0x4024F20: malloc (vg_replace_malloc.c:236) 
==3637== by 0x8048465: createHashTable (in /home/allan/qq) 
==3637== by 0x8048509: main (in /home/allan/qq) 
==3637== 
==3637== 
==3637== HEAP SUMMARY: 
==3637==  in use at exit: 0 bytes in 0 blocks 
==3637== total heap usage: 1 allocs, 1 frees, 844 bytes allocated 
==3637== 
==3637== All heap blocks were freed -- no leaks are possible 
==3637== 
==3637== For counts of detected and suppressed errors, rerun with: -v 
==3637== ERROR SUMMARY: 422 errors from 3 contexts (suppressed: 13 from 8) 

---

如果你确信你使用了24值，放置线路：

printf ("%d\n", sizeof(*new_table)*size_of_table); 

在malloc行之后，看看它输出了什么。