hashtable issue in C; double free detected in tcache 2

You should move list_destroy(list->node); outside the inner loop. You are freeing the node list multiple times inside a loop where you iterate on the node links.

Here is a modified version:

strhash_table *strhash_table_destroy(strhash_table *table) {
    unsigned int i;
    super_list *list;
    s_node *node;

    for (i = 0; i < table->len; i++) {
        list = table->list + i;
        for (node = list->node; node != NULL; node = node->next) {
            free(node->data);
        }
        list_destroy(list->node);
    }
    free(table->list);
    free(table);
    return table;
}

void list_destroy(s_node *head) {
    while (head) {
        head = list_headRemove(head);
    }
}

s_node *list_headRemove(s_node *head) {
    if (!head) return head;
    s_node *n = head->next;
    free(head);
    return n;
}

UPDATE

In the code posted, there are conflicting versions of functions list_destroy and list_headRemove, furthermore there are 2 calls to free(node); in the second function list_destroy, both of which are useless since node is a null pointer when the while loop exits.

UPDATE 2

There is a problem in strhash_table_free: you free list->node but you do not update list->node, so the list is freed a second time in strhash_table_destroy where list->len is not tested.

The field len in super_list seems redundant. You should just test if the node member is NULL and set it to NULL when the list is freed.

UPDATE 3

The final post is hardly minimal and does not show the problem... but I found some issues:

• strhash_table_destroy returns table after freeing it: this is bad because table is now an invalid pointer. strhash_table_destroy should not return anything.

• test_destroy dereferences table after strhash_table_destroy has freed it. This has undefined behavior. Remove this test function, just call strhash_table_destroy from main().

• you free node->data in strhash_table_remove before passing it to list_remove, which is bad because node->data has become invalid.

• worse: list_remove() does not test is the head node should be removed. In a minimal test case with a single element in the hash table, "ele1" is the head node, hence this node remains in the list, the len is decremented and becomes out of sync and the node has an invalid data pointer which will strhash_table_destroy will attempt to free, causing the double free issue.

• strhash_table_free seems incorrect and inconsistent with strhash_table_destroy.

There are probably other issues in the code.

Here is a modified version with some simplifications and fixes:

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

/**List header */
#ifndef LISTE_H
#define LISTE_H

struct _list_node {
    void *data;
    struct _list_node *next;
};

typedef struct _list_node s_node;

s_node *list_create(void);
void *list_get_data(s_node *node);
void list_set_data(s_node *node, void *data);
s_node *list_insert(s_node *head, void *data);
s_node *list_append(s_node *head, void *data);
s_node *list_process(s_node *head, int (*fct)(s_node *node, void *param), void *param);
s_node *list_ordered_append(s_node **head, int (*fct)(s_node *node, void *param), void *param);
s_node *list_headRemove(s_node *head);
s_node *list_remove(s_node *head, void *data);
void list_destroy(s_node *head);
void afficher_s_node(s_node *list);
int list_is_empty( s_node *node );
unsigned int list_size(s_node *node);
#endif

/****  c file list */
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
//#include "list.h"

s_node *list_create(void) {
    return NULL;
}

void *list_get_data(s_node *node) {
    return node->data;
}

void list_set_data(s_node *node, void *data) {
    node->data = data;
}

s_node *list_insert(s_node *head, void *data) {
    s_node *node = (s_node *)malloc(sizeof(s_node));
    if (node) {
        list_set_data(node, data);
        node->next = head;
        return node;
    } else {
        return head;
    }
}

s_node *list_append(s_node *head, void *data) {
    if (!head) return list_insert(head, data);

    s_node *node = head;
    while (node->next) {
        node = node->next;
    }
    node->next = list_insert(NULL, data);

    return head;
}

s_node *list_process(s_node *head, int (*fct)(s_node *node, void *param), void *param) {
    for (s_node *node = head; node; node = node->next) {
        if (fct(node, param) == 1) {
            return node;
        }
    }
    return NULL;
}

s_node *list_ordered_append(s_node **head, int (*fct)(s_node *node, void *param), void *param) {
    s_node *node;
    int res;

    // empty list
    if (!*head) {
        return *head = list_insert(*head, param);
    }

    // insert at head
    res = fct(*head, param);
    if (res > 0) {
        return *head = list_insert(*head, param);
    }
    if (res == 0) {
        return *head;
    }

    // generic case
    for (node = *head; node->next; node = node->next) {
        res = fct(node->next, param);
        if (res > 1) {
            return node->next = list_insert(node->next, param);
        }
        if (res == 0) {
            return node->next;
        }
    }

    // append node
    return node->next = list_insert(NULL, param);
}

s_node *list_headRemove(s_node *head) {
    if (head) {
        s_node *n = head->next;
        free(head);
        return n;
    } else {
        return NULL;
    }
}

s_node *list_remove(s_node *head, void *data) {
    if (!head) return head;

    if (head->data == data) {
        head = list_headRemove(head);
    } else {
        for (s_node *node = head; node->next; node = node->next) {
            if (node->next->data == data) {
                node->next = list_headRemove(node->next);
                break;
            }
        }
    }
    return head;
}

void list_destroy(s_node *head) {
    while (head)
        head = list_headRemove(head);
}

int list_is_empty(s_node *node) {
    return node == NULL;
}

unsigned int list_size(s_node *node) {
    unsigned int i = 0;
    while (node) {
        node = node->next;
        i++;
    }
    return i;
}

/* hash table header */
#ifndef HACHAGE_H
#define HACHAGE_H

//#include "list.h"

typedef struct {
    s_node *node;
    unsigned int len;
} super_list;

typedef struct {
    super_list *list;
    unsigned int len;
} strhash_table;

strhash_table *strhash_table_init(const unsigned int len);
void strhash_table_destroy(strhash_table *table);
strhash_table *strhash_table_free(strhash_table *table);
char *strhash_table_add(strhash_table *table, const char *str);
int strhash_table_remove(strhash_table *table, const char *str);
void strhash_table_info(strhash_table *table);
void strhash_print(strhash_table *table);

#endif

/****  c file hash table */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
//#include "hachage.h"
//#include "list.h"

int hashCode(const char *str, unsigned int size_hash_table) {
    unsigned int i, cle = 0;
    for (i = 0; str[i] != '\0'; i++) {
        cle *= 2;
        cle += (int)str[i];
    }
    return cle % size_hash_table;
}

int compare_str_add(s_node *node, void *param) {
    /* return <0 if node->data is before param, >0 if after, =0 if strings are equal */
    return strcmp((const char *)node->data, (const char *)param);
}

strhash_table *strhash_table_init(const unsigned int len) {
    strhash_table *table = (strhash_table *)malloc(sizeof(strhash_table));
    super_list *list = (super_list *)malloc(sizeof(super_list) * len);

    if (!table || !list) {
        free(table);
        free(list);
        return NULL;
    }

    for (unsigned int i = 0; i < len; i++) {
        list[i].node = list_create();
        list[i].len = 0;
    }
    table->list = list;
    table->len = len;

    return table;
}

void strhash_table_destroy(strhash_table *table) {
    for (unsigned int i = 0; i < table->len; i++) {
        super_list *list = table->list + i;
        s_node *node = list->node;
        while (node) {
            s_node *next = node->next;
            free(node->data);
            free(node);
            node = next;
        }
        list->node = NULL;
    }
    free(table->list);
    free(table);
}

char *strhash_table_add(strhash_table *table, const char *str) {
    char *to_insert = strdup(str);
    int index = hashCode(str, table->len);

    s_node *ordered_Add = list_ordered_append(&table->list[index].node, compare_str_add, to_insert);
    if (ordered_Add->data == to_insert) {
        /* node was inserted: increase len */
        table->list[index].len++;
    } else {
        /* node already present: free new data */
        free(to_insert);
    }
    return (char *)ordered_Add->data;
}

int find_str_node(s_node *node, void *param) {
    return strcmp((const char *)node->data, (const char *)param) == 0 ? 1 : 0;
}

// return 1 if successful
int strhash_table_remove(strhash_table *table, const char *str) {
    int index = hashCode(str, table->len);
    s_node *find_node = list_process(table->list[index].node, find_str_node, (void *)(uintptr_t)str);
    if (find_node) {
        /* node was found: free node and data */
        void *data = find_node->data;
        table->list[index].node = list_remove(table->list[index].node, data);
        table->list[index].len--;
        free(data);
        return 1;
    }
    return 0;
}

void strhash_table_info(strhash_table *table) {
    unsigned int i;
    unsigned int len, min, max;
    double deviation, moy;

    len = max = min = table->list[0].len;
    for (i = 1; i < table->len; i++) {
        if (table->list[i].len > max) max = table->list[i].len;
        else if (table->list[i].len < min) min = table->list[i].len;
        len += table->list[i].len;
    }

    moy = (double)len / table->len;
    deviation = 0;
    for (i = 0; i < table->len; i++) {
        deviation += (table->list[i].len - moy) * (table->list[i].len - moy);
    }
    deviation = sqrt(deviation / table->len);

    printf("Table hachage : ");
    printf("%p\n", (void *)table);
    printf("\tNombre total d'élément : " );
    printf("%u\n",len );
    printf("\tNombre minimum : ");
    printf("%u\n", min);
    printf("\tNombre maximum : ");
    printf("%u\n", max );
    printf("\tÉcart type du nombre d'éléments par entrée : ");
    printf("%.2f\n", deviation);
    return;
}

void strhash_print(strhash_table *table) {
    unsigned int i, j;
    super_list *list;
    s_node *node;
    printf("\nHash table de %p\n", (void *)table);
    printf("Start\n");
    for (i = 0; i < table->len; i++) {
        list = table->list + i;
        printf("\t%d ---\n", i);
        /****/
        for (j = 0, node = list->node; j < list->len; j++, node = node->next) {
            printf( "\t\t%d. %s\n", j, (char *)node->data);
        }
    }
    printf("End\n");
}

/**** test file */

int main(void) {
    strhash_table *table = strhash_table_init(10);
    strhash_print(table);
    strhash_table_add(table, "ele1");
    strhash_table_remove(table, "ele1");
    strhash_table_add(table, "ele1");
    strhash_table_add(table, "ele2");
    strhash_table_add(table, "ele3");
    strhash_table_add(table, "ele4");
    strhash_table_add(table, "ele5");
    strhash_table_remove(table, "ele1");
    strhash_print(table);
    strhash_table_destroy(table);

    return 0;
}

A cleaner way to do it in my opinion assuming you don't reuse list_headRemove and list_headRemove :

strhash_table *strhash_table_destroy(strhash_table *table) {
    unsigned int i;
    super_list *list;
    s_node *node, *next;

    for (i = 0; i < table->len; i++) {
        
        list = table->list + i;
        node = list->node;

        while (node) {
            next = node->next;

            free(node->data);           
            free(node);

            node = next;
        }

    }

    free(table->list);
    free(table);

    return table; /* This pointer is not valid anymore be careful */
}