From c686929914188d138527dcf460c025ef4b3638e9 Mon Sep 17 00:00:00 2001 From: drh Date: Fri, 25 Apr 2014 16:29:03 +0000 Subject: [PATCH] Enhance the sqlite3_rtree_query_info object to report on the number of elements in the priority queue at each level. FossilOrigin-Name: f7dad408dd46a1e3612b6142a3afb1d0d4fcda00 --- ext/rtree/rtree.c | 20 ++++++++++++++------ ext/rtree/sqlite3rtree.h | 2 ++ manifest | 14 +++++++------- manifest.uuid | 2 +- 4 files changed, 24 insertions(+), 14 deletions(-) diff --git a/ext/rtree/rtree.c b/ext/rtree/rtree.c index a6c99cb9ee..7b540b4be1 100644 --- a/ext/rtree/rtree.c +++ b/ext/rtree/rtree.c @@ -228,9 +228,11 @@ struct RtreeCursor { RtreeConstraint *aConstraint; /* Search constraints. */ int nPointAlloc; /* Number of slots allocated for aPoint[] */ int nPoint; /* Number of slots used in aPoint[] */ + int mxLevel; /* iLevel value for root of the tree */ RtreeSearchPoint *aPoint; /* Priority queue for search points */ RtreeSearchPoint sPoint; /* Cached next search point */ RtreeNode *aNode[RTREE_CACHE_SZ]; /* Rtree node cache */ + u32 anQueue[RTREE_MAX_DEPTH+1]; /* Number of queued entries by iLevel */ }; /* Return the Rtree of a RtreeCursor */ @@ -1179,7 +1181,8 @@ static RtreeSearchPoint *rtreeEnqueue( i = pCur->nPoint++; pNew = pCur->aPoint + i; pNew->rScore = rScore; - pNew->iLevel = iLevel; + pNew->iLevel = iLevel; + assert( iLevel>=0 && iLevel<=RTREE_MAX_DEPTH ); while( i>0 ){ RtreeSearchPoint *pParent; j = (i-1)/2; @@ -1203,6 +1206,7 @@ static RtreeSearchPoint *rtreeSearchPointNew( ){ RtreeSearchPoint *pNew, *pFirst; pFirst = rtreeSearchPointFirst(pCur); + pCur->anQueue[iLevel]++; if( pFirst==0 || pFirst->rScore>rScore || (pFirst->rScore==rScore && pFirst->iLevel>iLevel) @@ -1271,8 +1275,10 @@ static void rtreeSearchPointPop(RtreeCursor *p){ p->aNode[i] = 0; } if( p->bPoint ){ + p->anQueue[p->sPoint.iLevel]--; p->bPoint = 0; }else if( p->nPoint ){ + p->anQueue[p->aPoint[0].iLevel]--; n = --p->nPoint; p->aPoint[0] = p->aPoint[n]; if( n0 ){ + rc = nodeAcquire(pRtree, 1, 0, &pRoot); + if( rc==SQLITE_OK && argc>0 ){ pCsr->aConstraint = sqlite3_malloc(sizeof(RtreeConstraint)*argc); pCsr->nConstraint = argc; if( !pCsr->aConstraint ){ rc = SQLITE_NOMEM; }else{ memset(pCsr->aConstraint, 0, sizeof(RtreeConstraint)*argc); + memset(pCsr->anQueue, 0, sizeof(u32)*(pRtree->iDepth + 1)); assert( (idxStr==0 && argc==0) || (idxStr && (int)strlen(idxStr)==argc*2) ); for(ii=0; iipInfo->nCoord = pRtree->nDim*2; + p->pInfo->anQueue = pCsr->anQueue; + p->pInfo->mxLevel = pRtree->iDepth + 1; }else{ #ifdef SQLITE_RTREE_INT_ONLY p->u.rValue = sqlite3_value_int64(argv[ii]); @@ -1586,10 +1596,6 @@ static int rtreeFilter( } } } - - if( rc==SQLITE_OK ){ - rc = nodeAcquire(pRtree, 1, 0, &pRoot); - } if( rc==SQLITE_OK ){ RtreeSearchPoint *pNew; pNew = rtreeSearchPointNew(pCsr, RTREE_ZERO, pRtree->iDepth+1); @@ -1599,11 +1605,13 @@ static int rtreeFilter( pNew->eWithin = PARTLY_WITHIN; assert( pCsr->bPoint==1 ); pCsr->aNode[0] = pRoot; + pRoot = 0; RTREE_QUEUE_TRACE(pCsr, "PUSH-Fm:"); rc = rtreeStepToLeaf(pCsr); } } + nodeRelease(pRtree, pRoot); rtreeRelease(pRtree); return rc; } diff --git a/ext/rtree/sqlite3rtree.h b/ext/rtree/sqlite3rtree.h index 3f4df4ed89..5de0508d00 100644 --- a/ext/rtree/sqlite3rtree.h +++ b/ext/rtree/sqlite3rtree.h @@ -89,8 +89,10 @@ struct sqlite3_rtree_query_info { void *pUser; /* callback can use this, if desired */ void (*xDelUser)(void*); /* function to free pUser */ sqlite3_rtree_dbl *aCoord; /* Coordinates of node or entry to check */ + unsigned int *anQueue; /* Number of pending entries in the queue */ int nCoord; /* Number of coordinates */ int iLevel; /* Level of current node or entry */ + int mxLevel; /* The largest iLevel value in the tree */ sqlite3_int64 iRowid; /* Rowid for current entry */ sqlite3_rtree_dbl rParentScore; /* Score of parent node */ int eParentWithin; /* Visibility of parent node */ diff --git a/manifest b/manifest index a115e0886e..707f14a0a3 100644 --- a/manifest +++ b/manifest @@ -1,5 +1,5 @@ -C Fix\sthe\sgeneration\sof\ssqlite3_rtree_query_info.iRowid\sand\sadd\stest\scases\nto\sverify\sthat\sit\sis\sfixed. -D 2014-04-21T18:13:37.363 +C Enhance\sthe\ssqlite3_rtree_query_info\sobject\sto\sreport\son\sthe\snumber\sof\s\nelements\sin\sthe\spriority\squeue\sat\seach\slevel. +D 2014-04-25T16:29:03.796 F Makefile.arm-wince-mingw32ce-gcc d6df77f1f48d690bd73162294bbba7f59507c72f F Makefile.in e4ee6d36cdf6136aee0158675a3b24dd3bf31a5a F Makefile.linux-gcc 91d710bdc4998cb015f39edf3cb314ec4f4d7e23 @@ -120,7 +120,7 @@ F ext/misc/vfslog.c fe40fab5c077a40477f7e5eba994309ecac6cc95 F ext/misc/vtshim.c babb0dc2bf116029e3e7c9a618b8a1377045303e F ext/misc/wholenumber.c 784b12543d60702ebdd47da936e278aa03076212 F ext/rtree/README 6315c0d73ebf0ec40dedb5aa0e942bc8b54e3761 -F ext/rtree/rtree.c 77fdd459e7edf78a385a83930e2b072b2f0131b5 +F ext/rtree/rtree.c 6f70db93e0e42c369325c5cddcf2024c5a87ca43 F ext/rtree/rtree.h 834dbcb82dc85b2481cde6a07cdadfddc99e9b9e F ext/rtree/rtree1.test e2da4aaa426918d27122d1a1066c6ecf8409a514 F ext/rtree/rtree2.test acbb3a4ce0f4fbc2c304d2b4b784cfa161856bba @@ -138,7 +138,7 @@ F ext/rtree/rtreeD.test 636630357638f5983701550b37f0f5867130d2ca F ext/rtree/rtreeE.test 388c1c8602c3ce55c15f03b509e9cf545fb7c41f F ext/rtree/rtree_perf.tcl 6c18c1f23cd48e0f948930c98dfdd37dfccb5195 F ext/rtree/rtree_util.tcl 06aab2ed5b826545bf215fff90ecb9255a8647ea -F ext/rtree/sqlite3rtree.h 488cf8834d2012b913d33683157d3cf5f1327a69 +F ext/rtree/sqlite3rtree.h 83349d519fe5f518b3ea025d18dd1fe51b1684bd F ext/rtree/tkt3363.test 142ab96eded44a3615ec79fba98c7bde7d0f96de F ext/rtree/viewrtree.tcl eea6224b3553599ae665b239bd827e182b466024 F ext/session/session1.test 894e3bc9f497c4fa07a2aa3271e3911f3670c3d8 @@ -1177,7 +1177,7 @@ F tool/vdbe_profile.tcl 67746953071a9f8f2f668b73fe899074e2c6d8c1 F tool/warnings-clang.sh f6aa929dc20ef1f856af04a730772f59283631d4 F tool/warnings.sh d1a6de74685f360ab718efda6265994b99bbea01 F tool/win/sqlite.vsix 030f3eeaf2cb811a3692ab9c14d021a75ce41fff -P 4394693882c04c19ebe87ef7547c57e679554397 -R 9a6527f0d42b13ef1dcd87b1f989aba6 +P eba95ead49f8f8ce45d400186562ff0066537c5c +R efef19137bd31aa6c6fdc7dea3b8daf2 U drh -Z 8819b772d7d2f245af8d8a9675d9c9d8 +Z ded30c2c8b9ed7281fad6af13254832e diff --git a/manifest.uuid b/manifest.uuid index d92fc37198..8909227722 100644 --- a/manifest.uuid +++ b/manifest.uuid @@ -1 +1 @@ -eba95ead49f8f8ce45d400186562ff0066537c5c \ No newline at end of file +f7dad408dd46a1e3612b6142a3afb1d0d4fcda00 \ No newline at end of file -- 2.39.5