From 003533f7246b068635c94566ee631233d4d2e7ea Mon Sep 17 00:00:00 2001 From: dan Date: Thu, 27 Apr 2023 19:27:55 +0000 Subject: [PATCH] Dynamically resize the node hash table used by the rtree module. FossilOrigin-Name: f94f3da5de2b1085ea1967ca8961a923e79f5a1181b9507a2f4c9e29e47cbe29 --- ext/rtree/rtree.c | 61 +++++++++++++++++++++++++++++++++++++---------- manifest | 12 +++++----- manifest.uuid | 2 +- 3 files changed, 55 insertions(+), 20 deletions(-) diff --git a/ext/rtree/rtree.c b/ext/rtree/rtree.c index 102d0d08ab..93a88c06a3 100644 --- a/ext/rtree/rtree.c +++ b/ext/rtree/rtree.c @@ -124,11 +124,8 @@ typedef struct RtreeGlobal RtreeGlobal; /* Maximum number of auxiliary columns */ #define RTREE_MAX_AUX_COLUMN 100 -/* Size of hash table Rtree.aHash. This hash table is not expected to -** ever contain very many entries, so a fixed number of buckets is -** used. -*/ -#define HASHSIZE 97 +/* Initial size of hash table Rtree.aHash. */ +#define INITIAL_HASHSIZE 97 /* The xBestIndex method of this virtual table requires an estimate of ** the number of rows in the virtual table to calculate the costs of @@ -206,7 +203,9 @@ struct Rtree { /* Statement for writing to the "aux:" fields, if there are any */ sqlite3_stmt *pWriteAux; - RtreeNode *aHash[HASHSIZE]; /* Hash table of in-memory nodes. */ + int nHashSize; /* Number of hash buckets */ + int nHashEntry; /* Number of entries in hash table */ + RtreeNode **aHash; /* Hash table of in-memory nodes. */ RtreeGlobal *pGlobal; /* Database-wide object */ Rtree *pGlobalNext; /* Next in RtreeGlobal.pGlobalNext */ @@ -643,8 +642,8 @@ static void nodeZero(Rtree *pRtree, RtreeNode *p){ ** Given a node number iNode, return the corresponding key to use ** in the Rtree.aHash table. */ -static unsigned int nodeHash(i64 iNode){ - return ((unsigned)iNode) % HASHSIZE; +static unsigned int nodeHash(Rtree *pRtree, i64 iNode){ + return ((unsigned)iNode) % pRtree->nHashSize; } /* @@ -653,7 +652,7 @@ static unsigned int nodeHash(i64 iNode){ */ static RtreeNode *nodeHashLookup(Rtree *pRtree, i64 iNode){ RtreeNode *p; - for(p=pRtree->aHash[nodeHash(iNode)]; p && p->iNode!=iNode; p=p->pNext); + for(p=pRtree->aHash[nodeHash(pRtree, iNode)]; p&&p->iNode!=iNode; p=p->pNext); return p; } @@ -665,9 +664,33 @@ static void nodeHashInsert(Rtree *pRtree, RtreeNode *pNode){ assert( pNode->pNext==0 ); assert( pNode->pParent==0 || pNode->nRef>0 ); assert( pNode->bDel==0 ); - iHash = nodeHash(pNode->iNode); + + if( pRtree->nHashEntry>pRtree->nHashSize ){ + int nNew = pRtree->nHashSize * 2; + RtreeNode **aNew = (RtreeNode**)sqlite3_malloc64(sizeof(RtreeNode*)*nNew); + if( aNew ){ + int ii; + memset(aNew, 0, sizeof(RtreeNode*)*nNew); + for(ii=0; iinHashSize; ii++){ + RtreeNode *p, *pNext; + for(p=pRtree->aHash[ii]; p; p=pNext){ + int iBucket = p->iNode % nNew; + pNext = p->pNext; + p->pNext = aNew[iBucket]; + aNew[iBucket] = p; + } + } + + sqlite3_free(pRtree->aHash); + pRtree->aHash = aNew; + pRtree->nHashSize = nNew; + } + } + + iHash = nodeHash(pRtree, pNode->iNode); pNode->pNext = pRtree->aHash[iHash]; pRtree->aHash[iHash] = pNode; + pRtree->nHashEntry++; } /* @@ -676,10 +699,11 @@ static void nodeHashInsert(Rtree *pRtree, RtreeNode *pNode){ static void nodeHashDelete(Rtree *pRtree, RtreeNode *pNode){ RtreeNode **pp; if( pNode->iNode!=0 ){ - pp = &pRtree->aHash[nodeHash(pNode->iNode)]; + pp = &pRtree->aHash[nodeHash(pRtree, pNode->iNode)]; for( ; (*pp)!=pNode; pp = &(*pp)->pNext){ assert(*pp); } *pp = pNode->pNext; pNode->pNext = 0; + pRtree->nHashEntry--; } } @@ -928,7 +952,7 @@ static int rtreeFlushCache(Rtree *pRtree){ int i; int rc = SQLITE_OK; i64 iLIR = sqlite3_last_insert_rowid(pRtree->db); - for(i=0; inHashSize && rc==SQLITE_OK; i++){ RtreeNode *pNode; for(pNode=pRtree->aHash[i]; pNode; pNode=pNode->pNext){ if( pNode->isDirty ){ @@ -948,7 +972,7 @@ static int rtreeFlushCache(Rtree *pRtree){ static int rtreeResetHashTable(Rtree *pRtree, int writeDirty){ int i; int rc = SQLITE_OK; - for(i=0; inHashSize; i++){ RtreeNode *pNode = pRtree->aHash[i]; RtreeNode *pNext; if( pNode==0 ) continue; @@ -969,6 +993,7 @@ static int rtreeResetHashTable(Rtree *pRtree, int writeDirty){ } pRtree->aHash[i] = 0; } + pRtree->nHashEntry = 0; return rc; } @@ -1120,6 +1145,7 @@ static void rtreeRelease(Rtree *pRtree){ sqlite3_finalize(pRtree->pDeleteParent); sqlite3_finalize(pRtree->pWriteAux); sqlite3_free(pRtree->zReadAuxSql); + sqlite3_free(pRtree->aHash); /* Remove this object from the global list. */ if( pRtree->pGlobal ){ @@ -3923,6 +3949,15 @@ static int rtreeInit( memcpy(pRtree->zDb, argv[1], nDb); memcpy(pRtree->zName, argv[2], nName); + pRtree->aHash = (RtreeNode**)sqlite3_malloc64( + sizeof(RtreeNode*) * INITIAL_HASHSIZE + ); + if( pRtree->aHash==0 ){ + rc = SQLITE_NOMEM; + goto rtreeInit_fail; + } + memset(pRtree->aHash, 0, sizeof(RtreeNode*)*INITIAL_HASHSIZE); + pRtree->nHashSize = INITIAL_HASHSIZE; /* Create/Connect to the underlying relational database schema. If ** that is successful, call sqlite3_declare_vtab() to configure diff --git a/manifest b/manifest index 22e19da45e..5450a2447e 100644 --- a/manifest +++ b/manifest @@ -1,5 +1,5 @@ -C Fix\ssome\sproblems\swith\sthe\srtree\smodule\sand\sexisting\stests\son\sthis\sbranch. -D 2023-04-26T20:41:00.885 +C Dynamically\sresize\sthe\snode\shash\stable\sused\sby\sthe\srtree\smodule. +D 2023-04-27T19:27:55.114 F .fossil-settings/empty-dirs dbb81e8fc0401ac46a1491ab34a7f2c7c0452f2f06b54ebb845d024ca8283ef1 F .fossil-settings/ignore-glob 35175cdfcf539b2318cb04a9901442804be81cd677d8b889fcc9149c21f239ea F LICENSE.md df5091916dbb40e6e9686186587125e1b2ff51f022cc334e886c19a0e9982724 @@ -400,7 +400,7 @@ F ext/repair/test/checkindex01.test b530f141413b587c9eb78ff734de6bb79bc3515c3350 F ext/repair/test/test.tcl 686d76d888dffd021f64260abf29a55c57b2cedfa7fc69150b42b1d6119aac3c F ext/rtree/README 6315c0d73ebf0ec40dedb5aa0e942bc8b54e3761 F ext/rtree/geopoly.c 398b966772d81b9e6cd05caaf94f5d9d38b26f4245d4f0908b41c60024298412 -F ext/rtree/rtree.c 862d2aaac6dfc4f4b03f45e94ab4728f35daf27da0ef88b457a938acda3dd663 +F ext/rtree/rtree.c 92def73e587b2daaff1c8b2c50c5ca0c0e543222f4d0e926ce0479454bd2b673 F ext/rtree/rtree.h 4a690463901cb5e6127cf05eb8e642f127012fd5003830dbc974eca5802d9412 F ext/rtree/rtree1.test 96271886cb39b680ed8c0a8dc0dd341e52a368bbd54d461a433e7aecd0556a2a F ext/rtree/rtree2.test 9d9deddbb16fd0c30c36e6b4fdc3ee3132d765567f0f9432ee71e1303d32603d @@ -2059,8 +2059,8 @@ F vsixtest/vsixtest.tcl 6a9a6ab600c25a91a7acc6293828957a386a8a93 F vsixtest/vsixtest.vcxproj.data 2ed517e100c66dc455b492e1a33350c1b20fbcdc F vsixtest/vsixtest.vcxproj.filters 37e51ffedcdb064aad6ff33b6148725226cd608e F vsixtest/vsixtest_TemporaryKey.pfx e5b1b036facdb453873e7084e1cae9102ccc67a0 -P b35cb7458fe16390f3b1f0b2acfd3d51fabd6bf9c5f176a44d8b3cc932f74149 -R b6b76068a047066e137cc4bd01872ea2 +P 50e8a30be1a8d4af42a2c58bdffcf3c4eae00450f0bb9ec39548d5a52d2a68ee +R ef7db804b2d3b6c0c526bc82af548b3d U dan -Z ce5901679438646e425be2a25d931a5b +Z 41e485964a37c8d7a0bf6a892dd19281 # Remove this line to create a well-formed Fossil manifest. diff --git a/manifest.uuid b/manifest.uuid index 1d1b06cc9a..c551d9fae0 100644 --- a/manifest.uuid +++ b/manifest.uuid @@ -1 +1 @@ -50e8a30be1a8d4af42a2c58bdffcf3c4eae00450f0bb9ec39548d5a52d2a68ee \ No newline at end of file +f94f3da5de2b1085ea1967ca8961a923e79f5a1181b9507a2f4c9e29e47cbe29 \ No newline at end of file -- 2.39.5