Cannot free nodes in my hash table when there are collisions (using separate chaining) in C

Question

Ok so I have a hash table that I made in C. I'm using separate chaining (linked lists) to resolve collisions. I noticed that I can free the entire table IF there were no collisions and every item hashed to its own index. BUT if there is a collision and I have more than one value at an index, it is only able to free the first value and not the remaining values in that index. The program crashes when it tried to free the others at that index. I tried debugging it and I realized that those other values have been set to NULL, which I'm not sure why because when I'm inserting them to the table I'm using malloc. I know I'm missing something. If someone can help that would be super awesome, as I've been trying to solve this problem for several hours :/

Here's the code:

int symTabSearch(struct hashTable * h, char * label);
int insertToSymTab(struct hashTable * h, char * label, int locctr);

struct listNode
{
    char * label;
    int address;
    struct listNode * next;
};

struct hashTableNode
{
    int blockCount;         //number of elements in a block
    struct listNode * firstNode;
};

struct hashTable
{
    int tableSize;
    int count;              //number of elements in the table
    struct hashTableNode * table;
};

struct hashTable * createHashTable(int size)
{
    struct hashTable * ht;
    ht = (struct hashTable*)malloc(sizeof(struct hashTable));

    if (!ht)
        return NULL;

    ht->tableSize = size;
    ht->count = 0;
    ht->table = (struct hashTableNode *)malloc(sizeof(struct hashTableNode) * ht->tableSize);

    if (!ht->table)
    {
        printf("Memory error\n");
        return NULL;
    }

    int i;
    for (i = 0; i < ht->tableSize; i++)
    {
        ht->table[i].blockCount = 0;
        ht->table[i].firstNode = NULL;
    }

    return ht;
}

/*hash function: adds up the ascii values of each
character, multiplies by a prime number (37) and mods the sum wih the table size*/
int hash(char * label, int tableSize)
{
    int hashVal = 0;
    size_t i;

    for (i = 0; i < strlen(label); i++)
        hashVal = 37 * hashVal + label[i];

    hashVal %= tableSize;
    if (hashVal < 0)
        hashVal += tableSize;

    return hashVal;
}

int symTabSearch(struct hashTable * h, char * label)
{
    struct listNode * temp;
    temp = h->table[hash(label, h->tableSize)].firstNode; //temp points to the first listNode in table[hashedIndex]

    while (temp)
    {
        if (strcmp(temp->label, label) == 0)
            return 1;   //found

        temp = temp->next;      //go to next link
    }
    return 0;   //not found
}

int insertToSymTab(struct hashTable * h, char * label, int locctr)
{
    int index;
    struct listNode * currentNode, *newNode;

    index = hash(label, h->tableSize);
    currentNode = h->table[index].firstNode;

    newNode = (struct listNode *)malloc(sizeof(struct listNode));
    newNode->label = (char *)malloc(sizeof(char) * 7);  //allocates 7 chars to store label up to 6 chars long (0-5), last one is for the '\0'

    if (!newNode)   //if new node is null
    {
        printf("Error creating new node\n");
        return 0;
    }

    strcpy(newNode->label, label);
    newNode->address = locctr;

    if (h->table[index].firstNode == NULL)      //if first node at table index is empty
    {
        h->table[index].firstNode = newNode;
        h->table[index].firstNode->next = NULL;
    }
    else
    {                                           //firstNode was not empty, so chain newNode to the next empty node
        while (currentNode != NULL)             //go to next available node
            currentNode = currentNode->next;

        currentNode = newNode;
        currentNode->next = NULL;
    }

    h->table[index].blockCount++;
    h->count++;
    return 1;
}

void freeHashTable(struct hashTable * h)        //might not free memory properly, might crash too, test later
{
    int i, j;
    struct listNode * current, *temp;
    char * tempStr;

    if (!h)     //make sure table even has memory to be freed
        return;

    for (i = 0; i < h->tableSize; i++)
    {
        current = h->table[i].firstNode;
        for (j = 0; j < h->table[i].blockCount; j++)
        {
            temp = current;
            tempStr = current->label;
            current = current->next;
            free(temp);
            free(tempStr);
            temp = NULL;
            tempStr = NULL;
        }
    }

    free(h->table);
    h->table = NULL;
    free(h);
    h = NULL;
}

Three things: First [in C you should not cast the result of `malloc`](http://stackoverflow.com/questions/605845/do-i-cast-the-result-of-malloc) (or any function returning `void *`). Secondly, you need to traverse the list in `h->table[i].firstNode` to free all nodes. Thirdly, your `insertToSymTab` function doesn't work if the list is not empty, you don't actually append any new nodes. — Some programmer dude, Oct 27 '15 at 07:17
@JoachimPileborg I thought I was traversing each list and freeing each node? In my `freeHashTable` function the outer loop goes through each list and then the inner loop loops through the list and frees everything inside. And as for your third statement, How would I append a node to a list if I'm not already doing it? — David Velasquez, Oct 27 '15 at 07:22
Okay, I was wrong about the traversing the list in `freeHashTable`, you're just not doing it in a "standard way". :) I'll write an answer as the problem seems to be your (non-working) appending to the list. — Some programmer dude, Oct 27 '15 at 07:29

score 2 · Accepted Answer · answered Oct 27 '15 at 07:33

The problem is in the insertToSymTab function, when you attempt to append a node to the list.

The problem here is this loop:

while (currentNode != NULL)             //go to next available node
    currentNode = currentNode->next;

When that loop is done, you have passed the end of the list and the value of currentNode is NULL. Changing that pointer will not append the new node to the end of the list.

Instead you need to change your loop to e.g.

while (currentNode->next != NULL)
    currentNode = currentNode->next;

Then when the loop is over, currentNode will instead be the last node currently in the list, and you append the new node by changing currentNode->next:

currentNode->next = newNode;

Don't forget to set newNode->next to NULL.

You are a life saver man! Thanks so much :] I didn't realize I was completely passing over the list. I now see my mistake ha. — David Velasquez, Oct 27 '15 at 07:42

score 1 · Answer 2 · answered Oct 27 '15 at 07:37

Your error is in insertToSymTab here:

    while (currentNode != NULL)             //go to next available node
        currentNode = currentNode->next;

    currentNode = newNode;
    currentNode->next = NULL;

You set currentNode as currentNode->next (copying the pointer value) and then you set is as the newNode. But currentNode is not linked to the previous currentNode->next, it will just be a NULL pointer which you then assign to the newNode.

You either have to set currentNode->Next = newNode for the last node of the list or use a struct listnode ** pointer to achieve something similar to what I think you are trying here.

Edit: Joachim provided the answer more quickly

Cannot free nodes in my hash table when there are collisions (using separate chaining) in C

2 Answers2