Home > Net >  Initializing a Hash Table in C memory leak
Initializing a Hash Table in C memory leak

Time:10-01

The following code is giving segmentation fault. Where in the memory allocation did I wrongly allocate... There is a memory leak according to valgrind. What does "invalid size of 8 mean"?

Any help much appreciated. Thanks

// Represents a node in a hash table

typedef struct node {
    char word[LENGTH   1];
    struct node *next;
} node;

// TODO: Choose number of buckets in hash table
const unsigned int N = 26;

// Hash table
node *table[N];

// If loaded
bool loaded = false;

void init_table() {
    table = malloc(sizeof(node) * N);

    for (int i = 0 ; i < N; i  ) {
        table[i]->next = NULL;
    }
}

Valgrind is spitting this out:

enter image description here

CodePudding user response:

There are multiple problems:

  • table is defined as an array of N pointers to node structures. The line table = malloc(sizeof(node) * N); should not even compile. Your screenshot cannot possibly be produced by the posted code.

  • As a matter of fact, in C, unlike C , const unsigned int N = 26; does not define N as a compile time constant so node *table[N]; is an invalid definition at global scope and would define a variable length array (VLA) at local scope. Your compiler seems to accept extensions borrowed from C or might even compile the code as C . Define N as a macro or an enum value to make it a constant expression.

  • the loop dereferences the elements in table as table[i]->next = NULL; but the array contains null pointers: dereferencing them causes undefined behavior.

  • you should instead initialize the elements of table to NULL.

Here is a modified version:

// Represents a node in a hash table
typedef struct node {
    char word[LENGTH   1];
    struct node *next;
} node;

// TODO: Choose number of buckets in hash table
enum { N = 26 };

// Hash table
node *table[N];

// If loaded
bool loaded = false;

void init_table(void) {
    for (int i = 0; i < N; i  ) {
        table[i] = NULL;
    }
}
  • Related