| OLD | NEW |
|---|
| (Empty) |
| 1 /* | |
| 2 ** 2013-04-16 | |
| 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 ** | |
| 13 ** This file contains code for a virtual table that finds the transitive | |
| 14 ** closure of a parent/child relationship in a real table. The virtual | |
| 15 ** table is called "transitive_closure". | |
| 16 ** | |
| 17 ** A transitive_closure virtual table is created like this: | |
| 18 ** | |
| 19 ** CREATE VIRTUAL TABLE x USING transitive_closure( | |
| 20 ** tablename=<tablename>, -- T | |
| 21 ** idcolumn=<columnname>, -- X | |
| 22 ** parentcolumn=<columnname> -- P | |
| 23 ** ); | |
| 24 ** | |
| 25 ** When it is created, the new transitive_closure table may be supplied | |
| 26 ** with default values for the name of a table T and columns T.X and T.P. | |
| 27 ** The T.X and T.P columns must contain integers. The ideal case is for | |
| 28 ** T.X to be the INTEGER PRIMARY KEY. The T.P column should reference | |
| 29 ** the T.X column. The row referenced by T.P is the parent of the current row. | |
| 30 ** | |
| 31 ** The tablename, idcolumn, and parentcolumn supplied by the CREATE VIRTUAL | |
| 32 ** TABLE statement may be overridden in individual queries by including | |
| 33 ** terms like tablename='newtable', idcolumn='id2', or | |
| 34 ** parentcolumn='parent3' in the WHERE clause of the query. | |
| 35 ** | |
| 36 ** For efficiency, it is essential that there be an index on the P column: | |
| 37 ** | |
| 38 ** CREATE Tidx1 ON T(P) | |
| 39 ** | |
| 40 ** Suppose a specific instance of the closure table is as follows: | |
| 41 ** | |
| 42 ** CREATE VIRTUAL TABLE ct1 USING transitive_closure( | |
| 43 ** tablename='group', | |
| 44 ** idcolumn='groupId', | |
| 45 ** parentcolumn='parentId' | |
| 46 ** ); | |
| 47 ** | |
| 48 ** Such an instance of the transitive_closure virtual table would be | |
| 49 ** appropriate for walking a tree defined using a table like this, for example: | |
| 50 ** | |
| 51 ** CREATE TABLE group( | |
| 52 ** groupId INTEGER PRIMARY KEY, | |
| 53 ** parentId INTEGER REFERENCES group | |
| 54 ** ); | |
| 55 ** CREATE INDEX group_idx1 ON group(parentId); | |
| 56 ** | |
| 57 ** The group table above would presumably have other application-specific | |
| 58 ** fields. The key point here is that rows of the group table form a | |
| 59 ** tree. The purpose of the ct1 virtual table is to easily extract | |
| 60 ** branches of that tree. | |
| 61 ** | |
| 62 ** Once it has been created, the ct1 virtual table can be queried | |
| 63 ** as follows: | |
| 64 ** | |
| 65 ** SELECT * FROM element | |
| 66 ** WHERE element.groupId IN (SELECT id FROM ct1 WHERE root=?1); | |
| 67 ** | |
| 68 ** The above query will return all elements that are part of group ?1 | |
| 69 ** or children of group ?1 or grand-children of ?1 and so forth for all | |
| 70 ** descendents of group ?1. The same query can be formulated as a join: | |
| 71 ** | |
| 72 ** SELECT element.* FROM element, ct1 | |
| 73 ** WHERE element.groupid=ct1.id | |
| 74 ** AND ct1.root=?1; | |
| 75 ** | |
| 76 ** The depth of the transitive_closure (the number of generations of | |
| 77 ** parent/child relations to follow) can be limited by setting "depth" | |
| 78 ** column in the WHERE clause. So, for example, the following query | |
| 79 ** finds only children and grandchildren but no further descendents: | |
| 80 ** | |
| 81 ** SELECT element.* FROM element, ct1 | |
| 82 ** WHERE element.groupid=ct1.id | |
| 83 ** AND ct1.root=?1 | |
| 84 ** AND ct1.depth<=2; | |
| 85 ** | |
| 86 ** The "ct1.depth<=2" term could be a strict equality "ct1.depth=2" in | |
| 87 ** order to find only the grandchildren of ?1, not ?1 itself or the | |
| 88 ** children of ?1. | |
| 89 ** | |
| 90 ** The root=?1 term must be supplied in WHERE clause or else the query | |
| 91 ** of the ct1 virtual table will return an empty set. The tablename, | |
| 92 ** idcolumn, and parentcolumn attributes can be overridden in the WHERE | |
| 93 ** clause if desired. So, for example, the ct1 table could be repurposed | |
| 94 ** to find ancestors rather than descendents by inverting the roles of | |
| 95 ** the idcolumn and parentcolumn: | |
| 96 ** | |
| 97 ** SELECT element.* FROM element, ct1 | |
| 98 ** WHERE element.groupid=ct1.id | |
| 99 ** AND ct1.root=?1 | |
| 100 ** AND ct1.idcolumn='parentId' | |
| 101 ** AND ct1.parentcolumn='groupId'; | |
| 102 ** | |
| 103 ** Multiple calls to ct1 could be combined. For example, the following | |
| 104 ** query finds all elements that "cousins" of groupId ?1. That is to say | |
| 105 ** elements where the groupId is a grandchild of the grandparent of ?1. | |
| 106 ** (This definition of "cousins" also includes siblings and self.) | |
| 107 ** | |
| 108 ** SELECT element.* FROM element, ct1 | |
| 109 ** WHERE element.groupId=ct1.id | |
| 110 ** AND ct1.depth=2 | |
| 111 ** AND ct1.root IN (SELECT id FROM ct1 | |
| 112 ** WHERE root=?1 | |
| 113 ** AND depth=2 | |
| 114 ** AND idcolumn='parentId' | |
| 115 ** AND parentcolumn='groupId'); | |
| 116 ** | |
| 117 ** In our example, the group.groupId column is unique and thus the | |
| 118 ** subquery will return exactly one row. For that reason, the IN | |
| 119 ** operator could be replaced by "=" to get the same result. But | |
| 120 ** in the general case where the idcolumn is not unique, an IN operator | |
| 121 ** would be required for this kind of query. | |
| 122 ** | |
| 123 ** Note that because the tablename, idcolumn, and parentcolumn can | |
| 124 ** all be specified in the query, it is possible for an application | |
| 125 ** to define a single transitive_closure virtual table for use on lots | |
| 126 ** of different hierarchy tables. One might say: | |
| 127 ** | |
| 128 ** CREATE VIRTUAL TABLE temp.closure USING transitive_closure; | |
| 129 ** | |
| 130 ** As each database connection is being opened. Then the application | |
| 131 ** would always have a "closure" virtual table handy to use for querying. | |
| 132 ** | |
| 133 ** SELECT element.* FROM element, closure | |
| 134 ** WHERE element.groupid=ct1.id | |
| 135 ** AND closure.root=?1 | |
| 136 ** AND closure.tablename='group' | |
| 137 ** AND closure.idname='groupId' | |
| 138 ** AND closure.parentname='parentId'; | |
| 139 ** | |
| 140 ** See the documentation at http://www.sqlite.org/loadext.html for information | |
| 141 ** on how to compile and use loadable extensions such as this one. | |
| 142 */ | |
| 143 #include "sqlite3ext.h" | |
| 144 SQLITE_EXTENSION_INIT1 | |
| 145 #include <stdlib.h> | |
| 146 #include <string.h> | |
| 147 #include <assert.h> | |
| 148 #include <stdio.h> | |
| 149 #include <ctype.h> | |
| 150 | |
| 151 #ifndef SQLITE_OMIT_VIRTUALTABLE | |
| 152 | |
| 153 /* | |
| 154 ** Forward declaration of objects used by this implementation | |
| 155 */ | |
| 156 typedef struct closure_vtab closure_vtab; | |
| 157 typedef struct closure_cursor closure_cursor; | |
| 158 typedef struct closure_queue closure_queue; | |
| 159 typedef struct closure_avl closure_avl; | |
| 160 | |
| 161 /***************************************************************************** | |
| 162 ** AVL Tree implementation | |
| 163 */ | |
| 164 /* | |
| 165 ** Objects that want to be members of the AVL tree should embedded an | |
| 166 ** instance of this structure. | |
| 167 */ | |
| 168 struct closure_avl { | |
| 169 sqlite3_int64 id; /* Id of this entry in the table */ | |
| 170 int iGeneration; /* Which generation is this entry part of */ | |
| 171 closure_avl *pList; /* A linked list of nodes */ | |
| 172 closure_avl *pBefore; /* Other elements less than id */ | |
| 173 closure_avl *pAfter; /* Other elements greater than id */ | |
| 174 closure_avl *pUp; /* Parent element */ | |
| 175 short int height; /* Height of this node. Leaf==1 */ | |
| 176 short int imbalance; /* Height difference between pBefore and pAfter */ | |
| 177 }; | |
| 178 | |
| 179 /* Recompute the closure_avl.height and closure_avl.imbalance fields for p. | |
| 180 ** Assume that the children of p have correct heights. | |
| 181 */ | |
| 182 static void closureAvlRecomputeHeight(closure_avl *p){ | |
| 183 short int hBefore = p->pBefore ? p->pBefore->height : 0; | |
| 184 short int hAfter = p->pAfter ? p->pAfter->height : 0; | |
| 185 p->imbalance = hBefore - hAfter; /* -: pAfter higher. +: pBefore higher */ | |
| 186 p->height = (hBefore>hAfter ? hBefore : hAfter)+1; | |
| 187 } | |
| 188 | |
| 189 /* | |
| 190 ** P B | |
| 191 ** / \ / \ | |
| 192 ** B Z ==> X P | |
| 193 ** / \ / \ | |
| 194 ** X Y Y Z | |
| 195 ** | |
| 196 */ | |
| 197 static closure_avl *closureAvlRotateBefore(closure_avl *pP){ | |
| 198 closure_avl *pB = pP->pBefore; | |
| 199 closure_avl *pY = pB->pAfter; | |
| 200 pB->pUp = pP->pUp; | |
| 201 pB->pAfter = pP; | |
| 202 pP->pUp = pB; | |
| 203 pP->pBefore = pY; | |
| 204 if( pY ) pY->pUp = pP; | |
| 205 closureAvlRecomputeHeight(pP); | |
| 206 closureAvlRecomputeHeight(pB); | |
| 207 return pB; | |
| 208 } | |
| 209 | |
| 210 /* | |
| 211 ** P A | |
| 212 ** / \ / \ | |
| 213 ** X A ==> P Z | |
| 214 ** / \ / \ | |
| 215 ** Y Z X Y | |
| 216 ** | |
| 217 */ | |
| 218 static closure_avl *closureAvlRotateAfter(closure_avl *pP){ | |
| 219 closure_avl *pA = pP->pAfter; | |
| 220 closure_avl *pY = pA->pBefore; | |
| 221 pA->pUp = pP->pUp; | |
| 222 pA->pBefore = pP; | |
| 223 pP->pUp = pA; | |
| 224 pP->pAfter = pY; | |
| 225 if( pY ) pY->pUp = pP; | |
| 226 closureAvlRecomputeHeight(pP); | |
| 227 closureAvlRecomputeHeight(pA); | |
| 228 return pA; | |
| 229 } | |
| 230 | |
| 231 /* | |
| 232 ** Return a pointer to the pBefore or pAfter pointer in the parent | |
| 233 ** of p that points to p. Or if p is the root node, return pp. | |
| 234 */ | |
| 235 static closure_avl **closureAvlFromPtr(closure_avl *p, closure_avl **pp){ | |
| 236 closure_avl *pUp = p->pUp; | |
| 237 if( pUp==0 ) return pp; | |
| 238 if( pUp->pAfter==p ) return &pUp->pAfter; | |
| 239 return &pUp->pBefore; | |
| 240 } | |
| 241 | |
| 242 /* | |
| 243 ** Rebalance all nodes starting with p and working up to the root. | |
| 244 ** Return the new root. | |
| 245 */ | |
| 246 static closure_avl *closureAvlBalance(closure_avl *p){ | |
| 247 closure_avl *pTop = p; | |
| 248 closure_avl **pp; | |
| 249 while( p ){ | |
| 250 closureAvlRecomputeHeight(p); | |
| 251 if( p->imbalance>=2 ){ | |
| 252 closure_avl *pB = p->pBefore; | |
| 253 if( pB->imbalance<0 ) p->pBefore = closureAvlRotateAfter(pB); | |
| 254 pp = closureAvlFromPtr(p,&p); | |
| 255 p = *pp = closureAvlRotateBefore(p); | |
| 256 }else if( p->imbalance<=(-2) ){ | |
| 257 closure_avl *pA = p->pAfter; | |
| 258 if( pA->imbalance>0 ) p->pAfter = closureAvlRotateBefore(pA); | |
| 259 pp = closureAvlFromPtr(p,&p); | |
| 260 p = *pp = closureAvlRotateAfter(p); | |
| 261 } | |
| 262 pTop = p; | |
| 263 p = p->pUp; | |
| 264 } | |
| 265 return pTop; | |
| 266 } | |
| 267 | |
| 268 /* Search the tree rooted at p for an entry with id. Return a pointer | |
| 269 ** to the entry or return NULL. | |
| 270 */ | |
| 271 static closure_avl *closureAvlSearch(closure_avl *p, sqlite3_int64 id){ | |
| 272 while( p && id!=p->id ){ | |
| 273 p = (id<p->id) ? p->pBefore : p->pAfter; | |
| 274 } | |
| 275 return p; | |
| 276 } | |
| 277 | |
| 278 /* Find the first node (the one with the smallest key). | |
| 279 */ | |
| 280 static closure_avl *closureAvlFirst(closure_avl *p){ | |
| 281 if( p ) while( p->pBefore ) p = p->pBefore; | |
| 282 return p; | |
| 283 } | |
| 284 | |
| 285 /* Return the node with the next larger key after p. | |
| 286 */ | |
| 287 closure_avl *closureAvlNext(closure_avl *p){ | |
| 288 closure_avl *pPrev = 0; | |
| 289 while( p && p->pAfter==pPrev ){ | |
| 290 pPrev = p; | |
| 291 p = p->pUp; | |
| 292 } | |
| 293 if( p && pPrev==0 ){ | |
| 294 p = closureAvlFirst(p->pAfter); | |
| 295 } | |
| 296 return p; | |
| 297 } | |
| 298 | |
| 299 /* Insert a new node pNew. Return NULL on success. If the key is not | |
| 300 ** unique, then do not perform the insert but instead leave pNew unchanged | |
| 301 ** and return a pointer to an existing node with the same key. | |
| 302 */ | |
| 303 static closure_avl *closureAvlInsert( | |
| 304 closure_avl **ppHead, /* Head of the tree */ | |
| 305 closure_avl *pNew /* New node to be inserted */ | |
| 306 ){ | |
| 307 closure_avl *p = *ppHead; | |
| 308 if( p==0 ){ | |
| 309 p = pNew; | |
| 310 pNew->pUp = 0; | |
| 311 }else{ | |
| 312 while( p ){ | |
| 313 if( pNew->id<p->id ){ | |
| 314 if( p->pBefore ){ | |
| 315 p = p->pBefore; | |
| 316 }else{ | |
| 317 p->pBefore = pNew; | |
| 318 pNew->pUp = p; | |
| 319 break; | |
| 320 } | |
| 321 }else if( pNew->id>p->id ){ | |
| 322 if( p->pAfter ){ | |
| 323 p = p->pAfter; | |
| 324 }else{ | |
| 325 p->pAfter = pNew; | |
| 326 pNew->pUp = p; | |
| 327 break; | |
| 328 } | |
| 329 }else{ | |
| 330 return p; | |
| 331 } | |
| 332 } | |
| 333 } | |
| 334 pNew->pBefore = 0; | |
| 335 pNew->pAfter = 0; | |
| 336 pNew->height = 1; | |
| 337 pNew->imbalance = 0; | |
| 338 *ppHead = closureAvlBalance(p); | |
| 339 return 0; | |
| 340 } | |
| 341 | |
| 342 /* Walk the tree can call xDestroy on each node | |
| 343 */ | |
| 344 static void closureAvlDestroy(closure_avl *p, void (*xDestroy)(closure_avl*)){ | |
| 345 if( p ){ | |
| 346 closureAvlDestroy(p->pBefore, xDestroy); | |
| 347 closureAvlDestroy(p->pAfter, xDestroy); | |
| 348 xDestroy(p); | |
| 349 } | |
| 350 } | |
| 351 /* | |
| 352 ** End of the AVL Tree implementation | |
| 353 ******************************************************************************/ | |
| 354 | |
| 355 /* | |
| 356 ** A closure virtual-table object | |
| 357 */ | |
| 358 struct closure_vtab { | |
| 359 sqlite3_vtab base; /* Base class - must be first */ | |
| 360 char *zDb; /* Name of database. (ex: "main") */ | |
| 361 char *zSelf; /* Name of this virtual table */ | |
| 362 char *zTableName; /* Name of table holding parent/child relation */ | |
| 363 char *zIdColumn; /* Name of ID column of zTableName */ | |
| 364 char *zParentColumn; /* Name of PARENT column in zTableName */ | |
| 365 sqlite3 *db; /* The database connection */ | |
| 366 int nCursor; /* Number of pending cursors */ | |
| 367 }; | |
| 368 | |
| 369 /* A closure cursor object */ | |
| 370 struct closure_cursor { | |
| 371 sqlite3_vtab_cursor base; /* Base class - must be first */ | |
| 372 closure_vtab *pVtab; /* The virtual table this cursor belongs to */ | |
| 373 char *zTableName; /* Name of table holding parent/child relation */ | |
| 374 char *zIdColumn; /* Name of ID column of zTableName */ | |
| 375 char *zParentColumn; /* Name of PARENT column in zTableName */ | |
| 376 closure_avl *pCurrent; /* Current element of output */ | |
| 377 closure_avl *pClosure; /* The complete closure tree */ | |
| 378 }; | |
| 379 | |
| 380 /* A queue of AVL nodes */ | |
| 381 struct closure_queue { | |
| 382 closure_avl *pFirst; /* Oldest node on the queue */ | |
| 383 closure_avl *pLast; /* Youngest node on the queue */ | |
| 384 }; | |
| 385 | |
| 386 /* | |
| 387 ** Add a node to the end of the queue | |
| 388 */ | |
| 389 static void queuePush(closure_queue *pQueue, closure_avl *pNode){ | |
| 390 pNode->pList = 0; | |
| 391 if( pQueue->pLast ){ | |
| 392 pQueue->pLast->pList = pNode; | |
| 393 }else{ | |
| 394 pQueue->pFirst = pNode; | |
| 395 } | |
| 396 pQueue->pLast = pNode; | |
| 397 } | |
| 398 | |
| 399 /* | |
| 400 ** Extract the oldest element (the front element) from the queue. | |
| 401 */ | |
| 402 static closure_avl *queuePull(closure_queue *pQueue){ | |
| 403 closure_avl *p = pQueue->pFirst; | |
| 404 if( p ){ | |
| 405 pQueue->pFirst = p->pList; | |
| 406 if( pQueue->pFirst==0 ) pQueue->pLast = 0; | |
| 407 } | |
| 408 return p; | |
| 409 } | |
| 410 | |
| 411 /* | |
| 412 ** This function converts an SQL quoted string into an unquoted string | |
| 413 ** and returns a pointer to a buffer allocated using sqlite3_malloc() | |
| 414 ** containing the result. The caller should eventually free this buffer | |
| 415 ** using sqlite3_free. | |
| 416 ** | |
| 417 ** Examples: | |
| 418 ** | |
| 419 ** "abc" becomes abc | |
| 420 ** 'xyz' becomes xyz | |
| 421 ** [pqr] becomes pqr | |
| 422 ** `mno` becomes mno | |
| 423 */ | |
| 424 static char *closureDequote(const char *zIn){ | |
| 425 int nIn; /* Size of input string, in bytes */ | |
| 426 char *zOut; /* Output (dequoted) string */ | |
| 427 | |
| 428 nIn = (int)strlen(zIn); | |
| 429 zOut = sqlite3_malloc(nIn+1); | |
| 430 if( zOut ){ | |
| 431 char q = zIn[0]; /* Quote character (if any ) */ | |
| 432 | |
| 433 if( q!='[' && q!= '\'' && q!='"' && q!='`' ){ | |
| 434 memcpy(zOut, zIn, nIn+1); | |
| 435 }else{ | |
| 436 int iOut = 0; /* Index of next byte to write to output */ | |
| 437 int iIn; /* Index of next byte to read from input */ | |
| 438 | |
| 439 if( q=='[' ) q = ']'; | |
| 440 for(iIn=1; iIn<nIn; iIn++){ | |
| 441 if( zIn[iIn]==q ) iIn++; | |
| 442 zOut[iOut++] = zIn[iIn]; | |
| 443 } | |
| 444 } | |
| 445 assert( (int)strlen(zOut)<=nIn ); | |
| 446 } | |
| 447 return zOut; | |
| 448 } | |
| 449 | |
| 450 /* | |
| 451 ** Deallocate an closure_vtab object | |
| 452 */ | |
| 453 static void closureFree(closure_vtab *p){ | |
| 454 if( p ){ | |
| 455 sqlite3_free(p->zDb); | |
| 456 sqlite3_free(p->zSelf); | |
| 457 sqlite3_free(p->zTableName); | |
| 458 sqlite3_free(p->zIdColumn); | |
| 459 sqlite3_free(p->zParentColumn); | |
| 460 memset(p, 0, sizeof(*p)); | |
| 461 sqlite3_free(p); | |
| 462 } | |
| 463 } | |
| 464 | |
| 465 /* | |
| 466 ** xDisconnect/xDestroy method for the closure module. | |
| 467 */ | |
| 468 static int closureDisconnect(sqlite3_vtab *pVtab){ | |
| 469 closure_vtab *p = (closure_vtab*)pVtab; | |
| 470 assert( p->nCursor==0 ); | |
| 471 closureFree(p); | |
| 472 return SQLITE_OK; | |
| 473 } | |
| 474 | |
| 475 /* | |
| 476 ** Check to see if the argument is of the form: | |
| 477 ** | |
| 478 ** KEY = VALUE | |
| 479 ** | |
| 480 ** If it is, return a pointer to the first character of VALUE. | |
| 481 ** If not, return NULL. Spaces around the = are ignored. | |
| 482 */ | |
| 483 static const char *closureValueOfKey(const char *zKey, const char *zStr){ | |
| 484 int nKey = (int)strlen(zKey); | |
| 485 int nStr = (int)strlen(zStr); | |
| 486 int i; | |
| 487 if( nStr<nKey+1 ) return 0; | |
| 488 if( memcmp(zStr, zKey, nKey)!=0 ) return 0; | |
| 489 for(i=nKey; isspace(zStr[i]); i++){} | |
| 490 if( zStr[i]!='=' ) return 0; | |
| 491 i++; | |
| 492 while( isspace(zStr[i]) ){ i++; } | |
| 493 return zStr+i; | |
| 494 } | |
| 495 | |
| 496 /* | |
| 497 ** xConnect/xCreate method for the closure module. Arguments are: | |
| 498 ** | |
| 499 ** argv[0] -> module name ("transitive_closure") | |
| 500 ** argv[1] -> database name | |
| 501 ** argv[2] -> table name | |
| 502 ** argv[3...] -> arguments | |
| 503 */ | |
| 504 static int closureConnect( | |
| 505 sqlite3 *db, | |
| 506 void *pAux, | |
| 507 int argc, const char *const*argv, | |
| 508 sqlite3_vtab **ppVtab, | |
| 509 char **pzErr | |
| 510 ){ | |
| 511 int rc = SQLITE_OK; /* Return code */ | |
| 512 closure_vtab *pNew = 0; /* New virtual table */ | |
| 513 const char *zDb = argv[1]; | |
| 514 const char *zVal; | |
| 515 int i; | |
| 516 | |
| 517 (void)pAux; | |
| 518 *ppVtab = 0; | |
| 519 pNew = sqlite3_malloc( sizeof(*pNew) ); | |
| 520 if( pNew==0 ) return SQLITE_NOMEM; | |
| 521 rc = SQLITE_NOMEM; | |
| 522 memset(pNew, 0, sizeof(*pNew)); | |
| 523 pNew->db = db; | |
| 524 pNew->zDb = sqlite3_mprintf("%s", zDb); | |
| 525 if( pNew->zDb==0 ) goto closureConnectError; | |
| 526 pNew->zSelf = sqlite3_mprintf("%s", argv[2]); | |
| 527 if( pNew->zSelf==0 ) goto closureConnectError; | |
| 528 for(i=3; i<argc; i++){ | |
| 529 zVal = closureValueOfKey("tablename", argv[i]); | |
| 530 if( zVal ){ | |
| 531 sqlite3_free(pNew->zTableName); | |
| 532 pNew->zTableName = closureDequote(zVal); | |
| 533 if( pNew->zTableName==0 ) goto closureConnectError; | |
| 534 continue; | |
| 535 } | |
| 536 zVal = closureValueOfKey("idcolumn", argv[i]); | |
| 537 if( zVal ){ | |
| 538 sqlite3_free(pNew->zIdColumn); | |
| 539 pNew->zIdColumn = closureDequote(zVal); | |
| 540 if( pNew->zIdColumn==0 ) goto closureConnectError; | |
| 541 continue; | |
| 542 } | |
| 543 zVal = closureValueOfKey("parentcolumn", argv[i]); | |
| 544 if( zVal ){ | |
| 545 sqlite3_free(pNew->zParentColumn); | |
| 546 pNew->zParentColumn = closureDequote(zVal); | |
| 547 if( pNew->zParentColumn==0 ) goto closureConnectError; | |
| 548 continue; | |
| 549 } | |
| 550 *pzErr = sqlite3_mprintf("unrecognized argument: [%s]\n", argv[i]); | |
| 551 closureFree(pNew); | |
| 552 *ppVtab = 0; | |
| 553 return SQLITE_ERROR; | |
| 554 } | |
| 555 rc = sqlite3_declare_vtab(db, | |
| 556 "CREATE TABLE x(id,depth,root HIDDEN,tablename HIDDEN," | |
| 557 "idcolumn HIDDEN,parentcolumn HIDDEN)" | |
| 558 ); | |
| 559 #define CLOSURE_COL_ID 0 | |
| 560 #define CLOSURE_COL_DEPTH 1 | |
| 561 #define CLOSURE_COL_ROOT 2 | |
| 562 #define CLOSURE_COL_TABLENAME 3 | |
| 563 #define CLOSURE_COL_IDCOLUMN 4 | |
| 564 #define CLOSURE_COL_PARENTCOLUMN 5 | |
| 565 if( rc!=SQLITE_OK ){ | |
| 566 closureFree(pNew); | |
| 567 } | |
| 568 *ppVtab = &pNew->base; | |
| 569 return rc; | |
| 570 | |
| 571 closureConnectError: | |
| 572 closureFree(pNew); | |
| 573 return rc; | |
| 574 } | |
| 575 | |
| 576 /* | |
| 577 ** Open a new closure cursor. | |
| 578 */ | |
| 579 static int closureOpen(sqlite3_vtab *pVTab, sqlite3_vtab_cursor **ppCursor){ | |
| 580 closure_vtab *p = (closure_vtab*)pVTab; | |
| 581 closure_cursor *pCur; | |
| 582 pCur = sqlite3_malloc( sizeof(*pCur) ); | |
| 583 if( pCur==0 ) return SQLITE_NOMEM; | |
| 584 memset(pCur, 0, sizeof(*pCur)); | |
| 585 pCur->pVtab = p; | |
| 586 *ppCursor = &pCur->base; | |
| 587 p->nCursor++; | |
| 588 return SQLITE_OK; | |
| 589 } | |
| 590 | |
| 591 /* | |
| 592 ** Free up all the memory allocated by a cursor. Set it rLimit to 0 | |
| 593 ** to indicate that it is at EOF. | |
| 594 */ | |
| 595 static void closureClearCursor(closure_cursor *pCur){ | |
| 596 closureAvlDestroy(pCur->pClosure, (void(*)(closure_avl*))sqlite3_free); | |
| 597 sqlite3_free(pCur->zTableName); | |
| 598 sqlite3_free(pCur->zIdColumn); | |
| 599 sqlite3_free(pCur->zParentColumn); | |
| 600 pCur->zTableName = 0; | |
| 601 pCur->zIdColumn = 0; | |
| 602 pCur->zParentColumn = 0; | |
| 603 pCur->pCurrent = 0; | |
| 604 pCur->pClosure = 0; | |
| 605 } | |
| 606 | |
| 607 /* | |
| 608 ** Close a closure cursor. | |
| 609 */ | |
| 610 static int closureClose(sqlite3_vtab_cursor *cur){ | |
| 611 closure_cursor *pCur = (closure_cursor *)cur; | |
| 612 closureClearCursor(pCur); | |
| 613 pCur->pVtab->nCursor--; | |
| 614 sqlite3_free(pCur); | |
| 615 return SQLITE_OK; | |
| 616 } | |
| 617 | |
| 618 /* | |
| 619 ** Advance a cursor to its next row of output | |
| 620 */ | |
| 621 static int closureNext(sqlite3_vtab_cursor *cur){ | |
| 622 closure_cursor *pCur = (closure_cursor*)cur; | |
| 623 pCur->pCurrent = closureAvlNext(pCur->pCurrent); | |
| 624 return SQLITE_OK; | |
| 625 } | |
| 626 | |
| 627 /* | |
| 628 ** Allocate and insert a node | |
| 629 */ | |
| 630 static int closureInsertNode( | |
| 631 closure_queue *pQueue, /* Add new node to this queue */ | |
| 632 closure_cursor *pCur, /* The cursor into which to add the node */ | |
| 633 sqlite3_int64 id, /* The node ID */ | |
| 634 int iGeneration /* The generation number for this node */ | |
| 635 ){ | |
| 636 closure_avl *pNew = sqlite3_malloc( sizeof(*pNew) ); | |
| 637 if( pNew==0 ) return SQLITE_NOMEM; | |
| 638 memset(pNew, 0, sizeof(*pNew)); | |
| 639 pNew->id = id; | |
| 640 pNew->iGeneration = iGeneration; | |
| 641 closureAvlInsert(&pCur->pClosure, pNew); | |
| 642 queuePush(pQueue, pNew); | |
| 643 return SQLITE_OK; | |
| 644 } | |
| 645 | |
| 646 /* | |
| 647 ** Called to "rewind" a cursor back to the beginning so that | |
| 648 ** it starts its output over again. Always called at least once | |
| 649 ** prior to any closureColumn, closureRowid, or closureEof call. | |
| 650 ** | |
| 651 ** This routine actually computes the closure. | |
| 652 ** | |
| 653 ** See the comment at the beginning of closureBestIndex() for a | |
| 654 ** description of the meaning of idxNum. The idxStr parameter is | |
| 655 ** not used. | |
| 656 */ | |
| 657 static int closureFilter( | |
| 658 sqlite3_vtab_cursor *pVtabCursor, | |
| 659 int idxNum, const char *idxStr, | |
| 660 int argc, sqlite3_value **argv | |
| 661 ){ | |
| 662 closure_cursor *pCur = (closure_cursor *)pVtabCursor; | |
| 663 closure_vtab *pVtab = pCur->pVtab; | |
| 664 sqlite3_int64 iRoot; | |
| 665 int mxGen = 999999999; | |
| 666 char *zSql; | |
| 667 sqlite3_stmt *pStmt; | |
| 668 closure_avl *pAvl; | |
| 669 int rc = SQLITE_OK; | |
| 670 const char *zTableName = pVtab->zTableName; | |
| 671 const char *zIdColumn = pVtab->zIdColumn; | |
| 672 const char *zParentColumn = pVtab->zParentColumn; | |
| 673 closure_queue sQueue; | |
| 674 | |
| 675 (void)idxStr; /* Unused parameter */ | |
| 676 (void)argc; /* Unused parameter */ | |
| 677 closureClearCursor(pCur); | |
| 678 memset(&sQueue, 0, sizeof(sQueue)); | |
| 679 if( (idxNum & 1)==0 ){ | |
| 680 /* No root=$root in the WHERE clause. Return an empty set */ | |
| 681 return SQLITE_OK; | |
| 682 } | |
| 683 iRoot = sqlite3_value_int64(argv[0]); | |
| 684 if( (idxNum & 0x000f0)!=0 ){ | |
| 685 mxGen = sqlite3_value_int(argv[(idxNum>>4)&0x0f]); | |
| 686 if( (idxNum & 0x00002)!=0 ) mxGen--; | |
| 687 } | |
| 688 if( (idxNum & 0x00f00)!=0 ){ | |
| 689 zTableName = (const char*)sqlite3_value_text(argv[(idxNum>>8)&0x0f]); | |
| 690 pCur->zTableName = sqlite3_mprintf("%s", zTableName); | |
| 691 } | |
| 692 if( (idxNum & 0x0f000)!=0 ){ | |
| 693 zIdColumn = (const char*)sqlite3_value_text(argv[(idxNum>>12)&0x0f]); | |
| 694 pCur->zIdColumn = sqlite3_mprintf("%s", zIdColumn); | |
| 695 } | |
| 696 if( (idxNum & 0x0f0000)!=0 ){ | |
| 697 zParentColumn = (const char*)sqlite3_value_text(argv[(idxNum>>16)&0x0f]); | |
| 698 pCur->zParentColumn = sqlite3_mprintf("%s", zParentColumn); | |
| 699 } | |
| 700 | |
| 701 zSql = sqlite3_mprintf( | |
| 702 "SELECT \"%w\".\"%w\" FROM \"%w\" WHERE \"%w\".\"%w\"=?1", | |
| 703 zTableName, zIdColumn, zTableName, zTableName, zParentColumn); | |
| 704 if( zSql==0 ){ | |
| 705 return SQLITE_NOMEM; | |
| 706 }else{ | |
| 707 rc = sqlite3_prepare_v2(pVtab->db, zSql, -1, &pStmt, 0); | |
| 708 sqlite3_free(zSql); | |
| 709 if( rc ){ | |
| 710 sqlite3_free(pVtab->base.zErrMsg); | |
| 711 pVtab->base.zErrMsg = sqlite3_mprintf("%s", sqlite3_errmsg(pVtab->db)); | |
| 712 return rc; | |
| 713 } | |
| 714 } | |
| 715 if( rc==SQLITE_OK ){ | |
| 716 rc = closureInsertNode(&sQueue, pCur, iRoot, 0); | |
| 717 } | |
| 718 while( (pAvl = queuePull(&sQueue))!=0 ){ | |
| 719 if( pAvl->iGeneration>=mxGen ) continue; | |
| 720 sqlite3_bind_int64(pStmt, 1, pAvl->id); | |
| 721 while( rc==SQLITE_OK && sqlite3_step(pStmt)==SQLITE_ROW ){ | |
| 722 if( sqlite3_column_type(pStmt,0)==SQLITE_INTEGER ){ | |
| 723 sqlite3_int64 iNew = sqlite3_column_int64(pStmt, 0); | |
| 724 if( closureAvlSearch(pCur->pClosure, iNew)==0 ){ | |
| 725 rc = closureInsertNode(&sQueue, pCur, iNew, pAvl->iGeneration+1); | |
| 726 } | |
| 727 } | |
| 728 } | |
| 729 sqlite3_reset(pStmt); | |
| 730 } | |
| 731 sqlite3_finalize(pStmt); | |
| 732 if( rc==SQLITE_OK ){ | |
| 733 pCur->pCurrent = closureAvlFirst(pCur->pClosure); | |
| 734 } | |
| 735 | |
| 736 return rc; | |
| 737 } | |
| 738 | |
| 739 /* | |
| 740 ** Only the word and distance columns have values. All other columns | |
| 741 ** return NULL | |
| 742 */ | |
| 743 static int closureColumn(sqlite3_vtab_cursor *cur, sqlite3_context *ctx, int i){ | |
| 744 closure_cursor *pCur = (closure_cursor*)cur; | |
| 745 switch( i ){ | |
| 746 case CLOSURE_COL_ID: { | |
| 747 sqlite3_result_int64(ctx, pCur->pCurrent->id); | |
| 748 break; | |
| 749 } | |
| 750 case CLOSURE_COL_DEPTH: { | |
| 751 sqlite3_result_int(ctx, pCur->pCurrent->iGeneration); | |
| 752 break; | |
| 753 } | |
| 754 case CLOSURE_COL_ROOT: { | |
| 755 sqlite3_result_null(ctx); | |
| 756 break; | |
| 757 } | |
| 758 case CLOSURE_COL_TABLENAME: { | |
| 759 sqlite3_result_text(ctx, | |
| 760 pCur->zTableName ? pCur->zTableName : pCur->pVtab->zTableName, | |
| 761 -1, SQLITE_TRANSIENT); | |
| 762 break; | |
| 763 } | |
| 764 case CLOSURE_COL_IDCOLUMN: { | |
| 765 sqlite3_result_text(ctx, | |
| 766 pCur->zIdColumn ? pCur->zIdColumn : pCur->pVtab->zIdColumn, | |
| 767 -1, SQLITE_TRANSIENT); | |
| 768 break; | |
| 769 } | |
| 770 case CLOSURE_COL_PARENTCOLUMN: { | |
| 771 sqlite3_result_text(ctx, | |
| 772 pCur->zParentColumn ? pCur->zParentColumn : pCur->pVtab->zParentColumn, | |
| 773 -1, SQLITE_TRANSIENT); | |
| 774 break; | |
| 775 } | |
| 776 } | |
| 777 return SQLITE_OK; | |
| 778 } | |
| 779 | |
| 780 /* | |
| 781 ** The rowid. For the closure table, this is the same as the "id" column. | |
| 782 */ | |
| 783 static int closureRowid(sqlite3_vtab_cursor *cur, sqlite_int64 *pRowid){ | |
| 784 closure_cursor *pCur = (closure_cursor*)cur; | |
| 785 *pRowid = pCur->pCurrent->id; | |
| 786 return SQLITE_OK; | |
| 787 } | |
| 788 | |
| 789 /* | |
| 790 ** EOF indicator | |
| 791 */ | |
| 792 static int closureEof(sqlite3_vtab_cursor *cur){ | |
| 793 closure_cursor *pCur = (closure_cursor*)cur; | |
| 794 return pCur->pCurrent==0; | |
| 795 } | |
| 796 | |
| 797 /* | |
| 798 ** Search for terms of these forms: | |
| 799 ** | |
| 800 ** (A) root = $root | |
| 801 ** (B1) depth < $depth | |
| 802 ** (B2) depth <= $depth | |
| 803 ** (B3) depth = $depth | |
| 804 ** (C) tablename = $tablename | |
| 805 ** (D) idcolumn = $idcolumn | |
| 806 ** (E) parentcolumn = $parentcolumn | |
| 807 ** | |
| 808 ** | |
| 809 ** | |
| 810 ** idxNum meaning | |
| 811 ** ---------- ------------------------------------------------------ | |
| 812 ** 0x00000001 Term of the form (A) found | |
| 813 ** 0x00000002 The term of bit-2 is like (B1) | |
| 814 ** 0x000000f0 Index in filter.argv[] of $depth. 0 if not used. | |
| 815 ** 0x00000f00 Index in filter.argv[] of $tablename. 0 if not used. | |
| 816 ** 0x0000f000 Index in filter.argv[] of $idcolumn. 0 if not used | |
| 817 ** 0x000f0000 Index in filter.argv[] of $parentcolumn. 0 if not used. | |
| 818 ** | |
| 819 ** There must be a term of type (A). If there is not, then the index type | |
| 820 ** is 0 and the query will return an empty set. | |
| 821 */ | |
| 822 static int closureBestIndex( | |
| 823 sqlite3_vtab *pTab, /* The virtual table */ | |
| 824 sqlite3_index_info *pIdxInfo /* Information about the query */ | |
| 825 ){ | |
| 826 int iPlan = 0; | |
| 827 int i; | |
| 828 int idx = 1; | |
| 829 int seenMatch = 0; | |
| 830 const struct sqlite3_index_constraint *pConstraint; | |
| 831 closure_vtab *pVtab = (closure_vtab*)pTab; | |
| 832 double rCost = 10000000.0; | |
| 833 | |
| 834 pConstraint = pIdxInfo->aConstraint; | |
| 835 for(i=0; i<pIdxInfo->nConstraint; i++, pConstraint++){ | |
| 836 if( pConstraint->iColumn==CLOSURE_COL_ROOT | |
| 837 && pConstraint->op==SQLITE_INDEX_CONSTRAINT_EQ ){ | |
| 838 seenMatch = 1; | |
| 839 } | |
| 840 if( pConstraint->usable==0 ) continue; | |
| 841 if( (iPlan & 1)==0 | |
| 842 && pConstraint->iColumn==CLOSURE_COL_ROOT | |
| 843 && pConstraint->op==SQLITE_INDEX_CONSTRAINT_EQ | |
| 844 ){ | |
| 845 iPlan |= 1; | |
| 846 pIdxInfo->aConstraintUsage[i].argvIndex = 1; | |
| 847 pIdxInfo->aConstraintUsage[i].omit = 1; | |
| 848 rCost /= 100.0; | |
| 849 } | |
| 850 if( (iPlan & 0x0000f0)==0 | |
| 851 && pConstraint->iColumn==CLOSURE_COL_DEPTH | |
| 852 && (pConstraint->op==SQLITE_INDEX_CONSTRAINT_LT | |
| 853 || pConstraint->op==SQLITE_INDEX_CONSTRAINT_LE | |
| 854 || pConstraint->op==SQLITE_INDEX_CONSTRAINT_EQ) | |
| 855 ){ | |
| 856 iPlan |= idx<<4; | |
| 857 pIdxInfo->aConstraintUsage[i].argvIndex = ++idx; | |
| 858 if( pConstraint->op==SQLITE_INDEX_CONSTRAINT_LT ) iPlan |= 0x000002; | |
| 859 rCost /= 5.0; | |
| 860 } | |
| 861 if( (iPlan & 0x000f00)==0 | |
| 862 && pConstraint->iColumn==CLOSURE_COL_TABLENAME | |
| 863 && pConstraint->op==SQLITE_INDEX_CONSTRAINT_EQ | |
| 864 ){ | |
| 865 iPlan |= idx<<8; | |
| 866 pIdxInfo->aConstraintUsage[i].argvIndex = ++idx; | |
| 867 pIdxInfo->aConstraintUsage[i].omit = 1; | |
| 868 rCost /= 5.0; | |
| 869 } | |
| 870 if( (iPlan & 0x00f000)==0 | |
| 871 && pConstraint->iColumn==CLOSURE_COL_IDCOLUMN | |
| 872 && pConstraint->op==SQLITE_INDEX_CONSTRAINT_EQ | |
| 873 ){ | |
| 874 iPlan |= idx<<12; | |
| 875 pIdxInfo->aConstraintUsage[i].argvIndex = ++idx; | |
| 876 pIdxInfo->aConstraintUsage[i].omit = 1; | |
| 877 } | |
| 878 if( (iPlan & 0x0f0000)==0 | |
| 879 && pConstraint->iColumn==CLOSURE_COL_PARENTCOLUMN | |
| 880 && pConstraint->op==SQLITE_INDEX_CONSTRAINT_EQ | |
| 881 ){ | |
| 882 iPlan |= idx<<16; | |
| 883 pIdxInfo->aConstraintUsage[i].argvIndex = ++idx; | |
| 884 pIdxInfo->aConstraintUsage[i].omit = 1; | |
| 885 } | |
| 886 } | |
| 887 if( (pVtab->zTableName==0 && (iPlan & 0x000f00)==0) | |
| 888 || (pVtab->zIdColumn==0 && (iPlan & 0x00f000)==0) | |
| 889 || (pVtab->zParentColumn==0 && (iPlan & 0x0f0000)==0) | |
| 890 ){ | |
| 891 /* All of tablename, idcolumn, and parentcolumn must be specified | |
| 892 ** in either the CREATE VIRTUAL TABLE or in the WHERE clause constraints | |
| 893 ** or else the result is an empty set. */ | |
| 894 iPlan = 0; | |
| 895 } | |
| 896 pIdxInfo->idxNum = iPlan; | |
| 897 if( pIdxInfo->nOrderBy==1 | |
| 898 && pIdxInfo->aOrderBy[0].iColumn==CLOSURE_COL_ID | |
| 899 && pIdxInfo->aOrderBy[0].desc==0 | |
| 900 ){ | |
| 901 pIdxInfo->orderByConsumed = 1; | |
| 902 } | |
| 903 if( seenMatch && (iPlan&1)==0 ) rCost *= 1e30; | |
| 904 pIdxInfo->estimatedCost = rCost; | |
| 905 | |
| 906 return SQLITE_OK; | |
| 907 } | |
| 908 | |
| 909 /* | |
| 910 ** A virtual table module that implements the "transitive_closure". | |
| 911 */ | |
| 912 static sqlite3_module closureModule = { | |
| 913 0, /* iVersion */ | |
| 914 closureConnect, /* xCreate */ | |
| 915 closureConnect, /* xConnect */ | |
| 916 closureBestIndex, /* xBestIndex */ | |
| 917 closureDisconnect, /* xDisconnect */ | |
| 918 closureDisconnect, /* xDestroy */ | |
| 919 closureOpen, /* xOpen - open a cursor */ | |
| 920 closureClose, /* xClose - close a cursor */ | |
| 921 closureFilter, /* xFilter - configure scan constraints */ | |
| 922 closureNext, /* xNext - advance a cursor */ | |
| 923 closureEof, /* xEof - check for end of scan */ | |
| 924 closureColumn, /* xColumn - read data */ | |
| 925 closureRowid, /* xRowid - read data */ | |
| 926 0, /* xUpdate */ | |
| 927 0, /* xBegin */ | |
| 928 0, /* xSync */ | |
| 929 0, /* xCommit */ | |
| 930 0, /* xRollback */ | |
| 931 0, /* xFindMethod */ | |
| 932 0, /* xRename */ | |
| 933 0, /* xSavepoint */ | |
| 934 0, /* xRelease */ | |
| 935 0 /* xRollbackTo */ | |
| 936 }; | |
| 937 | |
| 938 #endif /* SQLITE_OMIT_VIRTUALTABLE */ | |
| 939 | |
| 940 /* | |
| 941 ** Register the closure virtual table | |
| 942 */ | |
| 943 #ifdef _WIN32 | |
| 944 __declspec(dllexport) | |
| 945 #endif | |
| 946 int sqlite3_closure_init( | |
| 947 sqlite3 *db, | |
| 948 char **pzErrMsg, | |
| 949 const sqlite3_api_routines *pApi | |
| 950 ){ | |
| 951 int rc = SQLITE_OK; | |
| 952 SQLITE_EXTENSION_INIT2(pApi); | |
| 953 (void)pzErrMsg; | |
| 954 #ifndef SQLITE_OMIT_VIRTUALTABLE | |
| 955 rc = sqlite3_create_module(db, "transitive_closure", &closureModule, 0); | |
| 956 #endif /* SQLITE_OMIT_VIRTUALTABLE */ | |
| 957 return rc; | |
| 958 } | |
| OLD | NEW |
|---|
Chromium Code Reviews
Issue 2363173002:
[sqlite] Remove obsolete reference version 3.8.7.4. (Closed)
