/*
** Return a pointer to the pBefore or pAfter pointer in the parent
** of p that points to p.  Or if p is the root node, return pp.
*/
static KVMemNode **kvmemFromPtr(KVMemNode *p, KVMemNode **pp){
  KVMemNode *pUp = p->pUp;
  if( pUp==0 ) return pp;

  if( pUp->pAfter==p ) return &pUp->pAfter;
  return &pUp->pBefore;
}

/*
** Rebalance all nodes starting with p and working up to the root.
** Return the new root.
................................................................................
      pNode = 0;
    }else{
      pChng->pData = 0;
    }
  }
  return pNode;
}

































/* Remove node pOld from the tree.  pOld must be an element of the tree.
*/
static void kvmemRemoveNode(KVMem *p, KVMemNode *pOld){
  KVMemNode **ppParent;           /* Location of pointer to pOld */
  KVMemNode *pBalance;            /* Node to run kvmemBalance() on */
  kvmemDataUnref(pOld->pData);
  pOld->pData = 0;
  ppParent = kvmemFromPtr(pOld, &p->pRoot);
  if( pOld->pBefore==0 && pOld->pAfter==0 ){
    *ppParent = 0;
    pBalance = pOld->pUp;
  }else if( pOld->pBefore && pOld->pAfter ){
    KVMemNode *pX, *pY;

    pX = kvmemFirst(pOld->pAfter);
    assert( pX->pBefore==0 );
    *kvmemFromPtr(pX, 0) = pX->pAfter;

    pBalance = pX->pUp;
    pX->pAfter = pOld->pAfter;
    if( pX->pAfter ){
      pX->pAfter->pUp = pX;
    }else{
      assert( pBalance==pOld );
      pBalance = pX;
................................................................................
  return SQLITE_OK;
}
static int kvmemCommitPhaseTwo(KVStore *pKVStore, int iLevel){
  KVMem *p = (KVMem*)pKVStore;
  assert( p->iMagicKVMemBase==SQLITE_KVMEMBASE_MAGIC );
  assert( iLevel>=0 );
  assert( iLevel<p->base.iTransLevel );

  while( p->base.iTransLevel>iLevel && p->base.iTransLevel>1 ){
    KVMemChng *pChng, *pNext;
    for(pChng=p->apLog[p->base.iTransLevel-2]; pChng; pChng=pNext){
      KVMemNode *pNode = pChng->pNode;
      if( pNode->pData ){
        pNode->mxTrans = pChng->oldTrans;
      }else{
................................................................................
      kvmemDataUnref(pChng->pData);
      pNext = pChng->pNext;
      sqlite4_free(pChng);
    }
    p->apLog[p->base.iTransLevel-2] = 0;
    p->base.iTransLevel--;
  }

  p->base.iTransLevel = iLevel;
  return SQLITE_OK;
}

/*
** Rollback a transaction or subtransaction.
**

/*
** Return a pointer to the pBefore or pAfter pointer in the parent
** of p that points to p.  Or if p is the root node, return pp.
*/
static KVMemNode **kvmemFromPtr(KVMemNode *p, KVMemNode **pp){
  KVMemNode *pUp = p->pUp;
  if( pUp==0 ) return pp;
  assert( pUp->pAfter==p || pUp->pBefore==p );
  if( pUp->pAfter==p ) return &pUp->pAfter;
  return &pUp->pBefore;
}

/*
** Rebalance all nodes starting with p and working up to the root.
** Return the new root.
................................................................................
      pNode = 0;
    }else{
      pChng->pData = 0;
    }
  }
  return pNode;
}

#ifdef SQLITE_DEBUG
/*
** Return the number of times that node pNode occurs in the sub-tree 
** headed by node pSub. This is used to assert() that no node structure
** is linked into the tree more than once.
*/
static int countNodeOccurences(KVMemNode *pSub, KVMemNode *pNode){
  int iRet = (pSub==pNode);
  if( pSub ){
    iRet += countNodeOccurences(pSub->pBefore, pNode);
    iRet += countNodeOccurences(pSub->pAfter, pNode);
  }
  return iRet;
}

/*
** Check that all the pUp pointers in the sub-tree headed by pSub are
** correct. Fail an assert if this is not the case.
*/
static void assertUpPointers(KVMemNode *pSub){
  if( pSub ){
    assert( pSub->pBefore==0 || pSub->pBefore->pUp==pSub );
    assert( pSub->pAfter==0 || pSub->pAfter->pUp==pSub );
    assertUpPointers(pSub->pBefore);
    assertUpPointers(pSub->pAfter);
  }
}

#else
#define assertUpPointers(x)
#endif

/* Remove node pOld from the tree.  pOld must be an element of the tree.
*/
static void kvmemRemoveNode(KVMem *p, KVMemNode *pOld){
  KVMemNode **ppParent;           /* Location of pointer to pOld */
  KVMemNode *pBalance;            /* Node to run kvmemBalance() on */
  kvmemDataUnref(pOld->pData);
  pOld->pData = 0;
  ppParent = kvmemFromPtr(pOld, &p->pRoot);
  if( pOld->pBefore==0 && pOld->pAfter==0 ){
    *ppParent = 0;
    pBalance = pOld->pUp;
  }else if( pOld->pBefore && pOld->pAfter ){
    KVMemNode *pX;                /* Smallest node that is larger than pOld */
    KVMemNode *pY;                /* Left-hand child of pOld */
    pX = kvmemFirst(pOld->pAfter);
    assert( pX->pBefore==0 );
    *kvmemFromPtr(pX, 0) = pX->pAfter;
    if( pX->pAfter ) pX->pAfter->pUp = pX->pUp;
    pBalance = pX->pUp;
    pX->pAfter = pOld->pAfter;
    if( pX->pAfter ){
      pX->pAfter->pUp = pX;
    }else{
      assert( pBalance==pOld );
      pBalance = pX;
................................................................................
  return SQLITE_OK;
}
static int kvmemCommitPhaseTwo(KVStore *pKVStore, int iLevel){
  KVMem *p = (KVMem*)pKVStore;
  assert( p->iMagicKVMemBase==SQLITE_KVMEMBASE_MAGIC );
  assert( iLevel>=0 );
  assert( iLevel<p->base.iTransLevel );
  assertUpPointers(p->pRoot);
  while( p->base.iTransLevel>iLevel && p->base.iTransLevel>1 ){
    KVMemChng *pChng, *pNext;
    for(pChng=p->apLog[p->base.iTransLevel-2]; pChng; pChng=pNext){
      KVMemNode *pNode = pChng->pNode;
      if( pNode->pData ){
        pNode->mxTrans = pChng->oldTrans;
      }else{
................................................................................
      kvmemDataUnref(pChng->pData);
      pNext = pChng->pNext;
      sqlite4_free(pChng);
    }
    p->apLog[p->base.iTransLevel-2] = 0;
    p->base.iTransLevel--;
  }
  assertUpPointers(p->pRoot);
  p->base.iTransLevel = iLevel;
  return SQLITE_OK;
}

/*
** Rollback a transaction or subtransaction.
**