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
> [email protected]
> http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users
_______________________________________________
sqlite-users mailing list
[email protected]
http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users
