Generic linked list print and add by value in C

user_10260064 0
Viewed 832

My goal is to write a simple generic linked list.

  1. I do not know how to create a perfect listPrint function because printf have to get the type of that value, plus I have to cast ptr->data to the appropiate format. Currently I can print just int, printf("%i ",*((int*)ptr->data)). How could I print any type of value like int,float,char..?

  2. when I pushBack to the list I have to create an int* i and then listPushBack(list,&i), but I would like to do this way listPushBack(list,101). I know that if I do the stuff like this I have to do this way, but what should I change in my code to allow me to listPushBack(list,101).

The elements stored in a given list will be the same type (list of int, list of double, list of struct WhatEver*, etc)

list.c

struct node {
    void* data;
    struct node* next;
    struct node* prev;
    size_t typeSize;
};
struct list {
    struct node* head;
    struct node* tail;
    size_t elementSize;
};
node* nCreate(void* data, size_t typeSize) {
    node* nNode = malloc(sizeof(node));
    nNode->data = malloc(typeSize);
    memcpy(nNode->data, data, typeSize);
    nNode->prev = nNode->next = NULL;
    nNode->typeSize = typeSize;
    return nNode;
}
list* listCreate(size_t typeSize) {
    list* l = malloc(sizeof(l));
    l->head = l->tail = NULL;
    l->elementSize = typeSize;
    return l;
}
void listPushBack(list* l, void* val) {
    node* newNode = nCreate(val,l->elementSize);
    ...
}
void listPrint(list* l) {
    node* ptr = l->head;
    do {
        printf("%i ",*((int*)ptr->data));
    } while((ptr = ptr->next) != NULL);
    printf("\n");
}

main

int main() {
    list* list = listCreate(sizeof(int));
    int* i = 10;
    listPushBack(list,&i);
    listPrint(list);
    return 0;
}
linked-list list c
4 Answers

For printing, you can include a function pointer in struct list which can be called to print the element. This can be set to a user defined function which will know how to print that specific type.

To do something like listPushBack(list,101), you'll need to create a wrapper function, i.e. listPushBackInt which takes an int as the second parameter, then pass the address of that parameter to the listPushBack.

So now your list struct would look like this:

struct list {
    struct node* head;
    struct node* tail;
    size_t elementSize;
    void (*elementPrint)(void *);
};

And your print function would do this:

void listPrint(list* l) {
    node* ptr = l->head;
    do {
        l->elementPrint(ptr->data);   // use function pointer
    } while((ptr = ptr->next) != NULL);
    printf("\n");
}

Now your list create function would take a parameter to set the function pointer:

list* listCreate(size_t typeSize, void (*print)(void *)) {
    list* l = malloc(sizeof(l));
    l->head = l->tail = NULL;
    l->elementSize = typeSize;
    l->elementPrint = print;   // set function pointer
    return l;
}

Now to create a list of int, you first create the printing function:

void printInt(void *data)
{
    printf("%i ", *(int*)data);
}

Then you create the list like this:

listCreate(sizeof(int), printInt);

And then you can create this wrapper function:

void listPushBackInt(list* l, int val)
{
    listPushBack(l, &val);
}

To insert int values like this:

listPushBackInt(l, 101)
user_16871190

Preamble

The way I'd do it uses function pointers and an 'apply' function that is given a list, a function pointer, and some (generic) data that is passed to the function pointer along with the pointer to the data in a list node.

The apply function sorts out the problem with how to print the contents of the list (although the code shown below has two apply functions, for applying the data in forward order of the list and in reverse order of the list).

You ask about being able to provide values instead of having to pass a pointer to the listPushBack() function. There isn't an easy way to do it other than by providing cover functions per type. Thus you could have:

static inline void listPushBack_int(list *lp, int i)
{
    listPushBack(lp, &i);
}

and similarly for any other type.

Bug in the code in the question

Note that the code in the question has a bug in the memory allocation — in listCreate(), you have:

list* l = malloc(sizeof(l));

and you need:

list *l = malloc(sizeof(*l));

genlist.h

Here is the header. Note that the struct list type, aka list, is opaque; the code using the header does not know anything about the internals of the structure type, and all access is via the functions defined in the code. I renamed listPushBack() to listPushTail() and added listPushHead(). I added listApplyForward() and listApplyReverse() and listDestroy(). I deleted listPrint() because it isn't generic and cannot easily be made generic.

#ifndef GENLIST_H_INCLUDED
#define GENLIST_H_INCLUDED

#include <stddef.h>         /* size_t */

typedef struct list list;

typedef void (*Apply)(const void *vp, void *thunk);

extern list *listCreate(size_t typeSize);
extern void listDestroy(list *lp);

extern void listPushHead(list *lp, void *val);
extern void listPushTail(list *lp, void *val);

extern void listApplyForward(const list *lp, Apply apply, void *thunk);
extern void listApplyReverse(const list *lp, Apply apply, void *thunk);

#endif /* GENLIST_H_INCLUDED */

This is clearly not a complete list interface — it is very much a bare-bones set of functions. It doesn't have code to access individual elements in the list, or retrieve values in the list, or remove values from the list, or … However, such functions can be designed and added as appropriate.

genlist.c

The node type is completely hidden too, so the nodeCreate() function (renamed from nCreate()) is static. Arguably, there should be a nodeDestroy() function too — but it is subsumed into the code inside listDestroy().

#include "genlist.h"
#include <assert.h>     /* DEBUG */

#ifdef DEBUG
#include <inttypes.h>   /* DEBUG */
#include <stdio.h>      /* DEBUG */
#endif /* DEBUG */
#include <stdlib.h>
#include <string.h>

typedef struct node node;

struct node
{
    void    *data;
    node    *next;
    node    *prev;
};

struct list
{
    node    *head;
    node    *tail;
    size_t  elementSize;
};

static node *nodeCreate(void *data, size_t typeSize)
{
    node *np = malloc(sizeof(node));
    assert(np != NULL);
    np->data = malloc(typeSize);
    assert(np->data != NULL);
    memcpy(np->data, data, typeSize);
    np->prev = np->next = NULL;
#ifdef DEBUG
    printf("Node: %zu: %.12" PRIXPTR ",%.12" PRIXPTR ",%.12" PRIXPTR "\n",
            typeSize, (uintptr_t)np, (uintptr_t)np->prev, (uintptr_t)np->next);
    fflush(stdout);
#endif /* DEBUG */
    return np;
}

list *listCreate(size_t typeSize)
{
    list *lp = malloc(sizeof(*lp));
    assert(lp != NULL);
    lp->head = lp->tail = NULL;
    lp->elementSize = typeSize;
#ifdef DEBUG
    printf("List: %zu: %.12" PRIXPTR ",%.12" PRIXPTR ",%.12" PRIXPTR "\n",
            lp->elementSize, (uintptr_t)lp, (uintptr_t)lp->head, (uintptr_t)lp->tail);
    fflush(stdout);
#endif /* DEBUG */
    return lp;
}

void listDestroy(list *lp)
{
    assert(lp != NULL);
#ifdef DEBUG
    printf("Destroy List: %zu: %.12" PRIXPTR ",%.12" PRIXPTR ",%.12" PRIXPTR "\n",
            lp->elementSize, (uintptr_t)lp, (uintptr_t)lp->head, (uintptr_t)lp->tail);
    fflush(stdout);
#endif /* DEBUG */
    node *np = lp->head;
    while (np != NULL)
    {
#ifdef DEBUG
        printf("Destroy Node: %.12" PRIXPTR ",%.12" PRIXPTR ",%.12" PRIXPTR "\n",
                (uintptr_t)np, (uintptr_t)np->prev, (uintptr_t)np->next);
        fflush(stdout);
#endif /* DEBUG */
        node *next = np->next;
        free(np->data);
        free(np);
        np = next;
    }
    free(lp);
}

void listPushTail(list *lp, void *val)
{
    node *newNode = nodeCreate(val, lp->elementSize);
    if (lp->head == NULL)
    {
        lp->head = newNode;
        lp->tail = newNode;
    }
    else
    {
        lp->tail->next = newNode;
        newNode->prev = lp->tail;
        lp->tail = newNode;
    }
}

void listPushHead(list *lp, void *val)
{
    node *newNode = nodeCreate(val, lp->elementSize);
    if (lp->head == NULL)
    {
        lp->head = newNode;
        lp->tail = newNode;
    }
    else
    {
        lp->head->prev = newNode;
        newNode->next = lp->head;
        lp->head = newNode;
    }
}

void listApplyForward(const list *lp, Apply apply, void *thunk)
{
    node *ptr = lp->head;
    while (ptr != NULL)
    {
        // apply(ptr->data, thunk);
        (*apply)(ptr->data, thunk);
        ptr = ptr->next;
    }
}

void listApplyReverse(const list *lp, Apply apply, void *thunk)
{
    node *ptr = lp->tail;
    while (ptr != NULL)
    {
        // apply(ptr->data, thunk);
        (*apply)(ptr->data, thunk);
        ptr = ptr->prev;
    }
}

The functions other than the 'apply' functions are straight-forward implementations of a doubly-linked list with null pointers marking the end of the list (other designs are possible, using circular lists, for example).

The functions listApplyForward() and listApplyReverse() iterate through the list, calling the function designated by the apply argument with the pointer to the data for the current node and the thunk — a pointer to arbitrary data that the called function knows what to do with. (The dictionary definition of 'thunk' isn't helpful; the Wikipedia definition of Thunk is more nearly on target but applies to a function (subroutine) rather than data. However, the man pages for (macOS and) FreeBSD qsort_r() use the name thunk with the same sense that I do — a generic data pointer passed to a callback function.)

I still prefer the explicit, pre-standard notation (*pointer)(arg1, …) when calling a function via a function pointer. People who learned C more recently may legitimately prefer to use pointer(arg1, …) instead. That notation didn't work when I learned C.

The code contains some debug code that I used while I was tracking down the misallocation problem. Arguably, the printing should be to stderr rather than stdout, but adding fflush(stdout) was sufficient for my purposes.

Note that this code assumes that you can safely make a bitwise copy of the data without running into ownership issues. That means it will work OK for structures that don't contain pointers, for example — but would fail horribly if the copied data contains pointers to dynamically allocated memory, or to local variables in the calling function, or even pointers to locations within the structure. You can devise more complex schemes for copying data. For example, you might pass a 'copy constructor' function pointer and a 'destructor' to the list creation function, and record those in list structure and use them when adding a node to the list or removing a node from the list, etc. OTOH, they're often unnecessary — bitwise copy often works for the structures embedded in lists — so you may end up with a couple of 'generic list' types, for data types which need more or less memory management.

main.c

This code exercises the public interface to the functions in genlist.[ch]. It creates a list of int and uses a function print_int() to print the data, and another function sum_int() to show how you could sum the elements in the list. It also creates a list of double, and uses a function print_dbl() to print the data, and calculates the value of value1 / value2 * value3 / value …, mainly to demonstrate a non-trivial user-defined structure type being used to control a calculation. This produces a different answer depending on whether the list is traversed forwards or backwards.

The code uses rand() to generate random numbers. It deliberately does not use srand(time(0)) or equivalent to change the sequence — for debugging work, the stability of the same numbers each time was more valuable.

#include "genlist.h"
#include <stdio.h>
#include <stdlib.h>
#include <inttypes.h>

static void print_int(const void *data, void *thunk)
{
    FILE *fp = thunk;
    fprintf(fp, " %d", *(int *)data);
}

static void print_dbl(const void *data, void *thunk)
{
    FILE *fp = thunk;
    fprintf(fp, " %7.3f", *(double *)data);
}

static void int_sum(const void *data, void *thunk)
{
    int *sum = thunk;
    *sum += *(int *)data;
}

typedef struct DblFun
{
    double val;
    int    idx;
} DblFun;

static void dbl_fun(const void *data, void *thunk)
{
    DblFun *dp = thunk;
    double val = *(double *)data;
    if (dp->idx == 0)
        dp->val = val;
    else if (dp->idx % 2 == 1)
        dp->val /= val;
    else
        dp->val *= val;
    dp->idx++;
}

int main(void)
{
    list *l1 = listCreate(sizeof(int));
    for (int i = 0; i < 10; i++)
    {
        //int j = 300 + i;
        //listPushTail(l1, &j);
        listPushTail(l1, &i);
        printf("List forward: ");
        listApplyForward(l1, print_int, stdout);
        putchar('\n');
        printf("List reverse: ");
        listApplyReverse(l1, print_int, stdout);
        putchar('\n');
    }
    int sum = 0;
    listApplyForward(l1, int_sum, &sum);
    printf("Sum = %d\n", sum);
    listDestroy(l1);

    list *l2 = listCreate(sizeof(double));
    for (int i = 0; i < 10; i++)
    {
        double d = (rand() % 20000) / 100.0 - 100.0;
        listPushHead(l2, &d);
        printf("List forward: ");
        listApplyForward(l2, print_dbl, stdout);
        putchar('\n');
        printf("List reverse: ");
        listApplyReverse(l2, print_dbl, stdout);
        putchar('\n');
    }
    DblFun d1 = { 0.0, 0 };
    DblFun d2 = { 0.0, 0 };
    listApplyForward(l2, dbl_fun, &d1);
    listApplyReverse(l2, dbl_fun, &d2);
    printf("Fwd: %13.6g, Rev: %13.6g\n", d1.val, d2.val);
    listDestroy(l2);

    return 0;
}

Test output

For a doubly-linked list, it is valuable to be able to test the chains of links both forwards and backwards. And printing the list as it is built reassures that it works in degenerate cases too.

List forward:  0
List reverse:  0
List forward:  0 1
List reverse:  1 0
List forward:  0 1 2
List reverse:  2 1 0
List forward:  0 1 2 3
List reverse:  3 2 1 0
List forward:  0 1 2 3 4
List reverse:  4 3 2 1 0
List forward:  0 1 2 3 4 5
List reverse:  5 4 3 2 1 0
List forward:  0 1 2 3 4 5 6
List reverse:  6 5 4 3 2 1 0
List forward:  0 1 2 3 4 5 6 7
List reverse:  7 6 5 4 3 2 1 0
List forward:  0 1 2 3 4 5 6 7 8
List reverse:  8 7 6 5 4 3 2 1 0
List forward:  0 1 2 3 4 5 6 7 8 9
List reverse:  9 8 7 6 5 4 3 2 1 0
Sum = 45
List forward:   68.070
List reverse:   68.070
List forward:   52.490  68.070
List reverse:   68.070  52.490
List forward:    0.730  52.490  68.070
List reverse:   68.070  52.490   0.730
List forward:  -63.420   0.730  52.490  68.070
List reverse:   68.070  52.490   0.730 -63.420
List forward:  -10.700 -63.420   0.730  52.490  68.070
List reverse:   68.070  52.490   0.730 -63.420 -10.700
List forward:   12.720 -10.700 -63.420   0.730  52.490  68.070
List reverse:   68.070  52.490   0.730 -63.420 -10.700  12.720
List forward:  -24.560  12.720 -10.700 -63.420   0.730  52.490  68.070
List reverse:   68.070  52.490   0.730 -63.420 -10.700  12.720 -24.560
List forward:    8.780 -24.560  12.720 -10.700 -63.420   0.730  52.490  68.070
List reverse:   68.070  52.490   0.730 -63.420 -10.700  12.720 -24.560   8.780
List forward:   79.230   8.780 -24.560  12.720 -10.700 -63.420   0.730  52.490  68.070
List reverse:   68.070  52.490   0.730 -63.420 -10.700  12.720 -24.560   8.780  79.230
List forward:   77.090  79.230   8.780 -24.560  12.720 -10.700 -63.420   0.730  52.490  68.070
List reverse:   68.070  52.490   0.730 -63.420 -10.700  12.720 -24.560   8.780  79.230  77.090
Fwd:      -27.7014, Rev:    -0.0360992

This code is available in my SOQ (Stack Overflow Questions) repository on GitHub as files genlist.h, genlist.c and main.c in the src/so-6529-2945 sub-directory.

user_151680

For the first point, I'm afraid that there is no other solution than storing the type in the list and using a switch when printing. For the second point, one possible solution would be to use an union instead of a void (naturally you can add any type you need in the union and in the function computing the type size) :

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

 union Value {
    int i;
    long long l;
    float f;
    double d;
};

static inline size_t sizeForType(char type) {
    switch(type) {
        case 'i': case 'f':  return 4;
        case 'l': case 'd': return 8;
        default: return 0;
    }
}

struct node {
    union Value data;
    struct node* next;
    struct node* prev;
};
struct list {
    struct node* head;
    struct node* tail;
    char type;
};
struct node* nCreate(union Value data, char type) {
    struct node* nNode = malloc(sizeof(*nNode));
    size_t size = sizeForType(type);
    nNode->data = data;
    nNode->prev = nNode->next = NULL;
    return nNode;
}

struct list* listCreate(char type) {
    struct list* l = malloc(sizeof(*l));
    l->head = l->tail = NULL;
    l->type = type;
    return l;
}

void listPushBack(struct list* l, union Value data) {
    struct node* newNode = nCreate(data, l->type);
    if (!l->head) l->head = newNode;
    if (!l->tail) l->tail = newNode;
    else {
        newNode->prev = l->tail;
        l->tail->next = newNode;
        l->tail = newNode;
    }
}

void listPrint(struct list* l) {
    struct node* ptr = l->head;
    if (!ptr) { printf("Empty list\n"); return; }
    do {
        switch(l->type) {
            case 'i': printf("%d ", ptr->data.i);    break;
            case 'l': printf("%lld ", ptr->data.l);  break;
            case 'f': printf("%f ", ptr->data.f);    break;
            case 'd': printf("%f ", ptr->data.d);    break;
        }
    } while((ptr = ptr->next) != NULL);
    printf("\n");
}

int main() {
    struct list* list = listCreate('i');
    union Value v = { .i = 10 };
    listPushBack(list, v);
    v.i = 11;
    listPushBack(list, v);
    v.i = 12;
    listPushBack(list, v);
    listPrint(list); //==> 10, 11, 12
    return 0;
}

Don't forget to free the allocated memory, I didn't do it.

user_21645730

Regarding printing the list: You could allow your print function to receive a function pointer that prints a data item, or at least produces a c-string style representation of it.

Such an approach is not uncommon. In fact, Gnome's glib uses this type of system. Here is an example from their hash table API: https://developer.gnome.org/glib/stable/glib-Hash-Tables.html

Notice how they make extensive use of function pointers.

You could apply this pattern to your push scenario, as well.

To summarize: The list nodes need only a void *data member. Type information can be handled using helper functions.

Edit 1: I didn't read your second point correctly, so I'd like to add clarification in case it's needed. The list will always store data as a (void *), which means two things: (1) The list won't ever know what data is being stored, (2) the caller must cast the data as a (void *). This is a non-issue due to the use of the helper function pointers the list processing functions can make use of.

user_135706160
Related