Re: Double linked list with one pointer

From: Bruce Momjian <pgman(at)candle(dot)pha(dot)pa(dot)us>
To: Gaetano Mendola <mendola(at)bigfoot(dot)com>
Cc: "pgsql-hackers(at)postgresql(dot)org" <pgsql-hackers(at)postgresql(dot)org>
Subject: Re: Double linked list with one pointer
Date: 2003-12-07 01:02:07
Message-ID: 200312070102.hB7127k14005@candle.pha.pa.us
Views: Raw Message | Whole Thread | Download mbox | Resend email
Thread:
Lists: pgsql-hackers

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(at)candle(dot)pha(dot)pa(dot)us | (610) 359-1001
+ If your life is a hard drive, | 13 Roberts Road
+ Christ can be your backup. | Newtown Square, Pennsylvania 19073

In response to

Responses

Browse pgsql-hackers by date

  From Date Subject
Next Message Bruce Momjian 2003-12-07 01:06:56 Re: 7.4.1 ... slight change of scheduale ...
Previous Message NK 2003-12-07 00:49:40 Help! Parser Stage: Get The Columns Of the Table