這段代碼有什麼問題？ [散列表在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行之後，看看它輸出了什麼。