--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/engine/sqlite/src/btmutex.cpp	Thu Feb 25 14:29:19 2010 +0000
@@ -0,0 +1,315 @@
+/*
+** 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.
+**
+*************************************************************************
+**
+** $Id: btmutex.cpp 1282 2008-11-13 09:31:33Z LarsPson $
+**
+** 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.
+*/
+#include "btreeInt.h"
+#if SQLITE_THREADSAFE && !defined(SQLITE_OMIT_SHARED_CACHE)
+
+
+/*
+** 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) );
+
+  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->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 ){
+      sqlite3_mutex_leave(pLater->pBt->mutex);
+      pLater->locked = 0;
+    }
+  }
+  sqlite3_mutex_enter(p->pBt->mutex);
+  p->locked = 1;
+  for(pLater=p->pNext; pLater; pLater=pLater->pNext){
+    if( pLater->wantToLock ){
+      sqlite3_mutex_enter(pLater->pBt->mutex);
+      pLater->locked = 1;
+    }
+  }
+}
+
+/*
+** Exit the recursive mutex on a Btree.
+*/
+void sqlite3BtreeLeave(Btree *p){
+  if( p->sharable ){
+    assert( p->wantToLock>0 );
+    p->wantToLock--;
+    if( p->wantToLock==0 ){
+      assert( p->locked );
+      sqlite3_mutex_leave(p->pBt->mutex);
+      p->locked = 0;
+    }
+  }
+}
+
+#ifndef NDEBUG
+/*
+** Return true if the BtShared mutex is held on the btree.  
+**
+** This routine makes no determination one why or another if the
+** database connection mutex is held.
+**
+** This routine is used only from within assert() statements.
+*/
+int sqlite3BtreeHoldsMutex(Btree *p){
+  return (p->sharable==0 ||
+             (p->locked && p->wantToLock && sqlite3_mutex_held(p->pBt->mutex)));
+}
+#endif
+
+
+#ifndef SQLITE_OMIT_INCRBLOB
+/*
+** Enter and leave a mutex on a Btree given a cursor owned by that
+** Btree.  These entry points are used by incremental I/O and can be
+** omitted if that module is not used.
+*/
+void sqlite3BtreeEnterCursor(BtCursor *pCur){
+  sqlite3BtreeEnter(pCur->pBtree);
+}
+void sqlite3BtreeLeaveCursor(BtCursor *pCur){
+  sqlite3BtreeLeave(pCur->pBtree);
+}
+#endif /* SQLITE_OMIT_INCRBLOB */
+
+
+/*
+** Enter the mutex on every Btree associated with a database
+** connection.  This is needed (for example) prior to parsing
+** a statement since we will be comparing table and column names
+** against all schemas and we do not want those schemas being
+** reset out from under us.
+**
+** There is a corresponding leave-all procedures.
+**
+** Enter the mutexes in accending order by BtShared pointer address
+** to avoid the possibility of deadlock when two threads with
+** two or more btrees in common both try to lock all their btrees
+** at the same instant.
+*/
+void sqlite3BtreeEnterAll(sqlite3 *db){
+  int i;
+  Btree *p, *pLater;
+  assert( sqlite3_mutex_held(db->mutex) );
+  for(i=0; i<db->nDb; i++){
+    p = db->aDb[i].pBt;
+    if( p && p->sharable ){
+      p->wantToLock++;
+      if( !p->locked ){
+        assert( p->wantToLock==1 );
+        while( p->pPrev ) p = p->pPrev;
+        while( p->locked && p->pNext ) p = p->pNext;
+        for(pLater = p->pNext; pLater; pLater=pLater->pNext){
+          if( pLater->locked ){
+            sqlite3_mutex_leave(pLater->pBt->mutex);
+            pLater->locked = 0;
+          }
+        }
+        while( p ){
+          sqlite3_mutex_enter(p->pBt->mutex);
+          p->locked++;
+          p = p->pNext;
+        }
+      }
+    }
+  }
+}
+void sqlite3BtreeLeaveAll(sqlite3 *db){
+  int i;
+  Btree *p;
+  assert( sqlite3_mutex_held(db->mutex) );
+  for(i=0; i<db->nDb; i++){
+    p = db->aDb[i].pBt;
+    if( p && p->sharable ){
+      assert( p->wantToLock>0 );
+      p->wantToLock--;
+      if( p->wantToLock==0 ){
+        assert( p->locked );
+        sqlite3_mutex_leave(p->pBt->mutex);
+        p->locked = 0;
+      }
+    }
+  }
+}
+
+#ifndef NDEBUG
+/*
+** Return true if the current thread holds the database connection
+** mutex and all required BtShared mutexes.
+**
+** This routine is used inside assert() statements only.
+*/
+int sqlite3BtreeHoldsAllMutexes(sqlite3 *db){
+  int i;
+  if( !sqlite3_mutex_held(db->mutex) ){
+    return 0;
+  }
+  for(i=0; i<db->nDb; i++){
+    Btree *p;
+    p = db->aDb[i].pBt;
+    if( p && p->sharable &&
+         (p->wantToLock==0 || !sqlite3_mutex_held(p->pBt->mutex)) ){
+      return 0;
+    }
+  }
+  return 1;
+}
+#endif /* NDEBUG */
+
+/*
+** Potentially dd a new Btree pointer to a BtreeMutexArray.
+** Really only add the Btree if it can possibly be shared with
+** another database connection.
+**
+** The Btrees 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;
+#ifndef NDEBUG
+  {
+    for(i=0; i<pArray->nMutex; i++){
+      assert( pArray->aBtree[i]!=pBtree );
+    }
+  }
+#endif
+  assert( pArray->nMutex>=0 );
+  assert( pArray->nMutex<sizeof(pArray->aBtree)/sizeof(pArray->aBtree[0])-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;
+}
+
+/*
+** Enter the mutex of every btree in the array.  This routine is
+** called at the beginning of sqlite3VdbeExec().  The mutexes are
+** exited at the end of the same function.
+*/
+void sqlite3BtreeMutexArrayEnter(BtreeMutexArray *pArray){
+  int i;
+  for(i=0; i<pArray->nMutex; i++){
+    Btree *p = pArray->aBtree[i];
+    /* Some basic sanity checking */
+    assert( i==0 || pArray->aBtree[i-1]->pBt<p->pBt );
+    assert( !p->locked || p->wantToLock>0 );
+
+    /* We should already hold a lock on the database connection */
+    assert( sqlite3_mutex_held(p->db->mutex) );
+
+    p->wantToLock++;
+    if( !p->locked && p->sharable ){
+      sqlite3_mutex_enter(p->pBt->mutex);
+      p->locked = 1;
+    }
+  }
+}
+
+/*
+** Leave the mutex of every btree in the group.
+*/
+void sqlite3BtreeMutexArrayLeave(BtreeMutexArray *pArray){
+  int i;
+  for(i=0; i<pArray->nMutex; i++){
+    Btree *p = pArray->aBtree[i];
+    /* Some basic sanity checking */
+    assert( i==0 || pArray->aBtree[i-1]->pBt<p->pBt );
+    assert( p->locked || !p->sharable );
+    assert( p->wantToLock>0 );
+
+    /* We should already hold a lock on the database connection */
+    assert( sqlite3_mutex_held(p->db->mutex) );
+
+    p->wantToLock--;
+    if( p->wantToLock==0 && p->locked ){
+      sqlite3_mutex_leave(p->pBt->mutex);
+      p->locked = 0;
+    }
+  }
+}
+
+
+#endif  /* SQLITE_THREADSAFE && !SQLITE_OMIT_SHARED_CACHE */