Merge Chromium + Blink git repositories
[chromium-blink-merge.git] / third_party / sqlite / sqlite-src-3080704 / src / rowset.c
blobff5593892ab3f5af79ff1d5a768c6529a82fadf9
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.
11 *************************************************************************
13 ** This module implements an object we call a "RowSet".
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.
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.
24 ** Hence, the primitive operations for a RowSet are:
26 ** CREATE
27 ** INSERT
28 ** TEST
29 ** SMALLEST
30 ** DESTROY
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.
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.
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.
50 ** No INSERTs may occurs after a SMALLEST. An assertion will fail if
51 ** that is attempted.
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).
60 ** There is an added cost of O(N) when switching between TEST and
61 ** SMALLEST primitives.
63 #include "sqliteInt.h"
67 ** Target size for allocation chunks.
69 #define ROWSET_ALLOCATION_SIZE 1024
72 ** The number of rowset entries per allocation chunk.
74 #define ROWSET_ENTRY_PER_CHUNK \
75 ((ROWSET_ALLOCATION_SIZE-8)/sizeof(struct RowSetEntry))
78 ** Each entry in a RowSet is an instance of the following object.
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.
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) */
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.
97 struct RowSetChunk {
98 struct RowSetChunk *pNextChunk; /* Next chunk on list of them all */
99 struct RowSetEntry aEntry[ROWSET_ENTRY_PER_CHUNK]; /* Allocated entries */
103 ** A RowSet in an instance of the following structure.
105 ** A typedef of this structure if found in sqliteInt.h.
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 */
120 ** Allowed values for RowSet.rsFlags
122 #define ROWSET_SORTED 0x01 /* True if RowSet.pEntry is sorted */
123 #define ROWSET_NEXT 0x02 /* True if sqlite3RowSetNext() has been called */
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.
131 ** It must be the case that N is sufficient to make a Rowset. If not
132 ** an assertion fault occurs.
134 ** If N is larger than the minimum, use the surplus as an initial
135 ** allocation of entries available to be filled.
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;
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.
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);
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;
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.
177 ** In an OOM situation, the RowSet.db->mallocFailed flag is set and this
178 ** routine returns NULL.
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;
188 pNew->pNextChunk = p->pChunk;
189 p->pChunk = pNew;
190 p->pFresh = pNew->aEntry;
191 p->nFresh = ROWSET_ENTRY_PER_CHUNK;
193 p->nFresh--;
194 return p->pFresh++;
198 ** Insert a new value into a RowSet.
200 ** The mallocFailed flag of the database connection is set if a
201 ** memory allocation fails.
203 void sqlite3RowSetInsert(RowSet *p, i64 rowid){
204 struct RowSetEntry *pEntry; /* The new entry */
205 struct RowSetEntry *pLast; /* The last prior entry */
207 /* This routine is never called after sqlite3RowSetNext() */
208 assert( p!=0 && (p->rsFlags & ROWSET_NEXT)==0 );
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;
219 pLast->pRight = pEntry;
220 }else{
221 p->pEntry = pEntry;
223 p->pLast = pEntry;
227 ** Merge two lists of RowSetEntry objects. Remove duplicates.
229 ** The input lists are connected via pRight pointers and are
230 ** assumed to each already be in sorted order.
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 */
236 struct RowSetEntry head;
237 struct RowSetEntry *pTail;
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;
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;
262 return head.pRight;
266 ** Sort all elements on the list of RowSetEntry objects into order of
267 ** increasing v.
269 static struct RowSetEntry *rowSetEntrySort(struct RowSetEntry *pIn){
270 unsigned int i;
271 struct RowSetEntry *pNext, *aBucket[40];
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;
281 aBucket[i] = pIn;
282 pIn = pNext;
284 pIn = 0;
285 for(i=0; i<sizeof(aBucket)/sizeof(aBucket[0]); i++){
286 pIn = rowSetEntryMerge(pIn, aBucket[i]);
288 return pIn;
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.
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 */
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;
310 if( pIn->pRight ){
311 rowSetTreeToList(pIn->pRight, &pIn->pRight, ppLast);
312 }else{
313 *ppLast = pIn;
315 assert( (*ppLast)->pRight==0 );
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.
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.
330 ** Return a pointer to the root of the constructed binary tree.
332 static struct RowSetEntry *rowSetNDeepTree(
333 struct RowSetEntry **ppList,
334 int iDepth
336 struct RowSetEntry *p; /* Root of the new tree */
337 struct RowSetEntry *pLeft; /* Left subtree */
338 if( *ppList==0 ){
339 return 0;
341 if( iDepth==1 ){
342 p = *ppList;
343 *ppList = p->pRight;
344 p->pLeft = p->pRight = 0;
345 return p;
347 pLeft = rowSetNDeepTree(ppList, iDepth-1);
348 p = *ppList;
349 if( p==0 ){
350 return pLeft;
352 p->pLeft = pLeft;
353 *ppList = p->pRight;
354 p->pRight = rowSetNDeepTree(ppList, iDepth-1);
355 return p;
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.
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 */
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);
378 return p;
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.
385 ** This routine should only be called once in the life of a RowSet.
387 static void rowSetToList(RowSet *p){
389 /* This routine is called only once */
390 assert( p!=0 && (p->rsFlags & ROWSET_NEXT)==0 );
392 if( (p->rsFlags & ROWSET_SORTED)==0 ){
393 p->pEntry = rowSetEntrySort(p->pEntry);
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);
409 p->pForest = p->pForest->pRight;
411 #endif
412 p->rsFlags |= ROWSET_NEXT; /* Verify this routine is never called again */
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.
420 ** After this routine has been called, the sqlite3RowSetInsert()
421 ** routine may not be called again.
423 int sqlite3RowSetNext(RowSet *p, i64 *pRowid){
424 assert( p!=0 );
426 /* Merge the forest into a single sorted list on first call */
427 if( (p->rsFlags & ROWSET_NEXT)==0 ) rowSetToList(p);
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);
436 return 1;
437 }else{
438 return 0;
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.
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.
450 int sqlite3RowSetTest(RowSet *pRowSet, int iBatch, sqlite3_int64 iRowid){
451 struct RowSetEntry *p, *pTree;
453 /* This routine is never called after sqlite3RowSetNext() */
454 assert( pRowSet!=0 && (pRowSet->rsFlags & ROWSET_NEXT)==0 );
456 /* Sort entries into the forest on the first test of a new batch
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);
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);
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);
485 pRowSet->pEntry = 0;
486 pRowSet->pLast = 0;
487 pRowSet->rsFlags |= ROWSET_SORTED;
489 pRowSet->iBatch = iBatch;
492 /* Test to see if the iRowid value appears anywhere in the forest.
493 ** Return 1 if it does and 0 if not.
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;
507 return 0;