On Sun, Mar 04, 2007 at 10:15:44PM -0600, Aaron Griffin wrote:
On 3/4/07, Jürgen Hötzel <juergen@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