XOR puzzle. SPOILER

[Dave Jones]

Several people have asked me for the answer to the XOR puzzle. I've
tried to send it to everyone who asked, but our version of the mailer
is not good at turning UUCP-style pathnames around, and I don't know
how either.  So a few of the replies got bounced back. 
(Can someone send me a rosetta stone, mapping UUCP to ARPA style names?)
Moral: If you send email to someone, include return addresses.  Include
both kinds if you got 'em.

Anyhow, I've decided to post the spoiler here.

The puzzle is this: Using the XOR trick, how do you implement a doubly-
linked list using only one pointer-wide field for both the links?

One correspondant said that the procedure is described in Knuth's Algorithms,
Vol. 1.


SPOILER:

The trick is to use two "real" pointers to point into the list, rather
than one. They will point to adjacent list-elements ("cons-records").

Then, in each cons-record, keep a field, "cdr", which contains

   XOR( prev, next )

where prev and next are real pointers to the previous and next cons-records
in the list.  Thus the field codes for both the previous and the next
cons-record.


typedef
struct Dcons  /* "cons" record for doubly-linked list */
{ 
  struct List* cdr; /* codes for previous and next members of list */
  void* car;        /* whatever it is you are listing.*/

} Dcons;

/* This structure "points" into a list.
 * Use it, rather than a single pointer, as a cursor to traverse
 * lists.
 */
typedef 
{
  Dcons* this;
  Dcons* next;

}List_ptr;


#define HEAD(list) ((list).this->car)

/* Kids, don't try this at home. 
 *
 * Send all scholarly discussion about how this won't work on an 
 * archetecture that stores pointers in Best Foods mayonaise jars to
 * 
 *                  Mr. and Mrs. A. Blythering-Pedant
 *                  Petrol Station
 *                  Toad-on-the-Green
 *                  Middlesex
 *                  
 * Thank you very much.
 */
#define XOR(p1,p2) ((Dcons*)((long)(p1) ^ (long)(p2)))



Now, can perform the following magic: 


List_ptr
prev(ptr)   /* Returns List_ptr previous to [ptr] */
  List_ptr ptr;
{
  List_ptr prev_ptr;
  prev_ptr.this =
	ptr.this == 0? 0 : XOR(ptr.this->cdr, ptr.next);
  prev_ptr.next = ptr.this;
  return prev_ptr;
}

List_ptr
next(ptr)       /* Returns List_ptr next after [ptr] */
  List_ptr ptr; 
{
  List_ptr next_ptr;
  next_ptr.this = ptr.next;
  next_ptr.next =
	ptr.next == 0? 0 : XOR(ptr.next->cdr, ptr.this);
  return next_ptr;
}