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#?

Crying

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 ;)

Sophrosyne

It may be worth noting that this should not be confused with the ^ (Handle to Object on Managed Heap) operator in C#. – Leslielesly

Answer 2

C# doesn't generally let you manipulate references at that level, so no, unfortunately.

Trismus

This is not exactly correct. Pointer structures - including XOR linked lists - can be implemented in managed code by using arrays, and fake pointers which are actually array indices. – Oxy

Not sure why you think this is unfortunate! – Brigantine

@Robin Green - being able to simulate a thing is not the same as being able to do a thing. – Trismus

there's an interesting philosophical debate to be had there – Oxy

Answer 3

As an alternative to the unsafe solutions that have been proposed.

If you backed your linked list with an array or list collection where instead of a memory pointer 'next' and 'previous' indicate indexes into the array you could implement this xor without resorting to using unsafe features.

Assimilate

Answer 4

There are ways to work with pointers in C#, but you can have a pointer to an object only temporarily, so you can't use them in this scenario. The main reason for this is garbage collection – as long as you can do things like XOR pointers and unXOR them later, the GC has no way of knowing whether it's safe to collect certain object or not.

You could make something very similar by emulating pointers using indexes in one big array, but you would have to implement a simple form of memory management yourself (i.e. when creating new node, where in the array should I put it?).

Another option would be to go with C++/CLI which allows you both the full flexibility of pointers on one hand and GC and access to the framework when you need it on the other.

Fitly

Answer 5

Sure. You would just need to code the class. the XOR operator in c# is ^ That should be all you need to start the coding. Note this will require the code to be declared "unsafe." See here: for how to use pointers in c#.

Farro

I don't think there is any "just need to ..." in this context. You would have to muck around with unsafe code and pointers, both of which C# will fight with you over. – Monopetalous

Sorry, was editing the post as you commented. Yes, its not so simple, but it is certainly possible. – Farro

Considering you're going to have to trick the compiler into letting you work with pointers to managed types, I doubt this is going to be feasible, much less usable at any level. – Monopetalous

Why is there tricking involved? I agree, writing code as unsafe generally is not a good idea, but to get the pointer to a struct requires mystruct* which seems not so difficult. – Farro

I would agree that it would be a much better idea to write this class in c++ and compile it as a dll and then call that dll in your c# program. – Farro

How do you construct a new struct on the heap and place a pointer to it into a Node* variable? – Monopetalous

You can get a pointer in C# only temporarily, using fixed or stackalloc. As long as the current method ends, the object you pinned can move and most likely will be garbage collected. – Fitly

Answer 6

Making a broad generalization here: C# appears to have gone the path of readability and clean interfaces and not the path of bit fiddling and packing all the information as dense as possible.

So, unless you have a specific need here, you should use the List you are provided. Future maintenance programmers will thank you for it.

Dielectric

Answer 7

It is possible however you have to understand how C# looks at objects. An instance variable does not actually contain an object but a pointer to the object in memory.

DateTime dt = DateTime.Now;

dt is a pointer to a struct in memory containing the DateTime scheme.

So you could do this type of linked list although I am not sure why you would as the framework typically has already implemented the most efficient collections. As a thought expirament it is possible.

Bayly

Bad example - DateTimes are structs, and therefore value types, not reference types. – Trismus