Re: Double linked list with one pointer

Greg Stark <gsstark(at)mit(dot)edu> writes:
> Treating pointers as integers is technically nonportable but
> realistically you would be pretty hard pressed to find any
> architecture anyone runs postgres on where there isn't some integer
> datatype that you can cast both directions from pointers safely.

... like, say, Datum. We already make that assumption, so there's no
new portability risk involved.

> Presumably if you wanted to do this you would implement it all in an
> abstraction that hid all the details from calling code.

The hard part would be to make such an abstraction. For instance,
I don't think you could hide the fact that two state variables are
required not one. (The obvious solution of making the state variable
be a two-component struct is not a good answer, because few if any
compilers would be able to figure out that they could/should put the
struct fields in registers; but keeping 'em in memory would absolutely
kill performance.)

There are worse problems too, having to do with lists that are modified
while they are traversed. There are many places that assume they can
lremove() any element other than the one they are currently stopped on
(for example, lnext() off an element and immediately delete it). That
will absolutely not work in the XOR scenario, and I see no way to make
it work without exposing some kind of interaction between lremove and
the list traversal macros. Likewise for insertion of elements into
lists.

In short the abstraction would be pretty leaky and correspondingly hard
to use. (If you've not read Joel Spolsky's article about leaky
abstractions, you should; I think it should be required reading for
every software designer.
http://www.joelonsoftware.com/articles/LeakyAbstractions.html )

Have we beaten this idea to death yet?

regards, tom lane