Re: embedded list v2

Andres Freund <andres(at)2ndquadrant(dot)com> writes:
> On Friday, September 14, 2012 10:48:35 PM Tom Lane wrote:
>> Instead let's provide a macro for an empty list value, so that you can
>> do something like
>> static ilist_d_head DatabaseList = EMPTY_DLIST;

> I don't think that can work with dlists because they are circular and need
> their pointers to be adjusted.

Well, actually, that just brings us to the main point which is: I do not
believe that circular links are a good design choice here. They prevent
the possibility of trivial list initialization, they make plain
iteration over the list more expensive, and you have provided no
evidence that there's any meaningful savings in other operations, much
less enough to justify those disadvantages.

>> The apparently random decisions to make some things inline functions
>> and other things macros (even though they evaluate their args multiple
>> times) will come back to bite us. I am much more interested in
>> unsurprising behavior of these constructs than I am in squeezing out
>> an instruction or two, so I'm very much against the unsafe macros.

> At the moment the only thing that are macros are things that cannot be
> expressed as inline functions because they return the actual contained type
> and/or because they contain a for() loop.

I don't really care. If you can't build it without multiple-evaluation
macros, it's too dangerous for a fundamental construct that's meant to
be used all over the place. Time to redesign.

One possible option, though it's a bit restrictive, is to insist that
the list node be the first element of whatever it's embedded in,
eliminating the need for ilist_container altogether. This would not
work if we meant to put these kinds of list links into Node-derived
structs, but I suspect we don't need that. Then for instance (given
the additional choice to not use circular links) dlist_get_head
would degenerate to ((type *) (ptr)->head.next), which eliminates
its multi-evaluation hazard and saves a few instructions as well.

Or if you don't want to do that, dlist_get_head(type, membername, ptr)
could be defined as
((type *) dlist_do_get_head(ptr, offsetof(type, membername)))
where dlist_do_get_head is an inline'able function, eliminating the
multi-evaluation-of-ptr hazard.

regards, tom lane