[pacman-dev] alpm_list: missing quick access to last element

Aaron Griffin aaronmgriffin at gmail.com
Mon Mar 5 10:56:43 EST 2007

On 3/5/07, Jürgen Hötzel <juergen at hoetzel.info> wrote:
> Circular lists are different. There is NO end of the list.  consider
> alpm_list_find: it will loop forever ;) pacmans implementation expects
> "non-circular" lists everywhere. Just an example:
> for(lp = info->files; lp; lp = lp->next) {
>         fprintf(fp, "%s\n", (char *)lp->data);
> }

True.  Using circular lists would cause a bit of a problem here.
The only problem with the ->last implementation is that it's a mostly
NULL pointer.  Generally, if something is NULL for an entire list,
except for one node, there's probably a better way to do it.  For
instance, if we go with the fairly typical:
struct list_node
{ struct list_node *next, *prev; void *data; };
struct list { struct list_node *head, *tail; };

It's easy to maintain the list head and tail in the main list struct,
and not pay the price for hundreds of NULL pointers.

Alternatively, adding entries at the beginning of the list would be
nearly as good, as there is no requirement that says a standard list
needs to be in any given order. (unless add_sorted is used, in which
case the ->last optimization is moot as well).

I guess my point is that there are hundreds of options here.  I think
we should think it through rather than putting the ->last pointer back
in there.

More information about the pacman-dev mailing list