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

Re: [CFReview] Red-Black Tree

From: Teodor Sigaev <teodor(at)sigaev(dot)ru>
To: Robert Haas <robertmhaas(at)gmail(dot)com>
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 14:21:10
Message-ID: 4B716F56.4060205@sigaev.ru (view raw or flat)
Thread:
Lists: pgsql-hackers
>> 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);
!       step ++;
!       step >>= 1;
!
!       while(step > 0) {
!               int i;

!               for (i = step-1; i < nentry; i += 2 * step)
!                       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
-- 
Teodor Sigaev                                   E-mail: teodor(at)sigaev(dot)ru
                                                    WWW: http://www.sigaev.ru/

In response to

Responses

pgsql-hackers by date

Next:From: Dave PageDate: 2010-02-09 14:22:55
Subject: Re: About psycopg2 (by its author)
Previous:From: Andres FreundDate: 2010-02-09 14:10:22
Subject: Re: Avoiding bad prepared-statement plans.

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