| OLD | NEW |
|---|
| (Empty) |
| 1 /* | |
| 2 ** 2008 December 3 | |
| 3 ** | |
| 4 ** The author disclaims copyright to this source code. In place of | |
| 5 ** a legal notice, here is a blessing: | |
| 6 ** | |
| 7 ** May you do good and not evil. | |
| 8 ** May you find forgiveness for yourself and forgive others. | |
| 9 ** May you share freely, never taking more than you give. | |
| 10 ** | |
| 11 ************************************************************************* | |
| 12 ** | |
| 13 ** This module implements an object we call a "RowSet". | |
| 14 ** | |
| 15 ** The RowSet object is a collection of rowids. Rowids | |
| 16 ** are inserted into the RowSet in an arbitrary order. Inserts | |
| 17 ** can be intermixed with tests to see if a given rowid has been | |
| 18 ** previously inserted into the RowSet. | |
| 19 ** | |
| 20 ** After all inserts are finished, it is possible to extract the | |
| 21 ** elements of the RowSet in sorted order. Once this extraction | |
| 22 ** process has started, no new elements may be inserted. | |
| 23 ** | |
| 24 ** Hence, the primitive operations for a RowSet are: | |
| 25 ** | |
| 26 ** CREATE | |
| 27 ** INSERT | |
| 28 ** TEST | |
| 29 ** SMALLEST | |
| 30 ** DESTROY | |
| 31 ** | |
| 32 ** The CREATE and DESTROY primitives are the constructor and destructor, | |
| 33 ** obviously. The INSERT primitive adds a new element to the RowSet. | |
| 34 ** TEST checks to see if an element is already in the RowSet. SMALLEST | |
| 35 ** extracts the least value from the RowSet. | |
| 36 ** | |
| 37 ** The INSERT primitive might allocate additional memory. Memory is | |
| 38 ** allocated in chunks so most INSERTs do no allocation. There is an | |
| 39 ** upper bound on the size of allocated memory. No memory is freed | |
| 40 ** until DESTROY. | |
| 41 ** | |
| 42 ** The TEST primitive includes a "batch" number. The TEST primitive | |
| 43 ** will only see elements that were inserted before the last change | |
| 44 ** in the batch number. In other words, if an INSERT occurs between | |
| 45 ** two TESTs where the TESTs have the same batch nubmer, then the | |
| 46 ** value added by the INSERT will not be visible to the second TEST. | |
| 47 ** The initial batch number is zero, so if the very first TEST contains | |
| 48 ** a non-zero batch number, it will see all prior INSERTs. | |
| 49 ** | |
| 50 ** No INSERTs may occurs after a SMALLEST. An assertion will fail if | |
| 51 ** that is attempted. | |
| 52 ** | |
| 53 ** The cost of an INSERT is roughly constant. (Sometime new memory | |
| 54 ** has to be allocated on an INSERT.) The cost of a TEST with a new | |
| 55 ** batch number is O(NlogN) where N is the number of elements in the RowSet. | |
| 56 ** The cost of a TEST using the same batch number is O(logN). The cost | |
| 57 ** of the first SMALLEST is O(NlogN). Second and subsequent SMALLEST | |
| 58 ** primitives are constant time. The cost of DESTROY is O(N). | |
| 59 ** | |
| 60 ** There is an added cost of O(N) when switching between TEST and | |
| 61 ** SMALLEST primitives. | |
| 62 ** | |
| 63 ** $Id: rowset.c,v 1.7 2009/05/22 01:00:13 drh Exp $ | |
| 64 */ | |
| 65 #include "sqliteInt.h" | |
| 66 | |
| 67 | |
| 68 /* | |
| 69 ** Target size for allocation chunks. | |
| 70 */ | |
| 71 #define ROWSET_ALLOCATION_SIZE 1024 | |
| 72 | |
| 73 /* | |
| 74 ** The number of rowset entries per allocation chunk. | |
| 75 */ | |
| 76 #define ROWSET_ENTRY_PER_CHUNK \ | |
| 77 ((ROWSET_ALLOCATION_SIZE-8)/sizeof(struct RowSetEntry)) | |
| 78 | |
| 79 /* | |
| 80 ** Each entry in a RowSet is an instance of the following object. | |
| 81 */ | |
| 82 struct RowSetEntry { | |
| 83 i64 v; /* ROWID value for this entry */ | |
| 84 struct RowSetEntry *pRight; /* Right subtree (larger entries) or list */ | |
| 85 struct RowSetEntry *pLeft; /* Left subtree (smaller entries) */ | |
| 86 }; | |
| 87 | |
| 88 /* | |
| 89 ** RowSetEntry objects are allocated in large chunks (instances of the | |
| 90 ** following structure) to reduce memory allocation overhead. The | |
| 91 ** chunks are kept on a linked list so that they can be deallocated | |
| 92 ** when the RowSet is destroyed. | |
| 93 */ | |
| 94 struct RowSetChunk { | |
| 95 struct RowSetChunk *pNextChunk; /* Next chunk on list of them all */ | |
| 96 struct RowSetEntry aEntry[ROWSET_ENTRY_PER_CHUNK]; /* Allocated entries */ | |
| 97 }; | |
| 98 | |
| 99 /* | |
| 100 ** A RowSet in an instance of the following structure. | |
| 101 ** | |
| 102 ** A typedef of this structure if found in sqliteInt.h. | |
| 103 */ | |
| 104 struct RowSet { | |
| 105 struct RowSetChunk *pChunk; /* List of all chunk allocations */ | |
| 106 sqlite3 *db; /* The database connection */ | |
| 107 struct RowSetEntry *pEntry; /* List of entries using pRight */ | |
| 108 struct RowSetEntry *pLast; /* Last entry on the pEntry list */ | |
| 109 struct RowSetEntry *pFresh; /* Source of new entry objects */ | |
| 110 struct RowSetEntry *pTree; /* Binary tree of entries */ | |
| 111 u16 nFresh; /* Number of objects on pFresh */ | |
| 112 u8 isSorted; /* True if pEntry is sorted */ | |
| 113 u8 iBatch; /* Current insert batch */ | |
| 114 }; | |
| 115 | |
| 116 /* | |
| 117 ** Turn bulk memory into a RowSet object. N bytes of memory | |
| 118 ** are available at pSpace. The db pointer is used as a memory context | |
| 119 ** for any subsequent allocations that need to occur. | |
| 120 ** Return a pointer to the new RowSet object. | |
| 121 ** | |
| 122 ** It must be the case that N is sufficient to make a Rowset. If not | |
| 123 ** an assertion fault occurs. | |
| 124 ** | |
| 125 ** If N is larger than the minimum, use the surplus as an initial | |
| 126 ** allocation of entries available to be filled. | |
| 127 */ | |
| 128 RowSet *sqlite3RowSetInit(sqlite3 *db, void *pSpace, unsigned int N){ | |
| 129 RowSet *p; | |
| 130 assert( N >= ROUND8(sizeof(*p)) ); | |
| 131 p = pSpace; | |
| 132 p->pChunk = 0; | |
| 133 p->db = db; | |
| 134 p->pEntry = 0; | |
| 135 p->pLast = 0; | |
| 136 p->pTree = 0; | |
| 137 p->pFresh = (struct RowSetEntry*)(ROUND8(sizeof(*p)) + (char*)p); | |
| 138 p->nFresh = (u16)((N - ROUND8(sizeof(*p)))/sizeof(struct RowSetEntry)); | |
| 139 p->isSorted = 1; | |
| 140 p->iBatch = 0; | |
| 141 return p; | |
| 142 } | |
| 143 | |
| 144 /* | |
| 145 ** Deallocate all chunks from a RowSet. This frees all memory that | |
| 146 ** the RowSet has allocated over its lifetime. This routine is | |
| 147 ** the destructor for the RowSet. | |
| 148 */ | |
| 149 void sqlite3RowSetClear(RowSet *p){ | |
| 150 struct RowSetChunk *pChunk, *pNextChunk; | |
| 151 for(pChunk=p->pChunk; pChunk; pChunk = pNextChunk){ | |
| 152 pNextChunk = pChunk->pNextChunk; | |
| 153 sqlite3DbFree(p->db, pChunk); | |
| 154 } | |
| 155 p->pChunk = 0; | |
| 156 p->nFresh = 0; | |
| 157 p->pEntry = 0; | |
| 158 p->pLast = 0; | |
| 159 p->pTree = 0; | |
| 160 p->isSorted = 1; | |
| 161 } | |
| 162 | |
| 163 /* | |
| 164 ** Insert a new value into a RowSet. | |
| 165 ** | |
| 166 ** The mallocFailed flag of the database connection is set if a | |
| 167 ** memory allocation fails. | |
| 168 */ | |
| 169 void sqlite3RowSetInsert(RowSet *p, i64 rowid){ | |
| 170 struct RowSetEntry *pEntry; /* The new entry */ | |
| 171 struct RowSetEntry *pLast; /* The last prior entry */ | |
| 172 assert( p!=0 ); | |
| 173 if( p->nFresh==0 ){ | |
| 174 struct RowSetChunk *pNew; | |
| 175 pNew = sqlite3DbMallocRaw(p->db, sizeof(*pNew)); | |
| 176 if( pNew==0 ){ | |
| 177 return; | |
| 178 } | |
| 179 pNew->pNextChunk = p->pChunk; | |
| 180 p->pChunk = pNew; | |
| 181 p->pFresh = pNew->aEntry; | |
| 182 p->nFresh = ROWSET_ENTRY_PER_CHUNK; | |
| 183 } | |
| 184 pEntry = p->pFresh++; | |
| 185 p->nFresh--; | |
| 186 pEntry->v = rowid; | |
| 187 pEntry->pRight = 0; | |
| 188 pLast = p->pLast; | |
| 189 if( pLast ){ | |
| 190 if( p->isSorted && rowid<=pLast->v ){ | |
| 191 p->isSorted = 0; | |
| 192 } | |
| 193 pLast->pRight = pEntry; | |
| 194 }else{ | |
| 195 assert( p->pEntry==0 ); /* Fires if INSERT after SMALLEST */ | |
| 196 p->pEntry = pEntry; | |
| 197 } | |
| 198 p->pLast = pEntry; | |
| 199 } | |
| 200 | |
| 201 /* | |
| 202 ** Merge two lists of RowSetEntry objects. Remove duplicates. | |
| 203 ** | |
| 204 ** The input lists are connected via pRight pointers and are | |
| 205 ** assumed to each already be in sorted order. | |
| 206 */ | |
| 207 static struct RowSetEntry *rowSetMerge( | |
| 208 struct RowSetEntry *pA, /* First sorted list to be merged */ | |
| 209 struct RowSetEntry *pB /* Second sorted list to be merged */ | |
| 210 ){ | |
| 211 struct RowSetEntry head; | |
| 212 struct RowSetEntry *pTail; | |
| 213 | |
| 214 pTail = &head; | |
| 215 while( pA && pB ){ | |
| 216 assert( pA->pRight==0 || pA->v<=pA->pRight->v ); | |
| 217 assert( pB->pRight==0 || pB->v<=pB->pRight->v ); | |
| 218 if( pA->v<pB->v ){ | |
| 219 pTail->pRight = pA; | |
| 220 pA = pA->pRight; | |
| 221 pTail = pTail->pRight; | |
| 222 }else if( pB->v<pA->v ){ | |
| 223 pTail->pRight = pB; | |
| 224 pB = pB->pRight; | |
| 225 pTail = pTail->pRight; | |
| 226 }else{ | |
| 227 pA = pA->pRight; | |
| 228 } | |
| 229 } | |
| 230 if( pA ){ | |
| 231 assert( pA->pRight==0 || pA->v<=pA->pRight->v ); | |
| 232 pTail->pRight = pA; | |
| 233 }else{ | |
| 234 assert( pB==0 || pB->pRight==0 || pB->v<=pB->pRight->v ); | |
| 235 pTail->pRight = pB; | |
| 236 } | |
| 237 return head.pRight; | |
| 238 } | |
| 239 | |
| 240 /* | |
| 241 ** Sort all elements on the pEntry list of the RowSet into ascending order. | |
| 242 */ | |
| 243 static void rowSetSort(RowSet *p){ | |
| 244 unsigned int i; | |
| 245 struct RowSetEntry *pEntry; | |
| 246 struct RowSetEntry *aBucket[40]; | |
| 247 | |
| 248 assert( p->isSorted==0 ); | |
| 249 memset(aBucket, 0, sizeof(aBucket)); | |
| 250 while( p->pEntry ){ | |
| 251 pEntry = p->pEntry; | |
| 252 p->pEntry = pEntry->pRight; | |
| 253 pEntry->pRight = 0; | |
| 254 for(i=0; aBucket[i]; i++){ | |
| 255 pEntry = rowSetMerge(aBucket[i], pEntry); | |
| 256 aBucket[i] = 0; | |
| 257 } | |
| 258 aBucket[i] = pEntry; | |
| 259 } | |
| 260 pEntry = 0; | |
| 261 for(i=0; i<sizeof(aBucket)/sizeof(aBucket[0]); i++){ | |
| 262 pEntry = rowSetMerge(pEntry, aBucket[i]); | |
| 263 } | |
| 264 p->pEntry = pEntry; | |
| 265 p->pLast = 0; | |
| 266 p->isSorted = 1; | |
| 267 } | |
| 268 | |
| 269 | |
| 270 /* | |
| 271 ** The input, pIn, is a binary tree (or subtree) of RowSetEntry objects. | |
| 272 ** Convert this tree into a linked list connected by the pRight pointers | |
| 273 ** and return pointers to the first and last elements of the new list. | |
| 274 */ | |
| 275 static void rowSetTreeToList( | |
| 276 struct RowSetEntry *pIn, /* Root of the input tree */ | |
| 277 struct RowSetEntry **ppFirst, /* Write head of the output list here */ | |
| 278 struct RowSetEntry **ppLast /* Write tail of the output list here */ | |
| 279 ){ | |
| 280 assert( pIn!=0 ); | |
| 281 if( pIn->pLeft ){ | |
| 282 struct RowSetEntry *p; | |
| 283 rowSetTreeToList(pIn->pLeft, ppFirst, &p); | |
| 284 p->pRight = pIn; | |
| 285 }else{ | |
| 286 *ppFirst = pIn; | |
| 287 } | |
| 288 if( pIn->pRight ){ | |
| 289 rowSetTreeToList(pIn->pRight, &pIn->pRight, ppLast); | |
| 290 }else{ | |
| 291 *ppLast = pIn; | |
| 292 } | |
| 293 assert( (*ppLast)->pRight==0 ); | |
| 294 } | |
| 295 | |
| 296 | |
| 297 /* | |
| 298 ** Convert a sorted list of elements (connected by pRight) into a binary | |
| 299 ** tree with depth of iDepth. A depth of 1 means the tree contains a single | |
| 300 ** node taken from the head of *ppList. A depth of 2 means a tree with | |
| 301 ** three nodes. And so forth. | |
| 302 ** | |
| 303 ** Use as many entries from the input list as required and update the | |
| 304 ** *ppList to point to the unused elements of the list. If the input | |
| 305 ** list contains too few elements, then construct an incomplete tree | |
| 306 ** and leave *ppList set to NULL. | |
| 307 ** | |
| 308 ** Return a pointer to the root of the constructed binary tree. | |
| 309 */ | |
| 310 static struct RowSetEntry *rowSetNDeepTree( | |
| 311 struct RowSetEntry **ppList, | |
| 312 int iDepth | |
| 313 ){ | |
| 314 struct RowSetEntry *p; /* Root of the new tree */ | |
| 315 struct RowSetEntry *pLeft; /* Left subtree */ | |
| 316 if( *ppList==0 ){ | |
| 317 return 0; | |
| 318 } | |
| 319 if( iDepth==1 ){ | |
| 320 p = *ppList; | |
| 321 *ppList = p->pRight; | |
| 322 p->pLeft = p->pRight = 0; | |
| 323 return p; | |
| 324 } | |
| 325 pLeft = rowSetNDeepTree(ppList, iDepth-1); | |
| 326 p = *ppList; | |
| 327 if( p==0 ){ | |
| 328 return pLeft; | |
| 329 } | |
| 330 p->pLeft = pLeft; | |
| 331 *ppList = p->pRight; | |
| 332 p->pRight = rowSetNDeepTree(ppList, iDepth-1); | |
| 333 return p; | |
| 334 } | |
| 335 | |
| 336 /* | |
| 337 ** Convert a sorted list of elements into a binary tree. Make the tree | |
| 338 ** as deep as it needs to be in order to contain the entire list. | |
| 339 */ | |
| 340 static struct RowSetEntry *rowSetListToTree(struct RowSetEntry *pList){ | |
| 341 int iDepth; /* Depth of the tree so far */ | |
| 342 struct RowSetEntry *p; /* Current tree root */ | |
| 343 struct RowSetEntry *pLeft; /* Left subtree */ | |
| 344 | |
| 345 assert( pList!=0 ); | |
| 346 p = pList; | |
| 347 pList = p->pRight; | |
| 348 p->pLeft = p->pRight = 0; | |
| 349 for(iDepth=1; pList; iDepth++){ | |
| 350 pLeft = p; | |
| 351 p = pList; | |
| 352 pList = p->pRight; | |
| 353 p->pLeft = pLeft; | |
| 354 p->pRight = rowSetNDeepTree(&pList, iDepth); | |
| 355 } | |
| 356 return p; | |
| 357 } | |
| 358 | |
| 359 /* | |
| 360 ** Convert the list in p->pEntry into a sorted list if it is not | |
| 361 ** sorted already. If there is a binary tree on p->pTree, then | |
| 362 ** convert it into a list too and merge it into the p->pEntry list. | |
| 363 */ | |
| 364 static void rowSetToList(RowSet *p){ | |
| 365 if( !p->isSorted ){ | |
| 366 rowSetSort(p); | |
| 367 } | |
| 368 if( p->pTree ){ | |
| 369 struct RowSetEntry *pHead, *pTail; | |
| 370 rowSetTreeToList(p->pTree, &pHead, &pTail); | |
| 371 p->pTree = 0; | |
| 372 p->pEntry = rowSetMerge(p->pEntry, pHead); | |
| 373 } | |
| 374 } | |
| 375 | |
| 376 /* | |
| 377 ** Extract the smallest element from the RowSet. | |
| 378 ** Write the element into *pRowid. Return 1 on success. Return | |
| 379 ** 0 if the RowSet is already empty. | |
| 380 ** | |
| 381 ** After this routine has been called, the sqlite3RowSetInsert() | |
| 382 ** routine may not be called again. | |
| 383 */ | |
| 384 int sqlite3RowSetNext(RowSet *p, i64 *pRowid){ | |
| 385 rowSetToList(p); | |
| 386 if( p->pEntry ){ | |
| 387 *pRowid = p->pEntry->v; | |
| 388 p->pEntry = p->pEntry->pRight; | |
| 389 if( p->pEntry==0 ){ | |
| 390 sqlite3RowSetClear(p); | |
| 391 } | |
| 392 return 1; | |
| 393 }else{ | |
| 394 return 0; | |
| 395 } | |
| 396 } | |
| 397 | |
| 398 /* | |
| 399 ** Check to see if element iRowid was inserted into the the rowset as | |
| 400 ** part of any insert batch prior to iBatch. Return 1 or 0. | |
| 401 */ | |
| 402 int sqlite3RowSetTest(RowSet *pRowSet, u8 iBatch, sqlite3_int64 iRowid){ | |
| 403 struct RowSetEntry *p; | |
| 404 if( iBatch!=pRowSet->iBatch ){ | |
| 405 if( pRowSet->pEntry ){ | |
| 406 rowSetToList(pRowSet); | |
| 407 pRowSet->pTree = rowSetListToTree(pRowSet->pEntry); | |
| 408 pRowSet->pEntry = 0; | |
| 409 pRowSet->pLast = 0; | |
| 410 } | |
| 411 pRowSet->iBatch = iBatch; | |
| 412 } | |
| 413 p = pRowSet->pTree; | |
| 414 while( p ){ | |
| 415 if( p->v<iRowid ){ | |
| 416 p = p->pRight; | |
| 417 }else if( p->v>iRowid ){ | |
| 418 p = p->pLeft; | |
| 419 }else{ | |
| 420 return 1; | |
| 421 } | |
| 422 } | |
| 423 return 0; | |
| 424 } | |
| OLD | NEW |
|---|
Chromium Code Reviews
Issue 3108030:
Move bundled copy of sqlite one level deeper to better separate it... (Closed)
Base URL: svn://svn.chromium.org/chrome/trunk/src/