SQLite4  Check-in [1df60437f3]

#define BT_MAX_DIRECT_OVERFLOW 8  /* Maximum direct overflow pages per cell */

/*
** Values that make up the single byte flags field at the start of
** b-tree pages. 
*/
#define BT_PGFLAGS_INTERNAL 0x01  /* True for non-leaf nodes */
#define BT_PGFLAGS_METATREE 0x02  /* True for a meta-tree page */
#define BT_PGFLAGS_SCHEDULE 0x04  /* True for a schedule-tree page */

/* #define BT_STDERR_DEBUG 1 */

typedef struct BtCursor BtCursor;
typedef struct FiCursor FiCursor;

struct bt_db {

  int bAscii,                     /* True to print keys and values as ASCII */
  BtPager *pPager,                /* Pager object (or NULL) */
  u8 *aData, int nData,           /* Buffer containing page data */
  sqlite4_buffer *pBuf            /* Output buffer */
){
  int i;
  int nCell = (int)btCellCount(aData, nData);
  u8 flags = btFlags(aData);      /* Page flags */

  sqlite4BtBufAppendf(pBuf, "Page %d: ", pgno);
  sqlite4BtBufAppendf(pBuf, "nCell=%d ", nCell);
  sqlite4BtBufAppendf(pBuf, "iFree=%d ", (int)btFreeOffset(aData, nData));
  sqlite4BtBufAppendf(pBuf, "flags=%d ", (int)btFlags(aData));
  if( btFlags(aData) & BT_PGFLAGS_INTERNAL ){
    sqlite4BtBufAppendf(pBuf, "rchild=%d ", (int)btGetU32(&aData[1]));
  }
  sqlite4BtBufAppendf(pBuf, "cell-offsets=(");
  for(i=0; i<nCell; i++){
    u8 *ptr = btCellPtrFind(aData, nData, i);
    sqlite4BtBufAppendf(pBuf, "%s%d", i==0?"":" ", (int)btGetU16(ptr));
  }
  sqlite4BtBufAppendf(pBuf, ")\n");

  for(i=0; i<nCell; i++){
    u8 *pCell;          /* Cell i */
    int nKey;           /* Number of bytes of key to output */
    u8 *pKey;           /* Buffer containing key. */
    int nVal;           /* Number of bytes of value to output */
    u8 *pVal = 0;       /* Buffer containing value. */

    pCell = btCellFind(aData, nData, i);
    sqlite4BtBufAppendf(pBuf, "  Cell %d: ", i);

    pCell += sqlite4BtVarintGet32(pCell, &nKey);
    pKey = pCell;
    pCell += nKey;
    btBufferAppendBlob(pBuf, bAscii, pKey, nKey);

    if( flags & BT_PGFLAGS_INTERNAL ){
      sqlite4BtBufAppendf(pBuf, "  child=%d ", (int)btGetU32(pCell));
    }else{

      sqlite4BtBufAppendf(pBuf, "  ");
      pCell += sqlite4BtVarintGet32(pCell, &nVal);
      if( nVal>=2 ){
        nVal -= 2;
        pVal = pCell;
      }else{
        sqlite4BtBufAppendf(pBuf, "delete-key");
      }
    }
    if( pVal ){
      btBufferAppendBlob(pBuf, bAscii, pVal, nVal);
      if( flags & BT_PGFLAGS_METATREE ){
        /* Interpret the meta-tree entry */
        u32 iAge = btGetU32(&pKey[0]);
        u32 iLevel = ~btGetU32(&pKey[4]);
        u32 iBlk = btGetU32(pVal);
        sqlite4BtBufAppendf(pBuf, "  [age=%d level=%d block=%d]", 
            (int)iAge, (int)iLevel, (int)iBlk
        );
      }
    }
    sqlite4BtBufAppendf(pBuf, "\n");
  }

  if( pPager && btFlags(aData) & BT_PGFLAGS_INTERNAL ){
    for(i=0; i<btCellCount(aData, nData); i++){
      BtPage *pChild;

    }
  }

  btCsrReset(&csr, 1);
  return rc;
}

static int btAllocateNewRoot(bt_db *db, int flag, u32 *piNew){
  u32 iNew = 0;
  BtPage *pPg;
  int rc;

  assert( flag==BT_PGFLAGS_METATREE || flag==BT_PGFLAGS_SCHEDULE || flag==0 );
  rc = sqlite4BtPageAllocate(db->pPager, &pPg);
  if( rc==SQLITE4_OK ){
    u8 *aData = sqlite4BtPageData(pPg);
    aData[0] = (flag & 0xFF);
    iNew = sqlite4BtPagePgno(pPg);
    sqlite4BtPageRelease(pPg);
  }

  *piNew = iNew;
  return rc;
}

  BtDbHdr *pHdr, 
  u32 *piRoot
){
  int rc = SQLITE4_OK;

  /* If the meta-tree has not been created, create it now. */
  if( pHdr->iMRoot==0 ){
    rc = btAllocateNewRoot(db, BT_PGFLAGS_METATREE, &pHdr->iMRoot);
  }

  /* If no writable sub-tree has been discovered, create one now. */
  if( rc==SQLITE4_OK && pHdr->iSubBlock==0 ){
    u32 iLevel;                   /* Level number for new sub-tree */
    u32 iSubBlock;                /* New block */

<ul>
  <li> Segment age (big-endian 32-bit integer).
  <li> Level number (ones-compliment of value as a big-endian 32-bit integer).
  <li> Separator key. All keys within the segment are guaranteed to be as
       large or larger than the separator key. The separator key may be
       zero bytes in size.
</ul>

<h3> Schedule-Page Format</h3>

<p>We might need more than one schedule page. Perhaps anyway... But say 
worry about this later on.

<p>The writer adds an entry to the schedule-tree. Schedule-tree entries
are always appended to the tree - the integer key is one greater than the
previous greatest key.

<p>The entry identifies the following:
<ul>
  <li><p> the inputs to the merge (age + level range).

  <li><p> space to write the output (allocated block numbers).
</ul>

<p>As well as the above, the entry contains space allocated for output 
fields. Output fields are populated by the checkpointer as it copies the
page image from the log to the database file. Output fields are:

<ul>
  <li><p> A flag to indicate that the merge has been performed.

  <li><p> A bitmask (or some other indication) indicating which of the output
          blocks were populated.

  <li><p> A pointer to a list of overflow pages that were freed, if any.

  <li><p> A pointer to the last key read from the input.
</ul>

<p>Note the implication here: A writer may only modify the page if it currently
resides in the db file (not the log). The writer can tell if the schedule page
resides in the db file or the log by checking the "merge performed" flag.

<ul>
  <li> Age of input segments (big-endian u32).

  <li> Max level of input segments (bit-endian u32). All segments of the
       specified age with a level equal to or less than this are considered
       inputs.

  <li> Number of allocated output blocks (big-endian u32) - <i>nBlock</i>.
       Maximum is (say) 32.

  <li> Block number of each allocated block (<i>nBlock</i> big-endian 
       u32 fields).
</ul>


<h2 id=in-memory_tree>3.2. In-Memory Tree</h2>

<p>This design uses the same multi-version in-memory tree that LSM does. 
The tree structure may be located in heap or shared memory. If shared memory
is used then a separate file (*-shm2 or some such) is used for the data. The