[mananaysiempre]

One thing this loses relatively to a conventional doubly linked list is the ability to remove an item while only having its address (or any other iterator pointing to it that is stable across other items being inserted or deleted). And unfortunately that’s often why you’re using a doubly linked list in the first place.

(A less intrinsic flaw is that coding an XOR linked list in strictly conformant C is exceedingly annoying. The standard does not guarantee that equal pointers turn into equal integers upon casting, so you’re forced to make everything into an uintptr_t to, essentially, maintain a canonical integer-cast version.)

[AceJohnny2]

> The standard does not guarantee that equal pointers turn into equal integers upon casting, so you’re forced to make everything into an uintptr_t to, essentially, maintain a canonical integer-cast version.

Of course! The standard does not guarantee that the size of an int is the same as the size of a pointer, i.e. `sizeof(int) =/= sizeof(int*)`. IIRC, this was the case on some of the PowerPCs I worked on decades ago. Now with x86-64 & Aarch64 having taken over the world (and with saner 32bit on the embedded end) we've almost forgotten the Cambrian explosion of "interesting" word-size machines.

The whole point of the C standard is that it allows implementers flexibility in the sizing of the basic data types, to match a given machine's architecture, with the standard only defining relationships between types (e.g. char <= short <= int <= long). The only surprise is that it took so long for fixed-width types to be standardized (C99).

[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.)

[tomsmeding]

On modern 64-bit machines, sizeof(int) != sizeof(int*) is very true. But there's probably a significant amount of code that assumes it's equal to sizeof(uint64_t) or sizeof(long). :)

[akoboldfrying]

True, but if you always keep a pair of adjacent pointers where before you would have kept just the first, efficient deletion and insertion come back. (You could even go the whole hog and encapsulate this pair as a new WidePointer type, with operator++() and operator--() internally operating on both, etc.)

This will likely be a small constant factor slower for some operations, of course, but if you need bidi traversal and node values are small compared to pointers, it's a solid space savings -- and the lower cache utilisation resulting from that savings may even make it a speed win overall.