[mananaysiempre]

I meant integers in general, not ints specifically. That is to say, the standard does not guarantee that, if p and q are (say) void pointers and p == q, then (uintptr_t)p == (uintptr_t)q. (Neither does it guarantee that, if p == NULL, then (uintptr_t)p == 0, but I digress.) Mere size shenanigans are not enough for things to get that bad. What you need is for there to be multiple ways to represent a pointer to the same place in memory, like on real-mode x86 in the large memory model.

The practical result is, you need to write XOR-linked-list operations something like this:

  struct node { uintptr_t link; };
  void prepend(uintptr_t head, struct node *n) {
          struct node *h = (void *)head;
          uintptr_t node = (uintptr_t)(void *)n;
          n->link = head ^ h->link;
          ((struct node *)(void *)h->link)->link ^= head ^ node;
          h->link = node;
  }

and you cannot for example make head, the sentinel node pointer, into a struct entry * instead, it has to be exposed as an uintptr_t (a canonical integer representation of that pointer).

[jasonthorsness]

Wow, TIL. So in the version unaware of this the list could be corrupted if the pointer you use, while correctly pointing to the head or tail of the list, happens to convert to a different bit representation for the XOR than the one you encoded into the node. Did you happen to ever see this in a real system?

[mananaysiempre]

I don’t have it in me right now to work out whether this can actually cause corruption, but as for equal pointers simply converting to unequal integers, sure:

  $ cat mismatch.c
  #include <stdio.h>
  char abc[48*1024U], def[48*1024U];
  int main(void) {
      void *p = &abc[sizeof abc], *q = &def[0];
      printf("%d\n", p == q); /* pointers are equal */
      printf("0x%.5lX == 0x%.5lX\n", /* linear addresses are equal */
          ((unsigned long)p >> 16 << 4) + (unsigned short)p,
          ((unsigned long)q >> 16 << 4) + (unsigned short)q);
      printf("0x%.8lX != 0x%.8lX\n", (unsigned long)p, (unsigned long)q);
      return 0;
  }
  $ # compile&link for DOS, 8086, huge memory model, create map file
  $ wcl -bcl=dos -0 -mh -fm mismatch.c
  Open Watcom C/C++16 Compile and Link Utility Version 1.9
  [snip]
  creating a DOS executable
  $ egrep '_abc|_def' mismatch.map
  0371:0000+     _abc
  0f71:0000+     _def
  $ emu2 mismatch.exe
  1
  0x10080 == 0x10080
  0x0408C000 != 0x10080000

(I said large memory model earlier. That was incorrect: if you compile for the large memory model, with -ml, the first line of the output will be 0, because then pointer comparisons will not canonicalize pointers. You need the huge memory model for that. Both 0 and 1 are OK according to the standard, as it does not guarantee anything about comparing a pointer one element past the end of one object to a pointer to another object.)