Re: [CFReview] Red-Black Tree

2010/2/8 Teodor Sigaev <teodor@sigaev.ru>:
>> I think that the code in ginInsertRecordBA() is needlessly complex.
>> As far as I can see, nNodesOnCurrentLevel is always exactly one more
>> than nNodesOnPreviousLevel, and I think step is also basically
>> redundant with both of these although the relationship is a little
>> more complex.  What I would suggest is something like:
>>
>> - initialize step to the largest power of 2 s.t. step<  nentry
>> - while step>  0
>> -- for (i = step; true; i += 2 * step)
>> --- insert entry #i-1
>> --- if i>  nentry - (2 * step)  /* must test before incrementing i, to
>> guard against overflow */
>> ---- break
>> -- step = step / 2
>
> Good idea, implemented.

Hmm.  I think your implementation is prone to overflow in two places -
both when computing step, and also when stepping through the array.
Proposed revision attached, with also some rewriting of the comment
for that function.

...Robert