Linked list with different types

Question

How do I create a list where each element can be of a different type?

What I am doing now is something along these lines:

typedef struct listitem
{
    int flavour;
    void *payload;
    struct listitem *next;
} listitem

And when accessing an item from this list, I check the value of flavour and then cast payload to the appropriate type. This approach seems a bit sledge-hammer to me.

What is the standard way to do this in C99?

Is there someway to infer the type of an object, given only its address?

John Källén · Accepted Answer · 2013-11-22 00:40:50Z

3

No, C doesn't provide you with reflection facilities, i.e. the capability to infer the type of an object based on its address. You're going to have to manage that yourself. You're doing the right thing, but you're going to have to manage the flavour yourself. Others have pointed out how to lessen the pain by putting all the alternative types in a union, so that you don't have to cast all the time. You may be well off writing a few inline functions that hide all the unions and what not. To get an idea:

typedef struct listitem
{
    int flavour;
    union {
        int i;
        char * str;
    };
    struct listitem * next;
};
int int_item(struct listitem * item)
{
    if (flavour != FLAVOUR_INT)
        error("Not an integer");
    return item->i;
}

char * string_item(struct listitem * item)
{
    if (flavour != FLAVOUR_STRING)
        error("Not a string");
    return item->str;
}

edited Nov 22, 2013 at 0:40

answered Nov 22, 2013 at 0:30

John Källén

8,04338 silver badges69 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

Hyperboreus Over a year ago

When I use union will C allocated memory for each member of the union for each listitem I create?

John Källén Over a year ago

You need to be careful about this. The union will contain spaces for primitives (ints, longs, doubles, chars) and pointers to such beasts. But if you need objectts like strings, which vary in size, you will typically have to allocate them separately with malloc() and then free() them from the listitem when you are discarding the list items. You could add a function pointer to your list item that should be called when the listitem is to be discarded. The function pointer would do nothing for primitive types, but call free() for all type that need freeing.

Hyperboreus Over a year ago

Thank you very much. This whole business (especially adding a function pointer for clean-up, why not just call it destructor) sounds like re-inventing OOP from scratch.

John Källén Over a year ago

Indeed; you are in a sense reinventing the C++ CComVariant class of ATL, which wraps the VARIANT struct used by COM. Since you're programming in C, you have to do everything yourself.

Charlie Burns · Accepted Answer · 2013-11-22 00:30:21Z

1

Pointers you can just use a void *. Other types you can use a union:

typedef struct listitem
{
    int flavour; // type of data held
    union {
        int i;
        double d;
        float f;
        :
        :
    };
    struct listitem *next;
} listitem

Sorry, I misread your question. You have manage flavour yourself.

answered Nov 22, 2013 at 0:30

Charlie Burns

7,05623 silver badges29 bronze badges

3 Comments

Hyperboreus Over a year ago

When I use union will C allocated memory for each member of the union for each listitem I create?

Charlie Burns Over a year ago

C will allocate enough memory for the largest member of the union. All of the members of union occupy the same location.

Hyperboreus Over a year ago

Now this is a neat feature. I will look into it in more detail. Thank you.

knarf · Accepted Answer · 2013-11-22 00:55:15Z

1

There's another way.

If you don't have many value for your flavour you can embed it the address. An address aligned to a power of two has its least significant bits to 0. In C11 you have a standard way of allocating aligned memory which can then be used to tag your pointers.

edited Nov 22, 2013 at 0:55

answered Nov 22, 2013 at 0:49

knarf

2,7425 gold badges26 silver badges35 bronze badges

Collectives™ on Stack Overflow

Linked list with different types

3 Answers 3

4 Comments

3 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

4 Comments

3 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related