Generic list contains garbage values in C

Question

So I wanted to write a function in C which converts a generic array into a single linked list.

The code I wrote:

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

void insert(Node** root, void* value) {
    Node* new_node = (Node *) malloc(sizeof(Node));
    Node* ptr;
    new_node->value = value;
    new_node->next = NULL;

    if (*root == NULL)
        *root = new_node;
    else {
        ptr = *root;
        while (ptr->next != NULL)
            ptr = ptr->next;
        ptr->next = new_node;
    }
}


Node* arr2list(void* array, size_t length) {
    Node *root = NULL;
    for(int i = 0; i < length; i++) {
        insert(&root,&array[i]);
    }
    return root;
}

I wrote a small test for it:

int main() {
    int arr[] = { 1, 2, 3, 4, 5 };
    int n = sizeof(arr) / sizeof(arr[0]);
    Node* root = arr2list(arr, n);
    while (root != NULL)
    {
        printf("%d,",*(int*) root->value);
        root = root->next;
    }
    return 0;
}

But I get garbage values: -13308,-2145276560,-2145276560,-2145276560,-2145276560,.

I can't seem to find the mistake that leads to those results.

What could be the issue?

@IłyaBursov It says: "error operand of type 'void' where arithmetic or pointer type is required". — vesii, Aug 20 '19 at 18:03
[Using void pointer to an array](//stackoverflow.com/q/8812690) — 001, Aug 20 '19 at 18:03
The first version of the question appears to be correct. Why did you change it? — user3386109, Aug 20 '19 at 18:04
@user3386109 someone suggested to change it (though it was right, but then he removed his comment). Johnny, this is a list not an array though. — vesii, Aug 20 '19 at 18:05
Yup, he was wrong. The problem is in the declaration of `arr2list`. `void *array` should be `int *array`. — user3386109, Aug 20 '19 at 18:11
@user3386109 I would like to create a generic function so I have to use `void*`. — vesii, Aug 20 '19 at 18:12
Yes, I know. The `insert` function is generic. The `arr2list` function does the conversion between a specific type of array, and the generic `insert` function. So `arr2list` cannot be generic. (Unless you get messy as shown in the latest edit to Pascal Cuoq's answer.) — user3386109, Aug 20 '19 at 18:15
vesii, Note: inconsistent to use `size_t length` and `int i`. Choose one type. Recommend `size_t`. — chux - Reinstate Monica, Aug 21 '19 at 01:23

Pascal Cuoq · Answer 1 · 2019-08-20T18:15:54.280

1

Your program contains &array[i] where array has type void* at line 28.

This is not standard C. GCC accepts it and treats the pointer arithmetic as char* arithmetic (arguably a bad idea, in particular because it feeds the confusion in an example such as this one).

Since your function arr2list consumes the array through some misaligned pointers, the results are apparently arbitrary values (that contain some of the bytes of the first array element and some of the bytes of the second array element, for instance).

I would be happy to say that the function arr2list must simply take as argument the length of one element, but this small change alone is not going to be enough in itself to make things work. Your linked list type stores pointers as data, so the function will also need to allocate a block for each of the elements, and store a pointer to this element inside the Node.

If you are content with making the list point to the elements of the array, then forget the above paragraph, you almost have a working solution, just make arr2list take an extra argument size_t elt_size and use (char*)array + elt_size*i instead of &array[i].

edited Aug 20 '19 at 18:15

answered Aug 20 '19 at 18:05

Pascal Cuoq

79,187
7
161
281

I use `C99`. So, how do I replace `&`? – vesii Aug 20 '19 at 18:06
2

@vesii `void*` arithmetic is not defined in any C standard. Not in C89, not in C99 and not in C11. If you are using GCC, try `-std=c99 -pedantic` to get something that resembles a C99 compiler. The problem is not that you are using `&`, it's fundamentally that your function `arr2list` is trying to offset a pointer without knowing the size of the elements it points to. – Pascal Cuoq Aug 20 '19 at 18:09
what do you mean by arithmetic? In the following link you have an example of `void*`: https://www.geeksforgeeks.org/generic-linked-list-in-c-2/ – vesii Aug 20 '19 at 18:12
What I called “`void*` arithmetic” is, in longer terms, “pointer arithmetic using a `void*` pointer”. It's not C. GCC makes it work like “`char*` arithmetic”, or “pointer arithmetic using a `char*` pointer”, which is not what you want. You would have been better served by a compilation error, which a standard C compiler would have provided. – Pascal Cuoq Aug 20 '19 at 18:18
@vesii in other words, your mistake is similar to the mistake in the question https://stackoverflow.com/questions/8812690/using-void-pointer-to-an-array which Johnny Mopp has pointed out in the comments. – Pascal Cuoq Aug 20 '19 at 18:19
@vesii note that the link you provided contains the same solution as my answer, in the form of `size_t data_size` as argument to the function `push`. – Pascal Cuoq Aug 20 '19 at 18:21

Generic list contains garbage values in C

1 Answers1