Dan wrote: > 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, I think the need for integer support is to avoid floating point rounding errors that might cause you to miss a key otherwise. I think this would be a nice feature to have. I think it should be implemented at runtime because if I ever have an application that need both say time (int) and spatial rtrees (floats) then it puts me into a problem of not being able to support both in a single build. -Steve >>>> 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 _______________________________________________ sqlite-users mailing list sqlite-users@sqlite.org http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users