Is it possible to write a generic traverse function in C for different list structures so long as they contain the "next" field?

Question

First time asking a question but I did look around Google and stackoverflow to see if someone has asked something similar before. In malloc, recasting and free, it looked like the OP asked something similar for example. But it was more complicated.

I was wondering whether it's possible to create a generic function for a list structure in C that traverses the list given that you know that the different types of structures will always have a "next" field.

For example, given these two list-type structures:

typedef struct _list1 {
    int value;
    list1 *next;
} list1;

typedef struct _list2 {
    int value;
    char *string;
    list2 *next;
} list2;

Is it possible to create a generic void freeList((void *) list) function or something which looks something like the below? I am aware it's a simple thing to write both free functions for each individual list separately.

void freeList((void *) list) {
    // Included this because the structs would have different sizes
    // so I thought it would be possible to cast it in order to properly dereference the field.
    if (sizeof *list == sizeof list1)
        *list = (list1) list;
    else if (sizeof *list == sizeof list2)
        *list = (list2) list;

    if (!list) return;
    else {
        free(list->next);
        free(list);
    }
}

So far, my experiments with the code shown above didn't fare well given that gcc would complain about dereferencing a void * pointer.

Answer 1

Making a heterogeneous list can be achieved by the use of a tagged union, or just a tag and casting:

struct list_item {
    struct list_item *next;
    enum datatype type;
    void *contents;
};

or

struct list_item {
    struct list_item *next;
    enum datatype type;
    union {
       int some_int;
       char some_char;
    } contents;
};

Then while traversing the list you just have to verify the type stored in type before using the contents of the element.

---

This check:

if (sizeof *list == sizeof list1)
    *list = (list1) list;
else if (sizeof *list == sizeof list2)
    *list = (list2) list;

doesn't work because sizeof is a static construct: its value is defined at compilation time. You're just asking for the sizeof void.

Answer 2

is it possible to create a generic function for a list structure in C that traverses the list given that you know that the different types of structures will always have a "next" field.

Yes, as mentioned before; you must be careful that every structure starts with the "next" field; the two structures in your post should therefore be reordered like this:

typedef struct _list1 {
    list1 *next;
    int value;
} list1;

typedef struct _list2 {
    list2 *next;
    int value;
    char *string;
} list2;

It is not clean code, because the compiler could reorder (and pad) the fields of the structure, but in general it should work.

Is it possible to create a generic void freeList((void) *list) function or something which looks something like...

This is possible if your structs do not refer malloced memory; or they do, but in a uniform (and known) way (note the first case is a sub-case of this last).

If the structs contain pointers pointing to memory that has to be freed, in fact, while freeing the struct the freeList() function should also free the referenced memory. A few solutions come to my mind:

1 - If all the different structs contain the same "pointers" layout, the routine can free those pointers in a uniform manner, knowing in advance what to do. In such scenario, one can also use pointer fields that are not used by all the structs, but only some.

2 - Every single instance of a struct could contain some helper field describing the pointer's layout. For example, just after the "next" field, another "mempntcnt" field could tell how many pointers (to be freed) follow the "next" field. Or, this "mempntcnt" could be passed as a parameter to freeList().

3 - This problem could be managed by a totally separated mechanism, outside the scope of freeList(). Much depends on the final usage: I mean, for a given (kind of) linked list, first call a routine that frees all the memory referenced by the list itself, then free the list by calling the common freeList(). After all, if different structs are needed, then different routines are used on them...

I hope I've been clear enough...

Answer 3

If you ensure that the next pointer is the first member of the struct then this is possible.

typedef struct list1 {
    // next pointer must be first
    struct list1 *next;
    int value;
} list1;

typedef struct list2 {
    // next pointer must be first
    struct list2 *next;
    int value;
    char *string;
} list2;

void freeList(void *list) {
    if (list) {
        freeList(*(void**)list);
        free(list);
    }
}