Re: equal() perf tweak

Neil Conway <neilc(at)samurai(dot)com> writes:
> #define length(l) ((l)->length)
> #define value(cell) ((cell)->elem.ptr_value)
> #define ivalue(cell) ((cell)->elem.int_value)
> #define ovalue(cell) ((cell)->elem.oid_value)

Couple of objections here: one is that defining such common words as
"length" or "value" as macros is going to break everything in sight
(starting with the List struct itself ;-)). Also, if we are going
to use NIL to represent an empty list, length() is really going to
need to be like
(l) ? l->length : 0
Coupling that objection with the fear of multiple evaluations of
arguments (not sure doing so would break anything, but definitely not
sure that it wouldn't), I think that length() will have to continue
to be a function not a macro. Possibly for the gcc case we could make
it a "static inline" function. As for value() and friends, use a less
generic name like cellvalue() ... and please respect the naming
convention stated just five lines earlier.

> #define lfirst(l) value((l)->head)
> #define lfirsti(l) ivalue((l)->head)
> #define lfirsto(l) ovalue((l)->head)

No, lfirst and friends will need to apply to ListCells not to Lists,
else the coding of foreach loops will break everywhere. I think there
are many more places that will want lfirst to apply to a ListCell than
will want it to apply to a raw List.

You will probably want to invent a function (not macro for fear of
multiple evals) like

ListCell *firstcell(l) {
return l ? l->head : NULL;
}

and use this (not a direct reference to l->head) in foreach(). Then
the places that do want a true lfirst() on a list will need to be
rewritten as lfirst(firstcell(list)).

Not sure what to do about the lsecond/lthird/lfourth macros. Those are
not used much. Maybe we could rename them to ListSecond etc and then
define ListFirst as lfirst(firstcell(list)) for the places that do want
it to work that way.

> #define foreach(_cell_,_list_) \
> for (_cell_ = (_list_)->head; _elt_->next != NULL; _elt_ = _elt->next)

The test condition still needs to be _elt_ != NULL.

> * XXX a few of the following functions are duplicated to handle
> * List of pointers and List of integers separately. Some day,
> * someone should unify them. - ay 11/2/94

How much of this NOTE can go away now?

> List *retval;

> retval = palloc(sizeof(*retval));

Can't we use makeNode()?

> /*
> * Add a new, and as yet undefined, head element to the list, which
> * must be non-NIL. The list is mutated in place. The caller should
> * fill in the value of the new head element.
> */
> static List *
> new_head_elem(List *list)

I don't think you want to do things this way; it won't scale up to the
merge-the-first-element-into-the-List-header approach. What would
probably be better is to have a combined
build-the-List-header-and-first-cell subroutine. Also, don't put in
cases to handle initially-empty lists, because there won't be any.

check_invariant() could reasonably also test that list->tail->next is
NULL.

> nconc(List *l1, List *l2)
> {
> /*
> * XXX: memory allocation is ambiguous here: does the caller free
> * the memory for l1 or l2?
> */

At present, the caller doesn't pfree anything, since the result list
needs every cell in both inputs. I think what we will want nconc to do
is pfree the second List header; in the event that the second List's
first element is palloc'd with the header, it will have to be
re-allocated (or maybe better, just re-use the storage in place).
You'll need to look at all the uses of nconc (fortunately there are not
many) to verify that the second List is never again used as an
independent entity. If it is, then we can't use nconc anyway unless we
first copy the second List, as later mods to either list could destroy
the invariant for the other list.

regards, tom lane