XOR链表

Question

我最近遇到了下面的链接,我发现它非常有趣.

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

• 通用调试工具不能遵循XOR链,使调试更加困难; [1]
• 内存使用量减少的代价是代码复杂性的增加,使维护成本更高;
• 大多数垃圾收集方案不适用于不包含文字指针的数据结构;
• 指针的异或未在某些上下文中定义(例如,C语言),尽管许多语言在指针和整数之间提供某种类型的转换;
• 如果没有遍历列表,则指针将是不可读的 - 例如,如果指向列表项的指针包含在另一个数据结构中;
• 在遍历列表时,您需要记住先前访问的节点的地址,以便计算下一个节点的地址.

现在我想知道这是否仅适用于低级语言,或者在C#中是否也可以？

是否有任何类似的选项可以用C#产生相同的结果？

Answer 1

TL; DR我很快在C#中编写了一个概念验证XorLinkedList实现.

使用C#中的不安全代码绝对是可能的.但是有一些限制:

1. XorLinkedList必须是"非托管结构",即它们不能包含托管引用
2. 由于C#泛型的限制,链表不能是通用的(甚至没有where T : struct)

后者似乎是因为您不能将泛型参数限制为非托管结构.只是where T : struct你还允许包含托管引用的结构.

这意味着您的XorLinkedList只能保存原始值,如整数,指针或其他非托管结构.

C#中的低级编程

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

我知道,非常脆弱.C#指针和IntPtr不支持XOR运算符(可能是个好主意).

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

之后不要忘记Marshal.FreeHGlobal那些节点(实现完整的IDisposable模式并确保将空闲的调用放在if(disposing)块之外.

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

结论

就个人而言,我绝不会在C#中使用XorLinkedList(当我编写内存分配器或内核数据结构等低级系统内容时,可能会使用C语言.在任何其他设置中,存储效率的小幅提升实在不值得痛苦.事实上,你不能将它与C#中的托管对象一起使用,这对于日常编程来说几乎没用.

此外,今天的存储几乎是免费的,即使是主内存也是如此,如果你使用的是C#,你很可能并不关心存储.我已经读过某个地方,CLR对象标题大约是40个字节,所以这个指针将是你最不关心的问题;)