---

CdbRooRoBtreeR.rdl

Go to the documentation of this file.

#ifndef CDBROOREADONLY_BTREE_R_RDL
#define CDBROOREADONLY_BTREE_R_RDL

// File and Version Information:
//      $Id: CdbRooRoBtreeR.rdl,v 1.1 2004/11/09 20:33:04 gapon Exp $

#include "CdbRooReadonly/CdbRooRoAbsBtreeR.hh"

#include <vector>

/// This is a persistent implementation for of a B-tree.
/**
  * This implementation requires that the whole contents of the B-tree were
  * stored in memory as a vector.
  *
  * NOTE: This model may not be efficient for operations with trees having
  *       many nodes (how many is as subject of a separate investigation
  *       for a specific values of template parameters).
  */
template< class  K,
          class  FCP   = CdbRooRoBtreeDefaultFCPR<K>,
          UInt_t ORDER = 4 >
class CdbRooRoBtreeR : public CdbRooRoAbsBtreeR<K,FCP,ORDER> {

public:

  // Constructors

    CdbRooRoBtreeR( );

  // Destructor

    virtual ~CdbRooRoBtreeR( ) { }

protected:

  /// Get a root node of the B-tree
  /**
    * Implements the corresponding method of the base class.
    *
    * @see CdbRooRoAbsBtreeR::root()
    */
    virtual UInt_t root( ) const { return _root; }

  /// Set new root node of the B-tree
  /**
    * Implements the corresponding method of the base class.
    *
    * @see CdbRooRoAbsBtreeR::root()
    */
    virtual void set_root( UInt_t node ) { _root = node; }

  /// Get a copy of specified node
  /**
    * Implements the corresponding method of the base class.
    *
    * @see CdbRooRoAbsBtreeR::readNode()
    */
    virtual CdbRooRoBtreeNodeR<K,ORDER> readNode( UInt_t node ) const { return _nodes[node]; }

  /// Save back the value of specified node
  /**
    * Implements the corresponding method of the base class.
    *
    * @see CdbRooRoAbsBtreeR::updateNode()
    */
    virtual void updateNode( UInt_t                             node,
                             const CdbRooRoBtreeNodeR<K,ORDER>& value ) { _nodes[node] = value; }

  /// Allocator
  /**
    * Implements the corresponding method of the base class.
    *
    * @see CdbRooRoAbsBtreeR::root()
    */
    virtual UInt_t allocate( UInt_t parent = 0 );

  /// Disposer
  /**
    * Implements the corresponding method of the base class.
    *
    * @see CdbRooRoAbsBtreeR::root()
    */
    virtual void release( UInt_t node );

private:

  /// This is in fact a normal/default constructor for specified node.
  /**
    * By default the node does not have a parent.
    */
    void init_node( UInt_t node,
                    UInt_t parent );

  /// Extend a list of free nodes
  /**
    * This list is only extended if it's empty.
    */
    void extend_free_list( );

private:

  /// The actual storage.
  /**
    * The first element of the array (index = 0) is not used, because
    * this number is meant to simulate "null pointer".
    *
    * The second element (index = 1) is used as a default root node.
    * This will change as the tree will expand.
    *
    * Initially spare elements begin from the index = 2.
    * This will also change as the tree will expand.
    */
    std::vector< CdbRooRoBtreeNodeR<K,ORDER> > _nodes;

  /// An index of the root node

    UInt_t _root;

  /// An index of the first spare node
  /**
    * These nodes form a linked list. So the first spare node is actually
    * the head of the list.
    */
    UInt_t _free;

  // This typedef is needed to avoid problems with the ClassDef macro used below.

    typedef CdbRooRoBtreeR<K,FCP,ORDER> MyType;

    ClassDef(MyType,1);
};

// Template class implementation

#ifndef __CINT__
#include "CdbRooReadonly/CdbRooRoBtreeR.cc"
#endif
#endif /* CDBROOREADONLY_BTREE_R_RDL */

---