NotificationsYou must be signed in to change notification settings
Fork6
Star31

Commit7ff432c

committed

1. Implemented binary search in array

Oleg Bartunov

1 parent720ca22 commit7ff432cCopy full SHA for 7ff432c

File tree

2 files changed

+20

-24

lines changed

contrib/intarray
- README.intarray
- _int.c

2 files changed

+20

-24

lines changed

`‎contrib/intarray/README.intarray`

Lines changed: 2 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -12,6 +12,8 @@ for additional information.`
`12`	`12`
`13`	`13`	`CHANGES:`
`14`	`14`
	`15`	`+October 1, 2001`
	`16`	`+ 1. Change search method in array to binary`
`15`	`17`	`September 28, 2001`
`16`	`18`	`1. gist__int_ops now is without lossy`
`17`	`19`	`2. add sort entry in picksplit`

`‎contrib/intarray/_int.c`

Lines changed: 18 additions & 24 deletions

Original file line number	Diff line number	Diff line change
`@@ -1741,33 +1741,29 @@ makepol(WORKSTATE *state) {`
`1741`	`1741`	`typedefstruct {`
`1742`	`1742`	`int4*arrb;`
`1743`	`1743`	`int4*arre;`
`1744`		`-int4*ptr;`
`1745`	`1744`	`}CHKVAL;`
`1746`	`1745`
`1747`	`1746`	`/*`
`1748`	`1747`	`* is there value 'val' in array or not ?`
`1749`		`- */`
	`1748`	`+ */`
`1750`	`1749`	`staticbool`
`1751`	`1750`	`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`	`+int4StopLow= ((CHKVAL)checkval)->arrb;`
	`1752`	`+int4StopHigh= ((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;`
`1769`	`1765`	`}`
`1770`		`-return false;`
	`1766`	`+return false;`
`1771`	`1767`	`}`
`1772`	`1768`
`1773`	`1769`	`staticbool`
`@@ -1818,8 +1814,7 @@ execconsistent( QUERYTYPE query, ArrayType array, bool calcnot ) {`
`1818`	`1814`	`CHKVALchkval;`
`1819`	`1815`
`1820`	`1816`	`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);`
`1823`	`1818`	`returnexecute(`
`1824`	`1819`	`GETQUERY(query)+query->size-1 ,`
`1825`	`1820`	`(void*)&chkval,calcnot,`
`@@ -1854,8 +1849,7 @@ boolop(PG_FUNCTION_ARGS) {`
`1854`	`1849`
`1855`	`1850`	`PREPAREARR(val);`
`1856`	`1851`	`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);`
`1859`	`1853`	`result=execute(`
`1860`	`1854`	`GETQUERY(query)+query->size-1 ,`
`1861`	`1855`	`&chkval, true,`

0 commit comments

Comments

(0)

Movatterモバイル変換

Navigation Menu

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

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Uh oh!

Commit7ff432c

File tree

2 files changed

2 files changed

`‎contrib/intarray/README.intarray`

`‎contrib/intarray/_int.c`

0 commit comments