Using malloc in C to allocate space for a typedef'd type

Question

I'm not sure exactly what I need to use as an argument to malloc to allocate space in the table_allocate(int) function. I was thinking just count_table* cTable = malloc(sizeof(count_table*)), but that doesn't do anything with the size parameter. Am I supposed to allocate space for the list_node_t also? Below is what I am working with.

In the .h file I'm given this signature:

//create a count table struct and allocate space for it                         
//return it as a pointer                                                        
count_table_t* table_allocate(int);

Here are the structs that I'm supposed to use:

typedef struct list_node list_node_t;

struct list_node {
  char *key;
  int value;

  //the next node in the list                                                   
  list_node_t *next;
};

typedef struct count_table count_table_t;

struct count_table {
  int size;
  //an array of list_node pointers                                              
  list_node_t **list_array;
};

Solution 1

count_table* cTable = malloc(sizeof(count_table*))

is wrong. It should be

count_table* cTable = malloc(sizeof(count_table));

Also, you must allocate memory for list_node_t also seperately.

EDIT:

Apart from what Clifford has pointed about allocating memory for the list node, I think the memory allocation should also be taken care for the char *key inside of the list node.

Solution 2

Your suggestion: count_table* cTable = malloc(sizeof(count_table*)) would only allocate space for a pointer to a count_table.

You'd need

count_table* cTable = malloc(sizeof(count_table) ) ;

Each list node would be separately allocated and cTable->size and cTable->list_array and the last list_node_t::next updated accordingly. Maintaining a pointer to the last node added would make adding nodes faster.

I am not sure why count_table::list_array is of type list_node_t** rather than just list_node_t* (and equally called list_array rather than just list). Is it your intention that it is both an array and a list at the same time? That would be somewhat redundant. The member need only be a pointer to the first node, successive nodes are then accessed via list_node::next

Solution 3

Given that the int is a "size" parameter for the created count_table_t, it appears that you are supposed to both allocate the count_table_t itself, as well as initialise its members.

Initialising the list_array member also involves a memory allocation, so it would look like:

count_table_t *table_allocate(int size)
{
    count_table_t *table = malloc(sizeof *table);
    int i;

    table->size = size;
    table->list_array = malloc(size * sizeof table->list_array[0]);
    for (i = 0; i < size; i++)
        table->list_array[i] = NULL;

    return table;
}

However, you also need to check for some error conditions: the multiplication of size by sizeof table->list_array[0] could overflow, and either of the malloc() calls could fail. So the function should actually look like this:

count_table_t *table_allocate(int size)
{
    count_table_t *table;
    int i;

    /* Check for overflow in list allocation size */
    if (size < 0 || size > (size_t)-1 / sizeof table->list_array[0])
        return NULL;

    table = malloc(sizeof *table);

    if (table == NULL)
        return NULL;

    table->size = size;
    table->list_array = malloc(size * sizeof table->list_array[0]);

    if (table->list_array == NULL) {
        free(table);
        return NULL;
    }

    for (i = 0; i < size; i++)
        table->list_array[i] = NULL;

    return table;
}

(Note that (size_t)-1 is a constant equal to the maximum value of a size_t, which is the type of the parameter to malloc()).

Solution 4

In addition to the other posters who point out that you're only allocating enough space for the pointer, not the space the data you want will occupy, I strongly urge you to do things like this:

count_table* cTable = malloc(sizeof(*cTable));

This will help you in case the type of cTable ever changes, you won't have to adjust two parts to that line, just the type.

View more solutions

Comments

[user516888]

so in the function I should probably malloc the count_table and then malloc space for the list_node_t and then put that list node inside the count_table? Am I getting this right?

[Jay]

Yes. You are getting this right. : ) But, please refer to Clifford's answer about your double pointer usage for list_node_t. You need to check why is it given as a double pointer there. Thanks!

[Clifford]

@detley: No I mean :: because the left-hand-side is a type not an instance. I am using C++ scope notation, though it is not intended that this is code, I am simply using it as a notation to refer to a member of a struct rather than member of an instance of a struct. There is no syntactic way of doing that in C.

[user516888]

what you are saying makes a lot of sense. as for the (int size) parameter... do you think it is intended that I add that many nodes to the count_table in that function? I don't understand what the size parameter is for.

[Jonathan Leffler]

I think the idea is that there is an array of lists, so that when a node is hashed, you look in the relevant array entry, then trundle down a singly linked list. That at least makes sense of the data structures.

[visual_learner]

+1 but I would write count_table* cTable = malloc(sizeof *cTable); personally.

[visual_learner]

Note also that the OP's int counts should all probably be size_ts.

[caf]

@Chris Lutz: Agreed (and that would remove the need for the < 0 check), but it sounds like the function signature and struct definition were handed-down requirements.

[Clifford]

@Jonathan Leffler: That sounds likely.

[Jay]

@Chris Lutz & Clifford, I do agree with your ideas about this. But, also many a times I have seen people make a typo error and miss the '*' thereby causing only 4 bytes to be allocated. This problem leads to troubles hard to find in a big code. So, am a little confused about this.