Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
| Comment: | Continuing work on the new custom query mechanism for r-tree. |
|---|---|
| Downloads: | Tarball | ZIP archive | SQL archive |
| Timelines: | family | ancestors | descendants | both | rtree-enhancements |
| Files: | files | file ages | folders |
| SHA1: | ca7357e66ca60f59477b1db000c2cdae |
| User & Date: | drh 2014-04-13 16:10:09 |
Context
|
2014-04-14
| ||
| 12:18 | Remove over 300 lines of unused code, code that implemented the older Guttman insertion algorithms that are no longer used. check-in: 3ba5f295 user: drh tags: rtree-enhancements | |
|
2014-04-13
| ||
| 16:10 | Continuing work on the new custom query mechanism for r-tree. check-in: ca7357e6 user: drh tags: rtree-enhancements | |
|
2014-04-12
| ||
| 17:44 | Continuing clean-up of the R-Tree module in preparation for cutting in the new generalized query mechanism. check-in: 66c858f2 user: drh tags: rtree-enhancements | |
Changes
Changes to ext/rtree/rtree.c.
268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 ... 856 857 858 859 860 861 862 863 864 865 866 867 868 869 870 ... 911 912 913 914 915 916 917 918 919 920 921 922 923 924 925 ... 941 942 943 944 945 946 947 948 949 950 951 952 953 954 955 956 957 958 959 960 961 962 963 ... 991 992 993 994 995 996 997 998 999 1000 1001 1002 1003 1004 1005 1006 1007 1008 1009 .... 1226 1227 1228 1229 1230 1231 1232 1233 1234 1235 1236 1237 1238 1239 1240 1241 1242 1243 1244 1245 1246 1247 1248 1249 1250 1251 1252 1253 1254 1255 1256 1257 1258 1259 1260 1261 1262 1263 1264 1265 1266 1267 1268 1269 1270 1271 1272 1273 .... 1322 1323 1324 1325 1326 1327 1328 1329 1330 1331 1332 1333 1334 1335 1336 1337 1338 |
/*
** A search constraint.
*/
struct RtreeConstraint {
int iCoord; /* Index of constrained coordinate */
int op; /* Constraining operation */
RtreeDValue rValue; /* Constraint value. */
int (*xGeom)(sqlite3_rtree_geometry*, int, RtreeDValue*, int*);
sqlite3_rtree_geometry *pGeom; /* Constraint callback argument for a MATCH */
};
/* Possible values for RtreeConstraint.op */
#define RTREE_EQ 0x41
#define RTREE_LE 0x42
#define RTREE_LT 0x43
#define RTREE_GE 0x44
#define RTREE_GT 0x45
#define RTREE_MATCH 0x46
/*
** An rtree structure node.
*/
struct RtreeNode {
RtreeNode *pParent; /* Parent node */
i64 iNode; /* The node number */
................................................................................
/*
** Free the RtreeCursor.aConstraint[] array and its contents.
*/
static void freeCursorConstraints(RtreeCursor *pCsr){
if( pCsr->aConstraint ){
int i; /* Used to iterate through constraint array */
for(i=0; i<pCsr->nConstraint; i++){
sqlite3_rtree_geometry *pGeom = pCsr->aConstraint[i].pGeom;
if( pGeom ){
if( pGeom->xDelUser ) pGeom->xDelUser(pGeom->pUser);
sqlite3_free(pGeom);
}
}
sqlite3_free(pCsr->aConstraint);
pCsr->aConstraint = 0;
................................................................................
assert( pConstraint->op==RTREE_MATCH );
assert( pConstraint->pGeom );
for(i=0; i<nCoord; i++){
aCoord[i] = DCOORD(pCell->aCoord[i]);
}
return pConstraint->xGeom(pConstraint->pGeom, nCoord, aCoord, pbRes);
}
/*
** Cursor pCursor currently points to a cell in a non-leaf page.
** Set *pbEof to true if the sub-tree headed by the cell is filtered
** (excluded) by the constraints in the pCursor->aConstraint[]
** array, or false otherwise.
................................................................................
assert(p->op==RTREE_LE || p->op==RTREE_LT || p->op==RTREE_GE
|| p->op==RTREE_GT || p->op==RTREE_EQ || p->op==RTREE_MATCH
);
switch( p->op ){
case RTREE_LE: case RTREE_LT:
bRes = p->rValue<cell_min;
break;
case RTREE_GE: case RTREE_GT:
bRes = p->rValue>cell_max;
break;
case RTREE_EQ:
bRes = (p->rValue>cell_max || p->rValue<cell_min);
break;
default: {
assert( p->op==RTREE_MATCH );
rc = testRtreeGeom(pRtree, p, &cell, &bRes);
bRes = !bRes;
break;
................................................................................
RtreeConstraint *p = &pCursor->aConstraint[ii];
RtreeDValue coord = DCOORD(cell.aCoord[p->iCoord]);
int res;
assert(p->op==RTREE_LE || p->op==RTREE_LT || p->op==RTREE_GE
|| p->op==RTREE_GT || p->op==RTREE_EQ || p->op==RTREE_MATCH
);
switch( p->op ){
case RTREE_LE: res = (coord<=p->rValue); break;
case RTREE_LT: res = (coord<p->rValue); break;
case RTREE_GE: res = (coord>=p->rValue); break;
case RTREE_GT: res = (coord>p->rValue); break;
case RTREE_EQ: res = (coord==p->rValue); break;
default: {
int rc;
assert( p->op==RTREE_MATCH );
rc = testRtreeGeom(pRtree, p, &cell, &res);
if( rc!=SQLITE_OK ){
return rc;
}
................................................................................
** This function is called to configure the RtreeConstraint object passed
** as the second argument for a MATCH constraint. The value passed as the
** first argument to this function is the right-hand operand to the MATCH
** operator.
*/
static int deserializeGeometry(sqlite3_value *pValue, RtreeConstraint *pCons){
RtreeMatchArg *p;
sqlite3_rtree_geometry *pGeom;
int nBlob;
/* Check that value is actually a blob. */
if( sqlite3_value_type(pValue)!=SQLITE_BLOB ) return SQLITE_ERROR;
/* Check that the blob is roughly the right size. */
nBlob = sqlite3_value_bytes(pValue);
if( nBlob<(int)sizeof(RtreeMatchArg)
|| ((nBlob-sizeof(RtreeMatchArg))%sizeof(RtreeDValue))!=0
){
return SQLITE_ERROR;
}
pGeom = (sqlite3_rtree_geometry *)sqlite3_malloc(
sizeof(sqlite3_rtree_geometry) + nBlob
);
if( !pGeom ) return SQLITE_NOMEM;
memset(pGeom, 0, sizeof(sqlite3_rtree_geometry));
p = (RtreeMatchArg *)&pGeom[1];
memcpy(p, sqlite3_value_blob(pValue), nBlob);
if( p->magic!=RTREE_GEOMETRY_MAGIC
|| nBlob!=(int)(sizeof(RtreeMatchArg) + (p->nParam-1)*sizeof(RtreeDValue))
){
sqlite3_free(pGeom);
return SQLITE_ERROR;
}
pGeom->pContext = p->cb.pContext;
pGeom->nParam = p->nParam;
pGeom->aParam = p->aParam;
pCons->xGeom = p->cb.xGeom;
pCons->pGeom = pGeom;
return SQLITE_OK;
}
/*
** Rtree virtual table module xFilter method.
*/
................................................................................
*/
rc = deserializeGeometry(argv[ii], p);
if( rc!=SQLITE_OK ){
break;
}
}else{
#ifdef SQLITE_RTREE_INT_ONLY
p->rValue = sqlite3_value_int64(argv[ii]);
#else
p->rValue = sqlite3_value_double(argv[ii]);
#endif
}
}
}
}
if( rc==SQLITE_OK ){
|
> | | < > > > | > | > | | | | | | | | | | | < < | | | | | |
268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 ... 860 861 862 863 864 865 866 867 868 869 870 871 872 873 874 ... 915 916 917 918 919 920 921 922 923 924 925 926 927 928 929 930 ... 946 947 948 949 950 951 952 953 954 955 956 957 958 959 960 961 962 963 964 965 966 967 968 ... 996 997 998 999 1000 1001 1002 1003 1004 1005 1006 1007 1008 1009 1010 1011 1012 1013 1014 .... 1231 1232 1233 1234 1235 1236 1237 1238 1239 1240 1241 1242 1243 1244 1245 1246 1247 1248 1249 1250 1251 1252 1253 1254 1255 1256 1257 1258 1259 1260 1261 1262 1263 1264 1265 1266 1267 1268 1269 1270 1271 1272 1273 1274 1275 1276 .... 1325 1326 1327 1328 1329 1330 1331 1332 1333 1334 1335 1336 1337 1338 1339 1340 1341 |
/*
** A search constraint.
*/
struct RtreeConstraint {
int iCoord; /* Index of constrained coordinate */
int op; /* Constraining operation */
union {
RtreeDValue rValue; /* Constraint value. */
int (*xGeom)(sqlite3_rtree_geometry*,int,RtreeDValue*,int*);
int (*xQueryFunc)(sqlite3_rtree_query_info*);
} u;
sqlite3_rtree_query_info *pGeom; /* xGeom and xQueryFunc argument */
};
/* Possible values for RtreeConstraint.op */
#define RTREE_EQ 0x41
#define RTREE_LE 0x42
#define RTREE_LT 0x43
#define RTREE_GE 0x44
#define RTREE_GT 0x45
#define RTREE_MATCH 0x46 /* Old-style sqlite3_rtree_geometry_callback() */
#define RTREE_QUERY 0x47 /* New-style sqlite3_rtree_query_callback() */
/*
** An rtree structure node.
*/
struct RtreeNode {
RtreeNode *pParent; /* Parent node */
i64 iNode; /* The node number */
................................................................................
/*
** Free the RtreeCursor.aConstraint[] array and its contents.
*/
static void freeCursorConstraints(RtreeCursor *pCsr){
if( pCsr->aConstraint ){
int i; /* Used to iterate through constraint array */
for(i=0; i<pCsr->nConstraint; i++){
sqlite3_rtree_query_info *pGeom = pCsr->aConstraint[i].pGeom;
if( pGeom ){
if( pGeom->xDelUser ) pGeom->xDelUser(pGeom->pUser);
sqlite3_free(pGeom);
}
}
sqlite3_free(pCsr->aConstraint);
pCsr->aConstraint = 0;
................................................................................
assert( pConstraint->op==RTREE_MATCH );
assert( pConstraint->pGeom );
for(i=0; i<nCoord; i++){
aCoord[i] = DCOORD(pCell->aCoord[i]);
}
return pConstraint->u.xGeom((sqlite3_rtree_geometry*)pConstraint->pGeom,
nCoord, aCoord, pbRes);
}
/*
** Cursor pCursor currently points to a cell in a non-leaf page.
** Set *pbEof to true if the sub-tree headed by the cell is filtered
** (excluded) by the constraints in the pCursor->aConstraint[]
** array, or false otherwise.
................................................................................
assert(p->op==RTREE_LE || p->op==RTREE_LT || p->op==RTREE_GE
|| p->op==RTREE_GT || p->op==RTREE_EQ || p->op==RTREE_MATCH
);
switch( p->op ){
case RTREE_LE: case RTREE_LT:
bRes = p->u.rValue<cell_min;
break;
case RTREE_GE: case RTREE_GT:
bRes = p->u.rValue>cell_max;
break;
case RTREE_EQ:
bRes = (p->u.rValue>cell_max || p->u.rValue<cell_min);
break;
default: {
assert( p->op==RTREE_MATCH );
rc = testRtreeGeom(pRtree, p, &cell, &bRes);
bRes = !bRes;
break;
................................................................................
RtreeConstraint *p = &pCursor->aConstraint[ii];
RtreeDValue coord = DCOORD(cell.aCoord[p->iCoord]);
int res;
assert(p->op==RTREE_LE || p->op==RTREE_LT || p->op==RTREE_GE
|| p->op==RTREE_GT || p->op==RTREE_EQ || p->op==RTREE_MATCH
);
switch( p->op ){
case RTREE_LE: res = (coord<=p->u.rValue); break;
case RTREE_LT: res = (coord<p->u.rValue); break;
case RTREE_GE: res = (coord>=p->u.rValue); break;
case RTREE_GT: res = (coord>p->u.rValue); break;
case RTREE_EQ: res = (coord==p->u.rValue); break;
default: {
int rc;
assert( p->op==RTREE_MATCH );
rc = testRtreeGeom(pRtree, p, &cell, &res);
if( rc!=SQLITE_OK ){
return rc;
}
................................................................................
** This function is called to configure the RtreeConstraint object passed
** as the second argument for a MATCH constraint. The value passed as the
** first argument to this function is the right-hand operand to the MATCH
** operator.
*/
static int deserializeGeometry(sqlite3_value *pValue, RtreeConstraint *pCons){
RtreeMatchArg *p;
sqlite3_rtree_query_info *pGeom;
int nBlob;
/* Check that value is actually a blob. */
if( sqlite3_value_type(pValue)!=SQLITE_BLOB ) return SQLITE_ERROR;
/* Check that the blob is roughly the right size. */
nBlob = sqlite3_value_bytes(pValue);
if( nBlob<(int)sizeof(RtreeMatchArg)
|| ((nBlob-sizeof(RtreeMatchArg))%sizeof(RtreeDValue))!=0
){
return SQLITE_ERROR;
}
pGeom = (sqlite3_rtree_query_info*)sqlite3_malloc( sizeof(*pGeom)+nBlob );
if( !pGeom ) return SQLITE_NOMEM;
memset(pGeom, 0, sizeof(*pGeom));
p = (RtreeMatchArg*)&pGeom[1];
memcpy(p, sqlite3_value_blob(pValue), nBlob);
if( p->magic!=RTREE_GEOMETRY_MAGIC
|| nBlob!=(int)(sizeof(RtreeMatchArg) + (p->nParam-1)*sizeof(RtreeDValue))
){
sqlite3_free(pGeom);
return SQLITE_ERROR;
}
pGeom->pContext = p->cb.pContext;
pGeom->nParam = p->nParam;
pGeom->aParam = p->aParam;
pCons->u.xGeom = p->cb.xGeom;
pCons->pGeom = pGeom;
return SQLITE_OK;
}
/*
** Rtree virtual table module xFilter method.
*/
................................................................................
*/
rc = deserializeGeometry(argv[ii], p);
if( rc!=SQLITE_OK ){
break;
}
}else{
#ifdef SQLITE_RTREE_INT_ONLY
p->u.rValue = sqlite3_value_int64(argv[ii]);
#else
p->u.rValue = sqlite3_value_double(argv[ii]);
#endif
}
}
}
}
if( rc==SQLITE_OK ){
|
Changes to ext/rtree/sqlite3rtree.h.
73 74 75 76 77 78 79 80 81 82 83 84 85 86 |
);
/*
** A pointer to a structure of the following type is passed as the
** argument to scored geometry callback registered using
** sqlite3_rtree_query_callback().
*/
struct sqlite3_rtree_query_info {
void *pContext; /* pContext from when function registered */
int nParam; /* Number of function parameters */
sqlite3_rtree_dbl *aParam; /* value of function parameters */
void *pUser; /* callback can use this, if desired */
void (*xDelUser)(void*); /* function to free pUser */
|
> > > > |
73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 |
); /* ** A pointer to a structure of the following type is passed as the ** argument to scored geometry callback registered using ** sqlite3_rtree_query_callback(). ** ** Note that the first 5 fields of this structure are identical to ** sqlite3_rtree_geometry. This structure is a subclass of ** sqlite3_rtree_geometry. */ struct sqlite3_rtree_query_info { void *pContext; /* pContext from when function registered */ int nParam; /* Number of function parameters */ sqlite3_rtree_dbl *aParam; /* value of function parameters */ void *pUser; /* callback can use this, if desired */ void (*xDelUser)(void*); /* function to free pUser */ |