bptree.cpp

用CJ60Lib界面库制作的SQL数据库客户与服务器程序。

// BPTree.cpp : implementation file
//

#include "stdafx.h"
#include "miniSQL.h"
#include "BPTree.h"

#ifdef _DEBUG
#define new DEBUG_NEW
#undef THIS_FILE
static char THIS_FILE[] = __FILE__;
#endif

/////////////////////////////////////////////////////////////
// CBPTNode

void CBPTNode::insert_key( int i, const CEntry& V )
{
	for( int j = keys()++; j > i; j-- )
		pick_key( j ) = pick_key( j - 1 );
    pick_key( i ) = V;
}

void CBPTNode::insert_ptr( int i, long P )
{
	for( int j = ptrs()++; j > i; j-- )
		pick_ptr( j ) = pick_ptr( j - 1 );
    pick_ptr( i ) = P;
}

void CBPTNode::remove_key( int i )
{
	for( int j = --keys(); i < j; i++ )
		pick_key( i ) = pick_key( i + 1 );
}

void CBPTNode::remove_ptr( int i )
{
	for( int j = --ptrs(); i < j; i++ )
		pick_ptr( i ) = pick_ptr( i + 1 );
}

int CBPTNode::find_ptr( long ptr )
{
    int i;
    for( i = ptrs() - 1; i >= 0; i-- )
        if( pick_ptr( i ) == ptr )
            break;
    return i;
}

int CBPTNode::lower_bound( const CEntry& V )
{
    int F = 0;
    int N = keys();
	for( ; 0 < N; )
    {
        int N2 = N / 2;
		int M = F + N2;
		if( pick_key( M ) < V )
			F = ++M, N -= N2 + 1;
		else
			N = N2; 
    }
	return F; 
}

int CBPTNode::upper_bound( const CEntry& V )
{
    int R = lower_bound( V );
    while( R < keys() && pick_key( R ) == V ) 
		R++;
    return R;
}

void CBPTNode::init( bool Leaf )
{
    leaf() = Leaf;
    keys() = ptrs() = 0;
    if( Leaf )
        insert_ptr( 0, -1 );
}

void CBPTNode::relink( CBlock* new_block, bool dirty )
{
    Bptr->lock() = false;
    Bptr = new_block;
    Bptr->lock() = true;
    Dptr = Bptr->GetBlock();
    dirty && ( Bptr->dirty() = true );
}

/////////////////////////////////////////////////////////////
// CPBucket

long CPBucket::insert( long PTR )
{
    PNode new_node;
    new_node.NEXT = head_posi;
    new_node.PTR  = PTR;
    bktAPI->WriteRec( head_posi = bktAPI->AllocRec(), &new_node );
    return head_posi;
}

long CPBucket::remove( long PTR )
{   
	long last = -1;
	long posi = head_posi;
	PNode node;
	for( ; posi != -1; last = posi, posi = node.NEXT )
	{
		bktAPI->ReadRec( posi, &node );
		if( node.PTR == PTR )
		{
			if( last == -1 )
				head_posi = node.NEXT;
			else
			{
				PNode last_node;
				bktAPI->ReadRec( last, &last_node );
				last_node.NEXT = node.NEXT;
				bktAPI->WriteRec( last, &last_node );
			}
			bktAPI->RemoveRec( posi );
			return head_posi;
		}
	}
	throw Error( ERROR_BUCKET_REMOVE, (int)PTR, CString("") );
}

void CPBucket::output( RESULT& ret )
{
	PNode node;
	long  posi = head_posi;
	while( posi != -1 )
	{
		bktAPI->ReadRec( posi, &node );
		ret.AddTail( node.PTR );
		posi = node.NEXT;
	}
}

/////////////////////////////////////////////////////////////
// CBPTree

CBPTree::CBPTree( const char* name, const CEntryAttr& kattr, bool dup ) : bptAPI( 0 ), bktAPI( 0 )
{
    bptAPI = new CFileAPI( name, ".bpt", BLOCK_SIZE, sizeof( CBPTAttr ), false );
    attr.bucket = dup;
    attr.kattr  = kattr;
    attr.kattr.rearrange();
    attr.root   = bptAPI->AllocRec();
    attr.N      = (BLOCK_SIZE-sizeof(int)*2-sizeof(bool)-sizeof(long)) 
                / (attr.kattr.length+sizeof(long));
    if( attr.N < 3 )
        throw Error( ERROR_BPLUS_CREATE, attr.kattr.length, CString("") );
    save_attr();
    if( attr.bucket )
        bktAPI = new CFileAPI( name, ".bkt", sizeof( PNode ), 0, false );
    CBPTNode( bptAPI->FetchBlock( attr.root ), attr, true ).init( true );
}

CBPTree::CBPTree( const char* name )
{
    bptAPI = new CFileAPI( name, ".bpt" );
    load_attr();
    if( attr.bucket )
        bktAPI = new CFileAPI( name, ".bkt" );
    else
        bktAPI = 0;
}

CBPTree::~CBPTree()
{
    save_attr();
    if( bptAPI )    delete bptAPI;
    if( bktAPI )    delete bktAPI;
}

long CBPTree::node_seek( const CEntry& KEY )
{
	while( !path.Empty() )  path.Pop();
	long node = attr.root;
	while( true )
	{
		CBPTNode N( bptAPI->FetchBlock( node ), attr, false );
		if( N.leaf() )
			return node;
		path.Push( node );
		node = N.pick_ptr( N.upper_bound( KEY ) );
	}
}

void CBPTree::node_insert( long node, const CEntry& KEY, long PTR )
{
	CBPTNode N( bptAPI->FetchBlock( node ), attr, true );
	if( N.leaf() )
	{
		int posi = N.lower_bound( KEY );
		if( !attr.bucket )
		{
			if( posi < N.keys() && N.pick_key( posi ) == KEY )
                throw Error( ERROR_BPLUS_INSERT, 0, _T("") );
			N.insert_key( posi, KEY );
			N.insert_ptr( posi, PTR );
        }
		else
		{
			if( !( posi < N.keys() && N.pick_key( posi ) == KEY ) )
			{
				N.insert_key( posi, KEY );
				N.insert_ptr( posi, -1 );
			}
			N.pick_ptr( posi ) = CPBucket( bktAPI, N.pick_ptr(posi) ).insert( PTR );
		}
	}
	else
    {
        int posi = N.lower_bound( KEY );
        if( posi < N.keys() && N.pick_key( posi ) == KEY )
            throw Error( ERROR_BPLUS_INSERT, 0, _T("") );
        N.insert_key( posi    , KEY );
        N.insert_ptr( posi + 1, PTR );
    }

	if( N.keys() >= attr.N )
	{
		CEntry V( attr.kattr );
        long new_node  = bptAPI->AllocRec();
        CBPTNode N1( bptAPI->FetchBlock( new_node ), attr, true );
        N1.init( N.leaf() );
        if( N.leaf() )
        {
            const int half = ( attr.N + 1 ) / 2;
            for( int i = N.keys() - 1; i >= half; i-- )
            {
                N1.insert_key( 0, N.pick_key( i ) );
                N1.insert_ptr( 0, N.pick_ptr( i ) );
                N.remove_key( i );
                N.remove_ptr( i );
            }
            V = N1.pick_key( 0 );
            N1.last_ptr() = N.last_ptr();
            N.last_ptr()  = new_node;
        }
        else
        {
            const int half = N.keys() - ( attr.N + 1 ) / 2;
            for( int i = N.keys() - 1; i >= half; i-- )
            {
                N1.insert_key( 0, N.pick_key( i ) );
                N1.insert_ptr( 0, N.pick_ptr( i + 1 ) );
                N.remove_key( i );
                N.remove_ptr( i + 1 );
            }
            V = N1.pick_key( 0 );
            N1.remove_key( 0 );
        }

        if( path.Size() )
        {
            long P = path.Pop();
            node_insert( P, V, new_node );
        }
        else
        {
            long new_P  = bptAPI->AllocRec();
            CBPTNode P( bptAPI->FetchBlock( new_P ), attr, true );
            P.init( false );
            P.insert_key( 0, V );
            P.insert_ptr( 0, new_node );
            P.insert_ptr( 0, node );
            attr.root = new_P;
        }
    }
}

void CBPTree::node_remove( long node, const CEntry& KEY, long PTR )
{
    CBPTNode N( bptAPI->FetchBlock( node ), attr, true );
    if( N.leaf() )
    {
        int posi = N.lower_bound( KEY );
        if( posi < N.keys()           && 
            N.pick_key( posi ) == KEY &&
            ( attr.bucket || N.pick_ptr( posi ) == PTR ) )
            if( !attr.bucket )
            {
                N.remove_key( posi );
                N.remove_ptr( posi );
            } 
			else 
            {
                N.pick_ptr( posi ) = CPBucket( bktAPI, N.pick_ptr(posi) ).remove( PTR );
                if( N.pick_ptr( posi ) == -1 )
                {
                    N.remove_key( posi );
                    N.remove_ptr( posi );
                }
            }
        else throw Error( ERROR_BPLUS_REMOVE, 0, _T("") );
    }
    else
    {
        int posi = N.lower_bound( KEY );
        N.remove_key( posi );
        N.remove_ptr( posi + 1 );
    }

    if( attr.root == node )
    {
        if( N.ptrs() == 1 && N.pick_ptr( 0 ) != -1 )
        {
            attr.root = N.pick_ptr( 0 );
            bptAPI->RemoveRec( node );
        }
    }
    else if(  N.leaf() && N.keys() <   attr.N       / 2 ||
             !N.leaf() && N.ptrs() < ( attr.N + 1 ) / 2 )
    {
        bool pre;
        long parent_node = path.Pop();
        CBPTNode P( bptAPI->FetchBlock( parent_node ), attr, true );
        int posi = P.find_ptr( node );
        int vposi;					//KEY position
        if( posi == P.ptrs() - 1 )
            pre = true,  vposi = --posi;
        else
            pre = false, vposi = posi++;
        CEntry V( P.pick_key( vposi ) );
        CBPTNode N1( bptAPI->FetchBlock( P.pick_ptr( posi ) ), attr, true );

        if( N.keys() + N1.keys() + !N.leaf() < attr.N )
        {
            CBPTNode *NA, *NB;
            if( pre )  NA = &N1, NB = &N;
            else       NA = &N , NB = &N1;
            if( !N.leaf() )
            {
                NA->insert_key( NA->keys(), V );
                int i;
                for( i = 0; i < NB->keys(); i++ )
                {
                    NA->insert_key( NA->keys(), NB->pick_key( i ) );
                    NA->insert_ptr( NA->ptrs(), NB->pick_ptr( i ) );
                }
                NA->insert_ptr( NA->ptrs(), NB->pick_ptr( i ) );
            }
            else
            {
                for( int i = 0; i < NB->keys(); ++i )
                {
                    NA->insert_key( NA->keys(),     NB->pick_key( i ) );
                    NA->insert_ptr( NA->ptrs() - 1, NB->pick_ptr( i ) );
                }
                NA->last_ptr() = NB->last_ptr();
            }
            node_remove( parent_node, V, 0 );
        }   
		else
            if( pre )
                if( !N.leaf() )
                {
                    N.insert_key( 0, V );
                    N.insert_ptr( 0, N1.last_ptr() );
                    V = N1.last_key();
                    N1.keys()--;
                    N1.ptrs()--;
                }
                else
                {
                    N.insert_key( 0, N1.last_key() );
                    N.insert_ptr( 0, N1.pick_ptr( N1.ptrs() - 2 ) );
                    V = N.pick_key( 0 );
                    N1.keys()--;
                    N1.remove_ptr( N1.ptrs() - 2 );
                }
            else
                if( !N.leaf() )
                {
                    N.insert_key( N.keys(), V );
                    N.insert_ptr( N.ptrs(), N1.pick_ptr( 0 ) );
                    V = N1.pick_key( 0 );
                    N1.remove_key( 0 );
                    N1.remove_ptr( 0 );
                }
                else
                {
                    N.insert_key( N.keys(), N1.pick_key( 0 ) );
                    N.insert_ptr( N.ptrs() - 1, N1.pick_ptr( 0 ) );
                    N1.remove_key( 0 );
                    N1.remove_ptr( 0 );
                    V = N1.pick_key( 0 );
                }
    }
}

bool CBPTree::convert( CEntry& ret, const CEntry& E, bool strict )
{
    if( strict && ret.values() != E.values() )
        return false;
    try
	{
		for( int i = ret.values() - 1; i >= 0; i-- )
			ret[i] = E[ attr.kattr.attr[i].name ];
	}
    catch( Error& e )
	{
        if( strict && e.m_ErrType == ENTRY_RANGE_ERROR )
            return false;
        throw e;
	}
    return true;
}

bool CBPTree::search( RESULT& ret, const CEntry& E )
{
    CEntry  KEY( attr.kattr );
    if( !convert( KEY, E, true ) )
        return false;
    CBPTNode N( bptAPI->FetchBlock( node_seek(KEY) ), attr, false );
    int posi = N.lower_bound( KEY );
    if( posi < N.keys() && N.pick_key( posi ) == KEY )
    {
        if( !attr.bucket )
            ret.AddTail( N.pick_ptr( posi ) );
        else
            CPBucket( bktAPI, N.pick_ptr(posi) ).output( ret );
    }
    return true;
}

bool CBPTree::search( RESULT& ret, const CEntry& E1, const CEntry& E2 )
{
    CEntry  KEY1( attr.kattr ), KEY2( attr.kattr );
    if( !convert( KEY1, E1, true ) || !convert( KEY2, E2, true ) )
        return false;
    long   node, last_node;
    int    posi, last_posi;
    CBPTNode N( bptAPI->FetchBlock( last_node=node_seek(KEY2) ), attr, false );
    last_posi = N.upper_bound(KEY2);
    N.relink( bptAPI->FetchBlock( node=node_seek(KEY1) ), false );
    posi = N.lower_bound(KEY1);
    while( node != last_node || posi < last_posi )
    {
        if( posi == N.keys() )
        {
            if( ( node = N.last_ptr() ) == -1 )
                break;
            N.relink( bptAPI->FetchBlock(node), false );
            posi = -1;
        }
        else if( !attr.bucket )
            ret.AddTail( N.pick_ptr( posi ) );
        else
            CPBucket( bktAPI, N.pick_ptr(posi) ).output( ret );
        ++posi;
    }
    return true;
}