Neil Conway wrote:
> Gaetano Mendola <mendola@bigfoot.com> writes:
>
>>Why instead of reinvent the whell not use, or at least do a "C" port of
>>stl::list ?
>
>
> Because (a) implementing a linked list is pretty trivial (b) the only
> difficult part is getting the semantics / API right. I don't see how
> std::list would help with (b), and (a) negates the benefit of
> importing the code from elsewhere.
>
> We'd also have to gut std::list, since we wouldn't be able to make use
> of C++ templates.
>
> That said, if you know of any specific techniques from std::list
> implementations that would be useful, please let me know.
An interesting think that stl::list do is to never do
an "if" branch during an insert/remove phase, an stl::list is a struct
with a Master Node:
struct node
{
void* value;
node* next;
node* prev;
}
struct list
{
node* master_node;
};
here respect your proposal a node is saved.
an empty list is initialized with:
master_node = [ ... create a node ... ]
master_node->next = master_node;
master_node->prev = master_node;
and the insertion phase sound like:
void
AddHead(list *l, node *e)
{
node *where = l->master_node->next;
e->next = where;
e->prev = where->prev;
where->prev->next = e;
where->prev = e;
}
void
AddTail(list *l, node *e)
{
node *where = l->master_node;
e->next = where;
e->prev = where->prev;
where->prev->next = e;
where->prev = e;
}
now is very late here ( 04:17 AM ) so I wrote
the wrong code ( not checked ) but show the idea of
avoid "if".
>>PS: My 2 cents: I don't like too much have the lenght inside the list
>>struct.
>
>
> Why not?
What if you will never call the size() on a list doing massive
insert ? May be we need two list, depending on the way we are going
to use it?
I'm too much C++ oriented and another very weak argument is: for the
same reason that STL (at least in gcc) doesn't have it:
http://gcc.gnu.org/ml/gcc-bugs/1998-12/msg00270.html
may be the third point not apply to us.
Regards
Gaetano Mendola
