btreend.cpp

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

}


template < class Key_T, class Obj_T >
BTreeNodeBase< Key_T, Obj_T > * BTreeSearchNode<Key_T,Obj_T>::
nextNode( int_16 & idx)
//---------------------------------------------------------------
{
    #if ( INSTRUMENTS == INSTRUMENTS_FULL_LOGGING )
    Log.printf( "SearchNode %p, idx = %d, _degree = %d, return = %p\n",
                                    this, idx + 1, _degree, (idx + 1 < _degree) ? _nodes[ idx + 1 ]._child : NULL );
    #endif

    idx += 1;
    if( idx >= _degree ) return NULL;

    return _nodes[ idx ]._child;
}

template < class Key_T, class Obj_T >
Obj_T * BTreeSearchNode<Key_T,Obj_T>::
nextObj( int_16 & )
//------------------------------------
{
    #if ( INSTRUMENTS == INSTRUMENTS_FULL_LOGGING )
    Log.printf( "SearchNode nextObj == NULL\n" );
    #endif

    return NULL;    // no objects in search node
}


/*--------------------- BTreeBucketNode -----------------------------*/

template < class Key_T, class Obj_T >
static uint BTreeBucketNode<Key_T,Obj_T>::
_objOrder( -1 );

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

const int BTreeBucketNodeNodePoolSize = 1024;
template < class Key_T, class Obj_T >
static MemoryPool BTreeBucketNode<Key_T,Obj_T>::
_nodePool( "BTreeBucketNodeNode" );

template < class Key_T, class Obj_T >
BTreeBucketNode<Key_T,Obj_T>::
BTreeBucketNode()
    : _degree(0)
//---------------------------------------------------------------
{
    _nodes = (ObjPtr *) _nodePool.alloc();
}

template < class Key_T, class Obj_T >
BTreeBucketNode<Key_T,Obj_T>::
BTreeBucketNode( Obj_T * obj )
    : _degree( 1 )
//---------------------------------------------------------------
{
    _nodes = (ObjPtr *) _nodePool.alloc();
    _nodes[ 0 ] = obj;
}

template < class Key_T, class Obj_T >
BTreeBucketNode<Key_T,Obj_T>::
~BTreeBucketNode()
{
    // 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 BTreeBucketNode<Key_T,Obj_T>::
ragnarok()
//----------------------------------------
{
    _pool.ragnarok();
    _nodePool.ragnarok();
}

template < class Key_T, class Obj_T >
static void BTreeBucketNode<Key_T,Obj_T>::
setObjOrder( uint objOrder )
//-------------------------------------------
{
    _objOrder = objOrder;
    _nodePool.setSize( sizeof( ObjPtr ) * 2 * objOrder + sizeof( ObjPtr ),
                       BTreeBucketNodeNodePoolSize );
}

#if INSTRUMENTS
template < class Key_T, class Obj_T >
void BTreeBucketNode<Key_T,Obj_T>::
print( int indent )
//----------------------------------
{
    int i;

    if( _degree == 0 ) {
        Log.printf( "%*c<empty bucket>\n", indent, ' ' );
    }

    for( i = 0; i < _degree; i += 1 ) {
        Log.printf( "%*c%s\n", indent, ' ',
                                        (const char *)(*_nodes[ i ]) );
    }
}
#endif


template < class Key_T, class Obj_T >
uint BTreeBucketNode<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== ( (const Key_T&)(*_nodes[ middle ])) ) {
            return middle;
        } else {
            if( key.operator< ( (const Key_T&)(*_nodes[ middle ])) ) {
                upper = middle;
            } else {
                lower = middle + 1;
            }
        }
    }

    return lower;
}


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

    idx = privSearch( key, 0, _degree );

    if( idx < _degree && key.operator== ( (const Key_T&)(*_nodes[idx]) )) {
        return _nodes[ idx ];
    } else {
        return NULL;    // not found
    }
}

template < class Key_T, class Obj_T >
void BTreeBucketNode<Key_T,Obj_T>::
remove( const Key_T & key )
//-----------------------------------
// remove an element from the bucket
{
    int idx;

    idx = privSearch( key, 0, _degree );

    if( idx < _degree &&
         key.operator== ( (const Key_T&)(*_nodes[idx]) ) ) {

        for( int j = idx; j < _degree; j += 1 ) {
            _nodes[ j ] = _nodes[ j + 1 ];
        }

        _degree -= 1;
    } else {
        #if INSTRUMENTS
        Log.printf( "NOT FOUND FOR REMOVE!\n", key.getString() );
        print( 0 );
        #endif

        BTreeExcept a( "Element Not Found for Remove",
                        BTreeExcept::NotFoundForRemove );
        throw( a );
    }
}

template < class Key_T, class Obj_T >
Obj_T * BTreeBucketNode<Key_T,Obj_T>::
insert( Obj_T * obj, bool & needsSplit, Key_T & key,
        BTreeNodeBase *& newNode )
//--------------------------------------------------
// attempt to insert object 'obj' into this bucket.  If the
// bucket is full, split it and return the new key and node
// in 'key' and 'newNode' respectively
{
    if( _degree == 2 * _objOrder + 1 ) {
        needsSplit = TRUE;              // we split
        return split( key, obj, newNode );
    } else {
        needsSplit = FALSE;             // we did not split
        return privInsert( obj );
    }
}

template < class Key_T, class Obj_T >
Obj_T * BTreeBucketNode<Key_T,Obj_T>::
privInsert( Obj_T * obj )
//------------------------------------
// insert the element -- there must be room for it!
{
    int idx;

    InternalAssert( _degree < _objOrder * 2 + 1 );

    idx = privSearch( (const Key_T&)(*obj), 0, _degree );

    if( idx < _degree &&
         ((const Key_T&)(*obj)).operator== ( (const Key_T&)(*_nodes[idx]) ) ) {

        if( obj == _nodes[ idx ] ) {
            return obj;
        }

        #if INSTRUMENTS
        Log.printf( "DUPLICATE! %s = \n", (const char *) (*obj) );
        Log.printf( "           %s\n", (const char *) (*_nodes[ idx ]) );
        print( 0 );
        #endif

        BTreeExcept a( "Duplicate", BTreeExcept::Duplicate );
        throw( a );
    }

    if( idx < _degree ) {
        for( int j = _degree; j > idx; j -= 1 ) {
            _nodes[ j ] = _nodes[ j - 1 ];
        }
    }
    _nodes[ idx ] = obj;

    _degree += 1;

    return _nodes[ idx ];
}

template < class Key_T, class Obj_T >
Obj_T * BTreeBucketNode<Key_T,Obj_T>::
split( Key_T & key, Obj_T * obj, BTreeNodeBase *& newNode )
//---------------------------------------------------------
{
    BTreeBucketNode *   right;
    Obj_T *             ret;

    #if ( INSTRUMENTS == INSTRUMENTS_FULL_LOGGING )
    Log.printf( "splitting bucketnode -- obj %s\n", (const char *)(*obj) );
    #endif

    right = new BTreeBucketNode();

    try {
        if( ((const Key_T &)(*obj)).operator< ( (const Key_T &)(*_nodes[ _objOrder ]) ) ) {

            for( int i = 0; i < _objOrder + 1; i += 1 ) {
                right->_nodes[ i ] = _nodes[ _objOrder + i ];
            }

            right->_degree = _objOrder + 1;
            _degree = _objOrder;
            ret = privInsert( obj );
        } else {
            if( ((const Key_T &)(*obj)).operator== (
                                (const Key_T &)(*_nodes[ _objOrder ]) ) ) {

                #if INSTRUMENTS
                Log.printf( "DUPLICATE! %s =\n", (const char *) (*obj) );
                Log.printf( "           %s\n", (const char *) (*_nodes[ _objOrder ] ) );
                print( 0 );
                #endif

                BTreeExcept a( "Duplicate", BTreeExcept::Duplicate );
                throw( a );
            } else {
                for( int i = 0; i < _objOrder; i += 1 ) {
                    right->_nodes[ i ] = _nodes[ _objOrder + i + 1 ];
                }
                right->_degree = _objOrder;
                _degree = _objOrder + 1;
                ret = right->privInsert( obj );
            }
        }
    } catch( BTreeExcept( oops ) ) {
        // privInsert may throw a duplicate (or other) exception -- try
        // to clean up as best as possible

        delete right;
        right = NULL;
        newNode = NULL;
        _degree = _objOrder * 2 + 1;
        throw;  // re-throw oops
    }

    if( right ) {
        key.operator= ( (const Key_T &) (*right->_nodes[ 0 ]) );
    }
    newNode = right;

    #if ( INSTRUMENTS == INSTRUMENTS_FULL_LOGGING )
    Log.printf( "split bucketnode -- key, %s, oldnode, newnode\n", key.getString() );
    print(0);
    newNode->print(0);
    #endif

    return ret;
}

template < class Key_T, class Obj_T >
BTreeNodeBase< Key_T, Obj_T > *
BTreeBucketNode<Key_T,Obj_T>::
nextNode( int_16 & )
//-----------------------------------
{
    #if ( INSTRUMENTS == INSTRUMENTS_FULL_LOGGING )
    Log.printf( "BucketNode nextNode == NULL\n" );
    #endif

    return NULL;    // no nodes in buckets
}

template < class Key_T, class Obj_T >
Obj_T * BTreeBucketNode<Key_T,Obj_T>::
nextObj( int_16 & idx)
//------------------------------------
{
    #if ( INSTRUMENTS == INSTRUMENTS_FULL_LOGGING )
    Log.printf( "BucketNode %p, idx = %d, _degree = %d, return = %p\n",
                                    this, idx + 1, _degree, (idx +1 < _degree) ? _nodes[ idx + 1 ] : NULL );
    #endif

    idx += 1;
    if( idx >= _degree ) return NULL;

    return _nodes[ idx ];
}