SQLite

  int mnPmaSize;                  /* Minimum PMA size, in bytes */
  int mxPmaSize;                  /* Maximum PMA size, in bytes.  0==no limit */
  VdbeSorterIter *aIter;          /* Array of iterators to merge */
  int *aTree;                     /* Current state of incremental merge */
  sqlite3_file *pTemp1;           /* PMA file 1 */
  SorterRecord *pRecord;          /* Head of in-memory record list */
  UnpackedRecord *pUnpacked;      /* Used to unpack keys */
  u8* aMemory;                    /* Block to allocate records from */
  int iMemory;                    /* Offset of free space in aMemory */
};

/*
** The following type is an iterator for a PMA. It caches the current key in 
** variables nKey/aKey. If the iterator is at EOF, pFile==0.
*/
struct VdbeSorterIter {
  i64 iReadOff;                   /* Current read offset */
  i64 iEof;                       /* 1 byte past EOF for this iterator */
  int nAlloc;                     /* Bytes of space at aAlloc */
  int nKey;                       /* Number of bytes in key */
  sqlite3_file *pFile;            /* File iterator is reading from */
  u8 *aAlloc;                     /* Allocated space */
  u8 *aKey;                       /* Pointer to current key */
  u8 *aBuffer;                    /* Current read buffer */
  int nBuffer;                    /* Size of read buffer in bytes */
  u8 *aMap;                       /* Pointer to mapping of pFile */
};

/*
** An instance of this structure is used to organize the stream of records
** being written to files by the merge-sort code into aligned, page-sized
** blocks.  Doing all I/O in aligned page-sized blocks helps I/O to go
** faster on many operating systems.

/*
** 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){
  sqlite3DbFree(db, pIter->aAlloc);
  sqlite3DbFree(db, pIter->aBuffer);
  if( pIter->aMap ) sqlite3OsUnfetch(pIter->pFile, 0, pIter->aMap);
  memset(pIter, 0, sizeof(VdbeSorterIter));
}

/*
** Read nByte bytes of data from the stream of data iterated by object p.
** If successful, set *ppOut to point to a buffer containing the data
** and return SQLITE_OK. Otherwise, if an error occurs, return an SQLite
** error code.
**
** The buffer indicated by *ppOut may only be considered valid until the
** next call to this function.
*/
static int vdbeSorterIterRead(
  sqlite3 *db,                    /* Database handle (for malloc) */
  VdbeSorterIter *p,              /* Iterator */
  int nByte,                      /* Bytes of data to read */
  u8 **ppOut                      /* OUT: Pointer to buffer containing data */
){
  int iBuf;                       /* Offset within buffer to read from */
  int nAvail;                     /* Bytes of data available in buffer */

  if( p->aMap ){
    *ppOut = &p->aMap[p->iReadOff];
    p->iReadOff += nByte;
    return SQLITE_OK;
  }

  assert( p->aBuffer );

  /* If there is no more data to be read from the buffer, read the next 
  ** p->nBuffer bytes of data from the file into it. Or, if there are less
  ** than p->nBuffer bytes remaining in the PMA, read all remaining data.  */
  iBuf = p->iReadOff % p->nBuffer;
  if( iBuf==0 ){

/*
** Read a varint from the stream of data accessed by p. Set *pnOut to
** the value read.
*/
static int vdbeSorterIterVarint(sqlite3 *db, VdbeSorterIter *p, u64 *pnOut){
  int iBuf;

  if( p->aMap ){
    p->iReadOff += sqlite3GetVarint(&p->aMap[p->iReadOff], pnOut);
  }else{
    iBuf = p->iReadOff % p->nBuffer;
    if( iBuf && (p->nBuffer-iBuf)>=9 ){
      p->iReadOff += sqlite3GetVarint(&p->aBuffer[iBuf], pnOut);
    }else{
      u8 aVarint[16], *a;
      int i = 0, rc;
      do{
        rc = vdbeSorterIterRead(db, p, 1, &a);
        if( rc ) return rc;
        aVarint[(i++)&0xf] = a[0];
      }while( (a[0]&0x80)!=0 );
      sqlite3GetVarint(aVarint, pnOut);
    }
  }

  return SQLITE_OK;
}


/*

  const VdbeSorter *pSorter,      /* Sorter object */
  i64 iStart,                     /* Start offset in pFile */
  VdbeSorterIter *pIter,          /* Iterator to populate */
  i64 *pnByte                     /* IN/OUT: Increment this value by PMA size */
){
  int rc = SQLITE_OK;
  int nBuf;
  void *pMap;

  nBuf = sqlite3BtreeGetPageSize(db->aDb[0].pBt);

  assert( pSorter->iWriteOff>iStart );
  assert( pIter->aAlloc==0 );
  assert( pIter->aBuffer==0 );
  pIter->pFile = pSorter->pTemp1;
  pIter->iReadOff = iStart;
  pIter->nAlloc = 128;
  pIter->aAlloc = (u8 *)sqlite3DbMallocRaw(db, pIter->nAlloc);

  /* See if this PMA can be read using xFetch. */
  rc = sqlite3OsFetch(pIter->pFile, 0, pSorter->iWriteOff, &pMap);
  if( rc!=SQLITE_OK ) return rc;
  if( pMap ){
    pIter->aMap = (u8*)pMap;
  }else{
    pIter->nBuffer = nBuf;
    pIter->aBuffer = (u8 *)sqlite3DbMallocRaw(db, nBuf);

    if( !pIter->aBuffer ){
      rc = SQLITE_NOMEM;
    }else{
      int iBuf;

      iBuf = iStart % nBuf;
      if( iBuf ){
        int nRead = nBuf - iBuf;
        if( (iStart + nRead) > pSorter->iWriteOff ){
          nRead = (int)(pSorter->iWriteOff - iStart);
        }
        rc = sqlite3OsRead(
            pSorter->pTemp1, &pIter->aBuffer[iBuf], nRead, iStart
        );
        assert( rc!=SQLITE_IOERR_SHORT_READ );
      }
    }
  }

  if( rc==SQLITE_OK ){
    u64 nByte;                       /* Size of PMA in bytes */
    pIter->iEof = pSorter->iWriteOff;
    rc = vdbeSorterIterVarint(db, pIter, &nByte);
    pIter->iEof = pIter->iReadOff + nByte;
    *pnByte += nByte;

  }

  if( rc==SQLITE_OK ){
    rc = vdbeSorterIterNext(db, pIter);
  }
  return rc;
}

  if( !sqlite3TempInMemory(db) ){
    pgsz = sqlite3BtreeGetPageSize(db->aDb[0].pBt);
    pSorter->mnPmaSize = SORTER_MIN_WORKING * pgsz;
    mxCache = db->aDb[0].pSchema->cache_size;
    if( mxCache<SORTER_MIN_WORKING ) mxCache = SORTER_MIN_WORKING;
    pSorter->mxPmaSize = mxCache * pgsz;

    pSorter->aMemory = (u8*)sqlite3DbMallocRaw(db, pSorter->mxPmaSize);
    assert( pSorter->iMemory==0 );
    if( !pSorter->aMemory ) return SQLITE_NOMEM;
  }

  return SQLITE_OK;
}

/*
** Free the list of sorted records starting at pRecord.

    sqlite3DbFree(db, pSorter->aIter);
    pSorter->aIter = 0;
  }
  if( pSorter->pTemp1 ){
    sqlite3OsCloseFree(pSorter->pTemp1);
    pSorter->pTemp1 = 0;
  }
  if( pSorter->aMemory==0 ){
    vdbeSorterRecordFree(db, pSorter->pRecord);
  }
  pSorter->pRecord = 0;
  pSorter->iWriteOff = 0;
  pSorter->iReadOff = 0;
  pSorter->nInMemory = 0;
  pSorter->nTree = 0;
  pSorter->nPMA = 0;
  pSorter->aTree = 0;
  pSorter->iMemory = 0;
}


/*
** Free any cursor components allocated by sqlite3VdbeSorterXXX routines.
*/
void sqlite3VdbeSorterClose(sqlite3 *db, VdbeCursor *pCsr){
  VdbeSorter *pSorter = pCsr->pSorter;
  if( pSorter ){
    sqlite3VdbeSorterReset(db, pSorter);
    sqlite3DbFree(db, pSorter->pUnpacked);
    sqlite3DbFree(db, pSorter->aMemory);
    sqlite3DbFree(db, pSorter);
    pCsr->pSorter = 0;
  }
}

/*
** Allocate space for a file-handle and open a temporary file. If successful,
** set *ppFile to point to the malloc'd file-handle and return SQLITE_OK.
** Otherwise, set *ppFile to 0 and return an SQLite error code.
*/
static int vdbeSorterOpenTempFile(sqlite3 *db, sqlite3_file **ppFile){
  int rc;
  rc = sqlite3OsOpenMalloc(db->pVfs, 0, ppFile,
      SQLITE_OPEN_TEMP_JOURNAL |
      SQLITE_OPEN_READWRITE    | SQLITE_OPEN_CREATE |
      SQLITE_OPEN_EXCLUSIVE    | SQLITE_OPEN_DELETEONCLOSE, &rc
  );
  if( rc==SQLITE_OK ){
    i64 max = SQLITE_MAX_MMAP_SIZE;
    sqlite3OsFileControlHint( *ppFile, SQLITE_FCNTL_MMAP_SIZE, (void*)&max);
  }
  return rc;
}

/*
** Merge the two sorted lists p1 and p2 into a single list.
** Set *ppOut to the head of the new list.
**
** In cases where key values are equal, keys from list p1 are considered

static void fileWriterWriteVarint(FileWriter *p, u64 iVal){
  int nByte; 
  u8 aByte[10];
  nByte = sqlite3PutVarint(aByte, iVal);
  fileWriterWrite(p, aByte, nByte);
}

#if SQLITE_MAX_MMAP_SIZE>0
/*
** The first argument is a file-handle open on a temporary file. The file
** is guaranteed to be nByte bytes or smaller in size. This function 
** attempts to extend the file to nByte bytes in size and to ensure that
** the VFS has memory mapped it.
**
** Whether or not the file does end up memory mapped of course depends on 
** the specific VFS implementation.
*/
static int vdbeSorterExtendFile(sqlite3_file *pFile, i64 nByte){
  int rc = sqlite3OsTruncate(pFile, nByte);
  if( rc==SQLITE_OK ){
    void *p = 0;
    sqlite3OsFetch(pFile, 0, nByte, &p);
    sqlite3OsUnfetch(pFile, 0, p);
  }
  return rc;
}
#else
# define vdbeSorterExtendFile(x,y) SQLITE_OK
#endif

/*
** Write the current contents of the in-memory linked-list to a PMA. Return
** SQLITE_OK if successful, or an SQLite error code otherwise.
**
** The format of a PMA is:
**
**     * A varint. This varint contains the total number of bytes of content

  /* If the first temporary PMA file has not been opened, open it now. */
  if( rc==SQLITE_OK && pSorter->pTemp1==0 ){
    rc = vdbeSorterOpenTempFile(db, &pSorter->pTemp1);
    assert( rc!=SQLITE_OK || pSorter->pTemp1 );
    assert( pSorter->iWriteOff==0 );
    assert( pSorter->nPMA==0 );
  }

  /* Try to get the file to memory map */
  if( rc==SQLITE_OK ){
    rc = vdbeSorterExtendFile(
        pSorter->pTemp1, pSorter->iWriteOff + pSorter->nInMemory + 9
    );
  }

  if( rc==SQLITE_OK ){
    SorterRecord *p;
    SorterRecord *pNext = 0;

    fileWriterInit(db, pSorter->pTemp1, &writer, pSorter->iWriteOff);
    pSorter->nPMA++;
    fileWriterWriteVarint(&writer, pSorter->nInMemory);
    for(p=pSorter->pRecord; p; p=pNext){
      pNext = p->pNext;
      fileWriterWriteVarint(&writer, p->nVal);
      fileWriterWrite(&writer, p->pVal, p->nVal);
      if( pSorter->aMemory==0 ) sqlite3DbFree(db, p);
    }
    pSorter->pRecord = p;
    rc = fileWriterFinish(db, &writer, &pSorter->iWriteOff);
  }

  if( pSorter->aMemory ) pSorter->pRecord = 0;
  assert( pSorter->pRecord==0 || rc!=SQLITE_OK );
  return rc;
}

/*
** Add a record to the sorter.
*/
int sqlite3VdbeSorterWrite(
  sqlite3 *db,                    /* Database handle */
  const VdbeCursor *pCsr,               /* Sorter cursor */
  Mem *pVal                       /* Memory cell containing record */
){
  VdbeSorter *pSorter = pCsr->pSorter;
  SorterRecord sRecord;           /* Used for aMemory overflow record */
  int rc = SQLITE_OK;             /* Return Code */
  SorterRecord *pNew;             /* New list element */

  assert( pSorter );
  pSorter->nInMemory += sqlite3VarintLen(pVal->n) + pVal->n;

  if( pSorter->aMemory ){
    int nReq = sizeof(SorterRecord) + pVal->n;
    if( (pSorter->iMemory+nReq) > pSorter->mxPmaSize ){
      pNew = &sRecord;
      pNew->pVal = pVal->z;
    }else{
      pNew = &pSorter->aMemory[pSorter->iMemory];
      pSorter->iMemory += ROUND8(nReq);
    }
  }else{
    pNew = (SorterRecord *)sqlite3DbMallocRaw(db, pVal->n+sizeof(SorterRecord));
    if( pNew==0 ){
      return SQLITE_NOMEM;
    }
  }

  if( pNew!=&sRecord ){
    pNew->pVal = (void*)&pNew[1];
    memcpy(pNew->pVal, pVal->z, pVal->n);
  }
  pNew->nVal = pVal->n;
  pNew->pNext = pSorter->pRecord;
  pSorter->pRecord = pNew;


  /* See if the contents of the sorter should now be written out. They
  ** are written out when either of the following are true:
  **
  **   * The total memory allocated for the in-memory list is greater 
  **     than (page-size * cache-size), or
  **
  **   * The total memory allocated for the in-memory list is greater 
  **     than (page-size * 10) and sqlite3HeapNearlyFull() returns true.
  */
  if( pSorter->mxPmaSize>0 ){
    if( (pNew==&sRecord) || (pSorter->aMemory==0 && (
        (pSorter->nInMemory > pSorter->mxPmaSize)
     || (pSorter->nInMemory > pSorter->mnPmaSize && sqlite3HeapNearlyFull())
    ))){
#ifdef SQLITE_DEBUG
      i64 nExpect = pSorter->iWriteOff
        + sqlite3VarintLen(pSorter->nInMemory)
        + pSorter->nInMemory;
#endif
      rc = vdbeSorterListToPMA(db, pCsr);
      pSorter->nInMemory = 0;
      pSorter->iMemory = 0;
      assert( rc!=SQLITE_OK || (nExpect==pSorter->iWriteOff) );
      assert( rc!=SQLITE_OK || pSorter->pRecord==0 );
    }
  }

  return rc;
}

/*
** Helper function for sqlite3VdbeSorterRewind(). 

        break;
      }

      /* Open the second temp file, if it is not already open. */
      if( pTemp2==0 ){
        assert( iWrite2==0 );
        rc = vdbeSorterOpenTempFile(db, &pTemp2);
        if( rc==SQLITE_OK ){
          rc = vdbeSorterExtendFile(pTemp2, pSorter->iWriteOff);
        }
      }

      if( rc==SQLITE_OK ){
        int bEof = 0;
        fileWriterInit(db, pTemp2, &writer, iWrite2);
        fileWriterWriteVarint(&writer, nWrite);
        while( rc==SQLITE_OK && bEof==0 ){

      }
      *pbEof = (pSorter->aIter[pSorter->aTree[1]].pFile==0);
    }
  }else{
    SorterRecord *pFree = pSorter->pRecord;
    pSorter->pRecord = pFree->pNext;
    pFree->pNext = 0;
    if( pSorter->aMemory==0 ){
      vdbeSorterRecordFree(db, pFree);
    }
    *pbEof = !pSorter->pRecord;
    rc = SQLITE_OK;
  }
  return rc;
}

/*