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. >> >> 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