OLD | NEW |
| (Empty) |
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 ** Two calling forms: | |
160 ** | |
161 ** Qcircle(X,Y,Radius,eType) -- All values are doubles | |
162 ** Qcircle('x:X y:Y r:R e:ETYPE') -- Single string parameter | |
163 */ | |
164 static 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 tested | |
178 ** 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_NOMEM | |
189 ** 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 that | |
195 ** tested bounding boxes that intersect the circular region are detected | |
196 ** is by testing if each corner of the bounding box lies within radius | |
197 ** 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 to | |
232 ** infinity in the X dimension. It covers the same range of the Y dimension | |
233 ** as the circular region. The second, aBox[1], extends to infinity in | |
234 ** the Y dimension and is constrained to the range of the circle in the | |
235 ** X dimension. | |
236 ** | |
237 ** Then imagine each box is split in half along its short axis by a line | |
238 ** that intersects the center of the circular region. A bounding box | |
239 ** being tested can be said to intersect the circular region if it contains | |
240 ** 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 does | |
255 ** intersect the region of interest. Set the output variable to true and | |
256 ** 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 does | |
269 ** cover part of the circular region, set the output variable to true | |
270 ** 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 with | |
292 ** 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 */ | |
325 static 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 "tcl.h" | |
357 | |
358 typedef struct Cube Cube; | |
359 struct Cube { | |
360 double x; | |
361 double y; | |
362 double z; | |
363 double width; | |
364 double height; | |
365 double depth; | |
366 }; | |
367 | |
368 static void cube_context_free(void *p){ | |
369 sqlite3_free(p); | |
370 } | |
371 | |
372 /* | |
373 ** The context pointer registered along with the 'cube' callback is | |
374 ** always ((void *)&gHere). This is just to facilitate testing, it is not | |
375 ** actually used for anything. | |
376 */ | |
377 static int gHere = 42; | |
378 | |
379 /* | |
380 ** Implementation of a simple r-tree geom callback to test for intersection | |
381 ** of r-tree rows with a "cube" shape. Cubes are defined by six scalar | |
382 ** 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 */ | |
388 static int cube_geom( | |
389 sqlite3_rtree_geometry *p, | |
390 int nCoord, | |
391 sqlite3_rtree_dbl *aCoord, | |
392 int *piRes | |
393 ){ | |
394 Cube *pCube = (Cube *)p->pUser; | |
395 | |
396 assert( p->pContext==(void *)&gHere ); | |
397 | |
398 if( pCube==0 ){ | |
399 if( p->nParam!=6 || nCoord!=6 | |
400 || p->aParam[3]<=0.0 || p->aParam[4]<=0.0 || p->aParam[5]<=0.0 | |
401 ){ | |
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->x | |
423 && aCoord[2]<=(pCube->y+pCube->height) | |
424 && aCoord[3]>=pCube->y | |
425 && aCoord[4]<=(pCube->z+pCube->depth) | |
426 && aCoord[5]>=pCube->z | |
427 ){ | |
428 *piRes = 1; | |
429 } | |
430 | |
431 return SQLITE_OK; | |
432 } | |
433 #endif /* SQLITE_ENABLE_RTREE */ | |
434 | |
435 static int register_cube_geom( | |
436 void * clientData, | |
437 Tcl_Interp *interp, | |
438 int objc, | |
439 Tcl_Obj *CONST objv[] | |
440 ){ | |
441 #ifndef SQLITE_ENABLE_RTREE | |
442 UNUSED_PARAMETER(clientData); | |
443 UNUSED_PARAMETER(interp); | |
444 UNUSED_PARAMETER(objc); | |
445 UNUSED_PARAMETER(objv); | |
446 #else | |
447 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 #endif | |
460 return TCL_OK; | |
461 } | |
462 | |
463 static int register_circle_geom( | |
464 void * clientData, | |
465 Tcl_Interp *interp, | |
466 int objc, | |
467 Tcl_Obj *CONST objv[] | |
468 ){ | |
469 #ifndef SQLITE_ENABLE_RTREE | |
470 UNUSED_PARAMETER(clientData); | |
471 UNUSED_PARAMETER(interp); | |
472 UNUSED_PARAMETER(objc); | |
473 UNUSED_PARAMETER(objv); | |
474 #else | |
475 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 #endif | |
496 return TCL_OK; | |
497 } | |
498 | |
499 int 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 } | |
OLD | NEW |