Can an XOR linked list be implemented in C++ without causing undefined behavior?

Question

An XOR linked list is a modified version of a normal doubly-linked list in which each node stores just one "pointer" instead of two. That "pointer" is composed of the XOR of the next and previous pointers. To traverse the list, two pointers are needed - one to the current node and one to the next or previous node. To traverse forward, the previous node's address is XORed with the "pointer" stored in the current node, revealing the true "next" pointer.

The C++ standard causes a bunch of operations on pointers and integers to result in undefined behavior - for example, you cannot guarantee that setting a particular bit in a number will not cause the hardware to trigger an interrupt, so in some cases the results of bit twiddling can be undefined.

My question is the following: is there a C++ implementation of an XOR linked list that does not result in undefined behavior?

Answer 1

My question is the following: is there a C++ implementation of an XOR linked list that does not result in undefined behavior?

If by "is there an implementation" you mean "has it already been written" then I don't know. If you mean "is it possible to write one" then yes it is but there might be some caveats about portability.

You can bit-twiddle to your heart's content if you convert both pointers to uintptr_t before you start, and store that type in the node instead of a pointer. Bitwise operations on unsigned types never result in undefined behavior.

However, uintptr_t is an optional type and so it's not entirely portable. There is no requirement that a C++ implementation actually has an integer type capable of representing an address. If the implementation doesn't have uintptr_t then the code is permitted to compile with a diagnostic, in which case its behavior is outside the scope of the standard. Not sure whether you consider that an infringement of "without UB" or not. I mean, seriously, a compiler that allows code which uses undefined types? ;-)

To avoid uintptr_t I think that you could do your bit-twiddling on an array of sizeof(node*) unsigned chars instead. Pointers are POD types and so can be copied, spindled and mutilated provided that the object representation is restored to its original condition before being used as a pointer.

Note also that if your C++ implementation has a garbage collector, then convert-to-integer / xor / xor-back-again / convert-to-pointer doesn't necessary stop the object being collected (because it results in an "unsafely derived pointer"). So for portability you must also ensure that the resulting pointers are valid. Two ways to do this:

1. call declare_reachable on them.
2. Use an implementation with relaxed pointer safety (it is implementation-defined whether this is the case, and you can test for it with get_pointer_safety() bearing in mind that a relaxed implementation is allowed to falsely claim that it's strict).

You might think that there's a third way (albeit one that defeats the purpose of the XOR linked list unless you happen to have it anyway):

• keep a separate container of all the pointer values

This is not guaranteed to work. An unsafely derived pointer is invalid even if it happens to be equal to a safely-derived pointer (3.7.4.3/4). I was surprised too.