Mesh Oriented datABase  (version 5.4.1)
Array-based unstructured mesh datastructure
TypeSequenceManager.cpp
Go to the documentation of this file.
00001 #include "TypeSequenceManager.hpp"
00002 #include "SequenceData.hpp"
00003 #include "moab/Error.hpp"
00004 #include <cassert>
00005 #include <limits>
00006 
00007 namespace moab
00008 {
00009 
00010 TypeSequenceManager::~TypeSequenceManager()
00011 {
00012     // We assume that for there to be multiple sequences referencing
00013     // the same SequenceData, there must be some portion of the
00014     // SequenceData that is unused. Otherwise the sequences should
00015     // have been merged. Given that assumption, it is the case that
00016     // either a) a SequenceData is in availableList or b) the
00017     // SequenceData is referenced by exactly one sequence.
00018 
00019     // Delete every entity sequence
00020     for( iterator i = begin(); i != end(); ++i )
00021     {
00022         EntitySequence* seq = *i;
00023         // Check for case b) above
00024         if( seq->using_entire_data() )
00025         {
00026             // Delete sequence before data, because sequence
00027             // has a pointer to data and may try to dereference
00028             // that pointer during its destruction.
00029             SequenceData* data = seq->data();
00030             delete seq;
00031             delete data;
00032         }
00033         else
00034         {
00035             delete seq;
00036         }
00037     }
00038     sequenceSet.clear();
00039 
00040     // Case a) above
00041     for( data_iterator i = availableList.begin(); i != availableList.end(); ++i )
00042         delete *i;
00043     availableList.clear();
00044 }
00045 
00046 ErrorCode TypeSequenceManager::merge_internal( iterator i, iterator j )
00047 {
00048     EntitySequence* dead = *j;
00049     sequenceSet.erase( j );
00050     ErrorCode rval = ( *i )->merge( *dead );
00051     if( MB_SUCCESS != rval )
00052     {
00053         sequenceSet.insert( dead );
00054         return rval;
00055     }
00056 
00057     if( lastReferenced == dead ) lastReferenced = *i;
00058     delete dead;
00059 
00060     // If merging results in no unused portions of the SequenceData,
00061     // remove it from the available list.
00062     if( ( *i )->using_entire_data() ) availableList.erase( ( *i )->data() );
00063 
00064     return MB_SUCCESS;
00065 }
00066 
00067 ErrorCode TypeSequenceManager::check_merge_next( iterator i )
00068 {
00069     iterator j = i;
00070     ++j;
00071     if( j == end() || ( *j )->data() != ( *i )->data() || ( *j )->start_handle() > ( *i )->end_handle() + 1 )
00072         return MB_SUCCESS;
00073 
00074     assert( ( *i )->end_handle() + 1 == ( *j )->start_handle() );
00075     return merge_internal( i, j );
00076 }
00077 
00078 ErrorCode TypeSequenceManager::check_merge_prev( iterator i )
00079 {
00080     if( i == begin() ) return MB_SUCCESS;
00081 
00082     iterator j = i;
00083     --j;
00084     if( ( *j )->data() != ( *i )->data() || ( *j )->end_handle() + 1 < ( *i )->start_handle() ) return MB_SUCCESS;
00085 
00086     assert( ( *j )->end_handle() + 1 == ( *i )->start_handle() );
00087     return merge_internal( i, j );
00088 }
00089 
00090 ErrorCode TypeSequenceManager::insert_sequence( EntitySequence* seq_ptr )
00091 {
00092     if( !seq_ptr->data() ) return MB_FAILURE;
00093 
00094     if( seq_ptr->data()->start_handle() > seq_ptr->start_handle() ||
00095         seq_ptr->data()->end_handle() < seq_ptr->end_handle() || seq_ptr->end_handle() < seq_ptr->start_handle() )
00096         return MB_FAILURE;
00097 
00098     iterator i = lower_bound( seq_ptr->start_handle() );
00099     if( i != end() )
00100     {
00101         if( ( *i )->start_handle() <= seq_ptr->end_handle() ) return MB_ALREADY_ALLOCATED;
00102         if( seq_ptr->data() != ( *i )->data() && ( *i )->data()->start_handle() <= seq_ptr->data()->end_handle() )
00103             return MB_ALREADY_ALLOCATED;
00104     }
00105 
00106     if( i != begin() )
00107     {
00108         iterator j = i;
00109         --j;
00110         if( seq_ptr->data() != ( *j )->data() && ( *j )->data()->end_handle() >= seq_ptr->data()->start_handle() )
00111             return MB_ALREADY_ALLOCATED;
00112     }
00113 
00114     i = sequenceSet.insert( i, seq_ptr );
00115 
00116     // Merge with previous sequence ?
00117     if( seq_ptr->start_handle() > seq_ptr->data()->start_handle() && i != begin() )
00118     {
00119         if( MB_SUCCESS != check_merge_prev( i ) )
00120         {
00121             sequenceSet.erase( i );
00122             return MB_FAILURE;
00123         }
00124     }
00125 
00126     // Merge with next sequence ?
00127     if( ( *i )->end_handle() < ( *i )->data()->end_handle() )
00128     {
00129         if( MB_SUCCESS != check_merge_next( i ) )
00130         {
00131             sequenceSet.erase( i );
00132             return MB_FAILURE;
00133         }
00134     }
00135 
00136     // We merged adjacent sequences sharing a SequenceData, so
00137     // we can safely assume that unless this EntitySequence is
00138     // using the entire SequenceData, there are unused portions.
00139     if( !seq_ptr->using_entire_data() ) availableList.insert( seq_ptr->data() );
00140 
00141     // lastReferenced is only allowed to be NULL if there are
00142     // no sequences (avoids unnecessary if's in fast path).
00143     if( !lastReferenced ) lastReferenced = seq_ptr;
00144 
00145     // Each SequenceData has a pointer to the first EntitySequence
00146     // referencing it. Update that pointer if the new sequence is
00147     // the first one.
00148     if( ( *i )->start_handle() == ( *i )->data()->start_handle() || lower_bound( ( *i )->data()->start_handle() ) == i )
00149         ( *i )->data()->seqManData.firstSequence = i;
00150 
00151     assert( check_valid_data( seq_ptr ) );
00152     return MB_SUCCESS;
00153 }
00154 
00155 ErrorCode TypeSequenceManager::replace_subsequence( EntitySequence* seq_ptr, const int* tag_sizes, int num_tag_sizes )
00156 {
00157     // Find the sequence of interest
00158     iterator i = lower_bound( seq_ptr->start_handle() );
00159     if( i == end() || ( *i )->data() == seq_ptr->data() ) return MB_FAILURE;
00160     // New sequence must be a subset of an existing one
00161     if( seq_ptr->start_handle() < ( *i )->start_handle() || seq_ptr->end_handle() > ( *i )->end_handle() )
00162         return MB_FAILURE;
00163     // New sequence's data must be new also, and cannot intersect
00164     // any existing sequence (just require that the data range
00165     // matches the sequence range for now)
00166     if( !seq_ptr->using_entire_data() ) return MB_FAILURE;
00167     // Copy tag data (move ownership of var-len data)
00168     SequenceData* const dead_data = ( *i )->data();
00169     dead_data->move_tag_data( seq_ptr->data(), tag_sizes, num_tag_sizes );
00170 
00171     // Split sequences sharing old data into two groups:
00172     // p->i : first sequence to i
00173     // i->n : i to one past last sequence
00174     iterator p, n = i;
00175     p = ( *i )->data()->seqManData.firstSequence;
00176     for( ++n; n != end() && ( *n )->data() == ( *i )->data(); ++n )
00177         ;
00178 
00179     // First subdivide EntitySequence as necessary
00180     // Move i to be the first sequence past the insertion point
00181     // such that the new order will be:
00182     // [p,i-1] seq_ptr [i,n]
00183     // where p == i if no previous sequence
00184 
00185     // Four possible cases:
00186     // 0. All entities in sequence are in new sequence
00187     // 1. Old entities in sequence before and after new sequence,
00188     //    requiring sequence to be split.
00189     // 2. Old entities after new sequence
00190     // 3. Old entities before new sequence
00191     const bool some_before = ( ( *i )->start_handle() < seq_ptr->start_handle() );
00192     const bool some_after  = ( ( *i )->end_handle() > seq_ptr->end_handle() );
00193     // Case 0
00194     if( !( some_before || some_after ) )
00195     {
00196         // Remove dead sequence from internal lists
00197         EntitySequence* seq = *i;
00198         iterator dead       = i;
00199         ++i;
00200         if( p == dead ) p = i;
00201         sequenceSet.erase( dead );
00202 
00203         // Delete old sequence
00204         delete seq;
00205         // Make sure lastReferenced isn't stale
00206         if( lastReferenced == seq ) lastReferenced = seq_ptr;
00207     }
00208     // Case 1
00209     else if( some_before && some_after )
00210     {
00211         i = split_sequence( i, seq_ptr->start_handle() );
00212         ( *i )->pop_front( seq_ptr->size() );
00213     }
00214     // Case 2
00215     else if( some_after )
00216     {
00217         ( *i )->pop_front( seq_ptr->size() );
00218     }
00219     // Case 3
00220     else
00221     {  // some_before
00222         ( *i )->pop_back( seq_ptr->size() );
00223         ++i;
00224     }
00225 
00226     // Now subdivide the underlying sequence data as necessary
00227     availableList.erase( dead_data );
00228     if( p != i )
00229     {
00230         iterator last = i;
00231         --last;
00232         SequenceData* new_data = ( *p )->create_data_subset( ( *p )->start_handle(), ( *last )->end_handle() );
00233         new_data->seqManData.firstSequence = p;
00234 
00235         for( ; p != i; ++p )
00236             ( *p )->data( new_data );
00237         // Copy tag data (move ownership of var-len data)
00238         dead_data->move_tag_data( new_data, tag_sizes, num_tag_sizes );
00239         if( !( *new_data->seqManData.firstSequence )->using_entire_data() ) availableList.insert( new_data );
00240     }
00241     if( i != n )
00242     {
00243         iterator last = n;
00244         --last;
00245         SequenceData* new_data = ( *i )->create_data_subset( ( *i )->start_handle(), ( *last )->end_handle() );
00246         new_data->seqManData.firstSequence = i;
00247         for( ; i != n; ++i )
00248             ( *i )->data( new_data );
00249         // Copy tag data (move ownership of var-len data)
00250         dead_data->move_tag_data( new_data, tag_sizes, num_tag_sizes );
00251         if( !( *new_data->seqManData.firstSequence )->using_entire_data() ) availableList.insert( new_data );
00252     }
00253     delete dead_data;
00254 
00255     // Put new sequence in lists
00256     return insert_sequence( seq_ptr );
00257 }
00258 
00259 TypeSequenceManager::iterator TypeSequenceManager::erase( iterator i )
00260 {
00261     EntitySequence* seq = *i;
00262     SequenceData* data  = seq->data();
00263     iterator j;
00264 
00265     // Check if we need to delete the referenced SequenceData also
00266     bool delete_data;
00267     if( seq->using_entire_data() )  // Only sequence
00268         delete_data = true;
00269     else if( data->seqManData.firstSequence != i )
00270     {  // Earlier sequence?
00271         delete_data = false;
00272         availableList.insert( data );
00273     }
00274     else
00275     {  // Later sequence ?
00276         j = i;
00277         ++j;
00278         delete_data = ( j == end() || ( *j )->data() != data );
00279         if( delete_data )
00280             availableList.erase( data );
00281         else
00282         {
00283             availableList.insert( data );
00284             data->seqManData.firstSequence = j;
00285         }
00286     }
00287 
00288     // Remove sequence, updating i to be next sequence
00289     j = i++;
00290     sequenceSet.erase( j );
00291 
00292     // Make sure lastReferenced isn't stale. It can only be NULL if
00293     // no sequences.
00294     if( lastReferenced == seq ) lastReferenced = sequenceSet.empty() ? 0 : *sequenceSet.begin();
00295 
00296     // Always delete sequence before the SequenceData it references.
00297     assert( 0 == find( seq->start_handle() ) );
00298     delete seq;
00299     if( delete_data )
00300         delete data;
00301     else
00302     {
00303         assert( check_valid_data( *data->seqManData.firstSequence ) );
00304         assert( lastReferenced != seq );
00305     }
00306     return i;
00307 }
00308 
00309 ErrorCode TypeSequenceManager::remove_sequence( const EntitySequence* seq_ptr, bool& unreferenced_data )
00310 {
00311     // Remove sequence from set
00312     iterator i = lower_bound( seq_ptr->start_handle() );
00313     if( i == end() || *i != seq_ptr ) return MB_ENTITY_NOT_FOUND;
00314     sequenceSet.erase( i );
00315 
00316     // Check if this is the only sequence referencing its data
00317     if( seq_ptr->using_entire_data() )
00318         unreferenced_data = true;
00319     else
00320     {
00321         i                 = lower_bound( seq_ptr->data()->start_handle() );
00322         unreferenced_data = i == end() || ( *i )->data() != seq_ptr->data();
00323         if( unreferenced_data )
00324             availableList.erase( seq_ptr->data() );
00325         else
00326             seq_ptr->data()->seqManData.firstSequence = i;  // Might be 'i' already
00327     }
00328 
00329     if( lastReferenced == seq_ptr ) lastReferenced = sequenceSet.empty() ? 0 : *sequenceSet.begin();
00330 
00331     return MB_SUCCESS;
00332 }
00333 
00334 TypeSequenceManager::iterator TypeSequenceManager::find_free_handle( EntityHandle min_start_handle,
00335                                                                      EntityHandle max_end_handle,
00336                                                                      bool& append_out,
00337                                                                      int values_per_ent )
00338 {
00339     for( data_iterator i = availableList.begin(); i != availableList.end(); ++i )
00340     {
00341         if( ( *( *i )->seqManData.firstSequence )->values_per_entity() != values_per_ent ) continue;
00342 
00343         if( ( *i )->start_handle() > max_end_handle || ( *i )->end_handle() < min_start_handle ) continue;
00344 
00345         for( iterator j = ( *i )->seqManData.firstSequence;
00346              j != end() && ( *j )->start_handle() <= ( max_end_handle + 1 ) && ( *j )->data() == *i; ++j )
00347         {
00348             if( ( *j )->end_handle() + 1 < min_start_handle ) continue;
00349             if( ( *j )->start_handle() > ( *i )->start_handle() && ( *j )->start_handle() > min_start_handle )
00350             {
00351                 append_out = false;
00352                 return j;
00353             }
00354             if( ( *j )->end_handle() < ( *i )->end_handle() && ( *j )->end_handle() < max_end_handle )
00355             {
00356                 append_out = true;
00357                 return j;
00358             }
00359         }
00360     }
00361 
00362     return end();
00363 }
00364 
00365 bool TypeSequenceManager::is_free_sequence( EntityHandle start,
00366                                             EntityID num_entities,
00367                                             SequenceData*& data_out,
00368                                             int values_per_ent )
00369 {
00370     data_out = 0;
00371     if( empty() ) return true;
00372 
00373     const_iterator i = lower_bound( start );
00374     if( i == end() )
00375     {
00376         --i;  // Safe because already tested empty()
00377         // If we don't overlap the last data object...
00378         if( ( *i )->data()->end_handle() < start ) return true;
00379         data_out = ( *i )->data();
00380         if( ( *i )->values_per_entity() != values_per_ent ) return false;
00381         // If we overlap a data object, we must be entirely inside of it
00382         return start + num_entities - 1 <= ( *i )->data()->end_handle();
00383     }
00384 
00385 #ifndef NDEBUG
00386     if( i != begin() )
00387     {
00388         const_iterator j = i;
00389         --j;
00390         assert( ( *j )->end_handle() < start );
00391     }
00392 #endif
00393 
00394     // Check if we fit in the block of free handles
00395     if( start + num_entities > ( *i )->start_handle() )  // start + num + 1 >= i->start
00396         return false;
00397 
00398     // Check if we overlap the data for the next sequence
00399     if( start + num_entities > ( *i )->data()->start_handle() )
00400     {
00401         data_out = ( *i )->data();
00402         if( ( *i )->values_per_entity() != values_per_ent ) return false;
00403         // If overlap, must be entirely contained
00404         return start >= data_out->start_handle() && start + num_entities - 1 <= data_out->end_handle();
00405     }
00406 
00407     // Check if we overlap the data for the previous sequence
00408     if( i != begin() )
00409     {
00410         --i;
00411         if( ( *i )->data()->end_handle() >= start )
00412         {
00413             data_out = ( *i )->data();
00414             if( ( *i )->values_per_entity() != values_per_ent ) return false;
00415             return start + num_entities - 1 <= ( *i )->data()->end_handle();
00416         }
00417     }
00418 
00419     // Unused handle block that overlaps no SequenceData
00420     return true;
00421 }
00422 
00423 EntityHandle TypeSequenceManager::find_free_block( EntityID num_entities,
00424                                                    EntityHandle min_start_handle,
00425                                                    EntityHandle max_end_handle )
00426 {
00427     const_iterator i = lower_bound( min_start_handle );
00428     if( i == end() ) return min_start_handle;
00429 
00430     if( ( *i )->start_handle() < min_start_handle + num_entities ) return min_start_handle;
00431 
00432     EntityHandle prev_end = ( *i )->end_handle();
00433     ++i;
00434     for( ; i != end(); prev_end = ( *i )->end_handle(), ++i )
00435     {
00436         EntityID len = ( *i )->start_handle() - prev_end - 1;
00437         if( len >= num_entities ) break;
00438     }
00439 
00440     if( prev_end + num_entities > max_end_handle )
00441         return 0;
00442     else
00443         return prev_end + 1;
00444 }
00445 
00446 struct range_data
00447 {
00448     EntityID num_entities;
00449     EntityHandle min_start_handle, max_end_handle;
00450     EntityHandle first, last;
00451 };
00452 
00453 static bool check_range( const range_data& d, bool prefer_end, EntityHandle& result )
00454 {
00455     EntityHandle first = std::max( d.min_start_handle, d.first );
00456     EntityHandle last  = std::min( d.max_end_handle, d.last );
00457     if( last < first + d.num_entities - 1 )
00458     {
00459         result = 0;
00460         return false;
00461     }
00462 
00463     result = prefer_end ? last + 1 - d.num_entities : first;
00464     return true;
00465 }
00466 
00467 EntityHandle TypeSequenceManager::find_free_sequence( EntityID num_entities,
00468                                                       EntityHandle min_start_handle,
00469                                                       EntityHandle max_end_handle,
00470                                                       SequenceData*& data_out,
00471                                                       EntityID& data_size,
00472                                                       int num_verts )
00473 {
00474     if( max_end_handle < min_start_handle + num_entities - 1 ) return 0;
00475 
00476     EntityHandle result;
00477     iterator p, i = lower_bound( min_start_handle );
00478     range_data d = { num_entities, min_start_handle, max_end_handle, 0, 0 };
00479 
00480     if( i == end() )
00481     {
00482         data_out = 0;
00483         return min_start_handle;
00484     }
00485     else if( i == begin() )
00486     {
00487         if( ( *i )->values_per_entity() == num_verts )
00488         {
00489             d.first = ( *i )->data()->start_handle();
00490             d.last  = ( *i )->start_handle() - 1;
00491             if( check_range( d, true, result ) )
00492             {
00493                 data_out = ( *i )->data();
00494                 return result;
00495             }
00496         }
00497         d.first = min_start_handle;
00498         d.last  = ( *i )->data()->start_handle() - 1;
00499         if( check_range( d, true, result ) )
00500         {
00501             data_out = 0;
00502             // This will back up against the end of the seq data, so
00503             // size the data that way
00504             data_size = num_entities;
00505             return result;
00506         }
00507         p = i++;
00508     }
00509     else
00510     {
00511         p = i;
00512         --p;
00513     }
00514 
00515     for( ; i != end() && ( *i )->start_handle() < max_end_handle; p = i++ )
00516     {
00517         if( ( *p )->data() == ( *i )->data() )
00518         {
00519             if( ( *p )->values_per_entity() == num_verts )
00520             {
00521                 d.first = ( *p )->end_handle() + 1;
00522                 d.last  = ( *i )->start_handle() - 1;
00523                 if( check_range( d, false, result ) )
00524                 {
00525                     data_out = ( *p )->data();
00526                     return result;
00527                 }
00528             }
00529         }
00530         else
00531         {
00532             if( ( *p )->values_per_entity() == num_verts )
00533             {
00534                 d.first = ( *p )->end_handle() + 1;
00535                 d.last  = ( *p )->data()->end_handle();
00536                 if( check_range( d, false, result ) )
00537                 {
00538                     data_out = ( *p )->data();
00539                     return result;
00540                 }
00541             }
00542             if( ( *i )->values_per_entity() == num_verts )
00543             {
00544                 d.first = ( *i )->data()->start_handle();
00545                 d.last  = ( *i )->start_handle() - 1;
00546                 if( check_range( d, true, result ) )
00547                 {
00548                     data_out = ( *i )->data();
00549                     return result;
00550                 }
00551             }
00552             d.first = ( *p )->data()->end_handle() + 1;
00553             d.last  = ( *i )->data()->start_handle() - 1;
00554             if( check_range( d, false, result ) )
00555             {
00556                 data_out  = 0;
00557                 data_size = d.last - d.first + 1;
00558                 return result;
00559             }
00560         }
00561     }
00562 
00563     if( ( *p )->values_per_entity() == num_verts )
00564     {
00565         d.first = ( *p )->end_handle() + 1;
00566         d.last  = ( *p )->data()->end_handle();
00567         if( check_range( d, false, result ) )
00568         {
00569             data_out = ( *p )->data();
00570             return result;
00571         }
00572     }
00573 
00574     d.first = ( *p )->data()->end_handle() + 1;
00575     d.last  = max_end_handle;
00576     if( check_range( d, false, result ) )
00577     {
00578         data_out = 0;
00579         return result;
00580     }
00581 
00582     data_out = 0;
00583     return 0;
00584 }
00585 
00586 EntityHandle TypeSequenceManager::last_free_handle( EntityHandle after_this ) const
00587 {
00588     int junk;
00589     const_iterator it = lower_bound( after_this );
00590     if( it == end() )
00591         return CREATE_HANDLE( TYPE_FROM_HANDLE( after_this ), MB_END_ID, junk );
00592     else if( ( *it )->start_handle() > after_this )
00593     {
00594         // Need to check against the sequence data first
00595         EntityHandle rhandle = ( *it )->data()->start_handle();
00596         return rhandle - 1;
00597     }
00598     else
00599         return 0;
00600 }
00601 
00602 ErrorCode TypeSequenceManager::check_valid_handles( Error* /* error_handler */,
00603                                                     EntityHandle first,
00604                                                     EntityHandle last ) const
00605 {
00606     const_iterator i = lower_bound( first );
00607     if( i == end() || ( *i )->start_handle() > first )
00608     {
00609 #if 0
00610     // MB_ENTITY_NOT_FOUND could be a non-error condition, do not call
00611     // MB_SET_ERR on it
00612     fprintf(
00613       stderr,
00614       "[Warning]: Invalid entity handle: 0x%lx\n", (unsigned long)first
00615       );
00616 #endif
00617         return MB_ENTITY_NOT_FOUND;
00618     }
00619 
00620     while( ( *i )->end_handle() < last )
00621     {
00622         EntityHandle prev_end = ( *i )->end_handle();
00623         ++i;
00624         if( i == end() || prev_end + 1 != ( *i )->start_handle() ) return MB_ENTITY_NOT_FOUND;
00625     }
00626 
00627     return MB_SUCCESS;
00628 }
00629 
00630 ErrorCode TypeSequenceManager::erase( Error* /* error_handler */, EntityHandle h )
00631 {
00632     EntitySequence* seq = find( h );
00633     if( !seq )
00634     {
00635 #if 0
00636     // MB_ENTITY_NOT_FOUND could be a non-error condition, do not call
00637     // MB_SET_ERR on it
00638     fprintf(
00639       stderr,
00640       "[Warning]: Invalid entity handle: 0x%lx\n", (unsigned long)h
00641       );
00642 #endif
00643         return MB_ENTITY_NOT_FOUND;
00644     }
00645 
00646     if( seq->start_handle() == h )
00647     {
00648         if( seq->end_handle() != h )
00649         {
00650             if( seq->using_entire_data() ) availableList.insert( seq->data() );
00651             seq->pop_front( 1 );
00652             return MB_SUCCESS;
00653         }
00654         SequenceData* data = seq->data();
00655         bool delete_data;
00656         ErrorCode rval = remove_sequence( seq, delete_data );
00657         if( MB_SUCCESS != rval ) return rval;
00658         delete seq;
00659         if( delete_data ) delete data;
00660     }
00661     else if( seq->end_handle() == h )
00662     {
00663         if( seq->using_entire_data() ) availableList.insert( seq->data() );
00664         seq->pop_back( 1 );
00665     }
00666     else
00667     {
00668         iterator i = lower_bound( h );
00669         if( ( *i )->using_entire_data() ) availableList.insert( ( *i )->data() );
00670         i   = split_sequence( i, h );
00671         seq = *i;
00672         assert( seq->start_handle() == h );
00673         seq->pop_front( 1 );
00674     }
00675 
00676     return MB_SUCCESS;
00677 }
00678 
00679 ErrorCode TypeSequenceManager::erase( Error* /* error */, EntityHandle first, EntityHandle last )
00680 {
00681     // First check that all entities in range are valid
00682 
00683     ErrorCode rval = check_valid_handles( NULL, first, last );
00684     if( MB_SUCCESS != rval ) return rval;
00685 
00686     // Now remove entities
00687 
00688     // Get first sequence intersecting range
00689     iterator i = lower_bound( first );
00690     if( i == end() )  // Shouldn't be possible given check_valid_handles call above.
00691         return MB_ENTITY_NOT_FOUND;
00692 
00693     // If range is entirely in interior of sequence, need to split sequence.
00694     if( ( *i )->start_handle() < first && ( *i )->end_handle() > last )
00695     {
00696         if( ( *i )->using_entire_data() ) availableList.insert( ( *i )->data() );
00697         i = split_sequence( i, first );
00698         ( *i )->pop_front( last - first + 1 );
00699         assert( check_valid_data( *i ) );
00700         return MB_SUCCESS;
00701     }
00702 
00703     // If range doesn't entirely contain first sequence, remove some
00704     // handles from the end of the sequence and advance to the next
00705     // sequence.
00706     if( ( *i )->start_handle() < first )
00707     {
00708         if( ( *i )->using_entire_data() ) availableList.insert( ( *i )->data() );
00709         ( *i )->pop_back( ( *i )->end_handle() - first + 1 );
00710         ++i;
00711     }
00712 
00713     // Destroy all sequences contained entirely within the range
00714     while( i != end() && ( *i )->end_handle() <= last )
00715         i = erase( i );
00716 
00717     // If necessary, remove entities from the beginning of the
00718     // last sequence.
00719     if( i != end() && ( *i )->start_handle() <= last )
00720     {
00721         if( ( *i )->using_entire_data() ) availableList.insert( ( *i )->data() );
00722         ( *i )->pop_front( last - ( *i )->start_handle() + 1 );
00723         assert( check_valid_data( *i ) );
00724     }
00725 
00726     return MB_SUCCESS;
00727 }
00728 
00729 TypeSequenceManager::iterator TypeSequenceManager::split_sequence( iterator i, EntityHandle h )
00730 {
00731     EntitySequence* seq = ( *i )->split( h );
00732     if( !seq ) return end();
00733 
00734     i = sequenceSet.insert( i, seq );
00735     assert( check_valid_data( *i ) );
00736 
00737     return i;
00738 }
00739 
00740 ErrorCode TypeSequenceManager::is_free_handle( EntityHandle handle,
00741                                                iterator& seq_iter_out,
00742                                                SequenceData*& data_ptr_out,
00743                                                EntityHandle& block_start,
00744                                                EntityHandle& block_end,
00745                                                int values_per_ent )
00746 {
00747     int junk;
00748     block_start = CREATE_HANDLE( TYPE_FROM_HANDLE( handle ), MB_START_ID, junk );
00749     block_end   = CREATE_HANDLE( TYPE_FROM_HANDLE( handle ), MB_END_ID, junk );
00750 
00751     iterator i = lower_bound( handle );
00752     if( i != end() )
00753     {
00754         block_end = ( *i )->start_handle() - 1;
00755 
00756         // If sequence contains handle, then already allocated
00757         if( ( *i )->start_handle() <= handle ) return MB_ALREADY_ALLOCATED;
00758 
00759         // Handle is not within an existing sequence, but is
00760         // within an existing SequenceData...
00761         if( ( *i )->data()->start_handle() <= handle )
00762         {
00763             // If values_per_entity don't match, can't put new entity
00764             // in existing SequenceData
00765             if( ( *i )->values_per_entity() != values_per_ent ) return MB_ALREADY_ALLOCATED;
00766 
00767             data_ptr_out = ( *i )->data();
00768             if( block_end == handle )
00769             {
00770                 // Prepend to existing sequence
00771                 seq_iter_out = i;
00772                 block_start  = handle;
00773             }
00774             else
00775             {
00776                 // Add new sequence to existing SequenceData
00777                 seq_iter_out = end();
00778                 if( i == begin() || ( *--i )->data() != data_ptr_out )
00779                     block_start = data_ptr_out->start_handle();
00780                 else
00781                     block_start = ( *i )->end_handle() + 1;
00782             }
00783             return MB_SUCCESS;
00784         }
00785     }
00786 
00787     if( i != begin() )
00788     {
00789         --i;
00790         block_start = ( *i )->end_handle() + 1;
00791 
00792         // Handle is within previous sequence data...
00793         if( ( *i )->data()->end_handle() >= handle )
00794         {
00795             // If values_per_entity don't match, can't put new entity
00796             // in existing SequenceData
00797             if( ( *i )->values_per_entity() != values_per_ent ) return MB_ALREADY_ALLOCATED;
00798 
00799             data_ptr_out = ( *i )->data();
00800             if( block_start == handle )
00801             {
00802                 // Append to existing sequence
00803                 seq_iter_out = i;
00804                 block_end    = handle;
00805             }
00806             else
00807             {
00808                 // Add new sequence to existing SequenceData
00809                 seq_iter_out = end();
00810                 if( ++i == end() || ( *i )->data() != data_ptr_out )
00811                     block_end = data_ptr_out->end_handle();
00812                 else
00813                     block_end = ( *i )->start_handle() - 1;
00814             }
00815             return MB_SUCCESS;
00816         }
00817     }
00818 
00819     seq_iter_out = end();
00820     data_ptr_out = 0;
00821 
00822     return MB_SUCCESS;
00823 }
00824 
00825 ErrorCode TypeSequenceManager::notify_appended( iterator seq )
00826 {
00827     ErrorCode rval = check_merge_next( seq );
00828     if( ( *seq )->using_entire_data() ) availableList.erase( ( *seq )->data() );
00829 
00830     return rval;
00831 }
00832 
00833 ErrorCode TypeSequenceManager::notify_prepended( iterator seq )
00834 {
00835     ErrorCode rval = check_merge_prev( seq );
00836     if( ( *seq )->using_entire_data() ) availableList.erase( ( *seq )->data() );
00837 
00838     return rval;
00839 }
00840 
00841 void TypeSequenceManager::get_memory_use( unsigned long long& entity_storage, unsigned long long& total_storage ) const
00842 {
00843     entity_storage = total_storage = 0;
00844     if( empty() ) return;
00845 
00846     EntityType mytype = TYPE_FROM_HANDLE( lastReferenced->start_handle() );
00847     int junk;
00848     get_memory_use( CREATE_HANDLE( mytype, MB_START_ID, junk ), CREATE_HANDLE( mytype, MB_END_ID, junk ),
00849                     entity_storage, total_storage );
00850 }
00851 
00852 void TypeSequenceManager::append_memory_use( EntityHandle first,
00853                                              EntityHandle last,
00854                                              const SequenceData* data,
00855                                              unsigned long long& entity_storage,
00856                                              unsigned long long& total_storage ) const
00857 {
00858     const unsigned long allocated_count = data->size();
00859 
00860     unsigned long bytes_per_ent, seq_size;
00861     const_iterator i = data->seqManData.firstSequence;
00862     ( *i )->get_const_memory_use( bytes_per_ent, seq_size );
00863 
00864     unsigned long other_ent_mem  = 0;
00865     unsigned long occupied_count = 0, entity_count = 0, sequence_count = 0;
00866     for( ; i != end() && ( *i )->data() == data; ++i )
00867     {
00868         occupied_count += ( *i )->size();
00869         ++sequence_count;
00870 
00871         EntityHandle start = std::max( first, ( *i )->start_handle() );
00872         EntityHandle stop  = std::min( last, ( *i )->end_handle() );
00873         if( stop < start ) continue;
00874 
00875         entity_count += stop - start + 1;
00876         other_ent_mem += ( *i )->get_per_entity_memory_use( start, stop );
00877     }
00878 
00879     unsigned long sum = sequence_count * seq_size + allocated_count * bytes_per_ent;
00880 
00881     // Watch for overflow
00882     assert( entity_count > 0 && occupied_count > 0 && allocated_count > 0 );
00883     if( std::numeric_limits< unsigned long >::max() / entity_count <= sum )
00884     {
00885         total_storage += sum * ( entity_count / occupied_count ) + other_ent_mem;
00886         entity_storage += sum * ( entity_count / allocated_count ) + other_ent_mem;
00887     }
00888     else
00889     {
00890         total_storage += sum * entity_count / occupied_count + other_ent_mem;
00891         entity_storage += sum * entity_count / allocated_count + other_ent_mem;
00892     }
00893 }
00894 
00895 void TypeSequenceManager::get_memory_use( EntityHandle first,
00896                                           EntityHandle last,
00897                                           unsigned long long& entity_storage,
00898                                           unsigned long long& total_storage ) const
00899 {
00900     entity_storage = total_storage = 0;
00901 
00902     while( first <= last )
00903     {
00904         const_iterator i = lower_bound( first );
00905         if( i == end() ) return;
00906 
00907         SequenceData* data = ( *i )->data();
00908         if( first < data->end_handle() )
00909         {
00910             append_memory_use( first, last, data, entity_storage, total_storage );
00911         }
00912         first = data->end_handle() + 1;
00913     }
00914 }
00915 
00916 EntityID TypeSequenceManager::get_occupied_size( const SequenceData* data ) const
00917 {
00918     EntityID result = 0;
00919     for( const_iterator i = data->seqManData.firstSequence; i != end() && ( *i )->data() == data; ++i )
00920         result += ( *i )->size();
00921 
00922     return result;
00923 }
00924 
00925 #ifndef NDEBUG
00926 bool TypeSequenceManager::check_valid_data( const EntitySequence* seq ) const
00927 {
00928     // Caller passed a sequence that should be contained, so cannot be empty
00929     if( empty() ) return false;
00930 
00931     // Make sure lastReferenced points to something
00932     if( !lastReferenced ) return false;
00933 
00934     const_iterator seqi = sequenceSet.lower_bound( lastReferenced );
00935     if( seqi == sequenceSet.end() || *seqi != lastReferenced ) return false;
00936 
00937     // Make sure passed sequence is in list
00938     const EntitySequence* seq2 = find( seq->start_handle() );
00939     if( seq2 != seq ) return false;
00940 
00941     // Check all sequences referencing the same SequenceData
00942     const SequenceData* data = seq->data();
00943     const_iterator i         = lower_bound( data->start_handle() );
00944     if( i != data->seqManData.firstSequence ) return false;
00945 
00946     if( i != begin() )
00947     {
00948         const_iterator j = i;
00949         --j;
00950         if( ( *j )->end_handle() >= data->start_handle() ) return false;
00951         if( ( *j )->data()->end_handle() >= data->start_handle() ) return false;
00952     }
00953 
00954     for( ;; )
00955     {
00956         seq2 = *i;
00957         ++i;
00958         if( i == end() ) return true;
00959         if( ( *i )->data() != data ) break;
00960 
00961         if( seq2->end_handle() >= ( *i )->start_handle() ) return false;
00962     }
00963 
00964     if( ( *i )->start_handle() <= data->end_handle() ) return false;
00965     if( ( *i )->data()->start_handle() <= data->end_handle() ) return false;
00966 
00967     return true;
00968 }
00969 
00970 #endif
00971 
00972 }  // namespace moab
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines