btree_rb.c revision c5c4113dfcabb1eed3d4bdf7609de5170027a794
#pragma ident "%Z%%M% %I% %E% SMI"
/*
** 2003 Feb 4
**
** The author disclaims copyright to this source code. In place of
** a legal notice, here is a blessing:
**
** May you do good and not evil.
** May you find forgiveness for yourself and forgive others.
** May you share freely, never taking more than you give.
**
*************************************************************************
** $Id: btree_rb.c,v 1.24.2.1 2004/06/26 14:40:05 drh Exp $
**
** This file implements an in-core database using Red-Black balanced
** binary trees.
**
** It was contributed to SQLite by anonymous on 2003-Feb-04 23:24:49 UTC.
*/
#include "btree.h"
#include "sqliteInt.h"
#include <assert.h>
/*
** Omit this whole file if the SQLITE_OMIT_INMEMORYDB macro is
** defined. This allows a lot of code to be omitted for installations
** that do not need it.
*/
#ifndef SQLITE_OMIT_INMEMORYDB
typedef struct BtRollbackOp BtRollbackOp;
/* Forward declarations */
static BtOps sqliteRbtreeOps;
static BtCursorOps sqliteRbtreeCursorOps;
/*
* During each transaction (or checkpoint), a linked-list of
* "rollback-operations" is accumulated. If the transaction is rolled back,
* then the list of operations must be executed (to restore the database to
* it's state before the transaction started). If the transaction is to be
* committed, just delete the list.
*
* Each operation is represented as follows, depending on the value of eOp:
*
* ROLLBACK_INSERT -> Need to insert (pKey, pData) into table iTab.
* ROLLBACK_DELETE -> Need to delete the record (pKey) into table iTab.
* ROLLBACK_CREATE -> Need to create table iTab.
* ROLLBACK_DROP -> Need to drop table iTab.
*/
struct BtRollbackOp {
int iTab;
int nKey;
void *pKey;
int nData;
void *pData;
};
/*
** Legal values for BtRollbackOp.eOp:
*/
struct Rbtree {
int aMetaData[SQLITE_N_BTREE_META];
int next_idx; /* next available table index */
};
/*
** Legal values for Rbtree.eTransState.
*/
#define TRANS_NONE 0 /* No transaction is in progress */
* transaction. */
struct RbtCursor {
int iTree; /* Index of pTree in pRbtree */
};
/*
** Legal values for RbtCursor.eSkip.
*/
#define SKIP_NONE 0 /* Always step the cursor */
struct BtRbTree {
};
struct BtRbNode {
int nKey;
void *pKey;
int nData;
void *pData;
int nBlackHeight; /* Only used during the red-black integrity check */
};
/* Forward declarations */
static int memRbtreeMoveto(
const void *pKey,
int nKey,
int *pRes
);
/*
** This routine checks all cursors that point to the same table
** as pCur points to. If any of those cursors were opened with
** wrFlag==0 then this routine returns SQLITE_LOCKED. If all
** cursors point to the same table were opened with wrFlag==1
** then this routine returns SQLITE_OK.
**
** In addition to checking for read-locks (where a read-lock
** means a cursor opened with wrFlag==0) this routine also NULLs
** out the pNode field of all other cursors.
** This is necessary because an insert
** or delete might change erase the node out from under
** another cursor.
*/
RbtCursor *p;
if( p!=pCur ){
if( p->wrFlag==0 ) return SQLITE_LOCKED;
p->pNode = 0;
}
}
return SQLITE_OK;
}
/*
* The key-compare function for the red-black trees. Returns as follows:
*
* (key1 < key2) -1
* (key1 == key2) 0
* (key1 > key2) 1
*
* Keys are compared using memcmp(). If one key is an exact prefix of the
* other, then the shorter key is less than the longer key.
*/
{
if( mcmp == 0){
}
}
/*
* Perform the LEFT-rotate transformation on node X of tree pTree. This
* transform is part of the red-black balancing code.
*
* | |
* X Y
* / \ / \
* a Y X c
* / \ / \
* b c a b
*
* BEFORE AFTER
*/
{
}
}
/*
* Perform the RIGHT-rotate transformation on node X of tree pTree. This
* transform is part of the red-black balancing code.
*
* | |
* X Y
* / \ / \
* Y c a X
* / \ / \
* a b b c
*
* BEFORE AFTER
*/
{
}
}
/*
* A string-manipulation helper function for check_redblack_tree(). If (orig ==
* NULL) a copy of val is returned. If (orig != NULL) then a copy of the *
* concatenation of orig and val is returned. The original orig is deleted
* (using sqliteFree()).
*/
char *z;
if( !orig ){
z = sqliteStrDup( val );
} else{
z = 0;
sqliteFree( orig );
}
return z;
}
/*
* Append a string representation of the entire node to orig and return it.
* This is used to produce debugging information if check_redblack_tree() finds
* a problem with a red-black binary tree.
*/
{
char buf[128];
int i;
for( i=0; i<indent; i++ ){
}
if( pNode ){
indent += 3;
}else{
}
}else{
}
return orig;
}
/*
* Print a representation of a node to stdout. This function is only included
* so you can call it from within a debugger if things get really bad. It
* is not called from anyplace in the code.
*/
{
/* Suppress a warning message about print_node() being unused */
(void)print_node;
}
/*
* Check the following properties of the red-black tree:
* (1) - If a node is red, both of it's children are black
* (2) - Each path from a given node to a leaf (NULL) node passes thru the
* same number of black nodes
*
* If there is a problem, append a description (using append_val() ) to *msg.
*/
{
/* 0 -> came from parent
* 1 -> came from left
* 2 -> came from right */
int prev_step = 0;
while( pNode ){
switch( prev_step ){
case 0:
}else{
prev_step = 1;
}
break;
case 1:
prev_step = 0;
}else{
prev_step = 2;
}
break;
case 2:
/* Check red-black property (1) */
){
char buf[128];
}
/* Check red-black property (2) */
{
int leftHeight = 0;
int rightHeight = 0;
}
}
if( leftHeight != rightHeight ){
char buf[128];
}
}
else prev_step = 2;
}
break;
default: assert(0);
}
}
}
/*
* Node pX has just been inserted into pTree (by code in sqliteRbtreeInsert()).
* It is possible that pX is a red node with a red parent, which is a violation
* of the red-black tree properties. This function performs rotations and
* color changes to rebalance the tree
*/
{
/* In the first iteration of this loop, pX points to the red node just
* inserted in the tree. If the parent of pX exists (pX is not the root
* node) and is red, then the properties of the red-black tree are
* violated.
*
* At the start of any subsequent iterations, pX points to a red node
* with a red parent. In all other respects the tree is a legal red-black
* binary tree. */
/* Grandparent of pX must exist and must be black. */
assert( pGrandparent );
/* Uncle of pX may or may not exist. */
else
/* If the uncle of pX exists and is red, we do the following:
* | |
* G(b) G(r)
* / \ / \
* U(r) P(r) U(b) P(b)
* \ \
* X(r) X(r)
*
* BEFORE AFTER
* pX is then set to G. If the parent of G is red, then the while loop
* will run again. */
pGrandparent->isBlack = 0;
pX = pGrandparent;
}else{
/* If pX is a right-child, do the following transform, essentially
* to change pX into a left-child:
* | |
* G(b) G(b)
* / \ / \
* P(r) U(b) X(r) U(b)
* \ /
* X(r) P(r) <-- new X
*
* BEFORE AFTER
*/
}
/* Do the following transform, which balances the tree :)
* | |
* G(b) P(b)
* / \ / \
* P(r) U(b) X(r) G(r)
* / \
* X(r) U(b)
*
* BEFORE AFTER
*/
pGrandparent->isBlack = 0;
}else{
/* This code is symetric to the illustrated case above. */
}
pGrandparent->isBlack = 0;
}
}
}
}
/*
* A child of pParent, which in turn had child pX, has just been removed from
* pTree (the figure below depicts the operation, Z is being removed). pParent
* or pX, or both may be NULL.
* | |
* P P
* / \ / \
* Z X
* / \
* X nil
*
* This function is only called if Z was black. In this case the red-black tree
* properties have been violated, and pX has an "extra black". This function
* performs rotations and color-changes to re-balance the tree.
*/
static
{
/* TODO: Comment this code! */
}
if( !pSib ){
}else if(
}else{
}
}
}else{
}
if( !pSib ){
}else if(
}else{
}
}
}
}
}
/*
* Create table n in tree pRbtree. Table n must not exist.
*/
{
}
/*
* Log a single "rollback-op" for the given Rbtree. See comments for struct
* BtRollbackOp.
*/
{
}
if( !pRbtree->pCheckRollback ){
}
}
}
int sqliteRbtreeOpen(
const char *zFilename,
int mode,
int nPg,
){
if( sqlite_malloc_failed ) goto open_no_mem;
/* Create a binary tree for the SQLITE_MASTER table at location 2 */
if( sqlite_malloc_failed ) goto open_no_mem;
/* Set file type to 4; this is so that "attach ':memory:' as ...." does not
** think that the database in uninitialised and refuse to attach
*/
return SQLITE_OK;
*ppBtree = 0;
return SQLITE_NOMEM;
}
/*
* Create a new table in the supplied Rbtree. Set *n to the new table number.
* Return SQLITE_OK if the operation is a success.
*/
{
btreeCreateTable(tree, *n);
if( sqlite_malloc_failed ) return SQLITE_NOMEM;
/* Set up the rollback structure (if we are not doing this as part of a
* rollback) */
if( pRollbackOp==0 ) return SQLITE_NOMEM;
pRollbackOp->iTab = *n;
}
return SQLITE_OK;
}
/*
* Delete table n from the supplied Rbtree.
*/
{
memRbtreeClearTable(tree, n);
if( pRollbackOp==0 ) return SQLITE_NOMEM;
pRollbackOp->iTab = n;
}
return SQLITE_OK;
}
{
*pRes = -1;
} else {
*pRes = -1;
}else{
}
}
return SQLITE_OK;
}
/*
* Get a new cursor for table iTable of the supplied Rbtree. The wrFlag
* parameter indicates that the cursor is open for writing.
*
* Note that RbtCursor.eSkip and RbtCursor.pNode both initialize to 0.
*/
static int memRbtreeCursor(
int iTable,
int wrFlag,
){
if( sqlite_malloc_failed ) return SQLITE_NOMEM;
return SQLITE_OK;
}
/*
* Insert a new record into the Rbtree. The key is given by (pKey,nKey)
* and the data is given by (pData,nData). The cursor is used only to
* define what database the record should be inserted into. The cursor
* is left pointing at the new record.
*
* If the key exists already in the tree, just replace the data.
*/
static int memRbtreeInsert(
const void *pKey,
int nKey,
const void *pDataInput,
int nData
){
void * pData;
int match;
/* It is illegal to call sqliteRbtreeInsert() if we are
** not in a transaction */
/* Make sure some other cursor isn't trying to read this same table */
if( checkReadLocks(pCur) ){
return SQLITE_LOCKED; /* The table pCur points to has a read lock */
}
/* Take a copy of the input data now, in case we need it for the
* replace case */
if( sqlite_malloc_failed ) return SQLITE_NOMEM;
/* Move the cursor to a node near the key to be inserted. If the key already
* exists in the table, then (match == 0). In this case we can just replace
* the data associated with the entry, we don't need to manipulate the tree.
*
* If there is no exact match, then the cursor points at what would be either
* the predecessor (match == -1) or successor (match == 1) of the
* searched-for key, were it to be inserted. The new node becomes a child of
* this node.
*
* The new node is initially red.
*/
if( match ){
if( pNode==0 ) return SQLITE_NOMEM;
if( sqlite_malloc_failed ) return SQLITE_NOMEM;
switch( match ){
case -1:
break;
case 1:
break;
default:
assert(0);
}
}else{
}
/* Point the cursor at the node just inserted, as per SQLite requirements */
/* A new node has just been inserted, so run the balancing code */
/* Set up a rollback-op in case we have to roll this operation back */
if( pOp==0 ) return SQLITE_NOMEM;
if( sqlite_malloc_failed ) return SQLITE_NOMEM;
}
}else{
/* No need to insert a new node in the tree, as the key already exists.
* Just clobber the current nodes data. */
/* Set up a rollback-op in case we have to roll this operation back */
if( pOp==0 ) return SQLITE_NOMEM;
if( sqlite_malloc_failed ) return SQLITE_NOMEM;
}else{
}
/* Actually clobber the nodes data */
}
return SQLITE_OK;
}
/* Move the cursor so that it points to an entry near pKey.
** Return a success code.
**
** *pRes<0 The cursor is left pointing at an entry that
** is smaller than pKey or if the table is empty
** and the cursor is therefore left point to nothing.
**
** *pRes==0 The cursor is left pointing at an entry that
** exactly matches pKey.
**
** *pRes>0 The cursor is left pointing at an entry that
** is larger than pKey.
*/
static int memRbtreeMoveto(
const void *pKey,
int nKey,
int *pRes
){
*pRes = -1;
switch( *pRes ){
case 1: /* cursor > key */
break;
case -1: /* cursor < key */
break;
}
}
/* If (pCur->pNode == NULL), then we have failed to find a match. Set
* pCur->pNode to pTmp, which is either NULL (if the tree is empty) or the
* last node traversed in the search. In either case the relation ship
* between pTmp and the searched for key is already stored in *pRes. pTmp is
* either the successor or predecessor of the key we tried to move to. */
return SQLITE_OK;
}
/*
** Delete the entry that the cursor is pointing to.
**
** The cursor is left pointing at either the next or the previous
** entry. If the cursor is left pointing to the next entry, then
** the pCur->eSkip flag is set to SKIP_NEXT which forces the next call to
** sqliteRbtreeNext() to be a no-op. That way, you can always call
** sqliteRbtreeNext() after a delete and the cursor will be left
** pointing to the first entry after the deleted entry. Similarly,
** pCur->eSkip is set to SKIP_PREV is the cursor is left pointing to
** the entry prior to the deleted entry so that a subsequent call to
** sqliteRbtreePrevious() will always leave the cursor pointing at the
** entry immediately before the one that was deleted.
*/
{
/* It is illegal to call sqliteRbtreeDelete() if we are
** not in a transaction */
/* Make sure some other cursor isn't trying to read this same table */
if( checkReadLocks(pCur) ){
return SQLITE_LOCKED; /* The table pCur points to has a read lock */
}
if( !pZ ){
return SQLITE_OK;
}
/* If we are not currently doing a rollback, set up a rollback op for this
* deletion */
if( pOp==0 ) return SQLITE_NOMEM;
}
/* First do a standard binary-tree delete (node pZ is to be deleted). How
* to do this depends on how many children pZ has:
*
* If pZ has no children or one child, then splice out pZ. If pZ has two
* children, splice out the successor of pZ and replace the key and data of
* pZ with the key and data of the spliced out successor. */
int dummy;
}
}else{
int res;
if( res ){
}
}
}
/* pZ now points at the node to be spliced out. This block does the
* splicing. */
{
BtRbNode **ppParentSlot = 0;
*ppParentSlot = pChild;
}else{
}
}
/* pZ now points at the spliced out node. pChild is the only child of pZ, or
* NULL if pZ has no children. If pZ is black, and not the tree root, then we
* will have violated the "same number of black nodes in every path to a
* leaf" property of the red-black tree. The code in do_delete_balancing()
* repairs this. */
}
sqliteFree(pZ);
return SQLITE_OK;
}
/*
* Empty table n of the Rbtree.
*/
{
while( pNode ){
}
}
else {
}else{
if( pRollbackOp==0 ) return SQLITE_NOMEM;
pRollbackOp->iTab = n;
}
sqliteFree( pNode );
if( pTmp ){
}
}
}
return SQLITE_OK;
}
{
}
}
*pRes = 0;
}else{
*pRes = 1;
}
return SQLITE_OK;
}
{
}
}
*pRes = 0;
}else{
*pRes = 1;
}
return SQLITE_OK;
}
/*
** Advance the cursor to the next entry in the database. If
** successful then set *pRes=0. If the cursor
** was already pointing to the last entry in the database before
** this routine was called, then set *pRes=1.
*/
{
}else{
}
}
}
*pRes = 1;
}else{
*pRes = 0;
}
return SQLITE_OK;
}
{
}else{
}
}
}
*pRes = 1;
}else{
*pRes = 0;
}
return SQLITE_OK;
}
{
}else{
*pSize = 0;
}
return SQLITE_OK;
}
{
}else{
}
return amt;
}
{
}else{
*pSize = 0;
}
return SQLITE_OK;
}
{
}else{
}
return amt;
}
{
}else{
assert( p!=0 );
if( p ){
}
}
return SQLITE_OK;
}
{
return SQLITE_OK;
}
{
return SQLITE_OK;
}
/*
* Check that each table in the Rbtree meets the requirements for a red-black
* binary tree. If an error is found, return an explanation of the problem in
* memory obtained from sqliteMalloc(). Parameters aRoot and nRoot are ignored.
*/
{
char * msg = 0;
HashElem *p;
}
return msg;
}
{
return SQLITE_OK;
}
return SQLITE_OK;
}
{
return SQLITE_ERROR;
return SQLITE_OK;
}
/*
** Delete a linked list of BtRollbackOp structures.
*/
while( pOp ){
}
}
/* Just delete pTransRollback and pCheckRollback */
tree->pTransRollback = 0;
tree->pCheckRollback = 0;
tree->pCheckRollbackTail = 0;
return SQLITE_OK;
}
/*
* Close the supplied Rbtree. Delete everything associated with it.
*/
{
HashElem *p;
}
return SQLITE_OK;
}
/*
* Execute and delete the supplied rollback-list on pRbtree.
*/
{
int res;
while( pList ){
case ROLLBACK_INSERT:
break;
case ROLLBACK_DELETE:
memRbtreeDelete( &cur );
break;
case ROLLBACK_CREATE:
break;
case ROLLBACK_DROP:
break;
default:
assert(0);
}
}
}
{
tree->pTransRollback = 0;
tree->pCheckRollback = 0;
tree->pCheckRollbackTail = 0;
return SQLITE_OK;
}
{
return SQLITE_ERROR;
return SQLITE_OK;
}
{
if( tree->pCheckRollback ){
tree->pCheckRollback = 0;
tree->pCheckRollbackTail = 0;
}
}
return SQLITE_OK;
}
{
tree->pCheckRollback = 0;
tree->pCheckRollbackTail = 0;
return SQLITE_OK;
}
#ifdef SQLITE_TEST
{
assert(!"Cannot call sqliteRbtreePageDump");
return SQLITE_OK;
}
{
assert(!"Cannot call sqliteRbtreeCursorDump");
return SQLITE_OK;
}
#endif
{
return 0;
}
/*
** Return the full pathname of the underlying database file.
*/
return 0; /* A NULL return indicates there is no underlying file */
}
/*
** The copy file function is not implemented for the in-memory database
*/
return SQLITE_INTERNAL; /* Not implemented */
}
static BtOps sqliteRbtreeOps = {
(int(*)(Btree*)) memRbtreeClose,
(int(*)(Btree*,int)) memRbtreeSetCacheSize,
(int(*)(Btree*,int)) memRbtreeSetSafetyLevel,
(int(*)(Btree*)) memRbtreeBeginTrans,
(int(*)(Btree*)) memRbtreeCommit,
(int(*)(Btree*)) memRbtreeRollback,
(int(*)(Btree*)) memRbtreeBeginCkpt,
(int(*)(Btree*)) memRbtreeCommitCkpt,
(int(*)(Btree*)) memRbtreeRollbackCkpt,
(int(*)(Btree*,int*)) memRbtreeCreateTable,
(int(*)(Btree*,int*)) memRbtreeCreateTable,
(int(*)(Btree*,int)) memRbtreeDropTable,
(int(*)(Btree*,int)) memRbtreeClearTable,
(int(*)(Btree*,int*)) memRbtreeGetMeta,
(int(*)(Btree*,int*)) memRbtreeUpdateMeta,
(char*(*)(Btree*,int*,int)) memRbtreeIntegrityCheck,
(const char*(*)(Btree*)) memRbtreeGetFilename,
#ifdef SQLITE_TEST
(int(*)(Btree*,int,int)) memRbtreePageDump,
#endif
};
static BtCursorOps sqliteRbtreeCursorOps = {
(int(*)(BtCursor*,const void*,int,int*)) memRbtreeMoveto,
(int(*)(BtCursor*)) memRbtreeDelete,
(int(*)(BtCursor*,const void*,int,const void*,int)) memRbtreeInsert,
(int(*)(BtCursor*,int*)) memRbtreeFirst,
(int(*)(BtCursor*,int*)) memRbtreeLast,
(int(*)(BtCursor*,int*)) memRbtreeNext,
(int(*)(BtCursor*,int*)) memRbtreePrevious,
(int(*)(BtCursor*,int*)) memRbtreeKeySize,
(int(*)(BtCursor*,int,int,char*)) memRbtreeKey,
(int(*)(BtCursor*,const void*,int,int,int*)) memRbtreeKeyCompare,
(int(*)(BtCursor*,int*)) memRbtreeDataSize,
(int(*)(BtCursor*,int,int,char*)) memRbtreeData,
(int(*)(BtCursor*)) memRbtreeCloseCursor,
#ifdef SQLITE_TEST
(int(*)(BtCursor*,int*)) memRbtreeCursorDump,
#endif
};
#endif /* SQLITE_OMIT_INMEMORYDB */