Memory allocation problem in HashTable

Question

Please don't close this saying a duplicate question. I made an important change so not to confuse people, I resubmitted this much clearer codes.

Please help me to solve this memory allocation problem. I'm working on a HashTable and this is what I've (partial codes only)

main.c

HashTablePtr hash;
hash = createHashTable(10);
insert(hash, "hello");
insert(hash, "world");

HashTable.c

    HashTablePtr createHashTable(unsigned int capacity){
    HashTablePtr hash;
    hash = (HashTablePtr) malloc(sizeof(HashTablePtr));
    hash->size = 0;
    hash->capacity = capacity;          
    hash->list = (ListPtr *)calloc(capacity, sizeof(List)); /*NO MEMORY ALLOCATION HERE*/
    return hash;

List.h

typedef struct list List;
typedef struct list * ListPtr;

struct list {
    int size;
    NodePtr head;
    NodePtr tail;
};
...
...

HashTable.h

    typedef struct hashtable * HashTablePtr;
    typedef struct hashtable HashTable;
    struct hashtable {
        unsigned int capacity;
        unsigned int size;
        ListPtr *list;
        unsigned int (*makeHash)(unsigned int, void *);
    };
...
...

When I run my debugger (Netbeans C/C++ debugger, I see no memory being allocated to hash->list. In above example, my attempt is to make it an array of 10 lists.

Please help me to solve this.

I'm not that expert in C, if that helps.

Answer 1

This line

hash = (HashTablePtr) malloc(sizeof(HashTablePtr));

should read

hash = (HashTablePtr) malloc(sizeof(HashTable));

I also suggest you follow the advice that was given to you in your previous post and NOT hide pointers by typedef'ing. Just use List *

[Whenever you see an alloc statement, the type you assigning to is a pointer, and the type you are allocating should be of the type (and not the pointer to the type)]

Answer 2

In this line:

hash->list = (ListPtr *)calloc(capacity, sizeof(List));

The calloc function will allocate some memory for List, then return a pointer to the allocated memory, which would be List* (or, equivalent to ListPtr due to the typedef.)

In the code, the pointer is then casted to (ListPtr*), which would actually be List** which is not the type List* which is expected. Therefore, change the ListPtr* to ListPtr and see if that would fix that line.

Edit

As pointed out by leiz and Klathzazt in the comments, the Hashtable.list type is ListPtr* or List**:

struct hashtable {
    ...
    ListPtr *list;

This would be the reason why trying to assign a ListPtr type returned and casted from calloc would cause a compiler error. Rather than storing a pointer to a pointer of a List in the Hashtable, it should just hold a pointer to the list:

struct hashtable {
    ...
    ListPtr list;

This should eliminate the compiler error, as the type of Hashtable.list and typecast both will be ListPtr.

Answer 3

One nice idiom that you can use as well is eg:

hash = (HashTablePtr) malloc(sizeof(*hash));

By not hard-coding any types in the allocation, the possibility of mixing things up is greatly reduced.

Note that 'hash' is not actually dereferenced here - sizeof() is always evaluated at compile time, so the compiler just figures out what type *hash /would/ have, and gets the size of that.

Answer 4

Personally I am not a huge fan of using typedefs, especially when you are a beginner. I think that may be partially what is confusing you. You are better avoiding things like:

typedef struct hashtable * HashTablePtr;

Using to many typedefs will make your code harder to read since you will need to constantly look up what they are referring too.

The main problem is that you were allocating the memory for the size of a hashtable/list pointer and not for the size of their respected structures. I think the code below shows this well. You will also want to check if you allocations worked. If malloc, calloc, realloc. etc. fail they return NULL. If this happens and you do not check for this case you will get a segfault error and your program will crash.

Also follow the c99 standard, and put all of your variable declarations at the start of the function.

c99 std

malloc manpage

struct hashtable *
createHashTable(unsigned int capacity){
    struct hashtable *hash;
    struct list *mylist;

    /* You want to allocate size of the hash structure not the size of a pointer. */
    hash = malloc(sizeof(struct hashtable)); 
    // always make sure if the allocation worked.
    if(hash == NULL){
        fprintf(stderr, "Could not allocate hashtable\n");
        return NULL;
    }

    hash->size = 0;
    hash->capacity = capacity;

    /* Unless you need the memory to be zero'd I would just use malloc here
     * mylist = calloc(capacity, sizeof(struct list)); */
    mylist = malloc(capacity * sizeof(struct list));
    if(mylist == NULL){
        fprintf(stderr, "Could not allocate list\n");
        free(hash); /* free our memory and handle the error*/
        return NULL;
    }

    mylist->head = NULL;
    mylist->size = 0;
    mylist->tail = NULL;    
    hash->list = mylist;

    return hash;
}

Also remember to free you list before you free your hashtable:

free(myhash->list);
free(myhash);