MOAB: Mesh Oriented datABase  (version 5.4.0)
TypeSequenceManager.hpp
Go to the documentation of this file.
00001 #ifndef TYPE_SEQUENCE_MANAGER_HPP
00002 #define TYPE_SEQUENCE_MANAGER_HPP
00003 
00004 #include "EntitySequence.hpp"
00005 #include "moab/Range.hpp"
00006 
00007 #include <set>
00008 #include <vector>
00009 
00010 namespace moab
00011 {
00012 
00013 class Error;
00014 
00015 /**\brief Maintain data structures organizing EntitySequence instances
00016  *
00017  * EntitySequenceManager is a composition of instances of TypeSequenceManager,
00018  * one instance for each EntityType.  The TypeSequenceManager provides
00019  * organization, ownership, and querying of EntitySequences for a specific
00020  * EntityType.
00021  */
00022 class TypeSequenceManager
00023 {
00024   public:
00025     /**\brief Comparison function used in std::set
00026      *
00027      * Define less-than comparison for EntitySequence pointers as a comparison
00028      * of the entity handles in the pointed-to EntitySequences.
00029      */
00030     template < class T >
00031     class SequenceCompare
00032     {
00033       public:
00034         inline bool operator()( const T* a, const T* b ) const
00035         {
00036             return a->end_handle() < b->start_handle();
00037         }
00038     };
00039     /**\brief Dummy EntitySequence for use in querying set container */
00040     class DummySequence : public EntitySequence
00041     {
00042       public:
00043         DummySequence( EntityHandle start ) : EntitySequence( start ) {}
00044 
00045         EntitySequence* split( EntityHandle )
00046         {
00047             return 0;
00048         }
00049         SequenceData* create_data_subset( EntityHandle, EntityHandle ) const
00050         {
00051             return 0;
00052         }
00053 
00054         void get_const_memory_use( unsigned long& a, unsigned long& b ) const
00055         {
00056             a = b = 0;
00057         }
00058         unsigned long get_per_entity_memory_use( EntityHandle, EntityHandle ) const
00059         {
00060             return 0;
00061         }
00062     };
00063 
00064     /**\brief Type of container for organizing EntitySequence instances */
00065     typedef std::set< EntitySequence*, SequenceCompare< EntitySequence > > set_type;
00066     /**\brief Iterator for set_type */
00067     typedef set_type::iterator iterator;
00068     /**\brief Iterator for set_type */
00069     typedef set_type::const_iterator const_iterator;
00070     /**\brief Type of container for organizing SequenceData instances */
00071     typedef std::set< SequenceData*, SequenceCompare< SequenceData > > data_set_type;
00072     /**\brief iterator type for data_set_type */
00073     typedef data_set_type::iterator data_iterator;
00074 
00075     struct SequenceDataPtr
00076     {
00077       private:
00078         friend class TypeSequenceManager;
00079         TypeSequenceManager::iterator firstSequence;
00080     };
00081 
00082   private:
00083     mutable EntitySequence* lastReferenced;  //!< Last accessed EntitySequence - Null only if no sequences
00084     set_type sequenceSet;                    //!< Set of all managed EntitySequence instances
00085     data_set_type availableList;             //!< SequenceData containing unused entries
00086 
00087     iterator erase( iterator i );  //!< Remove a sequence
00088 
00089     iterator split_sequence( iterator i, EntityHandle h );  //!< split a sequence
00090 
00091     void append_memory_use( EntityHandle first,
00092                             EntityHandle last,
00093                             const SequenceData* data,
00094                             unsigned long long& entity_storage,
00095                             unsigned long long& total_storage ) const;
00096 
00097     // check if sequence at passed iterator should be merged with
00098     // the subsequent sequence, and if so merge them retaining i.
00099     ErrorCode check_merge_next( iterator i );
00100     // check if sequence at passed iterator should be merged with
00101     // the previous sequence, and if so merge them retaining i.
00102     ErrorCode check_merge_prev( iterator i );
00103     // common code for check_merge_next and check_merge_prev
00104     ErrorCode merge_internal( iterator keep, iterator dead );
00105 
00106 #ifndef NDEBUG
00107     bool check_valid_data( const EntitySequence* seq ) const;
00108 #endif
00109 
00110   public:
00111     /**\brief Add an entity sequence
00112      *
00113      * Take ownership of passed EntitySequence, and update relevant
00114      * data structures.  Sequence may not overlap with any existing
00115      * sequence.
00116      *
00117      * NOTE:  Sequence may be merged with other, existing sequences.
00118      *        This function will always ensure that the passed
00119      *        EntitySequence* is the remaining one, but the passed
00120      *        sequence may have modified start and end handles.
00121      */
00122     ErrorCode insert_sequence( EntitySequence* seq_ptr );
00123 
00124     /**\brief Remove an entity sequence.
00125      *
00126      * Give up ownership of specified EntitySequence, and remove it
00127      * from all internal data structures.  Passes back bool flag to
00128      * notify caller that ownership of the corresponding SequenceData
00129      * is also relinquished because the specified EntitySequence is
00130      * the last one referencing it.
00131      */
00132     ErrorCode remove_sequence( const EntitySequence* seq_ptr, bool& is_last_user_of_sequence_data );
00133 
00134     /**\brief Replace sequence or subset of sequence
00135      *
00136      * Replace one sequence or a subset of one sequence with
00137      * another sequence.  With fail if a) the existing
00138      * sequence is not a subset of an existing sequence or
00139      * b) existing sequence shares a SequenceData with the
00140      * passed sequence.
00141      *
00142      * This method is provided for use when changing the
00143      * number of nodes in elements.
00144      */
00145     ErrorCode replace_subsequence( EntitySequence* seq_ptr, const int* tag_sizes, int num_tag_sizes );
00146 
00147     TypeSequenceManager() : lastReferenced( 0 ) {}
00148 
00149     ~TypeSequenceManager();
00150 
00151     /**\brief Start of EntitySequence set */
00152     const_iterator begin() const
00153     {
00154         return sequenceSet.begin();
00155     }
00156     iterator begin()
00157     {
00158         return sequenceSet.begin();
00159     }
00160 
00161     /**\brief End of EntitySequence set */
00162     const_iterator end() const
00163     {
00164         return sequenceSet.end();
00165     }
00166     iterator end()
00167     {
00168         return sequenceSet.end();
00169     }
00170 
00171     /**\brief Return EntitySequence for specified handle.
00172      *
00173      *  Return EntitySequence for specified handle, or if
00174      *  no such sequence, the next one.  Returns end() if
00175      *  all sequences have ranges less than specified handle.
00176      */
00177     const_iterator lower_bound( EntityHandle h ) const
00178     {
00179         DummySequence f( h );
00180         return sequenceSet.lower_bound( &f );
00181     }
00182     iterator lower_bound( EntityHandle h )
00183     {
00184         DummySequence f( h );
00185         return sequenceSet.lower_bound( &f );
00186     }
00187 
00188     /**\brief Return EntitySequence after specified handle.
00189      *
00190      *  Return EntitySequence with smallest start handle
00191      *  that is greater than input handle.  Returns end() if
00192      *  all sequences have start handles less than specified
00193      *  handle.
00194      */
00195     const_iterator upper_bound( EntityHandle h ) const
00196     {
00197         DummySequence f( h );
00198         return sequenceSet.upper_bound( &f );
00199     }
00200 
00201     /**\brief Get EntitySequence for handle.
00202      *\return EntitySequence for handle, or NULL if no such sequence.
00203      */
00204     inline EntitySequence* find( EntityHandle h ) const;
00205     inline EntitySequence* find( EntityHandle h );
00206     inline ErrorCode find( EntityHandle h, EntitySequence*& );
00207     inline ErrorCode find( EntityHandle h, const EntitySequence*& ) const;
00208     inline const EntitySequence* get_last_accessed() const;
00209 
00210     /**\brief Get handles for all entities in all sequences. */
00211     inline void get_entities( Range& entities_out ) const;
00212 
00213     /**\brief Get handles for all entities in all sequences. */
00214     inline void get_entities( std::vector< EntityHandle >& entities_out ) const;
00215 
00216     /**\brief Get number of entities represented by all sequences. */
00217     inline EntityID get_number_entities() const;
00218 
00219     ErrorCode check_valid_handles( Error* error_handler, EntityHandle first, EntityHandle last ) const;
00220 
00221     /**\brief Remove entities
00222      *
00223      * Update EntitySequence data as necessary to "delete" the
00224      * specified entities (e.g. split sequences, delete sequences,
00225      * free SequenceData instances, etc.)
00226      */
00227     ErrorCode erase( Error* error_handler, EntityHandle first, EntityHandle last );
00228     ErrorCode erase( Error* error_handler, EntityHandle entity );
00229 
00230     /**\brief Test if this instance contains no sequences */
00231     bool empty() const
00232     {
00233         return 0 == lastReferenced;
00234     }
00235 
00236     /**\brief Allocate a handle in an existing entity sequence
00237      *
00238      * Find an existing entity sequence to which a new handle can
00239      * be prepended or appended.  The 'append_out' flag indicates
00240      * to the caller that the new handle should be appended to the
00241      * returned sequence if true, and prepended if false.
00242      *
00243      * If no appropriate EntitySequence is available, NULL will
00244      * be returned.  The caller will typically then want to use
00245      * find_free_sequence() to find appropriate values for the
00246      * creation of a new EntitySequence.
00247      */
00248     iterator find_free_handle( EntityHandle min_start_handle,
00249                                EntityHandle max_end_handle,
00250                                bool& append_out,
00251                                int values_per_ent = 0 );
00252 
00253     /**\brief Find block of free handles
00254      *
00255      * Find block of free handles, such that block does not
00256      * overlap any existing EntitySequence.
00257      *\return First handle of block, or zero if no block found.
00258      */
00259     EntityHandle find_free_block( EntityID num_entities, EntityHandle min_start_handle, EntityHandle max_end_handle );
00260 
00261     /**\brief Find block of free handles
00262      *
00263      * Find block of free handles, such that block a) does not
00264      * overlap any existing EntitySequence and b) is either
00265      * entirely within one existing SequenceData or does not
00266      * overlap any SequenceData.
00267      *\param num_entities      Size of handle block.
00268      *\param min_start_handle  Block may not contain any handle less than this.
00269      *\param max_end_handle    Block may not contain any handle greater than this.
00270      *\param sequence_data_out If block is within an unused portion of an
00271      *                         existing SequenceData, a pointer to that
00272      *                         SequenceData.  NULL otherwise.
00273      *\return values_per_ent   Matched against EntitySequence::values_per_entity.
00274      *                         An existing SequenceData will not be returned if
00275      *                         the existing EntitySequences using have a different
00276      *                         value than the passed one.
00277      */
00278     EntityHandle find_free_sequence( EntityID num_entities,
00279                                      EntityHandle min_start_handle,
00280                                      EntityHandle max_end_handle,
00281                                      SequenceData*& sequence_data_out,
00282                                      EntityID& sequence_data_size,
00283                                      int values_per_ent = 0 );
00284 
00285     /**\brief Check if block of handles is free.
00286      *
00287      * Check if block of handles is free and can be allocated
00288      * as a single EntitySequence.  If the block of handles
00289      * is contained within an unused portion of a SequenceData,
00290      * the SequenceData is returned.
00291      */
00292     bool is_free_sequence( EntityHandle start_handle,
00293                            EntityID num_entities,
00294                            SequenceData*& sequence_data_out,
00295                            int values_per_ent = 0 );
00296 
00297     /**\brief Check if specific handle is free for allocation
00298      *
00299      * Check if a specific handle is not currently allocated
00300      * and can be allocated with the passed value of values_per_ent.
00301      * For example, the handle may not be allocated, but it may
00302      * fall within an existing SequenceData.  In that case, it
00303      * must be possible to store the specified values_per_ent
00304      * in the existing SequenceData.
00305      *
00306      * There are four possible return 'states' from this function:
00307      *
00308      * - handle is not available or cannot be allocated with specified
00309      *   values_per_ent.  Returned error code is MB_ALREADY_ALLOCATED.
00310      *
00311      * - handle can be appended or prepended to an existing sequence.
00312      *   seq_ptr_out is set to the sequence the handle should be added to.
00313      *
00314      * - handle cannot be appended to an existing sequence but falls
00315      *   within an existing SequenceData. The caller is expected
00316      *   to create a new sequence referencing that SequenceData. seq_ptr_out
00317      *   is NULL and data_ptr_out is set to existing SequenceData.
00318      *
00319      * - handle does not correspond to any existing sequence or data.
00320      *   The caller is expected to create a new sequence and SequenceData.
00321      *   Both seq_ptr_out and data_ptr_out are set to NULL.
00322      *   block_start and block_end are set to start and end handles of the
00323      *   largest sequence that can be allocated and contain the input handle.
00324      *
00325      *\param handle The handle the caller wishes to allocate as a new entity
00326      *\param seq_ptr_out Output: pointer to sequence to append or prepend to
00327      *              to allocate handle.  end() if no such sequence.
00328      *\param data_ptr_out Output: Pointer to existing SequenceData containing input
00329      *              handle, or NULL if no such SequenceData.
00330      *\param block_start Output: Smallest possible start handle for new sequence.
00331      *\param block_end   Output: Largest possible end handle for new sequence.
00332      */
00333     ErrorCode is_free_handle( EntityHandle handle,
00334                               iterator& seq_ptr_out,
00335                               SequenceData*& data_ptr_out,
00336                               EntityHandle& block_start,
00337                               EntityHandle& block_end,
00338                               int values_per_ent = 0 );
00339 
00340     EntityHandle last_free_handle( EntityHandle after_this ) const;
00341 
00342     /**\brief Notify that sequence was prepended to
00343      *
00344      * Notify of sequence modifications so we can check if
00345      * sequence needs to be merged.
00346      */
00347     ErrorCode notify_prepended( iterator seq );
00348 
00349     /**\brief Notify that sequence was appended to
00350      *
00351      * Notify of sequence modifications so we can check if
00352      * sequence needs to be merged.
00353      */
00354     ErrorCode notify_appended( iterator seq );
00355 
00356     void get_memory_use( unsigned long long& total_entity_storage, unsigned long long& total_storage ) const;
00357 
00358     void get_memory_use( EntityHandle start,
00359                          EntityHandle end,
00360                          unsigned long long& total_entity_storage,
00361                          unsigned long long& total_amortized_storage ) const;
00362 
00363     unsigned long get_sequence_count() const
00364     {
00365         return sequenceSet.size();
00366     }
00367 
00368     /**\brief Get used size of SequenceData
00369      *
00370      * Get the sum of the size of all EntitySequences referencing
00371      * a SequenceData.  Used for memory use calculations.
00372      */
00373     EntityID get_occupied_size( const SequenceData* ) const;
00374 };
00375 
00376 inline EntitySequence* TypeSequenceManager::find( EntityHandle h ) const
00377 {
00378     if( !lastReferenced )  // only null if empty
00379         return 0;
00380     else if( h >= lastReferenced->start_handle() && h <= lastReferenced->end_handle() )
00381         return lastReferenced;
00382     else
00383     {
00384         DummySequence seq( h );
00385         const_iterator i = sequenceSet.find( &seq );
00386         return i == end() ? 0 : ( lastReferenced = *i );
00387     }
00388 }
00389 inline EntitySequence* TypeSequenceManager::find( EntityHandle h )
00390 {
00391     if( !lastReferenced )  // only null if empty
00392         return 0;
00393     else if( h >= lastReferenced->start_handle() && h <= lastReferenced->end_handle() )
00394         return lastReferenced;
00395     else
00396     {
00397         DummySequence seq( h );
00398         iterator i = sequenceSet.find( &seq );
00399         return i == end() ? 0 : ( lastReferenced = *i );
00400     }
00401 }
00402 
00403 inline ErrorCode TypeSequenceManager::find( EntityHandle h, const EntitySequence*& seq ) const
00404 {
00405     if( !lastReferenced )
00406     {  // only null if empty
00407         seq = 0;
00408         return MB_ENTITY_NOT_FOUND;
00409     }
00410 
00411     seq = lastReferenced;
00412     if( h >= seq->start_handle() && h <= seq->end_handle() )
00413     {
00414         return MB_SUCCESS;
00415     }
00416 
00417     DummySequence ds( h );
00418     iterator i = sequenceSet.lower_bound( &ds );
00419     if( i == end() || ( *i )->start_handle() > h )
00420     {
00421         seq = 0;
00422         return MB_ENTITY_NOT_FOUND;
00423     }
00424     seq            = *i;
00425     lastReferenced = *i;
00426     return MB_SUCCESS;
00427 }
00428 
00429 inline ErrorCode TypeSequenceManager::find( EntityHandle h, EntitySequence*& seq )
00430 {
00431     if( !lastReferenced )
00432     {  // only null if empty
00433         seq = 0;
00434         return MB_ENTITY_NOT_FOUND;
00435     }
00436 
00437     seq = lastReferenced;
00438     if( h >= seq->start_handle() && h <= seq->end_handle() )
00439     {
00440         return MB_SUCCESS;
00441     }
00442 
00443     DummySequence ds( h );
00444     iterator i = sequenceSet.lower_bound( &ds );
00445     if( i == end() || ( *i )->start_handle() > h )
00446     {
00447         seq = 0;
00448         return MB_ENTITY_NOT_FOUND;
00449     }
00450     seq            = *i;
00451     lastReferenced = *i;
00452     return MB_SUCCESS;
00453 }
00454 
00455 inline const EntitySequence* TypeSequenceManager::get_last_accessed() const
00456 {
00457     return lastReferenced; /* only NULL if TypeSequenceManager is empty */
00458 }
00459 
00460 inline void TypeSequenceManager::get_entities( Range& entities_out ) const
00461 {
00462     Range::iterator in = entities_out.begin();
00463     for( const_iterator i = begin(); i != end(); ++i )
00464         in = entities_out.insert( in, ( *i )->start_handle(), ( *i )->end_handle() );
00465 }
00466 
00467 inline void TypeSequenceManager::get_entities( std::vector< EntityHandle >& entities_out ) const
00468 {
00469     for( const_iterator i = begin(); i != end(); ++i )
00470         for( EntityHandle j = ( *i )->start_handle(); j <= ( *i )->end_handle(); ++j )
00471             entities_out.push_back( j );
00472 }
00473 
00474 inline EntityID TypeSequenceManager::get_number_entities() const
00475 {
00476     EntityID count = 0;
00477     for( const_iterator i = begin(); i != end(); ++i )
00478         count += ( *i )->size();
00479     return count;
00480 }
00481 
00482 }  // namespace moab
00483 
00484 #endif
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines