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

[Jürgen Hötzel]

On Sun, Mar 04, 2007 at 10:15:44PM -0600, Aaron Griffin wrote:
> On 3/4/07, Jürgen Hötzel <juergen at hoetzel.info> wrote:
> > due the missing "last element hint" which speeded up the add operation
> > before aaron introduced the public alpm_list type two months ago. I
> > consider adding the "last element" member again. Any objections?
> 
> Actually, that's probably a bad idea.  It's almost trivial to convert
> the list to a circular one.  Then alpm_list_last(foo) would just be
> foo->prev;

This is the way Judd implemented it: He needed fast access to the last
element and also the "prev" element to allow fast inserts. So he used
non-circular double linked lists and the "last element hint".

> There should never be a case when this would cause a problem (i.e.
> some sort of "scan backward until ->prev is null" function would only
> be useful in the case of bad design).

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);
}

Jürgen
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 189 bytes
Desc: not available
URL: <http://archlinux.org/pipermail/pacman-dev/attachments/20070305/b4e0f550/attachment.pgp>