Creating a map without using a struct as linked list

Question

I have to create a struct for a map in C that contains a char* key and void* value which are stored together internally. Rather than having a linked list as an external struct, I have to allocate memory for a linked list cell which contains the link pointer, the key string, and the value together (contiguous).

The key and value data have to be stored directly in the cell and the cell has to be constructed at runtime. I get the beginning of this which would involve a struct like:

struct example {

    int count_of_list_elem;
    void *list;

}

But I don't know how this is possible w/o using another struct to form the linked list?

Would I have to create some cell within the struct itself, allocate memory to it and pass it three values? I'm just not sure how it would work.

EDIT: I need to use a void* array.

Answer 1

This is a standard way of handling dynamically sized structures in C:

struct example {
    struct example *next;    /* linked list */
    int count_of_list_elem;
    char data[1];
}

struct example *bigone = malloc (sizeof (struct example) + 10000);
if (!bigone)
     // error
bigone -> next = NULL;
bigone -> count_of_list_elem = 10000;
memcpy (bigone -> data, <data source>);

Answer 2

You can declare a struct before you define it, so that you can refer to it within the struct itself:

typedef struct tagMyStruct* my_struct_pointer;
typedef struct tagMyStruct
{
    char* KeyPtr;
    void* ValuePtr;
    my_struct_pointer NextPtr;
}   my_struct;

static my_struct_pointer _listHeadPtr = NULL;

my_struct_pointer AddNewCellToList(char* keyPtr, void* valuePtr)
{
    my_struct_pointer newCellPtr = malloc(sizeof(my_struct));
    newCellPtr->KeyPtr = keyPtr;
    newCellPtr->ValuePtr = valuePtr;
    newCellPtr->NextPtr = _listHeadPtr;
    _listHeadPtr = newCellPtr;
    return(newCellPtr);
}

You will need to malloc appropriate storage for the Key and Value before calling AddNewCellToList.

Answer 3

You can refer to a struct type within its own definition:

struct example {
    int count_of_list_elem;
    void *list;
    struct example *next;
}

Your handle on the whole linked list is just a pointer to the first element:

struct example *head;

You will want to be careful when you create a new node to initialize its next pointer to NULL to indicate that there are (initially) no elements after it.