1

Programming a simple singly-linked-list in C, I came about this repository on Github: https://github.com/clehner/ll.c while looking for some examples.
There is the following function (_list_next(void *)): 

struct list 
{
    struct list *next;      // on 64-bit-systems, we have 8 bytes here, on 32-bit-systems 4 bytes.
    void *value[];          // ISO C99 flexible array member, incomplete type, sizeof may not be applied and evaluates to zero.
};

void *_list_next(void *list)
{
    return list ? ((struct list *)list)[-1].next : NULL;   // <-- what is happening here?
}

Could you explain how this works?
It looks like he is casting a void pointer to a list pointer and then subscripting that pointer. How does that work and what exactly happens there?
I don't understand purpose of [-1].

j3141592653589793238
  • 1,810
  • 2
  • 16
  • 38
  • 1
    It seems to be doing something unpleasant. – Oliver Charlesworth Sep 27 '18 at 15:40
  • `a[b]` = `*(a + b)`, like in `char a[5]; char * b = &a[1]; b[-1] == a[0]; `. It's `*( (struct list*)list - 1)`, but i don't know why it does expect, that at `(uintptr_t)list - sizeof(*list)` theres a valid object of the `struct list` type. – KamilCuk Sep 27 '18 at 15:41
  • Sorry, what do you mean by unpleasant? @OliverCharlesworth – j3141592653589793238 Sep 27 '18 at 15:42
  • If you are looking for linked lists examples, look at [sys/queue.h from *bsd systems](https://github.com/zerovm/glibc/blob/master/misc/sys/queue.h) and [man queue.h](https://www.freebsd.org/cgi/man.cgi?query=queue&sektion=3). – KamilCuk Sep 27 '18 at 15:51

1 Answers1

1

This is undefined behavior that happens to work on the system where the author has tried it.

To understand what is going on, note the return value of _ll_new:

void * _ll_new(void *next, size_t size)
{
    struct ll *ll = malloc(sizeof(struct ll) + size);
    if (!ll)
        return NULL;
    ll->next = next;
    return &ll->value;
}

The author gives you the address of value, not the address of the node. However, _list_next needs the address of struct list: otherwise it would be unable to access next. Therefore, in order to get to next member you need to find its address by walking back one member.

That is the idea behind indexing list at [-1] - it gets the address of next associated with this particular address of value. However, this indexes the array outside of its valid range, which is undefined behavior.

Other functions do that too, but they use pointer arithmetic instead of indexing. For example, _ll_pop uses

ll--;

which achieves the same result.

A better approach would be using something along the lines of container_of macro.

Sergey Kalinichenko
  • 714,442
  • 84
  • 1,110
  • 1,523
  • So in other words... the author didn't know what he was doing? – j3141592653589793238 Sep 27 '18 at 15:48
  • 1
    @T.Meyer Oh no, he absolutely knew what he was doing - to be sure, this is a very clever piece of code. Unfortunately, it does something not allowed by the standard. However, the code resulting from compiling this code would almost certainly work because of the way the pointers are represented, and because structure layout allows it. – Sergey Kalinichenko Sep 27 '18 at 15:52
  • Shouldn't he use `container_of(ll, struct ll, value)` ? I guess his code will not work, if `sizeof(void*) != sizeof(struct ll*)` or if there are padding bytes between structure members, right? – KamilCuk Sep 27 '18 at 15:56
  • Result after some hours: I just learned incredibly much from this question. I really think that this piece of code along with you answer brought my C skills and knowledge to a complete new level! I've gone through tons of articles and questions and I really have to say that I love such low-level things. https://stackoverflow.com/questions/35589038/what-exactly-does-the-c-structure-dot-operator-do-lower-level-perspective https://stackoverflow.com/questions/5524552/access-struct-members-as-if-they-are-a-single-array – j3141592653589793238 Sep 29 '18 at 18:13
  • https://stackoverflow.com/questions/1241205/are-all-data-pointers-the-same-size-in-one-platform-for-all-data-types https://stackoverflow.com/questions/7312555/in-c-does-a-pointer-to-a-structure-always-point-to-its-first-member I think these links might be useful for someone like me who just wants to understand the logic behind all this. Finally, sorry for posting such a long comment, but I think it's appropriate or at least worth it. I'd just like to thank you again @dasblinkenlight A lot of things just became clear now. I've never experienced anything like this before! That's awesome! – j3141592653589793238 Sep 29 '18 at 18:18