Pointer Arithmetic For Intrusive Linked List

Question

I've been looking at this intrusive linked list implementation in C, and there is some pointer arithmetic that I cannot seem to piece together.

Firstly there is this function and macro which initiate a link node:

#define LINK_INIT(linkptr, structure, member) \
  link_init(linkptr, offsetof(structure, member))

void link_init(link *lnk, size_t offset) {
  lnk->next = (void*) ((size_t) lnk + 1 - offset);
  lnk->prev = lnk;
}

I understand that lnk->next (void*) ((size_t) lnk + 1 - offset) is a pointer to the next struct in the linked list, but I don't understand why adding 1 allows the pointer to work still when the offset is number of bytes offsetting the member from the start of the struct. In the struct header definition the author says that the low bit is used as a sentinel to signify the end of the list, and so the lnk->next pointer can be &'d with 1 to test for the end:

// All nodes (=next) must be allocated on (at least) two-byte boundaries
// because the low bit is used as a sentinel to signal end-of-list.
typedef struct link {
  struct link *prev; 
  void *next;
} link;

void* link_next(link *lnk) {
  if ((size_t) lnk->next & 1)
    return NULL;
  return lnk->next;
}

I'm just wondering why this works at all? I vaguely understand allocation boundaries but I guess not enough to see why this works.

Very bad approach! Using bits in a pointer should not be done, unless you have a very RAM-constrained target. And then a linked list is likely the wrong approach. And for a linked list, this is actually nonsense. Just use a null pointer. — too honest for this site
How did you actually allocate these pointers? This // because the low bit is used as a sentinel to signal end-of-list. sounds very odd. I don't believe you can (ab)use a pointer this way. — πάντα ῥεῖ
Using the low bit of a pointer as a sentinel is a very bad idea, made worse by the cast to size_t. At the very least, cast to something sensible, like intptr_t. — user3386109
@AndrewStocker Just follow @Olaf's advice and use a NULL pointer as usual. — πάντα ῥεῖ
@πάνταῥεῖ I agree that Olaf's advice is correct in general, I am just wondering why this would work anyways — Andrew Stocker

cadrian cadrian · Accepted Answer · 2016-01-12T09:14:10

It works because most modern architectures are 32-bit and even 64-bit wide, and pointers must be aligned on 32-bit or 64-bit blocks; in that case, the int value of a pointer is necessarily a multiple of 32 or 64; so at least it is even.

But that is not always true. Just because the int value of a pointer is odd, does not mean that the pointer is not valid. It depends on the architecture.

Furthermore, when getting the "next" pointer, a test must be performed to return the correct value: NULL.

Incorrect assumption on the pointer value, extra tests, and risks using incorrectly the invalid pointer… Why not setting the pointer to NULL in the first place?

Pointer Arithmetic For Intrusive Linked List

1 Answers