** beginning of the page and all free space is collected ** into one big FreeBlk at the end of the page.*/static void defragmentPage(Btree *pBt, MemPage *pPage){  int pc, i, n;  FreeBlk *pFBlk;  char newPage[SQLITE_USABLE_SIZE];  assert( sqlitepager_iswriteable(pPage) );  assert( pPage->isInit );  pc = sizeof(PageHdr);  pPage->u.hdr.firstCell = SWAB16(pBt, pc);  memcpy(newPage, pPage->u.aDisk, pc);  for(i=0; i<pPage->nCell; i++){    Cell *pCell = pPage->apCell[i];    /* This routine should never be called on an overfull page.  The    ** following asserts verify that constraint. */    assert( Addr(pCell) > Addr(pPage) );    assert( Addr(pCell) < Addr(pPage) + SQLITE_USABLE_SIZE );    n = cellSize(pBt, pCell);    pCell->h.iNext = SWAB16(pBt, pc + n);    memcpy(&newPage[pc], pCell, n);    pPage->apCell[i] = (Cell*)&pPage->u.aDisk[pc];    pc += n;  }  assert( pPage->nFree==SQLITE_USABLE_SIZE-pc );  memcpy(pPage->u.aDisk, newPage, pc);  if( pPage->nCell>0 ){    pPage->apCell[pPage->nCell-1]->h.iNext = 0;  }  pFBlk = (FreeBlk*)&pPage->u.aDisk[pc];  pFBlk->iSize = SWAB16(pBt, SQLITE_USABLE_SIZE - pc);  pFBlk->iNext = 0;  pPage->u.hdr.firstFree = SWAB16(pBt, pc);  memset(&pFBlk[1], 0, SQLITE_USABLE_SIZE - pc - sizeof(FreeBlk));}/*** Allocate nByte bytes of space on a page.  nByte must be a ** multiple of 4.**** Return the index into pPage->u.aDisk[] of the first byte of** the new allocation. Or return 0 if there is not enough free** space on the page to satisfy the allocation request.**** If the page contains nBytes of free space but does not contain** nBytes of contiguous free space, then this routine automatically** calls defragementPage() to consolidate all free space before ** allocating the new chunk.*/static int allocateSpace(Btree *pBt, MemPage *pPage, int nByte){  FreeBlk *p;  u16 *pIdx;  int start;  int iSize;#ifndef NDEBUG  int cnt = 0;#endif  assert( sqlitepager_iswriteable(pPage) );  assert( nByte==ROUNDUP(nByte) );  assert( pPage->isInit );  if( pPage->nFree<nByte || pPage->isOverfull ) return 0;  pIdx = &pPage->u.hdr.firstFree;  p = (FreeBlk*)&pPage->u.aDisk[SWAB16(pBt, *pIdx)];  while( (iSize = SWAB16(pBt, p->iSize))<nByte ){    assert( cnt++ < SQLITE_USABLE_SIZE/4 );    if( p->iNext==0 ){      defragmentPage(pBt, pPage);      pIdx = &pPage->u.hdr.firstFree;    }else{      pIdx = &p->iNext;    }    p = (FreeBlk*)&pPage->u.aDisk[SWAB16(pBt, *pIdx)];  }  if( iSize==nByte ){    start = SWAB16(pBt, *pIdx);    *pIdx = p->iNext;  }else{    FreeBlk *pNew;    start = SWAB16(pBt, *pIdx);    pNew = (FreeBlk*)&pPage->u.aDisk[start + nByte];    pNew->iNext = p->iNext;    pNew->iSize = SWAB16(pBt, iSize - nByte);    *pIdx = SWAB16(pBt, start + nByte);  }  pPage->nFree -= nByte;  return start;}/*** Return a section of the MemPage.u.aDisk[] to the freelist.** The first byte of the new free block is pPage->u.aDisk[start]** and the size of the block is "size" bytes.  Size must be** a multiple of 4.**** Most of the effort here is involved in coalesing adjacent** free blocks into a single big free block.*/static void freeSpace(Btree *pBt, MemPage *pPage, int start, int size){  int end = start + size;  u16 *pIdx, idx;  FreeBlk *pFBlk;  FreeBlk *pNew;  FreeBlk *pNext;  int iSize;  assert( sqlitepager_iswriteable(pPage) );  assert( size == ROUNDUP(size) );  assert( start == ROUNDUP(start) );  assert( pPage->isInit );  pIdx = &pPage->u.hdr.firstFree;  idx = SWAB16(pBt, *pIdx);  while( idx!=0 && idx<start ){    pFBlk = (FreeBlk*)&pPage->u.aDisk[idx];    iSize = SWAB16(pBt, pFBlk->iSize);    if( idx + iSize == start ){      pFBlk->iSize = SWAB16(pBt, iSize + size);      if( idx + iSize + size == SWAB16(pBt, pFBlk->iNext) ){        pNext = (FreeBlk*)&pPage->u.aDisk[idx + iSize + size];        if( pBt->needSwab ){          pFBlk->iSize = swab16((u16)swab16(pNext->iSize)+iSize+size);        }else{          pFBlk->iSize += pNext->iSize;        }        pFBlk->iNext = pNext->iNext;      }      pPage->nFree += size;      return;    }    pIdx = &pFBlk->iNext;    idx = SWAB16(pBt, *pIdx);  }  pNew = (FreeBlk*)&pPage->u.aDisk[start];  if( idx != end ){    pNew->iSize = SWAB16(pBt, size);    pNew->iNext = SWAB16(pBt, idx);  }else{    pNext = (FreeBlk*)&pPage->u.aDisk[idx];    pNew->iSize = SWAB16(pBt, size + SWAB16(pBt, pNext->iSize));    pNew->iNext = pNext->iNext;  }  *pIdx = SWAB16(pBt, start);  pPage->nFree += size;}/*** Initialize the auxiliary information for a disk block.**** The pParent parameter must be a pointer to the MemPage which** is the parent of the page being initialized.  The root of the** BTree (usually page 2) has no parent and so for that page, ** pParent==NULL.**** Return SQLITE_OK on success.  If we see that the page does** not contain a well-formed database page, then return ** SQLITE_CORRUPT.  Note that a return of SQLITE_OK does not** guarantee that the page is well-formed.  It only shows that** we failed to detect any corruption.*/static int initPage(Bt *pBt, MemPage *pPage, Pgno pgnoThis, MemPage *pParent){  int idx;           /* An index into pPage->u.aDisk[] */  Cell *pCell;       /* A pointer to a Cell in pPage->u.aDisk[] */  FreeBlk *pFBlk;    /* A pointer to a free block in pPage->u.aDisk[] */  int sz;            /* The size of a Cell in bytes */  int freeSpace;     /* Amount of free space on the page */  if( pPage->pParent ){    assert( pPage->pParent==pParent );    return SQLITE_OK;  }  if( pParent ){    pPage->pParent = pParent;    sqlitepager_ref(pParent);  }  if( pPage->isInit ) return SQLITE_OK;  pPage->isInit = 1;  pPage->nCell = 0;  freeSpace = USABLE_SPACE;  idx = SWAB16(pBt, pPage->u.hdr.firstCell);  while( idx!=0 ){    if( idx>SQLITE_USABLE_SIZE-MIN_CELL_SIZE ) goto page_format_error;    if( idx<sizeof(PageHdr) ) goto page_format_error;    if( idx!=ROUNDUP(idx) ) goto page_format_error;    pCell = (Cell*)&pPage->u.aDisk[idx];    sz = cellSize(pBt, pCell);    if( idx+sz > SQLITE_USABLE_SIZE ) goto page_format_error;    freeSpace -= sz;    pPage->apCell[pPage->nCell++] = pCell;    idx = SWAB16(pBt, pCell->h.iNext);  }  pPage->nFree = 0;  idx = SWAB16(pBt, pPage->u.hdr.firstFree);  while( idx!=0 ){    int iNext;    if( idx>SQLITE_USABLE_SIZE-sizeof(FreeBlk) ) goto page_format_error;    if( idx<sizeof(PageHdr) ) goto page_format_error;    pFBlk = (FreeBlk*)&pPage->u.aDisk[idx];    pPage->nFree += SWAB16(pBt, pFBlk->iSize);    iNext = SWAB16(pBt, pFBlk->iNext);    if( iNext>0 && iNext <= idx ) goto page_format_error;    idx = iNext;  }  if( pPage->nCell==0 && pPage->nFree==0 ){    /* As a special case, an uninitialized root page appears to be    ** an empty database */    return SQLITE_OK;  }  if( pPage->nFree!=freeSpace ) goto page_format_error;  return SQLITE_OK;page_format_error:  return SQLITE_CORRUPT;}/*** Set up a raw page so that it looks like a database page holding** no entries.*/static void zeroPage(Btree *pBt, MemPage *pPage){  PageHdr *pHdr;  FreeBlk *pFBlk;  assert( sqlitepager_iswriteable(pPage) );  memset(pPage, 0, SQLITE_USABLE_SIZE);  pHdr = &pPage->u.hdr;  pHdr->firstCell = 0;  pHdr->firstFree = SWAB16(pBt, sizeof(*pHdr));  pFBlk = (FreeBlk*)&pHdr[1];  pFBlk->iNext = 0;  pPage->nFree = SQLITE_USABLE_SIZE - sizeof(*pHdr);  pFBlk->iSize = SWAB16(pBt, pPage->nFree);  pPage->nCell = 0;  pPage->isOverfull = 0;}/*** This routine is called when the reference count for a page** reaches zero.  We need to unref the pParent pointer when that** happens.*/static void pageDestructor(void *pData){  MemPage *pPage = (MemPage*)pData;  if( pPage->pParent ){    MemPage *pParent = pPage->pParent;    pPage->pParent = 0;    sqlitepager_unref(pParent);  }}/*** Open a new database.**** Actually, this routine just sets up the internal data structures** for accessing the database.  We do not open the database file ** until the first page is loaded.**** zFilename is the name of the database file.  If zFilename is NULL** a new database with a random name is created.  This randomly named** database file will be deleted when sqliteBtreeClose() is called.*/int sqliteBtreeOpen(  const char *zFilename,    /* Name of the file containing the BTree database */  int omitJournal,          /* if TRUE then do not journal this file */  int nCache,               /* How many pages in the page cache */  Btree **ppBtree           /* Pointer to new Btree object written here */){  Btree *pBt;  int rc;  /*  ** The following asserts make sure that structures used by the btree are  ** the right size.  This is to guard against size changes that result  ** when compiling on a different architecture.  */  assert( sizeof(u32)==4 );  assert( sizeof(u16)==2 );  assert( sizeof(Pgno)==4 );  assert( sizeof(PageHdr)==8 );  assert( sizeof(CellHdr)==12 );  assert( sizeof(FreeBlk)==4 );  assert( sizeof(OverflowPage)==SQLITE_USABLE_SIZE );  assert( sizeof(FreelistInfo)==OVERFLOW_SIZE );  assert( sizeof(ptr)==sizeof(char*) );  assert( sizeof(uptr)==sizeof(ptr) );  pBt = sqliteMalloc( sizeof(*pBt) );  if( pBt==0 ){    *ppBtree = 0;    return SQLITE_NOMEM;  }  if( nCache<10 ) nCache = 10;  rc = sqlitepager_open(&pBt->pPager, zFilename, nCache, EXTRA_SIZE,                        !omitJournal);  if( rc!=SQLITE_OK ){    if( pBt->pPager ) sqlitepager_close(pBt->pPager);    sqliteFree(pBt);    *ppBtree = 0;    return rc;  }  sqlitepager_set_destructor(pBt->pPager, pageDestructor);  pBt->pCursor = 0;  pBt->page1 = 0;  pBt->readOnly = sqlitepager_isreadonly(pBt->pPager);  pBt->pOps = &sqliteBtreeOps;  *ppBtree = pBt;  return SQLITE_OK;}/*** Close an open database and invalidate all cursors.*/static int fileBtreeClose(Btree *pBt){  while( pBt->pCursor ){    fileBtreeCloseCursor(pBt->pCursor);  }  sqlitepager_close(pBt->pPager);  sqliteFree(pBt);  return SQLITE_OK;}/*** Change the limit on the number of pages allowed in the cache.**** The maximum number of cache pages is set to the absolute** value of mxPage.  If mxPage is negative, the pager will** operate asynchronously - it will not stop to do fsync()s** to insure data is written to the disk surface before** continuing.  Transactions still work if synchronous is off,** and the database cannot be corrupted if this program** crashes.  But if the operating system crashes or there is** an abrupt power failure when synchronous is off, the database** could be left in an inconsistent and unrecoverable state.** Synchronous is on by default so database corruption is not** normally a worry.*/static int fileBtreeSetCacheSize(Btree *pBt, int mxPage){  sqlitepager_set_cachesize(pBt->pPager, mxPage);  return SQLITE_OK;}/*** Change the way data is synced to disk in order to increase or decrease** how well the database resists damage due to OS crashes and power** failures.  Level 1 is the same as asynchronous (no syncs() occur and** there is a high probability of damage)  Level 2 is the default.  There** is a very low but non-zero probability of damage.  Level 3 reduces the** probability of damage to near zero but with a write performance reduction.*/static int fileBtreeSetSafetyLevel(Btree *pBt, int level){  sqlitepager_set_safety_level(pBt->pPager, level);  return SQLITE_OK;}/*** Get a reference to page1 of the database file.  This will** also acquire a readlock on that file.**** SQLITE_OK is returned on success.  If the file is not a** well-formed database file, then SQLITE_CORRUPT is returned.** SQLITE_BUSY is returned if the database is locked.  SQLITE_NOMEM** is returned if we run out of memory.  SQLITE_PROTOCOL is returned** if there is a locking protocol violation.*/static int lockBtree(Btree *pBt){  int rc;  if( pBt->page1 ) return SQLITE_OK;  rc = sqlitepager_get(pBt->pPager, 1, (void**)&pBt->page1);  if( rc!=SQLITE_OK ) return rc;  /* Do some checking to help insure the file we opened really is  ** a valid database file.   */  if( sqlitepager_pagecount(pBt->pPager)>0 ){    PageOne *pP1 = pBt->page1;    if( strcmp(pP1->zMagic,zMagicHeader)!=0 ||          (pP1->iMagic!=MAGIC && swab32(pP1->iMagic)!=MAGIC) ){      rc = SQLITE_NOTADB;      goto page1_init_failed;    }    pBt->needSwab = pP1->iMagic!=MAGIC;  }  return rc;page1_init_failed:  sqlitepager_unref(pBt->page1);  pBt->page1 = 0;  return rc;}/*** If there are no outstanding cursors and we are not in the middle** of a transaction but there is a read lock on the database, then** this routine unrefs the first page of the database file which ** has the effect of releasing the read lock.**** If there are any outstanding cursors, this routine is a no-op.**** If there is a transaction in progress, this routine is a no-op.*/static void unlockBtreeIfUnused(Btree *pBt){  if( pBt->inTrans==0 && pBt->pCursor==0 && pBt->page1!=0 ){    sqlitepager_unref(pBt->page1);    pBt->page1 = 0;    pBt->inTrans = 0;    pBt->inCkpt = 0;  }}/*** Create a new database by initializing the first two pages of the** file.*/static int newDatabase(Btree *pBt){  MemPage *pRoot;  PageOne *pP1;