Skip site navigation (1) Skip section navigation (2)

Re: [CFReview] Red-Black Tree

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-10 03:50:29
Message-ID: 603c8f071002091950i118ba144k182fa9dc24feba90@mail.gmail.com (view raw or flat)
Thread:
Lists: pgsql-hackers
2010/2/9 Teodor Sigaev <teodor(at)sigaev(dot)ru>:
>>> 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.
>
> Pls, point me, I don't see that
> !       step |= (step >>  1);
> !       step |= (step >>  2);
> !       step |= (step >>  4);
> !       step |= (step >>  8);
> !       step |= (step >> 16);

So suppose at this point that step is the largest integer that can be
represented...

> !       step ++;

Boom.

> !       step >>= 1;
> !
> !       while(step > 0) {
> !               int i;
>
> !               for (i = step-1; i < nentry; i += 2 * step)

And similarly here... if nentry is greater than maxint/2, then i += 2
* step will overflow, no?

> !                       ginInsertEntry(accum, heapptr, attnum, entries[i]);
>
> !               step >>= 1; /* /2 */
> !       }
>
>
>> Proposed revision attached, with also some rewriting of the comment
>> for that function.
>
> make check fails with your patch:
>
> #3  0x083d2b50 in ExceptionalCondition (conditionName=Could not find the
> frame base for "ExceptionalCondition".
> ) at assert.c:57
> #4  0x081086b6 in ginAppendData (old=0x287f2030, new=0x287f2044,
> arg=0xbfbfd5e4) at ginbulk.c:48
> #5  0x083f5632 in rb_insert (rb=0x2acfe610, data=0x287f2044) at rbtree.c:359
> #6  0x08108968 in ginInsertEntry (accum=0xbfbfd5e4, heapptr=0x28711af4,
> attnum=1, entry=2139062143) at ginbulk.c:135
> #7  0x08108ad9 in ginInsertRecordBA (accum=0xbfbfd5e4, heapptr=0x28711af4,
> attnum=1, entries=0x2ac77068, nentry=6) at ginbulk.c:202

Gaah, sorry.  Presumably I'm running off the end of the array, though
I don't see what I did wrong.  My brain is fried.

...Robert

In response to

Responses

pgsql-hackers by date

Next:From: Tom LaneDate: 2010-02-10 03:51:12
Subject: Re: Some belated patch review for "Buffers" explain analyze patch
Previous:From: M ZDate: 2010-02-10 03:49:44
Subject: Re: CVS checkout source code for different branches

Privacy Policy | About PostgreSQL
Copyright © 1996-2014 The PostgreSQL Global Development Group