**
** 1. Structure Records:
**
**   The set of segments that make up an index - the index structure - are
**   recorded in a single record within the %_data table. The record is a list
**   of SQLite varints. 
**






**   For each level from 0 to nMax:
**
**     + number of input segments in ongoing merge.
**     + total number of segments in level.
**     + for each segment from oldest to newest:
**         + segment id (always > 0)
**         + b-tree height (1 -> root is leaf, 2 -> root is parent of leaf etc.)
**         + first leaf page number (often 1)
................................................................................
    p->rc = SQLITE_NOMEM;
  }else{
    memset(pRet, 0, nByte);
  }
  return pRet;
}














/*
** Compare the contents of the pLeft buffer with the pRight/nRight blob.
**
** Return -ve if pLeft is smaller than pRight, 0 if they are equal or
** +ve if pRight is smaller than pLeft. In other words:
**
................................................................................
  Fts5Structure **ppOut           /* OUT: Deserialized object */
){
  int rc = SQLITE_OK;
  int i = 0;
  int iLvl;
  int nLevel = 0;
  int nSegment = 0;
  int nByte;                      /* Bytes of space to allocate */
  Fts5Structure *pRet = 0;

  /* Read the total number of levels and segments from the start of the
  ** structure record. Use these values to allocate space for the deserialized
  ** version of the record. */
  i = getVarint32(&pData[i], nLevel);
  i += getVarint32(&pData[i], nSegment);
  nByte = (
      sizeof(Fts5Structure) + 
      sizeof(Fts5StructureLevel) * (nLevel+1) +
      sizeof(Fts5StructureSegment) * (nSegment+nLevel+1)
  );
  pRet = (Fts5Structure*)sqlite3_malloc(nByte);

  if( pRet ){
    u8 *pSpace = (u8*)&pRet->aLevel[nLevel+1];
    memset(pRet, 0, nByte);
    pRet->nLevel = nLevel;
    i += sqlite3GetVarint(&pData[i], &pRet->nWriteCounter);

    for(iLvl=0; iLvl<nLevel; iLvl++){
      Fts5StructureLevel *pLvl = &pRet->aLevel[iLvl];
      int nTotal;
      int iSeg;

      i += getVarint32(&pData[i], pLvl->nMerge);
      i += getVarint32(&pData[i], nTotal);
      assert( nTotal>=pLvl->nMerge );
      pLvl->nSeg = nTotal;
      pLvl->aSeg = (Fts5StructureSegment*)pSpace;
      pSpace += ((nTotal+1) * sizeof(Fts5StructureSegment));




      for(iSeg=0; iSeg<nTotal; iSeg++){
        i += getVarint32(&pData[i], pLvl->aSeg[iSeg].iSegid);
        i += getVarint32(&pData[i], pLvl->aSeg[iSeg].nHeight);
        i += getVarint32(&pData[i], pLvl->aSeg[iSeg].pgnoFirst);
        i += getVarint32(&pData[i], pLvl->aSeg[iSeg].pgnoLast);
      }
    }











































    pRet->aLevel[nLevel].aSeg = (Fts5StructureSegment*)pSpace;







  }else{






    rc = SQLITE_NOMEM;
  }

  *ppOut = pRet;
  return rc;
}

/*
** Read, deserialize and return the structure record for index iIdx.
**
** The Fts5Structure.aLevel[] and each Fts5StructureLevel.aSeg[] array
** are over-allocated as described for function fts5StructureDecode() 
** above.
................................................................................
}

/*
** Release a reference to an Fts5Structure object returned by an earlier 
** call to fts5StructureRead() or fts5StructureDecode().
*/
static void fts5StructureRelease(Fts5Structure *pStruct){




  sqlite3_free(pStruct);
}

/*
** Return the total number of segments in index structure pStruct.
*/
static int fts5StructureCountSegments(Fts5Structure *pStruct){
................................................................................
  fprintf(stdout, "%s: %s\n", zCaption, buf.p);
  fflush(stdout);
  fts5BufferFree(&buf);
}
#else
# define fts5PrintStructure(x,y)
#endif





/*
** Return a copy of index structure pStruct. Except, promote as many segments
** as possible to level iPromote. If an OOM occurs, NULL is returned.
*/
static void fts5StructurePromoteTo(
  Fts5Index *p,
  int iPromote,
  int szPromote,
  Fts5Structure *pStruct
){
  Fts5Structure *pNew;
  u8 *pSpace;
  int nSeg = fts5StructureCountSegments(pStruct);
  int nLvl = pStruct->nLevel;
  int nByte = (
      sizeof(Fts5Structure) + 
      sizeof(Fts5StructureLevel) * (nLvl+1) +
      sizeof(Fts5StructureSegment) * (nSeg+nLvl+1)
  );
  int iTst;

  pNew = fts5IdxMalloc(p, nByte);
  if( !pNew ) return;
  pNew->nWriteCounter = pStruct->nWriteCounter;
  pNew->nLevel = pStruct->nLevel;
  pSpace = (u8*)&pNew->aLevel[nLvl+1];

  for(iTst=0; iTst<nLvl; iTst++){
    int nCopy;
    Fts5StructureLevel *pLvlOut = &pNew->aLevel[iTst];
    pLvlOut->aSeg = (Fts5StructureSegment*)pSpace;

    if( iTst==iPromote ){
      int il, is;
      int nSegCopy = 0;


      /* Figure out the number of segments that will be promoted. */
      for(il=iTst+1; il<pStruct->nLevel; il++){
        Fts5StructureLevel *pLvl = &pStruct->aLevel[il];
        if( pLvl->nMerge ) break;
        for(is=pLvl->nSeg-1; is>=0; is--){
          Fts5StructureSegment *pSeg = &pLvl->aSeg[is];
          int sz = pSeg->pgnoLast - pSeg->pgnoFirst + 1;

          if( sz>szPromote ){
            il = pStruct->nLevel;
            break;
          }
          nSegCopy++;
        }
      }
      assert( nSegCopy>0 );


      pSpace += (nSegCopy * sizeof(Fts5StructureSegment));
      pLvlOut->nSeg = nSegCopy;

      for(il=iTst+1; il<pStruct->nLevel && nSegCopy>0; il++){
        Fts5StructureLevel *pLvl = &pStruct->aLevel[il];
        for(is=pLvl->nSeg-1; is>=0 && nSegCopy>0; is--){
          Fts5StructureSegment *pSeg = &pLvl->aSeg[is];
          nSegCopy--;
          memcpy(&pLvlOut->aSeg[nSegCopy], pSeg, sizeof(Fts5StructureSegment));
          pLvl->nSeg--;
        }
      }
      assert( nSegCopy==0 );
    }

    nCopy = pStruct->aLevel[iTst].nSeg * sizeof(Fts5StructureSegment);
    if( nCopy ) memcpy(pSpace, pStruct->aLevel[iTst].aSeg, nCopy);
    pSpace += (nCopy + sizeof(Fts5StructureSegment));
    pLvlOut->nSeg += pStruct->aLevel[iTst].nSeg;
  }

  fts5PrintStructure("NEW", pNew);
  memcpy(pStruct, pNew, nByte);
  for(iTst=0; iTst<pNew->nLevel; iTst++){
    int iOff = pNew->aLevel[iTst].aSeg - (Fts5StructureSegment*)pNew;
    pStruct->aLevel[iTst].aSeg = &((Fts5StructureSegment*)pStruct)[iOff];
  }
  sqlite3_free(pNew);
}

/*
** A new segment has just been written to level iLvl of index structure
** pStruct. This function determines if any segments should be promoted
** as a result. Segments are promoted in two scenarios:
**
................................................................................
**
** If an error occurs, set the Fts5Index.rc error code. If an error has 
** already occurred, this function is a no-op.
*/
static void fts5IndexWork(
  Fts5Index *p,                   /* FTS5 backend object */
  int iIdx,                       /* Index to work on */
  Fts5Structure *pStruct,         /* Current structure of index */
  int nLeaf                       /* Number of output leaves just written */
){

  i64 nWrite;                     /* Initial value of write-counter */
  int nWork;                      /* Number of work-quanta to perform */
  int nRem;                       /* Number of leaf pages left to write */

  /* Update the write-counter. While doing so, set nWork. */
  nWrite = pStruct->nWriteCounter;
  nWork = ((nWrite + nLeaf) / p->nWorkUnit) - (nWrite / p->nWorkUnit);
................................................................................
#ifdef SQLITE_DEBUG
    for(iLvl=0; nBest==0 && iLvl<pStruct->nLevel; iLvl++){
      assert( pStruct->aLevel[iLvl].nSeg==0 );
    }
#endif

    if( nBest<p->nMinMerge && pStruct->aLevel[iBestLvl].nMerge==0 ) break;




    fts5IndexMergeLevel(p, iIdx, pStruct, iBestLvl, &nRem);
    fts5StructurePromote(p, iBestLvl+1, pStruct);
    assert( nRem==0 || p->rc==SQLITE_OK );

  }
}

/*
** Flush the contents of in-memory hash table iHash to a new level-0 
** segment on disk. Also update the corresponding structure record.
**
................................................................................
      pNext = pIter->pNext;
      fts5WritePendingDoclist(p, &writer, pIter);
      fts5FreePendingDoclist(pIter);
    }
    fts5WriteFinish(p, &writer, &nHeight, &pgnoLast);

    /* Edit the Fts5Structure and write it back to the database. */
    if( pStruct->nLevel==0 ) pStruct->nLevel = 1;




    pSeg = &pStruct->aLevel[0].aSeg[ pStruct->aLevel[0].nSeg++ ];
    pSeg->iSegid = iSegid;
    pSeg->nHeight = nHeight;
    pSeg->pgnoFirst = 1;
    pSeg->pgnoLast = pgnoLast;
  }


  fts5IndexWork(p, iHash, pStruct, pgnoLast);
  fts5StructureWrite(p, iHash, pStruct);
  fts5StructureRelease(pStruct);
}

/*
** Flush any data stored in the in-memory hash tables to the database.
*/

**
** 1. Structure Records:
**
**   The set of segments that make up an index - the index structure - are
**   recorded in a single record within the %_data table. The record is a list
**   of SQLite varints. 
**
**   The record begins with three varints:
**
**     + number of levels,
**     + total number of segments on all levels,
**     + value of write counter.
**
**   Then, for each level from 0 to nMax:
**
**     + number of input segments in ongoing merge.
**     + total number of segments in level.
**     + for each segment from oldest to newest:
**         + segment id (always > 0)
**         + b-tree height (1 -> root is leaf, 2 -> root is parent of leaf etc.)
**         + first leaf page number (often 1)
................................................................................
    p->rc = SQLITE_NOMEM;
  }else{
    memset(pRet, 0, nByte);
  }
  return pRet;
}

static void *fts5MallocZero(int *pRc, int nByte){
  void *pRet = 0;
  if( *pRc==SQLITE_OK ){
    pRet = sqlite3_malloc(nByte);
    if( pRet==0 && nByte>0 ){
      *pRc = SQLITE_NOMEM;
    }else{
      memset(pRet, 0, nByte);
    }
  }
  return pRet;
}

/*
** Compare the contents of the pLeft buffer with the pRight/nRight blob.
**
** Return -ve if pLeft is smaller than pRight, 0 if they are equal or
** +ve if pRight is smaller than pLeft. In other words:
**
................................................................................
  Fts5Structure **ppOut           /* OUT: Deserialized object */
){
  int rc = SQLITE_OK;
  int i = 0;
  int iLvl;
  int nLevel = 0;
  int nSegment = 0;
  int nByte;                      /* Bytes of space to allocate at pRet */
  Fts5Structure *pRet = 0;        /* Structure object to return */

  /* Read the total number of levels and segments from the start of the
  ** structure record.  */

  i = getVarint32(&pData[i], nLevel);
  i += getVarint32(&pData[i], nSegment);
  nByte = (
      sizeof(Fts5Structure) +                    /* Main structure */
      sizeof(Fts5StructureLevel) * (nLevel)      /* aLevel[] array */

  );
  pRet = (Fts5Structure*)fts5MallocZero(&rc, nByte);

  if( pRet ){


    pRet->nLevel = nLevel;
    i += sqlite3GetVarint(&pData[i], &pRet->nWriteCounter);

    for(iLvl=0; rc==SQLITE_OK && iLvl<nLevel; iLvl++){
      Fts5StructureLevel *pLvl = &pRet->aLevel[iLvl];
      int nTotal;
      int iSeg;

      i += getVarint32(&pData[i], pLvl->nMerge);
      i += getVarint32(&pData[i], nTotal);
      assert( nTotal>=pLvl->nMerge );

      pLvl->aSeg = (Fts5StructureSegment*)fts5MallocZero(&rc, 
          nTotal * sizeof(Fts5StructureSegment)
      );

      if( rc==SQLITE_OK ){
        pLvl->nSeg = nTotal;
        for(iSeg=0; iSeg<nTotal; iSeg++){
          i += getVarint32(&pData[i], pLvl->aSeg[iSeg].iSegid);
          i += getVarint32(&pData[i], pLvl->aSeg[iSeg].nHeight);
          i += getVarint32(&pData[i], pLvl->aSeg[iSeg].pgnoFirst);
          i += getVarint32(&pData[i], pLvl->aSeg[iSeg].pgnoLast);
        }
      }
    }
  }

  *ppOut = pRet;
  return rc;
}

/*
**
*/
static void fts5StructureAddLevel(int *pRc, Fts5Structure **ppStruct){
  if( *pRc==SQLITE_OK ){
    Fts5Structure *pStruct = *ppStruct;
    int nLevel = pStruct->nLevel;
    int nByte = (
        sizeof(Fts5Structure) +                  /* Main structure */
        sizeof(Fts5StructureLevel) * (nLevel+1)  /* aLevel[] array */
    );

    pStruct = sqlite3_realloc(pStruct, nByte);
    if( pStruct ){
      memset(&pStruct->aLevel[nLevel], 0, sizeof(Fts5StructureLevel));
      pStruct->nLevel++;
      *ppStruct = pStruct;
    }else{
      *pRc = SQLITE_NOMEM;
    }
  }
}

/*
** Extend level iLvl so that there is room for at least nExtra more
** segments.
*/
static void fts5StructureExtendLevel(
  int *pRc, 
  Fts5Structure *pStruct, 
  int iLvl, 
  int nExtra, 
  int bInsert
){
  if( *pRc==SQLITE_OK ){
    Fts5StructureLevel *pLvl = &pStruct->aLevel[iLvl];
    Fts5StructureSegment *aNew;
    int nByte;

    nByte = (pLvl->nSeg + nExtra) * sizeof(Fts5StructureSegment);
    aNew = sqlite3_realloc(pLvl->aSeg, nByte);
    if( aNew ){
      if( bInsert==0 ){
        memset(&aNew[pLvl->nSeg], 0, sizeof(Fts5StructureSegment) * nExtra);
      }else{
        int nMove = pLvl->nSeg * sizeof(Fts5StructureSegment);
        memmove(&aNew[nExtra], aNew, nMove);
        memset(aNew, 0, sizeof(Fts5StructureSegment) * nExtra);
      }
      pLvl->aSeg = aNew;
    }else{
      *pRc = SQLITE_NOMEM;
    }
  }


}

/*
** Read, deserialize and return the structure record for index iIdx.
**
** The Fts5Structure.aLevel[] and each Fts5StructureLevel.aSeg[] array
** are over-allocated as described for function fts5StructureDecode() 
** above.
................................................................................
}

/*
** Release a reference to an Fts5Structure object returned by an earlier 
** call to fts5StructureRead() or fts5StructureDecode().
*/
static void fts5StructureRelease(Fts5Structure *pStruct){
  int i;
  for(i=0; i<pStruct->nLevel; i++){
    sqlite3_free(pStruct->aLevel[i].aSeg);
  }
  sqlite3_free(pStruct);
}

/*
** Return the total number of segments in index structure pStruct.
*/
static int fts5StructureCountSegments(Fts5Structure *pStruct){
................................................................................
  fprintf(stdout, "%s: %s\n", zCaption, buf.p);
  fflush(stdout);
  fts5BufferFree(&buf);
}
#else
# define fts5PrintStructure(x,y)
#endif

static int fts5SegmentSize(Fts5StructureSegment *pSeg){
  return 1 + pSeg->pgnoLast - pSeg->pgnoFirst;
}

/*
** Return a copy of index structure pStruct. Except, promote as many segments
** as possible to level iPromote. If an OOM occurs, NULL is returned.
*/
static void fts5StructurePromoteTo(
  Fts5Index *p,
  int iPromote,
  int szPromote,
  Fts5Structure *pStruct
){























  int il, is;

  Fts5StructureLevel *pOut = &pStruct->aLevel[iPromote];


  for(il=iPromote+1; il<pStruct->nLevel; il++){
    Fts5StructureLevel *pLvl = &pStruct->aLevel[il];

    for(is=pLvl->nSeg-1; is>=0; is--){


      int sz = fts5SegmentSize(&pLvl->aSeg[is]);
      if( sz>szPromote ) return;







      fts5StructureExtendLevel(&p->rc, pStruct, iPromote, 1, 1);
      if( p->rc ) return;
      memcpy(pOut->aSeg, &pLvl->aSeg[is], sizeof(Fts5StructureSegment));
      pOut->nSeg++;







      pLvl->nSeg--;
    }
  }
















}

/*
** A new segment has just been written to level iLvl of index structure
** pStruct. This function determines if any segments should be promoted
** as a result. Segments are promoted in two scenarios:
**
................................................................................
**
** If an error occurs, set the Fts5Index.rc error code. If an error has 
** already occurred, this function is a no-op.
*/
static void fts5IndexWork(
  Fts5Index *p,                   /* FTS5 backend object */
  int iIdx,                       /* Index to work on */
  Fts5Structure **ppStruct,       /* IN/OUT: Current structure of index */
  int nLeaf                       /* Number of output leaves just written */
){
  Fts5Structure *pStruct = *ppStruct;
  i64 nWrite;                     /* Initial value of write-counter */
  int nWork;                      /* Number of work-quanta to perform */
  int nRem;                       /* Number of leaf pages left to write */

  /* Update the write-counter. While doing so, set nWork. */
  nWrite = pStruct->nWriteCounter;
  nWork = ((nWrite + nLeaf) / p->nWorkUnit) - (nWrite / p->nWorkUnit);
................................................................................
#ifdef SQLITE_DEBUG
    for(iLvl=0; nBest==0 && iLvl<pStruct->nLevel; iLvl++){
      assert( pStruct->aLevel[iLvl].nSeg==0 );
    }
#endif

    if( nBest<p->nMinMerge && pStruct->aLevel[iBestLvl].nMerge==0 ) break;
    if( iBestLvl==pStruct->nLevel-1 ){
      fts5StructureAddLevel(&p->rc, &pStruct);
    }
    fts5StructureExtendLevel(&p->rc, pStruct, iBestLvl+1, 1, 0);
    fts5IndexMergeLevel(p, iIdx, pStruct, iBestLvl, &nRem);
    fts5StructurePromote(p, iBestLvl+1, pStruct);
    assert( nRem==0 || p->rc==SQLITE_OK );
    *ppStruct = pStruct;
  }
}

/*
** Flush the contents of in-memory hash table iHash to a new level-0 
** segment on disk. Also update the corresponding structure record.
**
................................................................................
      pNext = pIter->pNext;
      fts5WritePendingDoclist(p, &writer, pIter);
      fts5FreePendingDoclist(pIter);
    }
    fts5WriteFinish(p, &writer, &nHeight, &pgnoLast);

    /* Edit the Fts5Structure and write it back to the database. */
    if( pStruct->nLevel==0 ){
      fts5StructureAddLevel(&p->rc, &pStruct);
    }
    fts5StructureExtendLevel(&p->rc, pStruct, 0, 1, 0);
    if( p->rc==SQLITE_OK ){
      pSeg = &pStruct->aLevel[0].aSeg[ pStruct->aLevel[0].nSeg++ ];
      pSeg->iSegid = iSegid;
      pSeg->nHeight = nHeight;
      pSeg->pgnoFirst = 1;
      pSeg->pgnoLast = pgnoLast;
    }
  }

  fts5IndexWork(p, iHash, &pStruct, pgnoLast);
  fts5StructureWrite(p, iHash, pStruct);
  fts5StructureRelease(pStruct);
}

/*
** Flush any data stored in the in-memory hash tables to the database.
*/