** 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,v 1.3 2003/04/16 01:28:16 drh Exp $
**
** 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"
................................................................................
*/
#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 Btree {
  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 Btree is to be deleted when closed */
  u8 eTransState; /* State of this Btree wrt transactions */

................................................................................
/*
** Legal values for Btree.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 BtCursor {
  BtCursorOps *pOps;	    /* Function table */
  Btree    *pBtree;
  BtRbTree *pTree;
  int       iTree;          /* Index of pTree in pBtree */
  BtRbNode *pNode;
  u8 eSkip;                 /* Determines if next step operation is a no-op */
};

................................................................................
   * 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 sqliteBtreeInsert()).
................................................................................
      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;
}

/*
................................................................................
 *             / \
 *            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;
}

................................................................................
}

int sqliteRBtreeOpen(const char *zFilename, int mode, int nPg, Btree **ppBtree)
{
  *ppBtree = (Btree *)sqliteMalloc(sizeof(Btree));
  sqliteHashInit(&(*ppBtree)->tblHash, SQLITE_HASH_INT, 0);

  /* Create binary trees for tables 0, 1 and 2. SQLite assumes these
   * tables always exist. At least I think so? */
  btreeCreateTable(*ppBtree, 0);
  btreeCreateTable(*ppBtree, 1);
  btreeCreateTable(*ppBtree, 2);
  (*ppBtree)->next_idx = 3;
  (*ppBtree)->pOps = &sqliteBtreeOps;
  /* Set file type to 4; this is so that "attach ':memory:' as ...."  does not
  ** think that the database in uninitialised and refuse to attach
  */
  (*ppBtree)->aMetaData[2] = 4;
................................................................................
 */
static int memBtreeDropTable(Btree* tree, int n)
{
  BtRbTree *pTree;
  assert( tree->eTransState != TRANS_NONE );

  memBtreeClearTable(tree, n);
  pTree = sqliteHashFind(&tree->tblHash, 0, n);
  assert(pTree);
  sqliteFree(pTree);
  sqliteHashInsert(&tree->tblHash, 0, n, 0);

  if( tree->eTransState != TRANS_ROLLBACK ){
    BtRollbackOp *pRollbackOp = sqliteMalloc(sizeof(BtRollbackOp));
    pRollbackOp->eOp = ROLLBACK_CREATE;
    pRollbackOp->iTab = n;
    btreeLogRollbackOp(tree, pRollbackOp);
  }

  return SQLITE_OK;
}

static int memBtreeKeyCompare(BtCursor* 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 Btree. The wrFlag
................................................................................
 * 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 memBtreeInsert(BtCursor* pCur, const void *pKey, int nKey,
			     const void *pDataInput, int nData)
{
  void * pData;
  int match;

  /* It is illegal to call sqliteBtreeInsert() if we are not in a transaction */
  assert( pCur->pBtree->eTransState != TRANS_NONE );

................................................................................
    pNode->nKey = nKey;
    pNode->pKey = sqliteMalloc(nKey);
    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;
................................................................................
  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
................................................................................
    pCur->eSkip = SKIP_NEXT;
    if( res ){
      memBtreeLast(pCur, &res);
      memBtreePrevious(pCur, &res);
      pCur->eSkip = SKIP_PREV;
    }
    if( pCur->pBtree->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;
  }

................................................................................
    }
    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 = sqliteMalloc(sizeof(BtRollbackOp));
	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 memBtreeNext(BtCursor* 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;
................................................................................

static int memBtreePrevious(BtCursor* 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;
................................................................................

/*
 * Close the supplied Btree. Delete everything associated with it.
 */
static int memBtreeClose(Btree* tree)
{
  HashElem *p;
  for(p=sqliteHashFirst(&tree->tblHash); p; p=sqliteHashNext(p)){
    tree->eTransState = TRANS_ROLLBACK;
    memBtreeClearTable(tree, sqliteHashKeysize(p));
    sqliteFree(sqliteHashData(p));
  }

  sqliteFree(tree);
  return SQLITE_OK;
}

static int memBtreeSetCacheSize(Btree* tree, int sz)
{
  return SQLITE_OK;
................................................................................
  BtCursor cur;
  int res;

  cur.pBtree = pBtree;
  while( pList ){
    switch( pList->eOp ){
      case ROLLBACK_INSERT:
	cur.pTree  = sqliteHashFind( &pBtree->tblHash, 0, pList->iTab );
	assert(cur.pTree);
	cur.iTree  = pList->iTab;
	cur.eSkip  = SKIP_NONE;
	memBtreeInsert( &cur, pList->pKey,
	    pList->nKey, pList->pData, pList->nData );
	break;
      case ROLLBACK_DELETE:
	cur.pTree  = sqliteHashFind( &pBtree->tblHash, 0, pList->iTab );
	assert(cur.pTree);
	cur.iTree  = pList->iTab;
	cur.eSkip  = SKIP_NONE;
	memBtreeMoveto(&cur, pList->pKey, pList->nKey, &res);
	assert(res == 0);
	memBtreeDelete( &cur );
	break;
      case ROLLBACK_CREATE:
	btreeCreateTable(pBtree, pList->iTab);
	break;
      case ROLLBACK_DROP:
	memBtreeDropTable(pBtree, pList->iTab);
	break;
      default:
	assert(0);
    }
    sqliteFree(pList->pKey);
    sqliteFree(pList->pData);
    pTmp = pList->pNext;
    sqliteFree(pList);
    pList = pTmp;
  }

** 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,v 1.4 2003/04/18 22:52:39 drh Exp $
**
** 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"
................................................................................
*/
#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 Btree {
  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 Btree is to be deleted when closed */
  u8 eTransState; /* State of this Btree wrt transactions */

................................................................................
/*
** Legal values for Btree.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 BtCursor {
  BtCursorOps *pOps;        /* Function table */
  Btree    *pBtree;
  BtRbTree *pTree;
  int       iTree;          /* Index of pTree in pBtree */
  BtRbNode *pNode;
  u8 eSkip;                 /* Determines if next step operation is a no-op */
};

................................................................................
   * 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 sqliteBtreeInsert()).
................................................................................
      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;
}

/*
................................................................................
 *             / \
 *            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;
}

................................................................................
}

int sqliteRBtreeOpen(const char *zFilename, int mode, int nPg, Btree **ppBtree)
{
  *ppBtree = (Btree *)sqliteMalloc(sizeof(Btree));
  sqliteHashInit(&(*ppBtree)->tblHash, SQLITE_HASH_INT, 0);

  /* Create a binary tree for the SQLITE_MASTER table at location 2 */



  btreeCreateTable(*ppBtree, 2);
  (*ppBtree)->next_idx = 3;
  (*ppBtree)->pOps = &sqliteBtreeOps;
  /* Set file type to 4; this is so that "attach ':memory:' as ...."  does not
  ** think that the database in uninitialised and refuse to attach
  */
  (*ppBtree)->aMetaData[2] = 4;
................................................................................
 */
static int memBtreeDropTable(Btree* tree, int n)
{
  BtRbTree *pTree;
  assert( tree->eTransState != TRANS_NONE );

  memBtreeClearTable(tree, n);
  pTree = sqliteHashInsert(&tree->tblHash, 0, n, 0);
  assert(pTree);
  sqliteFree(pTree);


  if( tree->eTransState != TRANS_ROLLBACK ){
    BtRollbackOp *pRollbackOp = sqliteMalloc(sizeof(BtRollbackOp));
    pRollbackOp->eOp = ROLLBACK_CREATE;
    pRollbackOp->iTab = n;
    btreeLogRollbackOp(tree, pRollbackOp);
  }

  return SQLITE_OK;
}

static int memBtreeKeyCompare(BtCursor* 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 Btree. The wrFlag
................................................................................
 * 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 memBtreeInsert(BtCursor* pCur, const void *pKey, int nKey,
                             const void *pDataInput, int nData)
{
  void * pData;
  int match;

  /* It is illegal to call sqliteBtreeInsert() if we are not in a transaction */
  assert( pCur->pBtree->eTransState != TRANS_NONE );

................................................................................
    pNode->nKey = nKey;
    pNode->pKey = sqliteMalloc(nKey);
    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;
................................................................................
  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
................................................................................
    pCur->eSkip = SKIP_NEXT;
    if( res ){
      memBtreeLast(pCur, &res);
      memBtreePrevious(pCur, &res);
      pCur->eSkip = SKIP_PREV;
    }
    if( pCur->pBtree->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;
  }

................................................................................
    }
    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 = sqliteMalloc(sizeof(BtRollbackOp));
        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 memBtreeNext(BtCursor* 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;
................................................................................

static int memBtreePrevious(BtCursor* 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;
................................................................................

/*
 * Close the supplied Btree. Delete everything associated with it.
 */
static int memBtreeClose(Btree* tree)
{
  HashElem *p;
  while( (p=sqliteHashFirst(&tree->tblHash))!=0 ){
    tree->eTransState = TRANS_ROLLBACK;
    memBtreeDropTable(tree, sqliteHashKeysize(p));

  }
  sqliteHashClear(&tree->tblHash);
  sqliteFree(tree);
  return SQLITE_OK;
}

static int memBtreeSetCacheSize(Btree* tree, int sz)
{
  return SQLITE_OK;
................................................................................
  BtCursor cur;
  int res;

  cur.pBtree = pBtree;
  while( pList ){
    switch( pList->eOp ){
      case ROLLBACK_INSERT:
        cur.pTree  = sqliteHashFind( &pBtree->tblHash, 0, pList->iTab );
        assert(cur.pTree);
        cur.iTree  = pList->iTab;
        cur.eSkip  = SKIP_NONE;
        memBtreeInsert( &cur, pList->pKey,
            pList->nKey, pList->pData, pList->nData );
        break;
      case ROLLBACK_DELETE:
        cur.pTree  = sqliteHashFind( &pBtree->tblHash, 0, pList->iTab );
        assert(cur.pTree);
        cur.iTree  = pList->iTab;
        cur.eSkip  = SKIP_NONE;
        memBtreeMoveto(&cur, pList->pKey, pList->nKey, &res);
        assert(res == 0);
        memBtreeDelete( &cur );
        break;
      case ROLLBACK_CREATE:
        btreeCreateTable(pBtree, pList->iTab);
        break;
      case ROLLBACK_DROP:
        memBtreeDropTable(pBtree, pList->iTab);
        break;
      default:
        assert(0);
    }
    sqliteFree(pList->pKey);
    sqliteFree(pList->pData);
    pTmp = pList->pNext;
    sqliteFree(pList);
    pList = pTmp;
  }