I am studying C (self-study, not in an educational institution) and have been trying to build a hashtable data structure as part of my learning.

Please refer to this hopefully reproducible example:

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

struct table_item {
    char *name;
    char gender;
    char *birthdate;
    char *address;
};

struct list_node {
    struct table_item *data;
    struct list_node *next;
    unsigned long long hash_key;
};

struct hashtable {
    int table_size;
    int num_entries;
    struct list_node **entries;
};

struct hashtable* init_hashtable(int size);
void free_hashtable(struct hashtable *table);

int main(void)
{
    struct hashtable *hashtable = NULL;
    int size_entry = 0;
    
    printf("Input hashtable array size: ");
    while (size_entry < 1) {
        scanf(" %d", &size_entry);
    }
    hashtable = init_hashtable(size_entry);

    free_hashtable(hashtable);

    return 0;
}

struct hashtable* init_hashtable(int size) {
    struct hashtable* new_table;
    if ((new_table = malloc(sizeof(struct hashtable))) == NULL) {
        perror("Error: failed to allocate memory for hash table\n");
        exit(EXIT_FAILURE);
    }
    new_table->table_size = size;
    new_table->num_entries = 0;
    if ((new_table->entries = malloc(size*sizeof(struct list_node))) == NULL) {
        perror("Error: failed to allocate memory for hash table array\n");
        exit(EXIT_FAILURE);
    }

    return new_table;
}

void free_hashtable(struct hashtable *table) {

    for (int i = 0; i < table->table_size; i  ) {
        if (table->entries[i] != NULL) {
            free_list(table->entries[i]);
            table->entries[i] = NULL;
        }
    }

    free(table->entries);
    free(table);
}

My issue is that trying to free the table always fails, even if I have not added anything to it.

I used GDB to check the issue. It seems that, in the above for loop, if (table->entries[i] != NULL) always fires (such as when i=0) even when I haven't added anything. This results in my free_list function trying to free inappropriate memory, which is why I get the stack dump.

Somehow it seems that table->entries[i] is actually not NULL but rather has a struct list_node * type, causing the if condition to fire inappropriately. Could somebody please explain to me why this is?

I was hoping that I could use this for loop to go through the entries array and only free memory where malloced nodes exist, but as it stands this will just crash my program. I am not sure how I can alter this to behave as I'd like it to.

CodePudding user response：

Somehow it seems that table->entries[i] is actually not NULL but rather has a struct list_node * type, causing the if condition to fire inappropriately. Could somebody please explain to me why this is?

You dynamically allocate space for table->entries. The initial contents of that allocated space are unspecified, so until you assign values to its contents, it is unsafe to have any particular expectations about them. In particular, you cannot assume that any or all elements will contain null pointers.

If you want to rely on those values to tell you something about what kind of cleanup needs to be performed, then you should set them all to appropriate values, I guess NULL, immediately after allocating the space.

Note also that there are null pointer values of every pointer type, so being null and having type struct list_node * are not mutually exclusive.

CodePudding user response：

Somehow it seems that table->entries[i] is actually not NULL

Indeed, because you never initialized it to NULL.

init_hashtable allocates space using malloc and points table->entries. Now malloc does not initialize the memory it provides. Its contents are garbage, and in particular, there is no reason why it should consist entirely of NULL pointers as your code expects.

If you want table->entries to be full of NULL pointers then you have to explicitly initialize it, either with a loop, or with memset(entries, 0, size*sizeof(struct list_node *)). Or best of all, by calling calloc instead of malloc, which also avoids bugs in case the multiplication size*sizeof(struct list_node *) overflows.

(Technically memset and calloc initialize memory to all-bits-zero, which in theory does not have to correspond to NULL pointers, but it actually does on all systems you are likely to encounter. But to be pedantic, the loop is the only strictly conforming way to do it.)

but rather has a struct list_node * type,

This has nothing to do with types. Types in C are statically determined from declarations, and there is no way for an object to have an unexpected type at runtime. The type of table->entries[i] is struct list_node * no matter what. The question is about the value of that object; you expect it to be NULL but it's not. "Null pointers" are not a separate type in C; NULL is simply a value that a pointer of any type may have.

As Avi Berger points out, there is another bug in that the size calculation in the malloc should be size*sizeof(struct list_node *) not sizeof(struct list_node). Each element is not a struct list_node but rather a pointer. In this case a struct list_node is larger than a pointer, so it's just wasting memory and not causing any other harm, but it should be fixed.