On Jul 12, 2008, at 2:42 AM, Steve Friedman wrote: > > > Filip Navara wrote: >> how about actually attaching the patch? :) >> >> - Filip >> >> On Fri, Jul 11, 2008 at 9:23 PM, Steve Friedman >> <[EMAIL PROTECTED]> wrote: >>> I've just started using the rtree extension, and have found that >>> the 32-bit >>> float for the range keys is not appropriate for me. Please find >>> attached a >>> patch for rtree.c (based on v1.5) that allows for int -OR- >>> unsigned int -OR- >>> float operation.
What kind of advantages does using int over float have here? With a little work it might be possible to select int or float at runtime. Do other people who know about such things think that this would be a good option to have? Dan. >>> Steve Friedman > > Not sure where it got deleted (since my inbox shows the attachment). > Included inline... > > --- rtree.c 2008-07-11 15:04:42.000000000 -0400 > +++ rtreemod.c 2008-07-11 15:04:31.000000000 -0400 > @@ -149,13 +149,36 @@ > RtreeConstraint *aConstraint; /* Search constraints. */ > }; > > +#if defined( SQLITE_RTREE_TYPE_INT) > +typedef int ConstraintType; > +# define sqlite3_result_ConstraintType sqlite3_result_int > +# define sqlite3_value_ConstraintType(x) ((int) sqlite3_value_int > ((x))) > +# define sqlite3_snprintf_ConstraintType( a, b, c) \ > + sqlite3_snprintf( (a), (b), " %d", (c)) > + > +#elif defined(SQLITE_RTREE_TYPE_UINT) > +typedef u32 ConstraintType; > +# define sqlite3_result_ConstraintType sqlite3_result_int64 > +# define sqlite3_value_ConstraintType(x) ((u32) > sqlite3_value_int64((x))) > +# define sqlite3_snprintf_ConstraintType( a, b, c) \ > + sqlite3_snprintf( (a), (b), " %u", (c)) > + > +#else > +typedef float ConstraintType; > +# define sqlite3_result_ConstraintType sqlite3_result_double > +# define sqlite3_value_ConstraintType(x) ((float) > sqlite3_value_double((x))) > +# define sqlite3_snprintf_ConstraintType( a, b, c) \ > + sqlite3_snprintf( (a), (b), " %f", (double) (c)) > +#endif > + > + > /* > ** A search constraint. > */ > struct RtreeConstraint { > int iCoord; /* Index of constrained > coordinate */ > int op; /* Constraining operation */ > - float rValue; /* Constraint value. */ > + ConstraintType rValue; /* Constraint value. */ > }; > > /* Possible values for RtreeConstraint.op */ > @@ -198,7 +221,7 @@ > */ > struct RtreeCell { > i64 iRowid; > - float aCoord[RTREE_MAX_DIMENSIONS*2]; > + ConstraintType aCoord[RTREE_MAX_DIMENSIONS*2]; > }; > > #define MAX(x,y) ((x) < (y) ? (y) : (x)) > @@ -211,14 +234,14 @@ > static int readInt16(u8 *p){ > return (p[0]<<8) + p[1]; > } > -static float readReal32(u8 *p){ > +static ConstraintType readReal32(u8 *p){ > u32 i = ( > (((u32)p[0]) << 24) + > (((u32)p[1]) << 16) + > (((u32)p[2]) << 8) + > (((u32)p[3]) << 0) > ); > - return *(float *)&i; > + return *(ConstraintType *)&i; > } > static i64 readInt64(u8 *p){ > return ( > @@ -243,9 +266,9 @@ > p[1] = (i>> 0)&0xFF; > return 2; > } > -static int writeReal32(u8 *p, float f){ > +static int writeReal32(u8 *p, ConstraintType f){ > u32 i; > - assert( sizeof(float)==4 ); > + assert( sizeof(ConstraintType)==4 ); > assert( sizeof(u32)==4 ); > i = *(u32 *)&f; > p[0] = (i>>24)&0xFF; > @@ -543,7 +566,7 @@ > /* > ** Return coordinate iCoord from cell iCell in node pNode. > */ > -static float nodeGetCoord( > +static ConstraintType nodeGetCoord( > Rtree *pRtree, > RtreeNode *pNode, > int iCell, > @@ -721,8 +744,8 @@ > for(ii=0; ii<pCursor->nConstraint; ii++){ > RtreeConstraint *p = &pCursor->aConstraint[ii]; > > - float cell_min = cell.aCoord[(p->iCoord>>1)*2]; > - float cell_max = cell.aCoord[(p->iCoord>>1)*2+1]; > + ConstraintType cell_min = cell.aCoord[(p->iCoord>>1)*2]; > + ConstraintType cell_max = cell.aCoord[(p->iCoord>>1)*2+1]; > assert( cell_min<=cell_max ); > > switch( p->op ){ > @@ -769,7 +792,7 @@ > nodeGetCell(pRtree, pCursor->pNode, pCursor->iCell, &cell); > for(ii=0; ii<pCursor->nConstraint; ii++){ > RtreeConstraint *p = &pCursor->aConstraint[ii]; > - float cell_val = cell.aCoord[p->iCoord]; > + ConstraintType cell_val = cell.aCoord[p->iCoord]; > int res; > switch( p->op ){ > case RTREE_LE: res = (cell_val<=p->rValue); break; > @@ -935,8 +958,8 @@ > i64 iRowid = nodeGetRowid(pRtree, pCsr->pNode, pCsr->iCell); > sqlite3_result_int64(ctx, iRowid); > }else{ > - float fCoord = nodeGetCoord(pRtree, pCsr->pNode, pCsr->iCell, > i-1); > - sqlite3_result_double(ctx, fCoord); > + ConstraintType fCoord = nodeGetCoord(pRtree, pCsr->pNode, > pCsr->iCell, i-1); > + sqlite3_result_ConstraintType(ctx, fCoord); > } > > return SQLITE_OK; > @@ -1009,7 +1032,7 @@ > RtreeConstraint *p = &pCsr->aConstraint[ii]; > p->op = idxStr[ii*2]; > p->iCoord = idxStr[ii*2+1]-'a'; > - p->rValue = sqlite3_value_double(argv[ii]); > + p->rValue = sqlite3_value_ConstraintType(argv[ii]); > } > } > } > @@ -1157,8 +1180,8 @@ > /* > ** Return the N-dimensional volumn of the cell stored in *p. > */ > -static float cellArea(Rtree *pRtree, RtreeCell *p){ > - float area = 1.0; > +static ConstraintType cellArea(Rtree *pRtree, RtreeCell *p){ > + ConstraintType area = 1.0; > int ii; > for(ii=0; ii<(pRtree->nDim*2); ii+=2){ > area = area * (p->aCoord[ii+1] - p->aCoord[ii]); > @@ -1170,8 +1193,8 @@ > ** Return the margin length of cell p. The margin length is the sum > ** of the objects size in each dimension. > */ > -static float cellMargin(Rtree *pRtree, RtreeCell *p){ > - float margin = 0.0; > +static ConstraintType cellMargin(Rtree *pRtree, RtreeCell *p){ > + ConstraintType margin = 0.0; > int ii; > for(ii=0; ii<(pRtree->nDim*2); ii+=2){ > margin += (p->aCoord[ii+1] - p->aCoord[ii]); > @@ -1193,8 +1216,8 @@ > /* > ** Return the amount cell p would grow by if it were unioned with > pCell. > */ > -static float cellGrowth(Rtree *pRtree, RtreeCell *p, RtreeCell > *pCell){ > - float area; > +static ConstraintType cellGrowth(Rtree *pRtree, RtreeCell *p, > RtreeCell > *pCell){ > + ConstraintType area; > RtreeCell cell; > memcpy(&cell, p, sizeof(RtreeCell)); > area = cellArea(pRtree, &cell); > @@ -1203,7 +1226,7 @@ > } > > #if VARIANT_RSTARTREE_CHOOSESUBTREE || VARIANT_RSTARTREE_SPLIT > -static float cellOverlap( > +static ConstraintType cellOverlap( > Rtree *pRtree, > RtreeCell *p, > RtreeCell *aCell, > @@ -1211,15 +1234,15 @@ > int iExclude > ){ > int ii; > - float overlap = 0.0; > + ConstraintType overlap = 0.0; > for(ii=0; ii<nCell; ii++){ > if( ii!=iExclude ){ > int jj; > - float o = 1.0; > + ConstraintType o = 1.0; > for(jj=0; jj<(pRtree->nDim*2); jj+=2){ > > - float x1 = MAX(p->aCoord[jj], aCell[ii].aCoord[jj]); > - float x2 = MIN(p->aCoord[jj+1], aCell[ii].aCoord[jj+1]); > + ConstraintType x1 = MAX(p->aCoord[jj], aCell[ii].aCoord[jj]); > + ConstraintType x2 = MIN(p->aCoord[jj+1], aCell[ii].aCoord > [jj+1]); > > if( x2<x1 ){ > o = 0.0; > @@ -1236,7 +1259,7 @@ > #endif > > #if VARIANT_RSTARTREE_CHOOSESUBTREE > -static float cellOverlapEnlargement( > +static ConstraintType cellOverlapEnlargement( > Rtree *pRtree, > RtreeCell *p, > RtreeCell *pInsert, > @@ -1244,8 +1267,8 @@ > int nCell, > int iExclude > ){ > - float before; > - float after; > + ConstraintType before; > + ConstraintType after; > before = cellOverlap(pRtree, p, aCell, nCell, iExclude); > cellUnion(pRtree, p, pInsert); > after = cellOverlap(pRtree, p, aCell, nCell, iExclude); > @@ -1273,9 +1296,9 @@ > int iCell; > sqlite3_int64 iBest; > > - float fMinGrowth; > - float fMinArea; > - float fMinOverlap; > + ConstraintType fMinGrowth; > + ConstraintType fMinArea; > + ConstraintType fMinOverlap; > > int nCell = NCELL(pNode); > RtreeCell cell; > @@ -1304,9 +1327,9 @@ > ** the smallest area. > */ > for(iCell=0; iCell<nCell; iCell++){ > - float growth; > - float area; > - float overlap = 0.0; > + ConstraintType growth; > + ConstraintType area; > + ConstraintType overlap = 0.0; > nodeGetCell(pRtree, pNode, iCell, &cell); > growth = cellGrowth(pRtree, &cell, pCell); > area = cellArea(pRtree, &cell); > @@ -1418,7 +1441,7 @@ > int i; > int iLeftSeed = 0; > int iRightSeed = 1; > - float maxNormalInnerWidth = 0.0; > + ConstraintType maxNormalInnerWidth = 0.0; > > /* Pick two "seed" cells from the array of cells. The algorithm > used > ** here is the LinearPickSeeds algorithm from Gutman[1984]. The > @@ -1426,18 +1449,18 @@ > ** variables iLeftSeek and iRightSeed. > */ > for(i=0; i<pRtree->nDim; i++){ > - float x1 = aCell[0].aCoord[i*2]; > - float x2 = aCell[0].aCoord[i*2+1]; > - float x3 = x1; > - float x4 = x2; > + ConstraintType x1 = aCell[0].aCoord[i*2]; > + ConstraintType x2 = aCell[0].aCoord[i*2+1]; > + ConstraintType x3 = x1; > + ConstraintType x4 = x2; > int jj; > > int iCellLeft = 0; > int iCellRight = 0; > > for(jj=1; jj<nCell; jj++){ > - float left = aCell[jj].aCoord[i*2]; > - float right = aCell[jj].aCoord[i*2+1]; > + ConstraintType left = aCell[jj].aCoord[i*2]; > + ConstraintType right = aCell[jj].aCoord[i*2+1]; > > if( left<x1 ) x1 = left; > if( right>x4 ) x4 = right; > @@ -1452,7 +1475,7 @@ > } > > if( x4!=x1 ){ > - float normalwidth = (x3 - x2) / (x4 - x1); > + ConstraintType normalwidth = (x3 - x2) / (x4 - x1); > if( normalwidth>maxNormalInnerWidth ){ > iLeftSeed = iCellLeft; > iRightSeed = iCellRight; > @@ -1481,13 +1504,13 @@ > #define FABS(a) ((a)<0.0?-1.0*(a):(a)) > > int iSelect = -1; > - float fDiff; > + ConstraintType fDiff; > int ii; > for(ii=0; ii<nCell; ii++){ > if( aiUsed[ii]==0 ){ > - float left = cellGrowth(pRtree, pLeftBox, &aCell[ii]); > - float right = cellGrowth(pRtree, pLeftBox, &aCell[ii]); > - float diff = FABS(right-left); > + ConstraintType left = cellGrowth(pRtree, pLeftBox, &aCell[ii]); > + ConstraintType right = cellGrowth(pRtree, pLeftBox, &aCell > [ii]); > + ConstraintType diff = FABS(right-left); > if( iSelect<0 || diff>fDiff ){ > fDiff = diff; > iSelect = ii; > @@ -1514,13 +1537,13 @@ > > int iLeftSeed = 0; > int iRightSeed = 1; > - float fWaste = 0.0; > + ConstraintType fWaste = 0.0; > > for(ii=0; ii<nCell; ii++){ > for(jj=ii+1; jj<nCell; jj++){ > - float right = cellArea(pRtree, &aCell[jj]); > - float growth = cellGrowth(pRtree, &aCell[ii], &aCell[jj]); > - float waste = growth - right; > + ConstraintType right = cellArea(pRtree, &aCell[jj]); > + ConstraintType growth = cellGrowth(pRtree, &aCell[ii], &aCell > [jj]); > + ConstraintType waste = growth - right; > > if( waste>fWaste ){ > iLeftSeed = ii; > @@ -1555,7 +1578,7 @@ > static void SortByDistance( > int *aIdx, > int nIdx, > - float *aDistance, > + ConstraintType *aDistance, > int *aSpare > ){ > if( nIdx>1 ){ > @@ -1581,8 +1604,8 @@ > aIdx[iLeft+iRight] = aLeft[iLeft]; > iLeft++; > }else{ > - float fLeft = aDistance[aLeft[iLeft]]; > - float fRight = aDistance[aRight[iRight]]; > + ConstraintType fLeft = aDistance[aLeft[iLeft]]; > + ConstraintType fRight = aDistance[aRight[iRight]]; > if( fLeft<fRight ){ > aIdx[iLeft+iRight] = aLeft[iLeft]; > iLeft++; > @@ -1598,8 +1621,8 @@ > { > int jj; > for(jj=1; jj<nIdx; jj++){ > - float left = aDistance[aIdx[jj-1]]; > - float right = aDistance[aIdx[jj]]; > + ConstraintType left = aDistance[aIdx[jj-1]]; > + ConstraintType right = aDistance[aIdx[jj]]; > assert( left<=right ); > } > } > @@ -1641,10 +1664,10 @@ > memcpy(aSpare, aLeft, sizeof(int)*nLeft); > aLeft = aSpare; > while( iLeft<nLeft || iRight<nRight ){ > - float xleft1 = aCell[aLeft[iLeft]].aCoord[iDim*2]; > - float xleft2 = aCell[aLeft[iLeft]].aCoord[iDim*2+1]; > - float xright1 = aCell[aRight[iRight]].aCoord[iDim*2]; > - float xright2 = aCell[aRight[iRight]].aCoord[iDim*2+1]; > + ConstraintType xleft1 = aCell[aLeft[iLeft]].aCoord[iDim*2]; > + ConstraintType xleft2 = aCell[aLeft[iLeft]].aCoord[iDim*2+1]; > + ConstraintType xright1 = aCell[aRight[iRight]].aCoord[iDim*2]; > + ConstraintType xright2 = aCell[aRight[iRight]].aCoord[iDim*2 > +1]; > > if( (iLeft!=nLeft) && ((iRight==nRight) > || (xleft1<xright1) > @@ -1663,10 +1686,10 @@ > { > int jj; > for(jj=1; jj<nIdx; jj++){ > - float xleft1 = aCell[aIdx[jj-1]].aCoord[iDim*2]; > - float xleft2 = aCell[aIdx[jj-1]].aCoord[iDim*2+1]; > - float xright1 = aCell[aIdx[jj]].aCoord[iDim*2]; > - float xright2 = aCell[aIdx[jj]].aCoord[iDim*2+1]; > + ConstraintType xleft1 = aCell[aIdx[jj-1]].aCoord[iDim*2]; > + ConstraintType xleft2 = aCell[aIdx[jj-1]].aCoord[iDim*2+1]; > + ConstraintType xright1 = aCell[aIdx[jj]].aCoord[iDim*2]; > + ConstraintType xright2 = aCell[aIdx[jj]].aCoord[iDim*2+1]; > assert( xleft1<=xright1 && (xleft1<xright1 || > xleft2<=xright2) ); > } > } > @@ -1693,7 +1716,7 @@ > > int iBestDim; > int iBestSplit; > - float fBestMargin; > + ConstraintType fBestMargin; > > int nByte = (pRtree->nDim+1)*(sizeof(int*)+nCell*sizeof(int)); > > @@ -1714,9 +1737,9 @@ > } > > for(ii=0; ii<pRtree->nDim; ii++){ > - float margin = 0.0; > - float fBestOverlap; > - float fBestArea; > + ConstraintType margin = 0.0; > + ConstraintType fBestOverlap; > + ConstraintType fBestArea; > int iBestLeft; > int nLeft; > > @@ -1728,8 +1751,8 @@ > RtreeCell left; > RtreeCell right; > int kk; > - float overlap; > - float area; > + ConstraintType overlap; > + ConstraintType area; > > memcpy(&left, &aCell[aaSorted[ii][0]], sizeof(RtreeCell)); > memcpy(&right, &aCell[aaSorted[ii][nCell-1]], sizeof > (RtreeCell)); > @@ -1809,7 +1832,7 @@ > for(i=nCell-2; i>0; i--){ > RtreeCell *pNext; > pNext = PickNext(pRtree, aCell, nCell, pBboxLeft, pBboxRight, > aiUsed); > - float diff = > + ConstraintType diff = > cellGrowth(pRtree, pBboxLeft, pNext) - > cellGrowth(pRtree, pBboxRight, pNext) > ; > @@ -2099,14 +2122,14 @@ > int *aOrder; > int *aSpare; > RtreeCell *aCell; > - float *aDistance; > + ConstraintType *aDistance; > int nCell; > - float aCenterCoord[RTREE_MAX_DIMENSIONS]; > + ConstraintType aCenterCoord[RTREE_MAX_DIMENSIONS]; > int iDim; > int ii; > int rc = SQLITE_OK; > > - memset(aCenterCoord, 0, sizeof(float)*RTREE_MAX_DIMENSIONS); > + memset(aCenterCoord, 0, sizeof(ConstraintType) > *RTREE_MAX_DIMENSIONS); > > nCell = NCELL(pNode)+1; > > @@ -2117,14 +2140,14 @@ > sizeof(RtreeCell) + /* aCell array */ > sizeof(int) + /* aOrder array */ > sizeof(int) + /* aSpare array */ > - sizeof(float) /* aDistance array */ > + sizeof(ConstraintType) /* aDistance array */ > )); > if( !aCell ){ > return SQLITE_NOMEM; > } > aOrder = (int *)&aCell[nCell]; > aSpare = (int *)&aOrder[nCell]; > - aDistance = (float *)&aSpare[nCell]; > + aDistance = (ConstraintType *)&aSpare[nCell]; > > for(ii=0; ii<nCell; ii++){ > if( ii==(nCell-1) ){ > @@ -2139,13 +2162,13 @@ > } > } > for(iDim=0; iDim<pRtree->nDim; iDim++){ > - aCenterCoord[iDim] = aCenterCoord[iDim]/((float)nCell*2.0); > + aCenterCoord[iDim] = aCenterCoord[iDim]/((ConstraintType) > nCell*2.0); > } > > for(ii=0; ii<nCell; ii++){ > aDistance[ii] = 0.0; > for(iDim=0; iDim<pRtree->nDim; iDim++){ > - float coord = aCell[ii].aCoord[iDim*2+1] - aCell[ii].aCoord > [iDim*2]; > + ConstraintType coord = aCell[ii].aCoord[iDim*2+1] - > aCell[ii].aCoord[iDim*2]; > aDistance[ii] += > (coord-aCenterCoord[iDim])*(coord-aCenterCoord[iDim]); > } > } > @@ -2388,8 +2411,8 @@ > /* Populate the cell.aCoord[] array. The first coordinate is > azData[3]. */ > assert( nData==(pRtree->nDim*2 + 3) ); > for(ii=0; ii<(pRtree->nDim*2); ii+=2){ > - cell.aCoord[ii] = (float)sqlite3_value_double(azData[ii+3]); > - cell.aCoord[ii+1] = (float)sqlite3_value_double(azData[ii+4]); > + cell.aCoord[ii] = sqlite3_value_ConstraintType(azData[ii+3]); > + cell.aCoord[ii+1] = sqlite3_value_ConstraintType(azData[ii+4]); > if( cell.aCoord[ii]>cell.aCoord[ii+1] ){ > rc = SQLITE_CONSTRAINT; > goto constraint; > @@ -2716,7 +2739,7 @@ > sqlite3_snprintf(512-nCell,&zCell[nCell],"%d", cell.iRowid); > nCell = strlen(zCell); > for(jj=0; jj<tree.nDim*2; jj++){ > - sqlite3_snprintf(512-nCell,&zCell[nCell]," > %f",(double)cell.aCoord[jj]); > + sqlite3_snprintf_ConstraintType(512-nCell,&zCell[nCell], > cell.aCoord[jj]); > nCell = strlen(zCell); > } > > > > _______________________________________________ > sqlite-users mailing list > sqlite-users@sqlite.org > http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users _______________________________________________ sqlite-users mailing list sqlite-users@sqlite.org http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users