MOAB: Mesh Oriented datABase  (version 5.3.1)
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, bool& append_out,
00336                                                                      int values_per_ent )
00337 {
00338     for( data_iterator i = availableList.begin(); i != availableList.end(); ++i )
00339     {
00340         if( ( *( *i )->seqManData.firstSequence )->values_per_entity() != values_per_ent ) continue;
00341 
00342         if( ( *i )->start_handle() > max_end_handle || ( *i )->end_handle() < min_start_handle ) continue;
00343 
00344         for( iterator j = ( *i )->seqManData.firstSequence;
00345              j != end() && ( *j )->start_handle() <= ( max_end_handle + 1 ) && ( *j )->data() == *i; ++j )
00346         {
00347             if( ( *j )->end_handle() + 1 < min_start_handle ) continue;
00348             if( ( *j )->start_handle() > ( *i )->start_handle() && ( *j )->start_handle() > min_start_handle )
00349             {
00350                 append_out = false;
00351                 return j;
00352             }
00353             if( ( *j )->end_handle() < ( *i )->end_handle() && ( *j )->end_handle() < max_end_handle )
00354             {
00355                 append_out = true;
00356                 return j;
00357             }
00358         }
00359     }
00360 
00361     return end();
00362 }
00363 
00364 bool TypeSequenceManager::is_free_sequence( EntityHandle start, EntityID num_entities, SequenceData*& data_out,
00365                                             int values_per_ent )
00366 {
00367     data_out = 0;
00368     if( empty() ) return true;
00369 
00370     const_iterator i = lower_bound( start );
00371     if( i == end() )
00372     {
00373         --i;  // Safe because already tested empty()
00374         // If we don't overlap the last data object...
00375         if( ( *i )->data()->end_handle() < start ) return true;
00376         data_out = ( *i )->data();
00377         if( ( *i )->values_per_entity() != values_per_ent ) return false;
00378         // If we overlap a data object, we must be entirely inside of it
00379         return start + num_entities - 1 <= ( *i )->data()->end_handle();
00380     }
00381 
00382 #ifndef NDEBUG
00383     if( i != begin() )
00384     {
00385         const_iterator j = i;
00386         --j;
00387         assert( ( *j )->end_handle() < start );
00388     }
00389 #endif
00390 
00391     // Check if we fit in the block of free handles
00392     if( start + num_entities > ( *i )->start_handle() )  // start + num + 1 >= i->start
00393         return false;
00394 
00395     // Check if we overlap the data for the next sequence
00396     if( start + num_entities > ( *i )->data()->start_handle() )
00397     {
00398         data_out = ( *i )->data();
00399         if( ( *i )->values_per_entity() != values_per_ent ) return false;
00400         // If overlap, must be entirely contained
00401         return start >= data_out->start_handle() && start + num_entities - 1 <= data_out->end_handle();
00402     }
00403 
00404     // Check if we overlap the data for the previous sequence
00405     if( i != begin() )
00406     {
00407         --i;
00408         if( ( *i )->data()->end_handle() >= start )
00409         {
00410             data_out = ( *i )->data();
00411             if( ( *i )->values_per_entity() != values_per_ent ) return false;
00412             return start + num_entities - 1 <= ( *i )->data()->end_handle();
00413         }
00414     }
00415 
00416     // Unused handle block that overlaps no SequenceData
00417     return true;
00418 }
00419 
00420 EntityHandle TypeSequenceManager::find_free_block( EntityID num_entities, EntityHandle min_start_handle,
00421                                                    EntityHandle max_end_handle )
00422 {
00423     const_iterator i = lower_bound( min_start_handle );
00424     if( i == end() ) return min_start_handle;
00425 
00426     if( ( *i )->start_handle() < min_start_handle + num_entities ) return min_start_handle;
00427 
00428     EntityHandle prev_end = ( *i )->end_handle();
00429     ++i;
00430     for( ; i != end(); prev_end = ( *i )->end_handle(), ++i )
00431     {
00432         EntityID len = ( *i )->start_handle() - prev_end - 1;
00433         if( len >= num_entities ) break;
00434     }
00435 
00436     if( prev_end + num_entities > max_end_handle )
00437         return 0;
00438     else
00439         return prev_end + 1;
00440 }
00441 
00442 struct range_data
00443 {
00444     EntityID num_entities;
00445     EntityHandle min_start_handle, max_end_handle;
00446     EntityHandle first, last;
00447 };
00448 
00449 static bool check_range( const range_data& d, bool prefer_end, EntityHandle& result )
00450 {
00451     EntityHandle first = std::max( d.min_start_handle, d.first );
00452     EntityHandle last  = std::min( d.max_end_handle, d.last );
00453     if( last < first + d.num_entities - 1 )
00454     {
00455         result = 0;
00456         return false;
00457     }
00458 
00459     result = prefer_end ? last + 1 - d.num_entities : first;
00460     return true;
00461 }
00462 
00463 EntityHandle TypeSequenceManager::find_free_sequence( EntityID num_entities, EntityHandle min_start_handle,
00464                                                       EntityHandle max_end_handle, SequenceData*& data_out,
00465                                                       EntityID& data_size, int num_verts )
00466 {
00467     if( max_end_handle < min_start_handle + num_entities - 1 ) return 0;
00468 
00469     EntityHandle result;
00470     iterator p, i = lower_bound( min_start_handle );
00471     range_data d = { num_entities, min_start_handle, max_end_handle, 0, 0 };
00472 
00473     if( i == end() )
00474     {
00475         data_out = 0;
00476         return min_start_handle;
00477     }
00478     else if( i == begin() )
00479     {
00480         if( ( *i )->values_per_entity() == num_verts )
00481         {
00482             d.first = ( *i )->data()->start_handle();
00483             d.last  = ( *i )->start_handle() - 1;
00484             if( check_range( d, true, result ) )
00485             {
00486                 data_out = ( *i )->data();
00487                 return result;
00488             }
00489         }
00490         d.first = min_start_handle;
00491         d.last  = ( *i )->data()->start_handle() - 1;
00492         if( check_range( d, true, result ) )
00493         {
00494             data_out = 0;
00495             // This will back up against the end of the seq data, so
00496             // size the data that way
00497             data_size = num_entities;
00498             return result;
00499         }
00500         p = i++;
00501     }
00502     else
00503     {
00504         p = i;
00505         --p;
00506     }
00507 
00508     for( ; i != end() && ( *i )->start_handle() < max_end_handle; p = i++ )
00509     {
00510         if( ( *p )->data() == ( *i )->data() )
00511         {
00512             if( ( *p )->values_per_entity() == num_verts )
00513             {
00514                 d.first = ( *p )->end_handle() + 1;
00515                 d.last  = ( *i )->start_handle() - 1;
00516                 if( check_range( d, false, result ) )
00517                 {
00518                     data_out = ( *p )->data();
00519                     return result;
00520                 }
00521             }
00522         }
00523         else
00524         {
00525             if( ( *p )->values_per_entity() == num_verts )
00526             {
00527                 d.first = ( *p )->end_handle() + 1;
00528                 d.last  = ( *p )->data()->end_handle();
00529                 if( check_range( d, false, result ) )
00530                 {
00531                     data_out = ( *p )->data();
00532                     return result;
00533                 }
00534             }
00535             if( ( *i )->values_per_entity() == num_verts )
00536             {
00537                 d.first = ( *i )->data()->start_handle();
00538                 d.last  = ( *i )->start_handle() - 1;
00539                 if( check_range( d, true, result ) )
00540                 {
00541                     data_out = ( *i )->data();
00542                     return result;
00543                 }
00544             }
00545             d.first = ( *p )->data()->end_handle() + 1;
00546             d.last  = ( *i )->data()->start_handle() - 1;
00547             if( check_range( d, false, result ) )
00548             {
00549                 data_out  = 0;
00550                 data_size = d.last - d.first + 1;
00551                 return result;
00552             }
00553         }
00554     }
00555 
00556     if( ( *p )->values_per_entity() == num_verts )
00557     {
00558         d.first = ( *p )->end_handle() + 1;
00559         d.last  = ( *p )->data()->end_handle();
00560         if( check_range( d, false, result ) )
00561         {
00562             data_out = ( *p )->data();
00563             return result;
00564         }
00565     }
00566 
00567     d.first = ( *p )->data()->end_handle() + 1;
00568     d.last  = max_end_handle;
00569     if( check_range( d, false, result ) )
00570     {
00571         data_out = 0;
00572         return result;
00573     }
00574 
00575     data_out = 0;
00576     return 0;
00577 }
00578 
00579 EntityHandle TypeSequenceManager::last_free_handle( EntityHandle after_this ) const
00580 {
00581     int junk;
00582     const_iterator it = lower_bound( after_this );
00583     if( it == end() )
00584         return CREATE_HANDLE( TYPE_FROM_HANDLE( after_this ), MB_END_ID, junk );
00585     else if( ( *it )->start_handle() > after_this )
00586     {
00587         // Need to check against the sequence data first
00588         EntityHandle rhandle = ( *it )->data()->start_handle();
00589         return rhandle - 1;
00590     }
00591     else
00592         return 0;
00593 }
00594 
00595 ErrorCode TypeSequenceManager::check_valid_handles( Error* /* error_handler */, EntityHandle first,
00596                                                     EntityHandle last ) const
00597 {
00598     const_iterator i = lower_bound( first );
00599     if( i == end() || ( *i )->start_handle() > first )
00600     {
00601 #if 0
00602     // MB_ENTITY_NOT_FOUND could be a non-error condition, do not call
00603     // MB_SET_ERR on it
00604     fprintf(
00605       stderr,
00606       "[Warning]: Invalid entity handle: 0x%lx\n", (unsigned long)first
00607       );
00608 #endif
00609         return MB_ENTITY_NOT_FOUND;
00610     }
00611 
00612     while( ( *i )->end_handle() < last )
00613     {
00614         EntityHandle prev_end = ( *i )->end_handle();
00615         ++i;
00616         if( i == end() || prev_end + 1 != ( *i )->start_handle() ) return MB_ENTITY_NOT_FOUND;
00617     }
00618 
00619     return MB_SUCCESS;
00620 }
00621 
00622 ErrorCode TypeSequenceManager::erase( Error* /* error_handler */, EntityHandle h )
00623 {
00624     EntitySequence* seq = find( h );
00625     if( !seq )
00626     {
00627 #if 0
00628     // MB_ENTITY_NOT_FOUND could be a non-error condition, do not call
00629     // MB_SET_ERR on it
00630     fprintf(
00631       stderr,
00632       "[Warning]: Invalid entity handle: 0x%lx\n", (unsigned long)h
00633       );
00634 #endif
00635         return MB_ENTITY_NOT_FOUND;
00636     }
00637 
00638     if( seq->start_handle() == h )
00639     {
00640         if( seq->end_handle() != h )
00641         {
00642             if( seq->using_entire_data() ) availableList.insert( seq->data() );
00643             seq->pop_front( 1 );
00644             return MB_SUCCESS;
00645         }
00646         SequenceData* data = seq->data();
00647         bool delete_data;
00648         ErrorCode rval = remove_sequence( seq, delete_data );
00649         if( MB_SUCCESS != rval ) return rval;
00650         delete seq;
00651         if( delete_data ) delete data;
00652     }
00653     else if( seq->end_handle() == h )
00654     {
00655         if( seq->using_entire_data() ) availableList.insert( seq->data() );
00656         seq->pop_back( 1 );
00657     }
00658     else
00659     {
00660         iterator i = lower_bound( h );
00661         if( ( *i )->using_entire_data() ) availableList.insert( ( *i )->data() );
00662         i   = split_sequence( i, h );
00663         seq = *i;
00664         assert( seq->start_handle() == h );
00665         seq->pop_front( 1 );
00666     }
00667 
00668     return MB_SUCCESS;
00669 }
00670 
00671 ErrorCode TypeSequenceManager::erase( Error* /* error */, EntityHandle first, EntityHandle last )
00672 {
00673     // First check that all entities in range are valid
00674 
00675     ErrorCode rval = check_valid_handles( NULL, first, last );
00676     if( MB_SUCCESS != rval ) return rval;
00677 
00678     // Now remove entities
00679 
00680     // Get first sequence intersecting range
00681     iterator i = lower_bound( first );
00682     if( i == end() )  // Shouldn't be possible given check_valid_handles call above.
00683         return MB_ENTITY_NOT_FOUND;
00684 
00685     // If range is entirely in interior of sequence, need to split sequence.
00686     if( ( *i )->start_handle() < first && ( *i )->end_handle() > last )
00687     {
00688         if( ( *i )->using_entire_data() ) availableList.insert( ( *i )->data() );
00689         i = split_sequence( i, first );
00690         ( *i )->pop_front( last - first + 1 );
00691         assert( check_valid_data( *i ) );
00692         return MB_SUCCESS;
00693     }
00694 
00695     // If range doesn't entirely contain first sequence, remove some
00696     // handles from the end of the sequence and advance to the next
00697     // sequence.
00698     if( ( *i )->start_handle() < first )
00699     {
00700         if( ( *i )->using_entire_data() ) availableList.insert( ( *i )->data() );
00701         ( *i )->pop_back( ( *i )->end_handle() - first + 1 );
00702         ++i;
00703     }
00704 
00705     // Destroy all sequences contained entirely within the range
00706     while( i != end() && ( *i )->end_handle() <= last )
00707         i = erase( i );
00708 
00709     // If necessary, remove entities from the beginning of the
00710     // last sequence.
00711     if( i != end() && ( *i )->start_handle() <= last )
00712     {
00713         if( ( *i )->using_entire_data() ) availableList.insert( ( *i )->data() );
00714         ( *i )->pop_front( last - ( *i )->start_handle() + 1 );
00715         assert( check_valid_data( *i ) );
00716     }
00717 
00718     return MB_SUCCESS;
00719 }
00720 
00721 TypeSequenceManager::iterator TypeSequenceManager::split_sequence( iterator i, EntityHandle h )
00722 {
00723     EntitySequence* seq = ( *i )->split( h );
00724     if( !seq ) return end();
00725 
00726     i = sequenceSet.insert( i, seq );
00727     assert( check_valid_data( *i ) );
00728 
00729     return i;
00730 }
00731 
00732 ErrorCode TypeSequenceManager::is_free_handle( EntityHandle handle, iterator& seq_iter_out, SequenceData*& data_ptr_out,
00733                                                EntityHandle& block_start, EntityHandle& block_end, int values_per_ent )
00734 {
00735     int junk;
00736     block_start = CREATE_HANDLE( TYPE_FROM_HANDLE( handle ), MB_START_ID, junk );
00737     block_end   = CREATE_HANDLE( TYPE_FROM_HANDLE( handle ), MB_END_ID, junk );
00738 
00739     iterator i = lower_bound( handle );
00740     if( i != end() )
00741     {
00742         block_end = ( *i )->start_handle() - 1;
00743 
00744         // If sequence contains handle, then already allocated
00745         if( ( *i )->start_handle() <= handle ) return MB_ALREADY_ALLOCATED;
00746 
00747         // Handle is not within an existing sequence, but is
00748         // within an existing SequenceData...
00749         if( ( *i )->data()->start_handle() <= handle )
00750         {
00751             // If values_per_entity don't match, can't put new entity
00752             // in existing SequenceData
00753             if( ( *i )->values_per_entity() != values_per_ent ) return MB_ALREADY_ALLOCATED;
00754 
00755             data_ptr_out = ( *i )->data();
00756             if( block_end == handle )
00757             {
00758                 // Prepend to existing sequence
00759                 seq_iter_out = i;
00760                 block_start  = handle;
00761             }
00762             else
00763             {
00764                 // Add new sequence to existing SequenceData
00765                 seq_iter_out = end();
00766                 if( i == begin() || ( *--i )->data() != data_ptr_out )
00767                     block_start = data_ptr_out->start_handle();
00768                 else
00769                     block_start = ( *i )->end_handle() + 1;
00770             }
00771             return MB_SUCCESS;
00772         }
00773     }
00774 
00775     if( i != begin() )
00776     {
00777         --i;
00778         block_start = ( *i )->end_handle() + 1;
00779 
00780         // Handle is within previous sequence data...
00781         if( ( *i )->data()->end_handle() >= handle )
00782         {
00783             // If values_per_entity don't match, can't put new entity
00784             // in existing SequenceData
00785             if( ( *i )->values_per_entity() != values_per_ent ) return MB_ALREADY_ALLOCATED;
00786 
00787             data_ptr_out = ( *i )->data();
00788             if( block_start == handle )
00789             {
00790                 // Append to existing sequence
00791                 seq_iter_out = i;
00792                 block_end    = handle;
00793             }
00794             else
00795             {
00796                 // Add new sequence to existing SequenceData
00797                 seq_iter_out = end();
00798                 if( ++i == end() || ( *i )->data() != data_ptr_out )
00799                     block_end = data_ptr_out->end_handle();
00800                 else
00801                     block_end = ( *i )->start_handle() - 1;
00802             }
00803             return MB_SUCCESS;
00804         }
00805     }
00806 
00807     seq_iter_out = end();
00808     data_ptr_out = 0;
00809 
00810     return MB_SUCCESS;
00811 }
00812 
00813 ErrorCode TypeSequenceManager::notify_appended( iterator seq )
00814 {
00815     ErrorCode rval = check_merge_next( seq );
00816     if( ( *seq )->using_entire_data() ) availableList.erase( ( *seq )->data() );
00817 
00818     return rval;
00819 }
00820 
00821 ErrorCode TypeSequenceManager::notify_prepended( iterator seq )
00822 {
00823     ErrorCode rval = check_merge_prev( seq );
00824     if( ( *seq )->using_entire_data() ) availableList.erase( ( *seq )->data() );
00825 
00826     return rval;
00827 }
00828 
00829 void TypeSequenceManager::get_memory_use( unsigned long long& entity_storage, unsigned long long& total_storage ) const
00830 {
00831     entity_storage = total_storage = 0;
00832     if( empty() ) return;
00833 
00834     EntityType mytype = TYPE_FROM_HANDLE( lastReferenced->start_handle() );
00835     int junk;
00836     get_memory_use( CREATE_HANDLE( mytype, MB_START_ID, junk ), CREATE_HANDLE( mytype, MB_END_ID, junk ),
00837                     entity_storage, total_storage );
00838 }
00839 
00840 void TypeSequenceManager::append_memory_use( EntityHandle first, EntityHandle last, const SequenceData* data,
00841                                              unsigned long long& entity_storage,
00842                                              unsigned long long& total_storage ) const
00843 {
00844     const unsigned long allocated_count = data->size();
00845 
00846     unsigned long bytes_per_ent, seq_size;
00847     const_iterator i = data->seqManData.firstSequence;
00848     ( *i )->get_const_memory_use( bytes_per_ent, seq_size );
00849 
00850     unsigned long other_ent_mem  = 0;
00851     unsigned long occupied_count = 0, entity_count = 0, sequence_count = 0;
00852     for( ; i != end() && ( *i )->data() == data; ++i )
00853     {
00854         occupied_count += ( *i )->size();
00855         ++sequence_count;
00856 
00857         EntityHandle start = std::max( first, ( *i )->start_handle() );
00858         EntityHandle stop  = std::min( last, ( *i )->end_handle() );
00859         if( stop < start ) continue;
00860 
00861         entity_count += stop - start + 1;
00862         other_ent_mem += ( *i )->get_per_entity_memory_use( start, stop );
00863     }
00864 
00865     unsigned long sum = sequence_count * seq_size + allocated_count * bytes_per_ent;
00866 
00867     // Watch for overflow
00868     assert( entity_count > 0 && occupied_count > 0 && allocated_count > 0 );
00869     if( std::numeric_limits< unsigned long >::max() / entity_count <= sum )
00870     {
00871         total_storage += sum * ( entity_count / occupied_count ) + other_ent_mem;
00872         entity_storage += sum * ( entity_count / allocated_count ) + other_ent_mem;
00873     }
00874     else
00875     {
00876         total_storage += sum * entity_count / occupied_count + other_ent_mem;
00877         entity_storage += sum * entity_count / allocated_count + other_ent_mem;
00878     }
00879 }
00880 
00881 void TypeSequenceManager::get_memory_use( EntityHandle first, EntityHandle last, unsigned long long& entity_storage,
00882                                           unsigned long long& total_storage ) const
00883 {
00884     entity_storage = total_storage = 0;
00885 
00886     while( first <= last )
00887     {
00888         const_iterator i = lower_bound( first );
00889         if( i == end() ) return;
00890 
00891         SequenceData* data = ( *i )->data();
00892         if( first < data->end_handle() ) { append_memory_use( first, last, data, entity_storage, total_storage ); }
00893         first = data->end_handle() + 1;
00894     }
00895 }
00896 
00897 EntityID TypeSequenceManager::get_occupied_size( const SequenceData* data ) const
00898 {
00899     EntityID result = 0;
00900     for( const_iterator i = data->seqManData.firstSequence; i != end() && ( *i )->data() == data; ++i )
00901         result += ( *i )->size();
00902 
00903     return result;
00904 }
00905 
00906 #ifndef NDEBUG
00907 bool TypeSequenceManager::check_valid_data( const EntitySequence* seq ) const
00908 {
00909     // Caller passed a sequence that should be contained, so cannot be empty
00910     if( empty() ) return false;
00911 
00912     // Make sure lastReferenced points to something
00913     if( !lastReferenced ) return false;
00914 
00915     const_iterator seqi = sequenceSet.lower_bound( lastReferenced );
00916     if( seqi == sequenceSet.end() || *seqi != lastReferenced ) return false;
00917 
00918     // Make sure passed sequence is in list
00919     const EntitySequence* seq2 = find( seq->start_handle() );
00920     if( seq2 != seq ) return false;
00921 
00922     // Check all sequences referencing the same SequenceData
00923     const SequenceData* data = seq->data();
00924     const_iterator i         = lower_bound( data->start_handle() );
00925     if( i != data->seqManData.firstSequence ) return false;
00926 
00927     if( i != begin() )
00928     {
00929         const_iterator j = i;
00930         --j;
00931         if( ( *j )->end_handle() >= data->start_handle() ) return false;
00932         if( ( *j )->data()->end_handle() >= data->start_handle() ) return false;
00933     }
00934 
00935     for( ;; )
00936     {
00937         seq2 = *i;
00938         ++i;
00939         if( i == end() ) return true;
00940         if( ( *i )->data() != data ) break;
00941 
00942         if( seq2->end_handle() >= ( *i )->start_handle() ) return false;
00943     }
00944 
00945     if( ( *i )->start_handle() <= data->end_handle() ) return false;
00946     if( ( *i )->data()->start_handle() <= data->end_handle() ) return false;
00947 
00948     return true;
00949 }
00950 
00951 #endif
00952 
00953 }  // namespace moab
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines