/*
        ** Enter a mutex on the given BTree object.
        **
        ** If the object is not sharable, then no mutex is ever required
        ** and this routine is a no-op.  The underlying mutex is non-recursive.
        ** But we keep a reference count in Btree.wantToLock so the behavior
        ** of this interface is recursive.
        **
        ** To avoid deadlocks, multiple Btrees are locked in the same order
        ** by all database connections.  The p->pNext is a list of other
        ** Btrees belonging to the same database connection as the p Btree
        ** which need to be locked after p.  If we cannot get a lock on
        ** p, then first unlock all of the others on p->pNext, then wait
        ** for the lock to become available on p, then relock all of the
        ** subsequent Btrees that desire a lock.
        */
        void sqlite3BtreeEnter(Btree *p)
        {
            Btree *pLater;

            /* Some basic sanity checking on the Btree.  The list of Btrees
            ** connected by pNext and pPrev should be in sorted order by
            ** Btree.pBt value. All elements of the list should belong to
            ** the same connection. Only shared Btrees are on the list. */
            assert( p->pNext==0 || p->pNext->pBt>p->pBt );
            assert( p->pPrev==0 || p->pPrev->pBt<p->pBt );
            assert( p->pNext==0 || p->pNext->db==p->db );
            assert( p->pPrev==0 || p->pPrev->db==p->db );
            assert( p->sharable || (p->pNext==0 && p->pPrev==0) );

            /* Check for locking consistency */
            assert( !p->locked || p->wantToLock>0 );
            assert( p->sharable || p->wantToLock==0 );

            /* We should already hold a lock on the database connection */
            assert( sqlite3_mutex_held(p->db->mutex) );

            /* Unless the database is sharable and unlocked, then BtShared.db
            ** should already be set correctly. */
            assert( (p->locked==0 && p->sharable) || p->pBt->db==p->db );

            if( !p->sharable ) return;
            p->wantToLock++;
            if( p->locked ) return;

            /* In most cases, we should be able to acquire the lock we
            ** want without having to go throught the ascending lock
            ** procedure that follows.  Just be sure not to block.
            */
            if( sqlite3_mutex_try(p->pBt->mutex)==SQLITE_OK ){
            p->pBt->db = p->db;
            p->locked = 1;
            return;
            }

            /* To avoid deadlock, first release all locks with a larger
            ** BtShared address.  Then acquire our lock.  Then reacquire
            ** the other BtShared locks that we used to hold in ascending
            ** order.
            */
            for(pLater=p->pNext; pLater; pLater=pLater->pNext){
            assert( pLater->sharable );
            assert( pLater->pNext==0 || pLater->pNext->pBt>pLater->pBt );
            assert( !pLater->locked || pLater->wantToLock>0 );
            if( pLater->locked ){
            unlockBtreeMutex(pLater);
            }
            }
            lockBtreeMutex(p);
            for(pLater=p->pNext; pLater; pLater=pLater->pNext){
            if( pLater->wantToLock ){
            lockBtreeMutex(pLater);
            }
            }
        }

		/*
		** 2007 August 27
		**
		** The author disclaims copyright to this source code.  In place of
		** a legal notice, here is a blessing:
		**
		**    May you do good and not evil.
		**    May you find forgiveness for yourself and forgive others.
		**    May you share freely, never taking more than you give.
		**
		*************************************************************************
		**
		** This file contains code used to implement mutexes on Btree objects.
		** This code really belongs in btree.c.  But btree.c is getting too
		** big and we want to break it down some.  This packaged seemed like
		** a good breakout.
		 *************************************************************************
		**  Included in SQLite3 port to C#-SQLite;  2008 Noah B Hart
		**  C#-SQLite is an independent reimplementation of the SQLite software library
		**
		**  SQLITE_SOURCE_ID: 2011-05-19 13:26:54 ed1da510a239ea767a01dc332b667119fa3c908e
		**
		*************************************************************************
		*/
		//#include "btreeInt.h"
#if !SQLITE_OMIT_SHARED_CACHE
#if SQLITE_THREADSAFE

/*
** Obtain the BtShared mutex associated with B-Tree handle p. Also,
** set BtShared.db to the database handle associated with p and the
** p->locked boolean to true.
*/
static void lockBtreeMutex(Btree *p){
  assert( p->locked==0 );
  assert( sqlite3_mutex_notheld(p->pBt->mutex) );
  assert( sqlite3_mutex_held(p->db->mutex) );

  sqlite3_mutex_enter(p->pBt->mutex);
  p->pBt->db = p->db;
  p->locked = 1;
}

/*
** Release the BtShared mutex associated with B-Tree handle p and
** clear the p->locked boolean.
*/
static void unlockBtreeMutex(Btree *p){
assert( p->locked==1 );
assert( sqlite3_mutex_held(p->pBt->mutex) );
assert( sqlite3_mutex_held(p->db->mutex) );
assert( p->db==p->pBt->db );

sqlite3_mutex_leave(p->pBt->mutex);
p->locked = 0;
}

/*
** Add a lock on the table with root-page iTable to the shared-btree used
** by Btree handle p. Parameter eLock must be either READ_LOCK or 
** WRITE_LOCK.
**
** This function assumes the following:
**
**   (a) The specified Btree object p is connected to a sharable
**       database (one with the BtShared.sharable flag set), and
**
**   (b) No other Btree objects hold a lock that conflicts
**       with the requested lock (i.e. querySharedCacheTableLock() has
**       already been called and returned SQLITE_OK).
**
** SQLITE_OK is returned if the lock is added successfully. SQLITE_NOMEM 
** is returned if a malloc attempt fails.
*/
static int setSharedCacheTableLock(Btree p, Pgno iTable, u8 eLock){
BtShared pBt = p.pBt;
BtLock pLock = 0;
BtLock pIter;

Debug.Assert( sqlite3BtreeHoldsMutex(p) );
Debug.Assert( eLock==READ_LOCK || eLock==WRITE_LOCK );
Debug.Assert( p.db!=null );

/* A connection with the read-uncommitted flag set will never try to
** obtain a read-lock using this function. The only read-lock obtained
** by a connection in read-uncommitted mode is on the sqlite_master
** table, and that lock is obtained in BtreeBeginTrans().  */
Debug.Assert( 0==(p.db.flags&SQLITE_ReadUncommitted) || eLock==WRITE_LOCK );

/* This function should only be called on a sharable b-tree after it
** has been determined that no other b-tree holds a conflicting lock.  */
Debug.Assert( p.sharable );
Debug.Assert( SQLITE_OK==querySharedCacheTableLock(p, iTable, eLock) );

/* First search the list for an existing lock on this table. */
for(pIter=pBt.pLock; pIter; pIter=pIter.pNext){
if( pIter.iTable==iTable && pIter.pBtree==p ){
pLock = pIter;
break;
}
}

/* If the above search did not find a BtLock struct associating Btree p
** with table iTable, allocate one and link it into the list.
*/
if( !pLock ){
pLock = (BtLock *)sqlite3MallocZero(sizeof(BtLock));
if( !pLock ){
return SQLITE_NOMEM;
}
pLock.iTable = iTable;
pLock.pBtree = p;
pLock.pNext = pBt.pLock;
pBt.pLock = pLock;
}

/* Set the BtLock.eLock variable to the maximum of the current lock
** and the requested lock. This means if a write-lock was already held
** and a read-lock requested, we don't incorrectly downgrade the lock.
*/
Debug.Assert( WRITE_LOCK>READ_LOCK );
if( eLock>pLock.eLock ){
pLock.eLock = eLock;
}

return SQLITE_OK;
}

 //# define sqlite3BtreeHoldsMutex(X) 1
 static bool sqlite3BtreeHoldsMutex( Btree X )
 {
   return true;
 }

 //# define sqlite3BtreeSharable(X) 0
 static bool sqlite3BtreeSharable( Btree X )
 {
   return false;
 }

    //int sqlite3BtreeCursor(
    //  Btree*,                              /* BTree containing table to open */
    //  int iTable,                          /* Index of root page */
    //  int wrFlag,                          /* 1 for writing.  0 for read-only */
    //  struct KeyInfo*,                     /* First argument to compare function */
    //  BtCursor pCursor                    /* Space to write cursor structure */
    //);
    //int sqlite3BtreeCursorSize(void);
    //void sqlite3BtreeCursorZero(BtCursor);

    //int sqlite3BtreeCloseCursor(BtCursor);
    //int sqlite3BtreeMovetoUnpacked(
    //  BtCursor*,
    //  UnpackedRecord pUnKey,
    //  i64 intKey,
    //  int bias,
    //  int pRes
    //);
    //int sqlite3BtreeCursorHasMoved(BtCursor*, int);
    //int sqlite3BtreeDelete(BtCursor);
    //int sqlite3BtreeInsert(BtCursor*, const void pKey, i64 nKey,
    //                                  const void pData, int nData,
    //                                  int nZero, int bias, int seekResult);
    //int sqlite3BtreeFirst(BtCursor*, int pRes);
    //int sqlite3BtreeLast(BtCursor*, int pRes);
    //int sqlite3BtreeNext(BtCursor*, int pRes);
    //int sqlite3BtreeEof(BtCursor);
    //int sqlite3BtreePrevious(BtCursor*, int pRes);
    //int sqlite3BtreeKeySize(BtCursor*, i64 pSize);
    //int sqlite3BtreeKey(BtCursor*, u32 offset, u32 amt, void);
    //const void *sqlite3BtreeKeyFetch(BtCursor*, int pAmt);
    //const void *sqlite3BtreeDataFetch(BtCursor*, int pAmt);
    //int sqlite3BtreeDataSize(BtCursor*, u32 pSize);
    //int sqlite3BtreeData(BtCursor*, u32 offset, u32 amt, void);
    //void sqlite3BtreeSetCachedRowid(BtCursor*, sqlite3_int64);
    //sqlite3_int64 sqlite3BtreeGetCachedRowid(BtCursor);

    //char *sqlite3BtreeIntegrityCheck(Btree*, int *aRoot, int nRoot, int, int);
    //struct Pager *sqlite3BtreePager(Btree);

    //int sqlite3BtreePutData(BtCursor*, u32 offset, u32 amt, void);
    //void sqlite3BtreeCacheOverflow(BtCursor );
    //void sqlite3BtreeClearCursor(BtCursor );

    //int sqlite3BtreeSetVersion(Btree *pBt, int iVersion);

    //#if !NDEBUG
    //int sqlite3BtreeCursorIsValid(BtCursor);
    //#endif

    //#if !SQLITE_OMIT_BTREECOUNT
    //int sqlite3BtreeCount(BtCursor *, i64 );
    //#endif

    //#if SQLITE_TEST
    //int sqlite3BtreeCursorInfo(BtCursor*, int*, int);
    //void sqlite3BtreeCursorList(Btree);
    //#endif

#if !SQLITE_OMIT_WAL
//int sqlite3BtreeCheckpoint(Btree*, int, int *, int );
#endif

    /*
** If we are not using shared cache, then there is no need to
** use mutexes to access the BtShared structures.  So make the
** Enter and Leave procedures no-ops.
*/
#if !SQLITE_OMIT_SHARED_CACHE
//void sqlite3BtreeEnter(Btree);
//void sqlite3BtreeEnterAll(sqlite3);
#else
    //# define sqlite3BtreeEnter(X)
    static void sqlite3BtreeEnter( Btree bt )
    {
    }

/*
** Return true if a particular Btree requires a lock.  Return FALSE if
** no lock is ever required since it is not sharable.
*/
int sqlite3BtreeSharable(Btree *p){
  return p->sharable;
}

/*
** Exit the recursive mutex on a Btree.
*/
void sqlite3BtreeLeave(Btree *p){
  if( p->sharable ){
assert( p->wantToLock>0 );
p->wantToLock--;
if( p->wantToLock==0 ){
  unlockBtreeMutex(p);
}
  }
}

 /*
 ** Add a new Btree pointer to a BtreeMutexArray.
 ** if the pointer can possibly be shared with
 ** another database connection.
 **
 ** The pointers are kept in sorted order by pBtree->pBt.  That
 ** way when we go to enter all the mutexes, we can enter them
 ** in order without every having to backup and retry and without
 ** worrying about deadlock.
 **
 ** The number of shared btrees will always be small (usually 0 or 1)
 ** so an insertion sort is an adequate algorithm here.
 */
 void sqlite3BtreeMutexArrayInsert(BtreeMutexArray *pArray, Btree *pBtree)
 {
     int i, j;
     BtShared *pBt;
     if( pBtree==0 || pBtree->sharable==0 ) return;
     #if !NDEBUG
     {
     for(i=0; i<pArray->nMutex; i++){
     assert( pArray->aBtree[i]!=pBtree );
     }
     }
     #endif
     assert( pArray->nMutex>=0 );
     assert( pArray->nMutex<ArraySize(pArray->aBtree)-1 );
     pBt = pBtree->pBt;
     for(i=0; i<pArray->nMutex; i++){
     assert( pArray->aBtree[i]!=pBtree );
     if( pArray->aBtree[i]->pBt>pBt ){
     for(j=pArray->nMutex; j>i; j--){
     pArray->aBtree[j] = pArray->aBtree[j-1];
     }
     pArray->aBtree[i] = pBtree;
     pArray->nMutex++;
     return;
     }
     }
     pArray->aBtree[pArray->nMutex++] = pBtree;
 }

    /*
    ** This routine is called to create a connection to a database BTree
    ** driver.  If zFilename is the name of a file, then that file is
    ** opened and used.  If zFilename is the magic name ":memory:" then
    ** the database is stored in memory (and is thus forgotten as soon as
    ** the connection is closed.)  If zFilename is NULL then the database
    ** is a "virtual" database for transient use only and is deleted as
    ** soon as the connection is closed.
    **
    ** A virtual database can be either a disk file (that is automatically
    ** deleted when the file is closed) or it an be held entirely in memory.
    ** The sqlite3TempInMemory() function is used to determine which.
    */
    static int sqlite3BtreeFactory(
    sqlite3 db,           /* Main database when opening aux otherwise 0 */
    string zFilename,     /* Name of the file containing the BTree database */
    bool omitJournal,     /* if TRUE then do not journal this file */
    int nCache,           /* How many pages in the page cache */
    int vfsFlags,         /* Flags passed through to vfsOpen */
    ref Btree ppBtree     /* Pointer to new Btree object written here */
    )
    {
      int btFlags = 0;
      int rc;

      Debug.Assert( sqlite3_mutex_held( db.mutex ) );
      //Debug.Assert( ppBtree != null);
      if ( omitJournal )
      {
        btFlags |= BTREE_OMIT_JOURNAL;
      }
      if ( ( db.flags & SQLITE_NoReadlock ) != 0 )
      {
        btFlags |= BTREE_NO_READLOCK;
      }
#if !SQLITE_OMIT_MEMORYDB
      if ( String.IsNullOrEmpty( zFilename ) && sqlite3TempInMemory( db ) )
      {

        zFilename = ":memory:";
      }
#endif // * SQLITE_OMIT_MEMORYDB */

      if ( ( vfsFlags & SQLITE_OPEN_MAIN_DB ) != 0 && ( zFilename == null ) )
      {// || *zFilename==0) ){
        vfsFlags = ( vfsFlags & ~SQLITE_OPEN_MAIN_DB ) | SQLITE_OPEN_TEMP_DB;
      }
      rc = sqlite3BtreeOpen( zFilename, db, ref ppBtree, btFlags, vfsFlags );
      /* If the B-Tree was successfully opened, set the pager-cache size to the
      ** default value. Except, if the call to BtreeOpen() returned a handle
      ** open on an existing shared pager-cache, do not change the pager-cache
      ** size.
      */
      if ( rc == SQLITE_OK && null == sqlite3BtreeSchema( ppBtree, 0, null ) )
      {
        sqlite3BtreeSetCacheSize( ppBtree, nCache );
      }
      return rc;
    }

//#define invalidateIncrblobCursors(x,y,z)
static void invalidateIncrblobCursors( Btree x, i64 y, int z )
{
}

/*
** This function changes all write-locks held by Btree p into read-locks.
*/
static void downgradeAllSharedCacheTableLocks(Btree p){
BtShared pBt = p.pBt;
if( pBt.pWriter==p ){
BtLock pLock;
pBt.pWriter = 0;
pBt.isExclusive = 0;
pBt.isPending = 0;
for(pLock=pBt.pLock; pLock; pLock=pLock.pNext){
Debug.Assert( pLock.eLock==READ_LOCK || pLock.pBtree==p );
pLock.eLock = READ_LOCK;
}
}
}

/*
** Release all the table locks (locks obtained via calls to
** the setSharedCacheTableLock() procedure) held by Btree object p.
**
** This function assumes that Btree p has an open read or write 
** transaction. If it does not, then the BtShared.isPending variable
** may be incorrectly cleared.
*/
static void clearAllSharedCacheTableLocks(Btree p){
BtShared pBt = p.pBt;
BtLock **ppIter = &pBt.pLock;

Debug.Assert( sqlite3BtreeHoldsMutex(p) );
Debug.Assert( p.sharable || 0==*ppIter );
Debug.Assert( p.inTrans>0 );

while( ppIter ){
BtLock pLock = ppIter;
Debug.Assert( pBt.isExclusive==null || pBt.pWriter==pLock.pBtree );
Debug.Assert( pLock.pBtree.inTrans>=pLock.eLock );
if( pLock.pBtree==p ){
ppIter = pLock.pNext;
//Debug.Assert( pLock.iTable!=1 || pLock==&p.lock );
if( pLock.iTable!=1 ){
pLock=null;//sqlite3_free(ref pLock);
}
}else{
ppIter = &pLock.pNext;
}
}

Debug.Assert( pBt.isPending==null || pBt.pWriter );
if( pBt.pWriter==p ){
pBt.pWriter = 0;
pBt.isExclusive = 0;
pBt.isPending = 0;
}else if( pBt.nTransaction==2 ){
/* This function is called when Btree p is concluding its 
** transaction. If there currently exists a writer, and p is not
** that writer, then the number of locks held by connections other
** than the writer must be about to drop to zero. In this case
** set the isPending flag to 0.
**
** If there is not currently a writer, then BtShared.isPending must
** be zero already. So this next line is harmless in that case.
*/
pBt.isPending = 0;
}
}

    /* A bunch of Debug.Assert() statements to check the transaction state variables
    ** of handle p (type Btree*) are internally consistent.
    */
#if DEBUG
    //#define btreeIntegrity(p) \
    //  Debug.Assert( p.pBt.inTransaction!=TRANS_NONE || p.pBt.nTransaction==0 ); \
    //  Debug.Assert( p.pBt.inTransaction>=p.inTrans );
    static void btreeIntegrity( Btree p )
    {
      Debug.Assert( p.pBt.inTransaction != TRANS_NONE || p.pBt.nTransaction == 0 );
      Debug.Assert( p.pBt.inTransaction >= p.inTrans );
    }

/*
** Return true if the BtShared mutex is held on the btree, or if the
** B-Tree is not marked as sharable.
**
** This routine is used only from within assert() statements.
*/
int sqlite3BtreeHoldsMutex(Btree *p){
  assert( p->sharable==0 || p->locked==0 || p->wantToLock>0 );
  assert( p->sharable==0 || p->locked==0 || p->db==p->pBt->db );
  assert( p->sharable==0 || p->locked==0 || sqlite3_mutex_held(p->pBt->mutex) );
  assert( p->sharable==0 || p->locked==0 || sqlite3_mutex_held(p->db->mutex) );

  return (p->sharable==0 || p->locked);
}

        private void Mark()
        {
            int bitmapSize = (int) (SupportClass.URShift(header.root[currIndex].size, (dbAllocationQuantumBits + 5))) + 1;
            bool existsNotMarkedObjects;
            long pos;
            int i, j;

            if (listener != null)
            {
                listener.GcStarted();
            }

            greyBitmap = new int[bitmapSize];
            blackBitmap = new int[bitmapSize];
            int rootOid = header.root[currIndex].rootObject;
            if (rootOid != 0)
            {
                MarkOid(rootOid);
                do
                {
                    existsNotMarkedObjects = false;
                    for (i = 0; i < bitmapSize; i++)
                    {
                        if (greyBitmap[i] != 0)
                        {
                            existsNotMarkedObjects = true;
                            for (j = 0; j < 32; j++)
                            {
                                if ((greyBitmap[i] & (1 << j)) != 0)
                                {
                                    pos = (((long) i << 5) + j) << dbAllocationQuantumBits;
                                    greyBitmap[i] &= ~ (1 << j);
                                    blackBitmap[i] |= 1 << j;
                                    int offs = (int) pos & (Page.pageSize - 1);
                                    Page pg = pool.GetPage(pos - offs);
                                    int typeOid = ObjectHeader.GetType(pg.data, offs);
                                    if (typeOid != 0)
                                    {
                                        ClassDescriptor desc = FindClassDescriptor(typeOid);
                                        if (typeof(Btree).IsAssignableFrom(desc.cls))
                                        {
                                            Btree btree = new Btree(pg.data, ObjectHeader.Sizeof + offs);
                                            btree.AssignOid(this, 0, false);
                                            btree.MarkTree();
                                        }
                                        else if (desc.hasReferences)
                                        {
                                            MarkObject(pool.Get(pos), ObjectHeader.Sizeof, desc);
                                        }
                                    }
                                    pool.Unfix(pg);
                                }
                            }
                        }
                    }
                }
                while (existsNotMarkedObjects);
            }
        }

/*
** The following are special cases for mutex enter routines for use
** in single threaded applications that use shared cache.  Except for
** these two routines, all mutex operations are no-ops in that case and
** are null #defines in btree.h.
**
** If shared cache is disabled, then all btree mutex routines, including
** the ones below, are no-ops and are null #defines in btree.h.
*/

void sqlite3BtreeEnter(Btree *p){
  p->pBt->db = p->db;
}

        private int Sweep()
        {
            int nDeallocated = 0;
            long pos;
            gcDone = true;
            for (int i = dbFirstUserId, j = committedIndexSize; i < j; i++)
            {
                pos = GetGCPos(i);
                if (pos != 0 && ((int) pos & (dbPageObjectFlag | dbFreeHandleFlag)) == 0)
                {
                    int bit = (int) (SupportClass.URShift(pos, dbAllocationQuantumBits));
                    if ((blackBitmap[SupportClass.URShift(bit, 5)] & (1 << (bit & 31))) == 0)
                    {
                        // object is not accessible
                        if (GetPos(i) != pos)
                        {
                            throw new StorageError(StorageError.INVALID_OID);
                        }
                        int offs = (int) pos & (Page.pageSize - 1);
                        Page pg = pool.GetPage(pos - offs);
                        int typeOid = ObjectHeader.GetType(pg.data, offs);
                        if (typeOid != 0)
                        {
                            ClassDescriptor desc = FindClassDescriptor(typeOid);
                            nDeallocated += 1;
                            if (typeof(Btree).IsAssignableFrom(desc.cls))
                            {
                                Btree btree = new Btree(pg.data, ObjectHeader.Sizeof + offs);
                                pool.Unfix(pg);
                                btree.AssignOid(this, i, false);
                                btree.Deallocate();
                            }
                            else
                            {
                                int size = ObjectHeader.GetSize(pg.data, offs);
                                pool.Unfix(pg);
                                FreeId(i);
                                objectCache.Remove(i);
                                CloneBitmap(pos, size);
                            }
                            if (listener != null)
                            {
                                listener.DeallocateObject(desc.cls, i);
                            }
                        }
                    }
                }
            }

            greyBitmap = null;
            blackBitmap = null;
            allocatedDelta = 0;
            gcActive = false;

            if (listener != null)
                listener.GcCompleted(nDeallocated);

            return nDeallocated;
        }

 //# define sqlite3BtreeMutexArrayInsert(X,Y)
 static void sqlite3BtreeMutexArrayInsert( BtreeMutexArray X, Btree Y ) { }