Re: equal() perf tweak

Neil Conway wrote:

> Gaetano Mendola <mendola(at)bigfoot(dot)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