Generic programming in C

Question

I am writing a generic linked list implementation in pure C.

struct Node {
    void *value;
    struct Node *next;
};

struct LinkedList {
    struct Node *start;
    struct Node *end;
};

void LinkedList_new(struct LinkedList* llist) {
    llist->start = 0;
    llist->end = 0;
    return;
}

void addNode( struct LinkedList *ll, void *_value ) {
    if ( NULL == ll->start ) {
        ll->start = (struct Node *) malloc( sizeof(struct Node) );
        ll->end = ll->start;
    } else {
        ll->end->next = (struct Node *) malloc( sizeof(struct Node) );
        ll->end = ll->end->next;
    }
    ll->end->value = _value;
    return;
};

This all works great. My problem is when I get to printing value to the screen. I can't seem to find a generic implementation for printing.

Is there a way to determine the TYPE allocated to void *? (And then just do conversion using a switch statement)

void printFunc(int aInt) {
    char str[15];
    sprintf(str, "%d", aInt);
    printf(str);
}

This is an implementation that works for int. Worst case I was thinking was writing a different function for each TYPE. Is this really my only route when using void *?

Is there a better way to do this?

You could use user-supplied function (per function pointer). Like there could be a function to compare for sorting. — deviantfan, Jan 20 '14 at 15:48
Don't cast the return value of `malloc`... if you're going generic: a void pointer is all you'll ever need — Elias Van Ootegem, Jan 20 '14 at 15:55
For a generic linked-list to actually be a meaningful container ADT, you will need to store the actual data inside it, and not just pointers. This means that you will have to update the `Node` type with a size-in-bytes parameter. And then hard copy the data to/from the linked list whenever a node is created/deleted/searched for. — Lundin, Jan 20 '14 at 16:24

score 18 · Accepted Answer · edited May 23 '17 at 11:59

18

No, there's no way to figure that out from the pointer alone. That would require type information to be stored at some well-defined location in all run-time structures, which is simply not how C uses the machine.

The common solution is for the user of the datatype to provide the print function that the application needs, since the application will know the type of data being stored. That is, there is usually an iteration function that takes a function pointer, calling the user's function (which might print the element) on each element of the list.

Here's how such a function could look:

void LinkedList_foreach(const LinkedList *start,
                        bool (*func)(void *element, void *data), void *data);

The above should call func() for each element of the list, passing it the element's data and the additional user-supplied data pointer which can be used by the caller to maintain state for the traversal. The callback func() should return false to stop the iteration, true to keep going.

To print an integer, assuming the integers are stored in the pointers, you could have:

static bool print_int(void *element, void *data)
{
  printf("%d\n", (int) element);
  return true;
}

Also, please don't cast the return value of malloc() in C.

edited May 23 '17 at 11:59

Community

1
1

answered Jan 20 '14 at 15:47

unwind

391,730
64
469
606

If I understand correctly, the developers need to write the print function to use the exact datatype they are using? For the implementation I wrote, I tested the int function with the ```void *``` after I posted this and it didn't work. Is there a way to safely type cast void to say ```int *```? (and eventually others) – collinglass Jan 20 '14 at 15:52
For readability, `typedef` the function pointer. For example `typedef bool (print_func_t)(void *element, void *data);`. And then pass the function pointer to the function as a `const print_func_t*`. – Lundin Jan 20 '14 at 16:27
@Lundin Sure, that's commonly done. Wouldn't make it a `const` pointer though, since that implies functions can be modified which they can't. – unwind Jan 20 '14 at 16:30
No, the const keyword implies that the function _cannot_ be modified :) – Lundin Jan 20 '14 at 16:46
1

@Lundin I know; I meant that writing it *without* `const` implies that the function can be modified, which it can't, so the `const` adds nothing. – unwind Jan 20 '14 at 16:47
With the typedef as I wrote it, it is perhaps not obvious to the reader that the passed type is a function pointer. Whether or not C actually allows you to modify the contents of a function pointer (by abusing the non-const type, like for example the UB you get when you try to access the contents of a string literal), I have no idea. – Lundin Jan 20 '14 at 16:52
Okay, I will give you the right answer. I am learning C, it is interesting the way generics are implemented. – collinglass Jan 21 '14 at 03:05
It is still not clear to me the role of void*data in your print_int .... It is not even used. Can you clarify? – johnbakers Jan 09 '16 at 16:51

Generic programming in C

1 Answers1