Re: Double linked list with one pointer

> -----Original Message-----
> From: Bruce Momjian [mailto:pgman@candle.pha.pa.us]
> Sent: Saturday, December 06, 2003 5:02 PM
> To: Gaetano Mendola
> Cc: pgsql-hackers@postgresql.org
> Subject: Re: [HACKERS] Double linked list with one pointer
>
>
> Gaetano Mendola wrote:
> > If I'm not wrong Neil Conway is working on
> > reimplement a double linked list.
> > Looking around I found this post of
> > "Herb Sutter" on comp.lang.c++:
> >
> >
> ======================================================================
> > ==
> > In particular, a motivation behind two-way pointers is that you
> > can have a more space-efficient doubly linked list if you
> store only one
> > (not two) pointer's worth of storage in each node. But how
> can the list
> > still be traversable in both directions? The idea is that each node
> > stores, not a pointer to one other node, but a pointer to
> the previous
> > node XOR'd with a pointer to the next node. To traverse the
> list in either
> > direction, at each node you get a pointer to the next node by simply
> > XORing the current node's two-way pointer value with the
> address of the
> > last node you visited, which yields the address of the next
> node you want
> > to visit. For more details, see:
> >
> >     "Running Circles Round You, Logically"
> >     by Steve Dewhurst
> >     C/C++ Users Journal (20, 6), June 2002
> >
> > I don't think the article is available online, alas, but
> you can find
> > some related source code demonstrating the technique at:
> >
> >     http://www.semantics.org/tyr/tyr0_5/list.h
>
> That certainly is an amazing idea.  You know the pointer you
> are coming from so you can XOR to find the next pointer.
>
> I agree with a Tom that we don't have much use for
> double-link lists, but is a nice idea.

Except when it causes undefined behavior.  The subtraction trick also
suffers from the same evil flaw.

http://groups.google.com/groups?hl=en&lr=&ie=UTF-8&oe=UTF-8&threadm=SErn
3.289%24O17.9552%40client&rnum=3&prev=/groups%3Fq%3Dxor%2Bhack%2Bgroup:c
omp.lang.c.*%2Bauthor:corbit%26hl%3Den%26lr%3D%26ie%3DUTF-8%26oe%3DUTF-8
%26selm%3DSErn3.289%2524O17.9552%2540client%26rnum%3D3

From the C-FAQ:

3.3b:    Here's a slick expression:
    a ^= b ^= a ^= b
It swaps a and b without using a temporary.

A:    Not portably, it doesn't.  It attempts to modify the variable atwice between sequence points, so its behavior is
undefined.
For example, it has been reported that when given the code
    int a = 123, b = 7654;    a ^= b ^= a ^= b;
the SCO Optimizing C compiler (icc) sets b to 123 and a to 0.
See also questions 3.1, 3.8, 10.3, and 20.15c.

10.3:    How can I write a generic macro to swap two values?

A:    There is no good answer to this question.  If the values areintegers, a well-known trick using exclusive-OR could
perhapsbeused, but it will not work for floating-point values orpointers, or if the two values are the same variable.
(Seequestions3.3b and 20.15c.)  If the macro is intended to beused on values of arbitrary type (the usual goal), it
cannotusea temporary, since it does not know what type of temporaryit needs (and would have a hard time picking a name
forit ifit did), and standard C does not provide a typeof operator. 
The best all-around solution is probably to forget about using amacro, unless you're willing to pass in the type as a
thirdargument.

20.15c:    How can I swap two values without using a temporary?

A:    The standard hoary old assembly language programmer's trick is:
    a ^= b;    b ^= a;    a ^= b;
But this sort of code has little place in modern, HLLprogramming.  Temporary variables are essentially free,and the
idiomaticcode using three assignments, namely 
    int t = a;    a = b;    b = t;
is not only clearer to the human reader, it is more likely to berecognized by the compiler and turned into the
most-efficientcode(e.g. using a swap instruction, if available).  The lattercode is obviously also amenable to use with
pointersandfloating-point values, unlike the XOR trick.  See also questions3.3b and 10.3.