{    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_TESTstatic 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;}#endifstatic 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 */