Linux Archive

Linux Archive (http://www.linux-archive.org/)
-   ArchLinux Pacman Development (http://www.linux-archive.org/archlinux-pacman-development/)
-   -   [pacman-dev] [PATCH] New alpm_list_join function + tail pointer (http://www.linux-archive.org/archlinux-pacman-development/2068-pacman-dev-patch-new-alpm_list_join-function-tail-pointer.html)

Nagy Gabor 11-21-2007 12:05 PM

[pacman-dev] [PATCH] New alpm_list_join function + tail pointer
 
> 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;h=conflict

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/


_______________________________________________
pacman-dev mailing list
pacman-dev@archlinux.org
http://archlinux.org/mailman/listinfo/pacman-dev

Xavier 11-21-2007 12:20 PM

[pacman-dev] [PATCH] New alpm_list_join function + tail pointer
 
On Wed, Nov 21, 2007 at 02:05:43PM +0100, Nagy Gabor wrote:
> > 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;h=conflict
>
> 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.
>

Well, I forgot to let my box running, so Dan probably couldn't reach it, and
so he reworked the patch himself and added additional comments like the one
above :)

> 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.

_______________________________________________
pacman-dev mailing list
pacman-dev@archlinux.org
http://archlinux.org/mailman/listinfo/pacman-dev


All times are GMT. The time now is 03:23 PM.

VBulletin, Copyright ©2000 - 2014, Jelsoft Enterprises Ltd.
Content Relevant URLs by vBSEO ©2007, Crawlability, Inc.