btree_rb.c

sqlite数据库管理系统开放源码

  {
    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 */