В чем проблема с этим кодом?[Hashtable в C]

Question

Я реализую хеш-таблицу. Следующее - моя функция для его инициализации. Я получаю некоторые ошибки, которые я не могу понять, почему. Я также процитировал то, что говорит Вальгринд.

 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

Вы уверены, это код, который вы тестируете? 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 и посмотрите, что она выводит.

Answer 2

Работает нормально для меня.Я добавил const int size_of_table = 12 и вызвал createHashTable() из main.

$ 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)
$