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