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