btree_rb.c

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

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