diff options
| -rw-r--r-- | contrib/intarray/README.intarray | 2 | ||||
| -rw-r--r-- | contrib/intarray/_int.c | 42 |
2 files changed, 20 insertions, 24 deletions
diff --git a/contrib/intarray/README.intarray b/contrib/intarray/README.intarray index 9f0374aca5f..f0138a14842 100644 --- a/contrib/intarray/README.intarray +++ b/contrib/intarray/README.intarray @@ -12,6 +12,8 @@ for additional information. CHANGES: +October 1, 2001 + 1. Change search method in array to binary September 28, 2001 1. gist__int_ops now is without lossy 2. add sort entry in picksplit diff --git a/contrib/intarray/_int.c b/contrib/intarray/_int.c index 3f38cdb0b03..a642998cd44 100644 --- a/contrib/intarray/_int.c +++ b/contrib/intarray/_int.c @@ -1741,33 +1741,29 @@ makepol(WORKSTATE *state) { typedef struct { int4 *arrb; int4 *arre; - int4 *ptr; } CHKVAL; /* * is there value 'val' in array or not ? - */ + */ static bool checkcondition_arr( void *checkval, int4 val ) { -#ifdef BS_DEBUG - elog(NOTICE,"OPERAND %d", val); -#endif - if ( val > *(((CHKVAL*)checkval)->ptr) ) { - while ( ((CHKVAL*)checkval)->ptr < ((CHKVAL*)checkval)->arre ) { - ((CHKVAL*)checkval)->ptr++; - if ( *(((CHKVAL*)checkval)->ptr) == val ) return true; - if ( val < *(((CHKVAL*)checkval)->ptr) ) return false; - } - } else if ( val < *(((CHKVAL*)checkval)->ptr) ) { - while ( ((CHKVAL*)checkval)->ptr > ((CHKVAL*)checkval)->arrb ) { - ((CHKVAL*)checkval)->ptr--; - if ( *(((CHKVAL*)checkval)->ptr) == val ) return true; - if ( val > *(((CHKVAL*)checkval)->ptr) ) return false; - } - } else { - return true; + int4 *StopLow = ((CHKVAL*)checkval)->arrb; + int4 *StopHigh = ((CHKVAL*)checkval)->arre; + int4 *StopMiddle; + + /* Loop invariant: StopLow <= val < StopHigh */ + + while (StopLow < StopHigh) { + StopMiddle = StopLow + (StopHigh - StopLow) / 2; + if (*StopMiddle == val) + return (true); + else if (*StopMiddle < val ) + StopLow = StopMiddle + 1; + else + StopHigh = StopMiddle; } - return false; + return false; } static bool @@ -1818,8 +1814,7 @@ execconsistent( QUERYTYPE *query, ArrayType *array, bool calcnot ) { CHKVAL chkval; chkval.arrb = ARRPTR(array); - chkval.arre = chkval.arrb + ARRNELEMS(array) - 1; - chkval.ptr = chkval.arrb + ARRNELEMS(array)/2; + chkval.arre = chkval.arrb + ARRNELEMS(array); return execute( GETQUERY(query) + query->size-1 , (void*)&chkval, calcnot, @@ -1854,8 +1849,7 @@ boolop(PG_FUNCTION_ARGS) { PREPAREARR(val); chkval.arrb = ARRPTR(val); - chkval.arre = chkval.arrb + ARRNELEMS(val) - 1; - chkval.ptr = chkval.arrb + ARRNELEMS(val)/2; + chkval.arre = chkval.arrb + ARRNELEMS(val); result = execute( GETQUERY(query) + query->size-1 , &chkval, true, |