third_party/sqlite/sqlite-src-3080704/src/test_rtree.c

   1 /*
   2 ** 2010 August 28
   3 **
   4 ** The author disclaims copyright to this source code.  In place of
   5 ** 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 code
  13 ** is not included in the SQLite library.
  14 */
  15
  16 #include <sqlite3.h>
  17 #include <tcl.h>
  18
  19 /* Solely for the UNUSED_PARAMETER() macro. */
  20 #include "sqliteInt.h"
  21
  22 #ifdef SQLITE_ENABLE_RTREE
  23 /*
  24 ** Type used to cache parameter information for the "circle" r-tree geometry
  25 ** callback.
  26 */
  27 typedef struct Circle Circle;
  28 struct 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 */
  45 static void circle_del(void *p){
  46   sqlite3_free(p);
  47 }
  48
  49 /*
  50 ** Implementation of "circle" r-tree geometry callback.
  51 */
  52 static int circle_geom(
  53   sqlite3_rtree_geometry *p,
  54   int nCoord,
  55   sqlite3_rtree_dbl *aCoord,
  56   int *pRes
  57 ){
  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 tested
  70     ** 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_NOMEM
  82     ** 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 that
  88     ** tested bounding boxes that intersect the circular region are detected
  89     ** is by testing if each corner of the bounding box lies within radius
  90     ** 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 to
  96     ** infinity in the X dimension. It covers the same range of the Y dimension
  97     ** as the circular region. The second, aBox[1], extends to infinity in
  98     ** the Y dimension and is constrained to the range of the circle in the
  99     ** X dimension.
 100     **
 101     ** Then imagine each box is split in half along its short axis by a line
 102     ** that intersects the center of the circular region. A bounding box
 103     ** being tested can be said to intersect the circular region if it contains
 104     ** 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 does
 119   ** intersect the region of interest. Set the output variable to true and
 120   ** 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 does
 136   ** cover part of the circular region, set the output variable to true
 137   ** 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. Set
 150   ** 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 static int circle_query_func(sqlite3_rtree_query_info *p){
 160   int i;                          /* Iterator variable */
 161   Circle *pCircle;                /* Structure defining circular region */
 162   double xmin, xmax;              /* X dimensions of box being tested */
 163   double ymin, ymax;              /* X dimensions of box being tested */
 164   int nWithin = 0;                /* Number of corners inside the circle */
 165
 166   xmin = p->aCoord[0];
 167   xmax = p->aCoord[1];
 168   ymin = p->aCoord[2];
 169   ymax = p->aCoord[3];
 170   pCircle = (Circle *)p->pUser;
 171   if( pCircle==0 ){
 172     /* If pUser is still 0, then the parameter values have not been tested
 173     ** for correctness or stored into a Circle structure yet. Do this now. */
 174
 175     /* This geometry callback is for use with a 2-dimensional r-tree table.
 176     ** Return an error if the table does not have exactly 2 dimensions. */
 177     if( p->nCoord!=4 ) return SQLITE_ERROR;
 178
 179     /* Test that the correct number of parameters (4) have been supplied,
 180     ** and that the parameters are in range (that the radius of the circle
 181     ** radius is greater than zero). */
 182     if( p->nParam!=4 || p->aParam[2]<0.0 ) return SQLITE_ERROR;
 183
 184     /* Allocate a structure to cache parameter data in. Return SQLITE_NOMEM
 185     ** if the allocation fails. */
 186     pCircle = (Circle *)(p->pUser = sqlite3_malloc(sizeof(Circle)));
 187     if( !pCircle ) return SQLITE_NOMEM;
 188     p->xDelUser = circle_del;
 189
 190     /* Record the center and radius of the circular region. One way that
 191     ** tested bounding boxes that intersect the circular region are detected
 192     ** is by testing if each corner of the bounding box lies within radius
 193     ** units of the center of the circle. */
 194     pCircle->centerx = p->aParam[0];
 195     pCircle->centery = p->aParam[1];
 196     pCircle->radius = p->aParam[2];
 197     pCircle->eScoreType = (int)p->aParam[3];
 198
 199     /* Define two bounding box regions. The first, aBox[0], extends to
 200     ** infinity in the X dimension. It covers the same range of the Y dimension
 201     ** as the circular region. The second, aBox[1], extends to infinity in
 202     ** the Y dimension and is constrained to the range of the circle in the
 203     ** X dimension.
 204     **
 205     ** Then imagine each box is split in half along its short axis by a line
 206     ** that intersects the center of the circular region. A bounding box
 207     ** being tested can be said to intersect the circular region if it contains
 208     ** points from each half of either of the two infinite bounding boxes.
 209     */
 210     pCircle->aBox[0].xmin = pCircle->centerx;
 211     pCircle->aBox[0].xmax = pCircle->centerx;
 212     pCircle->aBox[0].ymin = pCircle->centery + pCircle->radius;
 213     pCircle->aBox[0].ymax = pCircle->centery - pCircle->radius;
 214     pCircle->aBox[1].xmin = pCircle->centerx + pCircle->radius;
 215     pCircle->aBox[1].xmax = pCircle->centerx - pCircle->radius;
 216     pCircle->aBox[1].ymin = pCircle->centery;
 217     pCircle->aBox[1].ymax = pCircle->centery;
 218     pCircle->mxArea = 200.0*200.0;
 219   }
 220
 221   /* Check if any of the 4 corners of the bounding-box being tested lie
 222   ** inside the circular region. If they do, then the bounding-box does
 223   ** intersect the region of interest. Set the output variable to true and
 224   ** return SQLITE_OK in this case. */
 225   for(i=0; i<4; i++){
 226     double x = (i&0x01) ? xmax : xmin;
 227     double y = (i&0x02) ? ymax : ymin;
 228     double d2;
 229
 230     d2  = (x-pCircle->centerx)*(x-pCircle->centerx);
 231     d2 += (y-pCircle->centery)*(y-pCircle->centery);
 232     if( d2<(pCircle->radius*pCircle->radius) ) nWithin++;
 233   }
 234
 235   /* Check if the bounding box covers any other part of the circular region.
 236   ** See comments above for a description of how this test works. If it does
 237   ** cover part of the circular region, set the output variable to true
 238   ** and return SQLITE_OK. */
 239   if( nWithin==0 ){
 240     for(i=0; i<2; i++){
 241       if( xmin<=pCircle->aBox[i].xmin
 242        && xmax>=pCircle->aBox[i].xmax
 243        && ymin<=pCircle->aBox[i].ymin
 244        && ymax>=pCircle->aBox[i].ymax
 245       ){
 246         nWithin = 1;
 247         break;
 248       }
 249     }
 250   }
 251
 252   if( pCircle->eScoreType==1 ){
 253     /* Depth first search */
 254     p->rScore = p->iLevel;
 255   }else if( pCircle->eScoreType==2 ){
 256     /* Breadth first search */
 257     p->rScore = 100 - p->iLevel;
 258   }else if( pCircle->eScoreType==3 ){
 259     /* Depth-first search, except sort the leaf nodes by area with
 260     ** the largest area first */
 261     if( p->iLevel==1 ){
 262       p->rScore = 1.0 - (xmax-xmin)*(ymax-ymin)/pCircle->mxArea;
 263       if( p->rScore<0.01 ) p->rScore = 0.01;
 264     }else{
 265       p->rScore = 0.0;
 266     }
 267   }else if( pCircle->eScoreType==4 ){
 268     /* Depth-first search, except exclude odd rowids */
 269     p->rScore = p->iLevel;
 270     if( p->iRowid&1 ) nWithin = 0;
 271   }else{
 272     /* Breadth-first search, except exclude odd rowids */
 273     p->rScore = 100 - p->iLevel;
 274     if( p->iRowid&1 ) nWithin = 0;
 275   }
 276   if( nWithin==0 ){
 277     p->eWithin = NOT_WITHIN;
 278   }else if( nWithin>=4 ){
 279     p->eWithin = FULLY_WITHIN;
 280   }else{
 281     p->eWithin = PARTLY_WITHIN;
 282   }
 283   return SQLITE_OK;
 284 }
 285 /*
 286 ** Implementation of "breadthfirstsearch" r-tree geometry callback using the
 287 ** 2nd-generation interface that allows scoring.
 288 **
 289 **     ... WHERE id MATCH breadthfirstsearch($x0,$x1,$y0,$y1) ...
 290 **
 291 ** It returns all entries whose bounding boxes overlap with $x0,$x1,$y0,$y1.
 292 */
 293 static int bfs_query_func(sqlite3_rtree_query_info *p){
 294   double x0,x1,y0,y1;        /* Dimensions of box being tested */
 295   double bx0,bx1,by0,by1;    /* Boundary of the query function */
 296
 297   if( p->nParam!=4 ) return SQLITE_ERROR;
 298   x0 = p->aCoord[0];
 299   x1 = p->aCoord[1];
 300   y0 = p->aCoord[2];
 301   y1 = p->aCoord[3];
 302   bx0 = p->aParam[0];
 303   bx1 = p->aParam[1];
 304   by0 = p->aParam[2];
 305   by1 = p->aParam[3];
 306   p->rScore = 100 - p->iLevel;
 307   if( p->eParentWithin==FULLY_WITHIN ){
 308     p->eWithin = FULLY_WITHIN;
 309   }else if( x0>=bx0 && x1<=bx1 && y0>=by0 && y1<=by1 ){
 310     p->eWithin = FULLY_WITHIN;
 311   }else if( x1>=bx0 && x0<=bx1 && y1>=by0 && y0<=by1 ){
 312     p->eWithin = PARTLY_WITHIN;
 313   }else{
 314     p->eWithin = NOT_WITHIN;
 315   }
 316   return SQLITE_OK;
 317 }
 318
 319 /* END of implementation of "circle" geometry callback.
 320 **************************************************************************
 321 *************************************************************************/
 322
 323 #include <assert.h>
 324 #include "tcl.h"
 325
 326 typedef struct Cube Cube;
 327 struct Cube {
 328   double x;
 329   double y;
 330   double z;
 331   double width;
 332   double height;
 333   double depth;
 334 };
 335
 336 static void cube_context_free(void *p){
 337   sqlite3_free(p);
 338 }
 339
 340 /*
 341 ** The context pointer registered along with the 'cube' callback is
 342 ** always ((void *)&gHere). This is just to facilitate testing, it is not
 343 ** actually used for anything.
 344 */
 345 static int gHere = 42;
 346
 347 /*
 348 ** Implementation of a simple r-tree geom callback to test for intersection
 349 ** of r-tree rows with a "cube" shape. Cubes are defined by six scalar
 350 ** coordinates as follows:
 351 **
 352 **   cube(x, y, z, width, height, depth)
 353 **
 354 ** The width, height and depth parameters must all be greater than zero.
 355 */
 356 static int cube_geom(
 357   sqlite3_rtree_geometry *p,
 358   int nCoord,
 359   sqlite3_rtree_dbl *aCoord,
 360   int *piRes
 361 ){
 362   Cube *pCube = (Cube *)p->pUser;
 363
 364   assert( p->pContext==(void *)&gHere );
 365
 366   if( pCube==0 ){
 367     if( p->nParam!=6 || nCoord!=6
 368      || p->aParam[3]<=0.0 || p->aParam[4]<=0.0 || p->aParam[5]<=0.0
 369     ){
 370       return SQLITE_ERROR;
 371     }
 372     pCube = (Cube *)sqlite3_malloc(sizeof(Cube));
 373     if( !pCube ){
 374       return SQLITE_NOMEM;
 375     }
 376     pCube->x = p->aParam[0];
 377     pCube->y = p->aParam[1];
 378     pCube->z = p->aParam[2];
 379     pCube->width = p->aParam[3];
 380     pCube->height = p->aParam[4];
 381     pCube->depth = p->aParam[5];
 382
 383     p->pUser = (void *)pCube;
 384     p->xDelUser = cube_context_free;
 385   }
 386
 387   assert( nCoord==6 );
 388   *piRes = 0;
 389   if( aCoord[0]<=(pCube->x+pCube->width)
 390    && aCoord[1]>=pCube->x
 391    && aCoord[2]<=(pCube->y+pCube->height)
 392    && aCoord[3]>=pCube->y
 393    && aCoord[4]<=(pCube->z+pCube->depth)
 394    && aCoord[5]>=pCube->z
 395   ){
 396     *piRes = 1;
 397   }
 398
 399   return SQLITE_OK;
 400 }
 401 #endif /* SQLITE_ENABLE_RTREE */
 402
 403 static int register_cube_geom(
 404   void * clientData,
 405   Tcl_Interp *interp,
 406   int objc,
 407   Tcl_Obj *CONST objv[]
 408 ){
 409 #ifndef SQLITE_ENABLE_RTREE
 410   UNUSED_PARAMETER(clientData);
 411   UNUSED_PARAMETER(interp);
 412   UNUSED_PARAMETER(objc);
 413   UNUSED_PARAMETER(objv);
 414 #else
 415   extern int getDbPointer(Tcl_Interp*, const char*, sqlite3**);
 416   extern const char *sqlite3ErrName(int);
 417   sqlite3 *db;
 418   int rc;
 419
 420   if( objc!=2 ){
 421     Tcl_WrongNumArgs(interp, 1, objv, "DB");
 422     return TCL_ERROR;
 423   }
 424   if( getDbPointer(interp, Tcl_GetString(objv[1]), &db) ) return TCL_ERROR;
 425   rc = sqlite3_rtree_geometry_callback(db, "cube", cube_geom, (void *)&gHere);
 426   Tcl_SetResult(interp, (char *)sqlite3ErrName(rc), TCL_STATIC);
 427 #endif
 428   return TCL_OK;
 429 }
 430
 431 static int register_circle_geom(
 432   void * clientData,
 433   Tcl_Interp *interp,
 434   int objc,
 435   Tcl_Obj *CONST objv[]
 436 ){
 437 #ifndef SQLITE_ENABLE_RTREE
 438   UNUSED_PARAMETER(clientData);
 439   UNUSED_PARAMETER(interp);
 440   UNUSED_PARAMETER(objc);
 441   UNUSED_PARAMETER(objv);
 442 #else
 443   extern int getDbPointer(Tcl_Interp*, const char*, sqlite3**);
 444   extern const char *sqlite3ErrName(int);
 445   sqlite3 *db;
 446   int rc;
 447
 448   if( objc!=2 ){
 449     Tcl_WrongNumArgs(interp, 1, objv, "DB");
 450     return TCL_ERROR;
 451   }
 452   if( getDbPointer(interp, Tcl_GetString(objv[1]), &db) ) return TCL_ERROR;
 453   rc = sqlite3_rtree_geometry_callback(db, "circle", circle_geom, 0);
 454   if( rc==SQLITE_OK ){
 455     rc = sqlite3_rtree_query_callback(db, "Qcircle",
 456                                       circle_query_func, 0, 0);
 457   }
 458   if( rc==SQLITE_OK ){
 459     rc = sqlite3_rtree_query_callback(db, "breadthfirstsearch",
 460                                       bfs_query_func, 0, 0);
 461   }
 462   Tcl_SetResult(interp, (char *)sqlite3ErrName(rc), TCL_STATIC);
 463 #endif
 464   return TCL_OK;
 465 }
 466
 467 int Sqlitetestrtree_Init(Tcl_Interp *interp){
 468   Tcl_CreateObjCommand(interp, "register_cube_geom", register_cube_geom, 0, 0);
 469   Tcl_CreateObjCommand(interp, "register_circle_geom",register_circle_geom,0,0);
 470   return TCL_OK;
 471 }