MOAB: Mesh Oriented datABase
(version 5.2.1)
|
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 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