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
– deviantfan, Commented Jan 20, 2014 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
– Elias Van Ootegem, Commented Jan 20, 2014 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
– Lundin, Commented Jan 20, 2014 at 16:24

Community · Accepted Answer · 2017-05-23 11:59:11Z

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, 2017 at 11:59

CommunityBot

11 silver badge

answered Jan 20, 2014 at 15:47

unwind

402k64 gold badges492 silver badges620 bronze badges

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

8 Comments

collinglass Over a year ago

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)

Lundin Over a year ago

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*.

unwind Over a year ago

@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.

Lundin Over a year ago

No, the const keyword implies that the function cannot be modified :)

unwind Over a year ago

@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.

|

Collectives™ on Stack Overflow

Generic programming in C

1 Answer 1

8 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

8 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related