On Nov 20, 2007 9:56 AM, Nagy Gabor <ngaba@bibl.u-szeged.hu> wrote:

I'd be happy if I shouldn't resubmit a s/tmp/last/ change ;-) <- this is a trivial sed on my patch.

Please sed the patch and resubmit.

On Tue, Nov 20, 2007 at 03:11:22PM -0600, Aaron Griffin wrote:

...

On Nov 20, 2007 9:56 AM, Nagy Gabor <ngaba@bibl.u-szeged.hu> wrote:

...

I'd be happy if I shouldn't resubmit a s/tmp/last/ change ;-) <- this is a trivial sed on my patch.

Please sed the patch and resubmit.

I did it already:

http://chantry.homelinux.org/~xav/gitweb/gitweb.cgi?p=pacman.git;a=shortlog;... Thanks a lot. I found this comment _very_ useful: /* The list pointers passed in should be considered invalid after calling this function. */ This also shows that the tail pointer can confuse us. 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) Bye, ngaba ---------------------------------------------------- SZTE Egyetemi Könyvtár - http://www.bibl.u-szeged.hu This mail sent through IMP: http://horde.org/imp/

...

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 accordingly. Bye, ngaba ---------------------------------------------------- SZTE Egyetemi Könyvtár - http://www.bibl.u-szeged.hu This mail sent through IMP: http://horde.org/imp/

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;

Well, we don't want it? ;-) /me prefers: alpm_functions treat the input as a sublist of a list (the "whole list" is a special case of this): so we should pass the alpm_list_t parameter and a node parameter to select the sublist (special case: node parameter == NULL: whole list)

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

Overall, if we can live without "sublists", this looks good to me... Bye, ngaba ---------------------------------------------------- SZTE Egyetemi Könyvtár - http://www.bibl.u-szeged.hu This mail sent through IMP: http://horde.org/imp/

Idézés Aaron Griffin <aaronmgriffin@gmail.com>:

On Nov 21, 2007 9:28 AM, Justin Lampley <jrlampley@gmail.com> wrote:

...

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) }

Yeah. Dan suggested the same thing at one point. It's fine by me if someone wants to do this.

Here's another suggestion though, to make all our cleanup headaches... well, less painful.

struct alpm_list_t { alpm_list_node_t *first; alpm_list_node_t *last; alpm_list_fn_free *freefn; size_t size; }

then we rework alpm_list_free to do:

if(list->freefn) { list->freefn(node->data); } free(node):

Here's what we gain: * The ability to say "free all lists" in all alpm calls, while simply setting the freefn to NULL when returning package lists. * Less book keeping * No need for list freeing macros and knowing when and when not to call free_inner * No need for free_inner

Potential con: * Requires homogeneous lists that is not enforced in anyway. We do this now, but it could introduce more potential error based on the fact that we're making this op easier.

Thoughts?

Other con(?): This is an answer to both Aaron and Justin's idea. I like the idea of "list-header" (the new alpm_list_t), but alpm_list_mmerge won't like that (I refer to this possible hackish solution: http://www.archlinux.org/pipermail/pacman-dev/2007-November/010065.html) The problem is, that the list-header adds more bookkeeping to the code and we lose the current sublist-flexibility. And generating new list-headers to sublists would lead to many confusion imho. Bye ---------------------------------------------------- SZTE Egyetemi Könyvtár - http://www.bibl.u-szeged.hu This mail sent through IMP: http://horde.org/imp/