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