MOAB: Mesh Oriented datABase
(version 5.2.1)
|
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, EntitySequence*& seq ) 00388 { 00389 if( !lastReferenced ) 00390 { // only null if empty 00391 seq = 0; 00392 return MB_ENTITY_NOT_FOUND; 00393 } 00394 else if( h >= lastReferenced->start_handle() && h <= lastReferenced->end_handle() ) 00395 { 00396 seq = lastReferenced; 00397 return MB_SUCCESS; 00398 } 00399 else 00400 { 00401 DummySequence ds( h ); 00402 iterator i = sequenceSet.lower_bound( &ds ); 00403 if( i == end() || ( *i )->start_handle() > h ) 00404 { 00405 seq = 0; 00406 return MB_ENTITY_NOT_FOUND; 00407 } 00408 else 00409 { 00410 seq = lastReferenced = *i; 00411 return MB_SUCCESS; 00412 } 00413 } 00414 } 00415 00416 inline ErrorCode TypeSequenceManager::find( EntityHandle h, const EntitySequence*& seq ) const 00417 { 00418 if( !lastReferenced ) 00419 { // only null if empty 00420 seq = 0; 00421 return MB_ENTITY_NOT_FOUND; 00422 } 00423 else if( h >= lastReferenced->start_handle() && h <= lastReferenced->end_handle() ) 00424 { 00425 seq = lastReferenced; 00426 return MB_SUCCESS; 00427 } 00428 else 00429 { 00430 DummySequence ds( h ); 00431 const_iterator i = sequenceSet.lower_bound( &ds ); 00432 if( i == end() || ( *i )->start_handle() > h ) 00433 { 00434 seq = 0; 00435 return MB_ENTITY_NOT_FOUND; 00436 } 00437 else 00438 { 00439 seq = lastReferenced = *i; 00440 return MB_SUCCESS; 00441 } 00442 } 00443 } 00444 00445 inline const EntitySequence* TypeSequenceManager::get_last_accessed() const 00446 { 00447 return lastReferenced; /* only NULL if TypeSequenceManager is empty */ 00448 } 00449 00450 inline void TypeSequenceManager::get_entities( Range& entities_out ) const 00451 { 00452 Range::iterator in = entities_out.begin(); 00453 for( const_iterator i = begin(); i != end(); ++i ) 00454 in = entities_out.insert( in, ( *i )->start_handle(), ( *i )->end_handle() ); 00455 } 00456 00457 inline void TypeSequenceManager::get_entities( std::vector< EntityHandle >& entities_out ) const 00458 { 00459 for( const_iterator i = begin(); i != end(); ++i ) 00460 for( EntityHandle j = ( *i )->start_handle(); j <= ( *i )->end_handle(); ++j ) 00461 entities_out.push_back( j ); 00462 } 00463 00464 inline EntityID TypeSequenceManager::get_number_entities() const 00465 { 00466 EntityID count = 0; 00467 for( const_iterator i = begin(); i != end(); ++i ) 00468 count += ( *i )->size(); 00469 return count; 00470 } 00471 00472 } // namespace moab 00473 00474 #endif