SQLite

         memjournal.o \
         mutex.o mutex_noop.o mutex_os2.o mutex_unix.o mutex_w32.o \
         notify.o opcodes.o os.o os_os2.o os_unix.o os_win.o \
         pager.o parse.o pcache.o pcache1.o pragma.o prepare.o printf.o \
         random.o resolve.o rowset.o rtree.o select.o status.o \
         table.o tokenize.o trigger.o \
         update.o util.o vacuum.o \
         vdbe.o vdbeapi.o vdbeaux.o vdbeblob.o vdbemem.o vdbetrace.o \
         wal.o walker.o where.o utf.o vtab.o
         vdbe.o vdbeapi.o vdbeaux.o vdbeblob.o vdbemem.o vdbesort.o \
	 vdbetrace.o wal.o walker.o where.o utf.o vtab.o



# All of the source code files.
#
SRC = \
  $(TOP)/src/alter.c \

  $(TOP)/src/vacuum.c \
  $(TOP)/src/vdbe.c \
  $(TOP)/src/vdbe.h \
  $(TOP)/src/vdbeapi.c \
  $(TOP)/src/vdbeaux.c \
  $(TOP)/src/vdbeblob.c \
  $(TOP)/src/vdbemem.c \
  $(TOP)/src/vdbesort.c \
  $(TOP)/src/vdbetrace.c \
  $(TOP)/src/vdbeInt.h \
  $(TOP)/src/vtab.c \
  $(TOP)/src/wal.c \
  $(TOP)/src/wal.h \
  $(TOP)/src/walker.c \
  $(TOP)/src/where.c

** the index already exists and must be cleared before being refilled and
** the root page number of the index is taken from pIndex->tnum.
*/
static void sqlite3RefillIndex(Parse *pParse, Index *pIndex, int memRootPage){
  Table *pTab = pIndex->pTable;  /* The table that is indexed */
  int iTab = pParse->nTab++;     /* Btree cursor used for pTab */
  int iIdx = pParse->nTab++;     /* Btree cursor used for pIndex */
  int iSorter = pParse->nTab++;  /* Btree cursor used for sorting */
  int addr1;                     /* Address of top of loop */
  int tnum;                      /* Root page of index */
  Vdbe *v;                       /* Generate code into this virtual machine */
  KeyInfo *pKey;                 /* KeyInfo for index */
  int regIdxKey;                 /* Registers containing the index key */
  int regRecord;                 /* Register holding assemblied index record */
  sqlite3 *db = pParse->db;      /* The database connection */

  }
  pKey = sqlite3IndexKeyinfo(pParse, pIndex);
  sqlite3VdbeAddOp4(v, OP_OpenWrite, iIdx, tnum, iDb, 
                    (char *)pKey, P4_KEYINFO_HANDOFF);
  if( memRootPage>=0 ){
    sqlite3VdbeChangeP5(v, 1);
  }

  /* Open the sorter cursor. */
  sqlite3VdbeAddOp4(v, OP_OpenSorter, iSorter, 0, 0, (char*)pKey, P4_KEYINFO);

  /* Open the table. Loop through all rows of the table, inserting index
  ** records into the sorter. */
  sqlite3OpenTable(pParse, iTab, iDb, pTab, OP_OpenRead);
  addr1 = sqlite3VdbeAddOp2(v, OP_Rewind, iTab, 0);
  regRecord = sqlite3GetTempReg(pParse);
  regIdxKey = sqlite3GenerateIndexKey(pParse, pIndex, iTab, regRecord, 1);
  sqlite3VdbeAddOp2(v, OP_IdxInsert, iSorter, regRecord);
  sqlite3VdbeAddOp2(v, OP_Next, iTab, addr1+1);
  sqlite3VdbeJumpHere(v, addr1);

  /* Rewind the sorter. Loop through index records in sorted order. */
  addr1 = sqlite3VdbeAddOp2(v, OP_Rewind, iSorter, 0);
  sqlite3VdbeAddOp2(v, OP_RowKey, iSorter, regRecord);

  if( pIndex->onError!=OE_None ){
    const int regRowid = regIdxKey + pIndex->nColumn;
    const int j2 = sqlite3VdbeCurrentAddr(v) + 2;
    void * const pRegKey = SQLITE_INT_TO_PTR(regIdxKey);

    /* The registers accessed by the OP_IsUnique opcode were allocated
    ** using sqlite3GetTempRange() inside of the sqlite3GenerateIndexKey()
    ** call above. Just before that function was freed they were released
    ** (made available to the compiler for reuse) using 
    ** sqlite3ReleaseTempRange(). So in some ways having the OP_IsUnique
    ** opcode use the values stored within seems dangerous. However, since
    ** we can be sure that no other temp registers have been allocated
    ** since sqlite3ReleaseTempRange() was called, it is safe to do so.
    */
    sqlite3VdbeAddOp4(v, OP_IsUnique, iIdx, j2, regRowid, pRegKey, P4_INT32);
    sqlite3HaltConstraint(
        pParse, OE_Abort, "indexed columns are not unique", P4_STATIC);
  }
  sqlite3VdbeAddOp2(v, OP_IdxInsert, iIdx, regRecord);
  sqlite3VdbeAddOp3(v, OP_IdxInsert, iIdx, regRecord, 1);
  sqlite3VdbeChangeP5(v, OPFLAG_USESEEKRESULT);
  sqlite3ReleaseTempReg(pParse, regRecord);
  sqlite3VdbeAddOp2(v, OP_Next, iTab, addr1+1);
  sqlite3VdbeAddOp2(v, OP_Next, iSorter, addr1+1);
  sqlite3VdbeJumpHere(v, addr1);

  sqlite3VdbeAddOp1(v, OP_Close, iTab);
  sqlite3VdbeAddOp1(v, OP_Close, iSorter);
  sqlite3VdbeAddOp1(v, OP_Close, iIdx);
}

/*
** Create a new index for an SQL table.  pName1.pName2 is the name of the index 
** and pTblList is the name of the table that is to be indexed.  Both will 
** be NULL for a primary key or an index that is created to satisfy a

/* Opcode: OpenAutoindex P1 P2 * P4 *
**
** This opcode works the same as OP_OpenEphemeral.  It has a
** different name to distinguish its use.  Tables created using
** by this opcode will be used for automatically created transient
** indices in joins.
*/
case OP_OpenSorter: 
case OP_OpenAutoindex: 
case OP_OpenEphemeral: {
  VdbeCursor *pCx;
  static const int vfsFlags = 
      SQLITE_OPEN_READWRITE |
      SQLITE_OPEN_CREATE |
      SQLITE_OPEN_EXCLUSIVE |
      SQLITE_OPEN_DELETEONCLOSE |
      SQLITE_OPEN_TRANSIENT_DB;

  int btflags = BTREE_OMIT_JOURNAL | pOp->p5;
  if( pOp->opcode!=OP_OpenSorter ) btflags |= BTREE_SINGLE;

  assert( pOp->p1>=0 );
  pCx = allocateCursor(p, pOp->p1, pOp->p2, -1, 1);
  if( pCx==0 ) goto no_mem;
  pCx->nullRow = 1;
  rc = sqlite3BtreeOpen(db->pVfs, 0, db, &pCx->pBt, 
  rc = sqlite3BtreeOpen(db->pVfs, 0, db, &pCx->pBt, btflags, vfsFlags);
                        BTREE_OMIT_JOURNAL | BTREE_SINGLE | pOp->p5, vfsFlags);
  if( rc==SQLITE_OK ){
    rc = sqlite3BtreeBeginTrans(pCx->pBt, 1);
  }
  if( rc==SQLITE_OK ){
    /* If a transient index is required, create it by calling
    ** sqlite3BtreeCreateTable() with the BTREE_BLOBKEY flag before
    ** opening it. If a transient table is required, just use the
    ** automatically created table with root-page 1 (an BLOB_INTKEY table).
    */
    if( pOp->p4.pKeyInfo ){
      int pgno;
      assert( pOp->p4type==P4_KEYINFO );
      rc = sqlite3BtreeCreateTable(pCx->pBt, &pgno, BTREE_BLOBKEY | pOp->p5); 
      if( rc==SQLITE_OK ){
        assert( pgno==MASTER_ROOT+1 );
        rc = sqlite3BtreeCursor(pCx->pBt, pgno, 1, 
                                (KeyInfo*)pOp->p4.z, pCx->pCursor);
        pCx->pKeyInfo = pOp->p4.pKeyInfo;
        pCx->pKeyInfo->enc = ENC(p->db);
        pCx->pKeyInfo->enc = ENC(db);
      }
      pCx->isTable = 0;
    }else{
      rc = sqlite3BtreeCursor(pCx->pBt, MASTER_ROOT, 1, 0, pCx->pCursor);
      pCx->isTable = 1;
    }
  }
  pCx->isOrdered = (pOp->p5!=BTREE_UNORDERED);
  pCx->isIndex = !pCx->isTable;
  if( rc==SQLITE_OK && pOp->opcode==OP_OpenSorter ){
    rc = sqlite3VdbeSorterInit(db, pCx);
  }
  break;
}

/* Opcode: OpenPseudo P1 P2 P3 * *
**
** Open a new cursor that points to a fake table that contains a single
** row of data.  The content of that one row in the content of memory

  assert( pOp->p1>=0 && pOp->p1<p->nCursor );
  pC = p->apCsr[pOp->p1];
  assert( pC->isTable || pOp->opcode==OP_RowKey );
  assert( pC->isIndex || pOp->opcode==OP_RowData );
  assert( pC!=0 );
  assert( pC->nullRow==0 );
  assert( pC->pseudoTableReg==0 );

  if( pC->pSorter ){
    rc = sqlite3VdbeSorterRowkey(db, pC, pOut);
    break;
  }

  assert( pC->pCursor!=0 );
  pCrsr = pC->pCursor;
  assert( sqlite3BtreeCursorIsValid(pCrsr) );

  /* The OP_RowKey and OP_RowData opcodes always follow OP_NotExists or
  ** OP_Rewind/Op_Next with no intervening instructions that might invalidate
  ** the cursor.  Hence the following sqlite3VdbeCursorMoveto() call is always

  BtCursor *pCrsr;
  int res;

  assert( pOp->p1>=0 && pOp->p1<p->nCursor );
  pC = p->apCsr[pOp->p1];
  assert( pC!=0 );
  res = 1;
  if( pC->pSorter ){
    rc = sqlite3VdbeSorterRewind(db, pC, &res);
  if( (pCrsr = pC->pCursor)!=0 ){
  }else if( (pCrsr = pC->pCursor)!=0 ){
    rc = sqlite3BtreeFirst(pCrsr, &res);
    pC->atFirst = res==0 ?1:0;
    pC->deferredMoveto = 0;
    pC->cacheStatus = CACHE_STALE;
    pC->rowidIsValid = 0;
  }
  pC->nullRow = (u8)res;

  CHECK_FOR_INTERRUPT;
  assert( pOp->p1>=0 && pOp->p1<p->nCursor );
  assert( pOp->p5<=ArraySize(p->aCounter) );
  pC = p->apCsr[pOp->p1];
  if( pC==0 ){
    break;  /* See ticket #2273 */
  }
  if( pC->pSorter ){
    assert( pOp->opcode==OP_Next );
    rc = sqlite3VdbeSorterNext(db, pC, &res);
  }else{
  pCrsr = pC->pCursor;
  if( pCrsr==0 ){
    pC->nullRow = 1;
    break;
  }
  res = 1;
  assert( pC->deferredMoveto==0 );
  rc = pOp->opcode==OP_Next ? sqlite3BtreeNext(pCrsr, &res) :
                              sqlite3BtreePrevious(pCrsr, &res);
    pCrsr = pC->pCursor;
    if( pCrsr==0 ){
      pC->nullRow = 1;
      break;
    }
    res = 1;
    assert( pC->deferredMoveto==0 );
    rc = pOp->opcode==OP_Next ? sqlite3BtreeNext(pCrsr, &res) :
                                sqlite3BtreePrevious(pCrsr, &res);
  }
  pC->nullRow = (u8)res;
  pC->cacheStatus = CACHE_STALE;

  if( res==0 ){
    pc = pOp->p2 - 1;
    if( pOp->p5 ) p->aCounter[pOp->p5-1]++;
#ifdef SQLITE_TEST
    sqlite3_search_count++;
#endif
  }

  BtCursor *pCrsr;
  int nKey;
  const char *zKey;

  assert( pOp->p1>=0 && pOp->p1<p->nCursor );
  pC = p->apCsr[pOp->p1];
  assert( pC!=0 );
  rc = sqlite3VdbeSorterWrite(db, pC);
  if( rc!=SQLITE_OK ) goto abort_due_to_error;
  pIn2 = &aMem[pOp->p2];
  assert( pIn2->flags & MEM_Blob );
  pCrsr = pC->pCursor;
  if( ALWAYS(pCrsr!=0) ){
    assert( pC->isTable==0 );
    rc = ExpandBlob(pIn2);
    if( rc==SQLITE_OK ){

typedef struct VdbeOp Op;

/*
** Boolean values
*/
typedef unsigned char Bool;

/* Opaque type used by code in vdbesort.c */
typedef struct VdbeSorter VdbeSorter;

/*
** A cursor is a pointer into a single BTree within a database file.
** The cursor can seek to a BTree entry with a particular key, or
** loop over all entries of the Btree.  You can also insert new BTree
** entries or retrieve the key or data from the entry that the cursor
** is currently pointing to.
** 

  Bool isIndex;         /* True if an index containing keys only - no data */
  Bool isOrdered;       /* True if the underlying table is BTREE_UNORDERED */
  sqlite3_vtab_cursor *pVtabCursor;  /* The cursor for a virtual table */
  const sqlite3_module *pModule;     /* Module for cursor pVtabCursor */
  i64 seqCount;         /* Sequence counter */
  i64 movetoTarget;     /* Argument to the deferred sqlite3BtreeMoveto() */
  i64 lastRowid;        /* Last rowid from a Next or NextIdx operation */
  VdbeSorter *pSorter;  /* Sorter object for OP_OpenSorter cursors */

  /* Result of last sqlite3BtreeMoveto() done by an OP_NotExists or 
  ** OP_IsUnique opcode on this cursor. */
  int seekResult;

  /* Cached information about the header for the data record that the
  ** cursor is currently pointing to.  Only valid if cacheStatus matches

const char *sqlite3OpcodeName(int);
int sqlite3VdbeMemGrow(Mem *pMem, int n, int preserve);
int sqlite3VdbeCloseStatement(Vdbe *, int);
void sqlite3VdbeFrameDelete(VdbeFrame*);
int sqlite3VdbeFrameRestore(VdbeFrame *);
void sqlite3VdbeMemStoreType(Mem *pMem);

int sqlite3VdbeSorterInit(sqlite3 *, VdbeCursor *);
int sqlite3VdbeSorterWrite(sqlite3 *, VdbeCursor *);
void sqlite3VdbeSorterClose(sqlite3 *, VdbeCursor *);

#if !defined(SQLITE_OMIT_SHARED_CACHE) && SQLITE_THREADSAFE>0
  void sqlite3VdbeEnter(Vdbe*);
  void sqlite3VdbeLeave(Vdbe*);
#else
# define sqlite3VdbeEnter(X)
# define sqlite3VdbeLeave(X)
#endif

** Close a VDBE cursor and release all the resources that cursor 
** happens to hold.
*/
void sqlite3VdbeFreeCursor(Vdbe *p, VdbeCursor *pCx){
  if( pCx==0 ){
    return;
  }
  sqlite3VdbeSorterClose(p->db, pCx);
  if( pCx->pBt ){
    sqlite3BtreeClose(pCx->pBt);
    /* The pCx->pCursor will be close automatically, if it exists, by
    ** the call above. */
  }else if( pCx->pCursor ){
    sqlite3BtreeCloseCursor(pCx->pCursor);
  }

/*
** 2011 July 9
**
** 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.
**
*************************************************************************
** This file contains code for the VdbeSorter object, used in concert with
** a VdbeCursor to sort large numbers of keys (as may be required, for
** example, by CREATE INDEX statements on tables too large to fit in main
** memory).
*/

#include "sqliteInt.h"
#include "vdbeInt.h"

typedef struct VdbeSorterIter VdbeSorterIter;

/*
** The aIter[] and aTree[] arrays are used to iterate through the sorter
** contents after it has been populated. To iterate through the sorter
** contents, the contents of the nRoot b-trees must be incrementally merged. 
**
** The first nRoot elements of the aIter[] array contain cursors open 
** on each of the b-trees. An aIter[] element either points to a valid
** key or else is at EOF. For the purposes of the paragraphs below, we
** assume that the array is actually N elements in size, where N is the
** smallest power of 2 greater to or equal to nRoot. The extra aIter[]
** elements are treated as if they are empty trees (always at EOF).
**
** The aTree[] array is N elements in size. The value of N is stored in
** the VdbeSorter.nTree variable.
**
** The final (N/2) elements of aTree[] contain the results of comparing
** pairs of iterator keys together. Element i contains the result of 
** comparing aIter[2*i-N] and aIter[2*i-N+1]. Whichever key is smaller, the
** aTree element is set to the index of it. 
**
** For the purposes of this comparison, EOF is considered greater than any
** other key value. If the keys are equal (only possible with two EOF
** values), it doesn't matter which index is stored.
**
** The (N/4) elements of aTree[] that preceed the final (N/2) described 
** above contains the index of the smallest of each block of 4 iterators.
** And so on. So that aTree[1] contains the index of the iterator that 
** currently points to the smallest key value. aTree[0] is unused.
**
** Example:
**
**     aIter[0] -> Banana
**     aIter[1] -> Feijoa
**     aIter[2] -> Elderberry
**     aIter[3] -> Currant
**     aIter[4] -> Grapefruit
**     aIter[5] -> Apple
**     aIter[6] -> Durian
**     aIter[7] -> EOF
**
**     aTree[] = { X, 5   0, 5    0, 3, 5, 6 }
**
** The current element is "Apple" (the value of the key indicated by 
** iterator 5). When the Next() operation is invoked, iterator 5 will
** be advanced to the next key in its segment. Say the next key is
** "Eggplant":
**
**     aIter[5] -> Eggplant
**
** The contents of aTree[] are updated first by comparing the new iterator
** 5 key to the current key of iterator 4 (still "Grapefruit"). The iterator
** 5 value is still smaller, so aTree[6] is set to 5. And so on up the tree.
** The value of iterator 6 - "Durian" - is now smaller than that of iterator
** 5, so aTree[3] is set to 6. Key 0 is smaller than key 6 (Banana<Durian),
** so the value written into element 1 of the array is 0. As follows:
**
**     aTree[] = { X, 0   0, 6    0, 3, 5, 6 }
**
** In other words, each time we advance to the next sorter element, log2(N)
** key comparison operations are required, where N is the number of segments
** being merged (rounded up to the next power of 2).
*/
struct VdbeSorter {
  int nWorking;                   /* Start a new b-tree after this many pages */
  int nPage;                      /* Pages in file when current tree started */
  int nRoot;                      /* Total number of segment b-trees */
  int *aRoot;                     /* Array containing root pages */

  int nAlloc;                     /* Allocated size of aIter[] and aTree[] */
  int nTree;                      /* Used size of aTree/aIter (power of 2) */
  VdbeSorterIter *aIter;          /* Array of iterators to merge */
  int *aTree;                     /* Current state of incremental merge */
};

/*
** The following type is a simple wrapper around a BtCursor. It caches the
** current key in variables nKey/aKey. If possible, aKey points to memory
** managed by the BtCursor object. In this case variable bFree is zero.
** Otherwise, aKey[] may point to a block of memory allocated using
** sqlite3DbMalloc(). In this case, bFree is non-zero.
*/
struct VdbeSorterIter {
  BtCursor *pCsr;                 /* Cursor open on b-tree */
  int bFree;                      /* True if aKey should be freed */
  int nKey;                       /* Number of bytes in key */
  u8 *aKey;                       /* Pointer to current key */
};

/* Minimum allowable value for the VdbeSorter.nWorking variable */
#define SORTER_MIN_SEGMENT_SIZE 10

/*
** Append integer iRoot to the VdbeSorter.aRoot[] array of the sorter object
** passed as the second argument. SQLITE_NOMEM is returned if an OOM error
** is encountered, or SQLITE_OK if no error occurs.
**
** TODO: The aRoot[] array may grow indefinitely. Fix this.
*/
static int vdbeSorterAppendRoot(sqlite3 *db, VdbeSorter *p, int iRoot){
  int *aNew;                      /* New VdbeSorter.aRoot[] array */

  aNew = sqlite3DbRealloc(db, p->aRoot, (p->nRoot+1)*sizeof(int));
  if( !aNew ) return SQLITE_NOMEM;
  aNew[p->nRoot] = iRoot;
  p->nRoot++;
  p->aRoot = aNew;
  return SQLITE_OK;
}

/*
** Close any cursor and free all memory belonging to the VdbeSorterIter
** object passed as the second argument. All structure fields are set
** to zero before returning.
*/
static void vdbeSorterIterZero(sqlite3 *db, VdbeSorterIter *pIter){
  if( pIter->bFree ){
    sqlite3DbFree(db, pIter->aKey);
  }
  if( pIter->pCsr ){
    sqlite3BtreeCloseCursor(pIter->pCsr);
    sqlite3DbFree(db, pIter->pCsr);
  }
  memset(pIter, 0, sizeof(VdbeSorterIter));
}

/*
** Fetch the current key pointed to by the b-tree cursor managed by pIter
** into variables VdbeSorterIter.aKey and VdbeSorterIter.nKey. Return
** SQLITE_OK if no error occurs, or an SQLite error code otherwise.
*/
static int vdbeSorterIterLoadkey(sqlite3 *db, VdbeSorterIter *pIter){
  int rc = SQLITE_OK;
  assert( pIter->pCsr );
  if( sqlite3BtreeEof(pIter->pCsr) ){
    vdbeSorterIterZero(db, pIter);
  }else{
    i64 nByte64;
    sqlite3BtreeKeySize(pIter->pCsr, &nByte64);

    if( pIter->bFree ){
      sqlite3DbFree(db, pIter->aKey);
      pIter->aKey = 0;
    }

    pIter->nKey = nByte64;
    pIter->aKey = sqlite3DbMallocRaw(db, pIter->nKey);
    pIter->bFree = 1;
    if( pIter->aKey==0 ){
      rc = SQLITE_NOMEM;
    }else{
      rc = sqlite3BtreeKey(pIter->pCsr, 0, pIter->nKey, pIter->aKey);
    }

  }
  return rc;
}

/*
** Initialize iterator pIter to scan through the b-tree with root page
** iRoot. This function leaves the iterator pointing to the first key
** in the b-tree (or EOF if the b-tree is empty).
*/
static int vdbeSorterIterInit(
  sqlite3 *db,                    /* Database handle */
  VdbeCursor *pCsr,               /* Vdbe cursor handle */
  int iRoot,                      /* Root page of b-tree to iterate */
  VdbeSorterIter *pIter           /* Pointer to iterator to initialize */
){
  VdbeSorter *pSorter = pCsr->pSorter;
  int rc;

  pIter->pCsr = (BtCursor *)sqlite3DbMallocZero(db, sqlite3BtreeCursorSize());
  if( !pIter->pCsr ){
    rc = SQLITE_NOMEM;
  }else{
    rc = sqlite3BtreeCursor(pCsr->pBt, iRoot, 1, pCsr->pKeyInfo, pIter->pCsr);
  }
  if( rc==SQLITE_OK ){
    int bDummy;
    rc = sqlite3BtreeFirst(pIter->pCsr, &bDummy);
  }
  if( rc==SQLITE_OK ){
    rc = vdbeSorterIterLoadkey(db, pIter);
  }

  return rc;
}

/*
** Advance iterator pIter to the next key in its b-tree. 
*/
static int vdbeSorterIterNext(
  sqlite3 *db, 
  VdbeCursor *pCsr, 
  VdbeSorterIter *pIter
){
  int rc;
  int bDummy;
  VdbeSorter *pSorter = pCsr->pSorter;

  rc = sqlite3BtreeNext(pIter->pCsr, &bDummy);
  if( rc==SQLITE_OK ){
    rc = vdbeSorterIterLoadkey(db, pIter);
  }

  return rc;
}

/*
** This function is called to compare two iterator keys when merging 
** multiple b-tree segments. Parameter iOut is the index of the aTree[] 
** value to recalculate.
*/
static int vdbeSorterDoCompare(VdbeCursor *pCsr, int iOut){
  VdbeSorter *pSorter = pCsr->pSorter;
  int i1;
  int i2;
  int iRes;
  VdbeSorterIter *p1;
  VdbeSorterIter *p2;

  assert( iOut<pSorter->nTree && iOut>0 );

  if( iOut>=(pSorter->nTree/2) ){
    i1 = (iOut - pSorter->nTree/2) * 2;
    i2 = i1 + 1;
  }else{
    i1 = pSorter->aTree[iOut*2];
    i2 = pSorter->aTree[iOut*2+1];
  }

  p1 = &pSorter->aIter[i1];
  p2 = &pSorter->aIter[i2];

  if( p1->pCsr==0 ){
    iRes = i2;
  }else if( p2->pCsr==0 ){
    iRes = i1;
  }else{
    char aSpace[150];
    UnpackedRecord *r1;

    r1 = sqlite3VdbeRecordUnpack(
        pCsr->pKeyInfo, p1->nKey, p1->aKey, aSpace, sizeof(aSpace)
    );
    if( r1==0 ) return SQLITE_NOMEM;

    if( sqlite3VdbeRecordCompare(p2->nKey, p2->aKey, r1)>=0 ){
      iRes = i1;
    }else{
      iRes = i2;
    }
    sqlite3VdbeDeleteUnpackedRecord(r1);
  }

  pSorter->aTree[iOut] = iRes;
  return SQLITE_OK;
}

/*
** Initialize the temporary index cursor just opened as a sorter cursor.
*/
int sqlite3VdbeSorterInit(sqlite3 *db, VdbeCursor *pCsr){
  int rc;                         /* Return code */
  VdbeSorter *pSorter;            /* Allocated sorter object */

  /* Cursor must be a temp cursor and not open on an intkey table */
  assert( pCsr->pKeyInfo && pCsr->pBt );

  pSorter = sqlite3DbMallocZero(db, sizeof(VdbeSorter));
  if( !pSorter ) return SQLITE_NOMEM;
  pCsr->pSorter = pSorter;

  rc = vdbeSorterAppendRoot(db, pSorter, 2);
  if( rc!=SQLITE_OK ){
    sqlite3VdbeSorterClose(db, pCsr);
  }
  return rc;
}

/*
** Free any cursor components allocated by sqlite3VdbeSorterXXX routines.
*/
void sqlite3VdbeSorterClose(sqlite3 *db, VdbeCursor *pCsr){
  VdbeSorter *pSorter = pCsr->pSorter;
  if( pSorter ){
    sqlite3DbFree(db, pSorter->aRoot);
    if( pSorter->aIter ){
      int i;
      for(i=0; i<pSorter->nRoot; i++){
        vdbeSorterIterZero(db, &pSorter->aIter[i]);
      }
      sqlite3DbFree(db, pSorter->aIter);
      sqlite3DbFree(db, pSorter->aTree);
    }
    sqlite3DbFree(db, pSorter);
    pCsr->pSorter = 0;
  }
}

/*
** This function is called on a sorter cursor before each row is inserted.
** If the current b-tree being constructed is already considered "full",
** a new tree is started.
*/
int sqlite3VdbeSorterWrite(sqlite3 *db, VdbeCursor *pCsr){
  int rc = SQLITE_OK;             /* Return code */
  VdbeSorter *pSorter = pCsr->pSorter;
  if( pSorter ){
    Pager *pPager = sqlite3BtreePager(pCsr->pBt);
    int nPage;                    /* Current size of temporary file in pages */

    sqlite3PagerPagecount(pPager, &nPage);

    /* If pSorter->nWorking is still zero, but the temporary file has been
    ** created in the file-system, then the most recent insert into the
    ** current b-tree segment probably caused the cache to overflow (it is
    ** also possible that sqlite3_release_memory() was called). So set the
    ** size of the working set to a little less than the current size of the 
    ** file in pages.  */
    if( pSorter->nWorking==0 && sqlite3PagerFile(pPager)->pMethods ){
      pSorter->nWorking = nPage-5;
      if( pSorter->nWorking<SORTER_MIN_SEGMENT_SIZE ){
        pSorter->nWorking = SORTER_MIN_SEGMENT_SIZE;
      }
    }

    /* If the number of pages used by the current b-tree segment is greater
    ** than the size of the working set (VdbeSorter.nWorking), start a new
    ** segment b-tree.  */
    if( pSorter->nWorking && nPage>=(pSorter->nPage + pSorter->nWorking) ){
      BtCursor *p = pCsr->pCursor;/* Cursor structure to close and reopen */
      int iRoot;                  /* Root page of new tree */
      sqlite3BtreeCloseCursor(p);
      rc = sqlite3BtreeCreateTable(pCsr->pBt, &iRoot, BTREE_BLOBKEY);
      if( rc==SQLITE_OK ){
        rc = vdbeSorterAppendRoot(db, pSorter, iRoot);
      }
      if( rc==SQLITE_OK ){
        rc = sqlite3BtreeCursor(pCsr->pBt, iRoot, 1, pCsr->pKeyInfo, p);
      }
      pSorter->nPage = nPage;
    }
  }
  return rc;
}

/*
** Extend the pSorter->aIter[] and pSorter->aTree[] arrays using DbRealloc().
** Return SQLITE_OK if successful, or SQLITE_NOMEM otherwise.
*/
static int vdbeSorterGrowArrays(sqlite3* db, VdbeSorter *pSorter){
  int *aTree;                     /* New aTree[] allocation */
  VdbeSorterIter *aIter;          /* New aIter[] allocation */
  int nOld = pSorter->nAlloc;     /* Current size of arrays */
  int nNew = (nOld?nOld*2:64);    /* Size of arrays after reallocation */

  /* Realloc aTree[]. */
  aTree = sqlite3DbRealloc(db, pSorter->aTree, sizeof(int)*nNew);
  if( !aTree ) return SQLITE_NOMEM;
  memset(&aTree[nOld], 0, (nNew-nOld) * sizeof(int));
  pSorter->aTree = aTree;

  /* Realloc aIter[]. */
  aIter = sqlite3DbRealloc(db, pSorter->aIter, sizeof(VdbeSorterIter)*nNew);
  if( !aIter ) return SQLITE_NOMEM;
  memset(&aIter[nOld], 0, (nNew-nOld) * sizeof(VdbeSorterIter));
  pSorter->aIter = aIter;

  /* Set VdbeSorter.nAlloc to the new size of the arrays and return OK. */
  pSorter->nAlloc = nNew;
  return SQLITE_OK;
}

/*
** Helper function for sqlite3VdbeSorterRewind().
*/
static int vdbeSorterInitMerge(
  sqlite3 *db,
  VdbeCursor *pCsr,
  int iFirst,
  int *piNext
){
  Pager *pPager = sqlite3BtreePager(pCsr->pBt);
  VdbeSorter *pSorter = pCsr->pSorter;
  int rc = SQLITE_OK;
  int i;
  int nMaxRef = (pSorter->nWorking * 9/10);
  int N = 2;

  /* Initialize as many iterators as possible. */
  for(i=iFirst; rc==SQLITE_OK && i<pSorter->nRoot; i++){
    int iIter = i - iFirst;

    assert( iIter<=pSorter->nAlloc );
    if( iIter==pSorter->nAlloc ){
      rc = vdbeSorterGrowArrays(db, pSorter);
    }

    if( rc==SQLITE_OK ){
      VdbeSorterIter *pIter = &pSorter->aIter[iIter];
      rc = vdbeSorterIterInit(db, pCsr, pSorter->aRoot[i], pIter);
      if( i>iFirst+1 ){
        int nRef = sqlite3PagerRefcount(pPager) + (i+1-iFirst);
        if( nRef>=nMaxRef ){
          i++;
          break;
        }
      }
    }
  }
  *piNext = i;

  while( (i-iFirst)>N ) N += N;
  pSorter->nTree = N;

  /* Populate the aTree[] array. */
  for(i=N-1; rc==SQLITE_OK && i>0; i--){
    rc = vdbeSorterDoCompare(pCsr, i);
  }

  return rc;
}

/*
** Once the sorter has been populated, this function is called to prepare
** for iterating through its contents in sorted order.
*/
int sqlite3VdbeSorterRewind(sqlite3 *db, VdbeCursor *pCsr, int *pbEof){
  int rc = SQLITE_OK;             /* Return code */
  int N;
  int i;

  VdbeSorter *pSorter = pCsr->pSorter;
  BtCursor *p = pCsr->pCursor;    /* Cursor structure */

  assert( pSorter );
  sqlite3BtreeCloseCursor(p);

  while( rc==SQLITE_OK ){
    int iNext = 0;                /* Index of next segment to open */
    int iRoot = 0;                /* aRoot[] slot if merging to a new segment */

    do {
      rc = vdbeSorterInitMerge(db, pCsr, iNext, &iNext);

      if( rc==SQLITE_OK && (iRoot>0 || iNext<pSorter->nRoot) ){
        int pgno;
        int bEof = 0;
        rc = sqlite3BtreeCreateTable(pCsr->pBt, &pgno, BTREE_BLOBKEY);
        if( rc==SQLITE_OK ){
          pSorter->aRoot[iRoot] = pgno;
          rc = sqlite3BtreeCursor(pCsr->pBt, pgno, 1, pCsr->pKeyInfo, p);
        }

        while( rc==SQLITE_OK && bEof==0 ){
          VdbeSorterIter *pIter = &pSorter->aIter[ pSorter->aTree[1] ];
          rc = sqlite3BtreeInsert(p, pIter->aKey, pIter->nKey, 0, 0, 0, 1, 0);
          if( rc==SQLITE_OK ){
            rc = sqlite3VdbeSorterNext(db, pCsr, &bEof);
          }
        }
        sqlite3BtreeCloseCursor(p);
        iRoot++;
      }
    } while( rc==SQLITE_OK && iNext<pSorter->nRoot );

    if( iRoot==0 ) break;
    pSorter->nRoot = iRoot;
  }

  *pbEof = (pSorter->aIter[pSorter->aTree[1]].pCsr==0);
  return rc;
}

/*
** Advance to the next element in the sorter.
*/
int sqlite3VdbeSorterNext(sqlite3 *db, VdbeCursor *pCsr, int *pbEof){
  VdbeSorter *pSorter = pCsr->pSorter;
  int iPrev = pSorter->aTree[1];  /* Index of iterator to advance */
  int i;                          /* Index of aTree[] to recalculate */
  int rc;                         /* Return code */

  rc = vdbeSorterIterNext(db, pCsr, &pSorter->aIter[iPrev]);
  for(i=(pSorter->nTree+iPrev)/2; rc==SQLITE_OK && i>0; i=i/2){
    rc = vdbeSorterDoCompare(pCsr, i);
  }

  *pbEof = (pSorter->aIter[pSorter->aTree[1]].pCsr==0);
  return rc;
}

/*
** Copy the current sorter key into the memory cell pOut.
*/
int sqlite3VdbeSorterRowkey(sqlite3 *db, VdbeCursor *pCsr, Mem *pOut){
  VdbeSorter *pSorter = pCsr->pSorter;
  VdbeSorterIter *pIter;

  pIter = &pSorter->aIter[ pSorter->aTree[1] ];
  if( sqlite3VdbeMemGrow(pOut, pIter->nKey, 0) ){
    return SQLITE_NOMEM;
  }
  pOut->n = pIter->nKey;
  MemSetTypeFlag(pOut, MEM_Blob);
  memcpy(pOut->z, pIter->aKey, pIter->nKey);

  return SQLITE_OK;
}

# 2011 July 9
#
# 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.
#
#***********************************************************************
# This file implements regression tests for SQLite library.  The
# focus of this file is testing the CREATE INDEX statement.
#

set testdir [file dirname $argv0]
source $testdir/tester.tcl

set testprefix index4

do_execsql_test 1.1 {
  BEGIN;
    CREATE TABLE t1(x);
    INSERT INTO t1 VALUES(randomblob(102));
    INSERT INTO t1 SELECT randomblob(102) FROM t1;     --     2
    INSERT INTO t1 SELECT randomblob(102) FROM t1;     --     4
    INSERT INTO t1 SELECT randomblob(102) FROM t1;     --     8
    INSERT INTO t1 SELECT randomblob(102) FROM t1;     --    16
    INSERT INTO t1 SELECT randomblob(102) FROM t1;     --    32
    INSERT INTO t1 SELECT randomblob(102) FROM t1;     --    64
    INSERT INTO t1 SELECT randomblob(102) FROM t1;     --   128
    INSERT INTO t1 SELECT randomblob(102) FROM t1;     --   256
    INSERT INTO t1 SELECT randomblob(102) FROM t1;     --   512
    INSERT INTO t1 SELECT randomblob(102) FROM t1;     --  1024
    INSERT INTO t1 SELECT randomblob(102) FROM t1;     --  2048
    INSERT INTO t1 SELECT randomblob(102) FROM t1;     --  4096
    INSERT INTO t1 SELECT randomblob(102) FROM t1;     --  8192
    INSERT INTO t1 SELECT randomblob(102) FROM t1;     -- 16384
    INSERT INTO t1 SELECT randomblob(102) FROM t1;     -- 32768
    INSERT INTO t1 SELECT randomblob(102) FROM t1;     -- 65536
  COMMIT;
}

do_execsql_test 1.2 {
  CREATE INDEX i1 ON t1(x);
}
do_execsql_test 1.3 {
  PRAGMA integrity_check 
} {ok}

# The same test again - this time with limited memory.
#
ifcapable memorymanage {
  set soft_limit [sqlite3_soft_heap_limit 50000]

  db close
  sqlite3 db test.db

  do_execsql_test 1.4 {
    PRAGMA cache_size = 10;
    CREATE INDEX i2 ON t1(x);
  }
  do_execsql_test 1.5 {
    PRAGMA integrity_check 
  } {ok}

  sqlite3_soft_heap_limit $soft_limit
}


finish_test