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