---

CdbBdbSAbsBtree.hh

Go to the documentation of this file.

#ifndef CDBBDBSHARED_ABS_BTREE_HH
#define CDBBDBSHARED_ABS_BTREE_HH

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

#include "BdbUtil/Bdb.hh"

#include "CdbBase/CdbItr.hh"

#include "CdbBdbShared/CdbBdbSBtreeNode.hh"
#include "CdbBdbShared/CdbBdbSAbsBtreeItr.hh"

/// Default "fuzzy" search logic for entries
/**
  * By default exact match is expected.
  */
template< class K >
class CdbBdbSBtreeDefaultFCP {

public:

    static bool match( const K& object,
                       const K& subject )
    {
        return object == subject;
    }
};

/// An abstract class for B-tree (balanced tree)
/**
  * This template class implements the corresponding B-tree algorithms
  * for Objectivity embedded classes. The concrete storage for the B-tree
  * data structures is provided by derived classes.
  *
  * 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)
  *
  *     FCP - this is a policy class that is expected
  *           to provide the only method:
  *
  *         class <name> ... {
  *         public:
  *             static bool match( const K& source,
  *                                const K& target );
  *         };
  *
  *         This meathod is used for one-directional comparision of two
  *         keys. This operation is meant to answer a question if specified
  *         "source" key matches the "target" one.
  *
  *         It's not nessesary true that if "source" matches the "target"
  *         then the "targed" would match the "source" one.
  *
  *         The meaning of the "match" is up to the implementation
  *         of a concrete policy and type of keys (K).
  *
  *     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 FCP   = CdbBdbSBtreeDefaultFCP<K>,
          class ORDER = CdbBdbSBtreeDefaultOrder >
class CdbBdbSAbsBtree {

  // Let the actual implementation of the iterator to access internals
  // of the class.

    friend class CdbBdbSAbsBtreeItr<K,FCP,ORDER>;

protected:

    enum { N = ORDER::N };

public:

  /// Default constructor.
  /**
    * Creates an empty tree.
    */
    CdbBdbSAbsBtree( );

  /// Destructor
  /**
    * Destroys the tree.
    */
    virtual ~CdbBdbSAbsBtree( );

  /// Dump the tree
  /**
    * The dump is done onto a stream specified through the only parameter
    * of the method.
    */
    void dump( std::ostream& o ) const;

  /// Insert a key into the tree
  /**
    * Insert specified key into the tree. If the tree alredy has
    * such an element then just ignore it.
    */
    void insert( const K& key );

  /// Remove a key from the tree
  /**
    * Remove specified key from the tree. If the tree does not have
    * such an element then just ignore it.
    */
    void remove( const K& key );

  /// Search a key in the tree
  /**
    * This method will only look for the presence of specified
    * key in the tree. If there is such an entry it will just
    * return "true".
    */
    bool search( const K& key ) const;

  /// Extended search for a key in the tree
  /**
    * This method will look for the presence of specified
    * key in the tree.
    *
    * If there is such an entry then the method will return "true"
    * and a value of the found ("similar") key.
    */
    bool search( const K& key,
                 K&       result ) const;

  /// Search a key in the tree using "fuzzy" search logic
  /**
    * This method will use "fuzzy" logic to search for a key, which
    * is very similar to the one specified on the input. The "similarity"
    * is defined throught this (Btree) class template parameter.
    *
    * If there is such an entry then the method will return "true"
    * and a value of the found ("similar") key.
    */
    bool fuzzySearch( const K& key,
                      K&       result ) const;

  /// Reset the tree
  /**
    * This operation will remove all elements from the tree
    * except it's root node. The root node will get 0 keys.
    */
    void reset( );

  /// Get an instance of an iterator
  /**
    * This kind of iterator provides "non-sorted" access to the keys.
    */
    CdbItr<K> iterator( ) const;

protected:

  /// Get a root node of the B-tree
  /**
    * To be implemented by a storage provider of a derived class.
    */
    virtual d_ULong root( ) const = 0;

  /// Set new root node of the B-tree
  /**
    * To be implemented by a storage provider of a derived class.
    */
    virtual void set_root( d_ULong node ) = 0;

  /// Get a copy of specified node
  /**
    * To be implemented by a storage provider of a derived class.
    */
    virtual CdbBdbSBtreeNode<K,ORDER> readNode( d_ULong node ) const = 0;

  /// Save back the value of specified node
  /**
    * To be implemented by a storage provider of a derived class.
    */
    virtual void updateNode( d_ULong                          node,
                             const CdbBdbSBtreeNode<K,ORDER>& value ) = 0;

  /// Allocator
  /**
    * To be implemented by a storage provider of a derived class.
    */
    virtual d_ULong allocate( d_ULong parent = 0 ) = 0;

  /// Disposer
  /**
    * To be implemented by a storage provider of a derived class.
    */
    virtual void release( d_ULong node ) = 0;

private:

    /// A helper for the dump
    /**
      * Insert certain number of spaces into an output stream.
      */
    void spaces( std::ostream&     o,
                 unsigned int level ) const;

    /// Dump a node in the tree (recursive)
    /**
      * This is a recursive method. It will make a dump from specified
      * node through its dircet and indircet leaves.
      */
    void dump( std::ostream& o,
               d_ULong  node,
               unsigned int level ) const;

    /// The implementation of the search algorithm (recursive)
    /**
      * This method has the following communications:
      *
      * INPUT: A node to start the search with and the value of the key
      *        to look for.
      *
      * OUTPUT: Will return a non 0 address of a node containg the key if
      *         the one was found.
      */
    d_ULong doSearch( d_ULong  node,
                      const K& key ) const;

    /// The "fuzzy" logic implementation of the search algorithm (recursive)
    /**
      * This method has the following communications:
      *
      * INPUT: A node to start the search with and the value of the key
      *        to look for.
      *
      * OUTPUT: Will return a non 0 address of a node cotainig the key if
      *         the one was found. In this case the method will also return
      *         the value of the "approximate" key.
      */
    d_ULong doFuzzySearch( d_ULong  node,
                           const K& key,
                           K&       result ) const;

   /// Search for the leaf node
   /**
     * This algorithm will go down to a node where the specified key is supposed
     * to be insert. An address of that node will be returned.
     */
    d_ULong searchLeafForInsert( d_ULong  node,
                                 const K& key ) const;

   /// Insert only a key into a node
   /**
    * This method is equally applied to both leaf and non-leaf nodes.
    */
    void insertKeyOnly( d_ULong  node,
                        const K& key );

   /// Insert a key and replace old link at a node
   /**
    * This method can only be applied to non-leaf nodes that have enough room
    * for one more key. The method will also replace specified old link to a child
    * with two new ones.
    */
    void insertNoSplit( d_ULong  parent,
                        const K& key,
                        d_ULong  old,
                        d_ULong  left,
                        d_ULong  right );

   /// Insert a key, replace old link at a node, then split the node (recursive)
   /**
    * This method can only be applied to non-leaf nodes that is already full.
    */
    void insertAndSplit( d_ULong  parent,
                         const K& key,
                         d_ULong  old,
                         d_ULong  left,
                         d_ULong  right );

   /// Remove a key from a leaf node (recursive)
   /**
    * This method may also rebalance the tree if the number of element
    * in the node is less than allowed (N).
    *
    * NOTE: The minimum restriction of N does not apply to the root node
    *       if it's the only node in the tree.
    */
    void removeFromLeaf( d_ULong  node,
                         const K& key );

   /// Rebalance the tree starting from specified node (recursive)
   /**
    * A node passed to the method is the one having "underflow".
    */
    void rebalance( d_ULong node );

   /// Rebalance the tree by borrowing from a left node (recursive)
   /**
    * This "try" method is used to attemp borrowing a spare key
    * from any node left from the specified one.
    *
    * CONDITION: There's at least one node on the left possesing more
    *            than N keys.
    */
    bool borrowFromLeft( d_ULong right );

   /// Rebalance the tree by borrowing from a right node (recursive)
   /**
    * This "try" method is used to attemp borrowing a spare key
    * from any node right from the specified one.
    *
    * CONDITION: There's at least one node on the right possesing more
    *            than N keys.
    */
    bool borrowFromRight( d_ULong left );

   /// Rebalance the tree by joining with a neighbor node of the same parent
   /**
    * This "force" method will join with either neighbor,
    */
    void join( d_ULong node );

  /// Reset a sub-tree beneath (excluding) specified node (recursive)
  /**
    * This is a helper method.
    */
    void reset( d_ULong node );
};

#ifdef    BABAR_COMP_INST
#include "CdbBdbShared/CdbBdbSAbsBtree.cc"
#endif /* BABAR_COMP_INST */

#endif  // CDBBDBSHARED_ABS_BTREE_HH

---