Passing type as a parameter; generalised linked list in C?

[phalaris_trip]

I was trying to revise my linked list and implement it in C to check if there is a difference in performance... just as a sort of weird hobby..

In the absence of templates I'm trying to figure out how to pass a type as a parameter for this purpose. For example va_arg(arg, int) retrieves an int. I know it's a macro, not a function, but I still can't figure out how this is done.. if I could add this kind of functionality and then store the type somewhere in some variable then I could probably implement the linked list using void pointers.

Alternatively, would it be possible to just use void pointers and sizeof? How would one ensure that the user doesn't start mixing types within the linked list then?

Thanks for any advice, I'm really bored..

[Ancient Dragon]

va_args will be of no help to you because all it does is point to the beginning byte of the stack where a variable of unknown size starts. The program still has to know the data type.

This is how I impleneted a general-purpose linked list

typesed struct node
{
    void * data; // data for this node
    struct node* next;
    struct node* prev;
} LINK;

To insert a node at the head of the linked list.

struct node* insertHead(LINK** head, void* data)
{
      LINK* newNode = malloc(sizeof(LINK));
      newNode->data = data;
      newNode->next = NULL;
      newNode->prev = NULL;
      if( *head == NULL)
           *head = newNode;
     else
     {
         newNode->next = *head;
         *head = newNode;
     }
}

[Luckychap]

I think the node structure should be like this:

struct node {
    void *data;
    int type;
    struct node *next;
    struct node *prev;

}LINK;

where: type is used for type. For example type=1 indicates int, type=2 indicates float, type=3 indicates userdefine and so on...

and Insert function will look like this:

int inser(LINK **head, void data, int type) {
   if(type==1) { // int
      LINK *newnode = (LINK*)malloc(sizeof(LINK));
      newnode->data = malloc(sizeof(int));

   }

and so on......



}

[MonsieurPointer]

I also use void * as a data type to provide "generic" functionality in my linked lists. However, using the code that Ancient Dragon provided

struct node* insertHead(LINK** head, void* data)
    {
    LINK* newNode = malloc(sizeof(LINK));
    newNode->data = data;
    newNode->next = NULL;
    newNode->prev = NULL;
    if( *head == NULL)
    *head = newNode;
    else
    {
    newNode->next = *head;
    *head = newNode;
    }
    }

is highly dangerous, because you are just pointing newNode->data to your data. Once you free data and decide to iterate through the list, an error will likely occur.

To solve this issue I designed function pointers which provide me with the following:
- Copying data (e.g. when creating a node)
- Deleting data (e.g. when a node is deleted)
- Comparing data (e.g. to retrieve or delete node whose data matches that which is passed to the function)
- Printing data (for debugging purposes)

I realize that this leads to a lot of implementation, but it I feel it provides more control and flexibility than using a switch statement and additional data member.

[m4ster_r0shi]

I recently stumbled upon an interesting pdf explaining how you can do OOP in C -> http://www.planetpdf.com/codecuts/pdfs/ooc.pdf

It uses structures like this one to hold the type information in a compact way:

struct Class {

    size_t size;

    void * (* ctor) (void * self, va_list * app);
    void * (* dtor) (void * self);

    void * (* clone) (const void * self);

    int (* differ) (const void * self, const void * b);
};

Maybe skimming it could give you an idea or two.

[MonsieurPointer]

Interesting concept! Thank you for the information!

[Ancient Dragon]

>>is highly dangerous, because you are just pointing newNode->data to your data. Once you free data and decide to iterate through the list, an error will likely occur.

It's certainly true if the programmer doesn't know what the hell he/she is doing. It was assumed the calling function had already allocated memory for data. Another option would have been to add another parameter, such as size_t size and let the function allocate its own memory for the object.

[Narue]

I think the node structure should be like this:

struct node {
    void *data;
    int type;
    struct node *next;
    struct node *prev;

}LINK;

where: type is used for type. For example type=1 indicates int, type=2 indicates float, type=3 indicates userdefine and so on...

and Insert function will look like this:

int inser(LINK **head, void data, int type) {
   if(type==1) { // int
      LINK *newnode = (LINK*)malloc(sizeof(LINK));
      newnode->data = malloc(sizeof(int));

   }
and so on......
}

Um, no. All you're doing is limiting the number of types that the linked list can store. By using pointers to void, you guarantee that it can store any object type past, present, and future. This does place the burden on calling code of making sure that either

1. All pointed to objects have the same type (a homogeneous list) or
2. All pointed to objects have some way of exposing their type (a heterogeneous list)

The latter is what your idea does, but in a limited way. The list of supported types should be managed not by the linked list library, but by the application. This ensures greater re-usability of the library. Since the list contains pointers to void, the application can store pointers to an application-specific structure containing supported type information:

struct typed_data {
    enum supported_types type;
    void *value;
};

Your idea precludes that option as the list wouldn't recognize the typed_data structure.

To solve this issue I designed function pointers which provide me with the following:
- Copying data (e.g. when creating a node)
- Deleting data (e.g. when a node is deleted)
- Comparing data (e.g. to retrieve or delete node whose data matches that which is passed to the function)
- Printing data (for debugging purposes)

Indeed, and that's precisely how I've advocated handling generic container libraries in C (some example implementations can be found under the Libraries heading here). You mentioned that it leads to a lot of implementation, but that's not really the case at all. In fact, the solution is comparable to an explicitly typed implementation:

/* slist.h */
#ifndef SLIST_H
#define SLIST_H

#include <stdbool.h>
#include <stddef.h>

typedef int   (*cmp_f)(const void *p1, const void *p2);
typedef void *(*dup_f)(void *p);
typedef void  (*rel_f)(void *p);

typedef struct slist_node {
    void              *data;
    struct slist_node *next;
} slist_node_t;

typedef struct slist {
    slist_node_t *head; /* Dummy head of the list */
    cmp_f         cmp;  /* Compare two items (user-defined) */
    dup_f         dup;  /* Clone an item (user-defined) */
    rel_f         rel;  /* Destroy an item (user-defined) */
    size_t        size; /* Number of items */
} slist_t;

slist_t *slist_new(cmp_f cmp, dup_f dup, rel_f rel);
void     slist_delete(slist_t *list);
bool     slist_prepend(slist_t *list, void *data);

#endif

/* slist.c */
#include <stdbool.h>
#include <stdlib.h>
#include "slist.h"

slist_t *slist_new(cmp_f cmp, dup_f dup, rel_f rel)
{
    slist_node_t *dummy = malloc(sizeof *dummy);

    if (dummy == NULL)
        return NULL;

    slist_t *list = malloc(sizeof *list);

    if (list == NULL)
        free(dummy);
    else {
        list->head = dummy;
        list->head->data = NULL;
        list->head->next = NULL;

        list->cmp = cmp;
        list->dup = dup;
        list->rel = rel;

        list->size = 0;
    }

    return list;
}

void slist_delete(slist_t *list)
{
    while (list->head != NULL) {
        slist_node_t *next = list->head->next;

        list->rel(list->head->data);
        free(list->head);
        list->head = next;
    }

    free(list);
}

bool slist_prepend(slist_t *list, void *data)
{
    slist_node_t *node = malloc(sizeof *node);

    if (node == NULL)
        return false;

    node->data = list->dup(data);

    if (node->data == NULL) {
        free(node);
        return false;
    }

    node->next = list->head->next;
    list->head->next = node;

    ++list->size;

    return true;
}

/* main.c */
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "slist.h"

char *copy_str(const char *s)
{
    char *ret = malloc(strlen(s) + 1);

    if (ret != NULL)
        strcpy(ret, s);

    return ret;
}

int cmp(const void *p1, const void *p2)
{
    return strcmp((const char*)p1, (const char*)p2);
}

void *dup(void *p) { return copy_str(p); }
void rel(void *p) { free(p); }

int main(int argc, char *argv[])
{
    if (argc < 2) {
        fputs("usage: <prog> <filename>\n", stderr);
        return EXIT_FAILURE;
    }

    FILE *in = fopen(argv[1], "r");

    if (in == NULL) {
        perror("Error opening specified file");
        return EXIT_FAILURE;
    }

    slist_t *list = slist_new(cmp, dup, rel);

    if (list == NULL) {
        fputs("Error generating list\n", stderr);
        fclose(in);
        return EXIT_FAILURE;
    }

    char line[BUFSIZ];

    while (fgets(line, sizeof line, in) != NULL) {
        line[strcspn(line, "\n")] = '\0';

        if (!slist_prepend(list, line)) {
            fprintf(stderr, "Error adding '%s' to the list\n", line);
            break;
        }
    }

    printf("There are %d items:\n", list->size);

    for (slist_node_t *it = list->head->next; it != NULL; it = it->next)
        printf("'%s'\n", (const char*)it->data);

    slist_delete(list);

    return EXIT_SUCCESS;
}

There are a few extra lines in the implementation, plus the user-defined functions in the driver, but otherwise the code isn't much changed from if we used int rather than void* as the stored type.

[MonsieurPointer]

Ah! So your function pointers are defined in the structure... very nice. This is the route I should definitely take!

When I started to code my list library, I was worried about the size of the data structure, so I kept it to a minimum, e.g.:

typedef struct LIST_s
{
[INDENT]void *pData;[/INDENT]
[INDENT]LIST_p_t pNext;[/INDENT]
} LIST_t, *LIST_p_t;

Then, when trying delete a node using void *pData for comparison, extern error_t DeleteNode(LIST_p_t *ppList, void *pData, compare_fn_p_t pCompareFn); would indicate that the function pointer would have to passed each time.

With your method it is more compact and requires a lot less implementation on the user end!