[pacman-dev] alpm_list_t

[Justin Lampley]

Nagy Gabor wrote:
> 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
> accordingly.
> 
> Bye, ngaba
> 
> 
> ----------------------------------------------------
> SZTE Egyetemi Könyvtár - http://www.bibl.u-szeged.hu
> This mail sent through IMP: http://horde.org/imp/
> 
> 
> _______________________________________________
> pacman-dev mailing list
> pacman-dev at archlinux.org
> http://archlinux.org/mailman/listinfo/pacman-dev

One possible solution is to create a alpm_list_t struct and a 
alpm_list_node_t struct like Nagy suggested in another thread.  The 
alpm_list_t struct would contain:

struct alpm_list_t {
alpm_list_node_t *first;
alpm_list_node_t *last;
int size; (possibly)
}

We would then just turn what we currently have labeled as alpm_list_t 
into alpm_list_node_t.  This would ensure that the add and remove 
functions are passed a genuine list and not a node in a list.  It would 
also eliminate the need of having the head point to the tail so we have 
a quick reference to the last item in the list.

The join function would then accept list1 and list2 and list2 gets 
appended to list1.

list1->last->next = list2->first;
list2->first->prev = list1->last;
list1->last = list2->last;

since we do not want a list being a subset of another list we do
list2->first = NULL;
list2->last = NULL;

If you had the size then you could also speed up alpm_list_nth since you 
could determine whether starting from the first item or the last item 
would bring you to the nth item faster.

Of course, all this would require a lot of work to change over since all 
the list looping would have to be on alpm_list_node_t types instead of 
alpm_list_t types.

Just thought I would throw this idea out there and see what the rest of 
you thought.

Justin