Joerg Sonnenberger wrote:
> On Thu, Nov 22, 2007 at 05:00:32PM +1300, David Sainty wrote:
>   
>> It is also often cheaper to insert, and modify the existing node if
>> present rather than query before insert, and then repeat the lookup for
>> the insert operation too. It's also more "atomic friendly" than query +
>> insert, should the tree be doing its own locking.
>>     
>
> I guess the critical question here is: how much overhead do you have in
> preparing the new node. As soon as you have to allocate memory, just
> checking for dups first is way cheaper. That's what makes me believe
> that a simple boolean that tells "I was successful" is good enough.
>   
Fair point if the allocation is via malloc(), though it still depends on
the cost of node comparisons - which may be high in itself.

But I have a couple of counterpoints :)

If the node was allocated from a pool then the memory allocation cost
would be near O(1), as opposed to the (something like) O(lg(n)) cost of
the initial duplicate check.

Aside from cost, even in the error case (where the insert is really
never expected to fail) it would be nice to be able to report more
detail on the collision should it happen.

Cheers,

Dave