btreend.cpp

来自「开放源码的编译器open watcom 1.6.0版的源代码」· C++ 代码 · 共 690 行 · 第 1/2 页

/****************************************************************************
*
*                            Open Watcom Project
*
*    Portions Copyright (c) 1983-2002 Sybase, Inc. All Rights Reserved.
*
*  ========================================================================
*
*    This file contains Original Code and/or Modifications of Original
*    Code as defined in and that are subject to the Sybase Open Watcom
*    Public License version 1.0 (the 'License'). You may not use this file
*    except in compliance with the License. BY USING THIS FILE YOU AGREE TO
*    ALL TERMS AND CONDITIONS OF THE LICENSE. A copy of the License is
*    provided with the Original Code and Modifications, and is also
*    available at www.sybase.com/developer/opensource.
*
*    The Original Code and all software distributed under the License are
*    distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
*    EXPRESS OR IMPLIED, AND SYBASE AND ALL CONTRIBUTORS HEREBY DISCLAIM
*    ALL SUCH WARRANTIES, INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF
*    MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR
*    NON-INFRINGEMENT. Please see the License for the specific language
*    governing rights and limitations under the License.
*
*  ========================================================================
*
* Description:  WHEN YOU FIGURE OUT WHAT THIS FILE DOES, PLEASE
*               DESCRIBE IT HERE!
*
****************************************************************************/


#include "btreend.h"

#if 1 // only while in CPP file to instantiate
    #include "btree.h"
    #include "btreeit.h"
    #include "mrinfo.h"

    typedef BTreeBucketNode<MergeOffset,MergeDIE>       __grokky_1;
    typedef BTreeBucketNode<MergeNameKey,MergeDIE>      __grokky_2;
    typedef BTreeSearchNode<MergeOffset,MergeDIE>       __grokky_3;
    typedef BTreeSearchNode<MergeNameKey,MergeDIE>      __grokky_4;
#endif

#pragma warning 549 9   // sizeof contains compiler genned info

/*--------------------- BTreeSearchNode -------------------------------*/

template < class Key_T, class Obj_T >
static void BTreeNodeBase<Key_T,Obj_T>::
ragnarok()
//-----------------------------------
{
    BTreeSearchNode<Key_T,Obj_T>::ragnarok();
    BTreeBucketNode<Key_T,Obj_T>::ragnarok();
}

template < class Key_T, class Obj_T >
static void BTreeNodeBase<Key_T,Obj_T>::
setKeyObjOrder( uint keyOrd, uint objOrd )
//------------------------------------------
{
    BTreeSearchNode<Key_T,Obj_T>::setKeyOrder( keyOrd );
    BTreeBucketNode<Key_T,Obj_T>::setObjOrder( objOrd );
}


/*--------------------- BTreeSearchNode -------------------------------*/

template < class Key_T, class Obj_T >
static uint BTreeSearchNode<Key_T,Obj_T>::
_keyOrder( -1 );

const int BTreeSearchNodePoolSize = 1024;
template < class Key_T, class Obj_T >
static MemoryPool BTreeSearchNode<Key_T,Obj_T>::
_pool( sizeof( BTreeSearchNode ), "BTreeSearchNode", BTreeSearchNodePoolSize );

const int BTreeSearchNodeNodePoolSize = 1024;
template < class Key_T, class Obj_T >
static MemoryPool BTreeSearchNode<Key_T,Obj_T>::
_nodePool( "BTreeSearchNodeNode" );

template < class Key_T, class Obj_T >
BTreeSearchNode<Key_T,Obj_T>::
BTreeSearchNode( const Key_T & mid, BTreeNodeBase<Key_T,Obj_T> * lhn,
                BTreeNodeBase<Key_T,Obj_T> * rhn )
        : _degree( 2 )
{
    _nodes = (NodeStore *) _nodePool.alloc();
    _nodes[ 0 ]._separator.operator= ( mid );
    _nodes[ 0 ]._child = lhn;
    _nodes[ 1 ]._child = rhn;
}

template < class Key_T, class Obj_T >
BTreeSearchNode<Key_T,Obj_T>::
BTreeSearchNode()
    : _degree( 0 )
{
    _nodes = (NodeStore *) _nodePool.alloc();
}

template < class Key_T, class Obj_T >
BTreeSearchNode<Key_T,Obj_T>::
~BTreeSearchNode()
{
    // WARNING -- this destructor is not guaranteed to be called
    //            since the elements are pooled and freed using
    //            the pool's ragnarok
}

template < class Key_T, class Obj_T >
static void BTreeSearchNode<Key_T,Obj_T>::
ragnarok()
//----------------------------------------
{
    _pool.ragnarok();
    _nodePool.ragnarok();
}

template < class Key_T, class Obj_T >
static void BTreeSearchNode<Key_T,Obj_T>::
setKeyOrder( uint keyOrder )
//------------------------------------------
{
    _keyOrder = keyOrder;
    _nodePool.setSize( sizeof( NodeStore ) * keyOrder * 2 + sizeof( NodeStore ),
                       BTreeSearchNodeNodePoolSize );
}

#if INSTRUMENTS
template < class Key_T, class Obj_T >
void BTreeSearchNode<Key_T,Obj_T>::
print( int indent )
//----------------------------------
{
    int i;
    int len = 0;
    int test;
    char * dashes = "-------------------------------------------------------";

    for( i = 0; i < _degree - 1; i += 1 ) {
        if( _nodes[ i ]._separator.getString() ) {
            test = strlen( _nodes[ i ]._separator.getString() );
        } else {
            test = strlen( "NULL" );
        }
        len = (test>len) ? test : len;
    }

    for( i = 0; i < _degree - 1; i += 1 ) {
        _nodes[ i ]._child->print( indent + 15 );
        if( i == 0 ) {
            Log.printf( "%*c/%.*s\\\n", indent, ' ', len, dashes );
        }
        const char * c = _nodes[ i ]._separator.getString();
        if( c ) {
            Log.printf( "%*c|%*.*s|\n", indent, ' ', len, len, c );
        } else {
            Log.printf( "%*c|%*.*s|\n", indent, ' ', len, len, "NULL" );
        }
    }
    Log.printf( "%*c\\%*.*s/\n", indent, ' ', len, len, dashes );
    _nodes[ i ]._child->print( indent + 15 );
}
#endif

template < class Key_T, class Obj_T >
uint BTreeSearchNode<Key_T,Obj_T>::
privSearch( const Key_T & key, uint lower, uint upper )
//-----------------------------------------------------------------
// using a binary search, return the first element greater than key
{
    int middle;

    while( lower != upper ) {
        middle = (lower + upper) / 2;
        if( key.operator<( _nodes[ middle ]._separator ) ) {
            upper = middle;
        } else {
            lower = middle + 1;
        }
    }

    return lower;
}

template < class Key_T, class Obj_T >
Obj_T * BTreeSearchNode<Key_T,Obj_T>::
find( const Key_T & key )
//------------------------------------
{
    int idx;

    idx = privSearch( key, 0, _degree - 1 );
    return _nodes[ idx ]._child->find( key );
}

template < class Key_T, class Obj_T >
void BTreeSearchNode<Key_T,Obj_T>::
remove( const Key_T & key )
//-----------------------------------
// remove an element by finding the appropriate child and
// calling remove for them.
{
    int idx;

    idx = privSearch( key, 0, _degree - 1 );
    _nodes[ idx ]._child->remove( key );
}

template < class Key_T, class Obj_T >
Obj_T * BTreeSearchNode<Key_T,Obj_T>::
insert( Obj_T * obj, bool & needsSplit, Key_T & key,
        BTreeNodeBase *& newNode  )
//--------------------------------------------------------
// insert an element by finding the appropriate child (which may
// be another SearchNode, Bucket, or Leaf), and calling insert for them.
// If they split, they will set splitOccured to TRUE, and key and newNode
// will be set to the parent and right subtree respectively.  If we
// need to split while processing a child's split, set our caller's
// needsSplit, key, and newNode appropriately.
{
    int             idx;
    bool            splitOccurred;
    Obj_T *         res = NULL;

    #if ( INSTRUMENTS == INSTRUMENTS_FULL_LOGGING )
    Log.printf( "inserting in searchnode -- %s\n",
                                    ((const Key_T &)(*obj)).getString() );
    #endif

    needsSplit = FALSE;
    idx = privSearch( (const Key_T&)(*obj), 0, _degree - 1 );
    res = _nodes[ idx ]._child->insert( obj, splitOccurred, key, newNode );

    if( splitOccurred ) {    // our child split while inserting
        if( _degree == 2 * _keyOrder + 1 ) {    // we need to split
            split( key, newNode );
            needsSplit = TRUE;
            return res;
        } else {                                // we can insert without split
            privInsert( key, newNode );
            return res;
        }
    } else {
        return res;
    }
}

template < class Key_T, class Obj_T >
void BTreeSearchNode<Key_T,Obj_T>::
privInsert( const Key_T & key, BTreeNodeBase *& newNode )
//-------------------------------------------------------
// insert a new key / node to this.  This assumes that there
// is room (ie _degree < _keyOrder * 2), and doesn't check!
{
    int i;
    int j;

    for( i = 0; i < _degree - 1; i += 1 ) {
        if( key.operator< ( _nodes[ i ]._separator ) ) break;
    }

    if( i < _degree - 1 ) {
        _nodes[ _degree ]._child = _nodes[ _degree - 1 ]._child;
        for( j = _degree - 1; j > i; j -= 1 ) {
            _nodes[ j ]._separator.operator= ( _nodes[ j - 1 ]._separator );
            _nodes[ j ]._child = _nodes[ j - 1 ]._child;
        }
    }
    _nodes[ i ]._separator.operator= ( key );
    _nodes[ i + 1 ]._child = newNode;

    _degree += 1;
}

template < class Key_T, class Obj_T >
void BTreeSearchNode<Key_T,Obj_T>::
split( Key_T & key, BTreeNodeBase *& newNode )
//--------------------------------------------
// split this node into two, each with _keyOrder + 1 children.
// key and newNode are input and output parameters
{
    BTreeSearchNode *   other;
    BTreeNodeBase **    children;
    Key_T *             seps;
    int                 i;

    typedef BTreeNodeBase * BTreeNodeBasePtr;

    children = new BTreeNodeBasePtr [ _keyOrder * 2 + 2 ];
    seps = new Key_T [ _keyOrder * 2 + 1 ];

    #if ( INSTRUMENTS == INSTRUMENTS_FULL_LOGGING )
    Log.printf( "splitting searchnode -- key %s, newNode is\n", key.getString() );
    newNode->print( 0 );
    #endif

    InternalAssert( _degree == _keyOrder * 2 + 1 );

    for( i = 0; i < _degree-1 && _nodes[i]._separator.operator<(key); i += 1 ) {
        children[ i ] = _nodes[ i ]._child;
        seps[ i ].operator= ( _nodes[ i ]._separator );
    }

    seps[ i ].operator= ( key );
    children[ i ] = _nodes[ i ]._child;
    children[ i + 1 ] = newNode;

    for( ; i < _degree - 1; i += 1 ) {
        seps[ i + 1 ].operator= ( _nodes[ i ]._separator );
        children[ i + 2 ] = _nodes[ i + 1 ]._child;
    }

    other = new BTreeSearchNode();
    other->_degree = _keyOrder + 1;
    _degree = _keyOrder + 1;

    for( i = 0; i < _keyOrder; i += 1 ) {
        _nodes[ i ]._separator.operator=( seps[ i ] );
    }

    for( i = 0; i < _keyOrder + 1; i += 1 ) {
        _nodes[ i ]._child = children[ i ];
    }

    for( i = 0; i < _keyOrder; i += 1 ) {
        other->_nodes[ i ]._separator.operator= ( seps[ i + _keyOrder + 1 ] );
    }
    for( i = 0; i < _keyOrder + 1; i += 1 ) {
        other->_nodes[ i ]._child = children[ i + _keyOrder + 1 ];
    }

    #if ( INSTRUMENTS == INSTRUMENTS_FULL_LOGGING )
    Log.printf( "splitting searchnode -- about to assign key %s\n", seps[ _keyOrder ].getString() );
    #endif

    newNode = other;
    key.operator= ( seps[ _keyOrder ] );

    delete [] seps;
    delete [] children;