FAQ Search Today's Posts Mark Forums Read
» Video Reviews

» Linux Archive

Linux-archive is a website aiming to archive linux email lists and to make them easily accessible for linux users/developers.


» Sponsor

» Partners

» Sponsor

Go Back   Linux Archive > ArchLinux > ArchLinux Pacman Development

 
 
LinkBack Thread Tools
 
Old 11-21-2007, 01:00 PM
Nagy Gabor
 
Default [pacman-dev] alpm_list_t

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


_______________________________________________
pacman-dev mailing list
pacman-dev@archlinux.org
http://archlinux.org/mailman/listinfo/pacman-dev
 
Old 11-21-2007, 02:28 PM
Justin Lampley
 
Default [pacman-dev] alpm_list_t

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

_______________________________________________
pacman-dev mailing list
pacman-dev@archlinux.org
http://archlinux.org/mailman/listinfo/pacman-dev
 
Old 11-21-2007, 03:18 PM
Nagy Gabor
 
Default [pacman-dev] alpm_list_t

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


_______________________________________________
pacman-dev mailing list
pacman-dev@archlinux.org
http://archlinux.org/mailman/listinfo/pacman-dev
 
Old 11-21-2007, 04:56 PM
"Aaron Griffin"
 
Default [pacman-dev] alpm_list_t

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?

_______________________________________________
pacman-dev mailing list
pacman-dev@archlinux.org
http://archlinux.org/mailman/listinfo/pacman-dev
 
Old 11-22-2007, 09:18 AM
Nagy Gabor
 
Default [pacman-dev] alpm_list_t

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/


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

Thread Tools




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

VBulletin, Copyright ©2000 - 2014, Jelsoft Enterprises Ltd.
Content Relevant URLs by vBSEO ©2007, Crawlability, Inc.
Copyright ©2007 - 2008, www.linux-archive.org