/*** 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_INMEMORYDBtypedef 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;}