[pacman-dev] alpm_list_t

Nagy Gabor ngaba at bibl.u-szeged.hu
Wed Nov 21 09:00:47 EST 2007

> > I have an idea:
> > Since we can check in O(1) time whether a node is a "valid" head node or
> not
> > (node->prev && node->prev->next == NULL), we could modify alpm_list_last
> to
> > check this to choose between the new (fast) and the old (slow) algorithms.
> > And modify alpm_list.c to call alpm_list_last whenever last node is
> needed.
> > By doing this alpm_list.c becomes compatible with the old lists (head->prev
> ==
> > NULL) and we can use sublists (see also:
> > http://www.archlinux.org/pipermail/pacman-dev/2007-November/010213.html)
> > 
> It looks like this is doable, but I'm not sure I like the road this is
> taking. Surely there are better and cleaner list implementations than that.
Well, this still wouldn't be enough :-(

Notations: list is an alpm_list_t, i is a node in list.

Then alpm_list_add(i, foo) still corrupts the list.
What's more alpm_list_remove(i, foo) corrupts the list, if we remove i, even if
we used the old alpm_list_t implementation.

So if we keep with this implementation (I have no better idea:-(), then we
should modify functions in alpm_list.c to treat their input as a _node_ in an
alpm_list (i determines list uniquely!), so modify and use alpm_list_first

Bye, ngaba

SZTE Egyetemi Könyvtár - http://www.bibl.u-szeged.hu
This mail sent through IMP: http://horde.org/imp/

More information about the pacman-dev mailing list