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