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.15 2003/08/27 22:52:34 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"

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;

  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
 *

{
  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));
    pRollbackOp->eOp = ROLLBACK_CREATE;
    pRollbackOp->iTab = n;
    btreeLogRollbackOp(tree, pRollbackOp);

    }
  }
  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));
  pCur->pTree  = sqliteHashFind(&tree->tblHash, 0, iTable);
  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)

){
  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 = sqliteMalloc(nData);
  memcpy(pData, pDataInput, nData);

  /* Move the cursor to a node near the key to be inserted. If the key already

{
  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 

    return pCur->pNode->nData-offset;
  }
  assert(0);
}

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 );

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;