[pacman-dev] _alpm_list_add_first

[Dan McGee]

On 5/16/07, Aaron Griffin <aaronmgriffin at gmail.com> wrote:
> On 4/26/07, Nagy Gabor <ngaba at petra.hos.u-szeged.hu> wrote:
> > Hi!
> >
> > In many cases we use alpm_list as a "stack", or we just use
> > it as a set. In these cases an O(1) _alpm_list_add_first function would
> > be more efficient (which add the new member as a first element) than
> > the O(n) _alpm_list_add. Mostly in time "critical" parts (see my
> > favorite sortbydeps function for example;-).
>
> I was just thinking about something similar.  Given our usage pattern,
> the following *might* have an effect (pseudo code):
>
> alpm_list_add returns the node that was just added, and adds AFTER the
> passed in node.  So:
> a->b->c->d
> alpm_list_add(a,x);
> a->x->b->c->d
> alpm_list_add(c,y);
> a->x->b->c->y->d
>
> Returning the node that was just added would allow us to do the "add
> to the list" loops while maintaining a 'last' pointer, and not
> incurring the overhead of the last pointer on every node.

I have some local code of this kind of thing, and it does lead to some
dramatic speedups, the most notable being on a "pacman -Qo <file>"
operation, as alpm_list_ts of files are built, and we call
alpm_list_last an obscene number of times. We should find a
non-hackish way of doing it, however.

-Dan