moab
|
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