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