17c478bd9Sstevel@tonic-gate /*
27c478bd9Sstevel@tonic-gate ** 2003 Feb 4
37c478bd9Sstevel@tonic-gate **
47c478bd9Sstevel@tonic-gate ** The author disclaims copyright to this source code. In place of
57c478bd9Sstevel@tonic-gate ** a legal notice, here is a blessing:
67c478bd9Sstevel@tonic-gate **
77c478bd9Sstevel@tonic-gate ** May you do good and not evil.
87c478bd9Sstevel@tonic-gate ** May you find forgiveness for yourself and forgive others.
97c478bd9Sstevel@tonic-gate ** May you share freely, never taking more than you give.
107c478bd9Sstevel@tonic-gate **
117c478bd9Sstevel@tonic-gate *************************************************************************
127c478bd9Sstevel@tonic-gate ** $Id: btree_rb.c,v 1.24.2.1 2004/06/26 14:40:05 drh Exp $
137c478bd9Sstevel@tonic-gate **
147c478bd9Sstevel@tonic-gate ** This file implements an in-core database using Red-Black balanced
157c478bd9Sstevel@tonic-gate ** binary trees.
16*1da57d55SToomas Soome **
177c478bd9Sstevel@tonic-gate ** It was contributed to SQLite by anonymous on 2003-Feb-04 23:24:49 UTC.
187c478bd9Sstevel@tonic-gate */
197c478bd9Sstevel@tonic-gate #include "btree.h"
207c478bd9Sstevel@tonic-gate #include "sqliteInt.h"
217c478bd9Sstevel@tonic-gate #include <assert.h>
227c478bd9Sstevel@tonic-gate
237c478bd9Sstevel@tonic-gate /*
247c478bd9Sstevel@tonic-gate ** Omit this whole file if the SQLITE_OMIT_INMEMORYDB macro is
257c478bd9Sstevel@tonic-gate ** defined. This allows a lot of code to be omitted for installations
267c478bd9Sstevel@tonic-gate ** that do not need it.
277c478bd9Sstevel@tonic-gate */
287c478bd9Sstevel@tonic-gate #ifndef SQLITE_OMIT_INMEMORYDB
297c478bd9Sstevel@tonic-gate
307c478bd9Sstevel@tonic-gate
317c478bd9Sstevel@tonic-gate typedef struct BtRbTree BtRbTree;
327c478bd9Sstevel@tonic-gate typedef struct BtRbNode BtRbNode;
337c478bd9Sstevel@tonic-gate typedef struct BtRollbackOp BtRollbackOp;
347c478bd9Sstevel@tonic-gate typedef struct Rbtree Rbtree;
357c478bd9Sstevel@tonic-gate typedef struct RbtCursor RbtCursor;
367c478bd9Sstevel@tonic-gate
377c478bd9Sstevel@tonic-gate /* Forward declarations */
387c478bd9Sstevel@tonic-gate static BtOps sqliteRbtreeOps;
397c478bd9Sstevel@tonic-gate static BtCursorOps sqliteRbtreeCursorOps;
407c478bd9Sstevel@tonic-gate
417c478bd9Sstevel@tonic-gate /*
427c478bd9Sstevel@tonic-gate * During each transaction (or checkpoint), a linked-list of
437c478bd9Sstevel@tonic-gate * "rollback-operations" is accumulated. If the transaction is rolled back,
447c478bd9Sstevel@tonic-gate * then the list of operations must be executed (to restore the database to
457c478bd9Sstevel@tonic-gate * it's state before the transaction started). If the transaction is to be
467c478bd9Sstevel@tonic-gate * committed, just delete the list.
477c478bd9Sstevel@tonic-gate *
487c478bd9Sstevel@tonic-gate * Each operation is represented as follows, depending on the value of eOp:
497c478bd9Sstevel@tonic-gate *
507c478bd9Sstevel@tonic-gate * ROLLBACK_INSERT -> Need to insert (pKey, pData) into table iTab.
517c478bd9Sstevel@tonic-gate * ROLLBACK_DELETE -> Need to delete the record (pKey) into table iTab.
527c478bd9Sstevel@tonic-gate * ROLLBACK_CREATE -> Need to create table iTab.
537c478bd9Sstevel@tonic-gate * ROLLBACK_DROP -> Need to drop table iTab.
547c478bd9Sstevel@tonic-gate */
557c478bd9Sstevel@tonic-gate struct BtRollbackOp {
567c478bd9Sstevel@tonic-gate u8 eOp;
577c478bd9Sstevel@tonic-gate int iTab;
58*1da57d55SToomas Soome int nKey;
597c478bd9Sstevel@tonic-gate void *pKey;
607c478bd9Sstevel@tonic-gate int nData;
617c478bd9Sstevel@tonic-gate void *pData;
627c478bd9Sstevel@tonic-gate BtRollbackOp *pNext;
637c478bd9Sstevel@tonic-gate };
647c478bd9Sstevel@tonic-gate
657c478bd9Sstevel@tonic-gate /*
667c478bd9Sstevel@tonic-gate ** Legal values for BtRollbackOp.eOp:
677c478bd9Sstevel@tonic-gate */
687c478bd9Sstevel@tonic-gate #define ROLLBACK_INSERT 1 /* Insert a record */
697c478bd9Sstevel@tonic-gate #define ROLLBACK_DELETE 2 /* Delete a record */
707c478bd9Sstevel@tonic-gate #define ROLLBACK_CREATE 3 /* Create a table */
717c478bd9Sstevel@tonic-gate #define ROLLBACK_DROP 4 /* Drop a table */
727c478bd9Sstevel@tonic-gate
737c478bd9Sstevel@tonic-gate struct Rbtree {
747c478bd9Sstevel@tonic-gate BtOps *pOps; /* Function table */
757c478bd9Sstevel@tonic-gate int aMetaData[SQLITE_N_BTREE_META];
767c478bd9Sstevel@tonic-gate
777c478bd9Sstevel@tonic-gate int next_idx; /* next available table index */
787c478bd9Sstevel@tonic-gate Hash tblHash; /* All created tables, by index */
797c478bd9Sstevel@tonic-gate u8 isAnonymous; /* True if this Rbtree is to be deleted when closed */
807c478bd9Sstevel@tonic-gate u8 eTransState; /* State of this Rbtree wrt transactions */
817c478bd9Sstevel@tonic-gate
82*1da57d55SToomas Soome BtRollbackOp *pTransRollback;
837c478bd9Sstevel@tonic-gate BtRollbackOp *pCheckRollback;
847c478bd9Sstevel@tonic-gate BtRollbackOp *pCheckRollbackTail;
857c478bd9Sstevel@tonic-gate };
867c478bd9Sstevel@tonic-gate
877c478bd9Sstevel@tonic-gate /*
887c478bd9Sstevel@tonic-gate ** Legal values for Rbtree.eTransState.
897c478bd9Sstevel@tonic-gate */
907c478bd9Sstevel@tonic-gate #define TRANS_NONE 0 /* No transaction is in progress */
917c478bd9Sstevel@tonic-gate #define TRANS_INTRANSACTION 1 /* A transaction is in progress */
927c478bd9Sstevel@tonic-gate #define TRANS_INCHECKPOINT 2 /* A checkpoint is in progress */
937c478bd9Sstevel@tonic-gate #define TRANS_ROLLBACK 3 /* We are currently rolling back a checkpoint or
947c478bd9Sstevel@tonic-gate * transaction. */
957c478bd9Sstevel@tonic-gate
967c478bd9Sstevel@tonic-gate struct RbtCursor {
977c478bd9Sstevel@tonic-gate BtCursorOps *pOps; /* Function table */
987c478bd9Sstevel@tonic-gate Rbtree *pRbtree;
997c478bd9Sstevel@tonic-gate BtRbTree *pTree;
1007c478bd9Sstevel@tonic-gate int iTree; /* Index of pTree in pRbtree */
1017c478bd9Sstevel@tonic-gate BtRbNode *pNode;
1027c478bd9Sstevel@tonic-gate RbtCursor *pShared; /* List of all cursors on the same Rbtree */
1037c478bd9Sstevel@tonic-gate u8 eSkip; /* Determines if next step operation is a no-op */
1047c478bd9Sstevel@tonic-gate u8 wrFlag; /* True if this cursor is open for writing */
1057c478bd9Sstevel@tonic-gate };
1067c478bd9Sstevel@tonic-gate
1077c478bd9Sstevel@tonic-gate /*
1087c478bd9Sstevel@tonic-gate ** Legal values for RbtCursor.eSkip.
1097c478bd9Sstevel@tonic-gate */
1107c478bd9Sstevel@tonic-gate #define SKIP_NONE 0 /* Always step the cursor */
1117c478bd9Sstevel@tonic-gate #define SKIP_NEXT 1 /* The next sqliteRbtreeNext() is a no-op */
1127c478bd9Sstevel@tonic-gate #define SKIP_PREV 2 /* The next sqliteRbtreePrevious() is a no-op */
1137c478bd9Sstevel@tonic-gate #define SKIP_INVALID 3 /* Calls to Next() and Previous() are invalid */
1147c478bd9Sstevel@tonic-gate
1157c478bd9Sstevel@tonic-gate struct BtRbTree {
1167c478bd9Sstevel@tonic-gate RbtCursor *pCursors; /* All cursors pointing to this tree */
1177c478bd9Sstevel@tonic-gate BtRbNode *pHead; /* Head of the tree, or NULL */
1187c478bd9Sstevel@tonic-gate };
1197c478bd9Sstevel@tonic-gate
1207c478bd9Sstevel@tonic-gate struct BtRbNode {
1217c478bd9Sstevel@tonic-gate int nKey;
1227c478bd9Sstevel@tonic-gate void *pKey;
1237c478bd9Sstevel@tonic-gate int nData;
1247c478bd9Sstevel@tonic-gate void *pData;
1257c478bd9Sstevel@tonic-gate u8 isBlack; /* true for a black node, 0 for a red node */
1267c478bd9Sstevel@tonic-gate BtRbNode *pParent; /* Nodes parent node, NULL for the tree head */
1277c478bd9Sstevel@tonic-gate BtRbNode *pLeft; /* Nodes left child, or NULL */
1287c478bd9Sstevel@tonic-gate BtRbNode *pRight; /* Nodes right child, or NULL */
1297c478bd9Sstevel@tonic-gate
1307c478bd9Sstevel@tonic-gate int nBlackHeight; /* Only used during the red-black integrity check */
1317c478bd9Sstevel@tonic-gate };
1327c478bd9Sstevel@tonic-gate
1337c478bd9Sstevel@tonic-gate /* Forward declarations */
1347c478bd9Sstevel@tonic-gate static int memRbtreeMoveto(
1357c478bd9Sstevel@tonic-gate RbtCursor* pCur,
1367c478bd9Sstevel@tonic-gate const void *pKey,
1377c478bd9Sstevel@tonic-gate int nKey,
1387c478bd9Sstevel@tonic-gate int *pRes
1397c478bd9Sstevel@tonic-gate );
1407c478bd9Sstevel@tonic-gate static int memRbtreeClearTable(Rbtree* tree, int n);
1417c478bd9Sstevel@tonic-gate static int memRbtreeNext(RbtCursor* pCur, int *pRes);
1427c478bd9Sstevel@tonic-gate static int memRbtreeLast(RbtCursor* pCur, int *pRes);
1437c478bd9Sstevel@tonic-gate static int memRbtreePrevious(RbtCursor* pCur, int *pRes);
1447c478bd9Sstevel@tonic-gate
1457c478bd9Sstevel@tonic-gate
1467c478bd9Sstevel@tonic-gate /*
1477c478bd9Sstevel@tonic-gate ** This routine checks all cursors that point to the same table
1487c478bd9Sstevel@tonic-gate ** as pCur points to. If any of those cursors were opened with
1497c478bd9Sstevel@tonic-gate ** wrFlag==0 then this routine returns SQLITE_LOCKED. If all
1507c478bd9Sstevel@tonic-gate ** cursors point to the same table were opened with wrFlag==1
1517c478bd9Sstevel@tonic-gate ** then this routine returns SQLITE_OK.
1527c478bd9Sstevel@tonic-gate **
153*1da57d55SToomas Soome ** In addition to checking for read-locks (where a read-lock
1547c478bd9Sstevel@tonic-gate ** means a cursor opened with wrFlag==0) this routine also NULLs
1557c478bd9Sstevel@tonic-gate ** out the pNode field of all other cursors.
156*1da57d55SToomas Soome ** This is necessary because an insert
1577c478bd9Sstevel@tonic-gate ** or delete might change erase the node out from under
1587c478bd9Sstevel@tonic-gate ** another cursor.
1597c478bd9Sstevel@tonic-gate */
checkReadLocks(RbtCursor * pCur)1607c478bd9Sstevel@tonic-gate static int checkReadLocks(RbtCursor *pCur){
1617c478bd9Sstevel@tonic-gate RbtCursor *p;
1627c478bd9Sstevel@tonic-gate assert( pCur->wrFlag );
1637c478bd9Sstevel@tonic-gate for(p=pCur->pTree->pCursors; p; p=p->pShared){
1647c478bd9Sstevel@tonic-gate if( p!=pCur ){
1657c478bd9Sstevel@tonic-gate if( p->wrFlag==0 ) return SQLITE_LOCKED;
1667c478bd9Sstevel@tonic-gate p->pNode = 0;
1677c478bd9Sstevel@tonic-gate }
1687c478bd9Sstevel@tonic-gate }
1697c478bd9Sstevel@tonic-gate return SQLITE_OK;
1707c478bd9Sstevel@tonic-gate }
1717c478bd9Sstevel@tonic-gate
1727c478bd9Sstevel@tonic-gate /*
1737c478bd9Sstevel@tonic-gate * The key-compare function for the red-black trees. Returns as follows:
1747c478bd9Sstevel@tonic-gate *
1757c478bd9Sstevel@tonic-gate * (key1 < key2) -1
176*1da57d55SToomas Soome * (key1 == key2) 0
1777c478bd9Sstevel@tonic-gate * (key1 > key2) 1
1787c478bd9Sstevel@tonic-gate *
1797c478bd9Sstevel@tonic-gate * Keys are compared using memcmp(). If one key is an exact prefix of the
1807c478bd9Sstevel@tonic-gate * other, then the shorter key is less than the longer key.
1817c478bd9Sstevel@tonic-gate */
key_compare(void const * pKey1,int nKey1,void const * pKey2,int nKey2)1827c478bd9Sstevel@tonic-gate static int key_compare(void const*pKey1, int nKey1, void const*pKey2, int nKey2)
1837c478bd9Sstevel@tonic-gate {
1847c478bd9Sstevel@tonic-gate int mcmp = memcmp(pKey1, pKey2, (nKey1 <= nKey2)?nKey1:nKey2);
1857c478bd9Sstevel@tonic-gate if( mcmp == 0){
1867c478bd9Sstevel@tonic-gate if( nKey1 == nKey2 ) return 0;
1877c478bd9Sstevel@tonic-gate return ((nKey1 < nKey2)?-1:1);
1887c478bd9Sstevel@tonic-gate }
1897c478bd9Sstevel@tonic-gate return ((mcmp>0)?1:-1);
1907c478bd9Sstevel@tonic-gate }
1917c478bd9Sstevel@tonic-gate
1927c478bd9Sstevel@tonic-gate /*
1937c478bd9Sstevel@tonic-gate * Perform the LEFT-rotate transformation on node X of tree pTree. This
1947c478bd9Sstevel@tonic-gate * transform is part of the red-black balancing code.
1957c478bd9Sstevel@tonic-gate *
1967c478bd9Sstevel@tonic-gate * | |
1977c478bd9Sstevel@tonic-gate * X Y
1987c478bd9Sstevel@tonic-gate * / \ / \
1997c478bd9Sstevel@tonic-gate * a Y X c
2007c478bd9Sstevel@tonic-gate * / \ / \
2017c478bd9Sstevel@tonic-gate * b c a b
2027c478bd9Sstevel@tonic-gate *
2037c478bd9Sstevel@tonic-gate * BEFORE AFTER
2047c478bd9Sstevel@tonic-gate */
leftRotate(BtRbTree * pTree,BtRbNode * pX)2057c478bd9Sstevel@tonic-gate static void leftRotate(BtRbTree *pTree, BtRbNode *pX)
2067c478bd9Sstevel@tonic-gate {
2077c478bd9Sstevel@tonic-gate BtRbNode *pY;
2087c478bd9Sstevel@tonic-gate BtRbNode *pb;
2097c478bd9Sstevel@tonic-gate pY = pX->pRight;
2107c478bd9Sstevel@tonic-gate pb = pY->pLeft;
2117c478bd9Sstevel@tonic-gate
2127c478bd9Sstevel@tonic-gate pY->pParent = pX->pParent;
2137c478bd9Sstevel@tonic-gate if( pX->pParent ){
2147c478bd9Sstevel@tonic-gate if( pX->pParent->pLeft == pX ) pX->pParent->pLeft = pY;
2157c478bd9Sstevel@tonic-gate else pX->pParent->pRight = pY;
2167c478bd9Sstevel@tonic-gate }
2177c478bd9Sstevel@tonic-gate pY->pLeft = pX;
2187c478bd9Sstevel@tonic-gate pX->pParent = pY;
2197c478bd9Sstevel@tonic-gate pX->pRight = pb;
2207c478bd9Sstevel@tonic-gate if( pb ) pb->pParent = pX;
2217c478bd9Sstevel@tonic-gate if( pTree->pHead == pX ) pTree->pHead = pY;
2227c478bd9Sstevel@tonic-gate }
2237c478bd9Sstevel@tonic-gate
2247c478bd9Sstevel@tonic-gate /*
2257c478bd9Sstevel@tonic-gate * Perform the RIGHT-rotate transformation on node X of tree pTree. This
2267c478bd9Sstevel@tonic-gate * transform is part of the red-black balancing code.
2277c478bd9Sstevel@tonic-gate *
2287c478bd9Sstevel@tonic-gate * | |
2297c478bd9Sstevel@tonic-gate * X Y
2307c478bd9Sstevel@tonic-gate * / \ / \
2317c478bd9Sstevel@tonic-gate * Y c a X
2327c478bd9Sstevel@tonic-gate * / \ / \
2337c478bd9Sstevel@tonic-gate * a b b c
2347c478bd9Sstevel@tonic-gate *
2357c478bd9Sstevel@tonic-gate * BEFORE AFTER
2367c478bd9Sstevel@tonic-gate */
rightRotate(BtRbTree * pTree,BtRbNode * pX)2377c478bd9Sstevel@tonic-gate static void rightRotate(BtRbTree *pTree, BtRbNode *pX)
2387c478bd9Sstevel@tonic-gate {
2397c478bd9Sstevel@tonic-gate BtRbNode *pY;
2407c478bd9Sstevel@tonic-gate BtRbNode *pb;
2417c478bd9Sstevel@tonic-gate pY = pX->pLeft;
2427c478bd9Sstevel@tonic-gate pb = pY->pRight;
2437c478bd9Sstevel@tonic-gate
2447c478bd9Sstevel@tonic-gate pY->pParent = pX->pParent;
2457c478bd9Sstevel@tonic-gate if( pX->pParent ){
2467c478bd9Sstevel@tonic-gate if( pX->pParent->pLeft == pX ) pX->pParent->pLeft = pY;
2477c478bd9Sstevel@tonic-gate else pX->pParent->pRight = pY;
2487c478bd9Sstevel@tonic-gate }
2497c478bd9Sstevel@tonic-gate pY->pRight = pX;
2507c478bd9Sstevel@tonic-gate pX->pParent = pY;
2517c478bd9Sstevel@tonic-gate pX->pLeft = pb;
2527c478bd9Sstevel@tonic-gate if( pb ) pb->pParent = pX;
2537c478bd9Sstevel@tonic-gate if( pTree->pHead == pX ) pTree->pHead = pY;
2547c478bd9Sstevel@tonic-gate }
2557c478bd9Sstevel@tonic-gate
2567c478bd9Sstevel@tonic-gate /*
2577c478bd9Sstevel@tonic-gate * A string-manipulation helper function for check_redblack_tree(). If (orig ==
2587c478bd9Sstevel@tonic-gate * NULL) a copy of val is returned. If (orig != NULL) then a copy of the *
2597c478bd9Sstevel@tonic-gate * concatenation of orig and val is returned. The original orig is deleted
2607c478bd9Sstevel@tonic-gate * (using sqliteFree()).
2617c478bd9Sstevel@tonic-gate */
append_val(char * orig,char const * val)2627c478bd9Sstevel@tonic-gate static char *append_val(char * orig, char const * val){
2637c478bd9Sstevel@tonic-gate char *z;
2647c478bd9Sstevel@tonic-gate if( !orig ){
2657c478bd9Sstevel@tonic-gate z = sqliteStrDup( val );
2667c478bd9Sstevel@tonic-gate } else{
2677c478bd9Sstevel@tonic-gate z = 0;
2687c478bd9Sstevel@tonic-gate sqliteSetString(&z, orig, val, (char*)0);
2697c478bd9Sstevel@tonic-gate sqliteFree( orig );
2707c478bd9Sstevel@tonic-gate }
2717c478bd9Sstevel@tonic-gate return z;
2727c478bd9Sstevel@tonic-gate }
2737c478bd9Sstevel@tonic-gate
2747c478bd9Sstevel@tonic-gate /*
2757c478bd9Sstevel@tonic-gate * Append a string representation of the entire node to orig and return it.
2767c478bd9Sstevel@tonic-gate * This is used to produce debugging information if check_redblack_tree() finds
2777c478bd9Sstevel@tonic-gate * a problem with a red-black binary tree.
2787c478bd9Sstevel@tonic-gate */
append_node(char * orig,BtRbNode * pNode,int indent)2797c478bd9Sstevel@tonic-gate static char *append_node(char * orig, BtRbNode *pNode, int indent)
2807c478bd9Sstevel@tonic-gate {
2817c478bd9Sstevel@tonic-gate char buf[128];
2827c478bd9Sstevel@tonic-gate int i;
2837c478bd9Sstevel@tonic-gate
2847c478bd9Sstevel@tonic-gate for( i=0; i<indent; i++ ){
2857c478bd9Sstevel@tonic-gate orig = append_val(orig, " ");
2867c478bd9Sstevel@tonic-gate }
2877c478bd9Sstevel@tonic-gate
2887c478bd9Sstevel@tonic-gate sprintf(buf, "%p", pNode);
2897c478bd9Sstevel@tonic-gate orig = append_val(orig, buf);
2907c478bd9Sstevel@tonic-gate
2917c478bd9Sstevel@tonic-gate if( pNode ){
2927c478bd9Sstevel@tonic-gate indent += 3;
2937c478bd9Sstevel@tonic-gate if( pNode->isBlack ){
2947c478bd9Sstevel@tonic-gate orig = append_val(orig, " B \n");
2957c478bd9Sstevel@tonic-gate }else{
2967c478bd9Sstevel@tonic-gate orig = append_val(orig, " R \n");
2977c478bd9Sstevel@tonic-gate }
2987c478bd9Sstevel@tonic-gate orig = append_node( orig, pNode->pLeft, indent );
2997c478bd9Sstevel@tonic-gate orig = append_node( orig, pNode->pRight, indent );
3007c478bd9Sstevel@tonic-gate }else{
3017c478bd9Sstevel@tonic-gate orig = append_val(orig, "\n");
3027c478bd9Sstevel@tonic-gate }
3037c478bd9Sstevel@tonic-gate return orig;
3047c478bd9Sstevel@tonic-gate }
3057c478bd9Sstevel@tonic-gate
3067c478bd9Sstevel@tonic-gate /*
3077c478bd9Sstevel@tonic-gate * Print a representation of a node to stdout. This function is only included
3087c478bd9Sstevel@tonic-gate * so you can call it from within a debugger if things get really bad. It
3097c478bd9Sstevel@tonic-gate * is not called from anyplace in the code.
3107c478bd9Sstevel@tonic-gate */
print_node(BtRbNode * pNode)3117c478bd9Sstevel@tonic-gate static void print_node(BtRbNode *pNode)
3127c478bd9Sstevel@tonic-gate {
3137c478bd9Sstevel@tonic-gate char * str = append_node(0, pNode, 0);
3147c478bd9Sstevel@tonic-gate printf("%s", str);
3157c478bd9Sstevel@tonic-gate
3167c478bd9Sstevel@tonic-gate /* Suppress a warning message about print_node() being unused */
3177c478bd9Sstevel@tonic-gate (void)print_node;
3187c478bd9Sstevel@tonic-gate }
3197c478bd9Sstevel@tonic-gate
320*1da57d55SToomas Soome /*
3217c478bd9Sstevel@tonic-gate * Check the following properties of the red-black tree:
3227c478bd9Sstevel@tonic-gate * (1) - If a node is red, both of it's children are black
3237c478bd9Sstevel@tonic-gate * (2) - Each path from a given node to a leaf (NULL) node passes thru the
324*1da57d55SToomas Soome * same number of black nodes
3257c478bd9Sstevel@tonic-gate *
3267c478bd9Sstevel@tonic-gate * If there is a problem, append a description (using append_val() ) to *msg.
3277c478bd9Sstevel@tonic-gate */
check_redblack_tree(BtRbTree * tree,char ** msg)3287c478bd9Sstevel@tonic-gate static void check_redblack_tree(BtRbTree * tree, char ** msg)
3297c478bd9Sstevel@tonic-gate {
3307c478bd9Sstevel@tonic-gate BtRbNode *pNode;
3317c478bd9Sstevel@tonic-gate
332*1da57d55SToomas Soome /* 0 -> came from parent
3337c478bd9Sstevel@tonic-gate * 1 -> came from left
3347c478bd9Sstevel@tonic-gate * 2 -> came from right */
3357c478bd9Sstevel@tonic-gate int prev_step = 0;
3367c478bd9Sstevel@tonic-gate
3377c478bd9Sstevel@tonic-gate pNode = tree->pHead;
3387c478bd9Sstevel@tonic-gate while( pNode ){
3397c478bd9Sstevel@tonic-gate switch( prev_step ){
3407c478bd9Sstevel@tonic-gate case 0:
3417c478bd9Sstevel@tonic-gate if( pNode->pLeft ){
3427c478bd9Sstevel@tonic-gate pNode = pNode->pLeft;
343*1da57d55SToomas Soome }else{
3447c478bd9Sstevel@tonic-gate prev_step = 1;
3457c478bd9Sstevel@tonic-gate }
3467c478bd9Sstevel@tonic-gate break;
3477c478bd9Sstevel@tonic-gate case 1:
3487c478bd9Sstevel@tonic-gate if( pNode->pRight ){
3497c478bd9Sstevel@tonic-gate pNode = pNode->pRight;
3507c478bd9Sstevel@tonic-gate prev_step = 0;
3517c478bd9Sstevel@tonic-gate }else{
3527c478bd9Sstevel@tonic-gate prev_step = 2;
3537c478bd9Sstevel@tonic-gate }
3547c478bd9Sstevel@tonic-gate break;
3557c478bd9Sstevel@tonic-gate case 2:
3567c478bd9Sstevel@tonic-gate /* Check red-black property (1) */
3577c478bd9Sstevel@tonic-gate if( !pNode->isBlack &&
3587c478bd9Sstevel@tonic-gate ( (pNode->pLeft && !pNode->pLeft->isBlack) ||
3597c478bd9Sstevel@tonic-gate (pNode->pRight && !pNode->pRight->isBlack) )
3607c478bd9Sstevel@tonic-gate ){
3617c478bd9Sstevel@tonic-gate char buf[128];
3627c478bd9Sstevel@tonic-gate sprintf(buf, "Red node with red child at %p\n", pNode);
3637c478bd9Sstevel@tonic-gate *msg = append_val(*msg, buf);
3647c478bd9Sstevel@tonic-gate *msg = append_node(*msg, tree->pHead, 0);
3657c478bd9Sstevel@tonic-gate *msg = append_val(*msg, "\n");
3667c478bd9Sstevel@tonic-gate }
3677c478bd9Sstevel@tonic-gate
3687c478bd9Sstevel@tonic-gate /* Check red-black property (2) */
369*1da57d55SToomas Soome {
3707c478bd9Sstevel@tonic-gate int leftHeight = 0;
3717c478bd9Sstevel@tonic-gate int rightHeight = 0;
3727c478bd9Sstevel@tonic-gate if( pNode->pLeft ){
3737c478bd9Sstevel@tonic-gate leftHeight += pNode->pLeft->nBlackHeight;
3747c478bd9Sstevel@tonic-gate leftHeight += (pNode->pLeft->isBlack?1:0);
3757c478bd9Sstevel@tonic-gate }
3767c478bd9Sstevel@tonic-gate if( pNode->pRight ){
3777c478bd9Sstevel@tonic-gate rightHeight += pNode->pRight->nBlackHeight;
3787c478bd9Sstevel@tonic-gate rightHeight += (pNode->pRight->isBlack?1:0);
3797c478bd9Sstevel@tonic-gate }
3807c478bd9Sstevel@tonic-gate if( leftHeight != rightHeight ){
3817c478bd9Sstevel@tonic-gate char buf[128];
3827c478bd9Sstevel@tonic-gate sprintf(buf, "Different black-heights at %p\n", pNode);
3837c478bd9Sstevel@tonic-gate *msg = append_val(*msg, buf);
3847c478bd9Sstevel@tonic-gate *msg = append_node(*msg, tree->pHead, 0);
3857c478bd9Sstevel@tonic-gate *msg = append_val(*msg, "\n");
3867c478bd9Sstevel@tonic-gate }
3877c478bd9Sstevel@tonic-gate pNode->nBlackHeight = leftHeight;
3887c478bd9Sstevel@tonic-gate }
3897c478bd9Sstevel@tonic-gate
3907c478bd9Sstevel@tonic-gate if( pNode->pParent ){
3917c478bd9Sstevel@tonic-gate if( pNode == pNode->pParent->pLeft ) prev_step = 1;
3927c478bd9Sstevel@tonic-gate else prev_step = 2;
3937c478bd9Sstevel@tonic-gate }
3947c478bd9Sstevel@tonic-gate pNode = pNode->pParent;
3957c478bd9Sstevel@tonic-gate break;
3967c478bd9Sstevel@tonic-gate default: assert(0);
3977c478bd9Sstevel@tonic-gate }
3987c478bd9Sstevel@tonic-gate }
399*1da57d55SToomas Soome }
4007c478bd9Sstevel@tonic-gate
4017c478bd9Sstevel@tonic-gate /*
4027c478bd9Sstevel@tonic-gate * Node pX has just been inserted into pTree (by code in sqliteRbtreeInsert()).
4037c478bd9Sstevel@tonic-gate * It is possible that pX is a red node with a red parent, which is a violation
404*1da57d55SToomas Soome * of the red-black tree properties. This function performs rotations and
4057c478bd9Sstevel@tonic-gate * color changes to rebalance the tree
4067c478bd9Sstevel@tonic-gate */
do_insert_balancing(BtRbTree * pTree,BtRbNode * pX)4077c478bd9Sstevel@tonic-gate static void do_insert_balancing(BtRbTree *pTree, BtRbNode *pX)
4087c478bd9Sstevel@tonic-gate {
4097c478bd9Sstevel@tonic-gate /* In the first iteration of this loop, pX points to the red node just
4107c478bd9Sstevel@tonic-gate * inserted in the tree. If the parent of pX exists (pX is not the root
4117c478bd9Sstevel@tonic-gate * node) and is red, then the properties of the red-black tree are
4127c478bd9Sstevel@tonic-gate * violated.
4137c478bd9Sstevel@tonic-gate *
4147c478bd9Sstevel@tonic-gate * At the start of any subsequent iterations, pX points to a red node
4157c478bd9Sstevel@tonic-gate * with a red parent. In all other respects the tree is a legal red-black
4167c478bd9Sstevel@tonic-gate * binary tree. */
4177c478bd9Sstevel@tonic-gate while( pX != pTree->pHead && !pX->pParent->isBlack ){
4187c478bd9Sstevel@tonic-gate BtRbNode *pUncle;
4197c478bd9Sstevel@tonic-gate BtRbNode *pGrandparent;
4207c478bd9Sstevel@tonic-gate
4217c478bd9Sstevel@tonic-gate /* Grandparent of pX must exist and must be black. */
4227c478bd9Sstevel@tonic-gate pGrandparent = pX->pParent->pParent;
4237c478bd9Sstevel@tonic-gate assert( pGrandparent );
4247c478bd9Sstevel@tonic-gate assert( pGrandparent->isBlack );
4257c478bd9Sstevel@tonic-gate
4267c478bd9Sstevel@tonic-gate /* Uncle of pX may or may not exist. */
427*1da57d55SToomas Soome if( pX->pParent == pGrandparent->pLeft )
4287c478bd9Sstevel@tonic-gate pUncle = pGrandparent->pRight;
429*1da57d55SToomas Soome else
4307c478bd9Sstevel@tonic-gate pUncle = pGrandparent->pLeft;
4317c478bd9Sstevel@tonic-gate
4327c478bd9Sstevel@tonic-gate /* If the uncle of pX exists and is red, we do the following:
4337c478bd9Sstevel@tonic-gate * | |
4347c478bd9Sstevel@tonic-gate * G(b) G(r)
435*1da57d55SToomas Soome * / \ / \
4367c478bd9Sstevel@tonic-gate * U(r) P(r) U(b) P(b)
4377c478bd9Sstevel@tonic-gate * \ \
4387c478bd9Sstevel@tonic-gate * X(r) X(r)
4397c478bd9Sstevel@tonic-gate *
4407c478bd9Sstevel@tonic-gate * BEFORE AFTER
4417c478bd9Sstevel@tonic-gate * pX is then set to G. If the parent of G is red, then the while loop
4427c478bd9Sstevel@tonic-gate * will run again. */
4437c478bd9Sstevel@tonic-gate if( pUncle && !pUncle->isBlack ){
4447c478bd9Sstevel@tonic-gate pGrandparent->isBlack = 0;
4457c478bd9Sstevel@tonic-gate pUncle->isBlack = 1;
4467c478bd9Sstevel@tonic-gate pX->pParent->isBlack = 1;
4477c478bd9Sstevel@tonic-gate pX = pGrandparent;
4487c478bd9Sstevel@tonic-gate }else{
4497c478bd9Sstevel@tonic-gate
4507c478bd9Sstevel@tonic-gate if( pX->pParent == pGrandparent->pLeft ){
4517c478bd9Sstevel@tonic-gate if( pX == pX->pParent->pRight ){
4527c478bd9Sstevel@tonic-gate /* If pX is a right-child, do the following transform, essentially
453*1da57d55SToomas Soome * to change pX into a left-child:
454*1da57d55SToomas Soome * | |
4557c478bd9Sstevel@tonic-gate * G(b) G(b)
456*1da57d55SToomas Soome * / \ / \
4577c478bd9Sstevel@tonic-gate * P(r) U(b) X(r) U(b)
4587c478bd9Sstevel@tonic-gate * \ /
4597c478bd9Sstevel@tonic-gate * X(r) P(r) <-- new X
4607c478bd9Sstevel@tonic-gate *
4617c478bd9Sstevel@tonic-gate * BEFORE AFTER
4627c478bd9Sstevel@tonic-gate */
4637c478bd9Sstevel@tonic-gate pX = pX->pParent;
4647c478bd9Sstevel@tonic-gate leftRotate(pTree, pX);
4657c478bd9Sstevel@tonic-gate }
4667c478bd9Sstevel@tonic-gate
467*1da57d55SToomas Soome /* Do the following transform, which balances the tree :)
468*1da57d55SToomas Soome * | |
4697c478bd9Sstevel@tonic-gate * G(b) P(b)
470*1da57d55SToomas Soome * / \ / \
4717c478bd9Sstevel@tonic-gate * P(r) U(b) X(r) G(r)
4727c478bd9Sstevel@tonic-gate * / \
4737c478bd9Sstevel@tonic-gate * X(r) U(b)
4747c478bd9Sstevel@tonic-gate *
4757c478bd9Sstevel@tonic-gate * BEFORE AFTER
4767c478bd9Sstevel@tonic-gate */
4777c478bd9Sstevel@tonic-gate assert( pGrandparent == pX->pParent->pParent );
4787c478bd9Sstevel@tonic-gate pGrandparent->isBlack = 0;
4797c478bd9Sstevel@tonic-gate pX->pParent->isBlack = 1;
4807c478bd9Sstevel@tonic-gate rightRotate( pTree, pGrandparent );
4817c478bd9Sstevel@tonic-gate
4827c478bd9Sstevel@tonic-gate }else{
4837c478bd9Sstevel@tonic-gate /* This code is symetric to the illustrated case above. */
4847c478bd9Sstevel@tonic-gate if( pX == pX->pParent->pLeft ){
4857c478bd9Sstevel@tonic-gate pX = pX->pParent;
4867c478bd9Sstevel@tonic-gate rightRotate(pTree, pX);
4877c478bd9Sstevel@tonic-gate }
4887c478bd9Sstevel@tonic-gate assert( pGrandparent == pX->pParent->pParent );
4897c478bd9Sstevel@tonic-gate pGrandparent->isBlack = 0;
4907c478bd9Sstevel@tonic-gate pX->pParent->isBlack = 1;
4917c478bd9Sstevel@tonic-gate leftRotate( pTree, pGrandparent );
4927c478bd9Sstevel@tonic-gate }
4937c478bd9Sstevel@tonic-gate }
4947c478bd9Sstevel@tonic-gate }
4957c478bd9Sstevel@tonic-gate pTree->pHead->isBlack = 1;
4967c478bd9Sstevel@tonic-gate }
4977c478bd9Sstevel@tonic-gate
4987c478bd9Sstevel@tonic-gate /*
499*1da57d55SToomas Soome * A child of pParent, which in turn had child pX, has just been removed from
5007c478bd9Sstevel@tonic-gate * pTree (the figure below depicts the operation, Z is being removed). pParent
501*1da57d55SToomas Soome * or pX, or both may be NULL.
5027c478bd9Sstevel@tonic-gate * | |
5037c478bd9Sstevel@tonic-gate * P P
5047c478bd9Sstevel@tonic-gate * / \ / \
5057c478bd9Sstevel@tonic-gate * Z X
5067c478bd9Sstevel@tonic-gate * / \
5077c478bd9Sstevel@tonic-gate * X nil
5087c478bd9Sstevel@tonic-gate *
5097c478bd9Sstevel@tonic-gate * This function is only called if Z was black. In this case the red-black tree
510*1da57d55SToomas Soome * properties have been violated, and pX has an "extra black". This function
5117c478bd9Sstevel@tonic-gate * performs rotations and color-changes to re-balance the tree.
5127c478bd9Sstevel@tonic-gate */
513*1da57d55SToomas Soome static
do_delete_balancing(BtRbTree * pTree,BtRbNode * pX,BtRbNode * pParent)5147c478bd9Sstevel@tonic-gate void do_delete_balancing(BtRbTree *pTree, BtRbNode *pX, BtRbNode *pParent)
5157c478bd9Sstevel@tonic-gate {
516*1da57d55SToomas Soome BtRbNode *pSib;
5177c478bd9Sstevel@tonic-gate
5187c478bd9Sstevel@tonic-gate /* TODO: Comment this code! */
5197c478bd9Sstevel@tonic-gate while( pX != pTree->pHead && (!pX || pX->isBlack) ){
5207c478bd9Sstevel@tonic-gate if( pX == pParent->pLeft ){
5217c478bd9Sstevel@tonic-gate pSib = pParent->pRight;
5227c478bd9Sstevel@tonic-gate if( pSib && !(pSib->isBlack) ){
5237c478bd9Sstevel@tonic-gate pSib->isBlack = 1;
5247c478bd9Sstevel@tonic-gate pParent->isBlack = 0;
5257c478bd9Sstevel@tonic-gate leftRotate(pTree, pParent);
5267c478bd9Sstevel@tonic-gate pSib = pParent->pRight;
5277c478bd9Sstevel@tonic-gate }
5287c478bd9Sstevel@tonic-gate if( !pSib ){
5297c478bd9Sstevel@tonic-gate pX = pParent;
530*1da57d55SToomas Soome }else if(
5317c478bd9Sstevel@tonic-gate (!pSib->pLeft || pSib->pLeft->isBlack) &&
5327c478bd9Sstevel@tonic-gate (!pSib->pRight || pSib->pRight->isBlack) ) {
5337c478bd9Sstevel@tonic-gate pSib->isBlack = 0;
5347c478bd9Sstevel@tonic-gate pX = pParent;
5357c478bd9Sstevel@tonic-gate }else{
5367c478bd9Sstevel@tonic-gate if( (!pSib->pRight || pSib->pRight->isBlack) ){
5377c478bd9Sstevel@tonic-gate if( pSib->pLeft ) pSib->pLeft->isBlack = 1;
5387c478bd9Sstevel@tonic-gate pSib->isBlack = 0;
5397c478bd9Sstevel@tonic-gate rightRotate( pTree, pSib );
5407c478bd9Sstevel@tonic-gate pSib = pParent->pRight;
5417c478bd9Sstevel@tonic-gate }
5427c478bd9Sstevel@tonic-gate pSib->isBlack = pParent->isBlack;
5437c478bd9Sstevel@tonic-gate pParent->isBlack = 1;
5447c478bd9Sstevel@tonic-gate if( pSib->pRight ) pSib->pRight->isBlack = 1;
5457c478bd9Sstevel@tonic-gate leftRotate(pTree, pParent);
5467c478bd9Sstevel@tonic-gate pX = pTree->pHead;
5477c478bd9Sstevel@tonic-gate }
5487c478bd9Sstevel@tonic-gate }else{
5497c478bd9Sstevel@tonic-gate pSib = pParent->pLeft;
5507c478bd9Sstevel@tonic-gate if( pSib && !(pSib->isBlack) ){
5517c478bd9Sstevel@tonic-gate pSib->isBlack = 1;
5527c478bd9Sstevel@tonic-gate pParent->isBlack = 0;
5537c478bd9Sstevel@tonic-gate rightRotate(pTree, pParent);
5547c478bd9Sstevel@tonic-gate pSib = pParent->pLeft;
5557c478bd9Sstevel@tonic-gate }
5567c478bd9Sstevel@tonic-gate if( !pSib ){
5577c478bd9Sstevel@tonic-gate pX = pParent;
558*1da57d55SToomas Soome }else if(
5597c478bd9Sstevel@tonic-gate (!pSib->pLeft || pSib->pLeft->isBlack) &&
5607c478bd9Sstevel@tonic-gate (!pSib->pRight || pSib->pRight->isBlack) ){
5617c478bd9Sstevel@tonic-gate pSib->isBlack = 0;
5627c478bd9Sstevel@tonic-gate pX = pParent;
5637c478bd9Sstevel@tonic-gate }else{
5647c478bd9Sstevel@tonic-gate if( (!pSib->pLeft || pSib->pLeft->isBlack) ){
5657c478bd9Sstevel@tonic-gate if( pSib->pRight ) pSib->pRight->isBlack = 1;
5667c478bd9Sstevel@tonic-gate pSib->isBlack = 0;
5677c478bd9Sstevel@tonic-gate leftRotate( pTree, pSib );
5687c478bd9Sstevel@tonic-gate pSib = pParent->pLeft;
5697c478bd9Sstevel@tonic-gate }
5707c478bd9Sstevel@tonic-gate pSib->isBlack = pParent->isBlack;
5717c478bd9Sstevel@tonic-gate pParent->isBlack = 1;
5727c478bd9Sstevel@tonic-gate if( pSib->pLeft ) pSib->pLeft->isBlack = 1;
5737c478bd9Sstevel@tonic-gate rightRotate(pTree, pParent);
5747c478bd9Sstevel@tonic-gate pX = pTree->pHead;
5757c478bd9Sstevel@tonic-gate }
5767c478bd9Sstevel@tonic-gate }
5777c478bd9Sstevel@tonic-gate pParent = pX->pParent;
5787c478bd9Sstevel@tonic-gate }
5797c478bd9Sstevel@tonic-gate if( pX ) pX->isBlack = 1;
5807c478bd9Sstevel@tonic-gate }
5817c478bd9Sstevel@tonic-gate
5827c478bd9Sstevel@tonic-gate /*
5837c478bd9Sstevel@tonic-gate * Create table n in tree pRbtree. Table n must not exist.
5847c478bd9Sstevel@tonic-gate */
btreeCreateTable(Rbtree * pRbtree,int n)5857c478bd9Sstevel@tonic-gate static void btreeCreateTable(Rbtree* pRbtree, int n)
5867c478bd9Sstevel@tonic-gate {
5877c478bd9Sstevel@tonic-gate BtRbTree *pNewTbl = sqliteMalloc(sizeof(BtRbTree));
5887c478bd9Sstevel@tonic-gate sqliteHashInsert(&pRbtree->tblHash, 0, n, pNewTbl);
5897c478bd9Sstevel@tonic-gate }
5907c478bd9Sstevel@tonic-gate
5917c478bd9Sstevel@tonic-gate /*
5927c478bd9Sstevel@tonic-gate * Log a single "rollback-op" for the given Rbtree. See comments for struct
5937c478bd9Sstevel@tonic-gate * BtRollbackOp.
5947c478bd9Sstevel@tonic-gate */
btreeLogRollbackOp(Rbtree * pRbtree,BtRollbackOp * pRollbackOp)5957c478bd9Sstevel@tonic-gate static void btreeLogRollbackOp(Rbtree* pRbtree, BtRollbackOp *pRollbackOp)
5967c478bd9Sstevel@tonic-gate {
5977c478bd9Sstevel@tonic-gate assert( pRbtree->eTransState == TRANS_INCHECKPOINT ||
5987c478bd9Sstevel@tonic-gate pRbtree->eTransState == TRANS_INTRANSACTION );
5997c478bd9Sstevel@tonic-gate if( pRbtree->eTransState == TRANS_INTRANSACTION ){
6007c478bd9Sstevel@tonic-gate pRollbackOp->pNext = pRbtree->pTransRollback;
6017c478bd9Sstevel@tonic-gate pRbtree->pTransRollback = pRollbackOp;
6027c478bd9Sstevel@tonic-gate }
6037c478bd9Sstevel@tonic-gate if( pRbtree->eTransState == TRANS_INCHECKPOINT ){
6047c478bd9Sstevel@tonic-gate if( !pRbtree->pCheckRollback ){
6057c478bd9Sstevel@tonic-gate pRbtree->pCheckRollbackTail = pRollbackOp;
6067c478bd9Sstevel@tonic-gate }
6077c478bd9Sstevel@tonic-gate pRollbackOp->pNext = pRbtree->pCheckRollback;
6087c478bd9Sstevel@tonic-gate pRbtree->pCheckRollback = pRollbackOp;
6097c478bd9Sstevel@tonic-gate }
6107c478bd9Sstevel@tonic-gate }
6117c478bd9Sstevel@tonic-gate
sqliteRbtreeOpen(const char * zFilename,int mode,int nPg,Btree ** ppBtree)6127c478bd9Sstevel@tonic-gate int sqliteRbtreeOpen(
6137c478bd9Sstevel@tonic-gate const char *zFilename,
6147c478bd9Sstevel@tonic-gate int mode,
6157c478bd9Sstevel@tonic-gate int nPg,
6167c478bd9Sstevel@tonic-gate Btree **ppBtree
6177c478bd9Sstevel@tonic-gate ){
6187c478bd9Sstevel@tonic-gate Rbtree **ppRbtree = (Rbtree**)ppBtree;
6197c478bd9Sstevel@tonic-gate *ppRbtree = (Rbtree *)sqliteMalloc(sizeof(Rbtree));
6207c478bd9Sstevel@tonic-gate if( sqlite_malloc_failed ) goto open_no_mem;
6217c478bd9Sstevel@tonic-gate sqliteHashInit(&(*ppRbtree)->tblHash, SQLITE_HASH_INT, 0);
6227c478bd9Sstevel@tonic-gate
6237c478bd9Sstevel@tonic-gate /* Create a binary tree for the SQLITE_MASTER table at location 2 */
6247c478bd9Sstevel@tonic-gate btreeCreateTable(*ppRbtree, 2);
6257c478bd9Sstevel@tonic-gate if( sqlite_malloc_failed ) goto open_no_mem;
6267c478bd9Sstevel@tonic-gate (*ppRbtree)->next_idx = 3;
6277c478bd9Sstevel@tonic-gate (*ppRbtree)->pOps = &sqliteRbtreeOps;
6287c478bd9Sstevel@tonic-gate /* Set file type to 4; this is so that "attach ':memory:' as ...." does not
6297c478bd9Sstevel@tonic-gate ** think that the database in uninitialised and refuse to attach
6307c478bd9Sstevel@tonic-gate */
6317c478bd9Sstevel@tonic-gate (*ppRbtree)->aMetaData[2] = 4;
632*1da57d55SToomas Soome
6337c478bd9Sstevel@tonic-gate return SQLITE_OK;
6347c478bd9Sstevel@tonic-gate
6357c478bd9Sstevel@tonic-gate open_no_mem:
6367c478bd9Sstevel@tonic-gate *ppBtree = 0;
6377c478bd9Sstevel@tonic-gate return SQLITE_NOMEM;
6387c478bd9Sstevel@tonic-gate }
6397c478bd9Sstevel@tonic-gate
6407c478bd9Sstevel@tonic-gate /*
6417c478bd9Sstevel@tonic-gate * Create a new table in the supplied Rbtree. Set *n to the new table number.
6427c478bd9Sstevel@tonic-gate * Return SQLITE_OK if the operation is a success.
6437c478bd9Sstevel@tonic-gate */
memRbtreeCreateTable(Rbtree * tree,int * n)6447c478bd9Sstevel@tonic-gate static int memRbtreeCreateTable(Rbtree* tree, int* n)
6457c478bd9Sstevel@tonic-gate {
6467c478bd9Sstevel@tonic-gate assert( tree->eTransState != TRANS_NONE );
6477c478bd9Sstevel@tonic-gate
6487c478bd9Sstevel@tonic-gate *n = tree->next_idx++;
6497c478bd9Sstevel@tonic-gate btreeCreateTable(tree, *n);
6507c478bd9Sstevel@tonic-gate if( sqlite_malloc_failed ) return SQLITE_NOMEM;
6517c478bd9Sstevel@tonic-gate
6527c478bd9Sstevel@tonic-gate /* Set up the rollback structure (if we are not doing this as part of a
6537c478bd9Sstevel@tonic-gate * rollback) */
6547c478bd9Sstevel@tonic-gate if( tree->eTransState != TRANS_ROLLBACK ){
6557c478bd9Sstevel@tonic-gate BtRollbackOp *pRollbackOp = sqliteMalloc(sizeof(BtRollbackOp));
6567c478bd9Sstevel@tonic-gate if( pRollbackOp==0 ) return SQLITE_NOMEM;
6577c478bd9Sstevel@tonic-gate pRollbackOp->eOp = ROLLBACK_DROP;
6587c478bd9Sstevel@tonic-gate pRollbackOp->iTab = *n;
6597c478bd9Sstevel@tonic-gate btreeLogRollbackOp(tree, pRollbackOp);
6607c478bd9Sstevel@tonic-gate }
6617c478bd9Sstevel@tonic-gate
6627c478bd9Sstevel@tonic-gate return SQLITE_OK;
6637c478bd9Sstevel@tonic-gate }
6647c478bd9Sstevel@tonic-gate
6657c478bd9Sstevel@tonic-gate /*
666*1da57d55SToomas Soome * Delete table n from the supplied Rbtree.
6677c478bd9Sstevel@tonic-gate */
memRbtreeDropTable(Rbtree * tree,int n)6687c478bd9Sstevel@tonic-gate static int memRbtreeDropTable(Rbtree* tree, int n)
6697c478bd9Sstevel@tonic-gate {
6707c478bd9Sstevel@tonic-gate BtRbTree *pTree;
6717c478bd9Sstevel@tonic-gate assert( tree->eTransState != TRANS_NONE );
6727c478bd9Sstevel@tonic-gate
6737c478bd9Sstevel@tonic-gate memRbtreeClearTable(tree, n);
6747c478bd9Sstevel@tonic-gate pTree = sqliteHashInsert(&tree->tblHash, 0, n, 0);
6757c478bd9Sstevel@tonic-gate assert(pTree);
6767c478bd9Sstevel@tonic-gate assert( pTree->pCursors==0 );
6777c478bd9Sstevel@tonic-gate sqliteFree(pTree);
6787c478bd9Sstevel@tonic-gate
6797c478bd9Sstevel@tonic-gate if( tree->eTransState != TRANS_ROLLBACK ){
6807c478bd9Sstevel@tonic-gate BtRollbackOp *pRollbackOp = sqliteMalloc(sizeof(BtRollbackOp));
6817c478bd9Sstevel@tonic-gate if( pRollbackOp==0 ) return SQLITE_NOMEM;
6827c478bd9Sstevel@tonic-gate pRollbackOp->eOp = ROLLBACK_CREATE;
6837c478bd9Sstevel@tonic-gate pRollbackOp->iTab = n;
6847c478bd9Sstevel@tonic-gate btreeLogRollbackOp(tree, pRollbackOp);
6857c478bd9Sstevel@tonic-gate }
6867c478bd9Sstevel@tonic-gate
6877c478bd9Sstevel@tonic-gate return SQLITE_OK;
6887c478bd9Sstevel@tonic-gate }
6897c478bd9Sstevel@tonic-gate
memRbtreeKeyCompare(RbtCursor * pCur,const void * pKey,int nKey,int nIgnore,int * pRes)6907c478bd9Sstevel@tonic-gate static int memRbtreeKeyCompare(RbtCursor* pCur, const void *pKey, int nKey,
6917c478bd9Sstevel@tonic-gate int nIgnore, int *pRes)
6927c478bd9Sstevel@tonic-gate {
6937c478bd9Sstevel@tonic-gate assert(pCur);
6947c478bd9Sstevel@tonic-gate
6957c478bd9Sstevel@tonic-gate if( !pCur->pNode ) {
6967c478bd9Sstevel@tonic-gate *pRes = -1;
6977c478bd9Sstevel@tonic-gate } else {
6987c478bd9Sstevel@tonic-gate if( (pCur->pNode->nKey - nIgnore) < 0 ){
6997c478bd9Sstevel@tonic-gate *pRes = -1;
7007c478bd9Sstevel@tonic-gate }else{
701*1da57d55SToomas Soome *pRes = key_compare(pCur->pNode->pKey, pCur->pNode->nKey-nIgnore,
7027c478bd9Sstevel@tonic-gate pKey, nKey);
7037c478bd9Sstevel@tonic-gate }
7047c478bd9Sstevel@tonic-gate }
7057c478bd9Sstevel@tonic-gate return SQLITE_OK;
7067c478bd9Sstevel@tonic-gate }
7077c478bd9Sstevel@tonic-gate
7087c478bd9Sstevel@tonic-gate /*
7097c478bd9Sstevel@tonic-gate * Get a new cursor for table iTable of the supplied Rbtree. The wrFlag
7107c478bd9Sstevel@tonic-gate * parameter indicates that the cursor is open for writing.
7117c478bd9Sstevel@tonic-gate *
7127c478bd9Sstevel@tonic-gate * Note that RbtCursor.eSkip and RbtCursor.pNode both initialize to 0.
7137c478bd9Sstevel@tonic-gate */
memRbtreeCursor(Rbtree * tree,int iTable,int wrFlag,RbtCursor ** ppCur)7147c478bd9Sstevel@tonic-gate static int memRbtreeCursor(
7157c478bd9Sstevel@tonic-gate Rbtree* tree,
7167c478bd9Sstevel@tonic-gate int iTable,
7177c478bd9Sstevel@tonic-gate int wrFlag,
7187c478bd9Sstevel@tonic-gate RbtCursor **ppCur
7197c478bd9Sstevel@tonic-gate ){
7207c478bd9Sstevel@tonic-gate RbtCursor *pCur;
7217c478bd9Sstevel@tonic-gate assert(tree);
7227c478bd9Sstevel@tonic-gate pCur = *ppCur = sqliteMalloc(sizeof(RbtCursor));
7237c478bd9Sstevel@tonic-gate if( sqlite_malloc_failed ) return SQLITE_NOMEM;
7247c478bd9Sstevel@tonic-gate pCur->pTree = sqliteHashFind(&tree->tblHash, 0, iTable);
7257c478bd9Sstevel@tonic-gate assert( pCur->pTree );
7267c478bd9Sstevel@tonic-gate pCur->pRbtree = tree;
7277c478bd9Sstevel@tonic-gate pCur->iTree = iTable;
7287c478bd9Sstevel@tonic-gate pCur->pOps = &sqliteRbtreeCursorOps;
7297c478bd9Sstevel@tonic-gate pCur->wrFlag = wrFlag;
7307c478bd9Sstevel@tonic-gate pCur->pShared = pCur->pTree->pCursors;
7317c478bd9Sstevel@tonic-gate pCur->pTree->pCursors = pCur;
7327c478bd9Sstevel@tonic-gate
7337c478bd9Sstevel@tonic-gate assert( (*ppCur)->pTree );
7347c478bd9Sstevel@tonic-gate return SQLITE_OK;
7357c478bd9Sstevel@tonic-gate }
7367c478bd9Sstevel@tonic-gate
7377c478bd9Sstevel@tonic-gate /*
7387c478bd9Sstevel@tonic-gate * Insert a new record into the Rbtree. The key is given by (pKey,nKey)
7397c478bd9Sstevel@tonic-gate * and the data is given by (pData,nData). The cursor is used only to
7407c478bd9Sstevel@tonic-gate * define what database the record should be inserted into. The cursor
7417c478bd9Sstevel@tonic-gate * is left pointing at the new record.
7427c478bd9Sstevel@tonic-gate *
743*1da57d55SToomas Soome * If the key exists already in the tree, just replace the data.
7447c478bd9Sstevel@tonic-gate */
memRbtreeInsert(RbtCursor * pCur,const void * pKey,int nKey,const void * pDataInput,int nData)7457c478bd9Sstevel@tonic-gate static int memRbtreeInsert(
7467c478bd9Sstevel@tonic-gate RbtCursor* pCur,
7477c478bd9Sstevel@tonic-gate const void *pKey,
7487c478bd9Sstevel@tonic-gate int nKey,
7497c478bd9Sstevel@tonic-gate const void *pDataInput,
7507c478bd9Sstevel@tonic-gate int nData
7517c478bd9Sstevel@tonic-gate ){
7527c478bd9Sstevel@tonic-gate void * pData;
7537c478bd9Sstevel@tonic-gate int match;
7547c478bd9Sstevel@tonic-gate
7557c478bd9Sstevel@tonic-gate /* It is illegal to call sqliteRbtreeInsert() if we are
7567c478bd9Sstevel@tonic-gate ** not in a transaction */
7577c478bd9Sstevel@tonic-gate assert( pCur->pRbtree->eTransState != TRANS_NONE );
7587c478bd9Sstevel@tonic-gate
7597c478bd9Sstevel@tonic-gate /* Make sure some other cursor isn't trying to read this same table */
7607c478bd9Sstevel@tonic-gate if( checkReadLocks(pCur) ){
7617c478bd9Sstevel@tonic-gate return SQLITE_LOCKED; /* The table pCur points to has a read lock */
7627c478bd9Sstevel@tonic-gate }
7637c478bd9Sstevel@tonic-gate
764*1da57d55SToomas Soome /* Take a copy of the input data now, in case we need it for the
7657c478bd9Sstevel@tonic-gate * replace case */
7667c478bd9Sstevel@tonic-gate pData = sqliteMallocRaw(nData);
7677c478bd9Sstevel@tonic-gate if( sqlite_malloc_failed ) return SQLITE_NOMEM;
7687c478bd9Sstevel@tonic-gate memcpy(pData, pDataInput, nData);
7697c478bd9Sstevel@tonic-gate
7707c478bd9Sstevel@tonic-gate /* Move the cursor to a node near the key to be inserted. If the key already
7717c478bd9Sstevel@tonic-gate * exists in the table, then (match == 0). In this case we can just replace
7727c478bd9Sstevel@tonic-gate * the data associated with the entry, we don't need to manipulate the tree.
773*1da57d55SToomas Soome *
7747c478bd9Sstevel@tonic-gate * If there is no exact match, then the cursor points at what would be either
7757c478bd9Sstevel@tonic-gate * the predecessor (match == -1) or successor (match == 1) of the
7767c478bd9Sstevel@tonic-gate * searched-for key, were it to be inserted. The new node becomes a child of
7777c478bd9Sstevel@tonic-gate * this node.
778*1da57d55SToomas Soome *
7797c478bd9Sstevel@tonic-gate * The new node is initially red.
7807c478bd9Sstevel@tonic-gate */
7817c478bd9Sstevel@tonic-gate memRbtreeMoveto( pCur, pKey, nKey, &match);
7827c478bd9Sstevel@tonic-gate if( match ){
7837c478bd9Sstevel@tonic-gate BtRbNode *pNode = sqliteMalloc(sizeof(BtRbNode));
7847c478bd9Sstevel@tonic-gate if( pNode==0 ) return SQLITE_NOMEM;
7857c478bd9Sstevel@tonic-gate pNode->nKey = nKey;
7867c478bd9Sstevel@tonic-gate pNode->pKey = sqliteMallocRaw(nKey);
7877c478bd9Sstevel@tonic-gate if( sqlite_malloc_failed ) return SQLITE_NOMEM;
7887c478bd9Sstevel@tonic-gate memcpy(pNode->pKey, pKey, nKey);
7897c478bd9Sstevel@tonic-gate pNode->nData = nData;
790*1da57d55SToomas Soome pNode->pData = pData;
7917c478bd9Sstevel@tonic-gate if( pCur->pNode ){
7927c478bd9Sstevel@tonic-gate switch( match ){
7937c478bd9Sstevel@tonic-gate case -1:
7947c478bd9Sstevel@tonic-gate assert( !pCur->pNode->pRight );
7957c478bd9Sstevel@tonic-gate pNode->pParent = pCur->pNode;
7967c478bd9Sstevel@tonic-gate pCur->pNode->pRight = pNode;
7977c478bd9Sstevel@tonic-gate break;
7987c478bd9Sstevel@tonic-gate case 1:
7997c478bd9Sstevel@tonic-gate assert( !pCur->pNode->pLeft );
8007c478bd9Sstevel@tonic-gate pNode->pParent = pCur->pNode;
8017c478bd9Sstevel@tonic-gate pCur->pNode->pLeft = pNode;
8027c478bd9Sstevel@tonic-gate break;
8037c478bd9Sstevel@tonic-gate default:
8047c478bd9Sstevel@tonic-gate assert(0);
8057c478bd9Sstevel@tonic-gate }
8067c478bd9Sstevel@tonic-gate }else{
8077c478bd9Sstevel@tonic-gate pCur->pTree->pHead = pNode;
8087c478bd9Sstevel@tonic-gate }
8097c478bd9Sstevel@tonic-gate
8107c478bd9Sstevel@tonic-gate /* Point the cursor at the node just inserted, as per SQLite requirements */
8117c478bd9Sstevel@tonic-gate pCur->pNode = pNode;
8127c478bd9Sstevel@tonic-gate
8137c478bd9Sstevel@tonic-gate /* A new node has just been inserted, so run the balancing code */
8147c478bd9Sstevel@tonic-gate do_insert_balancing(pCur->pTree, pNode);
8157c478bd9Sstevel@tonic-gate
8167c478bd9Sstevel@tonic-gate /* Set up a rollback-op in case we have to roll this operation back */
8177c478bd9Sstevel@tonic-gate if( pCur->pRbtree->eTransState != TRANS_ROLLBACK ){
8187c478bd9Sstevel@tonic-gate BtRollbackOp *pOp = sqliteMalloc( sizeof(BtRollbackOp) );
8197c478bd9Sstevel@tonic-gate if( pOp==0 ) return SQLITE_NOMEM;
8207c478bd9Sstevel@tonic-gate pOp->eOp = ROLLBACK_DELETE;
8217c478bd9Sstevel@tonic-gate pOp->iTab = pCur->iTree;
8227c478bd9Sstevel@tonic-gate pOp->nKey = pNode->nKey;
8237c478bd9Sstevel@tonic-gate pOp->pKey = sqliteMallocRaw( pOp->nKey );
8247c478bd9Sstevel@tonic-gate if( sqlite_malloc_failed ) return SQLITE_NOMEM;
8257c478bd9Sstevel@tonic-gate memcpy( pOp->pKey, pNode->pKey, pOp->nKey );
8267c478bd9Sstevel@tonic-gate btreeLogRollbackOp(pCur->pRbtree, pOp);
8277c478bd9Sstevel@tonic-gate }
8287c478bd9Sstevel@tonic-gate
829*1da57d55SToomas Soome }else{
8307c478bd9Sstevel@tonic-gate /* No need to insert a new node in the tree, as the key already exists.
8317c478bd9Sstevel@tonic-gate * Just clobber the current nodes data. */
8327c478bd9Sstevel@tonic-gate
8337c478bd9Sstevel@tonic-gate /* Set up a rollback-op in case we have to roll this operation back */
8347c478bd9Sstevel@tonic-gate if( pCur->pRbtree->eTransState != TRANS_ROLLBACK ){
8357c478bd9Sstevel@tonic-gate BtRollbackOp *pOp = sqliteMalloc( sizeof(BtRollbackOp) );
8367c478bd9Sstevel@tonic-gate if( pOp==0 ) return SQLITE_NOMEM;
8377c478bd9Sstevel@tonic-gate pOp->iTab = pCur->iTree;
8387c478bd9Sstevel@tonic-gate pOp->nKey = pCur->pNode->nKey;
8397c478bd9Sstevel@tonic-gate pOp->pKey = sqliteMallocRaw( pOp->nKey );
8407c478bd9Sstevel@tonic-gate if( sqlite_malloc_failed ) return SQLITE_NOMEM;
8417c478bd9Sstevel@tonic-gate memcpy( pOp->pKey, pCur->pNode->pKey, pOp->nKey );
8427c478bd9Sstevel@tonic-gate pOp->nData = pCur->pNode->nData;
8437c478bd9Sstevel@tonic-gate pOp->pData = pCur->pNode->pData;
8447c478bd9Sstevel@tonic-gate pOp->eOp = ROLLBACK_INSERT;
8457c478bd9Sstevel@tonic-gate btreeLogRollbackOp(pCur->pRbtree, pOp);
8467c478bd9Sstevel@tonic-gate }else{
8477c478bd9Sstevel@tonic-gate sqliteFree( pCur->pNode->pData );
8487c478bd9Sstevel@tonic-gate }
8497c478bd9Sstevel@tonic-gate
8507c478bd9Sstevel@tonic-gate /* Actually clobber the nodes data */
8517c478bd9Sstevel@tonic-gate pCur->pNode->pData = pData;
8527c478bd9Sstevel@tonic-gate pCur->pNode->nData = nData;
8537c478bd9Sstevel@tonic-gate }
8547c478bd9Sstevel@tonic-gate
8557c478bd9Sstevel@tonic-gate return SQLITE_OK;
8567c478bd9Sstevel@tonic-gate }
8577c478bd9Sstevel@tonic-gate
8587c478bd9Sstevel@tonic-gate /* Move the cursor so that it points to an entry near pKey.
8597c478bd9Sstevel@tonic-gate ** Return a success code.
8607c478bd9Sstevel@tonic-gate **
8617c478bd9Sstevel@tonic-gate ** *pRes<0 The cursor is left pointing at an entry that
8627c478bd9Sstevel@tonic-gate ** is smaller than pKey or if the table is empty
8637c478bd9Sstevel@tonic-gate ** and the cursor is therefore left point to nothing.
8647c478bd9Sstevel@tonic-gate **
8657c478bd9Sstevel@tonic-gate ** *pRes==0 The cursor is left pointing at an entry that
8667c478bd9Sstevel@tonic-gate ** exactly matches pKey.
8677c478bd9Sstevel@tonic-gate **
8687c478bd9Sstevel@tonic-gate ** *pRes>0 The cursor is left pointing at an entry that
8697c478bd9Sstevel@tonic-gate ** is larger than pKey.
8707c478bd9Sstevel@tonic-gate */
memRbtreeMoveto(RbtCursor * pCur,const void * pKey,int nKey,int * pRes)8717c478bd9Sstevel@tonic-gate static int memRbtreeMoveto(
8727c478bd9Sstevel@tonic-gate RbtCursor* pCur,
8737c478bd9Sstevel@tonic-gate const void *pKey,
8747c478bd9Sstevel@tonic-gate int nKey,
8757c478bd9Sstevel@tonic-gate int *pRes
8767c478bd9Sstevel@tonic-gate ){
8777c478bd9Sstevel@tonic-gate BtRbNode *pTmp = 0;
8787c478bd9Sstevel@tonic-gate
8797c478bd9Sstevel@tonic-gate pCur->pNode = pCur->pTree->pHead;
8807c478bd9Sstevel@tonic-gate *pRes = -1;
8817c478bd9Sstevel@tonic-gate while( pCur->pNode && *pRes ) {
8827c478bd9Sstevel@tonic-gate *pRes = key_compare(pCur->pNode->pKey, pCur->pNode->nKey, pKey, nKey);
8837c478bd9Sstevel@tonic-gate pTmp = pCur->pNode;
8847c478bd9Sstevel@tonic-gate switch( *pRes ){
8857c478bd9Sstevel@tonic-gate case 1: /* cursor > key */
8867c478bd9Sstevel@tonic-gate pCur->pNode = pCur->pNode->pLeft;
8877c478bd9Sstevel@tonic-gate break;
8887c478bd9Sstevel@tonic-gate case -1: /* cursor < key */
8897c478bd9Sstevel@tonic-gate pCur->pNode = pCur->pNode->pRight;
8907c478bd9Sstevel@tonic-gate break;
8917c478bd9Sstevel@tonic-gate }
892*1da57d55SToomas Soome }
8937c478bd9Sstevel@tonic-gate
8947c478bd9Sstevel@tonic-gate /* If (pCur->pNode == NULL), then we have failed to find a match. Set
8957c478bd9Sstevel@tonic-gate * pCur->pNode to pTmp, which is either NULL (if the tree is empty) or the
8967c478bd9Sstevel@tonic-gate * last node traversed in the search. In either case the relation ship
8977c478bd9Sstevel@tonic-gate * between pTmp and the searched for key is already stored in *pRes. pTmp is
8987c478bd9Sstevel@tonic-gate * either the successor or predecessor of the key we tried to move to. */
8997c478bd9Sstevel@tonic-gate if( !pCur->pNode ) pCur->pNode = pTmp;
9007c478bd9Sstevel@tonic-gate pCur->eSkip = SKIP_NONE;
9017c478bd9Sstevel@tonic-gate
9027c478bd9Sstevel@tonic-gate return SQLITE_OK;
9037c478bd9Sstevel@tonic-gate }
9047c478bd9Sstevel@tonic-gate
9057c478bd9Sstevel@tonic-gate
9067c478bd9Sstevel@tonic-gate /*
9077c478bd9Sstevel@tonic-gate ** Delete the entry that the cursor is pointing to.
9087c478bd9Sstevel@tonic-gate **
9097c478bd9Sstevel@tonic-gate ** The cursor is left pointing at either the next or the previous
910*1da57d55SToomas Soome ** entry. If the cursor is left pointing to the next entry, then
911*1da57d55SToomas Soome ** the pCur->eSkip flag is set to SKIP_NEXT which forces the next call to
9127c478bd9Sstevel@tonic-gate ** sqliteRbtreeNext() to be a no-op. That way, you can always call
9137c478bd9Sstevel@tonic-gate ** sqliteRbtreeNext() after a delete and the cursor will be left
9147c478bd9Sstevel@tonic-gate ** pointing to the first entry after the deleted entry. Similarly,
9157c478bd9Sstevel@tonic-gate ** pCur->eSkip is set to SKIP_PREV is the cursor is left pointing to
9167c478bd9Sstevel@tonic-gate ** the entry prior to the deleted entry so that a subsequent call to
9177c478bd9Sstevel@tonic-gate ** sqliteRbtreePrevious() will always leave the cursor pointing at the
9187c478bd9Sstevel@tonic-gate ** entry immediately before the one that was deleted.
9197c478bd9Sstevel@tonic-gate */
memRbtreeDelete(RbtCursor * pCur)9207c478bd9Sstevel@tonic-gate static int memRbtreeDelete(RbtCursor* pCur)
9217c478bd9Sstevel@tonic-gate {
9227c478bd9Sstevel@tonic-gate BtRbNode *pZ; /* The one being deleted */
9237c478bd9Sstevel@tonic-gate BtRbNode *pChild; /* The child of the spliced out node */
9247c478bd9Sstevel@tonic-gate
9257c478bd9Sstevel@tonic-gate /* It is illegal to call sqliteRbtreeDelete() if we are
9267c478bd9Sstevel@tonic-gate ** not in a transaction */
9277c478bd9Sstevel@tonic-gate assert( pCur->pRbtree->eTransState != TRANS_NONE );
9287c478bd9Sstevel@tonic-gate
9297c478bd9Sstevel@tonic-gate /* Make sure some other cursor isn't trying to read this same table */
9307c478bd9Sstevel@tonic-gate if( checkReadLocks(pCur) ){
9317c478bd9Sstevel@tonic-gate return SQLITE_LOCKED; /* The table pCur points to has a read lock */
9327c478bd9Sstevel@tonic-gate }
9337c478bd9Sstevel@tonic-gate
9347c478bd9Sstevel@tonic-gate pZ = pCur->pNode;
9357c478bd9Sstevel@tonic-gate if( !pZ ){
9367c478bd9Sstevel@tonic-gate return SQLITE_OK;
9377c478bd9Sstevel@tonic-gate }
9387c478bd9Sstevel@tonic-gate
939*1da57d55SToomas Soome /* If we are not currently doing a rollback, set up a rollback op for this
9407c478bd9Sstevel@tonic-gate * deletion */
9417c478bd9Sstevel@tonic-gate if( pCur->pRbtree->eTransState != TRANS_ROLLBACK ){
9427c478bd9Sstevel@tonic-gate BtRollbackOp *pOp = sqliteMalloc( sizeof(BtRollbackOp) );
9437c478bd9Sstevel@tonic-gate if( pOp==0 ) return SQLITE_NOMEM;
9447c478bd9Sstevel@tonic-gate pOp->iTab = pCur->iTree;
9457c478bd9Sstevel@tonic-gate pOp->nKey = pZ->nKey;
9467c478bd9Sstevel@tonic-gate pOp->pKey = pZ->pKey;
9477c478bd9Sstevel@tonic-gate pOp->nData = pZ->nData;
9487c478bd9Sstevel@tonic-gate pOp->pData = pZ->pData;
9497c478bd9Sstevel@tonic-gate pOp->eOp = ROLLBACK_INSERT;
9507c478bd9Sstevel@tonic-gate btreeLogRollbackOp(pCur->pRbtree, pOp);
9517c478bd9Sstevel@tonic-gate }
9527c478bd9Sstevel@tonic-gate
9537c478bd9Sstevel@tonic-gate /* First do a standard binary-tree delete (node pZ is to be deleted). How
9547c478bd9Sstevel@tonic-gate * to do this depends on how many children pZ has:
9557c478bd9Sstevel@tonic-gate *
9567c478bd9Sstevel@tonic-gate * If pZ has no children or one child, then splice out pZ. If pZ has two
9577c478bd9Sstevel@tonic-gate * children, splice out the successor of pZ and replace the key and data of
9587c478bd9Sstevel@tonic-gate * pZ with the key and data of the spliced out successor. */
9597c478bd9Sstevel@tonic-gate if( pZ->pLeft && pZ->pRight ){
9607c478bd9Sstevel@tonic-gate BtRbNode *pTmp;
9617c478bd9Sstevel@tonic-gate int dummy;
9627c478bd9Sstevel@tonic-gate pCur->eSkip = SKIP_NONE;
9637c478bd9Sstevel@tonic-gate memRbtreeNext(pCur, &dummy);
9647c478bd9Sstevel@tonic-gate assert( dummy == 0 );
9657c478bd9Sstevel@tonic-gate if( pCur->pRbtree->eTransState == TRANS_ROLLBACK ){
9667c478bd9Sstevel@tonic-gate sqliteFree(pZ->pKey);
9677c478bd9Sstevel@tonic-gate sqliteFree(pZ->pData);
9687c478bd9Sstevel@tonic-gate }
9697c478bd9Sstevel@tonic-gate pZ->pData = pCur->pNode->pData;
9707c478bd9Sstevel@tonic-gate pZ->nData = pCur->pNode->nData;
9717c478bd9Sstevel@tonic-gate pZ->pKey = pCur->pNode->pKey;
9727c478bd9Sstevel@tonic-gate pZ->nKey = pCur->pNode->nKey;
9737c478bd9Sstevel@tonic-gate pTmp = pZ;
9747c478bd9Sstevel@tonic-gate pZ = pCur->pNode;
9757c478bd9Sstevel@tonic-gate pCur->pNode = pTmp;
9767c478bd9Sstevel@tonic-gate pCur->eSkip = SKIP_NEXT;
9777c478bd9Sstevel@tonic-gate }else{
9787c478bd9Sstevel@tonic-gate int res;
9797c478bd9Sstevel@tonic-gate pCur->eSkip = SKIP_NONE;
9807c478bd9Sstevel@tonic-gate memRbtreeNext(pCur, &res);
9817c478bd9Sstevel@tonic-gate pCur->eSkip = SKIP_NEXT;
9827c478bd9Sstevel@tonic-gate if( res ){
9837c478bd9Sstevel@tonic-gate memRbtreeLast(pCur, &res);
9847c478bd9Sstevel@tonic-gate memRbtreePrevious(pCur, &res);
9857c478bd9Sstevel@tonic-gate pCur->eSkip = SKIP_PREV;
9867c478bd9Sstevel@tonic-gate }
9877c478bd9Sstevel@tonic-gate if( pCur->pRbtree->eTransState == TRANS_ROLLBACK ){
9887c478bd9Sstevel@tonic-gate sqliteFree(pZ->pKey);
9897c478bd9Sstevel@tonic-gate sqliteFree(pZ->pData);
9907c478bd9Sstevel@tonic-gate }
9917c478bd9Sstevel@tonic-gate }
9927c478bd9Sstevel@tonic-gate
993*1da57d55SToomas Soome /* pZ now points at the node to be spliced out. This block does the
9947c478bd9Sstevel@tonic-gate * splicing. */
9957c478bd9Sstevel@tonic-gate {
9967c478bd9Sstevel@tonic-gate BtRbNode **ppParentSlot = 0;
9977c478bd9Sstevel@tonic-gate assert( !pZ->pLeft || !pZ->pRight ); /* pZ has at most one child */
9987c478bd9Sstevel@tonic-gate pChild = ((pZ->pLeft)?pZ->pLeft:pZ->pRight);
9997c478bd9Sstevel@tonic-gate if( pZ->pParent ){
10007c478bd9Sstevel@tonic-gate assert( pZ == pZ->pParent->pLeft || pZ == pZ->pParent->pRight );
10017c478bd9Sstevel@tonic-gate ppParentSlot = ((pZ == pZ->pParent->pLeft)
10027c478bd9Sstevel@tonic-gate ?&pZ->pParent->pLeft:&pZ->pParent->pRight);
10037c478bd9Sstevel@tonic-gate *ppParentSlot = pChild;
10047c478bd9Sstevel@tonic-gate }else{
10057c478bd9Sstevel@tonic-gate pCur->pTree->pHead = pChild;
10067c478bd9Sstevel@tonic-gate }
10077c478bd9Sstevel@tonic-gate if( pChild ) pChild->pParent = pZ->pParent;
10087c478bd9Sstevel@tonic-gate }
10097c478bd9Sstevel@tonic-gate
10107c478bd9Sstevel@tonic-gate /* pZ now points at the spliced out node. pChild is the only child of pZ, or
10117c478bd9Sstevel@tonic-gate * NULL if pZ has no children. If pZ is black, and not the tree root, then we
10127c478bd9Sstevel@tonic-gate * will have violated the "same number of black nodes in every path to a
10137c478bd9Sstevel@tonic-gate * leaf" property of the red-black tree. The code in do_delete_balancing()
10147c478bd9Sstevel@tonic-gate * repairs this. */
1015*1da57d55SToomas Soome if( pZ->isBlack ){
10167c478bd9Sstevel@tonic-gate do_delete_balancing(pCur->pTree, pChild, pZ->pParent);
10177c478bd9Sstevel@tonic-gate }
10187c478bd9Sstevel@tonic-gate
10197c478bd9Sstevel@tonic-gate sqliteFree(pZ);
10207c478bd9Sstevel@tonic-gate return SQLITE_OK;
10217c478bd9Sstevel@tonic-gate }
10227c478bd9Sstevel@tonic-gate
10237c478bd9Sstevel@tonic-gate /*
10247c478bd9Sstevel@tonic-gate * Empty table n of the Rbtree.
10257c478bd9Sstevel@tonic-gate */
memRbtreeClearTable(Rbtree * tree,int n)10267c478bd9Sstevel@tonic-gate static int memRbtreeClearTable(Rbtree* tree, int n)
10277c478bd9Sstevel@tonic-gate {
10287c478bd9Sstevel@tonic-gate BtRbTree *pTree;
10297c478bd9Sstevel@tonic-gate BtRbNode *pNode;
10307c478bd9Sstevel@tonic-gate
10317c478bd9Sstevel@tonic-gate pTree = sqliteHashFind(&tree->tblHash, 0, n);
10327c478bd9Sstevel@tonic-gate assert(pTree);
10337c478bd9Sstevel@tonic-gate
10347c478bd9Sstevel@tonic-gate pNode = pTree->pHead;
10357c478bd9Sstevel@tonic-gate while( pNode ){
10367c478bd9Sstevel@tonic-gate if( pNode->pLeft ){
10377c478bd9Sstevel@tonic-gate pNode = pNode->pLeft;
10387c478bd9Sstevel@tonic-gate }
10397c478bd9Sstevel@tonic-gate else if( pNode->pRight ){
10407c478bd9Sstevel@tonic-gate pNode = pNode->pRight;
10417c478bd9Sstevel@tonic-gate }
10427c478bd9Sstevel@tonic-gate else {
10437c478bd9Sstevel@tonic-gate BtRbNode *pTmp = pNode->pParent;
10447c478bd9Sstevel@tonic-gate if( tree->eTransState == TRANS_ROLLBACK ){
10457c478bd9Sstevel@tonic-gate sqliteFree( pNode->pKey );
10467c478bd9Sstevel@tonic-gate sqliteFree( pNode->pData );
10477c478bd9Sstevel@tonic-gate }else{
10487c478bd9Sstevel@tonic-gate BtRollbackOp *pRollbackOp = sqliteMallocRaw(sizeof(BtRollbackOp));
10497c478bd9Sstevel@tonic-gate if( pRollbackOp==0 ) return SQLITE_NOMEM;
10507c478bd9Sstevel@tonic-gate pRollbackOp->eOp = ROLLBACK_INSERT;
10517c478bd9Sstevel@tonic-gate pRollbackOp->iTab = n;
10527c478bd9Sstevel@tonic-gate pRollbackOp->nKey = pNode->nKey;
10537c478bd9Sstevel@tonic-gate pRollbackOp->pKey = pNode->pKey;
10547c478bd9Sstevel@tonic-gate pRollbackOp->nData = pNode->nData;
10557c478bd9Sstevel@tonic-gate pRollbackOp->pData = pNode->pData;
10567c478bd9Sstevel@tonic-gate btreeLogRollbackOp(tree, pRollbackOp);
10577c478bd9Sstevel@tonic-gate }
10587c478bd9Sstevel@tonic-gate sqliteFree( pNode );
10597c478bd9Sstevel@tonic-gate if( pTmp ){
10607c478bd9Sstevel@tonic-gate if( pTmp->pLeft == pNode ) pTmp->pLeft = 0;
10617c478bd9Sstevel@tonic-gate else if( pTmp->pRight == pNode ) pTmp->pRight = 0;
10627c478bd9Sstevel@tonic-gate }
10637c478bd9Sstevel@tonic-gate pNode = pTmp;
10647c478bd9Sstevel@tonic-gate }
10657c478bd9Sstevel@tonic-gate }
10667c478bd9Sstevel@tonic-gate
10677c478bd9Sstevel@tonic-gate pTree->pHead = 0;
10687c478bd9Sstevel@tonic-gate return SQLITE_OK;
10697c478bd9Sstevel@tonic-gate }
10707c478bd9Sstevel@tonic-gate
memRbtreeFirst(RbtCursor * pCur,int * pRes)10717c478bd9Sstevel@tonic-gate static int memRbtreeFirst(RbtCursor* pCur, int *pRes)
10727c478bd9Sstevel@tonic-gate {
10737c478bd9Sstevel@tonic-gate if( pCur->pTree->pHead ){
10747c478bd9Sstevel@tonic-gate pCur->pNode = pCur->pTree->pHead;
10757c478bd9Sstevel@tonic-gate while( pCur->pNode->pLeft ){
10767c478bd9Sstevel@tonic-gate pCur->pNode = pCur->pNode->pLeft;
10777c478bd9Sstevel@tonic-gate }
10787c478bd9Sstevel@tonic-gate }
10797c478bd9Sstevel@tonic-gate if( pCur->pNode ){
10807c478bd9Sstevel@tonic-gate *pRes = 0;
10817c478bd9Sstevel@tonic-gate }else{
10827c478bd9Sstevel@tonic-gate *pRes = 1;
10837c478bd9Sstevel@tonic-gate }
10847c478bd9Sstevel@tonic-gate pCur->eSkip = SKIP_NONE;
10857c478bd9Sstevel@tonic-gate return SQLITE_OK;
10867c478bd9Sstevel@tonic-gate }
10877c478bd9Sstevel@tonic-gate
memRbtreeLast(RbtCursor * pCur,int * pRes)10887c478bd9Sstevel@tonic-gate static int memRbtreeLast(RbtCursor* pCur, int *pRes)
10897c478bd9Sstevel@tonic-gate {
10907c478bd9Sstevel@tonic-gate if( pCur->pTree->pHead ){
10917c478bd9Sstevel@tonic-gate pCur->pNode = pCur->pTree->pHead;
10927c478bd9Sstevel@tonic-gate while( pCur->pNode->pRight ){
10937c478bd9Sstevel@tonic-gate pCur->pNode = pCur->pNode->pRight;
10947c478bd9Sstevel@tonic-gate }
10957c478bd9Sstevel@tonic-gate }
10967c478bd9Sstevel@tonic-gate if( pCur->pNode ){
10977c478bd9Sstevel@tonic-gate *pRes = 0;
10987c478bd9Sstevel@tonic-gate }else{
10997c478bd9Sstevel@tonic-gate *pRes = 1;
11007c478bd9Sstevel@tonic-gate }
11017c478bd9Sstevel@tonic-gate pCur->eSkip = SKIP_NONE;
11027c478bd9Sstevel@tonic-gate return SQLITE_OK;
11037c478bd9Sstevel@tonic-gate }
11047c478bd9Sstevel@tonic-gate
11057c478bd9Sstevel@tonic-gate /*
11067c478bd9Sstevel@tonic-gate ** Advance the cursor to the next entry in the database. If
11077c478bd9Sstevel@tonic-gate ** successful then set *pRes=0. If the cursor
11087c478bd9Sstevel@tonic-gate ** was already pointing to the last entry in the database before
11097c478bd9Sstevel@tonic-gate ** this routine was called, then set *pRes=1.
11107c478bd9Sstevel@tonic-gate */
memRbtreeNext(RbtCursor * pCur,int * pRes)11117c478bd9Sstevel@tonic-gate static int memRbtreeNext(RbtCursor* pCur, int *pRes)
11127c478bd9Sstevel@tonic-gate {
11137c478bd9Sstevel@tonic-gate if( pCur->pNode && pCur->eSkip != SKIP_NEXT ){
11147c478bd9Sstevel@tonic-gate if( pCur->pNode->pRight ){
11157c478bd9Sstevel@tonic-gate pCur->pNode = pCur->pNode->pRight;
11167c478bd9Sstevel@tonic-gate while( pCur->pNode->pLeft )
11177c478bd9Sstevel@tonic-gate pCur->pNode = pCur->pNode->pLeft;
11187c478bd9Sstevel@tonic-gate }else{
11197c478bd9Sstevel@tonic-gate BtRbNode * pX = pCur->pNode;
11207c478bd9Sstevel@tonic-gate pCur->pNode = pX->pParent;
11217c478bd9Sstevel@tonic-gate while( pCur->pNode && (pCur->pNode->pRight == pX) ){
11227c478bd9Sstevel@tonic-gate pX = pCur->pNode;
11237c478bd9Sstevel@tonic-gate pCur->pNode = pX->pParent;
11247c478bd9Sstevel@tonic-gate }
11257c478bd9Sstevel@tonic-gate }
11267c478bd9Sstevel@tonic-gate }
11277c478bd9Sstevel@tonic-gate pCur->eSkip = SKIP_NONE;
11287c478bd9Sstevel@tonic-gate
11297c478bd9Sstevel@tonic-gate if( !pCur->pNode ){
11307c478bd9Sstevel@tonic-gate *pRes = 1;
11317c478bd9Sstevel@tonic-gate }else{
11327c478bd9Sstevel@tonic-gate *pRes = 0;
11337c478bd9Sstevel@tonic-gate }
11347c478bd9Sstevel@tonic-gate
11357c478bd9Sstevel@tonic-gate return SQLITE_OK;
11367c478bd9Sstevel@tonic-gate }
11377c478bd9Sstevel@tonic-gate
memRbtreePrevious(RbtCursor * pCur,int * pRes)11387c478bd9Sstevel@tonic-gate static int memRbtreePrevious(RbtCursor* pCur, int *pRes)
11397c478bd9Sstevel@tonic-gate {
11407c478bd9Sstevel@tonic-gate if( pCur->pNode && pCur->eSkip != SKIP_PREV ){
11417c478bd9Sstevel@tonic-gate if( pCur->pNode->pLeft ){
11427c478bd9Sstevel@tonic-gate pCur->pNode = pCur->pNode->pLeft;
11437c478bd9Sstevel@tonic-gate while( pCur->pNode->pRight )
11447c478bd9Sstevel@tonic-gate pCur->pNode = pCur->pNode->pRight;
11457c478bd9Sstevel@tonic-gate }else{
11467c478bd9Sstevel@tonic-gate BtRbNode * pX = pCur->pNode;
11477c478bd9Sstevel@tonic-gate pCur->pNode = pX->pParent;
11487c478bd9Sstevel@tonic-gate while( pCur->pNode && (pCur->pNode->pLeft == pX) ){
11497c478bd9Sstevel@tonic-gate pX = pCur->pNode;
11507c478bd9Sstevel@tonic-gate pCur->pNode = pX->pParent;
11517c478bd9Sstevel@tonic-gate }
11527c478bd9Sstevel@tonic-gate }
11537c478bd9Sstevel@tonic-gate }
11547c478bd9Sstevel@tonic-gate pCur->eSkip = SKIP_NONE;
11557c478bd9Sstevel@tonic-gate
11567c478bd9Sstevel@tonic-gate if( !pCur->pNode ){
11577c478bd9Sstevel@tonic-gate *pRes = 1;
11587c478bd9Sstevel@tonic-gate }else{
11597c478bd9Sstevel@tonic-gate *pRes = 0;
11607c478bd9Sstevel@tonic-gate }
11617c478bd9Sstevel@tonic-gate
11627c478bd9Sstevel@tonic-gate return SQLITE_OK;
11637c478bd9Sstevel@tonic-gate }
11647c478bd9Sstevel@tonic-gate
memRbtreeKeySize(RbtCursor * pCur,int * pSize)11657c478bd9Sstevel@tonic-gate static int memRbtreeKeySize(RbtCursor* pCur, int *pSize)
11667c478bd9Sstevel@tonic-gate {
11677c478bd9Sstevel@tonic-gate if( pCur->pNode ){
11687c478bd9Sstevel@tonic-gate *pSize = pCur->pNode->nKey;
11697c478bd9Sstevel@tonic-gate }else{
11707c478bd9Sstevel@tonic-gate *pSize = 0;
11717c478bd9Sstevel@tonic-gate }
11727c478bd9Sstevel@tonic-gate return SQLITE_OK;
11737c478bd9Sstevel@tonic-gate }
11747c478bd9Sstevel@tonic-gate
memRbtreeKey(RbtCursor * pCur,int offset,int amt,char * zBuf)11757c478bd9Sstevel@tonic-gate static int memRbtreeKey(RbtCursor* pCur, int offset, int amt, char *zBuf)
11767c478bd9Sstevel@tonic-gate {
11777c478bd9Sstevel@tonic-gate if( !pCur->pNode ) return 0;
11787c478bd9Sstevel@tonic-gate if( !pCur->pNode->pKey || ((amt + offset) <= pCur->pNode->nKey) ){
11797c478bd9Sstevel@tonic-gate memcpy(zBuf, ((char*)pCur->pNode->pKey)+offset, amt);
11807c478bd9Sstevel@tonic-gate }else{
11817c478bd9Sstevel@tonic-gate memcpy(zBuf, ((char*)pCur->pNode->pKey)+offset, pCur->pNode->nKey-offset);
11827c478bd9Sstevel@tonic-gate amt = pCur->pNode->nKey-offset;
11837c478bd9Sstevel@tonic-gate }
11847c478bd9Sstevel@tonic-gate return amt;
11857c478bd9Sstevel@tonic-gate }
11867c478bd9Sstevel@tonic-gate
memRbtreeDataSize(RbtCursor * pCur,int * pSize)11877c478bd9Sstevel@tonic-gate static int memRbtreeDataSize(RbtCursor* pCur, int *pSize)
11887c478bd9Sstevel@tonic-gate {
11897c478bd9Sstevel@tonic-gate if( pCur->pNode ){
11907c478bd9Sstevel@tonic-gate *pSize = pCur->pNode->nData;
11917c478bd9Sstevel@tonic-gate }else{
11927c478bd9Sstevel@tonic-gate *pSize = 0;
11937c478bd9Sstevel@tonic-gate }
11947c478bd9Sstevel@tonic-gate return SQLITE_OK;
11957c478bd9Sstevel@tonic-gate }
11967c478bd9Sstevel@tonic-gate
memRbtreeData(RbtCursor * pCur,int offset,int amt,char * zBuf)11977c478bd9Sstevel@tonic-gate static int memRbtreeData(RbtCursor *pCur, int offset, int amt, char *zBuf)
11987c478bd9Sstevel@tonic-gate {
11997c478bd9Sstevel@tonic-gate if( !pCur->pNode ) return 0;
12007c478bd9Sstevel@tonic-gate if( (amt + offset) <= pCur->pNode->nData ){
12017c478bd9Sstevel@tonic-gate memcpy(zBuf, ((char*)pCur->pNode->pData)+offset, amt);
12027c478bd9Sstevel@tonic-gate }else{
12037c478bd9Sstevel@tonic-gate memcpy(zBuf, ((char*)pCur->pNode->pData)+offset ,pCur->pNode->nData-offset);
12047c478bd9Sstevel@tonic-gate amt = pCur->pNode->nData-offset;
12057c478bd9Sstevel@tonic-gate }
12067c478bd9Sstevel@tonic-gate return amt;
12077c478bd9Sstevel@tonic-gate }
12087c478bd9Sstevel@tonic-gate
memRbtreeCloseCursor(RbtCursor * pCur)12097c478bd9Sstevel@tonic-gate static int memRbtreeCloseCursor(RbtCursor* pCur)
12107c478bd9Sstevel@tonic-gate {
12117c478bd9Sstevel@tonic-gate if( pCur->pTree->pCursors==pCur ){
12127c478bd9Sstevel@tonic-gate pCur->pTree->pCursors = pCur->pShared;
12137c478bd9Sstevel@tonic-gate }else{
12147c478bd9Sstevel@tonic-gate RbtCursor *p = pCur->pTree->pCursors;
12157c478bd9Sstevel@tonic-gate while( p && p->pShared!=pCur ){ p = p->pShared; }
12167c478bd9Sstevel@tonic-gate assert( p!=0 );
12177c478bd9Sstevel@tonic-gate if( p ){
12187c478bd9Sstevel@tonic-gate p->pShared = pCur->pShared;
12197c478bd9Sstevel@tonic-gate }
12207c478bd9Sstevel@tonic-gate }
12217c478bd9Sstevel@tonic-gate sqliteFree(pCur);
12227c478bd9Sstevel@tonic-gate return SQLITE_OK;
12237c478bd9Sstevel@tonic-gate }
12247c478bd9Sstevel@tonic-gate
memRbtreeGetMeta(Rbtree * tree,int * aMeta)12257c478bd9Sstevel@tonic-gate static int memRbtreeGetMeta(Rbtree* tree, int* aMeta)
12267c478bd9Sstevel@tonic-gate {
12277c478bd9Sstevel@tonic-gate memcpy( aMeta, tree->aMetaData, sizeof(int) * SQLITE_N_BTREE_META );
12287c478bd9Sstevel@tonic-gate return SQLITE_OK;
12297c478bd9Sstevel@tonic-gate }
12307c478bd9Sstevel@tonic-gate
memRbtreeUpdateMeta(Rbtree * tree,int * aMeta)12317c478bd9Sstevel@tonic-gate static int memRbtreeUpdateMeta(Rbtree* tree, int* aMeta)
12327c478bd9Sstevel@tonic-gate {
12337c478bd9Sstevel@tonic-gate memcpy( tree->aMetaData, aMeta, sizeof(int) * SQLITE_N_BTREE_META );
12347c478bd9Sstevel@tonic-gate return SQLITE_OK;
12357c478bd9Sstevel@tonic-gate }
12367c478bd9Sstevel@tonic-gate
12377c478bd9Sstevel@tonic-gate /*
12387c478bd9Sstevel@tonic-gate * Check that each table in the Rbtree meets the requirements for a red-black
1239*1da57d55SToomas Soome * binary tree. If an error is found, return an explanation of the problem in
1240*1da57d55SToomas Soome * memory obtained from sqliteMalloc(). Parameters aRoot and nRoot are ignored.
12417c478bd9Sstevel@tonic-gate */
memRbtreeIntegrityCheck(Rbtree * tree,int * aRoot,int nRoot)12427c478bd9Sstevel@tonic-gate static char *memRbtreeIntegrityCheck(Rbtree* tree, int* aRoot, int nRoot)
12437c478bd9Sstevel@tonic-gate {
12447c478bd9Sstevel@tonic-gate char * msg = 0;
12457c478bd9Sstevel@tonic-gate HashElem *p;
12467c478bd9Sstevel@tonic-gate
12477c478bd9Sstevel@tonic-gate for(p=sqliteHashFirst(&tree->tblHash); p; p=sqliteHashNext(p)){
12487c478bd9Sstevel@tonic-gate BtRbTree *pTree = sqliteHashData(p);
12497c478bd9Sstevel@tonic-gate check_redblack_tree(pTree, &msg);
12507c478bd9Sstevel@tonic-gate }
12517c478bd9Sstevel@tonic-gate
12527c478bd9Sstevel@tonic-gate return msg;
12537c478bd9Sstevel@tonic-gate }
12547c478bd9Sstevel@tonic-gate
memRbtreeSetCacheSize(Rbtree * tree,int sz)12557c478bd9Sstevel@tonic-gate static int memRbtreeSetCacheSize(Rbtree* tree, int sz)
12567c478bd9Sstevel@tonic-gate {
12577c478bd9Sstevel@tonic-gate return SQLITE_OK;
12587c478bd9Sstevel@tonic-gate }
12597c478bd9Sstevel@tonic-gate
memRbtreeSetSafetyLevel(Rbtree * pBt,int level)12607c478bd9Sstevel@tonic-gate static int memRbtreeSetSafetyLevel(Rbtree *pBt, int level){
12617c478bd9Sstevel@tonic-gate return SQLITE_OK;
12627c478bd9Sstevel@tonic-gate }
12637c478bd9Sstevel@tonic-gate
memRbtreeBeginTrans(Rbtree * tree)12647c478bd9Sstevel@tonic-gate static int memRbtreeBeginTrans(Rbtree* tree)
12657c478bd9Sstevel@tonic-gate {
1266*1da57d55SToomas Soome if( tree->eTransState != TRANS_NONE )
12677c478bd9Sstevel@tonic-gate return SQLITE_ERROR;
12687c478bd9Sstevel@tonic-gate
12697c478bd9Sstevel@tonic-gate assert( tree->pTransRollback == 0 );
12707c478bd9Sstevel@tonic-gate tree->eTransState = TRANS_INTRANSACTION;
12717c478bd9Sstevel@tonic-gate return SQLITE_OK;
12727c478bd9Sstevel@tonic-gate }
12737c478bd9Sstevel@tonic-gate
12747c478bd9Sstevel@tonic-gate /*
12757c478bd9Sstevel@tonic-gate ** Delete a linked list of BtRollbackOp structures.
12767c478bd9Sstevel@tonic-gate */
deleteRollbackList(BtRollbackOp * pOp)12777c478bd9Sstevel@tonic-gate static void deleteRollbackList(BtRollbackOp *pOp){
12787c478bd9Sstevel@tonic-gate while( pOp ){
12797c478bd9Sstevel@tonic-gate BtRollbackOp *pTmp = pOp->pNext;
12807c478bd9Sstevel@tonic-gate sqliteFree(pOp->pData);
12817c478bd9Sstevel@tonic-gate sqliteFree(pOp->pKey);
12827c478bd9Sstevel@tonic-gate sqliteFree(pOp);
12837c478bd9Sstevel@tonic-gate pOp = pTmp;
12847c478bd9Sstevel@tonic-gate }
12857c478bd9Sstevel@tonic-gate }
12867c478bd9Sstevel@tonic-gate
memRbtreeCommit(Rbtree * tree)12877c478bd9Sstevel@tonic-gate static int memRbtreeCommit(Rbtree* tree){
12887c478bd9Sstevel@tonic-gate /* Just delete pTransRollback and pCheckRollback */
12897c478bd9Sstevel@tonic-gate deleteRollbackList(tree->pCheckRollback);
12907c478bd9Sstevel@tonic-gate deleteRollbackList(tree->pTransRollback);
12917c478bd9Sstevel@tonic-gate tree->pTransRollback = 0;
12927c478bd9Sstevel@tonic-gate tree->pCheckRollback = 0;
12937c478bd9Sstevel@tonic-gate tree->pCheckRollbackTail = 0;
12947c478bd9Sstevel@tonic-gate tree->eTransState = TRANS_NONE;
12957c478bd9Sstevel@tonic-gate return SQLITE_OK;
12967c478bd9Sstevel@tonic-gate }
12977c478bd9Sstevel@tonic-gate
12987c478bd9Sstevel@tonic-gate /*
12997c478bd9Sstevel@tonic-gate * Close the supplied Rbtree. Delete everything associated with it.
13007c478bd9Sstevel@tonic-gate */
memRbtreeClose(Rbtree * tree)13017c478bd9Sstevel@tonic-gate static int memRbtreeClose(Rbtree* tree)
13027c478bd9Sstevel@tonic-gate {
13037c478bd9Sstevel@tonic-gate HashElem *p;
13047c478bd9Sstevel@tonic-gate memRbtreeCommit(tree);
13057c478bd9Sstevel@tonic-gate while( (p=sqliteHashFirst(&tree->tblHash))!=0 ){
13067c478bd9Sstevel@tonic-gate tree->eTransState = TRANS_ROLLBACK;
13077c478bd9Sstevel@tonic-gate memRbtreeDropTable(tree, sqliteHashKeysize(p));
13087c478bd9Sstevel@tonic-gate }
13097c478bd9Sstevel@tonic-gate sqliteHashClear(&tree->tblHash);
13107c478bd9Sstevel@tonic-gate sqliteFree(tree);
13117c478bd9Sstevel@tonic-gate return SQLITE_OK;
13127c478bd9Sstevel@tonic-gate }
13137c478bd9Sstevel@tonic-gate
13147c478bd9Sstevel@tonic-gate /*
13157c478bd9Sstevel@tonic-gate * Execute and delete the supplied rollback-list on pRbtree.
13167c478bd9Sstevel@tonic-gate */
execute_rollback_list(Rbtree * pRbtree,BtRollbackOp * pList)13177c478bd9Sstevel@tonic-gate static void execute_rollback_list(Rbtree *pRbtree, BtRollbackOp *pList)
13187c478bd9Sstevel@tonic-gate {
13197c478bd9Sstevel@tonic-gate BtRollbackOp *pTmp;
13207c478bd9Sstevel@tonic-gate RbtCursor cur;
13217c478bd9Sstevel@tonic-gate int res;
13227c478bd9Sstevel@tonic-gate
13237c478bd9Sstevel@tonic-gate cur.pRbtree = pRbtree;
13247c478bd9Sstevel@tonic-gate cur.wrFlag = 1;
13257c478bd9Sstevel@tonic-gate while( pList ){
13267c478bd9Sstevel@tonic-gate switch( pList->eOp ){
13277c478bd9Sstevel@tonic-gate case ROLLBACK_INSERT:
13287c478bd9Sstevel@tonic-gate cur.pTree = sqliteHashFind( &pRbtree->tblHash, 0, pList->iTab );
13297c478bd9Sstevel@tonic-gate assert(cur.pTree);
13307c478bd9Sstevel@tonic-gate cur.iTree = pList->iTab;
13317c478bd9Sstevel@tonic-gate cur.eSkip = SKIP_NONE;
13327c478bd9Sstevel@tonic-gate memRbtreeInsert( &cur, pList->pKey,
13337c478bd9Sstevel@tonic-gate pList->nKey, pList->pData, pList->nData );
13347c478bd9Sstevel@tonic-gate break;
13357c478bd9Sstevel@tonic-gate case ROLLBACK_DELETE:
13367c478bd9Sstevel@tonic-gate cur.pTree = sqliteHashFind( &pRbtree->tblHash, 0, pList->iTab );
13377c478bd9Sstevel@tonic-gate assert(cur.pTree);
13387c478bd9Sstevel@tonic-gate cur.iTree = pList->iTab;
13397c478bd9Sstevel@tonic-gate cur.eSkip = SKIP_NONE;
13407c478bd9Sstevel@tonic-gate memRbtreeMoveto(&cur, pList->pKey, pList->nKey, &res);
13417c478bd9Sstevel@tonic-gate assert(res == 0);
13427c478bd9Sstevel@tonic-gate memRbtreeDelete( &cur );
13437c478bd9Sstevel@tonic-gate break;
13447c478bd9Sstevel@tonic-gate case ROLLBACK_CREATE:
13457c478bd9Sstevel@tonic-gate btreeCreateTable(pRbtree, pList->iTab);
13467c478bd9Sstevel@tonic-gate break;
13477c478bd9Sstevel@tonic-gate case ROLLBACK_DROP:
13487c478bd9Sstevel@tonic-gate memRbtreeDropTable(pRbtree, pList->iTab);
13497c478bd9Sstevel@tonic-gate break;
13507c478bd9Sstevel@tonic-gate default:
13517c478bd9Sstevel@tonic-gate assert(0);
13527c478bd9Sstevel@tonic-gate }
13537c478bd9Sstevel@tonic-gate sqliteFree(pList->pKey);
13547c478bd9Sstevel@tonic-gate sqliteFree(pList->pData);
13557c478bd9Sstevel@tonic-gate pTmp = pList->pNext;
13567c478bd9Sstevel@tonic-gate sqliteFree(pList);
13577c478bd9Sstevel@tonic-gate pList = pTmp;
13587c478bd9Sstevel@tonic-gate }
13597c478bd9Sstevel@tonic-gate }
13607c478bd9Sstevel@tonic-gate
memRbtreeRollback(Rbtree * tree)13617c478bd9Sstevel@tonic-gate static int memRbtreeRollback(Rbtree* tree)
13627c478bd9Sstevel@tonic-gate {
13637c478bd9Sstevel@tonic-gate tree->eTransState = TRANS_ROLLBACK;
13647c478bd9Sstevel@tonic-gate execute_rollback_list(tree, tree->pCheckRollback);
13657c478bd9Sstevel@tonic-gate execute_rollback_list(tree, tree->pTransRollback);
13667c478bd9Sstevel@tonic-gate tree->pTransRollback = 0;
13677c478bd9Sstevel@tonic-gate tree->pCheckRollback = 0;
13687c478bd9Sstevel@tonic-gate tree->pCheckRollbackTail = 0;
13697c478bd9Sstevel@tonic-gate tree->eTransState = TRANS_NONE;
13707c478bd9Sstevel@tonic-gate return SQLITE_OK;
13717c478bd9Sstevel@tonic-gate }
13727c478bd9Sstevel@tonic-gate
memRbtreeBeginCkpt(Rbtree * tree)13737c478bd9Sstevel@tonic-gate static int memRbtreeBeginCkpt(Rbtree* tree)
13747c478bd9Sstevel@tonic-gate {
1375*1da57d55SToomas Soome if( tree->eTransState != TRANS_INTRANSACTION )
13767c478bd9Sstevel@tonic-gate return SQLITE_ERROR;
13777c478bd9Sstevel@tonic-gate
13787c478bd9Sstevel@tonic-gate assert( tree->pCheckRollback == 0 );
13797c478bd9Sstevel@tonic-gate assert( tree->pCheckRollbackTail == 0 );
13807c478bd9Sstevel@tonic-gate tree->eTransState = TRANS_INCHECKPOINT;
13817c478bd9Sstevel@tonic-gate return SQLITE_OK;
13827c478bd9Sstevel@tonic-gate }
13837c478bd9Sstevel@tonic-gate
memRbtreeCommitCkpt(Rbtree * tree)13847c478bd9Sstevel@tonic-gate static int memRbtreeCommitCkpt(Rbtree* tree)
13857c478bd9Sstevel@tonic-gate {
1386*1da57d55SToomas Soome if( tree->eTransState == TRANS_INCHECKPOINT ){
13877c478bd9Sstevel@tonic-gate if( tree->pCheckRollback ){
13887c478bd9Sstevel@tonic-gate tree->pCheckRollbackTail->pNext = tree->pTransRollback;
13897c478bd9Sstevel@tonic-gate tree->pTransRollback = tree->pCheckRollback;
13907c478bd9Sstevel@tonic-gate tree->pCheckRollback = 0;
13917c478bd9Sstevel@tonic-gate tree->pCheckRollbackTail = 0;
13927c478bd9Sstevel@tonic-gate }
13937c478bd9Sstevel@tonic-gate tree->eTransState = TRANS_INTRANSACTION;
13947c478bd9Sstevel@tonic-gate }
13957c478bd9Sstevel@tonic-gate return SQLITE_OK;
13967c478bd9Sstevel@tonic-gate }
13977c478bd9Sstevel@tonic-gate
memRbtreeRollbackCkpt(Rbtree * tree)13987c478bd9Sstevel@tonic-gate static int memRbtreeRollbackCkpt(Rbtree* tree)
13997c478bd9Sstevel@tonic-gate {
14007c478bd9Sstevel@tonic-gate if( tree->eTransState != TRANS_INCHECKPOINT ) return SQLITE_OK;
14017c478bd9Sstevel@tonic-gate tree->eTransState = TRANS_ROLLBACK;
14027c478bd9Sstevel@tonic-gate execute_rollback_list(tree, tree->pCheckRollback);
14037c478bd9Sstevel@tonic-gate tree->pCheckRollback = 0;
14047c478bd9Sstevel@tonic-gate tree->pCheckRollbackTail = 0;
14057c478bd9Sstevel@tonic-gate tree->eTransState = TRANS_INTRANSACTION;
14067c478bd9Sstevel@tonic-gate return SQLITE_OK;
14077c478bd9Sstevel@tonic-gate }
14087c478bd9Sstevel@tonic-gate
14097c478bd9Sstevel@tonic-gate #ifdef SQLITE_TEST
memRbtreePageDump(Rbtree * tree,int pgno,int rec)14107c478bd9Sstevel@tonic-gate static int memRbtreePageDump(Rbtree* tree, int pgno, int rec)
14117c478bd9Sstevel@tonic-gate {
14127c478bd9Sstevel@tonic-gate assert(!"Cannot call sqliteRbtreePageDump");
14137c478bd9Sstevel@tonic-gate return SQLITE_OK;
14147c478bd9Sstevel@tonic-gate }
14157c478bd9Sstevel@tonic-gate
memRbtreeCursorDump(RbtCursor * pCur,int * aRes)14167c478bd9Sstevel@tonic-gate static int memRbtreeCursorDump(RbtCursor* pCur, int* aRes)
14177c478bd9Sstevel@tonic-gate {
14187c478bd9Sstevel@tonic-gate assert(!"Cannot call sqliteRbtreeCursorDump");
14197c478bd9Sstevel@tonic-gate return SQLITE_OK;
14207c478bd9Sstevel@tonic-gate }
14217c478bd9Sstevel@tonic-gate #endif
14227c478bd9Sstevel@tonic-gate
memRbtreePager(Rbtree * tree)14237c478bd9Sstevel@tonic-gate static struct Pager *memRbtreePager(Rbtree* tree)
14247c478bd9Sstevel@tonic-gate {
14257c478bd9Sstevel@tonic-gate return 0;
14267c478bd9Sstevel@tonic-gate }
14277c478bd9Sstevel@tonic-gate
14287c478bd9Sstevel@tonic-gate /*
14297c478bd9Sstevel@tonic-gate ** Return the full pathname of the underlying database file.
14307c478bd9Sstevel@tonic-gate */
memRbtreeGetFilename(Rbtree * pBt)14317c478bd9Sstevel@tonic-gate static const char *memRbtreeGetFilename(Rbtree *pBt){
14327c478bd9Sstevel@tonic-gate return 0; /* A NULL return indicates there is no underlying file */
14337c478bd9Sstevel@tonic-gate }
14347c478bd9Sstevel@tonic-gate
14357c478bd9Sstevel@tonic-gate /*
14367c478bd9Sstevel@tonic-gate ** The copy file function is not implemented for the in-memory database
14377c478bd9Sstevel@tonic-gate */
memRbtreeCopyFile(Rbtree * pBt,Rbtree * pBt2)14387c478bd9Sstevel@tonic-gate static int memRbtreeCopyFile(Rbtree *pBt, Rbtree *pBt2){
14397c478bd9Sstevel@tonic-gate return SQLITE_INTERNAL; /* Not implemented */
14407c478bd9Sstevel@tonic-gate }
14417c478bd9Sstevel@tonic-gate
14427c478bd9Sstevel@tonic-gate static BtOps sqliteRbtreeOps = {
14437c478bd9Sstevel@tonic-gate (int(*)(Btree*)) memRbtreeClose,
14447c478bd9Sstevel@tonic-gate (int(*)(Btree*,int)) memRbtreeSetCacheSize,
14457c478bd9Sstevel@tonic-gate (int(*)(Btree*,int)) memRbtreeSetSafetyLevel,
14467c478bd9Sstevel@tonic-gate (int(*)(Btree*)) memRbtreeBeginTrans,
14477c478bd9Sstevel@tonic-gate (int(*)(Btree*)) memRbtreeCommit,
14487c478bd9Sstevel@tonic-gate (int(*)(Btree*)) memRbtreeRollback,
14497c478bd9Sstevel@tonic-gate (int(*)(Btree*)) memRbtreeBeginCkpt,
14507c478bd9Sstevel@tonic-gate (int(*)(Btree*)) memRbtreeCommitCkpt,
14517c478bd9Sstevel@tonic-gate (int(*)(Btree*)) memRbtreeRollbackCkpt,
14527c478bd9Sstevel@tonic-gate (int(*)(Btree*,int*)) memRbtreeCreateTable,
14537c478bd9Sstevel@tonic-gate (int(*)(Btree*,int*)) memRbtreeCreateTable,
14547c478bd9Sstevel@tonic-gate (int(*)(Btree*,int)) memRbtreeDropTable,
14557c478bd9Sstevel@tonic-gate (int(*)(Btree*,int)) memRbtreeClearTable,
14567c478bd9Sstevel@tonic-gate (int(*)(Btree*,int,int,BtCursor**)) memRbtreeCursor,
14577c478bd9Sstevel@tonic-gate (int(*)(Btree*,int*)) memRbtreeGetMeta,
14587c478bd9Sstevel@tonic-gate (int(*)(Btree*,int*)) memRbtreeUpdateMeta,
14597c478bd9Sstevel@tonic-gate (char*(*)(Btree*,int*,int)) memRbtreeIntegrityCheck,
14607c478bd9Sstevel@tonic-gate (const char*(*)(Btree*)) memRbtreeGetFilename,
14617c478bd9Sstevel@tonic-gate (int(*)(Btree*,Btree*)) memRbtreeCopyFile,
14627c478bd9Sstevel@tonic-gate (struct Pager*(*)(Btree*)) memRbtreePager,
14637c478bd9Sstevel@tonic-gate #ifdef SQLITE_TEST
14647c478bd9Sstevel@tonic-gate (int(*)(Btree*,int,int)) memRbtreePageDump,
14657c478bd9Sstevel@tonic-gate #endif
14667c478bd9Sstevel@tonic-gate };
14677c478bd9Sstevel@tonic-gate
14687c478bd9Sstevel@tonic-gate static BtCursorOps sqliteRbtreeCursorOps = {
14697c478bd9Sstevel@tonic-gate (int(*)(BtCursor*,const void*,int,int*)) memRbtreeMoveto,
14707c478bd9Sstevel@tonic-gate (int(*)(BtCursor*)) memRbtreeDelete,
14717c478bd9Sstevel@tonic-gate (int(*)(BtCursor*,const void*,int,const void*,int)) memRbtreeInsert,
14727c478bd9Sstevel@tonic-gate (int(*)(BtCursor*,int*)) memRbtreeFirst,
14737c478bd9Sstevel@tonic-gate (int(*)(BtCursor*,int*)) memRbtreeLast,
14747c478bd9Sstevel@tonic-gate (int(*)(BtCursor*,int*)) memRbtreeNext,
14757c478bd9Sstevel@tonic-gate (int(*)(BtCursor*,int*)) memRbtreePrevious,
14767c478bd9Sstevel@tonic-gate (int(*)(BtCursor*,int*)) memRbtreeKeySize,
14777c478bd9Sstevel@tonic-gate (int(*)(BtCursor*,int,int,char*)) memRbtreeKey,
14787c478bd9Sstevel@tonic-gate (int(*)(BtCursor*,const void*,int,int,int*)) memRbtreeKeyCompare,
14797c478bd9Sstevel@tonic-gate (int(*)(BtCursor*,int*)) memRbtreeDataSize,
14807c478bd9Sstevel@tonic-gate (int(*)(BtCursor*,int,int,char*)) memRbtreeData,
14817c478bd9Sstevel@tonic-gate (int(*)(BtCursor*)) memRbtreeCloseCursor,
14827c478bd9Sstevel@tonic-gate #ifdef SQLITE_TEST
14837c478bd9Sstevel@tonic-gate (int(*)(BtCursor*,int*)) memRbtreeCursorDump,
14847c478bd9Sstevel@tonic-gate #endif
14857c478bd9Sstevel@tonic-gate
14867c478bd9Sstevel@tonic-gate };
14877c478bd9Sstevel@tonic-gate
14887c478bd9Sstevel@tonic-gate #endif /* SQLITE_OMIT_INMEMORYDB */
1489