diff options
author | mdm@chromium.org <mdm@chromium.org@0039d316-1c4b-4281-b951-d872f2087c98> | 2009-09-18 18:27:25 +0000 |
---|---|---|
committer | mdm@chromium.org <mdm@chromium.org@0039d316-1c4b-4281-b951-d872f2087c98> | 2009-09-18 18:27:25 +0000 |
commit | 997e22224e1062a4cd39373057a68879a1d7a3ac (patch) | |
tree | a90a9ce4272fc78f2459b1b2c78b52a3f6d4e5d3 /third_party/sqlite/ext/rtree/rtree.c | |
parent | 0d683c611a18dc6ea0e99f38c73b4fb96611041f (diff) | |
download | chromium_src-997e22224e1062a4cd39373057a68879a1d7a3ac.zip chromium_src-997e22224e1062a4cd39373057a68879a1d7a3ac.tar.gz chromium_src-997e22224e1062a4cd39373057a68879a1d7a3ac.tar.bz2 |
Update sqlite to version 3.6.18, porting our patches.
Hopefully this will help to address some valgrind issues.
BUG=none
TEST=none
git-svn-id: svn://svn.chromium.org/chrome/trunk/src@26596 0039d316-1c4b-4281-b951-d872f2087c98
Diffstat (limited to 'third_party/sqlite/ext/rtree/rtree.c')
-rw-r--r-- | third_party/sqlite/ext/rtree/rtree.c | 61 |
1 files changed, 48 insertions, 13 deletions
diff --git a/third_party/sqlite/ext/rtree/rtree.c b/third_party/sqlite/ext/rtree/rtree.c index 39116ce..5a4f570 100644 --- a/third_party/sqlite/ext/rtree/rtree.c +++ b/third_party/sqlite/ext/rtree/rtree.c @@ -12,7 +12,7 @@ ** This file contains code for implementations of the r-tree and r*-tree ** algorithms packaged as an SQLite virtual table module. ** -** $Id: rtree.c,v 1.7 2008/07/16 14:43:35 drh Exp $ +** $Id: rtree.c,v 1.14 2009/08/06 18:36:47 danielk1977 Exp $ */ #if !defined(SQLITE_CORE) || defined(SQLITE_ENABLE_RTREE) @@ -226,8 +226,12 @@ struct RtreeCell { RtreeCoord aCoord[RTREE_MAX_DIMENSIONS*2]; }; -#define MAX(x,y) ((x) < (y) ? (y) : (x)) -#define MIN(x,y) ((x) > (y) ? (y) : (x)) +#ifndef MAX +# define MAX(x,y) ((x) < (y) ? (y) : (x)) +#endif +#ifndef MIN +# define MIN(x,y) ((x) > (y) ? (y) : (x)) +#endif /* ** Functions to deserialize a 16 bit integer, 32 bit real number and @@ -396,7 +400,8 @@ nodeAcquire( */ if( (pNode = nodeHashLookup(pRtree, iNode)) ){ assert( !pParent || !pNode->pParent || pNode->pParent==pParent ); - if( pParent ){ + if( pParent && !pNode->pParent ){ + nodeReference(pParent); pNode->pParent = pParent; } pNode->nRef++; @@ -600,7 +605,7 @@ static void nodeGetCell( ** the virtual table module xCreate() and xConnect() methods. */ static int rtreeInit( - sqlite3 *, void *, int, const char *const*, sqlite3_vtab **, char **, int, int + sqlite3 *, void *, int, const char *const*, sqlite3_vtab **, char **, int ); /* @@ -613,7 +618,7 @@ static int rtreeCreate( sqlite3_vtab **ppVtab, char **pzErr ){ - return rtreeInit(db, pAux, argc, argv, ppVtab, pzErr, 1, (int)pAux); + return rtreeInit(db, pAux, argc, argv, ppVtab, pzErr, 1); } /* @@ -626,7 +631,7 @@ static int rtreeConnect( sqlite3_vtab **ppVtab, char **pzErr ){ - return rtreeInit(db, pAux, argc, argv, ppVtab, pzErr, 0, (int)pAux); + return rtreeInit(db, pAux, argc, argv, ppVtab, pzErr, 0); } /* @@ -1116,6 +1121,13 @@ static int rtreeBestIndex(sqlite3_vtab *tab, sqlite3_index_info *pIdxInfo){ pIdxInfo->idxNum = 1; pIdxInfo->aConstraintUsage[ii].argvIndex = 1; pIdxInfo->aConstraintUsage[jj].omit = 1; + + /* This strategy involves a two rowid lookups on an B-Tree structures + ** and then a linear search of an R-Tree node. This should be + ** considered almost as quick as a direct rowid lookup (for which + ** sqlite uses an internal cost of 0.0). + */ + pIdxInfo->estimatedCost = 10.0; return SQLITE_OK; } @@ -1169,6 +1181,8 @@ static int rtreeBestIndex(sqlite3_vtab *tab, sqlite3_index_info *pIdxInfo){ if( iIdx>0 && 0==(pIdxInfo->idxStr = sqlite3_mprintf("%s", zIdxStr)) ){ return SQLITE_NOMEM; } + assert( iIdx>=0 ); + pIdxInfo->estimatedCost = (2000000.0 / (double)(iIdx + 1)); return rc; } @@ -1216,6 +1230,25 @@ static void cellUnion(Rtree *pRtree, RtreeCell *p1, RtreeCell *p2){ } /* +** Return true if the area covered by p2 is a subset of the area covered +** by p1. False otherwise. +*/ +static int cellContains(Rtree *pRtree, RtreeCell *p1, RtreeCell *p2){ + int ii; + int isInt = (pRtree->eCoordType==RTREE_COORD_INT32); + for(ii=0; ii<(pRtree->nDim*2); ii+=2){ + RtreeCoord *a1 = &p1->aCoord[ii]; + RtreeCoord *a2 = &p2->aCoord[ii]; + if( (!isInt && (a2[0].f<a1[0].f || a2[1].f>a1[1].f)) + || ( isInt && (a2[0].i<a1[0].i || a2[1].i>a1[1].i)) + ){ + return 0; + } + } + return 1; +} + +/* ** Return the amount cell p would grow by if it were unioned with pCell. */ static float cellGrowth(Rtree *pRtree, RtreeCell *p, RtreeCell *pCell){ @@ -1381,7 +1414,7 @@ static void AdjustTree( int iCell = nodeParentIndex(pRtree, p); nodeGetCell(pRtree, pParent, iCell, &cell); - if( cellGrowth(pRtree, &cell, pCell)>0.0 ){ + if( !cellContains(pRtree, &cell, pCell) ){ cellUnion(pRtree, &cell, pCell); nodeOverwriteCell(pRtree, pParent, &cell, iCell); } @@ -2309,7 +2342,7 @@ static int hashIsEmpty(Rtree *pRtree){ /* ** The xUpdate method for rtree module virtual tables. */ -int rtreeUpdate( +static int rtreeUpdate( sqlite3_vtab *pVtab, int nData, sqlite3_value **azData, @@ -2623,18 +2656,18 @@ static int getPageSize(sqlite3 *db, const char *zDb, int *piPageSize){ */ static int rtreeInit( sqlite3 *db, /* Database connection */ - void *pAux, /* Pointer to head of rtree list */ + void *pAux, /* One of the RTREE_COORD_* constants */ int argc, const char *const*argv, /* Parameters to CREATE TABLE statement */ sqlite3_vtab **ppVtab, /* OUT: New virtual table */ char **pzErr, /* OUT: Error message, if any */ - int isCreate, /* True for xCreate, false for xConnect */ - int eCoordType /* One of the RTREE_COORD_* constants */ + int isCreate /* True for xCreate, false for xConnect */ ){ int rc = SQLITE_OK; int iPageSize = 0; Rtree *pRtree; int nDb; /* Length of string argv[1] */ int nName; /* Length of string argv[2] */ + int eCoordType = (int)pAux; const char *aErrMsg[] = { 0, /* 0 */ @@ -2704,8 +2737,10 @@ static int rtreeInit( zSql = sqlite3_mprintf("%s);", zTmp); sqlite3_free(zTmp); } - if( !zSql || sqlite3_declare_vtab(db, zSql) ){ + if( !zSql ){ rc = SQLITE_NOMEM; + }else if( SQLITE_OK!=(rc = sqlite3_declare_vtab(db, zSql)) ){ + *pzErr = sqlite3_mprintf("%s", sqlite3_errmsg(db)); } sqlite3_free(zSql); } |