AryaWu/sqlite
0
1/*2** 2010 August 283**4** The author disclaims copyright to this source code. In place of5** a legal notice, here is a blessing:6**7** May you do good and not evil.8** May you find forgiveness for yourself and forgive others.9** May you share freely, never taking more than you give.10**11*************************************************************************12** Code for testing all sorts of SQLite interfaces. This code13** is not included in the SQLite library. 14*/15 16#include "sqlite3.h"17#include "tclsqlite.h"18 19/* Solely for the UNUSED_PARAMETER() macro. */20#include "sqliteInt.h"21 22#ifdef SQLITE_ENABLE_RTREE23/* 24** Type used to cache parameter information for the "circle" r-tree geometry25** callback.26*/27typedef struct Circle Circle;28struct Circle {29 struct Box {30 double xmin;31 double xmax;32 double ymin;33 double ymax;34 } aBox[2];35 double centerx;36 double centery;37 double radius;38 double mxArea;39 int eScoreType;40};41 42/*43** Destructor function for Circle objects allocated by circle_geom().44*/45static void circle_del(void *p){46 sqlite3_free(p);47}48 49/*50** Implementation of "circle" r-tree geometry callback.51*/52static int circle_geom(53 sqlite3_rtree_geometry *p,54 int nCoord, 55 sqlite3_rtree_dbl *aCoord,56 int *pRes57){58 int i; /* Iterator variable */59 Circle *pCircle; /* Structure defining circular region */60 double xmin, xmax; /* X dimensions of box being tested */61 double ymin, ymax; /* X dimensions of box being tested */62 63 xmin = aCoord[0];64 xmax = aCoord[1];65 ymin = aCoord[2];66 ymax = aCoord[3];67 pCircle = (Circle *)p->pUser;68 if( pCircle==0 ){69 /* If pUser is still 0, then the parameter values have not been tested70 ** for correctness or stored into a Circle structure yet. Do this now. */71 72 /* This geometry callback is for use with a 2-dimensional r-tree table.73 ** Return an error if the table does not have exactly 2 dimensions. */74 if( nCoord!=4 ) return SQLITE_ERROR;75 76 /* Test that the correct number of parameters (3) have been supplied,77 ** and that the parameters are in range (that the radius of the circle 78 ** radius is greater than zero). */79 if( p->nParam!=3 || p->aParam[2]<0.0 ) return SQLITE_ERROR;80 81 /* Allocate a structure to cache parameter data in. Return SQLITE_NOMEM82 ** if the allocation fails. */83 pCircle = (Circle *)(p->pUser = sqlite3_malloc(sizeof(Circle)));84 if( !pCircle ) return SQLITE_NOMEM;85 p->xDelUser = circle_del;86 87 /* Record the center and radius of the circular region. One way that88 ** tested bounding boxes that intersect the circular region are detected89 ** is by testing if each corner of the bounding box lies within radius90 ** units of the center of the circle. */91 pCircle->centerx = p->aParam[0];92 pCircle->centery = p->aParam[1];93 pCircle->radius = p->aParam[2];94 95 /* Define two bounding box regions. The first, aBox[0], extends to96 ** infinity in the X dimension. It covers the same range of the Y dimension97 ** as the circular region. The second, aBox[1], extends to infinity in98 ** the Y dimension and is constrained to the range of the circle in the99 ** X dimension.100 **101 ** Then imagine each box is split in half along its short axis by a line102 ** that intersects the center of the circular region. A bounding box103 ** being tested can be said to intersect the circular region if it contains104 ** points from each half of either of the two infinite bounding boxes.105 */106 pCircle->aBox[0].xmin = pCircle->centerx;107 pCircle->aBox[0].xmax = pCircle->centerx;108 pCircle->aBox[0].ymin = pCircle->centery + pCircle->radius;109 pCircle->aBox[0].ymax = pCircle->centery - pCircle->radius;110 pCircle->aBox[1].xmin = pCircle->centerx + pCircle->radius;111 pCircle->aBox[1].xmax = pCircle->centerx - pCircle->radius;112 pCircle->aBox[1].ymin = pCircle->centery;113 pCircle->aBox[1].ymax = pCircle->centery;114 pCircle->mxArea = (xmax - xmin)*(ymax - ymin) + 1.0;115 }116 117 /* Check if any of the 4 corners of the bounding-box being tested lie 118 ** inside the circular region. If they do, then the bounding-box does119 ** intersect the region of interest. Set the output variable to true and120 ** return SQLITE_OK in this case. */121 for(i=0; i<4; i++){122 double x = (i&0x01) ? xmax : xmin;123 double y = (i&0x02) ? ymax : ymin;124 double d2;125 126 d2 = (x-pCircle->centerx)*(x-pCircle->centerx);127 d2 += (y-pCircle->centery)*(y-pCircle->centery);128 if( d2<(pCircle->radius*pCircle->radius) ){129 *pRes = 1;130 return SQLITE_OK;131 }132 }133 134 /* Check if the bounding box covers any other part of the circular region.135 ** See comments above for a description of how this test works. If it does136 ** cover part of the circular region, set the output variable to true137 ** and return SQLITE_OK. */138 for(i=0; i<2; i++){139 if( xmin<=pCircle->aBox[i].xmin 140 && xmax>=pCircle->aBox[i].xmax 141 && ymin<=pCircle->aBox[i].ymin 142 && ymax>=pCircle->aBox[i].ymax 143 ){144 *pRes = 1;145 return SQLITE_OK;146 }147 }148 149 /* The specified bounding box does not intersect the circular region. Set150 ** the output variable to zero and return SQLITE_OK. */151 *pRes = 0;152 return SQLITE_OK;153}154 155/*156** Implementation of "circle" r-tree geometry callback using the 157** 2nd-generation interface that allows scoring.158**159** Two calling forms:160**161** Qcircle(X,Y,Radius,eType) -- All values are doubles162** Qcircle('x:X y:Y r:R e:ETYPE') -- Single string parameter163*/164static int circle_query_func(sqlite3_rtree_query_info *p){165 int i; /* Iterator variable */166 Circle *pCircle; /* Structure defining circular region */167 double xmin, xmax; /* X dimensions of box being tested */168 double ymin, ymax; /* X dimensions of box being tested */169 int nWithin = 0; /* Number of corners inside the circle */170 171 xmin = p->aCoord[0];172 xmax = p->aCoord[1];173 ymin = p->aCoord[2];174 ymax = p->aCoord[3];175 pCircle = (Circle *)p->pUser;176 if( pCircle==0 ){177 /* If pUser is still 0, then the parameter values have not been tested178 ** for correctness or stored into a Circle structure yet. Do this now. */179 180 /* This geometry callback is for use with a 2-dimensional r-tree table.181 ** Return an error if the table does not have exactly 2 dimensions. */182 if( p->nCoord!=4 ) return SQLITE_ERROR;183 184 /* Test that the correct number of parameters (1 or 4) have been supplied.185 */186 if( p->nParam!=4 && p->nParam!=1 ) return SQLITE_ERROR;187 188 /* Allocate a structure to cache parameter data in. Return SQLITE_NOMEM189 ** if the allocation fails. */190 pCircle = (Circle *)(p->pUser = sqlite3_malloc(sizeof(Circle)));191 if( !pCircle ) return SQLITE_NOMEM;192 p->xDelUser = circle_del;193 194 /* Record the center and radius of the circular region. One way that195 ** tested bounding boxes that intersect the circular region are detected196 ** is by testing if each corner of the bounding box lies within radius197 ** units of the center of the circle. */198 if( p->nParam==4 ){199 pCircle->centerx = p->aParam[0];200 pCircle->centery = p->aParam[1];201 pCircle->radius = p->aParam[2];202 pCircle->eScoreType = (int)p->aParam[3];203 }else{204 const char *z = (const char*)sqlite3_value_text(p->apSqlParam[0]);205 pCircle->centerx = 0.0;206 pCircle->centery = 0.0;207 pCircle->radius = 0.0;208 pCircle->eScoreType = 0;209 while( z && z[0] ){210 if( z[0]=='r' && z[1]==':' ){211 pCircle->radius = atof(&z[2]);212 }else if( z[0]=='x' && z[1]==':' ){213 pCircle->centerx = atof(&z[2]);214 }else if( z[0]=='y' && z[1]==':' ){215 pCircle->centery = atof(&z[2]);216 }else if( z[0]=='e' && z[1]==':' ){217 pCircle->eScoreType = (int)atof(&z[2]);218 }else if( z[0]==' ' ){219 z++;220 continue;221 }222 while( z[0]!=0 && z[0]!=' ' ) z++;223 while( z[0]==' ' ) z++;224 }225 }226 if( pCircle->radius<0.0 ){227 sqlite3_free(pCircle);228 return SQLITE_NOMEM;229 }230 231 /* Define two bounding box regions. The first, aBox[0], extends to232 ** infinity in the X dimension. It covers the same range of the Y dimension233 ** as the circular region. The second, aBox[1], extends to infinity in234 ** the Y dimension and is constrained to the range of the circle in the235 ** X dimension.236 **237 ** Then imagine each box is split in half along its short axis by a line238 ** that intersects the center of the circular region. A bounding box239 ** being tested can be said to intersect the circular region if it contains240 ** points from each half of either of the two infinite bounding boxes.241 */242 pCircle->aBox[0].xmin = pCircle->centerx;243 pCircle->aBox[0].xmax = pCircle->centerx;244 pCircle->aBox[0].ymin = pCircle->centery + pCircle->radius;245 pCircle->aBox[0].ymax = pCircle->centery - pCircle->radius;246 pCircle->aBox[1].xmin = pCircle->centerx + pCircle->radius;247 pCircle->aBox[1].xmax = pCircle->centerx - pCircle->radius;248 pCircle->aBox[1].ymin = pCircle->centery;249 pCircle->aBox[1].ymax = pCircle->centery;250 pCircle->mxArea = 200.0*200.0;251 }252 253 /* Check if any of the 4 corners of the bounding-box being tested lie 254 ** inside the circular region. If they do, then the bounding-box does255 ** intersect the region of interest. Set the output variable to true and256 ** return SQLITE_OK in this case. */257 for(i=0; i<4; i++){258 double x = (i&0x01) ? xmax : xmin;259 double y = (i&0x02) ? ymax : ymin;260 double d2;261 262 d2 = (x-pCircle->centerx)*(x-pCircle->centerx);263 d2 += (y-pCircle->centery)*(y-pCircle->centery);264 if( d2<(pCircle->radius*pCircle->radius) ) nWithin++;265 }266 267 /* Check if the bounding box covers any other part of the circular region.268 ** See comments above for a description of how this test works. If it does269 ** cover part of the circular region, set the output variable to true270 ** and return SQLITE_OK. */271 if( nWithin==0 ){272 for(i=0; i<2; i++){273 if( xmin<=pCircle->aBox[i].xmin 274 && xmax>=pCircle->aBox[i].xmax 275 && ymin<=pCircle->aBox[i].ymin 276 && ymax>=pCircle->aBox[i].ymax 277 ){278 nWithin = 1;279 break;280 }281 }282 }283 284 if( pCircle->eScoreType==1 ){285 /* Depth first search */286 p->rScore = p->iLevel;287 }else if( pCircle->eScoreType==2 ){288 /* Breadth first search */289 p->rScore = 100 - p->iLevel;290 }else if( pCircle->eScoreType==3 ){291 /* Depth-first search, except sort the leaf nodes by area with292 ** the largest area first */293 if( p->iLevel==1 ){294 p->rScore = 1.0 - (xmax-xmin)*(ymax-ymin)/pCircle->mxArea;295 if( p->rScore<0.01 ) p->rScore = 0.01;296 }else{297 p->rScore = 0.0;298 }299 }else if( pCircle->eScoreType==4 ){300 /* Depth-first search, except exclude odd rowids */301 p->rScore = p->iLevel;302 if( p->iRowid&1 ) nWithin = 0;303 }else{304 /* Breadth-first search, except exclude odd rowids */305 p->rScore = 100 - p->iLevel;306 if( p->iRowid&1 ) nWithin = 0;307 }308 if( nWithin==0 ){309 p->eWithin = NOT_WITHIN;310 }else if( nWithin>=4 ){311 p->eWithin = FULLY_WITHIN;312 }else{313 p->eWithin = PARTLY_WITHIN;314 }315 return SQLITE_OK;316}317/*318** Implementation of "breadthfirstsearch" r-tree geometry callback using the 319** 2nd-generation interface that allows scoring.320**321** ... WHERE id MATCH breadthfirstsearch($x0,$x1,$y0,$y1) ...322**323** It returns all entries whose bounding boxes overlap with $x0,$x1,$y0,$y1.324*/325static int bfs_query_func(sqlite3_rtree_query_info *p){326 double x0,x1,y0,y1; /* Dimensions of box being tested */327 double bx0,bx1,by0,by1; /* Boundary of the query function */328 329 if( p->nParam!=4 ) return SQLITE_ERROR;330 x0 = p->aCoord[0];331 x1 = p->aCoord[1];332 y0 = p->aCoord[2];333 y1 = p->aCoord[3];334 bx0 = p->aParam[0];335 bx1 = p->aParam[1];336 by0 = p->aParam[2];337 by1 = p->aParam[3];338 p->rScore = 100 - p->iLevel;339 if( p->eParentWithin==FULLY_WITHIN ){340 p->eWithin = FULLY_WITHIN;341 }else if( x0>=bx0 && x1<=bx1 && y0>=by0 && y1<=by1 ){342 p->eWithin = FULLY_WITHIN;343 }else if( x1>=bx0 && x0<=bx1 && y1>=by0 && y0<=by1 ){344 p->eWithin = PARTLY_WITHIN;345 }else{346 p->eWithin = NOT_WITHIN;347 }348 return SQLITE_OK;349}350 351/* END of implementation of "circle" geometry callback.352**************************************************************************353*************************************************************************/354 355#include <assert.h>356#include "tclsqlite.h"357 358typedef struct Cube Cube;359struct Cube {360 double x;361 double y;362 double z;363 double width;364 double height;365 double depth;366};367 368static void cube_context_free(void *p){369 sqlite3_free(p);370}371 372/*373** The context pointer registered along with the 'cube' callback is374** always ((void *)&gHere). This is just to facilitate testing, it is not375** actually used for anything.376*/377static int gHere = 42;378 379/*380** Implementation of a simple r-tree geom callback to test for intersection381** of r-tree rows with a "cube" shape. Cubes are defined by six scalar382** coordinates as follows:383**384** cube(x, y, z, width, height, depth)385**386** The width, height and depth parameters must all be greater than zero.387*/388static int cube_geom(389 sqlite3_rtree_geometry *p,390 int nCoord,391 sqlite3_rtree_dbl *aCoord,392 int *piRes393){394 Cube *pCube = (Cube *)p->pUser;395 396 assert( p->pContext==(void *)&gHere );397 398 if( pCube==0 ){399 if( p->nParam!=6 || nCoord!=6400 || p->aParam[3]<=0.0 || p->aParam[4]<=0.0 || p->aParam[5]<=0.0401 ){402 return SQLITE_ERROR;403 }404 pCube = (Cube *)sqlite3_malloc(sizeof(Cube));405 if( !pCube ){406 return SQLITE_NOMEM;407 }408 pCube->x = p->aParam[0];409 pCube->y = p->aParam[1];410 pCube->z = p->aParam[2];411 pCube->width = p->aParam[3];412 pCube->height = p->aParam[4];413 pCube->depth = p->aParam[5];414 415 p->pUser = (void *)pCube;416 p->xDelUser = cube_context_free;417 }418 419 assert( nCoord==6 );420 *piRes = 0;421 if( aCoord[0]<=(pCube->x+pCube->width)422 && aCoord[1]>=pCube->x423 && aCoord[2]<=(pCube->y+pCube->height)424 && aCoord[3]>=pCube->y425 && aCoord[4]<=(pCube->z+pCube->depth)426 && aCoord[5]>=pCube->z427 ){428 *piRes = 1;429 }430 431 return SQLITE_OK;432}433#endif /* SQLITE_ENABLE_RTREE */434 435static int SQLITE_TCLAPI register_cube_geom(436 void * clientData,437 Tcl_Interp *interp,438 int objc,439 Tcl_Obj *CONST objv[]440){441#ifndef SQLITE_ENABLE_RTREE442 UNUSED_PARAMETER(clientData);443 UNUSED_PARAMETER(interp);444 UNUSED_PARAMETER(objc);445 UNUSED_PARAMETER(objv);446#else447 extern int getDbPointer(Tcl_Interp*, const char*, sqlite3**);448 extern const char *sqlite3ErrName(int);449 sqlite3 *db;450 int rc;451 452 if( objc!=2 ){453 Tcl_WrongNumArgs(interp, 1, objv, "DB");454 return TCL_ERROR;455 }456 if( getDbPointer(interp, Tcl_GetString(objv[1]), &db) ) return TCL_ERROR;457 rc = sqlite3_rtree_geometry_callback(db, "cube", cube_geom, (void *)&gHere);458 Tcl_SetResult(interp, (char *)sqlite3ErrName(rc), TCL_STATIC);459#endif460 return TCL_OK;461}462 463static int SQLITE_TCLAPI register_circle_geom(464 void * clientData,465 Tcl_Interp *interp,466 int objc,467 Tcl_Obj *CONST objv[]468){469#ifndef SQLITE_ENABLE_RTREE470 UNUSED_PARAMETER(clientData);471 UNUSED_PARAMETER(interp);472 UNUSED_PARAMETER(objc);473 UNUSED_PARAMETER(objv);474#else475 extern int getDbPointer(Tcl_Interp*, const char*, sqlite3**);476 extern const char *sqlite3ErrName(int);477 sqlite3 *db;478 int rc;479 480 if( objc!=2 ){481 Tcl_WrongNumArgs(interp, 1, objv, "DB");482 return TCL_ERROR;483 }484 if( getDbPointer(interp, Tcl_GetString(objv[1]), &db) ) return TCL_ERROR;485 rc = sqlite3_rtree_geometry_callback(db, "circle", circle_geom, 0);486 if( rc==SQLITE_OK ){487 rc = sqlite3_rtree_query_callback(db, "Qcircle",488 circle_query_func, 0, 0);489 }490 if( rc==SQLITE_OK ){491 rc = sqlite3_rtree_query_callback(db, "breadthfirstsearch",492 bfs_query_func, 0, 0);493 }494 Tcl_SetResult(interp, (char *)sqlite3ErrName(rc), TCL_STATIC);495#endif496 return TCL_OK;497}498 499int Sqlitetestrtree_Init(Tcl_Interp *interp){500 Tcl_CreateObjCommand(interp, "register_cube_geom", register_cube_geom, 0, 0);501 Tcl_CreateObjCommand(interp, "register_circle_geom",register_circle_geom,0,0);502 return TCL_OK;503}504