[x] Close ad

XOR LINKED LIST

XOR linked lists are a curious use of the bitwise exclusive disjunction (XOR) operation, here denoted by ⊕, to decrease storage requirements for doubly-linked lists. An ordinary doubly-linked list stores addresses of the previous and next list items in each list node, requiring two address fields:

 ...  A       B         C         D         E  ...
          <–  prev  <–  prev  <–  prev  <–
          –>  next  –>  next  –>  next  –>

An XOR linked list compresses the same information into one address field by storing the bitwise XOR of the address for previous and the address for next in one field:

 ...  A        B          C         D         E  ...
         <–>  A⊕C  <->  B⊕D  <->  C⊕E  <->

When you traverse the list from left to right: supposing you are at C, you can take the address of the previous item, B, and XOR it with the value in the link field (B⊕D). You will then have the address for D and you can continue traversing the list. The same pattern applies in the other direction.

To start traversing the list in either direction from some point, you need the address of two consecutive items, not just one. If the addresses of the two consecutive items are reversed, you will end up traversing the list in the opposite direction.

This form of linked list may be inadvisable:

  • General-purpose debugging tools cannot follow the XOR chain, making debugging more difficult;
  • The price for the decrease in memory usage is an increase in code complexity, making maintenance more expensive;
  • Conservative 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, though an int or long cast, depending on architecture, will often work)
  • 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.

Also, modern computer systems usually have cheap and plentiful memory, so storage overhead is not normally an issue outside specialised embedded systems. Where it is still desirable to reduce the overhead of a linked list, unrolling provides a more practical approach (as well as other advantages, such as increasing cache performance and speeding random accesses).

Features

  • The address of a single list item can be given to another program without exposing the other items -- a measure of security.
  • Two XOR operations suffice to do the traversal from one item to the next, the same instructions sufficing in both cases. Consider a list with items {…B C D…} and with R1 and R2 being registers containing, respectively, the address of the current (say C) list item and a work register containing the XOR of the current address with the previous address (say C⊕D). Cast as System/360 instructions:
X  R2,Link    R2 <- C⊕D ⊕ B⊕D (i.e. B⊕C, "Link" being the link field
                                  in the current record, containing B⊕D)
XR R1,R2      R1 <- C ⊕ B⊕C    (i.e. B, violá: the next record)
  • End of list is signified by imagining a list item at address zero placed adjacent to an end point, as in {0 A B C…}. The link field at A would be 0⊕B. An additional instruction is needed in the above sequence after the two XOR operations to detect a zero result in developing the address of the current item,
  • A list end point can be made reflective by making the link pointer be zero. A zero pointer is a mirror. (The XOR of the left and right neighbor addresses, being the same, is zero.)

Why does it work?

The key is the first operation, and the properties of XOR:

  • X⊕X=0
  • X⊕0=X
  • X⊕Y=Y⊕X
  • (X⊕Y)⊕Z=X⊕(Y⊕Z)
  • X⊕Y⊕X=Y

The R2 register always contains the XOR of the address of current item C with the address of the predecessor item P: C⊕P. The Link fields in the records contain the XOR of the left and right successor addressess, say L⊕R. XOR of R2 (C⊕P) with the current link field (L⊕R) yields C⊕P⊕L⊕R.

  • If the predecessor was L, the P(=L) and L cancel out leaving C⊕R.
  • If the predecessor had been R, the P(=R) and R cancel, leaving C⊕L.

In each case, the result is the XOR of the current address with the next address. XOR of this with the current address in R1 leaves the next address. R2 is left with the requisite XOR pair of the (now) current address and the predecessor.

See also