Rename 'digikam' folder to 'src'

Signed-off-by: Michele Calgaro <[email protected]>

1 files changed, 1488 insertions, 0 deletions

diff --git a/src/libs/sqlite2/btree_rb.c b/src/libs/sqlite2/btree_rb.c
new file mode 100644
index 00000000..18e49b81
--- /dev/null
+++ b/src/libs/sqlite2/btree_rb.c
@@ -0,0 +1,1488 @@
+/*
+** 2003 Feb 4
+**
+** 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: btree_rb.c 875429 2008-10-24 12:20:41Z cgilles $
+**
+** This file implements an in-core database using Red-Black balanced
+** binary trees.
+** 
+** It was contributed to SQLite by anonymous on 2003-Feb-04 23:24:49 UTC.
+*/
+#include "btree.h"
+#include "sqliteInt.h"
+#include <assert.h>
+
+/*
+** Omit this whole file if the SQLITE_OMIT_INMEMORYDB macro is
+** defined.  This allows a lot of code to be omitted for installations
+** that do not need it.
+*/
+#ifndef SQLITE_OMIT_INMEMORYDB
+
+
+typedef struct BtRbTree BtRbTree;
+typedef struct BtRbNode BtRbNode;
+typedef struct BtRollbackOp BtRollbackOp;
+typedef struct Rbtree Rbtree;
+typedef struct RbtCursor RbtCursor;
+
+/* Forward declarations */
+static BtOps sqliteRbtreeOps;
+static BtCursorOps sqliteRbtreeCursorOps;
+
+/*
+ * During each transaction (or checkpoint), a linked-list of
+ * "rollback-operations" is accumulated. If the transaction is rolled back,
+ * then the list of operations must be executed (to restore the database to
+ * it's state before the transaction started). If the transaction is to be
+ * committed, just delete the list.
+ *
+ * Each operation is represented as follows, depending on the value of eOp:
+ *
+ * ROLLBACK_INSERT  ->  Need to insert (pKey, pData) into table iTab.
+ * ROLLBACK_DELETE  ->  Need to delete the record (pKey) into table iTab.
+ * ROLLBACK_CREATE  ->  Need to create table iTab.
+ * ROLLBACK_DROP    ->  Need to drop table iTab.
+ */
+struct BtRollbackOp {
+  u8 eOp;
+  int iTab;
+  int nKey; 
+  void *pKey;
+  int nData;
+  void *pData;
+  BtRollbackOp *pNext;
+};
+
+/*
+** Legal values for BtRollbackOp.eOp:
+*/
+#define ROLLBACK_INSERT 1 /* Insert a record */
+#define ROLLBACK_DELETE 2 /* Delete a record */
+#define ROLLBACK_CREATE 3 /* Create a table */
+#define ROLLBACK_DROP   4 /* Drop a table */
+
+struct Rbtree {
+  BtOps *pOps;    /* Function table */
+  int aMetaData[SQLITE_N_BTREE_META];
+
+  int next_idx;   /* next available table index */
+  Hash tblHash;   /* All created tables, by index */
+  u8 isAnonymous; /* True if this Rbtree is to be deleted when closed */
+  u8 eTransState; /* State of this Rbtree wrt transactions */
+
+  BtRollbackOp *pTransRollback; 
+  BtRollbackOp *pCheckRollback;
+  BtRollbackOp *pCheckRollbackTail;
+};
+
+/*
+** Legal values for Rbtree.eTransState.
+*/
+#define TRANS_NONE           0  /* No transaction is in progress */
+#define TRANS_INTRANSACTION  1  /* A transaction is in progress */
+#define TRANS_INCHECKPOINT   2  /* A checkpoint is in progress  */
+#define TRANS_ROLLBACK       3  /* We are currently rolling back a checkpoint or
+                                 * transaction. */
+
+struct RbtCursor {
+  BtCursorOps *pOps;        /* Function table */
+  Rbtree    *pRbtree;
+  BtRbTree *pTree;
+  int       iTree;          /* Index of pTree in pRbtree */
+  BtRbNode *pNode;
+  RbtCursor *pShared;       /* List of all cursors on the same Rbtree */
+  u8 eSkip;                 /* Determines if next step operation is a no-op */
+  u8 wrFlag;                /* True if this cursor is open for writing */
+};
+
+/*
+** Legal values for RbtCursor.eSkip.
+*/
+#define SKIP_NONE     0   /* Always step the cursor */
+#define SKIP_NEXT     1   /* The next sqliteRbtreeNext() is a no-op */
+#define SKIP_PREV     2   /* The next sqliteRbtreePrevious() is a no-op */
+#define SKIP_INVALID  3   /* Calls to Next() and Previous() are invalid */
+
+struct BtRbTree {
+  RbtCursor *pCursors;     /* All cursors pointing to this tree */
+  BtRbNode *pHead;         /* Head of the tree, or NULL */
+};
+
+struct BtRbNode {
+  int nKey;
+  void *pKey;
+  int nData;
+  void *pData;
+  u8 isBlack;        /* true for a black node, 0 for a red node */
+  BtRbNode *pParent; /* Nodes parent node, NULL for the tree head */
+  BtRbNode *pLeft;   /* Nodes left child, or NULL */
+  BtRbNode *pRight;  /* Nodes right child, or NULL */
+
+  int nBlackHeight;  /* Only used during the red-black integrity check */
+};
+
+/* Forward declarations */
+static int memRbtreeMoveto(
+  RbtCursor* pCur,
+  const void *pKey,
+  int nKey,
+  int *pRes
+);
+static int memRbtreeClearTable(Rbtree* tree, int n);
+static int memRbtreeNext(RbtCursor* pCur, int *pRes);
+static int memRbtreeLast(RbtCursor* pCur, int *pRes);
+static int memRbtreePrevious(RbtCursor* pCur, int *pRes);
+
+
+/*
+** This routine checks all cursors that point to the same table
+** as pCur points to.  If any of those cursors were opened with
+** wrFlag==0 then this routine returns SQLITE_LOCKED.  If all
+** cursors point to the same table were opened with wrFlag==1
+** then this routine returns SQLITE_OK.
+**
+** In addition to checking for read-locks (where a read-lock 
+** means a cursor opened with wrFlag==0) this routine also NULLs
+** out the pNode field of all other cursors.
+** This is necessary because an insert 
+** or delete might change erase the node out from under
+** another cursor.
+*/
+static int checkReadLocks(RbtCursor *pCur){
+  RbtCursor *p;
+  assert( pCur->wrFlag );
+  for(p=pCur->pTree->pCursors; p; p=p->pShared){
+    if( p!=pCur ){
+      if( p->wrFlag==0 ) return SQLITE_LOCKED;
+      p->pNode = 0;
+    }
+  }
+  return SQLITE_OK;
+}
+
+/*
+ * The key-compare function for the red-black trees. Returns as follows:
+ *
+ * (key1 < key2)             -1
+ * (key1 == key2)             0 
+ * (key1 > key2)              1
+ *
+ * Keys are compared using memcmp(). If one key is an exact prefix of the
+ * other, then the shorter key is less than the longer key.
+ */
+static int key_compare(void const*pKey1, int nKey1, void const*pKey2, int nKey2)
+{
+  int mcmp = memcmp(pKey1, pKey2, (nKey1 <= nKey2)?nKey1:nKey2);
+  if( mcmp == 0){
+    if( nKey1 == nKey2 ) return 0;
+    return ((nKey1 < nKey2)?-1:1);
+  }
+  return ((mcmp>0)?1:-1);
+}
+
+/*
+ * Perform the LEFT-rotate transformation on node X of tree pTree. This
+ * transform is part of the red-black balancing code.
+ *
+ *        |                   |
+ *        X                   Y
+ *       / \                 / \
+ *      a   Y               X   c
+ *         / \             / \
+ *        b   c           a   b
+ *
+ *      BEFORE              AFTER
+ */
+static void leftRotate(BtRbTree *pTree, BtRbNode *pX)
+{
+  BtRbNode *pY;
+  BtRbNode *pb;
+  pY = pX->pRight;
+  pb = pY->pLeft;
+
+  pY->pParent = pX->pParent;
+  if( pX->pParent ){
+    if( pX->pParent->pLeft == pX ) pX->pParent->pLeft = pY;
+    else pX->pParent->pRight = pY;
+  }
+  pY->pLeft = pX;
+  pX->pParent = pY;
+  pX->pRight = pb;
+  if( pb ) pb->pParent = pX;
+  if( pTree->pHead == pX ) pTree->pHead = pY;
+}
+
+/*
+ * Perform the RIGHT-rotate transformation on node X of tree pTree. This
+ * transform is part of the red-black balancing code.
+ *
+ *        |                   |
+ *        X                   Y
+ *       / \                 / \
+ *      Y   c               a   X
+ *     / \                     / \
+ *    a   b                   b   c
+ *
+ *      BEFORE              AFTER
+ */
+static void rightRotate(BtRbTree *pTree, BtRbNode *pX)
+{
+  BtRbNode *pY;
+  BtRbNode *pb;
+  pY = pX->pLeft;
+  pb = pY->pRight;
+
+  pY->pParent = pX->pParent;
+  if( pX->pParent ){
+    if( pX->pParent->pLeft == pX ) pX->pParent->pLeft = pY;
+    else pX->pParent->pRight = pY;
+  }
+  pY->pRight = pX;
+  pX->pParent = pY;
+  pX->pLeft = pb;
+  if( pb ) pb->pParent = pX;
+  if( pTree->pHead == pX ) pTree->pHead = pY;
+}
+
+/*
+ * A string-manipulation helper function for check_redblack_tree(). If (orig ==
+ * NULL) a copy of val is returned. If (orig != NULL) then a copy of the *
+ * concatenation of orig and val is returned. The original orig is deleted
+ * (using sqliteFree()).
+ */
+static char *append_val(char * orig, char const * val){
+  char *z;
+  if( !orig ){
+    z = sqliteStrDup( val );
+  } else{
+    z = 0;
+    sqliteSetString(&z, orig, val, (char*)0);
+    sqliteFree( orig );
+  }
+  return z;
+}
+
+/*
+ * Append a string representation of the entire node to orig and return it.
+ * This is used to produce debugging information if check_redblack_tree() finds
+ * a problem with a red-black binary tree.
+ */
+static char *append_node(char * orig, BtRbNode *pNode, int indent)
+{
+  char buf[128];
+  int i;
+
+  for( i=0; i<indent; i++ ){
+      orig = append_val(orig, " ");
+  }
+
+  sprintf(buf, "%p", pNode);
+  orig = append_val(orig, buf);
+
+  if( pNode ){
+    indent += 3;
+    if( pNode->isBlack ){
+      orig = append_val(orig, " B \n");
+    }else{
+      orig = append_val(orig, " R \n");
+    }
+    orig = append_node( orig, pNode->pLeft, indent );
+    orig = append_node( orig, pNode->pRight, indent );
+  }else{
+    orig = append_val(orig, "\n");
+  }
+  return orig;
+}
+
+/*
+ * Print a representation of a node to stdout. This function is only included
+ * so you can call it from within a debugger if things get really bad.  It
+ * is not called from anyplace in the code.
+ */
+static void print_node(BtRbNode *pNode)
+{
+    char * str = append_node(0, pNode, 0);
+    printf("%s", str);
+
+    /* Suppress a warning message about print_node() being unused */
+    (void)print_node;
+}
+
+/* 
+ * Check the following properties of the red-black tree:
+ * (1) - If a node is red, both of it's children are black
+ * (2) - Each path from a given node to a leaf (NULL) node passes thru the
+ *       same number of black nodes 
+ *
+ * If there is a problem, append a description (using append_val() ) to *msg.
+ */
+static void check_redblack_tree(BtRbTree * tree, char ** msg)
+{
+  BtRbNode *pNode;
+
+  /* 0 -> came from parent 
+   * 1 -> came from left
+   * 2 -> came from right */
+  int prev_step = 0;
+
+  pNode = tree->pHead;
+  while( pNode ){
+    switch( prev_step ){
+      case 0:
+        if( pNode->pLeft ){
+          pNode = pNode->pLeft;
+        }else{ 
+          prev_step = 1;
+        }
+        break;
+      case 1:
+        if( pNode->pRight ){
+          pNode = pNode->pRight;
+          prev_step = 0;
+        }else{
+          prev_step = 2;
+        }
+        break;
+      case 2:
+        /* Check red-black property (1) */
+        if( !pNode->isBlack &&
+            ( (pNode->pLeft && !pNode->pLeft->isBlack) ||
+              (pNode->pRight && !pNode->pRight->isBlack) )
+          ){
+          char buf[128];
+          sprintf(buf, "Red node with red child at %p\n", pNode);
+          *msg = append_val(*msg, buf);
+          *msg = append_node(*msg, tree->pHead, 0);
+          *msg = append_val(*msg, "\n");
+        }
+
+        /* Check red-black property (2) */
+        { 
+          int leftHeight = 0;
+          int rightHeight = 0;
+          if( pNode->pLeft ){
+            leftHeight += pNode->pLeft->nBlackHeight;
+            leftHeight += (pNode->pLeft->isBlack?1:0);
+          }
+          if( pNode->pRight ){
+            rightHeight += pNode->pRight->nBlackHeight;
+            rightHeight += (pNode->pRight->isBlack?1:0);
+          }
+          if( leftHeight != rightHeight ){
+            char buf[128];
+            sprintf(buf, "Different black-heights at %p\n", pNode);
+            *msg = append_val(*msg, buf);
+            *msg = append_node(*msg, tree->pHead, 0);
+            *msg = append_val(*msg, "\n");
+          }
+          pNode->nBlackHeight = leftHeight;
+        }
+
+        if( pNode->pParent ){
+          if( pNode == pNode->pParent->pLeft ) prev_step = 1;
+          else prev_step = 2;
+        }
+        pNode = pNode->pParent;
+        break;
+      default: assert(0);
+    }
+  }
+} 
+
+/*
+ * Node pX has just been inserted into pTree (by code in sqliteRbtreeInsert()).
+ * It is possible that pX is a red node with a red parent, which is a violation
+ * of the red-black tree properties. This function performs rotations and 
+ * color changes to rebalance the tree
+ */
+static void do_insert_balancing(BtRbTree *pTree, BtRbNode *pX)
+{
+  /* In the first iteration of this loop, pX points to the red node just
+   * inserted in the tree. If the parent of pX exists (pX is not the root
+   * node) and is red, then the properties of the red-black tree are
+   * violated.
+   *
+   * At the start of any subsequent iterations, pX points to a red node
+   * with a red parent. In all other respects the tree is a legal red-black
+   * binary tree. */
+  while( pX != pTree->pHead && !pX->pParent->isBlack ){
+    BtRbNode *pUncle;
+    BtRbNode *pGrandparent;
+
+    /* Grandparent of pX must exist and must be black. */
+    pGrandparent = pX->pParent->pParent;
+    assert( pGrandparent );
+    assert( pGrandparent->isBlack );
+
+    /* Uncle of pX may or may not exist. */
+    if( pX->pParent == pGrandparent->pLeft ) 
+      pUncle = pGrandparent->pRight;
+    else 
+      pUncle = pGrandparent->pLeft;
+
+    /* If the uncle of pX exists and is red, we do the following:
+     *       |                 |
+     *      G(b)              G(r)
+     *      /  \              /  \        
+     *   U(r)   P(r)       U(b)  P(b)
+     *            \                \
+     *           X(r)              X(r)
+     *
+     *     BEFORE             AFTER
+     * pX is then set to G. If the parent of G is red, then the while loop
+     * will run again.  */
+    if( pUncle && !pUncle->isBlack ){
+      pGrandparent->isBlack = 0;
+      pUncle->isBlack = 1;
+      pX->pParent->isBlack = 1;
+      pX = pGrandparent;
+    }else{
+
+      if( pX->pParent == pGrandparent->pLeft ){
+        if( pX == pX->pParent->pRight ){
+          /* If pX is a right-child, do the following transform, essentially
+           * to change pX into a left-child: 
+           *       |                  | 
+           *      G(b)               G(b)
+           *      /  \               /  \        
+           *   P(r)   U(b)        X(r)  U(b)
+           *      \                /
+           *     X(r)            P(r) <-- new X
+           *
+           *     BEFORE             AFTER
+           */
+          pX = pX->pParent;
+          leftRotate(pTree, pX);
+        }
+
+        /* Do the following transform, which balances the tree :) 
+         *       |                  | 
+         *      G(b)               P(b)
+         *      /  \               /  \        
+         *   P(r)   U(b)        X(r)  G(r)
+         *    /                         \
+         *  X(r)                        U(b)
+         *
+         *     BEFORE             AFTER
+         */
+        assert( pGrandparent == pX->pParent->pParent );
+        pGrandparent->isBlack = 0;
+        pX->pParent->isBlack = 1;
+        rightRotate( pTree, pGrandparent );
+
+      }else{
+        /* This code is symetric to the illustrated case above. */
+        if( pX == pX->pParent->pLeft ){
+          pX = pX->pParent;
+          rightRotate(pTree, pX);
+        }
+        assert( pGrandparent == pX->pParent->pParent );
+        pGrandparent->isBlack = 0;
+        pX->pParent->isBlack = 1;
+        leftRotate( pTree, pGrandparent );
+      }
+    }
+  }
+  pTree->pHead->isBlack = 1;
+}
+
+/*
+ * A child of pParent, which in turn had child pX, has just been removed from 
+ * pTree (the figure below depicts the operation, Z is being removed). pParent
+ * or pX, or both may be NULL.  
+ *                |           |
+ *                P           P
+ *               / \         / \
+ *              Z           X
+ *             / \
+ *            X  nil
+ *
+ * This function is only called if Z was black. In this case the red-black tree
+ * properties have been violated, and pX has an "extra black". This function 
+ * performs rotations and color-changes to re-balance the tree.
+ */
+static 
+void do_delete_balancing(BtRbTree *pTree, BtRbNode *pX, BtRbNode *pParent)
+{
+  BtRbNode *pSib; 
+
+  /* TODO: Comment this code! */
+  while( pX != pTree->pHead && (!pX || pX->isBlack) ){
+    if( pX == pParent->pLeft ){
+      pSib = pParent->pRight;
+      if( pSib && !(pSib->isBlack) ){
+        pSib->isBlack = 1;
+        pParent->isBlack = 0;
+        leftRotate(pTree, pParent);
+        pSib = pParent->pRight;
+      }
+      if( !pSib ){
+        pX = pParent;
+      }else if( 
+          (!pSib->pLeft  || pSib->pLeft->isBlack) &&
+          (!pSib->pRight || pSib->pRight->isBlack) ) {
+        pSib->isBlack = 0;
+        pX = pParent;
+      }else{
+        if( (!pSib->pRight || pSib->pRight->isBlack) ){
+          if( pSib->pLeft ) pSib->pLeft->isBlack = 1;
+          pSib->isBlack = 0;
+          rightRotate( pTree, pSib );
+          pSib = pParent->pRight;
+        }
+        pSib->isBlack = pParent->isBlack;
+        pParent->isBlack = 1;
+        if( pSib->pRight ) pSib->pRight->isBlack = 1;
+        leftRotate(pTree, pParent);
+        pX = pTree->pHead;
+      }
+    }else{
+      pSib = pParent->pLeft;
+      if( pSib && !(pSib->isBlack) ){
+        pSib->isBlack = 1;
+        pParent->isBlack = 0;
+        rightRotate(pTree, pParent);
+        pSib = pParent->pLeft;
+      }
+      if( !pSib ){
+        pX = pParent;
+      }else if( 
+          (!pSib->pLeft  || pSib->pLeft->isBlack) &&
+          (!pSib->pRight || pSib->pRight->isBlack) ){
+        pSib->isBlack = 0;
+        pX = pParent;
+      }else{
+        if( (!pSib->pLeft || pSib->pLeft->isBlack) ){
+          if( pSib->pRight ) pSib->pRight->isBlack = 1;
+          pSib->isBlack = 0;
+          leftRotate( pTree, pSib );
+          pSib = pParent->pLeft;
+        }
+        pSib->isBlack = pParent->isBlack;
+        pParent->isBlack = 1;
+        if( pSib->pLeft ) pSib->pLeft->isBlack = 1;
+        rightRotate(pTree, pParent);
+        pX = pTree->pHead;
+      }
+    }
+    pParent = pX->pParent;
+  }
+  if( pX ) pX->isBlack = 1;
+}
+
+/*
+ * Create table n in tree pRbtree. Table n must not exist.
+ */
+static void btreeCreateTable(Rbtree* pRbtree, int n)
+{
+  BtRbTree *pNewTbl = sqliteMalloc(sizeof(BtRbTree));
+  sqliteHashInsert(&pRbtree->tblHash, 0, n, pNewTbl);
+}
+
+/*
+ * Log a single "rollback-op" for the given Rbtree. See comments for struct
+ * BtRollbackOp.
+ */
+static void btreeLogRollbackOp(Rbtree* pRbtree, BtRollbackOp *pRollbackOp)
+{
+  assert( pRbtree->eTransState == TRANS_INCHECKPOINT ||
+      pRbtree->eTransState == TRANS_INTRANSACTION );
+  if( pRbtree->eTransState == TRANS_INTRANSACTION ){
+    pRollbackOp->pNext = pRbtree->pTransRollback;
+    pRbtree->pTransRollback = pRollbackOp;
+  }
+  if( pRbtree->eTransState == TRANS_INCHECKPOINT ){
+    if( !pRbtree->pCheckRollback ){
+      pRbtree->pCheckRollbackTail = pRollbackOp;
+    }
+    pRollbackOp->pNext = pRbtree->pCheckRollback;
+    pRbtree->pCheckRollback = pRollbackOp;
+  }
+}
+
+int sqliteRbtreeOpen(
+  const char *zFilename,
+  int mode,
+  int nPg,
+  Btree **ppBtree
+){
+  Rbtree **ppRbtree = (Rbtree**)ppBtree;
+  *ppRbtree = (Rbtree *)sqliteMalloc(sizeof(Rbtree));
+  if( sqlite_malloc_failed ) goto open_no_mem;
+  sqliteHashInit(&(*ppRbtree)->tblHash, SQLITE_HASH_INT, 0);
+
+  /* Create a binary tree for the SQLITE_MASTER table at location 2 */
+  btreeCreateTable(*ppRbtree, 2);
+  if( sqlite_malloc_failed ) goto open_no_mem;
+  (*ppRbtree)->next_idx = 3;
+  (*ppRbtree)->pOps = &sqliteRbtreeOps;
+  /* Set file type to 4; this is so that "attach ':memory:' as ...."  does not
+  ** think that the database in uninitialised and refuse to attach
+  */
+  (*ppRbtree)->aMetaData[2] = 4;
+  
+  return SQLITE_OK;
+
+open_no_mem:
+  *ppBtree = 0;
+  return SQLITE_NOMEM;
+}
+
+/*
+ * Create a new table in the supplied Rbtree. Set *n to the new table number.
+ * Return SQLITE_OK if the operation is a success.
+ */
+static int memRbtreeCreateTable(Rbtree* tree, int* n)
+{
+  assert( tree->eTransState != TRANS_NONE );
+
+  *n = tree->next_idx++;
+  btreeCreateTable(tree, *n);
+  if( sqlite_malloc_failed ) return SQLITE_NOMEM;
+
+  /* Set up the rollback structure (if we are not doing this as part of a
+   * rollback) */
+  if( tree->eTransState != TRANS_ROLLBACK ){
+    BtRollbackOp *pRollbackOp = sqliteMalloc(sizeof(BtRollbackOp));
+    if( pRollbackOp==0 ) return SQLITE_NOMEM;
+    pRollbackOp->eOp = ROLLBACK_DROP;
+    pRollbackOp->iTab = *n;
+    btreeLogRollbackOp(tree, pRollbackOp);
+  }
+
+  return SQLITE_OK;
+}
+
+/*
+ * Delete table n from the supplied Rbtree. 
+ */
+static int memRbtreeDropTable(Rbtree* tree, int n)
+{
+  BtRbTree *pTree;
+  assert( tree->eTransState != TRANS_NONE );
+
+  memRbtreeClearTable(tree, n);
+  pTree = sqliteHashInsert(&tree->tblHash, 0, n, 0);
+  assert(pTree);
+  assert( pTree->pCursors==0 );
+  sqliteFree(pTree);
+
+  if( tree->eTransState != TRANS_ROLLBACK ){
+    BtRollbackOp *pRollbackOp = sqliteMalloc(sizeof(BtRollbackOp));
+    if( pRollbackOp==0 ) return SQLITE_NOMEM;
+    pRollbackOp->eOp = ROLLBACK_CREATE;
+    pRollbackOp->iTab = n;
+    btreeLogRollbackOp(tree, pRollbackOp);
+  }
+
+  return SQLITE_OK;
+}
+
+static int memRbtreeKeyCompare(RbtCursor* pCur, const void *pKey, int nKey,
+                                 int nIgnore, int *pRes)
+{
+  assert(pCur);
+
+  if( !pCur->pNode ) {
+    *pRes = -1;
+  } else {
+    if( (pCur->pNode->nKey - nIgnore) < 0 ){
+      *pRes = -1;
+    }else{
+      *pRes = key_compare(pCur->pNode->pKey, pCur->pNode->nKey-nIgnore, 
+          pKey, nKey);
+    }
+  }
+  return SQLITE_OK;
+}
+
+/*
+ * Get a new cursor for table iTable of the supplied Rbtree. The wrFlag
+ * parameter indicates that the cursor is open for writing.
+ *
+ * Note that RbtCursor.eSkip and RbtCursor.pNode both initialize to 0.
+ */
+static int memRbtreeCursor(
+  Rbtree* tree,
+  int iTable,
+  int wrFlag,
+  RbtCursor **ppCur
+){
+  RbtCursor *pCur;
+  assert(tree);
+  pCur = *ppCur = sqliteMalloc(sizeof(RbtCursor));
+  if( sqlite_malloc_failed ) return SQLITE_NOMEM;
+  pCur->pTree  = sqliteHashFind(&tree->tblHash, 0, iTable);
+  assert( pCur->pTree );
+  pCur->pRbtree = tree;
+  pCur->iTree  = iTable;
+  pCur->pOps = &sqliteRbtreeCursorOps;
+  pCur->wrFlag = wrFlag;
+  pCur->pShared = pCur->pTree->pCursors;
+  pCur->pTree->pCursors = pCur;
+
+  assert( (*ppCur)->pTree );
+  return SQLITE_OK;
+}
+
+/*
+ * Insert a new record into the Rbtree.  The key is given by (pKey,nKey)
+ * and the data is given by (pData,nData).  The cursor is used only to
+ * define what database the record should be inserted into.  The cursor
+ * is left pointing at the new record.
+ *
+ * If the key exists already in the tree, just replace the data. 
+ */
+static int memRbtreeInsert(
+  RbtCursor* pCur,
+  const void *pKey,
+  int nKey,
+  const void *pDataInput,
+  int nData
+){
+  void * pData;
+  int match;
+
+  /* It is illegal to call sqliteRbtreeInsert() if we are
+  ** not in a transaction */
+  assert( pCur->pRbtree->eTransState != TRANS_NONE );
+
+  /* Make sure some other cursor isn't trying to read this same table */
+  if( checkReadLocks(pCur) ){
+    return SQLITE_LOCKED; /* The table pCur points to has a read lock */
+  }
+
+  /* Take a copy of the input data now, in case we need it for the 
+   * replace case */
+  pData = sqliteMallocRaw(nData);
+  if( sqlite_malloc_failed ) return SQLITE_NOMEM;
+  memcpy(pData, pDataInput, nData);
+
+  /* Move the cursor to a node near the key to be inserted. If the key already
+   * exists in the table, then (match == 0). In this case we can just replace
+   * the data associated with the entry, we don't need to manipulate the tree.
+   * 
+   * If there is no exact match, then the cursor points at what would be either
+   * the predecessor (match == -1) or successor (match == 1) of the
+   * searched-for key, were it to be inserted. The new node becomes a child of
+   * this node.
+   * 
+   * The new node is initially red.
+   */
+  memRbtreeMoveto( pCur, pKey, nKey, &match);
+  if( match ){
+    BtRbNode *pNode = sqliteMalloc(sizeof(BtRbNode));
+    if( pNode==0 ) return SQLITE_NOMEM;
+    pNode->nKey = nKey;
+    pNode->pKey = sqliteMallocRaw(nKey);
+    if( sqlite_malloc_failed ) return SQLITE_NOMEM;
+    memcpy(pNode->pKey, pKey, nKey);
+    pNode->nData = nData;
+    pNode->pData = pData; 
+    if( pCur->pNode ){
+      switch( match ){
+        case -1:
+          assert( !pCur->pNode->pRight );
+          pNode->pParent = pCur->pNode;
+          pCur->pNode->pRight = pNode;
+          break;
+        case 1:
+          assert( !pCur->pNode->pLeft );
+          pNode->pParent = pCur->pNode;
+          pCur->pNode->pLeft = pNode;
+          break;
+        default:
+          assert(0);
+      }
+    }else{
+      pCur->pTree->pHead = pNode;
+    }
+
+    /* Point the cursor at the node just inserted, as per SQLite requirements */
+    pCur->pNode = pNode;
+
+    /* A new node has just been inserted, so run the balancing code */
+    do_insert_balancing(pCur->pTree, pNode);
+
+    /* Set up a rollback-op in case we have to roll this operation back */
+    if( pCur->pRbtree->eTransState != TRANS_ROLLBACK ){
+      BtRollbackOp *pOp = sqliteMalloc( sizeof(BtRollbackOp) );
+      if( pOp==0 ) return SQLITE_NOMEM;
+      pOp->eOp = ROLLBACK_DELETE;
+      pOp->iTab = pCur->iTree;
+      pOp->nKey = pNode->nKey;
+      pOp->pKey = sqliteMallocRaw( pOp->nKey );
+      if( sqlite_malloc_failed ) return SQLITE_NOMEM;
+      memcpy( pOp->pKey, pNode->pKey, pOp->nKey );
+      btreeLogRollbackOp(pCur->pRbtree, pOp);
+    }
+
+  }else{ 
+    /* No need to insert a new node in the tree, as the key already exists.
+     * Just clobber the current nodes data. */
+
+    /* Set up a rollback-op in case we have to roll this operation back */
+    if( pCur->pRbtree->eTransState != TRANS_ROLLBACK ){
+      BtRollbackOp *pOp = sqliteMalloc( sizeof(BtRollbackOp) );
+      if( pOp==0 ) return SQLITE_NOMEM;
+      pOp->iTab = pCur->iTree;
+      pOp->nKey = pCur->pNode->nKey;
+      pOp->pKey = sqliteMallocRaw( pOp->nKey );
+      if( sqlite_malloc_failed ) return SQLITE_NOMEM;
+      memcpy( pOp->pKey, pCur->pNode->pKey, pOp->nKey );
+      pOp->nData = pCur->pNode->nData;
+      pOp->pData = pCur->pNode->pData;
+      pOp->eOp = ROLLBACK_INSERT;
+      btreeLogRollbackOp(pCur->pRbtree, pOp);
+    }else{
+      sqliteFree( pCur->pNode->pData );
+    }
+
+    /* Actually clobber the nodes data */
+    pCur->pNode->pData = pData;
+    pCur->pNode->nData = nData;
+  }
+
+  return SQLITE_OK;
+}
+
+/* Move the cursor so that it points to an entry near pKey.
+** Return a success code.
+**
+**     *pRes<0      The cursor is left pointing at an entry that
+**                  is smaller than pKey or if the table is empty
+**                  and the cursor is therefore left point to nothing.
+**
+**     *pRes==0     The cursor is left pointing at an entry that
+**                  exactly matches pKey.
+**
+**     *pRes>0      The cursor is left pointing at an entry that
+**                  is larger than pKey.
+*/
+static int memRbtreeMoveto(
+  RbtCursor* pCur,
+  const void *pKey,
+  int nKey,
+  int *pRes
+){
+  BtRbNode *pTmp = 0;
+
+  pCur->pNode = pCur->pTree->pHead;
+  *pRes = -1;
+  while( pCur->pNode && *pRes ) {
+    *pRes = key_compare(pCur->pNode->pKey, pCur->pNode->nKey, pKey, nKey);
+    pTmp = pCur->pNode;
+    switch( *pRes ){
+      case 1:    /* cursor > key */
+        pCur->pNode = pCur->pNode->pLeft;
+        break;
+      case -1:   /* cursor < key */
+        pCur->pNode = pCur->pNode->pRight;
+        break;
+    }
+  } 
+
+  /* If (pCur->pNode == NULL), then we have failed to find a match. Set
+   * pCur->pNode to pTmp, which is either NULL (if the tree is empty) or the
+   * last node traversed in the search. In either case the relation ship
+   * between pTmp and the searched for key is already stored in *pRes. pTmp is
+   * either the successor or predecessor of the key we tried to move to. */
+  if( !pCur->pNode ) pCur->pNode = pTmp;
+  pCur->eSkip = SKIP_NONE;
+
+  return SQLITE_OK;
+}
+
+
+/*
+** Delete the entry that the cursor is pointing to.
+**
+** The cursor is left pointing at either the next or the previous
+** entry.  If the cursor is left pointing to the next entry, then 
+** the pCur->eSkip flag is set to SKIP_NEXT which forces the next call to 
+** sqliteRbtreeNext() to be a no-op.  That way, you can always call
+** sqliteRbtreeNext() after a delete and the cursor will be left
+** pointing to the first entry after the deleted entry.  Similarly,
+** pCur->eSkip is set to SKIP_PREV is the cursor is left pointing to
+** the entry prior to the deleted entry so that a subsequent call to
+** sqliteRbtreePrevious() will always leave the cursor pointing at the
+** entry immediately before the one that was deleted.
+*/
+static int memRbtreeDelete(RbtCursor* pCur)
+{
+  BtRbNode *pZ;      /* The one being deleted */
+  BtRbNode *pChild;  /* The child of the spliced out node */
+
+  /* It is illegal to call sqliteRbtreeDelete() if we are
+  ** not in a transaction */
+  assert( pCur->pRbtree->eTransState != TRANS_NONE );
+
+  /* Make sure some other cursor isn't trying to read this same table */
+  if( checkReadLocks(pCur) ){
+    return SQLITE_LOCKED; /* The table pCur points to has a read lock */
+  }
+
+  pZ = pCur->pNode;
+  if( !pZ ){
+    return SQLITE_OK;
+  }
+
+  /* If we are not currently doing a rollback, set up a rollback op for this 
+   * deletion */
+  if( pCur->pRbtree->eTransState != TRANS_ROLLBACK ){
+    BtRollbackOp *pOp = sqliteMalloc( sizeof(BtRollbackOp) );
+    if( pOp==0 ) return SQLITE_NOMEM;
+    pOp->iTab = pCur->iTree;
+    pOp->nKey = pZ->nKey;
+    pOp->pKey = pZ->pKey;
+    pOp->nData = pZ->nData;
+    pOp->pData = pZ->pData;
+    pOp->eOp = ROLLBACK_INSERT;
+    btreeLogRollbackOp(pCur->pRbtree, pOp);
+  }
+
+  /* First do a standard binary-tree delete (node pZ is to be deleted). How
+   * to do this depends on how many children pZ has:
+   *
+   * If pZ has no children or one child, then splice out pZ.  If pZ has two
+   * children, splice out the successor of pZ and replace the key and data of
+   * pZ with the key and data of the spliced out successor.  */
+  if( pZ->pLeft && pZ->pRight ){
+    BtRbNode *pTmp;
+    int dummy;
+    pCur->eSkip = SKIP_NONE;
+    memRbtreeNext(pCur, &dummy);
+    assert( dummy == 0 );
+    if( pCur->pRbtree->eTransState == TRANS_ROLLBACK ){
+      sqliteFree(pZ->pKey);
+      sqliteFree(pZ->pData);
+    }
+    pZ->pData = pCur->pNode->pData;
+    pZ->nData = pCur->pNode->nData;
+    pZ->pKey = pCur->pNode->pKey;
+    pZ->nKey = pCur->pNode->nKey;
+    pTmp = pZ;
+    pZ = pCur->pNode;
+    pCur->pNode = pTmp;
+    pCur->eSkip = SKIP_NEXT;
+  }else{
+    int res;
+    pCur->eSkip = SKIP_NONE;
+    memRbtreeNext(pCur, &res);
+    pCur->eSkip = SKIP_NEXT;
+    if( res ){
+      memRbtreeLast(pCur, &res);
+      memRbtreePrevious(pCur, &res);
+      pCur->eSkip = SKIP_PREV;
+    }
+    if( pCur->pRbtree->eTransState == TRANS_ROLLBACK ){
+        sqliteFree(pZ->pKey);
+        sqliteFree(pZ->pData);
+    }
+  }
+
+  /* pZ now points at the node to be spliced out. This block does the 
+   * splicing. */
+  {
+    BtRbNode **ppParentSlot = 0;
+    assert( !pZ->pLeft || !pZ->pRight ); /* pZ has at most one child */
+    pChild = ((pZ->pLeft)?pZ->pLeft:pZ->pRight);
+    if( pZ->pParent ){
+      assert( pZ == pZ->pParent->pLeft || pZ == pZ->pParent->pRight );
+      ppParentSlot = ((pZ == pZ->pParent->pLeft)
+          ?&pZ->pParent->pLeft:&pZ->pParent->pRight);
+      *ppParentSlot = pChild;
+    }else{
+      pCur->pTree->pHead = pChild;
+    }
+    if( pChild ) pChild->pParent = pZ->pParent;
+  }
+
+  /* pZ now points at the spliced out node. pChild is the only child of pZ, or
+   * NULL if pZ has no children. If pZ is black, and not the tree root, then we
+   * will have violated the "same number of black nodes in every path to a
+   * leaf" property of the red-black tree. The code in do_delete_balancing()
+   * repairs this. */
+  if( pZ->isBlack ){ 
+    do_delete_balancing(pCur->pTree, pChild, pZ->pParent);
+  }
+
+  sqliteFree(pZ);
+  return SQLITE_OK;
+}
+
+/*
+ * Empty table n of the Rbtree.
+ */
+static int memRbtreeClearTable(Rbtree* tree, int n)
+{
+  BtRbTree *pTree;
+  BtRbNode *pNode;
+
+  pTree = sqliteHashFind(&tree->tblHash, 0, n);
+  assert(pTree);
+
+  pNode = pTree->pHead;
+  while( pNode ){
+    if( pNode->pLeft ){
+      pNode = pNode->pLeft;
+    }
+    else if( pNode->pRight ){
+      pNode = pNode->pRight;
+    }
+    else {
+      BtRbNode *pTmp = pNode->pParent;
+      if( tree->eTransState == TRANS_ROLLBACK ){
+        sqliteFree( pNode->pKey );
+        sqliteFree( pNode->pData );
+      }else{
+        BtRollbackOp *pRollbackOp = sqliteMallocRaw(sizeof(BtRollbackOp));
+        if( pRollbackOp==0 ) return SQLITE_NOMEM;
+        pRollbackOp->eOp = ROLLBACK_INSERT;
+        pRollbackOp->iTab = n;
+        pRollbackOp->nKey = pNode->nKey;
+        pRollbackOp->pKey = pNode->pKey;
+        pRollbackOp->nData = pNode->nData;
+        pRollbackOp->pData = pNode->pData;
+        btreeLogRollbackOp(tree, pRollbackOp);
+      }
+      sqliteFree( pNode );
+      if( pTmp ){
+        if( pTmp->pLeft == pNode ) pTmp->pLeft = 0;
+        else if( pTmp->pRight == pNode ) pTmp->pRight = 0;
+      }
+      pNode = pTmp;
+    }
+  }
+
+  pTree->pHead = 0;
+  return SQLITE_OK;
+}
+
+static int memRbtreeFirst(RbtCursor* pCur, int *pRes)
+{
+  if( pCur->pTree->pHead ){
+    pCur->pNode = pCur->pTree->pHead;
+    while( pCur->pNode->pLeft ){
+      pCur->pNode = pCur->pNode->pLeft;
+    }
+  }
+  if( pCur->pNode ){
+    *pRes = 0;
+  }else{
+    *pRes = 1;
+  }
+  pCur->eSkip = SKIP_NONE;
+  return SQLITE_OK;
+}
+
+static int memRbtreeLast(RbtCursor* pCur, int *pRes)
+{
+  if( pCur->pTree->pHead ){
+    pCur->pNode = pCur->pTree->pHead;
+    while( pCur->pNode->pRight ){
+      pCur->pNode = pCur->pNode->pRight;
+    }
+  }
+  if( pCur->pNode ){
+    *pRes = 0;
+  }else{
+    *pRes = 1;
+  }
+  pCur->eSkip = SKIP_NONE;
+  return SQLITE_OK;
+}
+
+/*
+** Advance the cursor to the next entry in the database.  If
+** successful then set *pRes=0.  If the cursor
+** was already pointing to the last entry in the database before
+** this routine was called, then set *pRes=1.
+*/
+static int memRbtreeNext(RbtCursor* pCur, int *pRes)
+{
+  if( pCur->pNode && pCur->eSkip != SKIP_NEXT ){
+    if( pCur->pNode->pRight ){
+      pCur->pNode = pCur->pNode->pRight;
+      while( pCur->pNode->pLeft )
+        pCur->pNode = pCur->pNode->pLeft;
+    }else{
+      BtRbNode * pX = pCur->pNode;
+      pCur->pNode = pX->pParent;
+      while( pCur->pNode && (pCur->pNode->pRight == pX) ){
+        pX = pCur->pNode;
+        pCur->pNode = pX->pParent;
+      }
+    }
+  }
+  pCur->eSkip = SKIP_NONE;
+
+  if( !pCur->pNode ){
+    *pRes = 1;
+  }else{
+    *pRes = 0;
+  }
+
+  return SQLITE_OK;
+}
+
+static int memRbtreePrevious(RbtCursor* pCur, int *pRes)
+{
+  if( pCur->pNode && pCur->eSkip != SKIP_PREV ){
+    if( pCur->pNode->pLeft ){
+      pCur->pNode = pCur->pNode->pLeft;
+      while( pCur->pNode->pRight )
+        pCur->pNode = pCur->pNode->pRight;
+    }else{
+      BtRbNode * pX = pCur->pNode;
+      pCur->pNode = pX->pParent;
+      while( pCur->pNode && (pCur->pNode->pLeft == pX) ){
+        pX = pCur->pNode;
+        pCur->pNode = pX->pParent;
+      }
+    }
+  }
+  pCur->eSkip = SKIP_NONE;
+
+  if( !pCur->pNode ){
+    *pRes = 1;
+  }else{
+    *pRes = 0;
+  }
+
+  return SQLITE_OK;
+}
+
+static int memRbtreeKeySize(RbtCursor* pCur, int *pSize)
+{
+  if( pCur->pNode ){
+    *pSize = pCur->pNode->nKey;
+  }else{
+    *pSize = 0;
+  }
+  return SQLITE_OK;
+}
+
+static int memRbtreeKey(RbtCursor* pCur, int offset, int amt, char *zBuf)
+{
+  if( !pCur->pNode ) return 0;
+  if( !pCur->pNode->pKey || ((amt + offset) <= pCur->pNode->nKey) ){
+    memcpy(zBuf, ((char*)pCur->pNode->pKey)+offset, amt);
+  }else{
+    memcpy(zBuf, ((char*)pCur->pNode->pKey)+offset, pCur->pNode->nKey-offset);
+    amt = pCur->pNode->nKey-offset;
+  }
+  return amt;
+}
+
+static int memRbtreeDataSize(RbtCursor* pCur, int *pSize)
+{
+  if( pCur->pNode ){
+    *pSize = pCur->pNode->nData;
+  }else{
+    *pSize = 0;
+  }
+  return SQLITE_OK;
+}
+
+static int memRbtreeData(RbtCursor *pCur, int offset, int amt, char *zBuf)
+{
+  if( !pCur->pNode ) return 0;
+  if( (amt + offset) <= pCur->pNode->nData ){
+    memcpy(zBuf, ((char*)pCur->pNode->pData)+offset, amt);
+  }else{
+    memcpy(zBuf, ((char*)pCur->pNode->pData)+offset ,pCur->pNode->nData-offset);
+    amt = pCur->pNode->nData-offset;
+  }
+  return amt;
+}
+
+static int memRbtreeCloseCursor(RbtCursor* pCur)
+{
+  if( pCur->pTree->pCursors==pCur ){
+    pCur->pTree->pCursors = pCur->pShared;
+  }else{
+    RbtCursor *p = pCur->pTree->pCursors;
+    while( p && p->pShared!=pCur ){ p = p->pShared; }
+    assert( p!=0 );
+    if( p ){
+      p->pShared = pCur->pShared;
+    }
+  }
+  sqliteFree(pCur);
+  return SQLITE_OK;
+}
+
+static int memRbtreeGetMeta(Rbtree* tree, int* aMeta)
+{
+  memcpy( aMeta, tree->aMetaData, sizeof(int) * SQLITE_N_BTREE_META );
+  return SQLITE_OK;
+}
+
+static int memRbtreeUpdateMeta(Rbtree* tree, int* aMeta)
+{
+  memcpy( tree->aMetaData, aMeta, sizeof(int) * SQLITE_N_BTREE_META );
+  return SQLITE_OK;
+}
+
+/*
+ * Check that each table in the Rbtree meets the requirements for a red-black
+ * binary tree. If an error is found, return an explanation of the problem in 
+ * memory obtained from sqliteMalloc(). Parameters aRoot and nRoot are ignored. 
+ */
+static char *memRbtreeIntegrityCheck(Rbtree* tree, int* aRoot, int nRoot)
+{
+  char * msg = 0;
+  HashElem *p;
+
+  for(p=sqliteHashFirst(&tree->tblHash); p; p=sqliteHashNext(p)){
+    BtRbTree *pTree = sqliteHashData(p);
+    check_redblack_tree(pTree, &msg);
+  }
+
+  return msg;
+}
+
+static int memRbtreeSetCacheSize(Rbtree* tree, int sz)
+{
+  return SQLITE_OK;
+}
+
+static int memRbtreeSetSafetyLevel(Rbtree *pBt, int level){
+  return SQLITE_OK;
+}
+
+static int memRbtreeBeginTrans(Rbtree* tree)
+{
+  if( tree->eTransState != TRANS_NONE ) 
+    return SQLITE_ERROR;
+
+  assert( tree->pTransRollback == 0 );
+  tree->eTransState = TRANS_INTRANSACTION;
+  return SQLITE_OK;
+}
+
+/*
+** Delete a linked list of BtRollbackOp structures.
+*/
+static void deleteRollbackList(BtRollbackOp *pOp){
+  while( pOp ){
+    BtRollbackOp *pTmp = pOp->pNext;
+    sqliteFree(pOp->pData);
+    sqliteFree(pOp->pKey);
+    sqliteFree(pOp);
+    pOp = pTmp;
+  }
+}
+
+static int memRbtreeCommit(Rbtree* tree){
+  /* Just delete pTransRollback and pCheckRollback */
+  deleteRollbackList(tree->pCheckRollback);
+  deleteRollbackList(tree->pTransRollback);
+  tree->pTransRollback = 0;
+  tree->pCheckRollback = 0;
+  tree->pCheckRollbackTail = 0;
+  tree->eTransState = TRANS_NONE;
+  return SQLITE_OK;
+}
+
+/*
+ * Close the supplied Rbtree. Delete everything associated with it.
+ */
+static int memRbtreeClose(Rbtree* tree)
+{
+  HashElem *p;
+  memRbtreeCommit(tree);
+  while( (p=sqliteHashFirst(&tree->tblHash))!=0 ){
+    tree->eTransState = TRANS_ROLLBACK;
+    memRbtreeDropTable(tree, sqliteHashKeysize(p));
+  }
+  sqliteHashClear(&tree->tblHash);
+  sqliteFree(tree);
+  return SQLITE_OK;
+}
+
+/*
+ * Execute and delete the supplied rollback-list on pRbtree.
+ */
+static void execute_rollback_list(Rbtree *pRbtree, BtRollbackOp *pList)
+{
+  BtRollbackOp *pTmp;
+  RbtCursor cur;
+  int res;
+
+  cur.pRbtree = pRbtree;
+  cur.wrFlag = 1;
+  while( pList ){
+    switch( pList->eOp ){
+      case ROLLBACK_INSERT:
+        cur.pTree  = sqliteHashFind( &pRbtree->tblHash, 0, pList->iTab );
+        assert(cur.pTree);
+        cur.iTree  = pList->iTab;
+        cur.eSkip  = SKIP_NONE;
+        memRbtreeInsert( &cur, pList->pKey,
+            pList->nKey, pList->pData, pList->nData );
+        break;
+      case ROLLBACK_DELETE:
+        cur.pTree  = sqliteHashFind( &pRbtree->tblHash, 0, pList->iTab );
+        assert(cur.pTree);
+        cur.iTree  = pList->iTab;
+        cur.eSkip  = SKIP_NONE;
+        memRbtreeMoveto(&cur, pList->pKey, pList->nKey, &res);
+        assert(res == 0);
+        memRbtreeDelete( &cur );
+        break;
+      case ROLLBACK_CREATE:
+        btreeCreateTable(pRbtree, pList->iTab);
+        break;
+      case ROLLBACK_DROP:
+        memRbtreeDropTable(pRbtree, pList->iTab);
+        break;
+      default:
+        assert(0);
+    }
+    sqliteFree(pList->pKey);
+    sqliteFree(pList->pData);
+    pTmp = pList->pNext;
+    sqliteFree(pList);
+    pList = pTmp;
+  }
+}
+
+static int memRbtreeRollback(Rbtree* tree)
+{
+  tree->eTransState = TRANS_ROLLBACK;
+  execute_rollback_list(tree, tree->pCheckRollback);
+  execute_rollback_list(tree, tree->pTransRollback);
+  tree->pTransRollback = 0;
+  tree->pCheckRollback = 0;
+  tree->pCheckRollbackTail = 0;
+  tree->eTransState = TRANS_NONE;
+  return SQLITE_OK;
+}
+
+static int memRbtreeBeginCkpt(Rbtree* tree)
+{
+  if( tree->eTransState != TRANS_INTRANSACTION ) 
+    return SQLITE_ERROR;
+
+  assert( tree->pCheckRollback == 0 );
+  assert( tree->pCheckRollbackTail == 0 );
+  tree->eTransState = TRANS_INCHECKPOINT;
+  return SQLITE_OK;
+}
+
+static int memRbtreeCommitCkpt(Rbtree* tree)
+{
+  if( tree->eTransState == TRANS_INCHECKPOINT ){ 
+    if( tree->pCheckRollback ){
+      tree->pCheckRollbackTail->pNext = tree->pTransRollback;
+      tree->pTransRollback = tree->pCheckRollback;
+      tree->pCheckRollback = 0;
+      tree->pCheckRollbackTail = 0;
+    }
+    tree->eTransState = TRANS_INTRANSACTION;
+  }
+  return SQLITE_OK;
+}
+
+static int memRbtreeRollbackCkpt(Rbtree* tree)
+{
+  if( tree->eTransState != TRANS_INCHECKPOINT ) return SQLITE_OK;
+  tree->eTransState = TRANS_ROLLBACK;
+  execute_rollback_list(tree, tree->pCheckRollback);
+  tree->pCheckRollback = 0;
+  tree->pCheckRollbackTail = 0;
+  tree->eTransState = TRANS_INTRANSACTION;
+  return SQLITE_OK;
+}
+
+#ifdef SQLITE_TEST
+static int memRbtreePageDump(Rbtree* tree, int pgno, int rec)
+{
+  assert(!"Cannot call sqliteRbtreePageDump");
+  return SQLITE_OK;
+}
+
+static int memRbtreeCursorDump(RbtCursor* pCur, int* aRes)
+{
+  assert(!"Cannot call sqliteRbtreeCursorDump");
+  return SQLITE_OK;
+}
+#endif
+
+static struct Pager *memRbtreePager(Rbtree* tree)
+{
+  return 0;
+}
+
+/*
+** Return the full pathname of the underlying database file.
+*/
+static const char *memRbtreeGetFilename(Rbtree *pBt){
+  return 0;  /* A NULL return indicates there is no underlying file */
+}
+
+/*
+** The copy file function is not implemented for the in-memory database
+*/
+static int memRbtreeCopyFile(Rbtree *pBt, Rbtree *pBt2){
+  return SQLITE_INTERNAL;  /* Not implemented */
+}
+
+static BtOps sqliteRbtreeOps = {
+    (int(*)(Btree*)) memRbtreeClose,
+    (int(*)(Btree*,int)) memRbtreeSetCacheSize,
+    (int(*)(Btree*,int)) memRbtreeSetSafetyLevel,
+    (int(*)(Btree*)) memRbtreeBeginTrans,
+    (int(*)(Btree*)) memRbtreeCommit,
+    (int(*)(Btree*)) memRbtreeRollback,
+    (int(*)(Btree*)) memRbtreeBeginCkpt,
+    (int(*)(Btree*)) memRbtreeCommitCkpt,
+    (int(*)(Btree*)) memRbtreeRollbackCkpt,
+    (int(*)(Btree*,int*)) memRbtreeCreateTable,
+    (int(*)(Btree*,int*)) memRbtreeCreateTable,
+    (int(*)(Btree*,int)) memRbtreeDropTable,
+    (int(*)(Btree*,int)) memRbtreeClearTable,
+    (int(*)(Btree*,int,int,BtCursor**)) memRbtreeCursor,
+    (int(*)(Btree*,int*)) memRbtreeGetMeta,
+    (int(*)(Btree*,int*)) memRbtreeUpdateMeta,
+    (char*(*)(Btree*,int*,int)) memRbtreeIntegrityCheck,
+    (const char*(*)(Btree*)) memRbtreeGetFilename,
+    (int(*)(Btree*,Btree*)) memRbtreeCopyFile,
+    (struct Pager*(*)(Btree*)) memRbtreePager,
+#ifdef SQLITE_TEST
+    (int(*)(Btree*,int,int)) memRbtreePageDump,
+#endif
+};
+
+static BtCursorOps sqliteRbtreeCursorOps = {
+    (int(*)(BtCursor*,const void*,int,int*)) memRbtreeMoveto,
+    (int(*)(BtCursor*)) memRbtreeDelete,
+    (int(*)(BtCursor*,const void*,int,const void*,int)) memRbtreeInsert,
+    (int(*)(BtCursor*,int*)) memRbtreeFirst,
+    (int(*)(BtCursor*,int*)) memRbtreeLast,
+    (int(*)(BtCursor*,int*)) memRbtreeNext,
+    (int(*)(BtCursor*,int*)) memRbtreePrevious,
+    (int(*)(BtCursor*,int*)) memRbtreeKeySize,
+    (int(*)(BtCursor*,int,int,char*)) memRbtreeKey,
+    (int(*)(BtCursor*,const void*,int,int,int*)) memRbtreeKeyCompare,
+    (int(*)(BtCursor*,int*)) memRbtreeDataSize,
+    (int(*)(BtCursor*,int,int,char*)) memRbtreeData,
+    (int(*)(BtCursor*)) memRbtreeCloseCursor,
+#ifdef SQLITE_TEST
+    (int(*)(BtCursor*,int*)) memRbtreeCursorDump,
+#endif
+
+};
+
+#endif /* SQLITE_OMIT_INMEMORYDB */