[pacman-dev] _alpm_list_add_first

Aaron Griffin aaronmgriffin at gmail.com
Wed May 16 01:30:47 EDT 2007

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:

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.

More information about the pacman-dev mailing list