Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
Comment: | Allocate the initial RowHash object using lookaside. (CVS 6530) |
---|---|
Downloads: | Tarball | ZIP archive |
Timelines: | family | ancestors | descendants | both | trunk |
Files: | files | file ages | folders |
SHA1: |
9b30ab7199d8b51bdea8ec7f04102815 |
User & Date: | drh 2009-04-21 16:15:15.000 |
Context
2009-04-21
| ||
17:13 | Adjust the rowhash.test module so that it recovers gracefully in the rare event of a rowid collision. (CVS 6531) (check-in: 72e1680904 user: drh tags: trunk) | |
16:15 | Allocate the initial RowHash object using lookaside. (CVS 6530) (check-in: 9b30ab7199 user: drh tags: trunk) | |
15:05 | New comments and minor refactoring of rowhash.c. (CVS 6529) (check-in: b8cb4f3e24 user: drh tags: trunk) | |
Changes
Changes to src/rowhash.c.
︙ | ︙ | |||
27 28 29 30 31 32 33 | ** 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. ** | | | 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 | ** 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.3 2009/04/21 16:15:15 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. */ |
︙ | ︙ | |||
132 133 134 135 136 137 138 | }; /* ** RowHash structure. References to a structure of this type are passed ** around and used as opaque handles by code in other modules. */ struct RowHash { | < | < < < | > > | < | > | | 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 | }; /* ** RowHash structure. References to a structure of this type are passed ** around and used as opaque handles by code in other modules. */ struct RowHash { int nEntry; /* Number of used entries over all RowHashBlocks */ int iBatch; /* The current insert batch number */ 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 |
︙ | ︙ | |||
201 202 203 204 205 206 207 | ** 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; | | | 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 | ** 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; n<pRowHash->nHeight; n++){ int h1 = h / ROWHASH_POINTER_PER_PAGE; aOffset[n] = h - (h1 * ROWHASH_POINTER_PER_PAGE); h = h1; } |
︙ | ︙ | |||
229 230 231 232 233 234 235 | ** 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; | | | | 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 | ** 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->nEntry<ROWHASH_LINEAR_SEARCH_LIMIT ){ p->nLinearLimit = 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. */ |
︙ | ︙ | |||
337 338 339 340 341 342 343 | /* ** 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. */ | | | > | 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 | /* ** 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->pBlock->data.nUsed==ROWHASH_ELEM_PER_BLOCK ){ RowHashBlock *pBlock = (RowHashBlock*)sqlite3Malloc(sizeof(RowHashBlock)); |
︙ | ︙ | |||
379 380 381 382 383 384 385 | if( p ){ RowHashBlock *pBlock, *pNext; deleteHashTable(p->pHash, p->nHeight); for(pBlock=p->pBlock; pBlock; pBlock=pNext){ pNext = pBlock->data.pNext; sqlite3_free(pBlock); } | | | 378 379 380 381 382 383 384 385 386 387 | 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); } } |
Changes to src/sqliteInt.h.
1 2 3 4 5 6 7 8 9 10 11 12 13 | /* ** 2001 September 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. ** ************************************************************************* ** Internal interface definitions for SQLite. ** | | | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 | /* ** 2001 September 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. ** ************************************************************************* ** Internal interface definitions for SQLite. ** ** @(#) $Id: sqliteInt.h,v 1.856 2009/04/21 16:15:15 drh Exp $ */ #ifndef _SQLITEINT_H_ #define _SQLITEINT_H_ /* ** Include the configuration header output by 'configure' if we're using the ** autoconf-based build |
︙ | ︙ | |||
2398 2399 2400 2401 2402 2403 2404 | int sqlite3BitvecBuiltinTest(int,int*); RowSet *sqlite3RowSetInit(sqlite3*, void*, unsigned int); void sqlite3RowSetClear(RowSet*); void sqlite3RowSetInsert(RowSet*, i64); int sqlite3RowSetNext(RowSet*, i64*); | | | 2398 2399 2400 2401 2402 2403 2404 2405 2406 2407 2408 2409 2410 2411 2412 | int sqlite3BitvecBuiltinTest(int,int*); RowSet *sqlite3RowSetInit(sqlite3*, void*, unsigned int); void sqlite3RowSetClear(RowSet*); void sqlite3RowSetInsert(RowSet*, 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) int sqlite3ViewGetColumnNames(Parse*,Table*); |
︙ | ︙ |
Changes to src/vdbe.c.
︙ | ︙ | |||
39 40 41 42 43 44 45 | ** ** Various scripts scan this source file in order to generate HTML ** documentation, headers files, or other derived files. The formatting ** of the code in this file is, therefore, important. See other comments ** in this file for details. If in doubt, do not deviate from existing ** commenting and indentation practices when changing or adding code. ** | | | 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 | ** ** Various scripts scan this source file in order to generate HTML ** documentation, headers files, or other derived files. The formatting ** of the code in this file is, therefore, important. See other comments ** 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.835 2009/04/21 16:15:15 drh Exp $ */ #include "sqliteInt.h" #include "vdbeInt.h" /* ** The following global variable is incremented every time a cursor ** moves, either by the OP_SeekXX, OP_Next, or OP_Prev opcodes. The test |
︙ | ︙ | |||
4643 4644 4645 4646 4647 4648 4649 | rc = sqlite3RowhashTest(pIn1->u.pRowHash, pOp->p4.i, pIn3->u.i, &exists); if( exists ){ pc = pOp->p2 - 1; break; } } if( iSet>=0 ){ | | | 4643 4644 4645 4646 4647 4648 4649 4650 4651 4652 4653 4654 4655 4656 4657 | rc = sqlite3RowhashTest(pIn1->u.pRowHash, pOp->p4.i, pIn3->u.i, &exists); if( exists ){ pc = pOp->p2 - 1; break; } } if( iSet>=0 ){ rc = sqlite3RowhashInsert(db, &pIn1->u.pRowHash, pIn3->u.i); } break; } #ifndef SQLITE_OMIT_TRIGGER /* Opcode: ContextPush * * * |
︙ | ︙ |