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
=========================================================================


In this way we are going to save a pointer for each node,
what do you think ?



Regards
Gaetano Mendola


Sat, 06 Dec 2003 17:03:48 +0100
Gaetano Mendola <mendola@bigfoot.com>
Double linked list with one pointer
Gaetano Mendola <mendola@bigfoot.com> writes:
> If I'm not wrong Neil Conway is working on
> reimplement a double linked list.

No, he's working on keeping track of the list tail element (and length,
but the tail element is the important part).  There was nothing about
double linking.

> 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.

This is way too weird for my taste.  We do not need two-way list
traversal in 99.9% of the backend code (note the near complete lack of
use of Dllist).  Also, the described scheme is slower to traverse than a
standard list since you have to remember two words of state (prev and
cur pointer not just cur) to traverse the list; that bookkeeping, plus
the cost of the XOR itself, adds up.  Another cost that would be
significant from my point of view is loss of readability of list
structures in the debugger.  I don't want to pay that cost to buy a
feature we don't need.

			regards, tom lane

Sat, 06 Dec 2003 13:44:03 -0500
Tom Lane <tgl@sss.pgh.pa.us>
Re: 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.

-- 
  Bruce Momjian                        |  http://candle.pha.pa.us
  pgman@candle.pha.pa.us               |  (610) 359-1001
  +  If your life is a hard drive,     |  13 Roberts Road
  +  Christ can be your backup.        |  Newtown Square, Pennsylvania 19073

Sat, 6 Dec 2003 20:02:07 -0500 (EST)
Bruce Momjian <pgman@candle.pha.pa.us>
Re: Double linked list with one pointer


Bruce Momjian wrote:

>Gaetano Mendola wrote:
>  
>
>>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.
>  
>


I must confess that it strikes me as a really really horrid and ugly 
hack - very likely to be error-prone and non-portable and undebuggable, 
and for almost no saving worth having. But maybe that's just me.

In general I've been impressed with the quality of Pg code over the last 
6 months or so - I'd hate to see it polluted by something like this.

cheers

andrew


Sat, 06 Dec 2003 22:27:59 -0500
Andrew Dunstan <andrew@dunslane.net>
Re: Double linked list with one pointer
Andrew Dunstan wrote:
> 
> 
> Bruce Momjian wrote:
> 
> >Gaetano Mendola wrote:
> >  
> >
> >>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.
> >  
> >
> 
> 
> I must confess that it strikes me as a really really horrid and ugly 
> hack - very likely to be error-prone and non-portable and undebuggable, 
> and for almost no saving worth having. But maybe that's just me.
> 
> In general I've been impressed with the quality of Pg code over the last 
> 6 months or so - I'd hate to see it polluted by something like this.

Agreed, I just thought it was neat and I hadn't realized it was
possible.

Also, I don't think the problems for doing this for swaping values
without a temp table is relevant.  In those cases, you are doing the
swap without a temp variable, and this is the problem, more than the XOR
itself, which is what we would use and use  real temp table.

-- 
  Bruce Momjian                        |  http://candle.pha.pa.us
  pgman@candle.pha.pa.us               |  (610) 359-1001
  +  If your life is a hard drive,     |  13 Roberts Road
  +  Christ can be your backup.        |  Newtown Square, Pennsylvania 19073

Sun, 7 Dec 2003 00:21:12 -0500 (EST)
Bruce Momjian <pgman@candle.pha.pa.us>
Re: Double linked list with one pointer
Andrew Dunstan <andrew@dunslane.net> writes:
> I must confess that it strikes me as a really really horrid and ugly 
> hack - very likely to be error-prone and non-portable and undebuggable, 
> and for almost no saving worth having. But maybe that's just me.

No, that was exactly my reaction too.  I'd be willing to buy into it
if we had a lot of lists that needed to be traversable in both
directions and we were concerned about the storage overhead for such
lists.  But we don't, we aren't, and so I'm not ...

			regards, tom lane

Sun, 07 Dec 2003 00:50:26 -0500
Tom Lane <tgl@sss.pgh.pa.us>
Re: Double linked list with one pointer 