XOR linked list

Question

I recently came across the link below which I have found quite interesting.

http://en.wikipedia.org/wiki/XOR_linked_list

• General-purpose debugging tools cannot follow the XOR chain, making debugging more difficult; [1]
• The price for the decrease in memory usage is an increase in code complexity, making maintenance more expensive;
• Most garbage collection schemes do not work with data structures that do not contain literal pointers;
• XOR of pointers is not defined in some contexts (e.g., the C language), although many languages provide some kind of type conversion between pointers and integers;
• The pointers will be unreadable if one isn't traversing the list — for example, if the pointer to a list item was contained in another data structure;
• While traversing the list you need to remember the address of the previously accessed node in order to calculate the next node's address.

Now I am wondering if that is exclusive to low level languages or if that is also possible within C#?

Are there any similar options to produce the same results with C#?

Answer 1

TL;DR I quickly wrote a proof-of-concept XorLinkedList implementation in C#.

This is absolutely possible using unsafe code in C#. There are a few restrictions, though:

1. XorLinkedList must be "unmanaged structs", i.e., they cannot contain managed references
2. Due to a limitation in C# generics, the linked list cannot be generic (not even with where T : struct)

The latter seems to be because you cannot restrict the generic parameter to unmanaged structs. With just where T : struct you'd also allow structs that contain managed references.

This means that your XorLinkedList can only hold primitive values like ints, pointers or other unmanaged structs.

Low-level programming in C#

private static Node* _ptrXor(Node* a, Node* b)
{
    return (Node*)((ulong)a ^ (ulong)b);//very fragile
}

Very fragile, I know. C# pointers and IntPtr do not support the XOR-operator (probably a good idea).

private static Node* _allocate(Node* link, int value = 0)
{
    var node = (Node*) Marshal.AllocHGlobal(sizeof (Node));
    node->xorLink = link;
    node->value = value;
    return node;
}

Don't forget to Marshal.FreeHGlobal those nodes afterwards (Implement the full IDisposable pattern and be sure to place the free calls outside the if(disposing) block.

private static Node* _insertMiddle(Node* first, Node* second, int value)
{
    var node = _allocate(_ptrXor(first, second), value);
    var prev = _prev(first, second);
    first->xorLink = _ptrXor(prev, node);
    var next = _next(first, second);
    second->xorLink = _ptrXor(node, next);
    return node;
}

Conclusion

Personally, I would never use an XorLinkedList in C# (maybe in C when I'm writing really low level system stuff like memory allocators or kernel data structures. In any other setting the small gain in storage efficiency is really not worth the pain. The fact that you can't use it together with managed objects in C# renders it pretty much useless for everyday programming.

Also storage is almost free today, even main memory and if you're using C# you likely don't care about storage much. I've read somewhere that CLR object headers were around ~40 bytes, so this one pointer will be the least of your concerns ;)