Re: embedded list v3

Andres Freund <andres(at)2ndquadrant(dot)com> writes:
> Current version is available at branch ilist in:
> git://git.postgresql.org/git/users/andresfreund/postgres.git
> ssh://git(at)git(dot)postgresql(dot)org/users/andresfreund/postgres.git

I'm still pretty desperately unhappy with your insistence on circularly
linked dlists. Not only does that make initialization problematic,
but now it's not even consistent with slists.

A possible compromise that would fix the initialization issue is to
allow an empty dlist to be represented as *either* two NULL pointers
or a pair of self-pointers. Conversion from one case to the other
could happen like this:

INLINE_IF_POSSIBLE void
dlist_push_head(dlist_head *head, dlist_node *node)
{
+ if (head->head.next == NULL)
+ dlist_init(head);
+
node->next = head->head.next;
node->prev = &head->head;
node->next->prev = node;
head->head.next = node;

dlist_check(head);
}

It appears to me that of the inline'able functions, only dlist_push_head
and dlist_push_tail would need to do this; the others presume nonempty
lists and so wouldn't have to deal with the NULL/NULL case.
dlist_is_empty would need one extra test too. dlist_foreach could be
something like

#define dlist_foreach(iter, ptr)
for (AssertVariableIsOfTypeMacro(iter, dlist_iter),
AssertVariableIsOfTypeMacro(ptr, dlist_head *),
iter.end = &(ptr)->head,
iter.cur = iter.end->next ? iter.end->next : iter.end;
iter.cur != iter.end;
iter.cur = iter.cur->next)

I remain unimpressed with the micro-efficiency of this looping code,
but since you're set on pessimizing list iteration to speed up list
alteration, maybe it's the best we can do.

BTW, the "fast path" in dlist_move_head can't be right can it?

regards, tom lane