Creating generics with typedef in C

Question

I'm doing my hw in C right now and we were given the code below in lecture to create generic types. In C++, I know you can achieve this by just using templates. Our instructor wants us to use these (so no void* for now I don't think). However, I'm confused as to how I can declare this.

typedef struct Cell(x) *List(x);

struct Cell(x) {
   x* data;
   List(x) next;
};

So, I know whenever the compiler sees List(x), it will substitute in struct Cell(x), so I tried doing List(int) a; in main(), but that doesn't work

Answer 1

There is a way you can fake templates for generics like containers in C with macros. You must write two macros that generate declarations and the definition of a new struct type and the functions acting on this type.

For example for an (incomplete) list type:

#define DECLARE_LIST(T_Name, T_Tag, T_Type)         \
                                                    \
    typedef struct T_Name##Node T_Name##Node;       \
    typedef struct T_Name T_Name;                   \
                                                    \
    struct T_Name {                                 \
        T_Name##Node *head;                         \
        T_Name##Node *tail;                         \
        int count;                                  \
    };                                              \
                                                    \
    struct T_Name##Node {                           \
        T_Type value;                               \
        T_Name##Node *next;                         \
    };                                              \
                                                    \
    int T_Tag##_init(T_Name *ll);                   \
    int T_Tag##_free(T_Name *ll);                   \
    int T_Tag##_add(T_Name *ll, T_Type x);

#define DEFINE_LIST(T_Name, T_Tag, T_Type)          \
                                                    \
    int T_Tag##_init(T_Name *ll)                    \
    {                                               \
        ll->head = ll->tail = NULL;                 \
        ll->count = 0;                              \
        return 0;                                   \
    }                                               \
                                                    \
    int T_Tag##_free(T_Name *ll)                    \
    {                                               \
        while (ll->head) {                          \
            T_Name##Node *next = ll->head->next;    \
            free(ll->head);                         \
            ll->head = next;                        \
        }                                           \
        return 0;                                   \
    }                                               \
                                                    \
    int T_Tag##_add(T_Name *ll, T_Type x)           \
    {                                               \
        T_Name##Node *nd = malloc(sizeof(*nd));     \
                                                    \
        if (nd == NULL) return -1;                  \
        nd->next = NULL;                            \
        nd->value = x;                              \
                                                    \
        if (ll->head == NULL) {                     \
            ll->head = ll->tail = nd;               \
        } else {                                    \
            ll->tail->next = nd;                    \
            ll->tail = nd;                          \
        }                                           \
        ll->count++;                                \
                                                    \
        return 0;                                   \
    }

#define IMPLEMENT_LIST(T_Name, T_Tag, T_Type)       \
    DECLARE_LIST(T_Name, T_Tag, T_Type)             \
    DEFINE_LIST(T_Name, T_Tag, T_Type)              \

If you want to declare a new List type, you should DECLARE_LIST in a header and DEFINE_LIST in the C source. If the type is private to the compilation module, you can just place IMPLEMENT_LIST in the C source.

(The macro is incomplete, because it implements only three functions for the type, which are useless on their own. This is just to show the basic workings. You will usually end up with two huge macros.)

You can use the macro like this:

IMPLEMENT_LIST(Intlist, il, int)
IMPLEMENT_LIST(Stringlist, sl, char *)

This creates two new list types, Intlist and Stringlist, together with the according functions, prefixed il_ and sl_, which you can use like other functions:

int main()
{
    Intlist il;
    Stringlist sl;

    il_init(&il);
    sl_init(&sl);

    il_add(&il, 1);
    il_add(&il, 2);
    il_add(&il, 5);

    sl_add(&sl, "Hello");
    sl_add(&sl, "World");

    // ... more stuff ...

    il_free(&il);
    sl_free(&sl);

    return 0;
}

This method is type safe: You can't pass a Stringlist to an il function, for example. Because the code consists only of macros, you can implement it in a header file.

There are restrictions, though:

• Assignment is via =. That means that the string list for example can't keep a copy in a char array. If the client code copies data, the clean-up code doesn't know about it. You can cater for such cases by specifying copy, comparison, constructor and destructor functions (which can also be macros) as macro arguments, but this will quickly become complicated.

• There are "secret" type names involves like the node type in the example above. They must be valid identifiers (as opposed to C++, where the compiler creates mangles names), which might lead to surprising name clashes.

• When you use a private implementation, the functions aren't static as they ought to be.

It has the advantage, that Stringlist is a nicer name than std::list<std::string>, though.

Answer 2

New versions of C added "type-generic expressions", allowing for example the abs function to do different things with different argument types.

But as far as I know, there are still no generic types. Your choices for implementing collection types:

1. Give up type-safety, using void*
2. Type out the collection / container code for each element type.
3. Use macros to generate the same code as #2.

I suspect you're intended to do #3. Something along the lines of:

#define Cell(x) specialized_##x##_Cell
#define List(x) specialized_##x##_List

#define SINGLY_LINKED_LIST(x) \\
     typedef struct Cell(x) *List(x); \\
     struct Cell(x) \\
     { \\
          x* data; \\
          List(x) next; \\
     };

and then you can use it like

SINGLY_LINKED_LIST(int)

int main(void)
{
    List(int) a;
}