Back to index

php5  5.3.10
btree_rb.c
Go to the documentation of this file.
00001 /*
00002 ** 2003 Feb 4
00003 **
00004 ** The author disclaims copyright to this source code.  In place of
00005 ** a legal notice, here is a blessing:
00006 **
00007 **    May you do good and not evil.
00008 **    May you find forgiveness for yourself and forgive others.
00009 **    May you share freely, never taking more than you give.
00010 **
00011 *************************************************************************
00012 ** $Id: btree_rb.c 195361 2005-09-07 15:11:33Z iliaa $
00013 **
00014 ** This file implements an in-core database using Red-Black balanced
00015 ** binary trees.
00016 ** 
00017 ** It was contributed to SQLite by anonymous on 2003-Feb-04 23:24:49 UTC.
00018 */
00019 #include "btree.h"
00020 #include "sqliteInt.h"
00021 #include <assert.h>
00022 
00023 /*
00024 ** Omit this whole file if the SQLITE_OMIT_INMEMORYDB macro is
00025 ** defined.  This allows a lot of code to be omitted for installations
00026 ** that do not need it.
00027 */
00028 #ifndef SQLITE_OMIT_INMEMORYDB
00029 
00030 
00031 typedef struct BtRbTree BtRbTree;
00032 typedef struct BtRbNode BtRbNode;
00033 typedef struct BtRollbackOp BtRollbackOp;
00034 typedef struct Rbtree Rbtree;
00035 typedef struct RbtCursor RbtCursor;
00036 
00037 /* Forward declarations */
00038 static BtOps sqliteRbtreeOps;
00039 static BtCursorOps sqliteRbtreeCursorOps;
00040 
00041 /*
00042  * During each transaction (or checkpoint), a linked-list of
00043  * "rollback-operations" is accumulated. If the transaction is rolled back,
00044  * then the list of operations must be executed (to restore the database to
00045  * it's state before the transaction started). If the transaction is to be
00046  * committed, just delete the list.
00047  *
00048  * Each operation is represented as follows, depending on the value of eOp:
00049  *
00050  * ROLLBACK_INSERT  ->  Need to insert (pKey, pData) into table iTab.
00051  * ROLLBACK_DELETE  ->  Need to delete the record (pKey) into table iTab.
00052  * ROLLBACK_CREATE  ->  Need to create table iTab.
00053  * ROLLBACK_DROP    ->  Need to drop table iTab.
00054  */
00055 struct BtRollbackOp {
00056   u8 eOp;
00057   int iTab;
00058   int nKey; 
00059   void *pKey;
00060   int nData;
00061   void *pData;
00062   BtRollbackOp *pNext;
00063 };
00064 
00065 /*
00066 ** Legal values for BtRollbackOp.eOp:
00067 */
00068 #define ROLLBACK_INSERT 1 /* Insert a record */
00069 #define ROLLBACK_DELETE 2 /* Delete a record */
00070 #define ROLLBACK_CREATE 3 /* Create a table */
00071 #define ROLLBACK_DROP   4 /* Drop a table */
00072 
00073 struct Rbtree {
00074   BtOps *pOps;    /* Function table */
00075   int aMetaData[SQLITE_N_BTREE_META];
00076 
00077   int next_idx;   /* next available table index */
00078   Hash tblHash;   /* All created tables, by index */
00079   u8 isAnonymous; /* True if this Rbtree is to be deleted when closed */
00080   u8 eTransState; /* State of this Rbtree wrt transactions */
00081 
00082   BtRollbackOp *pTransRollback; 
00083   BtRollbackOp *pCheckRollback;
00084   BtRollbackOp *pCheckRollbackTail;
00085 };
00086 
00087 /*
00088 ** Legal values for Rbtree.eTransState.
00089 */
00090 #define TRANS_NONE           0  /* No transaction is in progress */
00091 #define TRANS_INTRANSACTION  1  /* A transaction is in progress */
00092 #define TRANS_INCHECKPOINT   2  /* A checkpoint is in progress  */
00093 #define TRANS_ROLLBACK       3  /* We are currently rolling back a checkpoint or
00094                                  * transaction. */
00095 
00096 struct RbtCursor {
00097   BtCursorOps *pOps;        /* Function table */
00098   Rbtree    *pRbtree;
00099   BtRbTree *pTree;
00100   int       iTree;          /* Index of pTree in pRbtree */
00101   BtRbNode *pNode;
00102   RbtCursor *pShared;       /* List of all cursors on the same Rbtree */
00103   u8 eSkip;                 /* Determines if next step operation is a no-op */
00104   u8 wrFlag;                /* True if this cursor is open for writing */
00105 };
00106 
00107 /*
00108 ** Legal values for RbtCursor.eSkip.
00109 */
00110 #define SKIP_NONE     0   /* Always step the cursor */
00111 #define SKIP_NEXT     1   /* The next sqliteRbtreeNext() is a no-op */
00112 #define SKIP_PREV     2   /* The next sqliteRbtreePrevious() is a no-op */
00113 #define SKIP_INVALID  3   /* Calls to Next() and Previous() are invalid */
00114 
00115 struct BtRbTree {
00116   RbtCursor *pCursors;     /* All cursors pointing to this tree */
00117   BtRbNode *pHead;         /* Head of the tree, or NULL */
00118 };
00119 
00120 struct BtRbNode {
00121   int nKey;
00122   void *pKey;
00123   int nData;
00124   void *pData;
00125   u8 isBlack;        /* true for a black node, 0 for a red node */
00126   BtRbNode *pParent; /* Nodes parent node, NULL for the tree head */
00127   BtRbNode *pLeft;   /* Nodes left child, or NULL */
00128   BtRbNode *pRight;  /* Nodes right child, or NULL */
00129 
00130   int nBlackHeight;  /* Only used during the red-black integrity check */
00131 };
00132 
00133 /* Forward declarations */
00134 static int memRbtreeMoveto(
00135   RbtCursor* pCur,
00136   const void *pKey,
00137   int nKey,
00138   int *pRes
00139 );
00140 static int memRbtreeClearTable(Rbtree* tree, int n);
00141 static int memRbtreeNext(RbtCursor* pCur, int *pRes);
00142 static int memRbtreeLast(RbtCursor* pCur, int *pRes);
00143 static int memRbtreePrevious(RbtCursor* pCur, int *pRes);
00144 
00145 
00146 /*
00147 ** This routine checks all cursors that point to the same table
00148 ** as pCur points to.  If any of those cursors were opened with
00149 ** wrFlag==0 then this routine returns SQLITE_LOCKED.  If all
00150 ** cursors point to the same table were opened with wrFlag==1
00151 ** then this routine returns SQLITE_OK.
00152 **
00153 ** In addition to checking for read-locks (where a read-lock 
00154 ** means a cursor opened with wrFlag==0) this routine also NULLs
00155 ** out the pNode field of all other cursors.
00156 ** This is necessary because an insert 
00157 ** or delete might change erase the node out from under
00158 ** another cursor.
00159 */
00160 static int checkReadLocks(RbtCursor *pCur){
00161   RbtCursor *p;
00162   assert( pCur->wrFlag );
00163   for(p=pCur->pTree->pCursors; p; p=p->pShared){
00164     if( p!=pCur ){
00165       if( p->wrFlag==0 ) return SQLITE_LOCKED;
00166       p->pNode = 0;
00167     }
00168   }
00169   return SQLITE_OK;
00170 }
00171 
00172 /*
00173  * The key-compare function for the red-black trees. Returns as follows:
00174  *
00175  * (key1 < key2)             -1
00176  * (key1 == key2)             0 
00177  * (key1 > key2)              1
00178  *
00179  * Keys are compared using memcmp(). If one key is an exact prefix of the
00180  * other, then the shorter key is less than the longer key.
00181  */
00182 static int key_compare(void const*pKey1, int nKey1, void const*pKey2, int nKey2)
00183 {
00184   int mcmp = memcmp(pKey1, pKey2, (nKey1 <= nKey2)?nKey1:nKey2);
00185   if( mcmp == 0){
00186     if( nKey1 == nKey2 ) return 0;
00187     return ((nKey1 < nKey2)?-1:1);
00188   }
00189   return ((mcmp>0)?1:-1);
00190 }
00191 
00192 /*
00193  * Perform the LEFT-rotate transformation on node X of tree pTree. This
00194  * transform is part of the red-black balancing code.
00195  *
00196  *        |                   |
00197  *        X                   Y
00198  *       / \                 / \
00199  *      a   Y               X   c
00200  *         / \             / \
00201  *        b   c           a   b
00202  *
00203  *      BEFORE              AFTER
00204  */
00205 static void leftRotate(BtRbTree *pTree, BtRbNode *pX)
00206 {
00207   BtRbNode *pY;
00208   BtRbNode *pb;
00209   pY = pX->pRight;
00210   pb = pY->pLeft;
00211 
00212   pY->pParent = pX->pParent;
00213   if( pX->pParent ){
00214     if( pX->pParent->pLeft == pX ) pX->pParent->pLeft = pY;
00215     else pX->pParent->pRight = pY;
00216   }
00217   pY->pLeft = pX;
00218   pX->pParent = pY;
00219   pX->pRight = pb;
00220   if( pb ) pb->pParent = pX;
00221   if( pTree->pHead == pX ) pTree->pHead = pY;
00222 }
00223 
00224 /*
00225  * Perform the RIGHT-rotate transformation on node X of tree pTree. This
00226  * transform is part of the red-black balancing code.
00227  *
00228  *        |                   |
00229  *        X                   Y
00230  *       / \                 / \
00231  *      Y   c               a   X
00232  *     / \                     / \
00233  *    a   b                   b   c
00234  *
00235  *      BEFORE              AFTER
00236  */
00237 static void rightRotate(BtRbTree *pTree, BtRbNode *pX)
00238 {
00239   BtRbNode *pY;
00240   BtRbNode *pb;
00241   pY = pX->pLeft;
00242   pb = pY->pRight;
00243 
00244   pY->pParent = pX->pParent;
00245   if( pX->pParent ){
00246     if( pX->pParent->pLeft == pX ) pX->pParent->pLeft = pY;
00247     else pX->pParent->pRight = pY;
00248   }
00249   pY->pRight = pX;
00250   pX->pParent = pY;
00251   pX->pLeft = pb;
00252   if( pb ) pb->pParent = pX;
00253   if( pTree->pHead == pX ) pTree->pHead = pY;
00254 }
00255 
00256 /*
00257  * A string-manipulation helper function for check_redblack_tree(). If (orig ==
00258  * NULL) a copy of val is returned. If (orig != NULL) then a copy of the *
00259  * concatenation of orig and val is returned. The original orig is deleted
00260  * (using sqliteFree()).
00261  */
00262 static char *append_val(char * orig, char const * val){
00263   char *z;
00264   if( !orig ){
00265     z = sqliteStrDup( val );
00266   } else{
00267     z = 0;
00268     sqliteSetString(&z, orig, val, (char*)0);
00269     sqliteFree( orig );
00270   }
00271   return z;
00272 }
00273 
00274 /*
00275  * Append a string representation of the entire node to orig and return it.
00276  * This is used to produce debugging information if check_redblack_tree() finds
00277  * a problem with a red-black binary tree.
00278  */
00279 static char *append_node(char * orig, BtRbNode *pNode, int indent)
00280 {
00281   char buf[128];
00282   int i;
00283 
00284   for( i=0; i<indent; i++ ){
00285       orig = append_val(orig, " ");
00286   }
00287 
00288   sprintf(buf, "%p", pNode);
00289   orig = append_val(orig, buf);
00290 
00291   if( pNode ){
00292     indent += 3;
00293     if( pNode->isBlack ){
00294       orig = append_val(orig, " B \n");
00295     }else{
00296       orig = append_val(orig, " R \n");
00297     }
00298     orig = append_node( orig, pNode->pLeft, indent );
00299     orig = append_node( orig, pNode->pRight, indent );
00300   }else{
00301     orig = append_val(orig, "\n");
00302   }
00303   return orig;
00304 }
00305 
00306 /*
00307  * Print a representation of a node to stdout. This function is only included
00308  * so you can call it from within a debugger if things get really bad.  It
00309  * is not called from anyplace in the code.
00310  */
00311 static void print_node(BtRbNode *pNode)
00312 {
00313     char * str = append_node(0, pNode, 0);
00314     printf("%s", str);
00315 
00316     /* Suppress a warning message about print_node() being unused */
00317     (void)print_node;
00318 }
00319 
00320 /* 
00321  * Check the following properties of the red-black tree:
00322  * (1) - If a node is red, both of it's children are black
00323  * (2) - Each path from a given node to a leaf (NULL) node passes thru the
00324  *       same number of black nodes 
00325  *
00326  * If there is a problem, append a description (using append_val() ) to *msg.
00327  */
00328 static void check_redblack_tree(BtRbTree * tree, char ** msg)
00329 {
00330   BtRbNode *pNode;
00331 
00332   /* 0 -> came from parent 
00333    * 1 -> came from left
00334    * 2 -> came from right */
00335   int prev_step = 0;
00336 
00337   pNode = tree->pHead;
00338   while( pNode ){
00339     switch( prev_step ){
00340       case 0:
00341         if( pNode->pLeft ){
00342           pNode = pNode->pLeft;
00343         }else{ 
00344           prev_step = 1;
00345         }
00346         break;
00347       case 1:
00348         if( pNode->pRight ){
00349           pNode = pNode->pRight;
00350           prev_step = 0;
00351         }else{
00352           prev_step = 2;
00353         }
00354         break;
00355       case 2:
00356         /* Check red-black property (1) */
00357         if( !pNode->isBlack &&
00358             ( (pNode->pLeft && !pNode->pLeft->isBlack) ||
00359               (pNode->pRight && !pNode->pRight->isBlack) )
00360           ){
00361           char buf[128];
00362           sprintf(buf, "Red node with red child at %p\n", pNode);
00363           *msg = append_val(*msg, buf);
00364           *msg = append_node(*msg, tree->pHead, 0);
00365           *msg = append_val(*msg, "\n");
00366         }
00367 
00368         /* Check red-black property (2) */
00369         { 
00370           int leftHeight = 0;
00371           int rightHeight = 0;
00372           if( pNode->pLeft ){
00373             leftHeight += pNode->pLeft->nBlackHeight;
00374             leftHeight += (pNode->pLeft->isBlack?1:0);
00375           }
00376           if( pNode->pRight ){
00377             rightHeight += pNode->pRight->nBlackHeight;
00378             rightHeight += (pNode->pRight->isBlack?1:0);
00379           }
00380           if( leftHeight != rightHeight ){
00381             char buf[128];
00382             sprintf(buf, "Different black-heights at %p\n", pNode);
00383             *msg = append_val(*msg, buf);
00384             *msg = append_node(*msg, tree->pHead, 0);
00385             *msg = append_val(*msg, "\n");
00386           }
00387           pNode->nBlackHeight = leftHeight;
00388         }
00389 
00390         if( pNode->pParent ){
00391           if( pNode == pNode->pParent->pLeft ) prev_step = 1;
00392           else prev_step = 2;
00393         }
00394         pNode = pNode->pParent;
00395         break;
00396       default: assert(0);
00397     }
00398   }
00399 } 
00400 
00401 /*
00402  * Node pX has just been inserted into pTree (by code in sqliteRbtreeInsert()).
00403  * It is possible that pX is a red node with a red parent, which is a violation
00404  * of the red-black tree properties. This function performs rotations and 
00405  * color changes to rebalance the tree
00406  */
00407 static void do_insert_balancing(BtRbTree *pTree, BtRbNode *pX)
00408 {
00409   /* In the first iteration of this loop, pX points to the red node just
00410    * inserted in the tree. If the parent of pX exists (pX is not the root
00411    * node) and is red, then the properties of the red-black tree are
00412    * violated.
00413    *
00414    * At the start of any subsequent iterations, pX points to a red node
00415    * with a red parent. In all other respects the tree is a legal red-black
00416    * binary tree. */
00417   while( pX != pTree->pHead && !pX->pParent->isBlack ){
00418     BtRbNode *pUncle;
00419     BtRbNode *pGrandparent;
00420 
00421     /* Grandparent of pX must exist and must be black. */
00422     pGrandparent = pX->pParent->pParent;
00423     assert( pGrandparent );
00424     assert( pGrandparent->isBlack );
00425 
00426     /* Uncle of pX may or may not exist. */
00427     if( pX->pParent == pGrandparent->pLeft ) 
00428       pUncle = pGrandparent->pRight;
00429     else 
00430       pUncle = pGrandparent->pLeft;
00431 
00432     /* If the uncle of pX exists and is red, we do the following:
00433      *       |                 |
00434      *      G(b)              G(r)
00435      *      /  \              /  \        
00436      *   U(r)   P(r)       U(b)  P(b)
00437      *            \                \
00438      *           X(r)              X(r)
00439      *
00440      *     BEFORE             AFTER
00441      * pX is then set to G. If the parent of G is red, then the while loop
00442      * will run again.  */
00443     if( pUncle && !pUncle->isBlack ){
00444       pGrandparent->isBlack = 0;
00445       pUncle->isBlack = 1;
00446       pX->pParent->isBlack = 1;
00447       pX = pGrandparent;
00448     }else{
00449 
00450       if( pX->pParent == pGrandparent->pLeft ){
00451         if( pX == pX->pParent->pRight ){
00452           /* If pX is a right-child, do the following transform, essentially
00453            * to change pX into a left-child: 
00454            *       |                  | 
00455            *      G(b)               G(b)
00456            *      /  \               /  \        
00457            *   P(r)   U(b)        X(r)  U(b)
00458            *      \                /
00459            *     X(r)            P(r) <-- new X
00460            *
00461            *     BEFORE             AFTER
00462            */
00463           pX = pX->pParent;
00464           leftRotate(pTree, pX);
00465         }
00466 
00467         /* Do the following transform, which balances the tree :) 
00468          *       |                  | 
00469          *      G(b)               P(b)
00470          *      /  \               /  \        
00471          *   P(r)   U(b)        X(r)  G(r)
00472          *    /                         \
00473          *  X(r)                        U(b)
00474          *
00475          *     BEFORE             AFTER
00476          */
00477         assert( pGrandparent == pX->pParent->pParent );
00478         pGrandparent->isBlack = 0;
00479         pX->pParent->isBlack = 1;
00480         rightRotate( pTree, pGrandparent );
00481 
00482       }else{
00483         /* This code is symetric to the illustrated case above. */
00484         if( pX == pX->pParent->pLeft ){
00485           pX = pX->pParent;
00486           rightRotate(pTree, pX);
00487         }
00488         assert( pGrandparent == pX->pParent->pParent );
00489         pGrandparent->isBlack = 0;
00490         pX->pParent->isBlack = 1;
00491         leftRotate( pTree, pGrandparent );
00492       }
00493     }
00494   }
00495   pTree->pHead->isBlack = 1;
00496 }
00497 
00498 /*
00499  * A child of pParent, which in turn had child pX, has just been removed from 
00500  * pTree (the figure below depicts the operation, Z is being removed). pParent
00501  * or pX, or both may be NULL.  
00502  *                |           |
00503  *                P           P
00504  *               / \         / \
00505  *              Z           X
00506  *             / \
00507  *            X  nil
00508  *
00509  * This function is only called if Z was black. In this case the red-black tree
00510  * properties have been violated, and pX has an "extra black". This function 
00511  * performs rotations and color-changes to re-balance the tree.
00512  */
00513 static 
00514 void do_delete_balancing(BtRbTree *pTree, BtRbNode *pX, BtRbNode *pParent)
00515 {
00516   BtRbNode *pSib; 
00517 
00518   /* TODO: Comment this code! */
00519   while( pX != pTree->pHead && (!pX || pX->isBlack) ){
00520     if( pX == pParent->pLeft ){
00521       pSib = pParent->pRight;
00522       if( pSib && !(pSib->isBlack) ){
00523         pSib->isBlack = 1;
00524         pParent->isBlack = 0;
00525         leftRotate(pTree, pParent);
00526         pSib = pParent->pRight;
00527       }
00528       if( !pSib ){
00529         pX = pParent;
00530       }else if( 
00531           (!pSib->pLeft  || pSib->pLeft->isBlack) &&
00532           (!pSib->pRight || pSib->pRight->isBlack) ) {
00533         pSib->isBlack = 0;
00534         pX = pParent;
00535       }else{
00536         if( (!pSib->pRight || pSib->pRight->isBlack) ){
00537           if( pSib->pLeft ) pSib->pLeft->isBlack = 1;
00538           pSib->isBlack = 0;
00539           rightRotate( pTree, pSib );
00540           pSib = pParent->pRight;
00541         }
00542         pSib->isBlack = pParent->isBlack;
00543         pParent->isBlack = 1;
00544         if( pSib->pRight ) pSib->pRight->isBlack = 1;
00545         leftRotate(pTree, pParent);
00546         pX = pTree->pHead;
00547       }
00548     }else{
00549       pSib = pParent->pLeft;
00550       if( pSib && !(pSib->isBlack) ){
00551         pSib->isBlack = 1;
00552         pParent->isBlack = 0;
00553         rightRotate(pTree, pParent);
00554         pSib = pParent->pLeft;
00555       }
00556       if( !pSib ){
00557         pX = pParent;
00558       }else if( 
00559           (!pSib->pLeft  || pSib->pLeft->isBlack) &&
00560           (!pSib->pRight || pSib->pRight->isBlack) ){
00561         pSib->isBlack = 0;
00562         pX = pParent;
00563       }else{
00564         if( (!pSib->pLeft || pSib->pLeft->isBlack) ){
00565           if( pSib->pRight ) pSib->pRight->isBlack = 1;
00566           pSib->isBlack = 0;
00567           leftRotate( pTree, pSib );
00568           pSib = pParent->pLeft;
00569         }
00570         pSib->isBlack = pParent->isBlack;
00571         pParent->isBlack = 1;
00572         if( pSib->pLeft ) pSib->pLeft->isBlack = 1;
00573         rightRotate(pTree, pParent);
00574         pX = pTree->pHead;
00575       }
00576     }
00577     pParent = pX->pParent;
00578   }
00579   if( pX ) pX->isBlack = 1;
00580 }
00581 
00582 /*
00583  * Create table n in tree pRbtree. Table n must not exist.
00584  */
00585 static void btreeCreateTable(Rbtree* pRbtree, int n)
00586 {
00587   BtRbTree *pNewTbl = sqliteMalloc(sizeof(BtRbTree));
00588   sqliteHashInsert(&pRbtree->tblHash, 0, n, pNewTbl);
00589 }
00590 
00591 /*
00592  * Log a single "rollback-op" for the given Rbtree. See comments for struct
00593  * BtRollbackOp.
00594  */
00595 static void btreeLogRollbackOp(Rbtree* pRbtree, BtRollbackOp *pRollbackOp)
00596 {
00597   assert( pRbtree->eTransState == TRANS_INCHECKPOINT ||
00598       pRbtree->eTransState == TRANS_INTRANSACTION );
00599   if( pRbtree->eTransState == TRANS_INTRANSACTION ){
00600     pRollbackOp->pNext = pRbtree->pTransRollback;
00601     pRbtree->pTransRollback = pRollbackOp;
00602   }
00603   if( pRbtree->eTransState == TRANS_INCHECKPOINT ){
00604     if( !pRbtree->pCheckRollback ){
00605       pRbtree->pCheckRollbackTail = pRollbackOp;
00606     }
00607     pRollbackOp->pNext = pRbtree->pCheckRollback;
00608     pRbtree->pCheckRollback = pRollbackOp;
00609   }
00610 }
00611 
00612 int sqliteRbtreeOpen(
00613   const char *zFilename,
00614   int mode,
00615   int nPg,
00616   Btree **ppBtree
00617 ){
00618   Rbtree **ppRbtree = (Rbtree**)ppBtree;
00619   *ppRbtree = (Rbtree *)sqliteMalloc(sizeof(Rbtree));
00620   if( sqlite_malloc_failed ) goto open_no_mem;
00621   sqliteHashInit(&(*ppRbtree)->tblHash, SQLITE_HASH_INT, 0);
00622 
00623   /* Create a binary tree for the SQLITE_MASTER table at location 2 */
00624   btreeCreateTable(*ppRbtree, 2);
00625   if( sqlite_malloc_failed ) goto open_no_mem;
00626   (*ppRbtree)->next_idx = 3;
00627   (*ppRbtree)->pOps = &sqliteRbtreeOps;
00628   /* Set file type to 4; this is so that "attach ':memory:' as ...."  does not
00629   ** think that the database in uninitialised and refuse to attach
00630   */
00631   (*ppRbtree)->aMetaData[2] = 4;
00632   
00633   return SQLITE_OK;
00634 
00635 open_no_mem:
00636   *ppBtree = 0;
00637   return SQLITE_NOMEM;
00638 }
00639 
00640 /*
00641  * Create a new table in the supplied Rbtree. Set *n to the new table number.
00642  * Return SQLITE_OK if the operation is a success.
00643  */
00644 static int memRbtreeCreateTable(Rbtree* tree, int* n)
00645 {
00646   assert( tree->eTransState != TRANS_NONE );
00647 
00648   *n = tree->next_idx++;
00649   btreeCreateTable(tree, *n);
00650   if( sqlite_malloc_failed ) return SQLITE_NOMEM;
00651 
00652   /* Set up the rollback structure (if we are not doing this as part of a
00653    * rollback) */
00654   if( tree->eTransState != TRANS_ROLLBACK ){
00655     BtRollbackOp *pRollbackOp = sqliteMalloc(sizeof(BtRollbackOp));
00656     if( pRollbackOp==0 ) return SQLITE_NOMEM;
00657     pRollbackOp->eOp = ROLLBACK_DROP;
00658     pRollbackOp->iTab = *n;
00659     btreeLogRollbackOp(tree, pRollbackOp);
00660   }
00661 
00662   return SQLITE_OK;
00663 }
00664 
00665 /*
00666  * Delete table n from the supplied Rbtree. 
00667  */
00668 static int memRbtreeDropTable(Rbtree* tree, int n)
00669 {
00670   BtRbTree *pTree;
00671   assert( tree->eTransState != TRANS_NONE );
00672 
00673   memRbtreeClearTable(tree, n);
00674   pTree = sqliteHashInsert(&tree->tblHash, 0, n, 0);
00675   assert(pTree);
00676   assert( pTree->pCursors==0 );
00677   sqliteFree(pTree);
00678 
00679   if( tree->eTransState != TRANS_ROLLBACK ){
00680     BtRollbackOp *pRollbackOp = sqliteMalloc(sizeof(BtRollbackOp));
00681     if( pRollbackOp==0 ) return SQLITE_NOMEM;
00682     pRollbackOp->eOp = ROLLBACK_CREATE;
00683     pRollbackOp->iTab = n;
00684     btreeLogRollbackOp(tree, pRollbackOp);
00685   }
00686 
00687   return SQLITE_OK;
00688 }
00689 
00690 static int memRbtreeKeyCompare(RbtCursor* pCur, const void *pKey, int nKey,
00691                                  int nIgnore, int *pRes)
00692 {
00693   assert(pCur);
00694 
00695   if( !pCur->pNode ) {
00696     *pRes = -1;
00697   } else {
00698     if( (pCur->pNode->nKey - nIgnore) < 0 ){
00699       *pRes = -1;
00700     }else{
00701       *pRes = key_compare(pCur->pNode->pKey, pCur->pNode->nKey-nIgnore, 
00702           pKey, nKey);
00703     }
00704   }
00705   return SQLITE_OK;
00706 }
00707 
00708 /*
00709  * Get a new cursor for table iTable of the supplied Rbtree. The wrFlag
00710  * parameter indicates that the cursor is open for writing.
00711  *
00712  * Note that RbtCursor.eSkip and RbtCursor.pNode both initialize to 0.
00713  */
00714 static int memRbtreeCursor(
00715   Rbtree* tree,
00716   int iTable,
00717   int wrFlag,
00718   RbtCursor **ppCur
00719 ){
00720   RbtCursor *pCur;
00721   assert(tree);
00722   pCur = *ppCur = sqliteMalloc(sizeof(RbtCursor));
00723   if( sqlite_malloc_failed ) return SQLITE_NOMEM;
00724   pCur->pTree  = sqliteHashFind(&tree->tblHash, 0, iTable);
00725   assert( pCur->pTree );
00726   pCur->pRbtree = tree;
00727   pCur->iTree  = iTable;
00728   pCur->pOps = &sqliteRbtreeCursorOps;
00729   pCur->wrFlag = wrFlag;
00730   pCur->pShared = pCur->pTree->pCursors;
00731   pCur->pTree->pCursors = pCur;
00732 
00733   assert( (*ppCur)->pTree );
00734   return SQLITE_OK;
00735 }
00736 
00737 /*
00738  * Insert a new record into the Rbtree.  The key is given by (pKey,nKey)
00739  * and the data is given by (pData,nData).  The cursor is used only to
00740  * define what database the record should be inserted into.  The cursor
00741  * is left pointing at the new record.
00742  *
00743  * If the key exists already in the tree, just replace the data. 
00744  */
00745 static int memRbtreeInsert(
00746   RbtCursor* pCur,
00747   const void *pKey,
00748   int nKey,
00749   const void *pDataInput,
00750   int nData
00751 ){
00752   void * pData;
00753   int match;
00754 
00755   /* It is illegal to call sqliteRbtreeInsert() if we are
00756   ** not in a transaction */
00757   assert( pCur->pRbtree->eTransState != TRANS_NONE );
00758 
00759   /* Make sure some other cursor isn't trying to read this same table */
00760   if( checkReadLocks(pCur) ){
00761     return SQLITE_LOCKED; /* The table pCur points to has a read lock */
00762   }
00763 
00764   /* Take a copy of the input data now, in case we need it for the 
00765    * replace case */
00766   pData = sqliteMallocRaw(nData);
00767   if( sqlite_malloc_failed ) return SQLITE_NOMEM;
00768   memcpy(pData, pDataInput, nData);
00769 
00770   /* Move the cursor to a node near the key to be inserted. If the key already
00771    * exists in the table, then (match == 0). In this case we can just replace
00772    * the data associated with the entry, we don't need to manipulate the tree.
00773    * 
00774    * If there is no exact match, then the cursor points at what would be either
00775    * the predecessor (match == -1) or successor (match == 1) of the
00776    * searched-for key, were it to be inserted. The new node becomes a child of
00777    * this node.
00778    * 
00779    * The new node is initially red.
00780    */
00781   memRbtreeMoveto( pCur, pKey, nKey, &match);
00782   if( match ){
00783     BtRbNode *pNode = sqliteMalloc(sizeof(BtRbNode));
00784     if( pNode==0 ) return SQLITE_NOMEM;
00785     pNode->nKey = nKey;
00786     pNode->pKey = sqliteMallocRaw(nKey);
00787     if( sqlite_malloc_failed ) return SQLITE_NOMEM;
00788     memcpy(pNode->pKey, pKey, nKey);
00789     pNode->nData = nData;
00790     pNode->pData = pData; 
00791     if( pCur->pNode ){
00792       switch( match ){
00793         case -1:
00794           assert( !pCur->pNode->pRight );
00795           pNode->pParent = pCur->pNode;
00796           pCur->pNode->pRight = pNode;
00797           break;
00798         case 1:
00799           assert( !pCur->pNode->pLeft );
00800           pNode->pParent = pCur->pNode;
00801           pCur->pNode->pLeft = pNode;
00802           break;
00803         default:
00804           assert(0);
00805       }
00806     }else{
00807       pCur->pTree->pHead = pNode;
00808     }
00809 
00810     /* Point the cursor at the node just inserted, as per SQLite requirements */
00811     pCur->pNode = pNode;
00812 
00813     /* A new node has just been inserted, so run the balancing code */
00814     do_insert_balancing(pCur->pTree, pNode);
00815 
00816     /* Set up a rollback-op in case we have to roll this operation back */
00817     if( pCur->pRbtree->eTransState != TRANS_ROLLBACK ){
00818       BtRollbackOp *pOp = sqliteMalloc( sizeof(BtRollbackOp) );
00819       if( pOp==0 ) return SQLITE_NOMEM;
00820       pOp->eOp = ROLLBACK_DELETE;
00821       pOp->iTab = pCur->iTree;
00822       pOp->nKey = pNode->nKey;
00823       pOp->pKey = sqliteMallocRaw( pOp->nKey );
00824       if( sqlite_malloc_failed ) return SQLITE_NOMEM;
00825       memcpy( pOp->pKey, pNode->pKey, pOp->nKey );
00826       btreeLogRollbackOp(pCur->pRbtree, pOp);
00827     }
00828 
00829   }else{ 
00830     /* No need to insert a new node in the tree, as the key already exists.
00831      * Just clobber the current nodes data. */
00832 
00833     /* Set up a rollback-op in case we have to roll this operation back */
00834     if( pCur->pRbtree->eTransState != TRANS_ROLLBACK ){
00835       BtRollbackOp *pOp = sqliteMalloc( sizeof(BtRollbackOp) );
00836       if( pOp==0 ) return SQLITE_NOMEM;
00837       pOp->iTab = pCur->iTree;
00838       pOp->nKey = pCur->pNode->nKey;
00839       pOp->pKey = sqliteMallocRaw( pOp->nKey );
00840       if( sqlite_malloc_failed ) return SQLITE_NOMEM;
00841       memcpy( pOp->pKey, pCur->pNode->pKey, pOp->nKey );
00842       pOp->nData = pCur->pNode->nData;
00843       pOp->pData = pCur->pNode->pData;
00844       pOp->eOp = ROLLBACK_INSERT;
00845       btreeLogRollbackOp(pCur->pRbtree, pOp);
00846     }else{
00847       sqliteFree( pCur->pNode->pData );
00848     }
00849 
00850     /* Actually clobber the nodes data */
00851     pCur->pNode->pData = pData;
00852     pCur->pNode->nData = nData;
00853   }
00854 
00855   return SQLITE_OK;
00856 }
00857 
00858 /* Move the cursor so that it points to an entry near pKey.
00859 ** Return a success code.
00860 **
00861 **     *pRes<0      The cursor is left pointing at an entry that
00862 **                  is smaller than pKey or if the table is empty
00863 **                  and the cursor is therefore left point to nothing.
00864 **
00865 **     *pRes==0     The cursor is left pointing at an entry that
00866 **                  exactly matches pKey.
00867 **
00868 **     *pRes>0      The cursor is left pointing at an entry that
00869 **                  is larger than pKey.
00870 */
00871 static int memRbtreeMoveto(
00872   RbtCursor* pCur,
00873   const void *pKey,
00874   int nKey,
00875   int *pRes
00876 ){
00877   BtRbNode *pTmp = 0;
00878 
00879   pCur->pNode = pCur->pTree->pHead;
00880   *pRes = -1;
00881   while( pCur->pNode && *pRes ) {
00882     *pRes = key_compare(pCur->pNode->pKey, pCur->pNode->nKey, pKey, nKey);
00883     pTmp = pCur->pNode;
00884     switch( *pRes ){
00885       case 1:    /* cursor > key */
00886         pCur->pNode = pCur->pNode->pLeft;
00887         break;
00888       case -1:   /* cursor < key */
00889         pCur->pNode = pCur->pNode->pRight;
00890         break;
00891     }
00892   } 
00893 
00894   /* If (pCur->pNode == NULL), then we have failed to find a match. Set
00895    * pCur->pNode to pTmp, which is either NULL (if the tree is empty) or the
00896    * last node traversed in the search. In either case the relation ship
00897    * between pTmp and the searched for key is already stored in *pRes. pTmp is
00898    * either the successor or predecessor of the key we tried to move to. */
00899   if( !pCur->pNode ) pCur->pNode = pTmp;
00900   pCur->eSkip = SKIP_NONE;
00901 
00902   return SQLITE_OK;
00903 }
00904 
00905 
00906 /*
00907 ** Delete the entry that the cursor is pointing to.
00908 **
00909 ** The cursor is left pointing at either the next or the previous
00910 ** entry.  If the cursor is left pointing to the next entry, then 
00911 ** the pCur->eSkip flag is set to SKIP_NEXT which forces the next call to 
00912 ** sqliteRbtreeNext() to be a no-op.  That way, you can always call
00913 ** sqliteRbtreeNext() after a delete and the cursor will be left
00914 ** pointing to the first entry after the deleted entry.  Similarly,
00915 ** pCur->eSkip is set to SKIP_PREV is the cursor is left pointing to
00916 ** the entry prior to the deleted entry so that a subsequent call to
00917 ** sqliteRbtreePrevious() will always leave the cursor pointing at the
00918 ** entry immediately before the one that was deleted.
00919 */
00920 static int memRbtreeDelete(RbtCursor* pCur)
00921 {
00922   BtRbNode *pZ;      /* The one being deleted */
00923   BtRbNode *pChild;  /* The child of the spliced out node */
00924 
00925   /* It is illegal to call sqliteRbtreeDelete() if we are
00926   ** not in a transaction */
00927   assert( pCur->pRbtree->eTransState != TRANS_NONE );
00928 
00929   /* Make sure some other cursor isn't trying to read this same table */
00930   if( checkReadLocks(pCur) ){
00931     return SQLITE_LOCKED; /* The table pCur points to has a read lock */
00932   }
00933 
00934   pZ = pCur->pNode;
00935   if( !pZ ){
00936     return SQLITE_OK;
00937   }
00938 
00939   /* If we are not currently doing a rollback, set up a rollback op for this 
00940    * deletion */
00941   if( pCur->pRbtree->eTransState != TRANS_ROLLBACK ){
00942     BtRollbackOp *pOp = sqliteMalloc( sizeof(BtRollbackOp) );
00943     if( pOp==0 ) return SQLITE_NOMEM;
00944     pOp->iTab = pCur->iTree;
00945     pOp->nKey = pZ->nKey;
00946     pOp->pKey = pZ->pKey;
00947     pOp->nData = pZ->nData;
00948     pOp->pData = pZ->pData;
00949     pOp->eOp = ROLLBACK_INSERT;
00950     btreeLogRollbackOp(pCur->pRbtree, pOp);
00951   }
00952 
00953   /* First do a standard binary-tree delete (node pZ is to be deleted). How
00954    * to do this depends on how many children pZ has:
00955    *
00956    * If pZ has no children or one child, then splice out pZ.  If pZ has two
00957    * children, splice out the successor of pZ and replace the key and data of
00958    * pZ with the key and data of the spliced out successor.  */
00959   if( pZ->pLeft && pZ->pRight ){
00960     BtRbNode *pTmp;
00961     int dummy;
00962     pCur->eSkip = SKIP_NONE;
00963     memRbtreeNext(pCur, &dummy);
00964     assert( dummy == 0 );
00965     if( pCur->pRbtree->eTransState == TRANS_ROLLBACK ){
00966       sqliteFree(pZ->pKey);
00967       sqliteFree(pZ->pData);
00968     }
00969     pZ->pData = pCur->pNode->pData;
00970     pZ->nData = pCur->pNode->nData;
00971     pZ->pKey = pCur->pNode->pKey;
00972     pZ->nKey = pCur->pNode->nKey;
00973     pTmp = pZ;
00974     pZ = pCur->pNode;
00975     pCur->pNode = pTmp;
00976     pCur->eSkip = SKIP_NEXT;
00977   }else{
00978     int res;
00979     pCur->eSkip = SKIP_NONE;
00980     memRbtreeNext(pCur, &res);
00981     pCur->eSkip = SKIP_NEXT;
00982     if( res ){
00983       memRbtreeLast(pCur, &res);
00984       memRbtreePrevious(pCur, &res);
00985       pCur->eSkip = SKIP_PREV;
00986     }
00987     if( pCur->pRbtree->eTransState == TRANS_ROLLBACK ){
00988         sqliteFree(pZ->pKey);
00989         sqliteFree(pZ->pData);
00990     }
00991   }
00992 
00993   /* pZ now points at the node to be spliced out. This block does the 
00994    * splicing. */
00995   {
00996     BtRbNode **ppParentSlot = 0;
00997     assert( !pZ->pLeft || !pZ->pRight ); /* pZ has at most one child */
00998     pChild = ((pZ->pLeft)?pZ->pLeft:pZ->pRight);
00999     if( pZ->pParent ){
01000       assert( pZ == pZ->pParent->pLeft || pZ == pZ->pParent->pRight );
01001       ppParentSlot = ((pZ == pZ->pParent->pLeft)
01002           ?&pZ->pParent->pLeft:&pZ->pParent->pRight);
01003       *ppParentSlot = pChild;
01004     }else{
01005       pCur->pTree->pHead = pChild;
01006     }
01007     if( pChild ) pChild->pParent = pZ->pParent;
01008   }
01009 
01010   /* pZ now points at the spliced out node. pChild is the only child of pZ, or
01011    * NULL if pZ has no children. If pZ is black, and not the tree root, then we
01012    * will have violated the "same number of black nodes in every path to a
01013    * leaf" property of the red-black tree. The code in do_delete_balancing()
01014    * repairs this. */
01015   if( pZ->isBlack ){ 
01016     do_delete_balancing(pCur->pTree, pChild, pZ->pParent);
01017   }
01018 
01019   sqliteFree(pZ);
01020   return SQLITE_OK;
01021 }
01022 
01023 /*
01024  * Empty table n of the Rbtree.
01025  */
01026 static int memRbtreeClearTable(Rbtree* tree, int n)
01027 {
01028   BtRbTree *pTree;
01029   BtRbNode *pNode;
01030 
01031   pTree = sqliteHashFind(&tree->tblHash, 0, n);
01032   assert(pTree);
01033 
01034   pNode = pTree->pHead;
01035   while( pNode ){
01036     if( pNode->pLeft ){
01037       pNode = pNode->pLeft;
01038     }
01039     else if( pNode->pRight ){
01040       pNode = pNode->pRight;
01041     }
01042     else {
01043       BtRbNode *pTmp = pNode->pParent;
01044       if( tree->eTransState == TRANS_ROLLBACK ){
01045         sqliteFree( pNode->pKey );
01046         sqliteFree( pNode->pData );
01047       }else{
01048         BtRollbackOp *pRollbackOp = sqliteMallocRaw(sizeof(BtRollbackOp));
01049         if( pRollbackOp==0 ) return SQLITE_NOMEM;
01050         pRollbackOp->eOp = ROLLBACK_INSERT;
01051         pRollbackOp->iTab = n;
01052         pRollbackOp->nKey = pNode->nKey;
01053         pRollbackOp->pKey = pNode->pKey;
01054         pRollbackOp->nData = pNode->nData;
01055         pRollbackOp->pData = pNode->pData;
01056         btreeLogRollbackOp(tree, pRollbackOp);
01057       }
01058       sqliteFree( pNode );
01059       if( pTmp ){
01060         if( pTmp->pLeft == pNode ) pTmp->pLeft = 0;
01061         else if( pTmp->pRight == pNode ) pTmp->pRight = 0;
01062       }
01063       pNode = pTmp;
01064     }
01065   }
01066 
01067   pTree->pHead = 0;
01068   return SQLITE_OK;
01069 }
01070 
01071 static int memRbtreeFirst(RbtCursor* pCur, int *pRes)
01072 {
01073   if( pCur->pTree->pHead ){
01074     pCur->pNode = pCur->pTree->pHead;
01075     while( pCur->pNode->pLeft ){
01076       pCur->pNode = pCur->pNode->pLeft;
01077     }
01078   }
01079   if( pCur->pNode ){
01080     *pRes = 0;
01081   }else{
01082     *pRes = 1;
01083   }
01084   pCur->eSkip = SKIP_NONE;
01085   return SQLITE_OK;
01086 }
01087 
01088 static int memRbtreeLast(RbtCursor* pCur, int *pRes)
01089 {
01090   if( pCur->pTree->pHead ){
01091     pCur->pNode = pCur->pTree->pHead;
01092     while( pCur->pNode->pRight ){
01093       pCur->pNode = pCur->pNode->pRight;
01094     }
01095   }
01096   if( pCur->pNode ){
01097     *pRes = 0;
01098   }else{
01099     *pRes = 1;
01100   }
01101   pCur->eSkip = SKIP_NONE;
01102   return SQLITE_OK;
01103 }
01104 
01105 /*
01106 ** Advance the cursor to the next entry in the database.  If
01107 ** successful then set *pRes=0.  If the cursor
01108 ** was already pointing to the last entry in the database before
01109 ** this routine was called, then set *pRes=1.
01110 */
01111 static int memRbtreeNext(RbtCursor* pCur, int *pRes)
01112 {
01113   if( pCur->pNode && pCur->eSkip != SKIP_NEXT ){
01114     if( pCur->pNode->pRight ){
01115       pCur->pNode = pCur->pNode->pRight;
01116       while( pCur->pNode->pLeft )
01117         pCur->pNode = pCur->pNode->pLeft;
01118     }else{
01119       BtRbNode * pX = pCur->pNode;
01120       pCur->pNode = pX->pParent;
01121       while( pCur->pNode && (pCur->pNode->pRight == pX) ){
01122         pX = pCur->pNode;
01123         pCur->pNode = pX->pParent;
01124       }
01125     }
01126   }
01127   pCur->eSkip = SKIP_NONE;
01128 
01129   if( !pCur->pNode ){
01130     *pRes = 1;
01131   }else{
01132     *pRes = 0;
01133   }
01134 
01135   return SQLITE_OK;
01136 }
01137 
01138 static int memRbtreePrevious(RbtCursor* pCur, int *pRes)
01139 {
01140   if( pCur->pNode && pCur->eSkip != SKIP_PREV ){
01141     if( pCur->pNode->pLeft ){
01142       pCur->pNode = pCur->pNode->pLeft;
01143       while( pCur->pNode->pRight )
01144         pCur->pNode = pCur->pNode->pRight;
01145     }else{
01146       BtRbNode * pX = pCur->pNode;
01147       pCur->pNode = pX->pParent;
01148       while( pCur->pNode && (pCur->pNode->pLeft == pX) ){
01149         pX = pCur->pNode;
01150         pCur->pNode = pX->pParent;
01151       }
01152     }
01153   }
01154   pCur->eSkip = SKIP_NONE;
01155 
01156   if( !pCur->pNode ){
01157     *pRes = 1;
01158   }else{
01159     *pRes = 0;
01160   }
01161 
01162   return SQLITE_OK;
01163 }
01164 
01165 static int memRbtreeKeySize(RbtCursor* pCur, int *pSize)
01166 {
01167   if( pCur->pNode ){
01168     *pSize = pCur->pNode->nKey;
01169   }else{
01170     *pSize = 0;
01171   }
01172   return SQLITE_OK;
01173 }
01174 
01175 static int memRbtreeKey(RbtCursor* pCur, int offset, int amt, char *zBuf)
01176 {
01177   if( !pCur->pNode ) return 0;
01178   if( !pCur->pNode->pKey || ((amt + offset) <= pCur->pNode->nKey) ){
01179     memcpy(zBuf, ((char*)pCur->pNode->pKey)+offset, amt);
01180   }else{
01181     memcpy(zBuf, ((char*)pCur->pNode->pKey)+offset, pCur->pNode->nKey-offset);
01182     amt = pCur->pNode->nKey-offset;
01183   }
01184   return amt;
01185 }
01186 
01187 static int memRbtreeDataSize(RbtCursor* pCur, int *pSize)
01188 {
01189   if( pCur->pNode ){
01190     *pSize = pCur->pNode->nData;
01191   }else{
01192     *pSize = 0;
01193   }
01194   return SQLITE_OK;
01195 }
01196 
01197 static int memRbtreeData(RbtCursor *pCur, int offset, int amt, char *zBuf)
01198 {
01199   if( !pCur->pNode ) return 0;
01200   if( (amt + offset) <= pCur->pNode->nData ){
01201     memcpy(zBuf, ((char*)pCur->pNode->pData)+offset, amt);
01202   }else{
01203     memcpy(zBuf, ((char*)pCur->pNode->pData)+offset ,pCur->pNode->nData-offset);
01204     amt = pCur->pNode->nData-offset;
01205   }
01206   return amt;
01207 }
01208 
01209 static int memRbtreeCloseCursor(RbtCursor* pCur)
01210 {
01211   if( pCur->pTree->pCursors==pCur ){
01212     pCur->pTree->pCursors = pCur->pShared;
01213   }else{
01214     RbtCursor *p = pCur->pTree->pCursors;
01215     while( p && p->pShared!=pCur ){ p = p->pShared; }
01216     assert( p!=0 );
01217     if( p ){
01218       p->pShared = pCur->pShared;
01219     }
01220   }
01221   sqliteFree(pCur);
01222   return SQLITE_OK;
01223 }
01224 
01225 static int memRbtreeGetMeta(Rbtree* tree, int* aMeta)
01226 {
01227   memcpy( aMeta, tree->aMetaData, sizeof(int) * SQLITE_N_BTREE_META );
01228   return SQLITE_OK;
01229 }
01230 
01231 static int memRbtreeUpdateMeta(Rbtree* tree, int* aMeta)
01232 {
01233   memcpy( tree->aMetaData, aMeta, sizeof(int) * SQLITE_N_BTREE_META );
01234   return SQLITE_OK;
01235 }
01236 
01237 /*
01238  * Check that each table in the Rbtree meets the requirements for a red-black
01239  * binary tree. If an error is found, return an explanation of the problem in 
01240  * memory obtained from sqliteMalloc(). Parameters aRoot and nRoot are ignored. 
01241  */
01242 static char *memRbtreeIntegrityCheck(Rbtree* tree, int* aRoot, int nRoot)
01243 {
01244   char * msg = 0;
01245   HashElem *p;
01246 
01247   for(p=sqliteHashFirst(&tree->tblHash); p; p=sqliteHashNext(p)){
01248     BtRbTree *pTree = sqliteHashData(p);
01249     check_redblack_tree(pTree, &msg);
01250   }
01251 
01252   return msg;
01253 }
01254 
01255 static int memRbtreeSetCacheSize(Rbtree* tree, int sz)
01256 {
01257   return SQLITE_OK;
01258 }
01259 
01260 static int memRbtreeSetSafetyLevel(Rbtree *pBt, int level){
01261   return SQLITE_OK;
01262 }
01263 
01264 static int memRbtreeBeginTrans(Rbtree* tree)
01265 {
01266   if( tree->eTransState != TRANS_NONE ) 
01267     return SQLITE_ERROR;
01268 
01269   assert( tree->pTransRollback == 0 );
01270   tree->eTransState = TRANS_INTRANSACTION;
01271   return SQLITE_OK;
01272 }
01273 
01274 /*
01275 ** Delete a linked list of BtRollbackOp structures.
01276 */
01277 static void deleteRollbackList(BtRollbackOp *pOp){
01278   while( pOp ){
01279     BtRollbackOp *pTmp = pOp->pNext;
01280     sqliteFree(pOp->pData);
01281     sqliteFree(pOp->pKey);
01282     sqliteFree(pOp);
01283     pOp = pTmp;
01284   }
01285 }
01286 
01287 static int memRbtreeCommit(Rbtree* tree){
01288   /* Just delete pTransRollback and pCheckRollback */
01289   deleteRollbackList(tree->pCheckRollback);
01290   deleteRollbackList(tree->pTransRollback);
01291   tree->pTransRollback = 0;
01292   tree->pCheckRollback = 0;
01293   tree->pCheckRollbackTail = 0;
01294   tree->eTransState = TRANS_NONE;
01295   return SQLITE_OK;
01296 }
01297 
01298 /*
01299  * Close the supplied Rbtree. Delete everything associated with it.
01300  */
01301 static int memRbtreeClose(Rbtree* tree)
01302 {
01303   HashElem *p;
01304   memRbtreeCommit(tree);
01305   while( (p=sqliteHashFirst(&tree->tblHash))!=0 ){
01306     tree->eTransState = TRANS_ROLLBACK;
01307     memRbtreeDropTable(tree, sqliteHashKeysize(p));
01308   }
01309   sqliteHashClear(&tree->tblHash);
01310   sqliteFree(tree);
01311   return SQLITE_OK;
01312 }
01313 
01314 /*
01315  * Execute and delete the supplied rollback-list on pRbtree.
01316  */
01317 static void execute_rollback_list(Rbtree *pRbtree, BtRollbackOp *pList)
01318 {
01319   BtRollbackOp *pTmp;
01320   RbtCursor cur;
01321   int res;
01322 
01323   cur.pRbtree = pRbtree;
01324   cur.wrFlag = 1;
01325   while( pList ){
01326     switch( pList->eOp ){
01327       case ROLLBACK_INSERT:
01328         cur.pTree  = sqliteHashFind( &pRbtree->tblHash, 0, pList->iTab );
01329         assert(cur.pTree);
01330         cur.iTree  = pList->iTab;
01331         cur.eSkip  = SKIP_NONE;
01332         memRbtreeInsert( &cur, pList->pKey,
01333             pList->nKey, pList->pData, pList->nData );
01334         break;
01335       case ROLLBACK_DELETE:
01336         cur.pTree  = sqliteHashFind( &pRbtree->tblHash, 0, pList->iTab );
01337         assert(cur.pTree);
01338         cur.iTree  = pList->iTab;
01339         cur.eSkip  = SKIP_NONE;
01340         memRbtreeMoveto(&cur, pList->pKey, pList->nKey, &res);
01341         assert(res == 0);
01342         memRbtreeDelete( &cur );
01343         break;
01344       case ROLLBACK_CREATE:
01345         btreeCreateTable(pRbtree, pList->iTab);
01346         break;
01347       case ROLLBACK_DROP:
01348         memRbtreeDropTable(pRbtree, pList->iTab);
01349         break;
01350       default:
01351         assert(0);
01352     }
01353     sqliteFree(pList->pKey);
01354     sqliteFree(pList->pData);
01355     pTmp = pList->pNext;
01356     sqliteFree(pList);
01357     pList = pTmp;
01358   }
01359 }
01360 
01361 static int memRbtreeRollback(Rbtree* tree)
01362 {
01363   tree->eTransState = TRANS_ROLLBACK;
01364   execute_rollback_list(tree, tree->pCheckRollback);
01365   execute_rollback_list(tree, tree->pTransRollback);
01366   tree->pTransRollback = 0;
01367   tree->pCheckRollback = 0;
01368   tree->pCheckRollbackTail = 0;
01369   tree->eTransState = TRANS_NONE;
01370   return SQLITE_OK;
01371 }
01372 
01373 static int memRbtreeBeginCkpt(Rbtree* tree)
01374 {
01375   if( tree->eTransState != TRANS_INTRANSACTION ) 
01376     return SQLITE_ERROR;
01377 
01378   assert( tree->pCheckRollback == 0 );
01379   assert( tree->pCheckRollbackTail == 0 );
01380   tree->eTransState = TRANS_INCHECKPOINT;
01381   return SQLITE_OK;
01382 }
01383 
01384 static int memRbtreeCommitCkpt(Rbtree* tree)
01385 {
01386   if( tree->eTransState == TRANS_INCHECKPOINT ){ 
01387     if( tree->pCheckRollback ){
01388       tree->pCheckRollbackTail->pNext = tree->pTransRollback;
01389       tree->pTransRollback = tree->pCheckRollback;
01390       tree->pCheckRollback = 0;
01391       tree->pCheckRollbackTail = 0;
01392     }
01393     tree->eTransState = TRANS_INTRANSACTION;
01394   }
01395   return SQLITE_OK;
01396 }
01397 
01398 static int memRbtreeRollbackCkpt(Rbtree* tree)
01399 {
01400   if( tree->eTransState != TRANS_INCHECKPOINT ) return SQLITE_OK;
01401   tree->eTransState = TRANS_ROLLBACK;
01402   execute_rollback_list(tree, tree->pCheckRollback);
01403   tree->pCheckRollback = 0;
01404   tree->pCheckRollbackTail = 0;
01405   tree->eTransState = TRANS_INTRANSACTION;
01406   return SQLITE_OK;
01407 }
01408 
01409 #ifdef SQLITE_TEST
01410 static int memRbtreePageDump(Rbtree* tree, int pgno, int rec)
01411 {
01412   assert(!"Cannot call sqliteRbtreePageDump");
01413   return SQLITE_OK;
01414 }
01415 
01416 static int memRbtreeCursorDump(RbtCursor* pCur, int* aRes)
01417 {
01418   assert(!"Cannot call sqliteRbtreeCursorDump");
01419   return SQLITE_OK;
01420 }
01421 #endif
01422 
01423 static struct Pager *memRbtreePager(Rbtree* tree)
01424 {
01425   return 0;
01426 }
01427 
01428 /*
01429 ** Return the full pathname of the underlying database file.
01430 */
01431 static const char *memRbtreeGetFilename(Rbtree *pBt){
01432   return 0;  /* A NULL return indicates there is no underlying file */
01433 }
01434 
01435 /*
01436 ** The copy file function is not implemented for the in-memory database
01437 */
01438 static int memRbtreeCopyFile(Rbtree *pBt, Rbtree *pBt2){
01439   return SQLITE_INTERNAL;  /* Not implemented */
01440 }
01441 
01442 static BtOps sqliteRbtreeOps = {
01443     (int(*)(Btree*)) memRbtreeClose,
01444     (int(*)(Btree*,int)) memRbtreeSetCacheSize,
01445     (int(*)(Btree*,int)) memRbtreeSetSafetyLevel,
01446     (int(*)(Btree*)) memRbtreeBeginTrans,
01447     (int(*)(Btree*)) memRbtreeCommit,
01448     (int(*)(Btree*)) memRbtreeRollback,
01449     (int(*)(Btree*)) memRbtreeBeginCkpt,
01450     (int(*)(Btree*)) memRbtreeCommitCkpt,
01451     (int(*)(Btree*)) memRbtreeRollbackCkpt,
01452     (int(*)(Btree*,int*)) memRbtreeCreateTable,
01453     (int(*)(Btree*,int*)) memRbtreeCreateTable,
01454     (int(*)(Btree*,int)) memRbtreeDropTable,
01455     (int(*)(Btree*,int)) memRbtreeClearTable,
01456     (int(*)(Btree*,int,int,BtCursor**)) memRbtreeCursor,
01457     (int(*)(Btree*,int*)) memRbtreeGetMeta,
01458     (int(*)(Btree*,int*)) memRbtreeUpdateMeta,
01459     (char*(*)(Btree*,int*,int)) memRbtreeIntegrityCheck,
01460     (const char*(*)(Btree*)) memRbtreeGetFilename,
01461     (int(*)(Btree*,Btree*)) memRbtreeCopyFile,
01462     (struct Pager*(*)(Btree*)) memRbtreePager,
01463 #ifdef SQLITE_TEST
01464     (int(*)(Btree*,int,int)) memRbtreePageDump,
01465 #endif
01466 };
01467 
01468 static BtCursorOps sqliteRbtreeCursorOps = {
01469     (int(*)(BtCursor*,const void*,int,int*)) memRbtreeMoveto,
01470     (int(*)(BtCursor*)) memRbtreeDelete,
01471     (int(*)(BtCursor*,const void*,int,const void*,int)) memRbtreeInsert,
01472     (int(*)(BtCursor*,int*)) memRbtreeFirst,
01473     (int(*)(BtCursor*,int*)) memRbtreeLast,
01474     (int(*)(BtCursor*,int*)) memRbtreeNext,
01475     (int(*)(BtCursor*,int*)) memRbtreePrevious,
01476     (int(*)(BtCursor*,int*)) memRbtreeKeySize,
01477     (int(*)(BtCursor*,int,int,char*)) memRbtreeKey,
01478     (int(*)(BtCursor*,const void*,int,int,int*)) memRbtreeKeyCompare,
01479     (int(*)(BtCursor*,int*)) memRbtreeDataSize,
01480     (int(*)(BtCursor*,int,int,char*)) memRbtreeData,
01481     (int(*)(BtCursor*)) memRbtreeCloseCursor,
01482 #ifdef SQLITE_TEST
01483     (int(*)(BtCursor*,int*)) memRbtreeCursorDump,
01484 #endif
01485 
01486 };
01487 
01488 #endif /* SQLITE_OMIT_INMEMORYDB */