| 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. (Sometimes 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 #include "sqliteInt.h" | |
| 64 | |
| 65 | |
| 66 /* | |
| 67 ** Target size for allocation chunks. | |
| 68 */ | |
| 69 #define ROWSET_ALLOCATION_SIZE 1024 | |
| 70 | |
| 71 /* | |
| 72 ** The number of rowset entries per allocation chunk. | |
| 73 */ | |
| 74 #define ROWSET_ENTRY_PER_CHUNK \ | |
| 75 ((ROWSET_ALLOCATION_SIZE-8)/sizeof(struct RowSetEntry)) | |
| 76 | |
| 77 /* | |
| 78 ** Each entry in a RowSet is an instance of the following object. | |
| 79 ** | |
| 80 ** This same object is reused to store a linked list of trees of RowSetEntry | |
| 81 ** objects. In that alternative use, pRight points to the next entry | |
| 82 ** in the list, pLeft points to the tree, and v is unused. The | |
| 83 ** RowSet.pForest value points to the head of this forest list. | |
| 84 */ | |
| 85 struct RowSetEntry { | |
| 86 i64 v; /* ROWID value for this entry */ | |
| 87 struct RowSetEntry *pRight; /* Right subtree (larger entries) or list */ | |
| 88 struct RowSetEntry *pLeft; /* Left subtree (smaller entries) */ | |
| 89 }; | |
| 90 | |
| 91 /* | |
| 92 ** RowSetEntry objects are allocated in large chunks (instances of the | |
| 93 ** following structure) to reduce memory allocation overhead. The | |
| 94 ** chunks are kept on a linked list so that they can be deallocated | |
| 95 ** when the RowSet is destroyed. | |
| 96 */ | |
| 97 struct RowSetChunk { | |
| 98 struct RowSetChunk *pNextChunk; /* Next chunk on list of them all */ | |
| 99 struct RowSetEntry aEntry[ROWSET_ENTRY_PER_CHUNK]; /* Allocated entries */ | |
| 100 }; | |
| 101 | |
| 102 /* | |
| 103 ** A RowSet in an instance of the following structure. | |
| 104 ** | |
| 105 ** A typedef of this structure if found in sqliteInt.h. | |
| 106 */ | |
| 107 struct RowSet { | |
| 108 struct RowSetChunk *pChunk; /* List of all chunk allocations */ | |
| 109 sqlite3 *db; /* The database connection */ | |
| 110 struct RowSetEntry *pEntry; /* List of entries using pRight */ | |
| 111 struct RowSetEntry *pLast; /* Last entry on the pEntry list */ | |
| 112 struct RowSetEntry *pFresh; /* Source of new entry objects */ | |
| 113 struct RowSetEntry *pForest; /* List of binary trees of entries */ | |
| 114 u16 nFresh; /* Number of objects on pFresh */ | |
| 115 u16 rsFlags; /* Various flags */ | |
| 116 int iBatch; /* Current insert batch */ | |
| 117 }; | |
| 118 | |
| 119 /* | |
| 120 ** Allowed values for RowSet.rsFlags | |
| 121 */ | |
| 122 #define ROWSET_SORTED 0x01 /* True if RowSet.pEntry is sorted */ | |
| 123 #define ROWSET_NEXT 0x02 /* True if sqlite3RowSetNext() has been called */ | |
| 124 | |
| 125 /* | |
| 126 ** Turn bulk memory into a RowSet object. N bytes of memory | |
| 127 ** are available at pSpace. The db pointer is used as a memory context | |
| 128 ** for any subsequent allocations that need to occur. | |
| 129 ** Return a pointer to the new RowSet object. | |
| 130 ** | |
| 131 ** It must be the case that N is sufficient to make a Rowset. If not | |
| 132 ** an assertion fault occurs. | |
| 133 ** | |
| 134 ** If N is larger than the minimum, use the surplus as an initial | |
| 135 ** allocation of entries available to be filled. | |
| 136 */ | |
| 137 RowSet *sqlite3RowSetInit(sqlite3 *db, void *pSpace, unsigned int N){ | |
| 138 RowSet *p; | |
| 139 assert( N >= ROUND8(sizeof(*p)) ); | |
| 140 p = pSpace; | |
| 141 p->pChunk = 0; | |
| 142 p->db = db; | |
| 143 p->pEntry = 0; | |
| 144 p->pLast = 0; | |
| 145 p->pForest = 0; | |
| 146 p->pFresh = (struct RowSetEntry*)(ROUND8(sizeof(*p)) + (char*)p); | |
| 147 p->nFresh = (u16)((N - ROUND8(sizeof(*p)))/sizeof(struct RowSetEntry)); | |
| 148 p->rsFlags = ROWSET_SORTED; | |
| 149 p->iBatch = 0; | |
| 150 return p; | |
| 151 } | |
| 152 | |
| 153 /* | |
| 154 ** Deallocate all chunks from a RowSet. This frees all memory that | |
| 155 ** the RowSet has allocated over its lifetime. This routine is | |
| 156 ** the destructor for the RowSet. | |
| 157 */ | |
| 158 void sqlite3RowSetClear(RowSet *p){ | |
| 159 struct RowSetChunk *pChunk, *pNextChunk; | |
| 160 for(pChunk=p->pChunk; pChunk; pChunk = pNextChunk){ | |
| 161 pNextChunk = pChunk->pNextChunk; | |
| 162 sqlite3DbFree(p->db, pChunk); | |
| 163 } | |
| 164 p->pChunk = 0; | |
| 165 p->nFresh = 0; | |
| 166 p->pEntry = 0; | |
| 167 p->pLast = 0; | |
| 168 p->pForest = 0; | |
| 169 p->rsFlags = ROWSET_SORTED; | |
| 170 } | |
| 171 | |
| 172 /* | |
| 173 ** Allocate a new RowSetEntry object that is associated with the | |
| 174 ** given RowSet. Return a pointer to the new and completely uninitialized | |
| 175 ** objected. | |
| 176 ** | |
| 177 ** In an OOM situation, the RowSet.db->mallocFailed flag is set and this | |
| 178 ** routine returns NULL. | |
| 179 */ | |
| 180 static struct RowSetEntry *rowSetEntryAlloc(RowSet *p){ | |
| 181 assert( p!=0 ); | |
| 182 if( p->nFresh==0 ){ | |
| 183 struct RowSetChunk *pNew; | |
| 184 pNew = sqlite3DbMallocRaw(p->db, sizeof(*pNew)); | |
| 185 if( pNew==0 ){ | |
| 186 return 0; | |
| 187 } | |
| 188 pNew->pNextChunk = p->pChunk; | |
| 189 p->pChunk = pNew; | |
| 190 p->pFresh = pNew->aEntry; | |
| 191 p->nFresh = ROWSET_ENTRY_PER_CHUNK; | |
| 192 } | |
| 193 p->nFresh--; | |
| 194 return p->pFresh++; | |
| 195 } | |
| 196 | |
| 197 /* | |
| 198 ** Insert a new value into a RowSet. | |
| 199 ** | |
| 200 ** The mallocFailed flag of the database connection is set if a | |
| 201 ** memory allocation fails. | |
| 202 */ | |
| 203 void sqlite3RowSetInsert(RowSet *p, i64 rowid){ | |
| 204 struct RowSetEntry *pEntry; /* The new entry */ | |
| 205 struct RowSetEntry *pLast; /* The last prior entry */ | |
| 206 | |
| 207 /* This routine is never called after sqlite3RowSetNext() */ | |
| 208 assert( p!=0 && (p->rsFlags & ROWSET_NEXT)==0 ); | |
| 209 | |
| 210 pEntry = rowSetEntryAlloc(p); | |
| 211 if( pEntry==0 ) return; | |
| 212 pEntry->v = rowid; | |
| 213 pEntry->pRight = 0; | |
| 214 pLast = p->pLast; | |
| 215 if( pLast ){ | |
| 216 if( (p->rsFlags & ROWSET_SORTED)!=0 && rowid<=pLast->v ){ | |
| 217 p->rsFlags &= ~ROWSET_SORTED; | |
| 218 } | |
| 219 pLast->pRight = pEntry; | |
| 220 }else{ | |
| 221 p->pEntry = pEntry; | |
| 222 } | |
| 223 p->pLast = pEntry; | |
| 224 } | |
| 225 | |
| 226 /* | |
| 227 ** Merge two lists of RowSetEntry objects. Remove duplicates. | |
| 228 ** | |
| 229 ** The input lists are connected via pRight pointers and are | |
| 230 ** assumed to each already be in sorted order. | |
| 231 */ | |
| 232 static struct RowSetEntry *rowSetEntryMerge( | |
| 233 struct RowSetEntry *pA, /* First sorted list to be merged */ | |
| 234 struct RowSetEntry *pB /* Second sorted list to be merged */ | |
| 235 ){ | |
| 236 struct RowSetEntry head; | |
| 237 struct RowSetEntry *pTail; | |
| 238 | |
| 239 pTail = &head; | |
| 240 while( pA && pB ){ | |
| 241 assert( pA->pRight==0 || pA->v<=pA->pRight->v ); | |
| 242 assert( pB->pRight==0 || pB->v<=pB->pRight->v ); | |
| 243 if( pA->v<pB->v ){ | |
| 244 pTail->pRight = pA; | |
| 245 pA = pA->pRight; | |
| 246 pTail = pTail->pRight; | |
| 247 }else if( pB->v<pA->v ){ | |
| 248 pTail->pRight = pB; | |
| 249 pB = pB->pRight; | |
| 250 pTail = pTail->pRight; | |
| 251 }else{ | |
| 252 pA = pA->pRight; | |
| 253 } | |
| 254 } | |
| 255 if( pA ){ | |
| 256 assert( pA->pRight==0 || pA->v<=pA->pRight->v ); | |
| 257 pTail->pRight = pA; | |
| 258 }else{ | |
| 259 assert( pB==0 || pB->pRight==0 || pB->v<=pB->pRight->v ); | |
| 260 pTail->pRight = pB; | |
| 261 } | |
| 262 return head.pRight; | |
| 263 } | |
| 264 | |
| 265 /* | |
| 266 ** Sort all elements on the list of RowSetEntry objects into order of | |
| 267 ** increasing v. | |
| 268 */ | |
| 269 static struct RowSetEntry *rowSetEntrySort(struct RowSetEntry *pIn){ | |
| 270 unsigned int i; | |
| 271 struct RowSetEntry *pNext, *aBucket[40]; | |
| 272 | |
| 273 memset(aBucket, 0, sizeof(aBucket)); | |
| 274 while( pIn ){ | |
| 275 pNext = pIn->pRight; | |
| 276 pIn->pRight = 0; | |
| 277 for(i=0; aBucket[i]; i++){ | |
| 278 pIn = rowSetEntryMerge(aBucket[i], pIn); | |
| 279 aBucket[i] = 0; | |
| 280 } | |
| 281 aBucket[i] = pIn; | |
| 282 pIn = pNext; | |
| 283 } | |
| 284 pIn = 0; | |
| 285 for(i=0; i<sizeof(aBucket)/sizeof(aBucket[0]); i++){ | |
| 286 pIn = rowSetEntryMerge(pIn, aBucket[i]); | |
| 287 } | |
| 288 return pIn; | |
| 289 } | |
| 290 | |
| 291 | |
| 292 /* | |
| 293 ** The input, pIn, is a binary tree (or subtree) of RowSetEntry objects. | |
| 294 ** Convert this tree into a linked list connected by the pRight pointers | |
| 295 ** and return pointers to the first and last elements of the new list. | |
| 296 */ | |
| 297 static void rowSetTreeToList( | |
| 298 struct RowSetEntry *pIn, /* Root of the input tree */ | |
| 299 struct RowSetEntry **ppFirst, /* Write head of the output list here */ | |
| 300 struct RowSetEntry **ppLast /* Write tail of the output list here */ | |
| 301 ){ | |
| 302 assert( pIn!=0 ); | |
| 303 if( pIn->pLeft ){ | |
| 304 struct RowSetEntry *p; | |
| 305 rowSetTreeToList(pIn->pLeft, ppFirst, &p); | |
| 306 p->pRight = pIn; | |
| 307 }else{ | |
| 308 *ppFirst = pIn; | |
| 309 } | |
| 310 if( pIn->pRight ){ | |
| 311 rowSetTreeToList(pIn->pRight, &pIn->pRight, ppLast); | |
| 312 }else{ | |
| 313 *ppLast = pIn; | |
| 314 } | |
| 315 assert( (*ppLast)->pRight==0 ); | |
| 316 } | |
| 317 | |
| 318 | |
| 319 /* | |
| 320 ** Convert a sorted list of elements (connected by pRight) into a binary | |
| 321 ** tree with depth of iDepth. A depth of 1 means the tree contains a single | |
| 322 ** node taken from the head of *ppList. A depth of 2 means a tree with | |
| 323 ** three nodes. And so forth. | |
| 324 ** | |
| 325 ** Use as many entries from the input list as required and update the | |
| 326 ** *ppList to point to the unused elements of the list. If the input | |
| 327 ** list contains too few elements, then construct an incomplete tree | |
| 328 ** and leave *ppList set to NULL. | |
| 329 ** | |
| 330 ** Return a pointer to the root of the constructed binary tree. | |
| 331 */ | |
| 332 static struct RowSetEntry *rowSetNDeepTree( | |
| 333 struct RowSetEntry **ppList, | |
| 334 int iDepth | |
| 335 ){ | |
| 336 struct RowSetEntry *p; /* Root of the new tree */ | |
| 337 struct RowSetEntry *pLeft; /* Left subtree */ | |
| 338 if( *ppList==0 ){ | |
| 339 return 0; | |
| 340 } | |
| 341 if( iDepth==1 ){ | |
| 342 p = *ppList; | |
| 343 *ppList = p->pRight; | |
| 344 p->pLeft = p->pRight = 0; | |
| 345 return p; | |
| 346 } | |
| 347 pLeft = rowSetNDeepTree(ppList, iDepth-1); | |
| 348 p = *ppList; | |
| 349 if( p==0 ){ | |
| 350 return pLeft; | |
| 351 } | |
| 352 p->pLeft = pLeft; | |
| 353 *ppList = p->pRight; | |
| 354 p->pRight = rowSetNDeepTree(ppList, iDepth-1); | |
| 355 return p; | |
| 356 } | |
| 357 | |
| 358 /* | |
| 359 ** Convert a sorted list of elements into a binary tree. Make the tree | |
| 360 ** as deep as it needs to be in order to contain the entire list. | |
| 361 */ | |
| 362 static struct RowSetEntry *rowSetListToTree(struct RowSetEntry *pList){ | |
| 363 int iDepth; /* Depth of the tree so far */ | |
| 364 struct RowSetEntry *p; /* Current tree root */ | |
| 365 struct RowSetEntry *pLeft; /* Left subtree */ | |
| 366 | |
| 367 assert( pList!=0 ); | |
| 368 p = pList; | |
| 369 pList = p->pRight; | |
| 370 p->pLeft = p->pRight = 0; | |
| 371 for(iDepth=1; pList; iDepth++){ | |
| 372 pLeft = p; | |
| 373 p = pList; | |
| 374 pList = p->pRight; | |
| 375 p->pLeft = pLeft; | |
| 376 p->pRight = rowSetNDeepTree(&pList, iDepth); | |
| 377 } | |
| 378 return p; | |
| 379 } | |
| 380 | |
| 381 /* | |
| 382 ** Take all the entries on p->pEntry and on the trees in p->pForest and | |
| 383 ** sort them all together into one big ordered list on p->pEntry. | |
| 384 ** | |
| 385 ** This routine should only be called once in the life of a RowSet. | |
| 386 */ | |
| 387 static void rowSetToList(RowSet *p){ | |
| 388 | |
| 389 /* This routine is called only once */ | |
| 390 assert( p!=0 && (p->rsFlags & ROWSET_NEXT)==0 ); | |
| 391 | |
| 392 if( (p->rsFlags & ROWSET_SORTED)==0 ){ | |
| 393 p->pEntry = rowSetEntrySort(p->pEntry); | |
| 394 } | |
| 395 | |
| 396 /* While this module could theoretically support it, sqlite3RowSetNext() | |
| 397 ** is never called after sqlite3RowSetText() for the same RowSet. So | |
| 398 ** there is never a forest to deal with. Should this change, simply | |
| 399 ** remove the assert() and the #if 0. */ | |
| 400 assert( p->pForest==0 ); | |
| 401 #if 0 | |
| 402 while( p->pForest ){ | |
| 403 struct RowSetEntry *pTree = p->pForest->pLeft; | |
| 404 if( pTree ){ | |
| 405 struct RowSetEntry *pHead, *pTail; | |
| 406 rowSetTreeToList(pTree, &pHead, &pTail); | |
| 407 p->pEntry = rowSetEntryMerge(p->pEntry, pHead); | |
| 408 } | |
| 409 p->pForest = p->pForest->pRight; | |
| 410 } | |
| 411 #endif | |
| 412 p->rsFlags |= ROWSET_NEXT; /* Verify this routine is never called again */ | |
| 413 } | |
| 414 | |
| 415 /* | |
| 416 ** Extract the smallest element from the RowSet. | |
| 417 ** Write the element into *pRowid. Return 1 on success. Return | |
| 418 ** 0 if the RowSet is already empty. | |
| 419 ** | |
| 420 ** After this routine has been called, the sqlite3RowSetInsert() | |
| 421 ** routine may not be called again. | |
| 422 */ | |
| 423 int sqlite3RowSetNext(RowSet *p, i64 *pRowid){ | |
| 424 assert( p!=0 ); | |
| 425 | |
| 426 /* Merge the forest into a single sorted list on first call */ | |
| 427 if( (p->rsFlags & ROWSET_NEXT)==0 ) rowSetToList(p); | |
| 428 | |
| 429 /* Return the next entry on the list */ | |
| 430 if( p->pEntry ){ | |
| 431 *pRowid = p->pEntry->v; | |
| 432 p->pEntry = p->pEntry->pRight; | |
| 433 if( p->pEntry==0 ){ | |
| 434 sqlite3RowSetClear(p); | |
| 435 } | |
| 436 return 1; | |
| 437 }else{ | |
| 438 return 0; | |
| 439 } | |
| 440 } | |
| 441 | |
| 442 /* | |
| 443 ** Check to see if element iRowid was inserted into the rowset as | |
| 444 ** part of any insert batch prior to iBatch. Return 1 or 0. | |
| 445 ** | |
| 446 ** If this is the first test of a new batch and if there exist entries | |
| 447 ** on pRowSet->pEntry, then sort those entries into the forest at | |
| 448 ** pRowSet->pForest so that they can be tested. | |
| 449 */ | |
| 450 int sqlite3RowSetTest(RowSet *pRowSet, int iBatch, sqlite3_int64 iRowid){ | |
| 451 struct RowSetEntry *p, *pTree; | |
| 452 | |
| 453 /* This routine is never called after sqlite3RowSetNext() */ | |
| 454 assert( pRowSet!=0 && (pRowSet->rsFlags & ROWSET_NEXT)==0 ); | |
| 455 | |
| 456 /* Sort entries into the forest on the first test of a new batch | |
| 457 */ | |
| 458 if( iBatch!=pRowSet->iBatch ){ | |
| 459 p = pRowSet->pEntry; | |
| 460 if( p ){ | |
| 461 struct RowSetEntry **ppPrevTree = &pRowSet->pForest; | |
| 462 if( (pRowSet->rsFlags & ROWSET_SORTED)==0 ){ | |
| 463 p = rowSetEntrySort(p); | |
| 464 } | |
| 465 for(pTree = pRowSet->pForest; pTree; pTree=pTree->pRight){ | |
| 466 ppPrevTree = &pTree->pRight; | |
| 467 if( pTree->pLeft==0 ){ | |
| 468 pTree->pLeft = rowSetListToTree(p); | |
| 469 break; | |
| 470 }else{ | |
| 471 struct RowSetEntry *pAux, *pTail; | |
| 472 rowSetTreeToList(pTree->pLeft, &pAux, &pTail); | |
| 473 pTree->pLeft = 0; | |
| 474 p = rowSetEntryMerge(pAux, p); | |
| 475 } | |
| 476 } | |
| 477 if( pTree==0 ){ | |
| 478 *ppPrevTree = pTree = rowSetEntryAlloc(pRowSet); | |
| 479 if( pTree ){ | |
| 480 pTree->v = 0; | |
| 481 pTree->pRight = 0; | |
| 482 pTree->pLeft = rowSetListToTree(p); | |
| 483 } | |
| 484 } | |
| 485 pRowSet->pEntry = 0; | |
| 486 pRowSet->pLast = 0; | |
| 487 pRowSet->rsFlags |= ROWSET_SORTED; | |
| 488 } | |
| 489 pRowSet->iBatch = iBatch; | |
| 490 } | |
| 491 | |
| 492 /* Test to see if the iRowid value appears anywhere in the forest. | |
| 493 ** Return 1 if it does and 0 if not. | |
| 494 */ | |
| 495 for(pTree = pRowSet->pForest; pTree; pTree=pTree->pRight){ | |
| 496 p = pTree->pLeft; | |
| 497 while( p ){ | |
| 498 if( p->v<iRowid ){ | |
| 499 p = p->pRight; | |
| 500 }else if( p->v>iRowid ){ | |
| 501 p = p->pLeft; | |
| 502 }else{ | |
| 503 return 1; | |
| 504 } | |
| 505 } | |
| 506 } | |
| 507 return 0; | |
| 508 } | |
| OLD | NEW |
|---|
Chromium Code Reviews
Issue 2363173002:
[sqlite] Remove obsolete reference version 3.8.7.4. (Closed)
