Merge Chromium + Blink git repositories
[chromium-blink-merge.git] / third_party / sqlite / sqlite-src-3080704 / src / test_rtree.c
blob9d19fa0e2c86657b56dc4c8a22cd37e5485c8cbb
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.
11 *************************************************************************
12 ** Code for testing all sorts of SQLite interfaces. This code
13 ** is not included in the SQLite library.
16 #include <sqlite3.h>
17 #include <tcl.h>
19 /* Solely for the UNUSED_PARAMETER() macro. */
20 #include "sqliteInt.h"
22 #ifdef SQLITE_ENABLE_RTREE
23 /*
24 ** Type used to cache parameter information for the "circle" r-tree geometry
25 ** callback.
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;
43 ** Destructor function for Circle objects allocated by circle_geom().
45 static void circle_del(void *p){
46 sqlite3_free(p);
50 ** Implementation of "circle" r-tree geometry callback.
52 static int circle_geom(
53 sqlite3_rtree_geometry *p,
54 int nCoord,
55 sqlite3_rtree_dbl *aCoord,
56 int *pRes
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 */
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. */
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;
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;
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;
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];
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.
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.
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;
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;
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;
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
144 *pRes = 1;
145 return SQLITE_OK;
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;
156 ** Implementation of "circle" r-tree geometry callback using the
157 ** 2nd-generation interface that allows scoring.
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 */
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. */
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;
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;
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;
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];
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.
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.
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;
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;
230 d2 = (x-pCircle->centerx)*(x-pCircle->centerx);
231 d2 += (y-pCircle->centery)*(y-pCircle->centery);
232 if( d2<(pCircle->radius*pCircle->radius) ) nWithin++;
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
246 nWithin = 1;
247 break;
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;
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;
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;
283 return SQLITE_OK;
286 ** Implementation of "breadthfirstsearch" r-tree geometry callback using the
287 ** 2nd-generation interface that allows scoring.
289 ** ... WHERE id MATCH breadthfirstsearch($x0,$x1,$y0,$y1) ...
291 ** It returns all entries whose bounding boxes overlap with $x0,$x1,$y0,$y1.
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 */
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;
316 return SQLITE_OK;
319 /* END of implementation of "circle" geometry callback.
320 **************************************************************************
321 *************************************************************************/
323 #include <assert.h>
324 #include "tcl.h"
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;
336 static void cube_context_free(void *p){
337 sqlite3_free(p);
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.
345 static int gHere = 42;
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:
352 ** cube(x, y, z, width, height, depth)
354 ** The width, height and depth parameters must all be greater than zero.
356 static int cube_geom(
357 sqlite3_rtree_geometry *p,
358 int nCoord,
359 sqlite3_rtree_dbl *aCoord,
360 int *piRes
362 Cube *pCube = (Cube *)p->pUser;
364 assert( p->pContext==(void *)&gHere );
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
370 return SQLITE_ERROR;
372 pCube = (Cube *)sqlite3_malloc(sizeof(Cube));
373 if( !pCube ){
374 return SQLITE_NOMEM;
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];
383 p->pUser = (void *)pCube;
384 p->xDelUser = cube_context_free;
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
396 *piRes = 1;
399 return SQLITE_OK;
401 #endif /* SQLITE_ENABLE_RTREE */
403 static int register_cube_geom(
404 void * clientData,
405 Tcl_Interp *interp,
406 int objc,
407 Tcl_Obj *CONST objv[]
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;
420 if( objc!=2 ){
421 Tcl_WrongNumArgs(interp, 1, objv, "DB");
422 return TCL_ERROR;
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;
431 static int register_circle_geom(
432 void * clientData,
433 Tcl_Interp *interp,
434 int objc,
435 Tcl_Obj *CONST objv[]
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;
448 if( objc!=2 ){
449 Tcl_WrongNumArgs(interp, 1, objv, "DB");
450 return TCL_ERROR;
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);
458 if( rc==SQLITE_OK ){
459 rc = sqlite3_rtree_query_callback(db, "breadthfirstsearch",
460 bfs_query_func, 0, 0);
462 Tcl_SetResult(interp, (char *)sqlite3ErrName(rc), TCL_STATIC);
463 #endif
464 return TCL_OK;
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;