Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit7ff432c

Browse files
committed
1. Implemented binary search in array
Oleg Bartunov
1 parent720ca22 commit7ff432c

File tree

2 files changed

+20
-24
lines changed

2 files changed

+20
-24
lines changed

‎contrib/intarray/README.intarray‎

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -12,6 +12,8 @@ for additional information.
1212

1313
CHANGES:
1414

15+
October 1, 2001
16+
1. Change search method in array to binary
1517
September 28, 2001
1618
1. gist__int_ops now is without lossy
1719
2. add sort entry in picksplit

‎contrib/intarray/_int.c‎

Lines changed: 18 additions & 24 deletions
Original file line numberDiff line numberDiff line change
@@ -1741,33 +1741,29 @@ makepol(WORKSTATE *state) {
17411741
typedefstruct {
17421742
int4*arrb;
17431743
int4*arre;
1744-
int4*ptr;
17451744
}CHKVAL;
17461745

17471746
/*
17481747
* is there value 'val' in array or not ?
1749-
*/
1748+
*/
17501749
staticbool
17511750
checkcondition_arr(void*checkval,int4val ) {
1752-
#ifdefBS_DEBUG
1753-
elog(NOTICE,"OPERAND %d",val);
1754-
#endif
1755-
if (val>*(((CHKVAL*)checkval)->ptr) ) {
1756-
while ( ((CHKVAL*)checkval)->ptr< ((CHKVAL*)checkval)->arre ) {
1757-
((CHKVAL*)checkval)->ptr++;
1758-
if (*(((CHKVAL*)checkval)->ptr)==val )return true;
1759-
if (val<*(((CHKVAL*)checkval)->ptr) )return false;
1760-
}
1761-
}elseif (val<*(((CHKVAL*)checkval)->ptr) ) {
1762-
while ( ((CHKVAL*)checkval)->ptr> ((CHKVAL*)checkval)->arrb ) {
1763-
((CHKVAL*)checkval)->ptr--;
1764-
if (*(((CHKVAL*)checkval)->ptr)==val )return true;
1765-
if (val>*(((CHKVAL*)checkval)->ptr) )return false;
1766-
}
1767-
}else {
1768-
return true;
1751+
int4*StopLow= ((CHKVAL*)checkval)->arrb;
1752+
int4*StopHigh= ((CHKVAL*)checkval)->arre;
1753+
int4*StopMiddle;
1754+
1755+
/* Loop invariant: StopLow <= val < StopHigh */
1756+
1757+
while (StopLow<StopHigh) {
1758+
StopMiddle=StopLow+ (StopHigh-StopLow) /2;
1759+
if (*StopMiddle==val)
1760+
return (true);
1761+
elseif (*StopMiddle<val )
1762+
StopLow=StopMiddle+1;
1763+
else
1764+
StopHigh=StopMiddle;
17691765
}
1770-
return false;
1766+
return false;
17711767
}
17721768

17731769
staticbool
@@ -1818,8 +1814,7 @@ execconsistent( QUERYTYPE *query, ArrayType *array, bool calcnot ) {
18181814
CHKVALchkval;
18191815

18201816
chkval.arrb=ARRPTR(array);
1821-
chkval.arre=chkval.arrb+ARRNELEMS(array)-1;
1822-
chkval.ptr=chkval.arrb+ARRNELEMS(array)/2;
1817+
chkval.arre=chkval.arrb+ARRNELEMS(array);
18231818
returnexecute(
18241819
GETQUERY(query)+query->size-1 ,
18251820
(void*)&chkval,calcnot,
@@ -1854,8 +1849,7 @@ boolop(PG_FUNCTION_ARGS) {
18541849

18551850
PREPAREARR(val);
18561851
chkval.arrb=ARRPTR(val);
1857-
chkval.arre=chkval.arrb+ARRNELEMS(val)-1;
1858-
chkval.ptr=chkval.arrb+ARRNELEMS(val)/2;
1852+
chkval.arre=chkval.arrb+ARRNELEMS(val);
18591853
result=execute(
18601854
GETQUERY(query)+query->size-1 ,
18611855
&chkval, true,

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp