From: | Robert Haas <robertmhaas(at)gmail(dot)com> |
---|---|
To: | Teodor Sigaev <teodor(at)sigaev(dot)ru> |
Cc: | Mark Cave-Ayland <mark(dot)cave-ayland(at)siriusit(dot)co(dot)uk>, Pgsql Hackers <pgsql-hackers(at)postgresql(dot)org> |
Subject: | Re: [CFReview] Red-Black Tree |
Date: | 2010-02-09 04:43:08 |
Message-ID: | 603c8f071002082043x394c2196mac94fab7c2f279dd@mail.gmail.com |
Views: | Raw Message | Whole Thread | Download mbox | Resend email |
Thread: | |
Lists: | pgsql-hackers |
2010/2/8 Teodor Sigaev <teodor(at)sigaev(dot)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
Attachment | Content-Type | Size |
---|---|---|
rbtree-0.12-rmh | application/octet-stream | 33.4 KB |
From | Date | Subject | |
---|---|---|---|
Next Message | Robert Haas | 2010-02-09 04:44:36 | Re: review: More frame options in window functions |
Previous Message | Robert Haas | 2010-02-09 04:40:33 | Re: [CFReview] Red-Black Tree |