Re: embedded list v2

On Tue, Jun 26, 2012 at 7:26 PM, Andres Freund <andres(at)2ndquadrant(dot)com> wrote:
> Attached are three patches:
> 1. embedded list implementation
> 2. make the list implementation usable without USE_INLINE
> 3. convert all callers to ilist.h away from dllist.h

This code doesn't follow PostgreSQL coding style guidelines; in a
function definition, the name must start on its own line. Also, stuff
like this is grossly unlike what's done elsewhere; use the same
formatting as e.g. foreach:

+#define ilist_d_reverse_foreach(name, ptr) for(name =
(ptr)->head.prev; \
+ name != &(ptr)->head; \
+ name = name->prev)

And this is definitely NOT going to survive pgindent:

+ for(cur = head->head.prev;
+ cur != &head->head;
+ cur = cur->prev){
+ if(!(cur) ||
+ !(cur->next) ||
+ !(cur->prev) ||
+ !(cur->prev->next == cur) ||
+ !(cur->next->prev == cur))
+ {
+ elog(ERROR, "double linked list is corrupted");
+ }
+ }

And this is another meme we don't use elsewhere; add an explicit NULL test:

+ while ((cur = last->next))

And then there's stuff like this:

+ if(!cur){
+ elog(ERROR, "single linked list is corrupted");
+ }

Aside from the formatting issues, I think it would be sensible to
preserve the terminology of talking about the "head" and "tail" of a
list that we use elsewhere, instead of calling them the "front" and
"back" as you've done here. I would suggest that instead of add_after
and add_before you use the names insert_after and insert_before, which
I think is more clear; also instead of remove, I think you should say
delete, for consistency with pg_list.h.

A number of these inlined functions could be rewritten as macros -
e.g. ilist_d_has_next, ilist_d_has_prev, ilist_d_is_empty. Since some
things are written as macros anyway maybe it's good to do all the
one-liners that way, although I guess it doesn't matter that much. I
also agree with your XXX comment that ilist_s_remove should probably
be out of line.

Apart from the above, mostly fairly superficial concerns I think this
makes sense.

--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company