** database page. The first argument to each is the number of usable** bytes on each page of the database (often 1024). The second is the** page number to look up in the pointer map.**** PTRMAP_PAGENO returns the database page number of the pointer-map** page that stores the required pointer. PTRMAP_PTROFFSET returns** the offset of the requested map entry.**** If the pgno argument passed to PTRMAP_PAGENO is a pointer-map page,** then pgno is returned. So (pgno==PTRMAP_PAGENO(pgsz, pgno)) can be** used to test if pgno is a pointer-map page. PTRMAP_ISPAGE implements** this test.*/#define PTRMAP_PAGENO(pBt, pgno) ptrmapPageno(pBt, pgno)#define PTRMAP_PTROFFSET(pBt, pgno) (5*(pgno-ptrmapPageno(pBt, pgno)-1))#define PTRMAP_ISPAGE(pBt, pgno) (PTRMAP_PAGENO((pBt),(pgno))==(pgno))static Pgno ptrmapPageno(BtShared *pBt, Pgno pgno){  int nPagesPerMapPage = (pBt->usableSize/5)+1;  int iPtrMap = (pgno-2)/nPagesPerMapPage;  int ret = (iPtrMap*nPagesPerMapPage) + 2;   if( ret==PENDING_BYTE_PAGE(pBt) ){    ret++;  }  return ret;}/*** The pointer map is a lookup table that identifies the parent page for** each child page in the database file.  The parent page is the page that** contains a pointer to the child.  Every page in the database contains** 0 or 1 parent pages.  (In this context 'database page' refers** to any page that is not part of the pointer map itself.)  Each pointer map** entry consists of a single byte 'type' and a 4 byte parent page number.** The PTRMAP_XXX identifiers below are the valid types.**** The purpose of the pointer map is to facility moving pages from one** position in the file to another as part of autovacuum.  When a page** is moved, the pointer in its parent must be updated to point to the** new location.  The pointer map is used to locate the parent page quickly.**** PTRMAP_ROOTPAGE: The database page is a root-page. The page-number is not**                  used in this case.**** PTRMAP_FREEPAGE: The database page is an unused (free) page. The page-number **                  is not used in this case.**** PTRMAP_OVERFLOW1: The database page is the first page in a list of **                   overflow pages. The page number identifies the page that**                   contains the cell with a pointer to this overflow page.**** PTRMAP_OVERFLOW2: The database page is the second or later page in a list of**                   overflow pages. The page-number identifies the previous**                   page in the overflow page list.**** PTRMAP_BTREE: The database page is a non-root btree page. The page number**               identifies the parent page in the btree.*/#define PTRMAP_ROOTPAGE 1#define PTRMAP_FREEPAGE 2#define PTRMAP_OVERFLOW1 3#define PTRMAP_OVERFLOW2 4#define PTRMAP_BTREE 5/*** Write an entry into the pointer map.**** This routine updates the pointer map entry for page number 'key'** so that it maps to type 'eType' and parent page number 'pgno'.** An error code is returned if something goes wrong, otherwise SQLITE_OK.*/static int ptrmapPut(BtShared *pBt, Pgno key, u8 eType, Pgno parent){  u8 *pPtrmap;    /* The pointer map page */  Pgno iPtrmap;   /* The pointer map page number */  int offset;     /* Offset in pointer map page */  int rc;  /* The master-journal page number must never be used as a pointer map page */  assert( 0==PTRMAP_ISPAGE(pBt, PENDING_BYTE_PAGE(pBt)) );  assert( pBt->autoVacuum );  if( key==0 ){    return SQLITE_CORRUPT_BKPT;  }  iPtrmap = PTRMAP_PAGENO(pBt, key);  rc = sqlite3pager_get(pBt->pPager, iPtrmap, (void **)&pPtrmap);  if( rc!=SQLITE_OK ){    return rc;  }  offset = PTRMAP_PTROFFSET(pBt, key);  if( eType!=pPtrmap[offset] || get4byte(&pPtrmap[offset+1])!=parent ){    TRACE(("PTRMAP_UPDATE: %d->(%d,%d)\n", key, eType, parent));    rc = sqlite3pager_write(pPtrmap);    if( rc==SQLITE_OK ){      pPtrmap[offset] = eType;      put4byte(&pPtrmap[offset+1], parent);    }  }  sqlite3pager_unref(pPtrmap);  return rc;}/*** Read an entry from the pointer map.**** This routine retrieves the pointer map entry for page 'key', writing** the type and parent page number to *pEType and *pPgno respectively.** An error code is returned if something goes wrong, otherwise SQLITE_OK.*/static int ptrmapGet(BtShared *pBt, Pgno key, u8 *pEType, Pgno *pPgno){  int iPtrmap;       /* Pointer map page index */  u8 *pPtrmap;       /* Pointer map page data */  int offset;        /* Offset of entry in pointer map */  int rc;  iPtrmap = PTRMAP_PAGENO(pBt, key);  rc = sqlite3pager_get(pBt->pPager, iPtrmap, (void **)&pPtrmap);  if( rc!=0 ){    return rc;  }  offset = PTRMAP_PTROFFSET(pBt, key);  assert( pEType!=0 );  *pEType = pPtrmap[offset];  if( pPgno ) *pPgno = get4byte(&pPtrmap[offset+1]);  sqlite3pager_unref(pPtrmap);  if( *pEType<1 || *pEType>5 ) return SQLITE_CORRUPT_BKPT;  return SQLITE_OK;}#endif /* SQLITE_OMIT_AUTOVACUUM *//*** Given a btree page and a cell index (0 means the first cell on** the page, 1 means the second cell, and so forth) return a pointer** to the cell content.**** This routine works only for pages that do not contain overflow cells.*/static u8 *findCell(MemPage *pPage, int iCell){  u8 *data = pPage->aData;  assert( iCell>=0 );  assert( iCell<get2byte(&data[pPage->hdrOffset+3]) );  return data + get2byte(&data[pPage->cellOffset+2*iCell]);}/*** This a more complex version of findCell() that works for** pages that do contain overflow cells.  See insert*/static u8 *findOverflowCell(MemPage *pPage, int iCell){  int i;  for(i=pPage->nOverflow-1; i>=0; i--){    int k;    struct _OvflCell *pOvfl;    pOvfl = &pPage->aOvfl[i];    k = pOvfl->idx;    if( k<=iCell ){      if( k==iCell ){        return pOvfl->pCell;      }      iCell--;    }  }  return findCell(pPage, iCell);}/*** Parse a cell content block and fill in the CellInfo structure.  There** are two versions of this function.  parseCell() takes a cell index** as the second argument and parseCellPtr() takes a pointer to the** body of the cell as its second argument.*/static void parseCellPtr(  MemPage *pPage,         /* Page containing the cell */  u8 *pCell,              /* Pointer to the cell text. */  CellInfo *pInfo         /* Fill in this structure */){  int n;                  /* Number bytes in cell content header */  u32 nPayload;           /* Number of bytes of cell payload */  pInfo->pCell = pCell;  assert( pPage->leaf==0 || pPage->leaf==1 );  n = pPage->childPtrSize;  assert( n==4-4*pPage->leaf );  if( pPage->hasData ){    n += getVarint32(&pCell[n], &nPayload);  }else{    nPayload = 0;  }  pInfo->nData = nPayload;  if( pPage->intKey ){    n += getVarint(&pCell[n], (u64 *)&pInfo->nKey);  }else{    u32 x;    n += getVarint32(&pCell[n], &x);    pInfo->nKey = x;    nPayload += x;  }  pInfo->nHeader = n;  if( nPayload<=pPage->maxLocal ){    /* This is the (easy) common case where the entire payload fits    ** on the local page.  No overflow is required.    */    int nSize;          /* Total size of cell content in bytes */    pInfo->nLocal = nPayload;    pInfo->iOverflow = 0;    nSize = nPayload + n;    if( nSize<4 ){      nSize = 4;        /* Minimum cell size is 4 */    }    pInfo->nSize = nSize;  }else{    /* If the payload will not fit completely on the local page, we have    ** to decide how much to store locally and how much to spill onto    ** overflow pages.  The strategy is to minimize the amount of unused    ** space on overflow pages while keeping the amount of local storage    ** in between minLocal and maxLocal.    **    ** Warning:  changing the way overflow payload is distributed in any    ** way will result in an incompatible file format.    */    int minLocal;  /* Minimum amount of payload held locally */    int maxLocal;  /* Maximum amount of payload held locally */    int surplus;   /* Overflow payload available for local storage */    minLocal = pPage->minLocal;    maxLocal = pPage->maxLocal;    surplus = minLocal + (nPayload - minLocal)%(pPage->pBt->usableSize - 4);    if( surplus <= maxLocal ){      pInfo->nLocal = surplus;    }else{      pInfo->nLocal = minLocal;    }    pInfo->iOverflow = pInfo->nLocal + n;    pInfo->nSize = pInfo->iOverflow + 4;  }}static void parseCell(  MemPage *pPage,         /* Page containing the cell */  int iCell,              /* The cell index.  First cell is 0 */  CellInfo *pInfo         /* Fill in this structure */){  parseCellPtr(pPage, findCell(pPage, iCell), pInfo);}/*** Compute the total number of bytes that a Cell needs in the cell** data area of the btree-page.  The return number includes the cell** data header and the local payload, but not any overflow page or** the space used by the cell pointer.*/#ifndef NDEBUGstatic int cellSize(MemPage *pPage, int iCell){  CellInfo info;  parseCell(pPage, iCell, &info);  return info.nSize;}#endifstatic int cellSizePtr(MemPage *pPage, u8 *pCell){  CellInfo info;  parseCellPtr(pPage, pCell, &info);  return info.nSize;}#ifndef SQLITE_OMIT_AUTOVACUUM/*** If the cell pCell, part of page pPage contains a pointer** to an overflow page, insert an entry into the pointer-map** for the overflow page.*/static int ptrmapPutOvflPtr(MemPage *pPage, u8 *pCell){  if( pCell ){    CellInfo info;    parseCellPtr(pPage, pCell, &info);    if( (info.nData+(pPage->intKey?0:info.nKey))>info.nLocal ){      Pgno ovfl = get4byte(&pCell[info.iOverflow]);      return ptrmapPut(pPage->pBt, ovfl, PTRMAP_OVERFLOW1, pPage->pgno);    }  }  return SQLITE_OK;}/*** If the cell with index iCell on page pPage contains a pointer** to an overflow page, insert an entry into the pointer-map** for the overflow page.*/static int ptrmapPutOvfl(MemPage *pPage, int iCell){  u8 *pCell;  pCell = findOverflowCell(pPage, iCell);  return ptrmapPutOvflPtr(pPage, pCell);}#endif/*** Do sanity checking on a page.  Throw an exception if anything is** not right.**** This routine is used for internal error checking only.  It is omitted** from most builds.*/#if defined(BTREE_DEBUG) && !defined(NDEBUG) && 0static void _pageIntegrity(MemPage *pPage){  int usableSize;  u8 *data;  int i, j, idx, c, pc, hdr, nFree;  int cellOffset;  int nCell, cellLimit;  u8 *used;  used = sqliteMallocRaw( pPage->pBt->pageSize );  if( used==0 ) return;  usableSize = pPage->pBt->usableSize;  assert( pPage->aData==&((unsigned char*)pPage)[-pPage->pBt->pageSize] );  hdr = pPage->hdrOffset;  assert( hdr==(pPage->pgno==1 ? 100 : 0) );  assert( pPage->pgno==sqlite3pager_pagenumber(pPage->aData) );  c = pPage->aData[hdr];  if( pPage->isInit ){    assert( pPage->leaf == ((c & PTF_LEAF)!=0) );    assert( pPage->zeroData == ((c & PTF_ZERODATA)!=0) );    assert( pPage->leafData == ((c & PTF_LEAFDATA)!=0) );    assert( pPage->intKey == ((c & (PTF_INTKEY|PTF_LEAFDATA))!=0) );    assert( pPage->hasData ==             !(pPage->zeroData || (!pPage->leaf && pPage->leafData)) );    assert( pPage->cellOffset==pPage->hdrOffset+12-4*pPage->leaf );    assert( pPage->nCell = get2byte(&pPage->aData[hdr+3]) );  }  data = pPage->aData;  memset(used, 0, usableSize);  for(i=0; i<hdr+10-pPage->leaf*4; i++) used[i] = 1;  nFree = 0;  pc = get2byte(&data[hdr+1]);  while( pc ){    int size;    assert( pc>0 && pc<usableSize-4 );    size = get2byte(&data[pc+2]);    assert( pc+size<=usableSize );    nFree += size;    for(i=pc; i<pc+size; i++){      assert( used[i]==0 );      used[i] = 1;    }    pc = get2byte(&data[pc]);  }  idx = 0;  nCell = get2byte(&data[hdr+3]);  cellLimit = get2byte(&data[hdr+5]);  assert( pPage->isInit==0          || pPage->nFree==nFree+data[hdr+7]+cellLimit-(cellOffset+2*nCell) );  cellOffset = pPage->cellOffset;  for(i=0; i<nCell; i++){    int size;    pc = get2byte(&data[cellOffset+2*i]);    assert( pc>0 && pc<usableSize-4 );    size = cellSize(pPage, &data[pc]);    assert( pc+size<=usableSize );    for(j=pc; j<pc+size; j++){      assert( used[j]==0 );      used[j] = 1;    }  }  for(i=cellOffset+2*nCell; i<cellimit; i++){    assert( used[i]==0 );    used[i] = 1;  }  nFree = 0;  for(i=0; i<usableSize; i++){    assert( used[i]<=1 );    if( used[i]==0 ) nFree++;  }  assert( nFree==data[hdr+7] );