btree_rb.c

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

/*
** 2003 Feb 4
**
** The author disclaims copyright to this source code.  In place of
** 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.24.2.1 2004/06/26 14:40:05 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"
#include "sqliteInt.h"
#include <assert.h>

/*
** Omit this whole file if the SQLITE_OMIT_INMEMORYDB macro is
** defined.  This allows a lot of code to be omitted for installations
** that do not need it.
*/
#ifndef SQLITE_OMIT_INMEMORYDB


typedef struct BtRbTree BtRbTree;
typedef struct BtRbNode BtRbNode;
typedef struct BtRollbackOp BtRollbackOp;
typedef struct Rbtree Rbtree;
typedef struct RbtCursor RbtCursor;

/* Forward declarations */
static BtOps sqliteRbtreeOps;
static BtCursorOps sqliteRbtreeCursorOps;

/*
 * During each transaction (or checkpoint), a linked-list of
 * "rollback-operations" is accumulated. If the transaction is rolled back,
 * then the list of operations must be executed (to restore the database to
 * it's state before the transaction started). If the transaction is to be
 * committed, just delete the list.
 *
 * Each operation is represented as follows, depending on the value of eOp:
 *
 * ROLLBACK_INSERT  ->  Need to insert (pKey, pData) into table iTab.
 * ROLLBACK_DELETE  ->  Need to delete the record (pKey) into table iTab.
 * ROLLBACK_CREATE  ->  Need to create table iTab.
 * ROLLBACK_DROP    ->  Need to drop table iTab.
 */
struct BtRollbackOp {
  u8 eOp;
  int iTab;
  int nKey; 
  void *pKey;
  int nData;
  void *pData;
  BtRollbackOp *pNext;
};

/*
** Legal values for BtRollbackOp.eOp:
*/
#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 Rbtree {
  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 Rbtree is to be deleted when closed */
  u8 eTransState; /* State of this Rbtree wrt transactions */

  BtRollbackOp *pTransRollback; 
  BtRollbackOp *pCheckRollback;
  BtRollbackOp *pCheckRollbackTail;
};

/*
** Legal values for Rbtree.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 RbtCursor {
  BtCursorOps *pOps;        /* Function table */
  Rbtree    *pRbtree;
  BtRbTree *pTree;
  int       iTree;          /* Index of pTree in pRbtree */
  BtRbNode *pNode;
  RbtCursor *pShared;       /* List of all cursors on the same Rbtree */
  u8 eSkip;                 /* Determines if next step operation is a no-op */
  u8 wrFlag;                /* True if this cursor is open for writing */
};

/*
** Legal values for RbtCursor.eSkip.
*/
#define SKIP_NONE     0   /* Always step the cursor */
#define SKIP_NEXT     1   /* The next sqliteRbtreeNext() is a no-op */
#define SKIP_PREV     2   /* The next sqliteRbtreePrevious() is a no-op */
#define SKIP_INVALID  3   /* Calls to Next() and Previous() are invalid */

struct BtRbTree {
  RbtCursor *pCursors;     /* All cursors pointing to this tree */
  BtRbNode *pHead;         /* Head of the tree, or NULL */
};

struct BtRbNode {
  int nKey;
  void *pKey;
  int nData;
  void *pData;
  u8 isBlack;        /* true for a black node, 0 for a red node */
  BtRbNode *pParent; /* Nodes parent node, NULL for the tree head */
  BtRbNode *pLeft;   /* Nodes left child, or NULL */
  BtRbNode *pRight;  /* Nodes right child, or NULL */

  int nBlackHeight;  /* Only used during the red-black integrity check */
};

/* Forward declarations */
static int memRbtreeMoveto(
  RbtCursor* pCur,
  const void *pKey,
  int nKey,
  int *pRes
);
static int memRbtreeClearTable(Rbtree* tree, int n);
static int memRbtreeNext(RbtCursor* pCur, int *pRes);
static int memRbtreeLast(RbtCursor* pCur, int *pRes);
static int memRbtreePrevious(RbtCursor* pCur, int *pRes);


/*
** This routine checks all cursors that point to the same table
** as pCur points to.  If any of those cursors were opened with
** wrFlag==0 then this routine returns SQLITE_LOCKED.  If all
** cursors point to the same table were opened with wrFlag==1
** then this routine returns SQLITE_OK.
**
** In addition to checking for read-locks (where a read-lock 
** means a cursor opened with wrFlag==0) this routine also NULLs
** out the pNode field of all other cursors.
** This is necessary because an insert 
** or delete might change erase the node out from under
** another cursor.
*/
static int checkReadLocks(RbtCursor *pCur){
  RbtCursor *p;
  assert( pCur->wrFlag );
  for(p=pCur->pTree->pCursors; p; p=p->pShared){
    if( p!=pCur ){
      if( p->wrFlag==0 ) return SQLITE_LOCKED;
      p->pNode = 0;
    }
  }
  return SQLITE_OK;
}

/*
 * The key-compare function for the red-black trees. Returns as follows:
 *
 * (key1 < key2)             -1
 * (key1 == key2)             0 
 * (key1 > key2)              1
 *
 * Keys are compared using memcmp(). If one key is an exact prefix of the
 * other, then the shorter key is less than the longer key.
 */
static int key_compare(void const*pKey1, int nKey1, void const*pKey2, int nKey2)
{
  int mcmp = memcmp(pKey1, pKey2, (nKey1 <= nKey2)?nKey1:nKey2);
  if( mcmp == 0){
    if( nKey1 == nKey2 ) return 0;
    return ((nKey1 < nKey2)?-1:1);
  }
  return ((mcmp>0)?1:-1);
}

/*
 * Perform the LEFT-rotate transformation on node X of tree pTree. This
 * transform is part of the red-black balancing code.
 *
 *        |                   |
 *        X                   Y
 *       / \                 / \
 *      a   Y               X   c
 *         / \             / \
 *        b   c           a   b
 *
 *      BEFORE              AFTER
 */
static void leftRotate(BtRbTree *pTree, BtRbNode *pX)
{
  BtRbNode *pY;
  BtRbNode *pb;
  pY = pX->pRight;
  pb = pY->pLeft;

  pY->pParent = pX->pParent;
  if( pX->pParent ){
    if( pX->pParent->pLeft == pX ) pX->pParent->pLeft = pY;
    else pX->pParent->pRight = pY;
  }
  pY->pLeft = pX;
  pX->pParent = pY;
  pX->pRight = pb;
  if( pb ) pb->pParent = pX;
  if( pTree->pHead == pX ) pTree->pHead = pY;
}

/*
 * Perform the RIGHT-rotate transformation on node X of tree pTree. This
 * transform is part of the red-black balancing code.
 *
 *        |                   |
 *        X                   Y
 *       / \                 / \
 *      Y   c               a   X
 *     / \                     / \
 *    a   b                   b   c
 *
 *      BEFORE              AFTER
 */
static void rightRotate(BtRbTree *pTree, BtRbNode *pX)
{
  BtRbNode *pY;
  BtRbNode *pb;
  pY = pX->pLeft;
  pb = pY->pRight;

  pY->pParent = pX->pParent;
  if( pX->pParent ){
    if( pX->pParent->pLeft == pX ) pX->pParent->pLeft = pY;
    else pX->pParent->pRight = pY;
  }
  pY->pRight = pX;
  pX->pParent = pY;
  pX->pLeft = pb;
  if( pb ) pb->pParent = pX;
  if( pTree->pHead == pX ) pTree->pHead = pY;
}

/*
 * A string-manipulation helper function for check_redblack_tree(). If (orig ==
 * NULL) a copy of val is returned. If (orig != NULL) then a copy of the *
 * concatenation of orig and val is returned. The original orig is deleted
 * (using sqliteFree()).
 */
static char *append_val(char * orig, char const * val){
  char *z;
  if( !orig ){
    z = sqliteStrDup( val );
  } else{
    z = 0;
    sqliteSetString(&z, orig, val, (char*)0);
    sqliteFree( orig );
  }
  return z;
}

/*
 * Append a string representation of the entire node to orig and return it.
 * This is used to produce debugging information if check_redblack_tree() finds
 * a problem with a red-black binary tree.
 */
static char *append_node(char * orig, BtRbNode *pNode, int indent)
{
  char buf[128];
  int i;

  for( i=0; i<indent; i++ ){
      orig = append_val(orig, " ");
  }

  sprintf(buf, "%p", pNode);
  orig = append_val(orig, buf);

  if( pNode ){
    indent += 3;
    if( pNode->isBlack ){
      orig = append_val(orig, " B \n");
    }else{
      orig = append_val(orig, " R \n");
    }
    orig = append_node( orig, pNode->pLeft, indent );
    orig = append_node( orig, pNode->pRight, indent );
  }else{
    orig = append_val(orig, "\n");
  }
  return orig;
}

/*
 * Print a representation of a node to stdout. This function is only included
 * so you can call it from within a debugger if things get really bad.  It
 * is not called from anyplace in the code.
 */
static void print_node(BtRbNode *pNode)
{
    char * str = append_node(0, pNode, 0);
    printf("%s", str);

    /* Suppress a warning message about print_node() being unused */
    (void)print_node;
}

/* 
 * Check the following properties of the red-black tree:
 * (1) - If a node is red, both of it's children are black
 * (2) - Each path from a given node to a leaf (NULL) node passes thru the
 *       same number of black nodes 
 *
 * If there is a problem, append a description (using append_val() ) to *msg.
 */
static void check_redblack_tree(BtRbTree * tree, char ** msg)
{
  BtRbNode *pNode;

  /* 0 -> came from parent 
   * 1 -> came from left
   * 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 sqliteRbtreeInsert()).
 * It is possible that pX is a red node with a red parent, which is a violation
 * of the red-black tree properties. This function performs rotations and 
 * color changes to rebalance the tree
 */
static void do_insert_balancing(BtRbTree *pTree, BtRbNode *pX)
{
  /* In the first iteration of this loop, pX points to the red node just
   * inserted in the tree. If the parent of pX exists (pX is not the root
   * node) and is red, then the properties of the red-black tree are
   * violated.
   *
   * At the start of any subsequent iterations, pX points to a red node
   * with a red parent. In all other respects the tree is a legal red-black
   * binary tree. */
  while( pX != pTree->pHead && !pX->pParent->isBlack ){
    BtRbNode *pUncle;
    BtRbNode *pGrandparent;

    /* Grandparent of pX must exist and must be black. */
    pGrandparent = pX->pParent->pParent;
    assert( pGrandparent );
    assert( pGrandparent->isBlack );

    /* Uncle of pX may or may not exist. */
    if( pX->pParent == pGrandparent->pLeft ) 
      pUncle = pGrandparent->pRight;
    else 
      pUncle = pGrandparent->pLeft;

    /* If the uncle of pX exists and is red, we do the following:
     *       |                 |
     *      G(b)              G(r)
     *      /  \              /  \        
     *   U(r)   P(r)       U(b)  P(b)
     *            \                \
     *           X(r)              X(r)
     *
     *     BEFORE             AFTER
     * pX is then set to G. If the parent of G is red, then the while loop
     * will run again.  */
    if( pUncle && !pUncle->isBlack ){
      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;
}