From 1b26c7ccfaad54b045056f0863212ce67ecca643 Mon Sep 17 00:00:00 2001 From: drh Date: Wed, 22 Apr 2009 02:15:47 +0000 Subject: [PATCH] Remove the rowhash object from the code. Rowset now fills its role. (CVS 6535) FossilOrigin-Name: e963bed0fe3ce5fa32f04b930e5ed0956dc2aa47 --- Makefile.in | 6 +- main.mk | 3 +- manifest | 29 ++-- manifest.uuid | 2 +- src/rowhash.c | 390 -------------------------------------------- src/sqliteInt.h | 13 +- src/vdbe.c | 24 +-- src/vdbeInt.h | 4 +- src/vdbeaux.c | 5 +- src/vdbemem.c | 7 +- src/where.c | 49 +++--- tool/mksqlite3c.tcl | 1 - 12 files changed, 61 insertions(+), 472 deletions(-) delete mode 100644 src/rowhash.c diff --git a/Makefile.in b/Makefile.in index 1e73af6ddd..debe2f16dc 100644 --- a/Makefile.in +++ b/Makefile.in @@ -172,7 +172,7 @@ OBJS0 = alter.lo analyze.lo attach.lo auth.lo backup.lo bitvec.lo btmutex.lo \ mutex.lo mutex_noop.lo mutex_os2.lo mutex_unix.lo mutex_w32.lo \ notify.lo opcodes.lo os.lo os_unix.lo os_win.lo os_os2.lo \ pager.lo parse.lo pcache.lo pcache1.lo pragma.lo prepare.lo printf.lo \ - random.lo resolve.lo rowhash.lo rowset.lo select.lo status.lo \ + random.lo resolve.lo rowset.lo select.lo status.lo \ table.lo tokenize.lo trigger.lo update.lo \ util.lo vacuum.lo \ vdbe.lo vdbeapi.lo vdbeaux.lo vdbeblob.lo vdbemem.lo \ @@ -249,7 +249,6 @@ SRC = \ $(TOP)/src/printf.c \ $(TOP)/src/random.c \ $(TOP)/src/resolve.c \ - $(TOP)/src/rowhash.c \ $(TOP)/src/rowset.c \ $(TOP)/src/select.c \ $(TOP)/src/status.c \ @@ -672,9 +671,6 @@ random.lo: $(TOP)/src/random.c $(HDR) resolve.lo: $(TOP)/src/resolve.c $(HDR) $(LTCOMPILE) $(TEMP_STORE) -c $(TOP)/src/resolve.c -rowhash.lo: $(TOP)/src/rowhash.c $(HDR) - $(LTCOMPILE) $(TEMP_STORE) -c $(TOP)/src/rowhash.c - rowset.lo: $(TOP)/src/rowset.c $(HDR) $(LTCOMPILE) $(TEMP_STORE) -c $(TOP)/src/rowset.c diff --git a/main.mk b/main.mk index 439fac682b..718ba49a8b 100644 --- a/main.mk +++ b/main.mk @@ -61,7 +61,7 @@ LIBOBJ+= alter.o analyze.o attach.o auth.o \ mutex.o mutex_noop.o mutex_os2.o mutex_unix.o mutex_w32.o \ notify.o opcodes.o os.o os_os2.o os_unix.o os_win.o \ pager.o parse.o pcache.o pcache1.o pragma.o prepare.o printf.o \ - random.o resolve.o rowhash.o rowset.o rtree.o select.o status.o \ + random.o resolve.o rowset.o rtree.o select.o status.o \ table.o tokenize.o trigger.o \ update.o util.o vacuum.o \ vdbe.o vdbeapi.o vdbeaux.o vdbeblob.o vdbemem.o \ @@ -130,7 +130,6 @@ SRC = \ $(TOP)/src/printf.c \ $(TOP)/src/random.c \ $(TOP)/src/resolve.c \ - $(TOP)/src/rowhash.c \ $(TOP)/src/rowset.c \ $(TOP)/src/select.c \ $(TOP)/src/status.c \ diff --git a/manifest b/manifest index a374f13dd6..6d41c9a92e 100644 --- a/manifest +++ b/manifest @@ -1,7 +1,7 @@ -C Extend\sthe\sRowset\sobject\sto\scontain\sall\sthe\scapabilities\sof\sRowhash\sin\naddition\sto\sits\slegacy\scapabilities.\s\sUse\sRowset\sto\sreplace\sRowhash.\nIn\saddition\sto\srequiring\sless\scode,\sThis\sremoves\sthe\s2^32\sresult\srow\nlimitation,\suses\sless\smemory,\sand\sgives\sbetter\sbounds\son\sworst-case\nperformance.\s\sThe\sRowhash\simplementation\shas\syet\sto\sbe\sremoved.\s(CVS\s6534) -D 2009-04-22T00:47:01 +C Remove\sthe\srowhash\sobject\sfrom\sthe\scode.\s\sRowset\snow\sfills\sits\srole.\s(CVS\s6535) +D 2009-04-22T02:15:48 F Makefile.arm-wince-mingw32ce-gcc fcd5e9cd67fe88836360bb4f9ef4cb7f8e2fb5a0 -F Makefile.in fa5998fe08bd8c0fdc7f9f66cea16c0279f39da8 +F Makefile.in 583e87706abc3026960ed759aff6371faf84c211 F Makefile.linux-gcc d53183f4aa6a9192d249731c90dbdffbd2c68654 F Makefile.vxworks 40c707b2589f61436b89788003b1ccf5679ec3e6 F README b974cdc3f9f12b87e851b04e75996d720ebf81ac @@ -83,7 +83,7 @@ F ext/rtree/tkt3363.test 6662237ea75bb431cd5d262dfc9535e1023315fc F ext/rtree/viewrtree.tcl 09526398dae87a5a87c5aac2b3854dbaf8376869 F install-sh 9d4de14ab9fb0facae2f48780b874848cbf2f895 F ltmain.sh 3ff0879076df340d2e23ae905484d8c15d5fdea8 -F main.mk aeaf069e8ec8238ccfab5bdc4219149b16a3ee04 +F main.mk bbb170882a34fe51dbd2d2e9c450c6cc0dad3325 F mkdll.sh 7d09b23c05d56532e9d44a50868eb4b12ff4f74a F mkextu.sh 416f9b7089d80e5590a29692c9d9280a10dbad9f F mkextw.sh 4123480947681d9b434a5e7b1ee08135abe409ac @@ -154,13 +154,12 @@ F src/prepare.c 72d74e6d3b9c8eb0663b33ec6438aa718096ac79 F src/printf.c ea2d76000cc5f4579d7e9cb2f5460433eec0d384 F src/random.c 676b9d7ac820fe81e6fb2394ac8c10cff7f38628 F src/resolve.c 094e44450371fb27869eb8bf679aacbe51fdc56d -F src/rowhash.c 05179a59fda8494dff033fba16bf653ead96ab37 F src/rowset.c ee0f774f20bf3fd27470603d2d56d1767bbe1013 F src/select.c 35225756c247484f473678e5bd191d70a6e4dba0 F src/shell.c 0a11f831603f17fea20ca97133c0f64e716af4a7 F src/sqlite.h.in 8e0e256079bac2319380bdfebf403fcbe630510f F src/sqlite3ext.h 1db7d63ab5de4b3e6b83dd03d1a4e64fef6d2a17 -F src/sqliteInt.h 7522dc01d59a4e54a01b044c66e21cc6276b03f7 +F src/sqliteInt.h dc64bc8198a2ad3532a996fcecda71ff89a578f0 F src/sqliteLimit.h ffe93f5a0c4e7bd13e70cd7bf84cfb5c3465f45d F src/status.c 237b193efae0cf6ac3f0817a208de6c6c6ef6d76 F src/table.c cc86ad3d6ad54df7c63a3e807b5783c90411a08d @@ -201,16 +200,16 @@ F src/update.c 8ededddcde6f7b6da981dd0429a5d34518a475b7 F src/utf.c 9541d28f40441812c0b40f00334372a0542c00ff F src/util.c 828c552a22a1d5b650b8a5ea0009546715c45d93 F src/vacuum.c 07121a727beeee88f27d704a00313ad6a7c9bef0 -F src/vdbe.c cbef2e1fd232206136cfd94abba0cc64172214f9 +F src/vdbe.c 13f976672cd9d7fce04f9847d74da8c3b869a013 F src/vdbe.h 35a648bc3279a120da24f34d9a25213ec15daf8a -F src/vdbeInt.h d3adfeccc750643ae7861f2d29f579d3dad28785 +F src/vdbeInt.h 8726f7b4e3b55c8acf6d304a5b5f727ac1b6c5ab F src/vdbeapi.c 015c9d0fb7047657a13a7bb6aa886f75e43db02d -F src/vdbeaux.c 8b2ecd0ed6fb7e2113c33618ea37f2abafd97717 +F src/vdbeaux.c fdad66c73adb1c6ca6a0cd7a0f9517e5df758122 F src/vdbeblob.c e67757450ae8581a8b354d9d7e467e41502dfe38 -F src/vdbemem.c 96e57468036638c3de72e2ed8b08f308c5982053 +F src/vdbemem.c 111d8193859d16aefd5d3cb57472808584ea5503 F src/vtab.c 6118d71c5137e20a7ac51fb5d9beb0361fbedb89 F src/walker.c 7cdf63223c953d4343c6833e940f110281a378ee -F src/where.c 894363060378c1828eccd99a36f71e2b81870f1f +F src/where.c 48f711d293486b43bf87ab3d1eeeebae50cb6839 F test/aggerror.test a867e273ef9e3d7919f03ef4f0e8c0d2767944f2 F test/alias.test 597662c5d777a122f9a3df0047ea5c5bd383a911 F test/all.test 14165b3e32715b700b5f0cbf8f6e3833dda0be45 @@ -707,7 +706,7 @@ F tool/lempar.c aeba88b8566ff66f8a67c96b3eb2dd95e7d8908d F tool/mkkeywordhash.c 8e57fbe8c4fe2f1800f9190fd361231cb8558407 F tool/mkopts.tcl 66ac10d240cc6e86abd37dc908d50382f84ff46e x F tool/mkspeedsql.tcl a1a334d288f7adfe6e996f2e712becf076745c97 -F tool/mksqlite3c.tcl 2b34be291baff0fdfeb37a970b51cd7ff9891c2a +F tool/mksqlite3c.tcl 671833bd775e76ebd922b9e82c2508a344562511 F tool/mksqlite3internalh.tcl 7b43894e21bcb1bb39e11547ce7e38a063357e87 F tool/omittest.tcl 27d6f6e3b1e95aeb26a1c140e6eb57771c6d794a F tool/opcodeDoc.awk b3a2a3d5d3075b8bd90b7afe24283efdd586659c @@ -721,7 +720,7 @@ F tool/speedtest16.c c8a9c793df96db7e4933f0852abb7a03d48f2e81 F tool/speedtest2.tcl ee2149167303ba8e95af97873c575c3e0fab58ff F tool/speedtest8.c 2902c46588c40b55661e471d7a86e4dd71a18224 F tool/speedtest8inst1.c 293327bc76823f473684d589a8160bde1f52c14e -P 799d31d99fd18a6f99862433384e37d6747ee5b3 -R 1ce70fdfa14fdba2ade8fa79758df61c +P b101cf70b75c9772aaf50e0eadd0cfa37c84d193 +R 4b293c104cb64e8cb94e481dce760f86 U drh -Z c3b824b2829f5e843646dc0fa08d702e +Z 77e80e656a1a39cdd643ee53416f4c84 diff --git a/manifest.uuid b/manifest.uuid index fb5d86070e..371a0e4cdf 100644 --- a/manifest.uuid +++ b/manifest.uuid @@ -1 +1 @@ -b101cf70b75c9772aaf50e0eadd0cfa37c84d193 \ No newline at end of file +e963bed0fe3ce5fa32f04b930e5ed0956dc2aa47 \ No newline at end of file diff --git a/src/rowhash.c b/src/rowhash.c deleted file mode 100644 index 50559e6d8c..0000000000 --- a/src/rowhash.c +++ /dev/null @@ -1,390 +0,0 @@ -/* -** 2009 April 15 -** -** The author disclaims copyright to this source code. In place of -** a legal notice, here is a blessing: -** -** May you do good and not evil. -** May you find forgiveness for yourself and forgive others. -** May you share freely, never taking more than you give. -** -************************************************************************* -** -** This file contains the implementation of the RowHash data structure. -** A RowHash has the following properties: -** -** * A RowHash stores an unordered "bag" of 64-bit integer rowids. -** There is no other content. -** -** * Primative operations are CREATE, INSERT, TEST, and DESTROY. -** There is no way to remove individual elements from the RowHash -** once they are inserted. -** -** * INSERT operations are batched. TEST operation will ignore -** elements in the current INSERT batch. Only elements inserted -** in prior batches will be seen by a TEST. -** -** The insert batch number is a parameter to the TEST primitive. The -** hash table is rebuilt whenever the batch number increases. TEST -** operations only look for INSERTs that occurred in prior batches. -** -** The caller is responsible for insuring that there are no duplicate -** INSERTs. -** -** $Id: rowhash.c,v 1.5 2009/04/22 00:47:01 drh Exp $ -*/ -#include "sqliteInt.h" - -/* -** An upper bound on the size of heap allocations made by this module. -** Limiting the size of allocations helps to avoid memory fragmentation. -*/ -#define ROWHASH_ALLOCATION 1024 - -/* -** If there are less than this number of elements in the RowHash, do not -** bother building a hash-table. Just do a linear search. -*/ -#define ROWHASH_LINEAR_SEARCH_LIMIT 10 - -/* -** This value is what we want the average length of the collision hash -** chain to be. -*/ -#define ROWHASH_COLLISION_LENGTH 3 - - -/* Forward references to data structures. */ -typedef struct RowHashElem RowHashElem; -typedef struct RowHashBlock RowHashBlock; -typedef union RowHashPtr RowHashPtr; -typedef struct RowHashPage RowHashPage; - -/* -** Number of elements in the RowHashBlock.aElem[] array. This array is -** sized to make RowHashBlock very close to (without exceeding) -** ROWHASH_ALLOCATION bytes in size. -*/ -#define ROWHASH_ELEM_PER_BLOCK ( \ - (ROWHASH_ALLOCATION - ROUND8(sizeof(struct RowHashBlockData))) / \ - sizeof(RowHashElem) \ -) - -/* -** Number of pointers that fit into a single allocation of -** ROWHASH_ALLOCATION bytes. -*/ -#define ROWHASH_POINTER_PER_PAGE (ROWHASH_ALLOCATION/sizeof(RowHashPtr)) - -/* -** A page of pointers used to construct a hash table. -** -** The hash table is actually a tree composed of instances of this -** object. Leaves of the tree use the a[].pElem pointer to point -** to RowHashElem entries. Interior nodes of the tree use the -** a[].pPage element to point to subpages. -** -** The hash table is split into a tree in order to avoid having -** to make large memory allocations, since large allocations can -** result in unwanted memory fragmentation. -*/ -struct RowHashPage { - union RowHashPtr { - RowHashPage *pPage; /* Used by interior nodes. Pointer to subtree. */ - RowHashElem *pElem; /* Used by leaves. Pointer to hash entry. */ - } a[ROWHASH_POINTER_PER_PAGE]; -}; - -/* -** Each 64-bit integer in a RowHash is stored as an instance of -** this object. -** -** Instances of this object are not allocated separately. They are -** allocated in large blocks using the RowHashBlock object as a container. -*/ -struct RowHashElem { - i64 iVal; /* The value being stored. A rowid. */ - RowHashElem *pNext; /* Next element with the same hash */ -}; - -/* -** In order to avoid many small allocations of RowHashElem objects, -** multiple RowHashElem objects are allocated at once, as an instance -** of this object, and then used as needed. -** -** A single RowHash object will allocate one or more of these RowHashBlock -** objects. As many are allocated as are needed to store all of the -** content. All RowHashBlocks are kept on a linked list formed using -** RowHashBlock.data.pNext so that they can be freed when the RowHash -** is destroyed. -** -** The linked list of RowHashBlock objects also provides a way to sequentially -** scan all elements in the RowHash. This sequential scan is used when -** rebuilding the hash table. The hash table is rebuilt after every -** batch of inserts. -*/ -struct RowHashBlock { - struct RowHashBlockData { - RowHashBlock *pNext; /* Next RowHashBlock object in list of them all */ - } data; - RowHashElem aElem[ROWHASH_ELEM_PER_BLOCK]; /* Available RowHashElem objects */ -}; - -/* -** RowHash structure. References to a structure of this type are passed -** around and used as opaque handles by code in other modules. -*/ -struct RowHash { - unsigned int nEntry; /* Number of used entries over all RowHashBlocks */ - int iBatch; /* The current insert batch number */ - u16 nUsed; /* Number of used entries in first RowHashBlock */ - u8 nHeight; /* Height of tree of hash pages */ - u8 nLinearLimit; /* Linear search limit (used if pHash==0) */ - int nBucket; /* Number of buckets in hash table */ - RowHashPage *pHash; /* Pointer to root of hash table tree */ - RowHashBlock *pBlock; /* Linked list of RowHashBlocks */ - sqlite3 *db; /* Associated database connection */ -}; - - -/* -** Allocate a hash table tree of height nHeight with *pnLeaf leaf pages. -** Set *pp to point to the root of the tree. If the maximum number of leaf -** pages in a tree of height nHeight is less than *pnLeaf, allocate only -** that part of the tree that is necessary to account for all leaves. -** -** Before returning, subtract the number of leaves in the tree allocated -** from *pnLeaf. -** -** This routine returns SQLITE_NOMEM if a malloc() fails, or SQLITE_OK -** otherwise. -*/ -static int allocHashTable(RowHashPage **pp, int nHeight, int *pnLeaf){ - RowHashPage *p = (RowHashPage *)sqlite3MallocZero(sizeof(*p)); - if( !p ){ - return SQLITE_NOMEM; - } - *pp = p; - if( nHeight==0 ){ - (*pnLeaf)--; - }else{ - int ii; - for(ii=0; ii0; ii++){ - if( allocHashTable(&p->a[ii].pPage, nHeight-1, pnLeaf) ){ - return SQLITE_NOMEM; - } - } - } - return SQLITE_OK; -} - -/* -** Delete the hash table tree of height nHeight passed as the first argument. -*/ -static void deleteHashTable(RowHashPage *p, int nHeight){ - if( p ){ - if( nHeight>0 ){ - int ii; - for(ii=0; iia[ii].pPage, nHeight-1); - } - } - sqlite3_free(p); - } -} - -/* -** Find the hash-bucket associated with value iVal. Return a pointer to it. -** -** By "hash-bucket", we mean the RowHashPage.a[].pElem pointer that -** corresponds to a particular hash entry. -*/ -static RowHashElem **findHashBucket(RowHash *pRowHash, i64 iVal){ - int aOffset[16]; - int n; - RowHashPage *pPage = pRowHash->pHash; - int h = (((u64)iVal) % pRowHash->nBucket); - - assert( pRowHash->nHeight < sizeof(aOffset)/sizeof(aOffset[0]) ); - for(n=0; nnHeight; n++){ - int h1 = h / ROWHASH_POINTER_PER_PAGE; - aOffset[n] = h - (h1 * ROWHASH_POINTER_PER_PAGE); - h = h1; - } - aOffset[n] = h; - for(n=pRowHash->nHeight; n>0; n--){ - pPage = pPage->a[aOffset[n]].pPage; - } - return &pPage->a[aOffset[0]].pElem; -} - -/* -** Build a new hash table tree in p->pHash. The new hash table should -** contain all p->nEntry entries in the p->pBlock list. If there -** existed a prior tree, delete the old tree first before constructing -** the new one. -** -** If the number of entries (p->nEntry) is less than -** ROWHASH_LINEAR_SEARCH_LIMIT, then we are guessing that a linear -** search is going to be faster than a lookup, so do not bother -** building the hash table. -*/ -static int makeHashTable(RowHash *p, int iBatch){ - RowHashBlock *pBlock; - int nBucket; - int nLeaf, n; - - /* Delete the old hash table. */ - deleteHashTable(p->pHash, p->nHeight); - assert( p->iBatch!=iBatch ); - p->iBatch = iBatch; - - /* Skip building the hash table if the number of elements is small */ - if( p->nEntrynLinearLimit = p->nEntry; - p->pHash = 0; - return SQLITE_OK; - } - - /* Determine how many leaves the hash-table will comprise. */ - nLeaf = 1 + (p->nEntry / (ROWHASH_POINTER_PER_PAGE*ROWHASH_COLLISION_LENGTH)); - p->nBucket = nBucket = nLeaf*ROWHASH_POINTER_PER_PAGE; - - /* Set nHeight to the height of the tree that contains the leaf pages. If - ** RowHash.nHeight is zero, then the whole hash-table fits on a single - ** leaf. If RowHash.nHeight is 1, then RowHash.pHash points to an array - ** of pointers to leaf pages. If 2, pHash points to an array of pointers - ** to arrays of pointers to leaf pages. And so on. - */ - p->nHeight = 0; - n = nLeaf; - while( n>1 ){ - n = (n+ROWHASH_POINTER_PER_PAGE-1) / ROWHASH_POINTER_PER_PAGE; - p->nHeight++; - } - - /* Allocate the hash-table. */ - if( allocHashTable(&p->pHash, p->nHeight, &nLeaf) ){ - return SQLITE_NOMEM; - } - - /* Insert all values into the hash-table. */ - for(pBlock=p->pBlock; pBlock; pBlock=pBlock->data.pNext){ - RowHashElem * const pEnd = &pBlock->aElem[ - pBlock==p->pBlock?p->nUsed:ROWHASH_ELEM_PER_BLOCK - ]; - RowHashElem *pIter; - for(pIter=pBlock->aElem; pIteriVal); - pIter->pNext = *ppElem; - *ppElem = pIter; - } - } - - return SQLITE_OK; -} - -/* -** Check to see if iVal has been inserted into the hash table "p" -** in some batch prior to iBatch. If so, set *pExists to 1. -** If not, set *pExists to 0. -** -** The hash table is rebuilt whenever iBatch changes. A hash table -** rebuild might encounter an out-of-memory condition. If that happens, -** return SQLITE_NOMEM. If there are no problems, return SQLITE_OK. -** -** The initial "batch" is 0. So, if there were prior calls to -** sqlite3RowhashInsert() and then this routine is invoked with iBatch==0, -** because all prior inserts where in the same batch, none of the prior -** inserts will be visible and this routine will indicate not found. -** Hence, the first invocation of this routine should probably use -** a batch number of 1. -*/ -int sqlite3RowhashTest( - RowHash *p, /* The RowHash to search in */ - int iBatch, /* Look for values inserted in batches prior to this batch */ - i64 iVal, /* The rowid value we are looking for */ - int *pExists /* Store 0 or 1 hear to indicate not-found or found */ -){ - *pExists = 0; - if( p ){ - assert( p->pBlock ); - if( iBatch!=p->iBatch && makeHashTable(p, iBatch) ){ - return SQLITE_NOMEM; - } - if( p->pHash ){ - RowHashElem *pElem = *findHashBucket(p, iVal); - for(; pElem; pElem=pElem->pNext){ - if( pElem->iVal==iVal ){ - *pExists = 1; - break; - } - } - }else{ - int ii; - RowHashElem *aElem = p->pBlock->aElem; - for(ii=0; iinLinearLimit; ii++){ - if( aElem[ii].iVal==iVal ){ - *pExists = 1; - break; - } - } - } - } - return SQLITE_OK; -} - -/* -** Insert value iVal into the RowHash object. Allocate a new RowHash -** object if necessary. -** -** Return SQLITE_OK if all goes as planned. If a malloc() fails, return -** SQLITE_NOMEM. -*/ -int sqlite3RowhashInsert(sqlite3 *db, RowHash **pp, i64 iVal){ - RowHash *p = *pp; - - /* If the RowHash structure has not been allocated, allocate it now. */ - if( !p ){ - p = (RowHash*)sqlite3DbMallocZero(db, sizeof(RowHash)); - if( !p ){ - return SQLITE_NOMEM; - } - p->db = db; - *pp = p; - } - - /* If the current RowHashBlock is full, or if the first RowHashBlock has - ** not yet been allocated, allocate one now. */ - if( !p->pBlock || p->nUsed==ROWHASH_ELEM_PER_BLOCK ){ - RowHashBlock *pBlock = (RowHashBlock*)sqlite3Malloc(sizeof(RowHashBlock)); - if( !pBlock ){ - return SQLITE_NOMEM; - } - pBlock->data.pNext = p->pBlock; - p->pBlock = pBlock; - p->nUsed = 0; - } - assert( p->nUsed==(p->nEntry % ROWHASH_ELEM_PER_BLOCK) ); - - /* Add iVal to the current RowHashBlock. */ - p->pBlock->aElem[p->nUsed].iVal = iVal; - p->nUsed++; - p->nEntry++; - return SQLITE_OK; -} - -/* -** Destroy the RowHash object passed as the first argument. -*/ -void sqlite3RowhashDestroy(RowHash *p){ - if( p ){ - RowHashBlock *pBlock, *pNext; - deleteHashTable(p->pHash, p->nHeight); - for(pBlock=p->pBlock; pBlock; pBlock=pNext){ - pNext = pBlock->data.pNext; - sqlite3_free(pBlock); - } - sqlite3DbFree(p->db, p); - } -} diff --git a/src/sqliteInt.h b/src/sqliteInt.h index 2e51888e00..5a61ea5b49 100644 --- a/src/sqliteInt.h +++ b/src/sqliteInt.h @@ -11,7 +11,7 @@ ************************************************************************* ** Internal interface definitions for SQLite. ** -** @(#) $Id: sqliteInt.h,v 1.857 2009/04/22 00:47:01 drh Exp $ +** @(#) $Id: sqliteInt.h,v 1.858 2009/04/22 02:15:48 drh Exp $ */ #ifndef _SQLITEINT_H_ #define _SQLITEINT_H_ @@ -557,7 +557,6 @@ struct BusyHandler { typedef struct AggInfo AggInfo; typedef struct AuthContext AuthContext; typedef struct Bitvec Bitvec; -typedef struct RowHash RowHash; typedef struct RowSet RowSet; typedef struct CollSeq CollSeq; typedef struct Column Column; @@ -1752,7 +1751,7 @@ struct WhereLevel { #define WHERE_FILL_ROWSET 0x0008 /* Save results in a RowSet object */ #define WHERE_OMIT_OPEN 0x0010 /* Table cursor are already open */ #define WHERE_OMIT_CLOSE 0x0020 /* Omit close of table & index cursors */ -#define WHERE_FILL_ROWHASH 0x0040 /* Save results in a RowHash object */ +#define WHERE_FILL_ROWTEST 0x0040 /* Save results using OP_RowSetTest */ /* ** The WHERE clause processing routine has two halves. The @@ -1765,8 +1764,8 @@ struct WhereInfo { Parse *pParse; /* Parsing and code generating context */ u16 wctrlFlags; /* Flags originally passed to sqlite3WhereBegin() */ u8 okOnePass; /* Ok to use one-pass algorithm for UPDATE or DELETE */ - int regRowSet; /* Store rowids in this rowset/rowhash */ - int iRowidHandler; /* Address of OP_RowSet or OP_RowHash */ + int regRowSet; /* Store rowids in this rowset */ + int iRowidHandler; /* Address of OP_RowSet or OP_RowSetTest */ SrcList *pTabList; /* List of tables in the join */ int iTop; /* The very beginning of the WHERE loop */ int iContinue; /* Jump here to continue with next record */ @@ -2403,10 +2402,6 @@ void sqlite3RowSetInsert(RowSet*, i64); int sqlite3RowSetTest(RowSet*, u8 iBatch, i64); int sqlite3RowSetNext(RowSet*, i64*); -int sqlite3RowhashInsert(sqlite3*, RowHash **pp, i64 iVal); -int sqlite3RowhashTest(RowHash *p, int iSet, i64 iVal, int *pExists); -void sqlite3RowhashDestroy(RowHash *p); - void sqlite3CreateView(Parse*,Token*,Token*,Token*,Select*,int,int); #if !defined(SQLITE_OMIT_VIEW) || !defined(SQLITE_OMIT_VIRTUALTABLE) diff --git a/src/vdbe.c b/src/vdbe.c index 8cc33d0be4..a5312fc834 100644 --- a/src/vdbe.c +++ b/src/vdbe.c @@ -43,7 +43,7 @@ ** in this file for details. If in doubt, do not deviate from existing ** commenting and indentation practices when changing or adding code. ** -** $Id: vdbe.c,v 1.836 2009/04/22 00:47:01 drh Exp $ +** $Id: vdbe.c,v 1.837 2009/04/22 02:15:48 drh Exp $ */ #include "sqliteInt.h" #include "vdbeInt.h" @@ -4604,34 +4604,35 @@ case OP_RowSetRead: { /* jump, out3 */ break; } -/* Opcode: RowHash P1 P2 P3 P4 +/* Opcode: RowSetTest P1 P2 P3 P4 ** ** Register P3 is assumed to hold a 64-bit integer value. If register P1 -** contains a rowid-hash object and the rowid-hash object contains +** contains a RowSet object and that RowSet object contains ** the value held in P3, jump to register P2. Otherwise, insert the -** integer in P3 into the rowid-hash container and continue on to the +** integer in P3 into the RowSet and continue on to the ** next opcode. ** -** The rowid-hash is optimized for the case where successive sets +** The RowSet object is optimized for the case where successive sets ** of integers, where each set contains no duplicates. Each set ** of values is identified by a unique P4 value. The first set -** must have P4==0, the final set P4=-1. +** must have P4==0, the final set P4=-1. P4 must be either -1 or +** non-negative. For non-negative values of P4 only the lower 4 +** bits are significant. ** ** This allows optimizations: (a) when P4==0 there is no need to test -** the row-hash object for P3, as it is guaranteed not to contain it, +** the rowset object for P3, as it is guaranteed not to contain it, ** (b) when P4==-1 there is no need to insert the value, as it will ** never be tested for, and (c) when a value that is part of set X is ** inserted, there is no need to search to see if the same value was ** previously inserted as part of set X (only if it was previously ** inserted as part of some other set). */ -case OP_RowHash: { /* jump, in1, in3 */ +case OP_RowSetTest: { /* jump, in1, in3 */ int iSet = pOp->p4.i; assert( pIn3->flags&MEM_Int ); - /* If there is anything other than a row-hash object in memory cell P1, - ** delete it now and initialize P1 with an empty row-hash (a null pointer - ** is an acceptable representation of an empty row-hash). + /* If there is anything other than a rowset object in memory cell P1, + ** delete it now and initialize P1 with an empty rowset */ if( (pIn1->flags & MEM_RowSet)==0 ){ sqlite3VdbeMemSetRowSet(pIn1); @@ -4639,6 +4640,7 @@ case OP_RowHash: { /* jump, in1, in3 */ } assert( pOp->p4type==P4_INT32 ); + assert( iSet==-1 || iSet>=0 ); if( iSet ){ int exists; exists = sqlite3RowSetTest(pIn1->u.pRowSet, iSet>=0 ? iSet & 0xf : 0xff, diff --git a/src/vdbeInt.h b/src/vdbeInt.h index e5b9f25b29..cbf867dd06 100644 --- a/src/vdbeInt.h +++ b/src/vdbeInt.h @@ -15,7 +15,7 @@ ** 6000 lines long) it was split up into several smaller files and ** this header information was factored out. ** -** $Id: vdbeInt.h,v 1.168 2009/04/21 09:02:47 danielk1977 Exp $ +** $Id: vdbeInt.h,v 1.169 2009/04/22 02:15:48 drh Exp $ */ #ifndef _VDBEINT_H_ #define _VDBEINT_H_ @@ -115,7 +115,6 @@ struct Mem { int nZero; /* Used when bit MEM_Zero is set in flags */ FuncDef *pDef; /* Used only when flags==MEM_Agg */ RowSet *pRowSet; /* Used only when flags==MEM_RowSet */ - RowHash *pRowHash; /* Used only when flags==MEM_RowHash */ } u; double r; /* Real value */ sqlite3 *db; /* The associated database connection */ @@ -149,7 +148,6 @@ struct Mem { #define MEM_Real 0x0008 /* Value is a real number */ #define MEM_Blob 0x0010 /* Value is a BLOB */ #define MEM_RowSet 0x0020 /* Value is a RowSet object */ -#define MEM_RowHash 0x0040 /* Value is a RowHash object */ #define MEM_TypeMask 0x00ff /* Mask of type bits */ /* Whenever Mem contains a valid string or blob representation, one of diff --git a/src/vdbeaux.c b/src/vdbeaux.c index 697a61bad7..8d16b875c9 100644 --- a/src/vdbeaux.c +++ b/src/vdbeaux.c @@ -14,7 +14,7 @@ ** to version 2.8.7, all this code was combined into the vdbe.c source file. ** But that file was getting too big so this subroutines were split out. ** -** $Id: vdbeaux.c,v 1.452 2009/04/21 09:02:47 danielk1977 Exp $ +** $Id: vdbeaux.c,v 1.453 2009/04/22 02:15:48 drh Exp $ */ #include "sqliteInt.h" #include "vdbeInt.h" @@ -1224,9 +1224,6 @@ static void Cleanup(Vdbe *p){ if( pMem->flags & MEM_RowSet ){ sqlite3RowSetClear(pMem->u.pRowSet); } - if( pMem->flags & MEM_RowHash ){ - sqlite3RowhashDestroy(pMem->u.pRowHash); - } MemSetTypeFlag(pMem, MEM_Null); } releaseMemArray(&p->aMem[1], p->nMem); diff --git a/src/vdbemem.c b/src/vdbemem.c index 478ed26646..6bc0e1ff81 100644 --- a/src/vdbemem.c +++ b/src/vdbemem.c @@ -15,7 +15,7 @@ ** only within the VDBE. Interface routines refer to a Mem using the ** name sqlite_value ** -** $Id: vdbemem.c,v 1.141 2009/04/21 09:02:47 danielk1977 Exp $ +** $Id: vdbemem.c,v 1.142 2009/04/22 02:15:49 drh Exp $ */ #include "sqliteInt.h" #include "vdbeInt.h" @@ -270,7 +270,7 @@ int sqlite3VdbeMemFinalize(Mem *pMem, FuncDef *pFunc){ */ void sqlite3VdbeMemReleaseExternal(Mem *p){ assert( p->db==0 || sqlite3_mutex_held(p->db->mutex) ); - if( p->flags&(MEM_Agg|MEM_Dyn|MEM_RowSet|MEM_RowHash) ){ + if( p->flags&(MEM_Agg|MEM_Dyn|MEM_RowSet) ){ if( p->flags&MEM_Agg ){ sqlite3VdbeMemFinalize(p, p->u.pDef); assert( (p->flags & MEM_Agg)==0 ); @@ -281,9 +281,6 @@ void sqlite3VdbeMemReleaseExternal(Mem *p){ p->xDel = 0; }else if( p->flags&MEM_RowSet ){ sqlite3RowSetClear(p->u.pRowSet); - }else if( p->flags&MEM_RowHash ){ - sqlite3RowhashDestroy(p->u.pRowHash); - p->u.pRowHash = 0; } } } diff --git a/src/where.c b/src/where.c index 2ff8637490..15c3e73650 100644 --- a/src/where.c +++ b/src/where.c @@ -16,7 +16,7 @@ ** so is applicable. Because this module is responsible for selecting ** indices, you might also think of this module as the "query optimizer". ** -** $Id: where.c,v 1.384 2009/04/21 17:23:05 danielk1977 Exp $ +** $Id: where.c,v 1.385 2009/04/22 02:15:49 drh Exp $ */ #include "sqliteInt.h" @@ -2414,14 +2414,11 @@ static Bitmask codeOneLoopStart( ** 1) If pWInfo->regRowSet is non-zero, then the rowid must be inserted ** into the RowSet object stored in register pWInfo->regRowSet. ** - ** 2) If pWInfo->regRowHash is non-zero, then the rowid must be inserted - ** into the RowHash object stored in register pWInfo->regRowHash. - ** ** Extracting a rowid value from a VDBE cursor is not always a cheap ** operation, especially if the rowid is being extracted from an index ** cursor. If the rowid value is available as a by-product of the code ** generated to create the top of the scan loop, then it can be reused - ** for either of the two purposes enumerated above without extracting + ** without extracting ** it from a cursor. The following two variables are used to communicate ** the availability of the rowid value to the C-code at the end of this ** function that generates the rowid-handling VDBE code. @@ -2437,7 +2434,7 @@ static Bitmask codeOneLoopStart( iCur = pTabItem->iCursor; bRev = (pLevel->plan.wsFlags & WHERE_REVERSE)!=0; omitTable = (pLevel->plan.wsFlags & WHERE_IDX_ONLY)!=0 - && (wctrlFlags & WHERE_FILL_ROWHASH)==0; + && (wctrlFlags & WHERE_FILL_ROWTEST)==0; regRowSet = pWInfo->regRowSet; codeRowSetEarly = 0; @@ -2817,22 +2814,22 @@ static Bitmask codeOneLoopStart( ** In the example, there are three indexed terms connected by OR. ** The top of the loop looks like this: ** - ** Null 1 # Zero the row-hash in reg 1 + ** Null 1 # Zero the rowset in reg 1 ** ** Then, for each indexed term, the following. The arguments to - ** RowHash are such that the rowid of the current row is inserted - ** into the row-hash. If it is already present, control skips the + ** RowSetTest are such that the rowid of the current row is inserted + ** into the RowSet. If it is already present, control skips the ** Gosub opcode and jumps straight to the code generated by WhereEnd(). ** ** sqlite3WhereBegin() - ** RowHash # Insert rowid into rowhash + ** RowSetTest # Insert rowid into rowset ** Gosub 2 A ** sqlite3WhereEnd() ** ** Following the above, code to terminate the loop. Label A, the target ** of the Gosub above, jumps to the instruction right after the Goto. ** - ** Null 1 # Zero the row-hash in reg 1 + ** Null 1 # Zero the rowset in reg 1 ** Goto B # The loop is finished. ** ** A: # Return data, whatever. @@ -2842,14 +2839,14 @@ static Bitmask codeOneLoopStart( ** B: ** */ - const int f = WHERE_OMIT_OPEN | WHERE_OMIT_CLOSE | WHERE_FILL_ROWHASH; + const int f = WHERE_OMIT_OPEN | WHERE_OMIT_CLOSE | WHERE_FILL_ROWTEST; WhereClause *pOrWc; /* The OR-clause broken out into subterms */ WhereTerm *pFinal; /* Final subterm within the OR-clause. */ SrcList oneTab; /* Shortened table list */ int regReturn = ++pParse->nMem; /* Register used with OP_Gosub */ - int regRowhash = ++pParse->nMem; /* Register for RowHash object */ + int regRowset = ++pParse->nMem; /* Register for RowSet object */ int iLoopBody = sqlite3VdbeMakeLabel(v); /* Start of loop body */ int iRetInit; /* Address of regReturn init */ int ii; @@ -2866,8 +2863,8 @@ static Bitmask codeOneLoopStart( oneTab.nAlloc = 1; oneTab.a[0] = *pTabItem; - /* Initialize the row-hash register to contain NULL. An SQL NULL is - ** equivalent to an empty row-hash. + /* Initialize the rowset register to contain NULL. An SQL NULL is + ** equivalent to an empty rowset. ** ** Also initialize regReturn to contain the address of the instruction ** immediately following the OP_Return at the bottom of the loop. This @@ -2877,7 +2874,7 @@ static Bitmask codeOneLoopStart( ** fall through to the next instruction, just as an OP_Next does if ** called on an uninitialized cursor. */ - sqlite3VdbeAddOp2(v, OP_Null, 0, regRowhash); + sqlite3VdbeAddOp2(v, OP_Null, 0, regRowset); iRetInit = sqlite3VdbeAddOp2(v, OP_Integer, 0, regReturn); /* iReleaseReg = iRowidReg = sqlite3GetTempReg(pParse); */ @@ -2888,18 +2885,18 @@ static Bitmask codeOneLoopStart( /* Loop through table entries that match term pOrTerm. */ pSubWInfo = sqlite3WhereBegin( - pParse, &oneTab, pOrTerm->pExpr, 0, f, regRowhash); + pParse, &oneTab, pOrTerm->pExpr, 0, f, regRowset); if( pSubWInfo ){ int iSet = ((ii==pOrWc->nTerm-1)?-1:ii); - /* The call to sqlite3WhereBegin has coded an OP_RowHash - ** at instruction iRowHash. Set P2 (the jump target) of this + /* The call to sqlite3WhereBegin has coded an OP_RowSetTest + ** at instruction iRowSet. Set P2 (the jump target) of this ** instruction to jump past the OP_Gosub coded below. This way, ** if the rowid is already in the hash-table, the body of the ** loop is not executed. */ - int iRowHash = pSubWInfo->iRowidHandler; - sqlite3VdbeChangeP2(v, iRowHash, sqlite3VdbeCurrentAddr(v) + 1); - sqlite3VdbeChangeP4(v, iRowHash, (char *)iSet, P4_INT32); + int iRowSet = pSubWInfo->iRowidHandler; + sqlite3VdbeChangeP2(v, iRowSet, sqlite3VdbeCurrentAddr(v) + 1); + sqlite3VdbeChangeP4(v, iRowSet, (char *)iSet, P4_INT32); sqlite3VdbeAddOp2(v, OP_Gosub, regReturn, iLoopBody); /* Finish the loop through table entries that match term pOrTerm. */ @@ -2908,7 +2905,7 @@ static Bitmask codeOneLoopStart( } } sqlite3VdbeChangeP1(v, iRetInit, sqlite3VdbeCurrentAddr(v)); - sqlite3VdbeAddOp2(v, OP_Null, 0, regRowhash); + sqlite3VdbeAddOp2(v, OP_Null, 0, regRowset); sqlite3VdbeAddOp2(v, OP_Goto, 0, pLevel->addrBrk); sqlite3VdbeResolveLabel(v, iLoopBody); @@ -2998,8 +2995,8 @@ static Bitmask codeOneLoopStart( if( pWInfo->wctrlFlags&WHERE_FILL_ROWSET ){ sqlite3VdbeAddOp2(v, OP_RowSetAdd, regRowSet, iRowidReg); }else{ - assert( pWInfo->wctrlFlags&WHERE_FILL_ROWHASH ); - sqlite3VdbeAddOp3(v, OP_RowHash, regRowSet, 0, iRowidReg); + assert( pWInfo->wctrlFlags&WHERE_FILL_ROWTEST ); + sqlite3VdbeAddOp3(v, OP_RowSetTest, regRowSet, 0, iRowidReg); } } sqlite3ReleaseTempReg(pParse, iReleaseReg); @@ -3189,7 +3186,7 @@ WhereInfo *sqlite3WhereBegin( pWInfo->pWC = pWC = (WhereClause *)&((u8 *)pWInfo)[nByteWInfo]; pWInfo->wctrlFlags = wctrlFlags; pMaskSet = (WhereMaskSet*)&pWC[1]; - assert( regRowSet==0 || (wctrlFlags&(WHERE_FILL_ROWSET|WHERE_FILL_ROWHASH)) ); + assert( regRowSet==0 || (wctrlFlags&(WHERE_FILL_ROWSET|WHERE_FILL_ROWTEST)) ); /* Split the WHERE clause into separate subexpressions where each ** subexpression is separated by an AND operator. diff --git a/tool/mksqlite3c.tcl b/tool/mksqlite3c.tcl index 4ad960e2dc..857ecfb7f5 100644 --- a/tool/mksqlite3c.tcl +++ b/tool/mksqlite3c.tcl @@ -239,7 +239,6 @@ foreach file { os_unix.c os_win.c - rowhash.c bitvec.c pcache.c pcache1.c -- 2.47.2