[sql] Import SQLite 3.17.0.

third_party/sqlite/src/src/rowset.c

 /*
 ** 2008 December 3
 **
 ** 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.
 **
@@ skipping 39 matching lines @@
 ** No INSERTs may occurs after a SMALLEST.  An assertion will fail if
 ** that is attempted.
 **
 ** The cost of an INSERT is roughly constant.  (Sometimes new memory
 ** has to be allocated on an INSERT.)  The cost of a TEST with a new
 ** batch number is O(NlogN) where N is the number of elements in the RowSet.
 ** The cost of a TEST using the same batch number is O(logN).  The cost
 ** of the first SMALLEST is O(NlogN).  Second and subsequent SMALLEST
 ** primitives are constant time.  The cost of DESTROY is O(N).
 **
-** There is an added cost of O(N) when switching between TEST and
-** SMALLEST primitives.
+** TEST and SMALLEST may not be used by the same RowSet.  This used to
+** be possible, but the feature was not used, so it was removed in order
+** to simplify the code.
 */
 #include "sqliteInt.h"
 
 
 /*
 ** Target size for allocation chunks.
 */
 #define ROWSET_ALLOCATION_SIZE 1024
 
 /*
@@ skipping 100 matching lines @@
 /*
 ** Allocate a new RowSetEntry object that is associated with the
 ** given RowSet.  Return a pointer to the new and completely uninitialized
 ** objected.
 **
 ** In an OOM situation, the RowSet.db->mallocFailed flag is set and this
 ** routine returns NULL.
 */
 static struct RowSetEntry *rowSetEntryAlloc(RowSet *p){
   assert( p!=0 );
-  if( p->nFresh==0 ){
+  if( p->nFresh==0 ){  /*OPTIMIZATION-IF-FALSE*/
+    /* We could allocate a fresh RowSetEntry each time one is needed, but it
+    ** is more efficient to pull a preallocated entry from the pool */
     struct RowSetChunk *pNew;
-    pNew = sqlite3DbMallocRaw(p->db, sizeof(*pNew));
+    pNew = sqlite3DbMallocRawNN(p->db, sizeof(*pNew));
     if( pNew==0 ){
       return 0;
     }
     pNew->pNextChunk = p->pChunk;
     p->pChunk = pNew;
     p->pFresh = pNew->aEntry;
     p->nFresh = ROWSET_ENTRY_PER_CHUNK;
   }
   p->nFresh--;
   return p->pFresh++;
@@ skipping 11 matching lines @@
 
   /* This routine is never called after sqlite3RowSetNext() */
   assert( p!=0 && (p->rsFlags & ROWSET_NEXT)==0 );
 
   pEntry = rowSetEntryAlloc(p);
   if( pEntry==0 ) return;
   pEntry->v = rowid;
   pEntry->pRight = 0;
   pLast = p->pLast;
   if( pLast ){
-    if( (p->rsFlags & ROWSET_SORTED)!=0 && rowid<=pLast->v ){
+    if( rowid<=pLast->v ){  /*OPTIMIZATION-IF-FALSE*/
+      /* Avoid unnecessary sorts by preserving the ROWSET_SORTED flags
+      ** where possible */
       p->rsFlags &= ~ROWSET_SORTED;
     }
     pLast->pRight = pEntry;
   }else{
     p->pEntry = pEntry;
   }
   p->pLast = pEntry;
 }
 
 /*
 ** Merge two lists of RowSetEntry objects.  Remove duplicates.
 **
 ** The input lists are connected via pRight pointers and are 
 ** assumed to each already be in sorted order.
 */
 static struct RowSetEntry *rowSetEntryMerge(
   struct RowSetEntry *pA,    /* First sorted list to be merged */
   struct RowSetEntry *pB     /* Second sorted list to be merged */
 ){
   struct RowSetEntry head;
   struct RowSetEntry *pTail;
 
   pTail = &head;
-  while( pA && pB ){
+  assert( pA!=0 && pB!=0 );
+  for(;;){
     assert( pA->pRight==0 || pA->v<=pA->pRight->v );
     assert( pB->pRight==0 || pB->v<=pB->pRight->v );
-    if( pA->v<pB->v ){
-      pTail->pRight = pA;
+    if( pA->v<=pB->v ){
+      if( pA->v<pB->v ) pTail = pTail->pRight = pA;
       pA = pA->pRight;
-      pTail = pTail->pRight;
-    }else if( pB->v<pA->v ){
-      pTail->pRight = pB;
+      if( pA==0 ){
+        pTail->pRight = pB;
+        break;
+      }
+    }else{
+      pTail = pTail->pRight = pB;
       pB = pB->pRight;
-      pTail = pTail->pRight;
-    }else{
-      pA = pA->pRight;
+      if( pB==0 ){
+        pTail->pRight = pA;
+        break;
+      }
     }
   }
-  if( pA ){
-    assert( pA->pRight==0 || pA->v<=pA->pRight->v );
-    pTail->pRight = pA;
-  }else{
-    assert( pB==0 || pB->pRight==0 || pB->v<=pB->pRight->v );
-    pTail->pRight = pB;
-  }
   return head.pRight;
 }
 
 /*
 ** Sort all elements on the list of RowSetEntry objects into order of
 ** increasing v.
 */ 
 static struct RowSetEntry *rowSetEntrySort(struct RowSetEntry *pIn){
   unsigned int i;
   struct RowSetEntry *pNext, *aBucket[40];
 
   memset(aBucket, 0, sizeof(aBucket));
   while( pIn ){
     pNext = pIn->pRight;
     pIn->pRight = 0;
     for(i=0; aBucket[i]; i++){
       pIn = rowSetEntryMerge(aBucket[i], pIn);
       aBucket[i] = 0;
     }
     aBucket[i] = pIn;
     pIn = pNext;
   }
-  pIn = 0;
-  for(i=0; i<sizeof(aBucket)/sizeof(aBucket[0]); i++){
-    pIn = rowSetEntryMerge(pIn, aBucket[i]);
+  pIn = aBucket[0];
+  for(i=1; i<sizeof(aBucket)/sizeof(aBucket[0]); i++){
+    if( aBucket[i]==0 ) continue;
+    pIn = pIn ? rowSetEntryMerge(pIn, aBucket[i]) : aBucket[i];
   }
   return pIn;
 }
 
 
 /*
 ** The input, pIn, is a binary tree (or subtree) of RowSetEntry objects.
 ** Convert this tree into a linked list connected by the pRight pointers
 ** and return pointers to the first and last elements of the new list.
 */
@@ skipping 31 matching lines @@
 ** and leave *ppList set to NULL.
 **
 ** Return a pointer to the root of the constructed binary tree.
 */
 static struct RowSetEntry *rowSetNDeepTree(
   struct RowSetEntry **ppList,
   int iDepth
 ){
   struct RowSetEntry *p;         /* Root of the new tree */
   struct RowSetEntry *pLeft;     /* Left subtree */
-  if( *ppList==0 ){
-    return 0;
+  if( *ppList==0 ){ /*OPTIMIZATION-IF-TRUE*/
+    /* Prevent unnecessary deep recursion when we run out of entries */
+    return 0; 
   }
-  if( iDepth==1 ){
+  if( iDepth>1 ){   /*OPTIMIZATION-IF-TRUE*/
+    /* This branch causes a *balanced* tree to be generated.  A valid tree
+    ** is still generated without this branch, but the tree is wildly
+    ** unbalanced and inefficient. */
+    pLeft = rowSetNDeepTree(ppList, iDepth-1);
+    p = *ppList;
+    if( p==0 ){     /*OPTIMIZATION-IF-FALSE*/
+      /* It is safe to always return here, but the resulting tree
+      ** would be unbalanced */
+      return pLeft;
+    }
+    p->pLeft = pLeft;
+    *ppList = p->pRight;
+    p->pRight = rowSetNDeepTree(ppList, iDepth-1);
+  }else{
     p = *ppList;
     *ppList = p->pRight;
     p->pLeft = p->pRight = 0;
-    return p;
   }
-  pLeft = rowSetNDeepTree(ppList, iDepth-1);
-  p = *ppList;
-  if( p==0 ){
-    return pLeft;
-  }
-  p->pLeft = pLeft;
-  *ppList = p->pRight;
-  p->pRight = rowSetNDeepTree(ppList, iDepth-1);
   return p;
 }
 
 /*
 ** Convert a sorted list of elements into a binary tree. Make the tree
 ** as deep as it needs to be in order to contain the entire list.
 */
 static struct RowSetEntry *rowSetListToTree(struct RowSetEntry *pList){
   int iDepth;           /* Depth of the tree so far */
   struct RowSetEntry *p;       /* Current tree root */
   struct RowSetEntry *pLeft;   /* Left subtree */
 
   assert( pList!=0 );
   p = pList;
   pList = p->pRight;
   p->pLeft = p->pRight = 0;
   for(iDepth=1; pList; iDepth++){
     pLeft = p;
     p = pList;
     pList = p->pRight;
     p->pLeft = pLeft;
     p->pRight = rowSetNDeepTree(&pList, iDepth);
   }
   return p;
 }
 
 /*
-** Take all the entries on p->pEntry and on the trees in p->pForest and
-** sort them all together into one big ordered list on p->pEntry.
-**
-** This routine should only be called once in the life of a RowSet.
-*/
-static void rowSetToList(RowSet *p){
-
-  /* This routine is called only once */
-  assert( p!=0 && (p->rsFlags & ROWSET_NEXT)==0 );
-
-  if( (p->rsFlags & ROWSET_SORTED)==0 ){
-    p->pEntry = rowSetEntrySort(p->pEntry);
-  }
-
-  /* While this module could theoretically support it, sqlite3RowSetNext()
-  ** is never called after sqlite3RowSetText() for the same RowSet.  So
-  ** there is never a forest to deal with.  Should this change, simply
-  ** remove the assert() and the #if 0. */
-  assert( p->pForest==0 );
-#if 0
-  while( p->pForest ){
-    struct RowSetEntry *pTree = p->pForest->pLeft;
-    if( pTree ){
-      struct RowSetEntry *pHead, *pTail;
-      rowSetTreeToList(pTree, &pHead, &pTail);
-      p->pEntry = rowSetEntryMerge(p->pEntry, pHead);
-    }
-    p->pForest = p->pForest->pRight;
-  }
-#endif
-  p->rsFlags |= ROWSET_NEXT;  /* Verify this routine is never called again */
-}
-
-/*
 ** Extract the smallest element from the RowSet.
 ** Write the element into *pRowid.  Return 1 on success.  Return
 ** 0 if the RowSet is already empty.
 **
 ** After this routine has been called, the sqlite3RowSetInsert()
-** routine may not be called again.  
+** routine may not be called again.
+**
+** This routine may not be called after sqlite3RowSetTest() has
+** been used.  Older versions of RowSet allowed that, but as the
+** capability was not used by the code generator, it was removed
+** for code economy.
 */
 int sqlite3RowSetNext(RowSet *p, i64 *pRowid){
   assert( p!=0 );
+  assert( p->pForest==0 );  /* Cannot be used with sqlite3RowSetText() */
 
   /* Merge the forest into a single sorted list on first call */
-  if( (p->rsFlags & ROWSET_NEXT)==0 ) rowSetToList(p);
+  if( (p->rsFlags & ROWSET_NEXT)==0 ){  /*OPTIMIZATION-IF-FALSE*/
+    if( (p->rsFlags & ROWSET_SORTED)==0 ){  /*OPTIMIZATION-IF-FALSE*/
+      p->pEntry = rowSetEntrySort(p->pEntry);
+    }
+    p->rsFlags |= ROWSET_SORTED|ROWSET_NEXT;
+  }
 
   /* Return the next entry on the list */
   if( p->pEntry ){
     *pRowid = p->pEntry->v;
     p->pEntry = p->pEntry->pRight;
-    if( p->pEntry==0 ){
+    if( p->pEntry==0 ){ /*OPTIMIZATION-IF-TRUE*/
+      /* Free memory immediately, rather than waiting on sqlite3_finalize() */
       sqlite3RowSetClear(p);
     }
     return 1;
   }else{
     return 0;
   }
 }
 
 /*
 ** Check to see if element iRowid was inserted into the rowset as
 ** part of any insert batch prior to iBatch.  Return 1 or 0.
 **
 ** If this is the first test of a new batch and if there exist entries
 ** on pRowSet->pEntry, then sort those entries into the forest at
 ** pRowSet->pForest so that they can be tested.
 */
 int sqlite3RowSetTest(RowSet *pRowSet, int iBatch, sqlite3_int64 iRowid){
   struct RowSetEntry *p, *pTree;
 
   /* This routine is never called after sqlite3RowSetNext() */
   assert( pRowSet!=0 && (pRowSet->rsFlags & ROWSET_NEXT)==0 );
 
-  /* Sort entries into the forest on the first test of a new batch 
+  /* Sort entries into the forest on the first test of a new batch.
+  ** To save unnecessary work, only do this when the batch number changes.
   */
-  if( iBatch!=pRowSet->iBatch ){
+  if( iBatch!=pRowSet->iBatch ){  /*OPTIMIZATION-IF-FALSE*/
     p = pRowSet->pEntry;
     if( p ){
       struct RowSetEntry **ppPrevTree = &pRowSet->pForest;
-      if( (pRowSet->rsFlags & ROWSET_SORTED)==0 ){
+      if( (pRowSet->rsFlags & ROWSET_SORTED)==0 ){ /*OPTIMIZATION-IF-FALSE*/
+        /* Only sort the current set of entiries if they need it */
         p = rowSetEntrySort(p);
       }
       for(pTree = pRowSet->pForest; pTree; pTree=pTree->pRight){
         ppPrevTree = &pTree->pRight;
         if( pTree->pLeft==0 ){
           pTree->pLeft = rowSetListToTree(p);
           break;
         }else{
           struct RowSetEntry *pAux, *pTail;
           rowSetTreeToList(pTree->pLeft, &pAux, &pTail);
@@ skipping 26 matching lines @@
         p = p->pRight;
       }else if( p->v>iRowid ){
         p = p->pLeft;
       }else{
         return 1;
       }
     }
   }
   return 0;
 }