Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
Comment: | Continuing clean-up of the R-Tree module in preparation for cutting in the new generalized query mechanism. |
---|---|
Downloads: | Tarball | ZIP archive |
Timelines: | family | ancestors | descendants | both | rtree-enhancements |
Files: | files | file ages | folders |
SHA1: |
66c858f20586424e15d0bfa3d7b56643 |
User & Date: | drh 2014-04-12 17:44:00.241 |
Context
2014-04-13
| ||
16:10 | Continuing work on the new custom query mechanism for r-tree. (check-in: ca7357e66c 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: 66c858f205 user: drh tags: rtree-enhancements) | |
2014-04-11
| ||
23:14 | Add the new interfaces to rtree, though they do not yet work. Add the "show_speedtest1_rtree.tcl" script for showing the test data used for the R-Tree tests of speedtest1. Change speedtest1 to generate better R-Tree test data. (check-in: 0b70275972 user: drh tags: rtree-enhancements) | |
Changes
Changes to ext/rtree/rtree.c.
︙ | ︙ | |||
285 286 287 288 289 290 291 | #define RTREE_GT 0x45 #define RTREE_MATCH 0x46 /* ** An rtree structure node. */ struct RtreeNode { | | | | | | | < < < < < | < < < < < < < | | < < < < | | | > | < | > | > > > > > > > > > > > > > > > > > > > > > | 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 | #define RTREE_GT 0x45 #define RTREE_MATCH 0x46 /* ** An rtree structure node. */ struct RtreeNode { RtreeNode *pParent; /* Parent node */ i64 iNode; /* The node number */ int nRef; /* Number of references to this node */ int isDirty; /* True if the node needs to be written to disk */ u8 *zData; /* Content of the node, as should be on disk */ RtreeNode *pNext; /* Next node in this hash collision chain */ }; /* Return the number of cells in a node */ #define NCELL(pNode) readInt16(&(pNode)->zData[2]) /* ** A single cell from a node, deserialized */ struct RtreeCell { i64 iRowid; /* Node or entry ID */ RtreeCoord aCoord[RTREE_MAX_DIMENSIONS*2]; /* Bounding box coordinates */ }; /* ** This object becomes the sqlite3_user_data() for the SQL functions ** that are created by sqlite3_rtree_geometry_callback() and ** sqlite3_rtree_query_callback() and which appear on the right of MATCH ** operators in order to constrain a search. ** ** xGeom and xQueryFunc are the callback functions. Exactly one of ** xGeom and xQueryFunc fields is non-NULL, depending on whether the ** SQL function was created using sqlite3_rtree_geometry_callback() or ** sqlite3_rtree_query_callback(). ** ** This object is deleted automatically by the destructor mechanism in ** sqlite3_create_function_v2(). */ struct RtreeGeomCallback { int (*xGeom)(sqlite3_rtree_geometry*, int, RtreeDValue*, int*); int (*xQueryFunc)(sqlite3_rtree_query_info*); void (*xDestructor)(void*); void *pContext; }; /* ** Value for the first field of every RtreeMatchArg object. The MATCH ** operator tests that the first field of a blob operand matches this ** value to avoid operating on invalid blobs (which could cause a segfault). */ #define RTREE_GEOMETRY_MAGIC 0x891245AB /* ** An instance of this structure (in the form of a BLOB) is returned by ** the SQL functions that sqlite3_rtree_geometry_callback() and ** sqlite3_rtree_query_callback() create, and is read as the right-hand ** operand to the MATCH operator of an R-Tree. */ struct RtreeMatchArg { u32 magic; /* Always RTREE_GEOMETRY_MAGIC */ RtreeGeomCallback cb; /* Info about the callback functions */ int nParam; /* Number of parameters to the SQL function */ RtreeDValue aParam[1]; /* Values for parameters to the SQL function */ }; #ifndef MAX # define MAX(x,y) ((x) < (y) ? (y) : (x)) #endif #ifndef MIN # define MIN(x,y) ((x) > (y) ? (y) : (x)) #endif |
︙ | ︙ | |||
1249 1250 1251 1252 1253 1254 1255 | if( p->magic!=RTREE_GEOMETRY_MAGIC || nBlob!=(int)(sizeof(RtreeMatchArg) + (p->nParam-1)*sizeof(RtreeDValue)) ){ sqlite3_free(pGeom); return SQLITE_ERROR; } | | | | 1255 1256 1257 1258 1259 1260 1261 1262 1263 1264 1265 1266 1267 1268 1269 1270 1271 1272 1273 | 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. */ |
︙ | ︙ | |||
3351 3352 3353 3354 3355 3356 3357 | rc = sqlite3_create_module_v2(db, "rtree_i32", &rtreeModule, c, 0); } return rc; } /* | | > > | | | | > > > > | > > | < | | | | < < < | | | | | < < < | 3357 3358 3359 3360 3361 3362 3363 3364 3365 3366 3367 3368 3369 3370 3371 3372 3373 3374 3375 3376 3377 3378 3379 3380 3381 3382 3383 3384 3385 3386 3387 3388 3389 3390 3391 3392 3393 3394 3395 3396 3397 3398 3399 3400 3401 3402 3403 3404 3405 3406 3407 3408 3409 3410 3411 3412 3413 3414 3415 3416 3417 3418 3419 3420 3421 3422 3423 3424 3425 3426 3427 3428 3429 3430 3431 3432 3433 3434 3435 3436 3437 3438 3439 3440 3441 3442 3443 3444 3445 3446 3447 3448 3449 3450 3451 3452 3453 3454 3455 3456 3457 3458 3459 3460 3461 3462 3463 3464 | rc = sqlite3_create_module_v2(db, "rtree_i32", &rtreeModule, c, 0); } return rc; } /* ** This routine deletes the RtreeGeomCallback object that was attached ** one of the SQL functions create by sqlite3_rtree_geometry_callback() ** or sqlite3_rtree_query_callback(). In other words, this routine is the ** destructor for an RtreeGeomCallback objecct. This routine is called when ** the corresponding SQL function is deleted. */ static void rtreeFreeCallback(void *p){ RtreeGeomCallback *pGeom = (RtreeGeomCallback*)p; if( pGeom->xDestructor ) pGeom->xDestructor(pGeom->pContext); sqlite3_free(p); } /* ** Each call to sqlite3_rtree_geometry_callback() or ** sqlite3_rtree_query_callback() creates an ordinary SQLite ** scalar function that is implemented by this routine. ** ** All this function does is construct an RtreeMatchArg object that ** contains the geometry-checking callback routines and a list of ** parameters to this function, then return that RtreeMatchArg object ** as a BLOB. ** ** The R-Tree MATCH operator will read the returned BLOB, deserialize ** the RtreeMatchArg object, and use the RtreeMatchArg object to figure ** out which elements of the R-Tree should be returned by the query. */ static void geomCallback(sqlite3_context *ctx, int nArg, sqlite3_value **aArg){ RtreeGeomCallback *pGeomCtx = (RtreeGeomCallback *)sqlite3_user_data(ctx); RtreeMatchArg *pBlob; int nBlob; nBlob = sizeof(RtreeMatchArg) + (nArg-1)*sizeof(RtreeDValue); pBlob = (RtreeMatchArg *)sqlite3_malloc(nBlob); if( !pBlob ){ sqlite3_result_error_nomem(ctx); }else{ int i; pBlob->magic = RTREE_GEOMETRY_MAGIC; pBlob->cb = pGeomCtx[0]; pBlob->nParam = nArg; for(i=0; i<nArg; i++){ #ifdef SQLITE_RTREE_INT_ONLY pBlob->aParam[i] = sqlite3_value_int64(aArg[i]); #else pBlob->aParam[i] = sqlite3_value_double(aArg[i]); #endif } sqlite3_result_blob(ctx, pBlob, nBlob, sqlite3_free); } } /* ** Register a new geometry function for use with the r-tree MATCH operator. */ int sqlite3_rtree_geometry_callback( sqlite3 *db, /* Register SQL function on this connection */ const char *zGeom, /* Name of the new SQL function */ int (*xGeom)(sqlite3_rtree_geometry*,int,RtreeDValue*,int*), /* Callback */ void *pContext /* Extra data associated with the callback */ ){ RtreeGeomCallback *pGeomCtx; /* Context object for new user-function */ /* Allocate and populate the context object. */ pGeomCtx = (RtreeGeomCallback *)sqlite3_malloc(sizeof(RtreeGeomCallback)); if( !pGeomCtx ) return SQLITE_NOMEM; pGeomCtx->xGeom = xGeom; pGeomCtx->xQueryFunc = 0; pGeomCtx->xDestructor = 0; pGeomCtx->pContext = pContext; return sqlite3_create_function_v2(db, zGeom, -1, SQLITE_ANY, (void *)pGeomCtx, geomCallback, 0, 0, rtreeFreeCallback ); } /* ** Register a new 2nd-generation geometry function for use with the ** r-tree MATCH operator. */ int sqlite3_rtree_query_callback( sqlite3 *db, /* Register SQL function on this connection */ const char *zQueryFunc, /* Name of new SQL function */ int (*xQueryFunc)(sqlite3_rtree_query_info*), /* Callback */ void *pContext, /* Extra data passed into the callback */ void (*xDestructor)(void*) /* Destructor for the extra data */ ){ RtreeGeomCallback *pGeomCtx; /* Context object for new user-function */ /* Allocate and populate the context object. */ pGeomCtx = (RtreeGeomCallback *)sqlite3_malloc(sizeof(RtreeGeomCallback)); if( !pGeomCtx ) return SQLITE_NOMEM; pGeomCtx->xGeom = 0; pGeomCtx->xQueryFunc = xQueryFunc; pGeomCtx->xDestructor = xDestructor; pGeomCtx->pContext = pContext; return sqlite3_create_function_v2(db, zQueryFunc, -1, SQLITE_ANY, (void *)pGeomCtx, geomCallback, 0, 0, rtreeFreeCallback ); } #if !SQLITE_CORE #ifdef _WIN32 |
︙ | ︙ |
Changes to src/test_rtree.c.
︙ | ︙ | |||
46 47 48 49 50 51 52 | /* ** Implementation of "circle" r-tree geometry callback. */ static int circle_geom( sqlite3_rtree_geometry *p, int nCoord, | < < < | < | 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 | /* ** Implementation of "circle" r-tree geometry callback. */ static int circle_geom( sqlite3_rtree_geometry *p, int nCoord, sqlite3_rtree_dbl *aCoord, int *pRes ){ int i; /* Iterator variable */ Circle *pCircle; /* Structure defining circular region */ double xmin, xmax; /* X dimensions of box being tested */ double ymin, ymax; /* X dimensions of box being tested */ |
︙ | ︙ | |||
149 150 151 152 153 154 155 156 157 158 159 160 161 162 | } /* The specified bounding box does not intersect the circular region. Set ** the output variable to zero and return SQLITE_OK. */ *pRes = 0; return SQLITE_OK; } /* END of implementation of "circle" geometry callback. ************************************************************************** *************************************************************************/ #include <assert.h> #include "tcl.h" | > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > | 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 | } /* The specified bounding box does not intersect the circular region. Set ** the output variable to zero and return SQLITE_OK. */ *pRes = 0; return SQLITE_OK; } /* ** Implementation of "circle" r-tree geometry callback using the ** 2nd-generation interface that allows scoring. */ static int circle_query_func(sqlite3_rtree_query_info *p){ int i; /* Iterator variable */ Circle *pCircle; /* Structure defining circular region */ double xmin, xmax; /* X dimensions of box being tested */ double ymin, ymax; /* X dimensions of box being tested */ int nWithin = 0; /* Number of corners inside the circle */ if( p->pUser==0 ){ /* If pUser is still 0, then the parameter values have not been tested ** for correctness or stored into a Circle structure yet. Do this now. */ /* This geometry callback is for use with a 2-dimensional r-tree table. ** Return an error if the table does not have exactly 2 dimensions. */ if( p->nCoord!=4 ) return SQLITE_ERROR; /* Test that the correct number of parameters (3) have been supplied, ** and that the parameters are in range (that the radius of the circle ** radius is greater than zero). */ if( p->nParam!=3 || p->aParam[2]<0.0 ) return SQLITE_ERROR; /* Allocate a structure to cache parameter data in. Return SQLITE_NOMEM ** if the allocation fails. */ pCircle = (Circle *)(p->pUser = sqlite3_malloc(sizeof(Circle))); if( !pCircle ) return SQLITE_NOMEM; p->xDelUser = circle_del; /* Record the center and radius of the circular region. One way that ** tested bounding boxes that intersect the circular region are detected ** is by testing if each corner of the bounding box lies within radius ** units of the center of the circle. */ pCircle->centerx = p->aParam[0]; pCircle->centery = p->aParam[1]; pCircle->radius = p->aParam[2]; /* Define two bounding box regions. The first, aBox[0], extends to ** infinity in the X dimension. It covers the same range of the Y dimension ** as the circular region. The second, aBox[1], extends to infinity in ** the Y dimension and is constrained to the range of the circle in the ** X dimension. ** ** Then imagine each box is split in half along its short axis by a line ** that intersects the center of the circular region. A bounding box ** being tested can be said to intersect the circular region if it contains ** points from each half of either of the two infinite bounding boxes. */ pCircle->aBox[0].xmin = pCircle->centerx; pCircle->aBox[0].xmax = pCircle->centerx; pCircle->aBox[0].ymin = pCircle->centery + pCircle->radius; pCircle->aBox[0].ymax = pCircle->centery - pCircle->radius; pCircle->aBox[1].xmin = pCircle->centerx + pCircle->radius; pCircle->aBox[1].xmax = pCircle->centerx - pCircle->radius; pCircle->aBox[1].ymin = pCircle->centery; pCircle->aBox[1].ymax = pCircle->centery; } pCircle = (Circle *)p->pUser; xmin = p->aCoord[0]; xmax = p->aCoord[1]; ymin = p->aCoord[2]; ymax = p->aCoord[3]; /* Check if any of the 4 corners of the bounding-box being tested lie ** inside the circular region. If they do, then the bounding-box does ** intersect the region of interest. Set the output variable to true and ** return SQLITE_OK in this case. */ for(i=0; i<4; i++){ double x = (i&0x01) ? xmax : xmin; double y = (i&0x02) ? ymax : ymin; double d2; d2 = (x-pCircle->centerx)*(x-pCircle->centerx); d2 += (y-pCircle->centery)*(y-pCircle->centery); if( d2<(pCircle->radius*pCircle->radius) ) nWithin++; } /* Check if the bounding box covers any other part of the circular region. ** See comments above for a description of how this test works. If it does ** cover part of the circular region, set the output variable to true ** and return SQLITE_OK. */ if( nWithin==0 ){ for(i=0; i<2; i++){ if( xmin<=pCircle->aBox[i].xmin && xmax>=pCircle->aBox[i].xmax && ymin<=pCircle->aBox[i].ymin && ymax>=pCircle->aBox[i].ymax ){ nWithin = 1; break; } } } p->rScore = p->iLevel; if( nWithin==0 ){ p->eWithin = NOT_WITHIN; }else if( nWithin>=4 ){ p->eWithin = FULLY_WITHIN; }else{ p->eWithin = PARTLY_WITHIN; } return SQLITE_OK; } /* END of implementation of "circle" geometry callback. ************************************************************************** *************************************************************************/ #include <assert.h> #include "tcl.h" |
︙ | ︙ | |||
190 191 192 193 194 195 196 | ** cube(x, y, z, width, height, depth) ** ** The width, height and depth parameters must all be greater than zero. */ static int cube_geom( sqlite3_rtree_geometry *p, int nCoord, | < < < | < | 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 | ** cube(x, y, z, width, height, depth) ** ** The width, height and depth parameters must all be greater than zero. */ static int cube_geom( sqlite3_rtree_geometry *p, int nCoord, sqlite3_rtree_dbl *aCoord, int *piRes ){ Cube *pCube = (Cube *)p->pUser; assert( p->pContext==(void *)&gHere ); if( pCube==0 ){ |
︙ | ︙ | |||
289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 | if( objc!=2 ){ Tcl_WrongNumArgs(interp, 1, objv, "DB"); return TCL_ERROR; } if( getDbPointer(interp, Tcl_GetString(objv[1]), &db) ) return TCL_ERROR; rc = sqlite3_rtree_geometry_callback(db, "circle", circle_geom, 0); Tcl_SetResult(interp, (char *)sqlite3ErrName(rc), TCL_STATIC); #endif return TCL_OK; } int Sqlitetestrtree_Init(Tcl_Interp *interp){ Tcl_CreateObjCommand(interp, "register_cube_geom", register_cube_geom, 0, 0); Tcl_CreateObjCommand(interp, "register_circle_geom",register_circle_geom,0,0); return TCL_OK; } | > > > > | 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 | if( objc!=2 ){ Tcl_WrongNumArgs(interp, 1, objv, "DB"); return TCL_ERROR; } if( getDbPointer(interp, Tcl_GetString(objv[1]), &db) ) return TCL_ERROR; rc = sqlite3_rtree_geometry_callback(db, "circle", circle_geom, 0); if( rc==SQLITE_OK ){ rc = sqlite3_rtree_query_callback(db, "Qcircle", circle_query_func, 0, 0); } Tcl_SetResult(interp, (char *)sqlite3ErrName(rc), TCL_STATIC); #endif return TCL_OK; } int Sqlitetestrtree_Init(Tcl_Interp *interp){ Tcl_CreateObjCommand(interp, "register_cube_geom", register_cube_geom, 0, 0); Tcl_CreateObjCommand(interp, "register_circle_geom",register_circle_geom,0,0); return TCL_OK; } |