---

CdbBdbSAbsBtree.cc

Go to the documentation of this file.

// File and Version Information:
//      $Id: CdbBdbSAbsBtree.cc,v 1.6 2004/08/06 05:54:24 bartoldu Exp $

/// Implementation file for the CdbBdbSAbsBtree class
/**
  * @see CdbBdbSAbsBtree
  */

#include "BaBar/BaBar.hh"

#if !defined(OO_DDL_TRANSLATION)
#include "CdbBdbShared/CdbBdbSAbsBtree.hh"
#endif // OO_DDL_TRANSLATION

#include <assert.h>
using std::endl;
using std::ostream;

template< class K,
          class FCP,
          class ORDER >
CdbBdbSAbsBtree<K,FCP,ORDER>::CdbBdbSAbsBtree( )
{ }

template< class K,
          class FCP,
          class ORDER >
CdbBdbSAbsBtree<K,FCP,ORDER>::~CdbBdbSAbsBtree( )
{ }

template< class K,
          class FCP,
          class ORDER >
void
CdbBdbSAbsBtree<K,FCP,ORDER>::dump( ostream& o ) const
{
    dump( o, root( ), 0 );
}

template< class K,
          class FCP,
          class ORDER >
void
CdbBdbSAbsBtree<K,FCP,ORDER>::insert( const K& key )
{
    if( ! search( key )) {

        d_ULong node = searchLeafForInsert( root( ), key );
        if( readNode( node ).n < 2*N ) {

            insertKeyOnly( node, key );

        } else {

            d_ULong parent = readNode( node ).parent;

          // Insert new element into a temporary array (has one more element
          // than allowed.

            K tmp[2*N+1];
            {
                tmp[2*N] = key;     // By default - just append. This may be overwriten
                                    // by the loop below if the element needs to be inserted.

                CdbBdbSBtreeNode<K,ORDER> nodeValue = readNode( node );
                {
                    K* iKeyPtr = &( nodeValue.key[0] );
                    K* oKeyPtr = &(           tmp[0] );

                    for( unsigned int i = 0; i < 2*N; ++i ) {
                        if( key < *iKeyPtr ) {

                          // Insert the key, copy the tail and break.

                            *(oKeyPtr++) = key;
                            for( unsigned int j = i; j < 2*N; ++j ) *(oKeyPtr++) = *(iKeyPtr++);

                            break;

                        } else {
                            *(oKeyPtr++) = *(iKeyPtr++);
                        }
                    }
                }
            }

          // Split the leaf only and promote the middle element up.

            d_ULong                   nLeft      = allocate( parent );
            CdbBdbSBtreeNode<K,ORDER> nLeftValue = readNode( nLeft );
            {
                nLeftValue.n = N;
                for( unsigned int i = 0; i < N; ++i ) nLeftValue.key[i] = tmp[i];
            }
            updateNode( nLeft, nLeftValue );

            d_ULong                   nRight      = allocate( parent );
            CdbBdbSBtreeNode<K,ORDER> nRightValue = readNode( nRight );
            {
                nRightValue.n = N;
                for( unsigned int i = 0; i < N; ++i ) nRightValue.key[i] = tmp[N+1+i];
            }
            updateNode( nRight, nRightValue );

          // The further scenario depends on which node we're going to split.
          // If it's the root node itself (which may happen if we're just filled
          // it up then we will split it by making it a non-leaf node.
          //
          // Otherwise we'll propagate this operation to a parent of
          // the current node

            if( parent ) {

              // Propagate operation up to the parent.

                if( readNode( parent ).n < 2*N ) {

                    insertNoSplit( parent,
                                   tmp[N],
                                   node,
                                   nLeft,
                                   nRight );
                } else {

                    insertAndSplit( parent,
                                    tmp[N],
                                    node,
                                    nLeft,
                                    nRight );
                }
                release( node );

            } else {

              // Promote the leaf root node onto a non-leaf one.

                CdbBdbSBtreeNode<K,ORDER> nodeValue = readNode( node );
                {
                    nodeValue.isLeaf = false;
                    nodeValue.n      = 1;

                    nodeValue.key[0] = tmp[N];

                    nodeValue.child[0] = nLeft;
                    nodeValue.child[1] = nRight;
                }
                updateNode( node, nodeValue );

                CdbBdbSBtreeNode<K,ORDER> nLeftValue = readNode( nLeft );
                {
                    nLeftValue.parent = node;
                }
                updateNode( nLeft, nLeftValue );

                CdbBdbSBtreeNode<K,ORDER> nRightValue = readNode( nRight );
                {
                    nRightValue.parent = node;
                }
                updateNode( nRight, nRightValue );
            }
        }
    }
}

template< class K,
          class FCP,
          class ORDER >
void
CdbBdbSAbsBtree<K,FCP,ORDER>::remove( const K& key )
{
    d_ULong node = doSearch( root( ), key );
    if( node ) {

        if( readNode( node ).isLeaf ) {

            removeFromLeaf( node, key );
            return;

        } else {

          // To removing from a non-leaf node we need to swap this key
          // with an appropriate (next) key in a leaf node below.
          // Then we just do removal from the leaf node.

            CdbBdbSBtreeNode<K,ORDER> nodeValue = readNode( node );

            for( unsigned int i = 0; i < nodeValue.n; ++i ) {
                if( key == nodeValue.key[i] ) {

                  // Find an appropriate leaf node for swapping.

                    d_ULong                   leafNode      = nodeValue.child[i+1];
                    CdbBdbSBtreeNode<K,ORDER> leafNodeValue = readNode( leafNode );

                    while( ! leafNodeValue.isLeaf ) {
                        leafNode      = leafNodeValue.child[0];
                        leafNodeValue = readNode( leafNode );
                    }

                  // Swap the keys
                  //
                  // NOTE: We must be careful with the actual values of the keys
                  //       because the comparision of the keys may be based on a subset
                  //       of information held by the corresponding objects.

                    K tmp = nodeValue.key[i];

                    nodeValue.key[i]     = leafNodeValue.key[0];
                    leafNodeValue.key[0] = tmp;

                    updateNode( node,     nodeValue );
                    updateNode( leafNode, leafNodeValue );

                  // Go and remove the key from the leaf.

                    removeFromLeaf( leafNode, key );
                    return;
                }
            }
        }
        assert( 0 );    // B-tree corruption. Failed to remove a key.
    }
}

template< class K,
          class FCP,
          class ORDER >
bool
CdbBdbSAbsBtree<K,FCP,ORDER>::search( const K& key ) const
{
    return 0 != doSearch( root( ),
                          key );
}

template< class K,
          class FCP,
          class ORDER >
bool
CdbBdbSAbsBtree<K,FCP,ORDER>::search( const K& key,
                                      K&       result ) const
{
    d_ULong node = doSearch( root( ),
                             key );
    if( node ) {

      // Search again for the key in the found node.
      //
      // NOTE: The search algorithm is a little bit inefficient
      //       in some sense because the presence of the target key
      //       has already been identified by the search algorithm

        CdbBdbSBtreeNode<K,ORDER> nodeValue = readNode( node );

        for( unsigned int i = 0; i < nodeValue.n; i++ ) {
            if( key == nodeValue.key[i] ) {
                result = nodeValue.key[i];
                return true;
            }
        }
        assert( 0 );    // B-tree corruption. Unexpected branch of execution.
    }
    return false;
}

template< class K,
          class FCP,
          class ORDER >
bool
CdbBdbSAbsBtree<K,FCP,ORDER>::fuzzySearch( const K& key,
                                           K&       result ) const
{
    return 0 != doFuzzySearch( root( ),
                               key,
                               result );
}

template< class K,
          class FCP,
          class ORDER >
void
CdbBdbSAbsBtree<K,FCP,ORDER>::reset( )
{
    reset( root( ));
}

template< class K,
          class FCP,
          class ORDER >
CdbItr<K>
CdbBdbSAbsBtree<K,FCP,ORDER>::iterator( ) const
{
  // ATTENTION: This is not a memory leak - the created object
  //            will be destroyed by the iterator.

    return CdbItr<K>( new CdbBdbSAbsBtreeItr<K,FCP,ORDER>( this ));
}

template< class K,
          class FCP,
          class ORDER >
void
CdbBdbSAbsBtree<K,FCP,ORDER>::spaces( ostream&     o,
                                      unsigned int level ) const
{
    for( int i = 0; i < 2*level; ++i ) o << ' ';
}

template< class K,
          class FCP,
          class ORDER >
void
CdbBdbSAbsBtree<K,FCP,ORDER>::dump( ostream&     o,
                                    d_ULong      node,
                                    unsigned int level ) const
{
    CdbBdbSBtreeNode<K,ORDER> nodeValue = readNode( node );

    spaces( o, level );

    o << node << ": [ ";
    for( int i = 0; i < nodeValue.n; ++i ) o << nodeValue.key[i] << ' ';
    o << "] "<< "< " << nodeValue.parent << " :";

    if( nodeValue.isLeaf ) {
        o << " >" << endl;
    } else {

        for( int i = 0; i < nodeValue.n + 1; ++i ) o << " " << nodeValue.child[i];
        o << " >" << endl;

        for( int i = 0; i < nodeValue.n + 1; ++i ) dump( o, nodeValue.child[i], level + 1 );
    }
}

template< class K,
          class FCP,
          class ORDER >
d_ULong
CdbBdbSAbsBtree<K,FCP,ORDER>::doSearch( d_ULong  node,
                                        const K& key ) const
{
  // The pointer must be valid and the node's occupancy must be non 0.

    if( node ) {

        CdbBdbSBtreeNode<K,ORDER> nodeValue = readNode( node );
        if( nodeValue.n ) {

          // Search for the key in the current node first.

            for( unsigned int i = 0; i < nodeValue.n; i++ )
                if( key == nodeValue.key[i] ) return node;

          // If the children are present then proceed the search doesn the tree.

            if( ! nodeValue.isLeaf ) {

                for( unsigned int i = 0; i < nodeValue.n; i++ )
                    if( key < nodeValue.key[i] ) return doSearch( nodeValue.child[i],
                                                                  key );

                return doSearch( nodeValue.child[ nodeValue.n ],
                                 key );
            }
        }
    }
    return 0;
}

template< class K,
          class FCP,
          class ORDER >
d_ULong
CdbBdbSAbsBtree<K,FCP,ORDER>::doFuzzySearch( d_ULong  node,
                                             const K& key,
                                             K&       result ) const
{
  // The pointer must be valid and the node's occupancy must be non 0.

    if( node ) {

        CdbBdbSBtreeNode<K,ORDER> nodeValue = readNode( node );
        if( nodeValue.n ) {

          // Search for an appropriate match in the current node first
          // using "fuzzy" comparision policy.

            for( unsigned int i = 0; i < nodeValue.n; i++ )
                if( FCP::match( key,
                                nodeValue.key[i] )) {
                    result = nodeValue.key[i];
                    return node;
                }

          // If the children are present then proceed the search doesn the tree.

            if( ! nodeValue.isLeaf ) {

                for( unsigned int i = 0; i < nodeValue.n; i++ )
                    if( key < nodeValue.key[i] ) return doFuzzySearch( nodeValue.child[i],
                                                                       key,
                                                                       result );

                return doFuzzySearch( nodeValue.child[ nodeValue.n ],
                                      key,
                                      result );
            }
        }
    }
    return 0;
}

template< class K,
          class FCP,
          class ORDER >
d_ULong
CdbBdbSAbsBtree<K,FCP,ORDER>::searchLeafForInsert( d_ULong  node,
                                                   const K& key ) const
{
    CdbBdbSBtreeNode<K,ORDER> nodeValue = readNode( node );
    if( nodeValue.isLeaf ) return node;

    for( unsigned int i = 0; i < nodeValue.n; i++ )
        if( key < nodeValue.key[i] ) return searchLeafForInsert( nodeValue.child[i],
                                                                 key );

    return searchLeafForInsert( nodeValue.child[ nodeValue.n ],
                                key );
}

template< class K,
          class FCP,
          class ORDER >
void
CdbBdbSAbsBtree<K,FCP,ORDER>::insertKeyOnly( d_ULong  node,
                                             const K& key )
{
  // Insert the key into a leaf node assuming that there is at least one place.

    CdbBdbSBtreeNode<K,ORDER> nodeValue = readNode( node );
    {
      // Check if new key needs to shift others.

        for( unsigned int i = 0; i < nodeValue.n; ++i )
            if( key < nodeValue.key[i] ) {

              // Shift one element right to have a room for the new key.

                for( unsigned int j = nodeValue.n; j > i; --j )
                    nodeValue.key[j] = nodeValue.key[j-1];

                nodeValue.key[i] = key;
                ++( nodeValue.n );

                updateNode( node, nodeValue );

                return;
            }

      // Append by the end of the list.

        nodeValue.key[ ( nodeValue.n )++ ] = key;
    }
    updateNode( node, nodeValue );

    return;
}

template< class K,
          class FCP,
          class ORDER >
void
CdbBdbSAbsBtree<K,FCP,ORDER>::insertNoSplit( d_ULong  parent,
                                             const K& key,
                                             d_ULong  old,
                                             d_ULong  left,
                                             d_ULong  right )
{
  // Insert new element into specified parent node. Also replace the old child with
  // a couple of new ones surrounding the newely inserted element.

    insertKeyOnly( parent, key );

  // Find the old child and replace it with new ones. Make a shift if needed
  // to have more room for the right child.
  //
  // NOTE: This operation assumes that the counter of the node's occupancy
  //       has already been incremented.

    CdbBdbSBtreeNode<K,ORDER> parentValue = readNode( parent );
    {
        for( unsigned int i = 0; i < parentValue.n; ++i ) {
            if( parentValue.child[i] == old ) {

              // Shift one element right to have a room for the new link.

                for( unsigned int j = parentValue.n; j > i; --j ) parentValue.child[j] = parentValue.child[j-1];

                parentValue.child[i]   = left;
                parentValue.child[i+1] = right;

                break;
            }
        }
    }
    updateNode( parent, parentValue );
}

template< class K,
          class FCP,
          class ORDER >
void
CdbBdbSAbsBtree<K,FCP,ORDER>::insertAndSplit( d_ULong  parent,
                                              const K& key,
                                              d_ULong  old,
                                              d_ULong  left,
                                              d_ULong  right )
{
  // Insert new element into specified parent node. Also replace the old child with
  // a couple of new ones surrounding the newely inserted element.
  // Split the parent.

    CdbBdbSBtreeNode<K,ORDER> parentValue = readNode( parent );
    {

      // Insert new element into a temporary array (has one more element
      // than allowed.

        K tmp[2*N+1];
        {
            tmp[2*N] = key;     // By default - just append. This may be overwriten
                                // by the loop below if the element needs to be inserted.

            K* iKeyPtr = &( parentValue.key[0] );
            K* oKeyPtr = &(             tmp[0] );

            for( unsigned int i = 0; i < 2*N; ++i ) {
                if( key < *iKeyPtr ) {

                  // Insert the key, copy the tail and break.

                    *(oKeyPtr++) = key;
                    for( unsigned int j = i; j < 2*N; ++j ) *(oKeyPtr++) = *(iKeyPtr++);

                    break;

                } else {
                    *(oKeyPtr++) = *(iKeyPtr++);
                }
            }
        }

      // Replace old link with two new ones in a temporary array (has one more element
      // than allowed.

        d_ULong tmp_child[2*N+2];
        {
          // Just copy all links into a temporary array.

            for( unsigned int i = 0; i < 2*N+1; ++i ) {
                tmp_child[i] = parentValue.child[i];
            }

          // Then insert new elements.

            for( unsigned int i = 0; i < 2*N+1; ++i ) {
                if( tmp_child[i] == old ) {

                  // Shift one element right to have a room for the new link.

                    for( unsigned int j = 2*N+1; j > i; --j ) tmp_child[j] = tmp_child[j-1];

                    tmp_child[i]   = left;
                    tmp_child[i+1] = right;

                    break;
                }
            }
        }

      // Split the parent and promote the middle element up.

        d_ULong                   parentOfParent      = parentValue.parent;
        CdbBdbSBtreeNode<K,ORDER> parentOfParentValue = readNode( parentOfParent );

        d_ULong                   nLeft      = allocate( parentOfParent );
        CdbBdbSBtreeNode<K,ORDER> nLeftValue = readNode( nLeft );
        {
            nLeftValue.isLeaf = false;
            nLeftValue.n      = N;

            for( unsigned int i = 0; i < N;   ++i ) nLeftValue.key[i] = tmp[i];
            for( unsigned int i = 0; i < N+1; ++i ) {

                nLeftValue.child[i] = tmp_child[i];

                CdbBdbSBtreeNode<K,ORDER> nLeftChildValue = readNode( nLeftValue.child[i] );
                { nLeftChildValue.parent = nLeft; }
                updateNode( nLeftValue.child[i], nLeftChildValue );
            }
        }
        updateNode( nLeft, nLeftValue );

        d_ULong                   nRight      = allocate( parentOfParent );
        CdbBdbSBtreeNode<K,ORDER> nRightValue = readNode( nRight );
        {
            nRightValue.isLeaf = false;
            nRightValue.n      = N;

            for( unsigned int i = 0; i < N;   ++i ) nRightValue.key[i] = tmp[N+1+i];
            for( unsigned int i = 0; i < N+1; ++i ) {

                nRightValue.child[i] = tmp_child[N+1+i];

                CdbBdbSBtreeNode<K,ORDER> nRightChildValue = readNode( nRightValue.child[i] );
                { nRightChildValue.parent = nRight; }
                updateNode( nRightValue.child[i], nRightChildValue );
            }
        }
        updateNode( nRight, nRightValue );

        if( parentOfParent ) {

          // Follow the split if the "parent of parent" is not a root node.

            if( parentOfParentValue.n < 2*N ) {

                insertNoSplit( parentOfParent,
                               tmp[N],
                               parent,
                               nLeft,
                               nRight );
            } else {

                insertAndSplit( parentOfParent,
                                tmp[N],
                                parent,
                                nLeft,
                                nRight );
            }

        } else {

          // Create new root.

            d_ULong                   newRoot      = allocate( );
            CdbBdbSBtreeNode<K,ORDER> newRootValue = readNode( newRoot );
            {
                newRootValue.isLeaf = false;
                newRootValue.n      = 1;

                newRootValue.key[0] = tmp[N];

                newRootValue.child[0] = nLeft;
                newRootValue.child[1] = nRight;

                CdbBdbSBtreeNode<K,ORDER> nLeftValue = readNode( nLeft );
                { nLeftValue.parent = newRoot; }
                updateNode( nLeft, nLeftValue );

                CdbBdbSBtreeNode<K,ORDER> nRightValue = readNode( nRight );
                { nRightValue.parent = newRoot; }
                updateNode( nRight, nRightValue );
            }
            updateNode( newRoot, newRootValue );

            set_root( newRoot );
        }
    }
    release( parent );
}

template< class K,
          class FCP,
          class ORDER >
void
CdbBdbSAbsBtree<K,FCP,ORDER>::removeFromLeaf( d_ULong  node,
                                              const K& key )
{
  // Remove element no mattter if less than allowed is left.
  // The subsequent rebalancing will correct this situation if needed.

    CdbBdbSBtreeNode<K,ORDER> nodeValue = readNode( node );
    {
        for( unsigned int i = 0; i < nodeValue.n; ++i ) {
            if( key == nodeValue.key[i] ) {

                for( unsigned int j = i; j < nodeValue.n - 1; ++j )
                    nodeValue.key[j] = nodeValue.key[j+1];

                --( nodeValue.n );

                break;
            }
        }
    }
    updateNode( node, nodeValue );

  // If this is the root node then we are allowed
  // to remove all elements.

    if(( ! nodeValue.parent ) || ( nodeValue.n >= N )) {

      // No repalancing is needed.

        ;

    } else {

      // Go to rebalance the tree

        rebalance( node );
    }
}

template< class K,
          class FCP,
          class ORDER >
void
CdbBdbSAbsBtree<K,FCP,ORDER>::rebalance( d_ULong node )
{
    d_ULong parent = readNode( node ).parent;

    assert( parent );   // B-tree corruption. Unexpected branch of execution.

 // Try simplest methods first.

    if( borrowFromLeft ( node )) return;
    if( borrowFromRight( node )) return;

  // Force joining with neighbors.

    join( node );

  // Check if previous has triggered "underflow" condition
  // at the parent.

    CdbBdbSBtreeNode<K,ORDER> parentValue = readNode( parent );
    if( parentValue.n < N ) {

      // The root node needs special processing.

        d_ULong parentOfParent = parentValue.parent;
        if( ! parentOfParent ) {

            if( 0 == parentValue.n ) {

                d_ULong newRoot = parentValue.child[0];
                {
                    CdbBdbSBtreeNode<K,ORDER> newRootValue = readNode( newRoot );
                    { newRootValue.parent = 0; }
                    updateNode( newRoot, newRootValue );
                }
                set_root( newRoot );

                release( parent );
            }

        } else {

          // Proceed up with rebalancing of a regular "underflow"-ed
          // non-leaf node.

            rebalance( parent );
        }
    }
}

template< class K,
          class FCP,
          class ORDER >
bool
CdbBdbSAbsBtree<K,FCP,ORDER>::borrowFromLeft( d_ULong right )
{
    d_ULong parent = readNode( right ).parent;

    assert( parent );   // B-tree corruption. Unexpected branch of execution.

    CdbBdbSBtreeNode<K,ORDER> parentValue = readNode( parent );

    for( unsigned int i = 0; i < parentValue.n + 1; ++i ) {
        if( right == parentValue.child[i] ) {
            if( i ) {

                d_ULong left = parentValue.child[i-1];

              // Check if there is one extra key in _any_ left node of the current parent.
              //
              // NOTE: Effectivly what we're doing is a right shift for one key
              //       through the parent using as many nodes from the left
              //       as we have in our disposal.
              //
              // IMPLEMENTATION NOTE: This little optimization has to be studied
              //                      to prove the overall performance improvement
              //                      for the removal algorithm. What we expect
              //                      to gain by this optimization is to reduce
              //                      the chance for other (heavier) rebalancing
              //                      methods to be triggered.

                if(( readNode( left ).n > N ) || borrowFromLeft( left )) {

                  // Re-read parent and left nodes since they might be modified as a result
                  // recursive borrowing from the left.

                    CdbBdbSBtreeNode<K,ORDER> parentValue = readNode( parent );
                    CdbBdbSBtreeNode<K,ORDER> leftValue   = readNode( left );
                    CdbBdbSBtreeNode<K,ORDER> rightValue  = readNode( right );
                    {
                      // Copy middle key from the parent and insert it as the left-most
                      // key of the right node to have enough (N) keys in there.

                        for( unsigned int j = rightValue.n; j > 0; --j ) {
                            rightValue.key[j] = rightValue.key[j-1];
                        }
                        rightValue.key[0] = parentValue.key[i-1];
                        ++( rightValue.n );

                      // Remove the right-most key from the left node and put it
                      // instead of the middle key of the parent.

                        parentValue.key[i-1] = leftValue.key[ --( leftValue.n ) ];

                      // Remove the right-most child from the left node and insert it
                      // as the left-most child of the right node to have N+1 children in here.

                        if( ! rightValue.isLeaf ) {
                            for( unsigned int j = rightValue.n; j > 0; --j ) {
                                rightValue.child[j] = rightValue.child[j-1];
                            }
                            rightValue.child[0] = leftValue.child[ leftValue.n + 1 ];

                            CdbBdbSBtreeNode<K,ORDER> newLeftMostChild = readNode( rightValue.child[0] );
                            { newLeftMostChild.parent = right; }
                            updateNode( rightValue.child[0], newLeftMostChild );
                        }
                    }
                    updateNode( parent, parentValue );
                    updateNode( left,   leftValue   );
                    updateNode( right,  rightValue  );

                  // Success.

//                    cout << "borrowFromLeft:" << endl;
//                    dump( cout );

                    return true;
                }
            }
        }
    }
    return false;
}

template< class K,
          class FCP,
          class ORDER >
bool
CdbBdbSAbsBtree<K,FCP,ORDER>::borrowFromRight( d_ULong left )
{
    d_ULong parent = readNode( left ).parent;

    assert( parent );   // B-tree corruption. Unexpected branch of execution.

    CdbBdbSBtreeNode<K,ORDER> parentValue = readNode( parent );

    for( unsigned int i = 0; i < parentValue.n; ++i ) {
        if( left == parentValue.child[i] ) {

            d_ULong right = parentValue.child[i+1];

          // Check if there is one extra key in _any_ right node on the current parent.
          //
          // NOTE: Effectivly what we're doing is a right shift for one key
          //       through the parent using as many nodes from the right
          //       as we have in our disposal.
          //
          // IMPLEMENTATION NOTE: This little optimization has to be studied
          //                      to prove the overall performance improvement
          //                      for the removal algorithm. What we expect
          //                      to gain by this optimization is to reduce
          //                      the chance for other (heavier) rebalancing
          //                      methods to be triggered.

            if(( readNode( right ).n > N ) || borrowFromRight( right )) {

              // Re-read parent and right nodes since they might be modified as a result
              // recursive borrowing from the right.

                CdbBdbSBtreeNode<K,ORDER> parentValue = readNode( parent );
                CdbBdbSBtreeNode<K,ORDER> leftValue   = readNode( left );
                CdbBdbSBtreeNode<K,ORDER> rightValue  = readNode( right );
                {

                  // Copy middle key from the parent and append it as the right-most
                  // key in the left node to have enough (N) keys in there.

                    leftValue.key[ ( leftValue.n )++ ] = parentValue.key[i];

                  // Remove the left-most key from the right node and put it
                  // instead of the middle key of the parent.

                    parentValue.key[i] = rightValue.key[0];

                    --( rightValue.n );
                    for( unsigned int j = 0; j < rightValue.n; ++j ) {
                        rightValue.key[j] = rightValue.key[j+1];
                    }

                  // Remove the left-most child from the right node and append it
                  // as the right-most child of the left node to have N+1 children in here.

                    if( ! leftValue.isLeaf ) {

                        CdbBdbSBtreeNode<K,ORDER> newRightMostChild = readNode( rightValue.child[0] );
                        { newRightMostChild.parent = left; }
                        updateNode( rightValue.child[0], newRightMostChild );

                        leftValue.child[ leftValue.n ] = rightValue.child[0];
                        for( unsigned int j = 0; j < rightValue.n + 1; ++j ) {
                            rightValue.child[j] = rightValue.child[j+1];
                        }
                    }
                }
                updateNode( parent, parentValue );
                updateNode( left,   leftValue   );
                updateNode( right,  rightValue  );

              // Success.

                return true;
            }
        }
    }
    return false;
}

template< class K,
          class FCP,
          class ORDER >
void
CdbBdbSAbsBtree<K,FCP,ORDER>::join( d_ULong node )
{
    d_ULong parent = readNode( node ).parent;

    assert( parent );           // B-tree corruption. Unexpected branch of execution.

    CdbBdbSBtreeNode<K,ORDER> parentValue = readNode( parent );
    
    assert( parentValue.n );    // B-tree corruption. Unexpected branch of execution.

    for( unsigned int i = 0; i < parentValue.n + 1; ++i ) {
        if( node == parentValue.child[i] ) {

          // Try left leaf

            if( i ) {

                d_ULong left = parentValue.child[i-1];

                CdbBdbSBtreeNode<K,ORDER> leftValue = readNode( left );
                CdbBdbSBtreeNode<K,ORDER> nodeValue = readNode( node );

                if(( leftValue.n + 1 + nodeValue.n ) == 2*N ) {

                    unsigned int left_n_before = leftValue.n;

                  // Copy the middle key from the parent and append it as the right-most
                  // key of the left node.

                    leftValue.key[ ( leftValue.n )++ ] = parentValue.key[i-1];

                  // Copy remaining keys from the node and append them as right-most elements
                  // of the left node.

                    for( unsigned int j = 0; j < nodeValue.n; ++j )
                        leftValue.key[ ( leftValue.n )++ ] = nodeValue.key[j];

                  // Shrink the parent by one node. In fact we're going
                  // to make left shift operation.

                    for( unsigned int j = i; j < parentValue.n; ++j )
                        parentValue.key[j-1] = parentValue.key[j];

                    for( unsigned int j = i; j < parentValue.n; ++j )
                        parentValue.child[j] = parentValue.child[j+1];

                    --( parentValue.n );
                    
                  // Copy all the children of the current node and append them
                  // as the right-most children of the left node.

                    if( ! nodeValue.isLeaf ) {
                        for( unsigned int j = 0; j < nodeValue.n + 1; ++j ) {

                            CdbBdbSBtreeNode<K,ORDER> newRightMostChild = readNode( nodeValue.child[j] );
                            { newRightMostChild.parent = left; }
                            updateNode( nodeValue.child[j], newRightMostChild );

                            leftValue.child[++left_n_before] = nodeValue.child[j];
                        }
                    }

                    updateNode( parent, parentValue );
                    updateNode( left,   leftValue   );
                    updateNode( node,   nodeValue   );

                  // Destroy the emptied node.

                    release( node );

                  // Success.

                    return;
                }
            }

          // Try right leaf

            if( i < parentValue.n ) {

                d_ULong right = parentValue.child[i+1];

                CdbBdbSBtreeNode<K,ORDER> nodeValue  = readNode( node );
                CdbBdbSBtreeNode<K,ORDER> rightValue = readNode( right );

                if(( nodeValue.n + 1 + rightValue.n ) == 2*N ) {

                    unsigned int node_n_before = nodeValue.n;

                  // Copy the middle key from the parent and append it as the right-most
                  // key of the current node.

                    nodeValue.key[ ( nodeValue.n )++ ] = parentValue.key[i];

                  // Copy keys from the right node and append them as right-most elements
                  // of the current node.

                    for( unsigned int j = 0; j < rightValue.n; ++j )
                        nodeValue.key[ ( nodeValue.n )++ ] = rightValue.key[j];

                  // Shrink the parent by one node. In fact we're going
                  // to make left shift operation.

                    --( parentValue.n );

                    for( unsigned int j = i; j < parentValue.n; ++j )
                        parentValue.key[j] = parentValue.key[j+1];

                    for( unsigned int j = i + 1; j < parentValue.n + 1; ++j )
                        parentValue.child[j] = parentValue.child[j+1];
                    
                  // Copy all the children of the right node and append them
                  // as the right-most children of the current node.

                    if( ! nodeValue.isLeaf ) {
                        for( unsigned int j = 0; j < rightValue.n + 1; ++j ) {

                            CdbBdbSBtreeNode<K,ORDER> newRightMostChild = readNode( rightValue.child[j] );
                            { newRightMostChild.parent = node; }
                            updateNode( rightValue.child[j], newRightMostChild );

                            nodeValue.child[++node_n_before] = rightValue.child[j];
                        }
                    }

                    updateNode( parent, parentValue );
                    updateNode( node,   nodeValue   );
                    updateNode( right,  rightValue  );

                  // Destroy the emptied node.

                    release( right );

                  // Success.

                    return;
                }
            }

          // Both scenarios have failed.

            break;
        }
    }
    assert( 0 );    // B-tree corruption. Unexpected branch of execution.
}

template< class K,
          class FCP,
          class ORDER >
void
CdbBdbSAbsBtree<K,FCP,ORDER>::reset( d_ULong node )
{
    CdbBdbSBtreeNode<K,ORDER> nodeValue = readNode( node );
    {
        if( ! nodeValue.isLeaf ) {
            for( int i = 0; i < nodeValue.n + 1; ++i ) {
                reset  ( nodeValue.child[i] );
                release( nodeValue.child[i] );
            }
            nodeValue.isLeaf = true;
        }
        nodeValue.n = 0;
    }
    updateNode( node, nodeValue );
}

/////////////////
// End Of File //
/////////////////

---