---

CdbBdbSBtreeNode.hh

Go to the documentation of this file.

#ifndef CDBBDBSHARED_BTREE_NODE_HH
#define CDBBDBSHARED_BTREE_NODE_HH

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

#include "BdbUtil/Bdb.hh"

/// The default order of the B-tree
/**
  * NOTE: This order can't be changed after a persistent B-tree object
  *       is created.
  */
class CdbBdbSBtreeDefaultOrder {

public:

    enum { N = 2 };
};

/// An embeddable node class for the persistent capable B-tree.
/**
  * This template class implement nodes for the corresponding B-tree
  * data structures and related algorithms.
  *
  * The template is parametrized by mean of the following parameters:
  *
  *     K - is a type of keys. This type has to provide the following
  *         methods:
  *
  *             default constructor
  *             copy constructor
  *             destructor
  *
  *         and operators:
  *
  *             =
  *             ==
  *             <
  *             <<    (into std::ostream)
  *
  *     ORDER - is a utility class with the only usable enumeration
  *             specifying an order of the tree. Here is expected interface
  *             of this class:
  *
  *             class <name > ... {
  *             public:
  *                 enum { N = <order> };
  *             };
  *
  *         The reason why we're usingthis tricky way to specify the order
  *         instead of the non-class template parameter, like "unsigned ORDER",
  *         is that teh current version of the DDL compiler does not seem
  *         to support this kind of syntax.
  */
template< class K,
          class ORDER = CdbBdbSBtreeDefaultOrder >
class CdbBdbSBtreeNode {

public:

  // The default constructor will create an empty leaf node w/o a parent,
  // with no values and no children. The normal constructor will setup
  // a parent of the node.

    CdbBdbSBtreeNode( )           : parent(0), isLeaf(d_True), n(0) { }
    CdbBdbSBtreeNode( d_ULong p ) : parent(p), isLeaf(d_True), n(0) { }

  // The copy constructor
  /**
    */
    CdbBdbSBtreeNode( const CdbBdbSBtreeNode<K,ORDER>& theNode )
    {
        copySelf( theNode );
    }

  /// The destructor
  /**
    * NOTE: The destructor is NOT virtual because this is an embedded
    *       class.
    */
    ~CdbBdbSBtreeNode( ) { }

  // The assignment operator
  /**
    */
    CdbBdbSBtreeNode<K,ORDER>& operator=( const CdbBdbSBtreeNode<K,ORDER>& theNode )
    {
        if( this != &theNode ) copySelf( theNode );
        return *this;
    }

private:

  /// Set up own context from specified one
  /**
    * This helper method is used by constructors and assignment operator.
    */
    void copySelf( const CdbBdbSBtreeNode<K,ORDER>& theNode )
    {
        parent = theNode.parent;
        isLeaf = theNode.isLeaf;
        n      = theNode.n;
        for( unsigned int i = 0; i <= 2 * ORDER::N; ++i ) child[i] = theNode.child[i];
        for( unsigned int i = 0; i <  2 * ORDER::N; ++i ) key  [i] = theNode.key  [i];
    }

public:

  // Back link to the parent

    d_ULong parent;

  // There are 'n+1' pointers to child nodes.

    d_ULong child[ 2 * ORDER::N + 1 ];

  // There are 'n' keys in the node. The keys are sorted.

    K key[ 2 * ORDER::N ];

  // The leaf node does not have any children.

    d_Boolean isLeaf;

  // Occupancy for "root" node:        0 .. 2 * ORDER::N
  //               other nodes: ORDER::N .. 2 * ORDER::N

    d_Octet n;
};

template< class ORDER,
          class K >
std::ostream&
operator<<( std::ostream&                         o,
            const CdbBdbSBtreeNode<K,ORDER>& theNode )
{
    return o << theNode.parent;
}

#endif  // CDBBDBSHARED_BTREE_NODE_HH

---