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#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*/ 80struct RowSetEntry { 81 i64 v; /* ROWID value for this entry */ 82 struct RowSetEntry *pRight; /* Right subtree (larger entries) or list */ 83 struct RowSetEntry *pLeft; /* Left subtree (smaller entries) */ 84}; 85 86/* 87** RowSetEntry objects are allocated in large chunks (instances of the 88** following structure) to reduce memory allocation overhead. The 89** chunks are kept on a linked list so that they can be deallocated 90** when the RowSet is destroyed. 91*/ 92struct RowSetChunk { 93 struct RowSetChunk *pNextChunk; /* Next chunk on list of them all */ 94 struct RowSetEntry aEntry[ROWSET_ENTRY_PER_CHUNK]; /* Allocated entries */ 95}; 96 97/* 98** A RowSet in an instance of the following structure. 99** 100** A typedef of this structure if found in sqliteInt.h. 101*/ 102struct RowSet { 103 struct RowSetChunk *pChunk; /* List of all chunk allocations */ 104 sqlite3 *db; /* The database connection */ 105 struct RowSetEntry *pEntry; /* List of entries using pRight */ 106 struct RowSetEntry *pLast; /* Last entry on the pEntry list */ 107 struct RowSetEntry *pFresh; /* Source of new entry objects */ 108 struct RowSetEntry *pTree; /* Binary tree of entries */ 109 u16 nFresh; /* Number of objects on pFresh */ 110 u8 isSorted; /* True if pEntry is sorted */ 111 u8 iBatch; /* Current insert batch */ 112}; 113 114/* 115** Turn bulk memory into a RowSet object. N bytes of memory 116** are available at pSpace. The db pointer is used as a memory context 117** for any subsequent allocations that need to occur. 118** Return a pointer to the new RowSet object. 119** 120** It must be the case that N is sufficient to make a Rowset. If not 121** an assertion fault occurs. 122** 123** If N is larger than the minimum, use the surplus as an initial 124** allocation of entries available to be filled. 125*/ 126RowSet *sqlite3RowSetInit(sqlite3 *db, void *pSpace, unsigned int N){ 127 RowSet *p; 128 assert( N >= ROUND8(sizeof(*p)) ); 129 p = pSpace; 130 p->pChunk = 0; 131 p->db = db; 132 p->pEntry = 0; 133 p->pLast = 0; 134 p->pTree = 0; 135 p->pFresh = (struct RowSetEntry*)(ROUND8(sizeof(*p)) + (char*)p); 136 p->nFresh = (u16)((N - ROUND8(sizeof(*p)))/sizeof(struct RowSetEntry)); 137 p->isSorted = 1; 138 p->iBatch = 0; 139 return p; 140} 141 142/* 143** Deallocate all chunks from a RowSet. This frees all memory that 144** the RowSet has allocated over its lifetime. This routine is 145** the destructor for the RowSet. 146*/ 147void sqlite3RowSetClear(RowSet *p){ 148 struct RowSetChunk *pChunk, *pNextChunk; 149 for(pChunk=p->pChunk; pChunk; pChunk = pNextChunk){ 150 pNextChunk = pChunk->pNextChunk; 151 sqlite3DbFree(p->db, pChunk); 152 } 153 p->pChunk = 0; 154 p->nFresh = 0; 155 p->pEntry = 0; 156 p->pLast = 0; 157 p->pTree = 0; 158 p->isSorted = 1; 159} 160 161/* 162** Insert a new value into a RowSet. 163** 164** The mallocFailed flag of the database connection is set if a 165** memory allocation fails. 166*/ 167void sqlite3RowSetInsert(RowSet *p, i64 rowid){ 168 struct RowSetEntry *pEntry; /* The new entry */ 169 struct RowSetEntry *pLast; /* The last prior entry */ 170 assert( p!=0 ); 171 if( p->nFresh==0 ){ 172 struct RowSetChunk *pNew; 173 pNew = sqlite3DbMallocRaw(p->db, sizeof(*pNew)); 174 if( pNew==0 ){ 175 return; 176 } 177 pNew->pNextChunk = p->pChunk; 178 p->pChunk = pNew; 179 p->pFresh = pNew->aEntry; 180 p->nFresh = ROWSET_ENTRY_PER_CHUNK; 181 } 182 pEntry = p->pFresh++; 183 p->nFresh--; 184 pEntry->v = rowid; 185 pEntry->pRight = 0; 186 pLast = p->pLast; 187 if( pLast ){ 188 if( p->isSorted && rowid<=pLast->v ){ 189 p->isSorted = 0; 190 } 191 pLast->pRight = pEntry; 192 }else{ 193 assert( p->pEntry==0 ); /* Fires if INSERT after SMALLEST */ 194 p->pEntry = pEntry; 195 } 196 p->pLast = pEntry; 197} 198 199/* 200** Merge two lists of RowSetEntry objects. Remove duplicates. 201** 202** The input lists are connected via pRight pointers and are 203** assumed to each already be in sorted order. 204*/ 205static struct RowSetEntry *rowSetMerge( 206 struct RowSetEntry *pA, /* First sorted list to be merged */ 207 struct RowSetEntry *pB /* Second sorted list to be merged */ 208){ 209 struct RowSetEntry head; 210 struct RowSetEntry *pTail; 211 212 pTail = &head; 213 while( pA && pB ){ 214 assert( pA->pRight==0 || pA->v<=pA->pRight->v ); 215 assert( pB->pRight==0 || pB->v<=pB->pRight->v ); 216 if( pA->v<pB->v ){ 217 pTail->pRight = pA; 218 pA = pA->pRight; 219 pTail = pTail->pRight; 220 }else if( pB->v<pA->v ){ 221 pTail->pRight = pB; 222 pB = pB->pRight; 223 pTail = pTail->pRight; 224 }else{ 225 pA = pA->pRight; 226 } 227 } 228 if( pA ){ 229 assert( pA->pRight==0 || pA->v<=pA->pRight->v ); 230 pTail->pRight = pA; 231 }else{ 232 assert( pB==0 || pB->pRight==0 || pB->v<=pB->pRight->v ); 233 pTail->pRight = pB; 234 } 235 return head.pRight; 236} 237 238/* 239** Sort all elements on the pEntry list of the RowSet into ascending order. 240*/ 241static void rowSetSort(RowSet *p){ 242 unsigned int i; 243 struct RowSetEntry *pEntry; 244 struct RowSetEntry *aBucket[40]; 245 246 assert( p->isSorted==0 ); 247 memset(aBucket, 0, sizeof(aBucket)); 248 while( p->pEntry ){ 249 pEntry = p->pEntry; 250 p->pEntry = pEntry->pRight; 251 pEntry->pRight = 0; 252 for(i=0; aBucket[i]; i++){ 253 pEntry = rowSetMerge(aBucket[i], pEntry); 254 aBucket[i] = 0; 255 } 256 aBucket[i] = pEntry; 257 } 258 pEntry = 0; 259 for(i=0; i<sizeof(aBucket)/sizeof(aBucket[0]); i++){ 260 pEntry = rowSetMerge(pEntry, aBucket[i]); 261 } 262 p->pEntry = pEntry; 263 p->pLast = 0; 264 p->isSorted = 1; 265} 266 267 268/* 269** The input, pIn, is a binary tree (or subtree) of RowSetEntry objects. 270** Convert this tree into a linked list connected by the pRight pointers 271** and return pointers to the first and last elements of the new list. 272*/ 273static void rowSetTreeToList( 274 struct RowSetEntry *pIn, /* Root of the input tree */ 275 struct RowSetEntry **ppFirst, /* Write head of the output list here */ 276 struct RowSetEntry **ppLast /* Write tail of the output list here */ 277){ 278 assert( pIn!=0 ); 279 if( pIn->pLeft ){ 280 struct RowSetEntry *p; 281 rowSetTreeToList(pIn->pLeft, ppFirst, &p); 282 p->pRight = pIn; 283 }else{ 284 *ppFirst = pIn; 285 } 286 if( pIn->pRight ){ 287 rowSetTreeToList(pIn->pRight, &pIn->pRight, ppLast); 288 }else{ 289 *ppLast = pIn; 290 } 291 assert( (*ppLast)->pRight==0 ); 292} 293 294 295/* 296** Convert a sorted list of elements (connected by pRight) into a binary 297** tree with depth of iDepth. A depth of 1 means the tree contains a single 298** node taken from the head of *ppList. A depth of 2 means a tree with 299** three nodes. And so forth. 300** 301** Use as many entries from the input list as required and update the 302** *ppList to point to the unused elements of the list. If the input 303** list contains too few elements, then construct an incomplete tree 304** and leave *ppList set to NULL. 305** 306** Return a pointer to the root of the constructed binary tree. 307*/ 308static struct RowSetEntry *rowSetNDeepTree( 309 struct RowSetEntry **ppList, 310 int iDepth 311){ 312 struct RowSetEntry *p; /* Root of the new tree */ 313 struct RowSetEntry *pLeft; /* Left subtree */ 314 if( *ppList==0 ){ 315 return 0; 316 } 317 if( iDepth==1 ){ 318 p = *ppList; 319 *ppList = p->pRight; 320 p->pLeft = p->pRight = 0; 321 return p; 322 } 323 pLeft = rowSetNDeepTree(ppList, iDepth-1); 324 p = *ppList; 325 if( p==0 ){ 326 return pLeft; 327 } 328 p->pLeft = pLeft; 329 *ppList = p->pRight; 330 p->pRight = rowSetNDeepTree(ppList, iDepth-1); 331 return p; 332} 333 334/* 335** Convert a sorted list of elements into a binary tree. Make the tree 336** as deep as it needs to be in order to contain the entire list. 337*/ 338static struct RowSetEntry *rowSetListToTree(struct RowSetEntry *pList){ 339 int iDepth; /* Depth of the tree so far */ 340 struct RowSetEntry *p; /* Current tree root */ 341 struct RowSetEntry *pLeft; /* Left subtree */ 342 343 assert( pList!=0 ); 344 p = pList; 345 pList = p->pRight; 346 p->pLeft = p->pRight = 0; 347 for(iDepth=1; pList; iDepth++){ 348 pLeft = p; 349 p = pList; 350 pList = p->pRight; 351 p->pLeft = pLeft; 352 p->pRight = rowSetNDeepTree(&pList, iDepth); 353 } 354 return p; 355} 356 357/* 358** Convert the list in p->pEntry into a sorted list if it is not 359** sorted already. If there is a binary tree on p->pTree, then 360** convert it into a list too and merge it into the p->pEntry list. 361*/ 362static void rowSetToList(RowSet *p){ 363 if( !p->isSorted ){ 364 rowSetSort(p); 365 } 366 if( p->pTree ){ 367 struct RowSetEntry *pHead, *pTail; 368 rowSetTreeToList(p->pTree, &pHead, &pTail); 369 p->pTree = 0; 370 p->pEntry = rowSetMerge(p->pEntry, pHead); 371 } 372} 373 374/* 375** Extract the smallest element from the RowSet. 376** Write the element into *pRowid. Return 1 on success. Return 377** 0 if the RowSet is already empty. 378** 379** After this routine has been called, the sqlite3RowSetInsert() 380** routine may not be called again. 381*/ 382int sqlite3RowSetNext(RowSet *p, i64 *pRowid){ 383 rowSetToList(p); 384 if( p->pEntry ){ 385 *pRowid = p->pEntry->v; 386 p->pEntry = p->pEntry->pRight; 387 if( p->pEntry==0 ){ 388 sqlite3RowSetClear(p); 389 } 390 return 1; 391 }else{ 392 return 0; 393 } 394} 395 396/* 397** Check to see if element iRowid was inserted into the the rowset as 398** part of any insert batch prior to iBatch. Return 1 or 0. 399*/ 400int sqlite3RowSetTest(RowSet *pRowSet, u8 iBatch, sqlite3_int64 iRowid){ 401 struct RowSetEntry *p; 402 if( iBatch!=pRowSet->iBatch ){ 403 if( pRowSet->pEntry ){ 404 rowSetToList(pRowSet); 405 pRowSet->pTree = rowSetListToTree(pRowSet->pEntry); 406 pRowSet->pEntry = 0; 407 pRowSet->pLast = 0; 408 } 409 pRowSet->iBatch = iBatch; 410 } 411 p = pRowSet->pTree; 412 while( p ){ 413 if( p->v<iRowid ){ 414 p = p->pRight; 415 }else if( p->v>iRowid ){ 416 p = p->pLeft; 417 }else{ 418 return 1; 419 } 420 } 421 return 0; 422} 423