Mesh Oriented datABase  (version 5.5.1)
An array-based unstructured mesh library
TypeSequenceManager.cpp
Go to the documentation of this file.
2 #include "SequenceData.hpp"
3 #include "moab/Error.hpp"
4 #include <cassert>
5 #include <limits>
6 
7 namespace moab
8 {
9 
11 {
12  // We assume that for there to be multiple sequences referencing
13  // the same SequenceData, there must be some portion of the
14  // SequenceData that is unused. Otherwise the sequences should
15  // have been merged. Given that assumption, it is the case that
16  // either a) a SequenceData is in availableList or b) the
17  // SequenceData is referenced by exactly one sequence.
18 
19  // Delete every entity sequence
20  for( iterator i = begin(); i != end(); ++i )
21  {
22  EntitySequence* seq = *i;
23  // Check for case b) above
24  if( seq->using_entire_data() )
25  {
26  // Delete sequence before data, because sequence
27  // has a pointer to data and may try to dereference
28  // that pointer during its destruction.
29  SequenceData* data = seq->data();
30  delete seq;
31  delete data;
32  }
33  else
34  {
35  delete seq;
36  }
37  }
38  sequenceSet.clear();
39 
40  // Case a) above
41  for( data_iterator i = availableList.begin(); i != availableList.end(); ++i )
42  delete *i;
43  availableList.clear();
44 }
45 
47 {
48  EntitySequence* dead = *j;
49  sequenceSet.erase( j );
50  ErrorCode rval = ( *i )->merge( *dead );
51  if( MB_SUCCESS != rval )
52  {
53  sequenceSet.insert( dead );
54  return rval;
55  }
56 
57  if( lastReferenced == dead ) lastReferenced = *i;
58  delete dead;
59 
60  // If merging results in no unused portions of the SequenceData,
61  // remove it from the available list.
62  if( ( *i )->using_entire_data() ) availableList.erase( ( *i )->data() );
63 
64  return MB_SUCCESS;
65 }
66 
68 {
69  iterator j = i;
70  ++j;
71  if( j == end() || ( *j )->data() != ( *i )->data() || ( *j )->start_handle() > ( *i )->end_handle() + 1 )
72  return MB_SUCCESS;
73 
74  assert( ( *i )->end_handle() + 1 == ( *j )->start_handle() );
75  return merge_internal( i, j );
76 }
77 
79 {
80  if( i == begin() ) return MB_SUCCESS;
81 
82  iterator j = i;
83  --j;
84  if( ( *j )->data() != ( *i )->data() || ( *j )->end_handle() + 1 < ( *i )->start_handle() ) return MB_SUCCESS;
85 
86  assert( ( *j )->end_handle() + 1 == ( *i )->start_handle() );
87  return merge_internal( i, j );
88 }
89 
91 {
92  if( !seq_ptr->data() ) return MB_FAILURE;
93 
94  if( seq_ptr->data()->start_handle() > seq_ptr->start_handle() ||
95  seq_ptr->data()->end_handle() < seq_ptr->end_handle() || seq_ptr->end_handle() < seq_ptr->start_handle() )
96  return MB_FAILURE;
97 
98  iterator i = lower_bound( seq_ptr->start_handle() );
99  if( i != end() )
100  {
101  if( ( *i )->start_handle() <= seq_ptr->end_handle() ) return MB_ALREADY_ALLOCATED;
102  if( seq_ptr->data() != ( *i )->data() && ( *i )->data()->start_handle() <= seq_ptr->data()->end_handle() )
103  return MB_ALREADY_ALLOCATED;
104  }
105 
106  if( i != begin() )
107  {
108  iterator j = i;
109  --j;
110  if( seq_ptr->data() != ( *j )->data() && ( *j )->data()->end_handle() >= seq_ptr->data()->start_handle() )
111  return MB_ALREADY_ALLOCATED;
112  }
113 
114  i = sequenceSet.insert( i, seq_ptr );
115 
116  // Merge with previous sequence ?
117  if( seq_ptr->start_handle() > seq_ptr->data()->start_handle() && i != begin() )
118  {
119  if( MB_SUCCESS != check_merge_prev( i ) )
120  {
121  sequenceSet.erase( i );
122  return MB_FAILURE;
123  }
124  }
125 
126  // Merge with next sequence ?
127  if( ( *i )->end_handle() < ( *i )->data()->end_handle() )
128  {
129  if( MB_SUCCESS != check_merge_next( i ) )
130  {
131  sequenceSet.erase( i );
132  return MB_FAILURE;
133  }
134  }
135 
136  // We merged adjacent sequences sharing a SequenceData, so
137  // we can safely assume that unless this EntitySequence is
138  // using the entire SequenceData, there are unused portions.
139  if( !seq_ptr->using_entire_data() ) availableList.insert( seq_ptr->data() );
140 
141  // lastReferenced is only allowed to be NULL if there are
142  // no sequences (avoids unnecessary if's in fast path).
143  if( !lastReferenced ) lastReferenced = seq_ptr;
144 
145  // Each SequenceData has a pointer to the first EntitySequence
146  // referencing it. Update that pointer if the new sequence is
147  // the first one.
148  if( ( *i )->start_handle() == ( *i )->data()->start_handle() || lower_bound( ( *i )->data()->start_handle() ) == i )
149  ( *i )->data()->seqManData.firstSequence = i;
150 
151  assert( check_valid_data( seq_ptr ) );
152  return MB_SUCCESS;
153 }
154 
155 ErrorCode TypeSequenceManager::replace_subsequence( EntitySequence* seq_ptr, const int* tag_sizes, int num_tag_sizes )
156 {
157  // Find the sequence of interest
158  iterator i = lower_bound( seq_ptr->start_handle() );
159  if( i == end() || ( *i )->data() == seq_ptr->data() ) return MB_FAILURE;
160  // New sequence must be a subset of an existing one
161  if( seq_ptr->start_handle() < ( *i )->start_handle() || seq_ptr->end_handle() > ( *i )->end_handle() )
162  return MB_FAILURE;
163  // New sequence's data must be new also, and cannot intersect
164  // any existing sequence (just require that the data range
165  // matches the sequence range for now)
166  if( !seq_ptr->using_entire_data() ) return MB_FAILURE;
167  // Copy tag data (move ownership of var-len data)
168  SequenceData* const dead_data = ( *i )->data();
169  dead_data->move_tag_data( seq_ptr->data(), tag_sizes, num_tag_sizes );
170 
171  // Split sequences sharing old data into two groups:
172  // p->i : first sequence to i
173  // i->n : i to one past last sequence
174  iterator p, n = i;
175  p = ( *i )->data()->seqManData.firstSequence;
176  for( ++n; n != end() && ( *n )->data() == ( *i )->data(); ++n )
177  ;
178 
179  // First subdivide EntitySequence as necessary
180  // Move i to be the first sequence past the insertion point
181  // such that the new order will be:
182  // [p,i-1] seq_ptr [i,n]
183  // where p == i if no previous sequence
184 
185  // Four possible cases:
186  // 0. All entities in sequence are in new sequence
187  // 1. Old entities in sequence before and after new sequence,
188  // requiring sequence to be split.
189  // 2. Old entities after new sequence
190  // 3. Old entities before new sequence
191  const bool some_before = ( ( *i )->start_handle() < seq_ptr->start_handle() );
192  const bool some_after = ( ( *i )->end_handle() > seq_ptr->end_handle() );
193  // Case 0
194  if( !( some_before || some_after ) )
195  {
196  // Remove dead sequence from internal lists
197  EntitySequence* seq = *i;
198  iterator dead = i;
199  ++i;
200  if( p == dead ) p = i;
201  sequenceSet.erase( dead );
202 
203  // Delete old sequence
204  delete seq;
205  // Make sure lastReferenced isn't stale
206  if( lastReferenced == seq ) lastReferenced = seq_ptr;
207  }
208  // Case 1
209  else if( some_before && some_after )
210  {
211  i = split_sequence( i, seq_ptr->start_handle() );
212  ( *i )->pop_front( seq_ptr->size() );
213  }
214  // Case 2
215  else if( some_after )
216  {
217  ( *i )->pop_front( seq_ptr->size() );
218  }
219  // Case 3
220  else
221  { // some_before
222  ( *i )->pop_back( seq_ptr->size() );
223  ++i;
224  }
225 
226  // Now subdivide the underlying sequence data as necessary
227  availableList.erase( dead_data );
228  if( p != i )
229  {
230  iterator last = i;
231  --last;
232  SequenceData* new_data = ( *p )->create_data_subset( ( *p )->start_handle(), ( *last )->end_handle() );
233  new_data->seqManData.firstSequence = p;
234 
235  for( ; p != i; ++p )
236  ( *p )->data( new_data );
237  // Copy tag data (move ownership of var-len data)
238  dead_data->move_tag_data( new_data, tag_sizes, num_tag_sizes );
239  if( !( *new_data->seqManData.firstSequence )->using_entire_data() ) availableList.insert( new_data );
240  }
241  if( i != n )
242  {
243  iterator last = n;
244  --last;
245  SequenceData* new_data = ( *i )->create_data_subset( ( *i )->start_handle(), ( *last )->end_handle() );
246  new_data->seqManData.firstSequence = i;
247  for( ; i != n; ++i )
248  ( *i )->data( new_data );
249  // Copy tag data (move ownership of var-len data)
250  dead_data->move_tag_data( new_data, tag_sizes, num_tag_sizes );
251  if( !( *new_data->seqManData.firstSequence )->using_entire_data() ) availableList.insert( new_data );
252  }
253  delete dead_data;
254 
255  // Put new sequence in lists
256  return insert_sequence( seq_ptr );
257 }
258 
260 {
261  EntitySequence* seq = *i;
262  SequenceData* data = seq->data();
263  iterator j;
264 
265  // Check if we need to delete the referenced SequenceData also
266  bool delete_data;
267  if( seq->using_entire_data() ) // Only sequence
268  delete_data = true;
269  else if( data->seqManData.firstSequence != i )
270  { // Earlier sequence?
271  delete_data = false;
272  availableList.insert( data );
273  }
274  else
275  { // Later sequence ?
276  j = i;
277  ++j;
278  delete_data = ( j == end() || ( *j )->data() != data );
279  if( delete_data )
280  availableList.erase( data );
281  else
282  {
283  availableList.insert( data );
284  data->seqManData.firstSequence = j;
285  }
286  }
287 
288  // Remove sequence, updating i to be next sequence
289  j = i++;
290  sequenceSet.erase( j );
291 
292  // Make sure lastReferenced isn't stale. It can only be NULL if
293  // no sequences.
294  if( lastReferenced == seq ) lastReferenced = sequenceSet.empty() ? 0 : *sequenceSet.begin();
295 
296  // Always delete sequence before the SequenceData it references.
297  assert( 0 == find( seq->start_handle() ) );
298  delete seq;
299  if( delete_data )
300  delete data;
301  else
302  {
303  assert( check_valid_data( *data->seqManData.firstSequence ) );
304  assert( lastReferenced != seq );
305  }
306  return i;
307 }
308 
309 ErrorCode TypeSequenceManager::remove_sequence( const EntitySequence* seq_ptr, bool& unreferenced_data )
310 {
311  // Remove sequence from set
312  iterator i = lower_bound( seq_ptr->start_handle() );
313  if( i == end() || *i != seq_ptr ) return MB_ENTITY_NOT_FOUND;
314  sequenceSet.erase( i );
315 
316  // Check if this is the only sequence referencing its data
317  if( seq_ptr->using_entire_data() )
318  unreferenced_data = true;
319  else
320  {
321  i = lower_bound( seq_ptr->data()->start_handle() );
322  unreferenced_data = i == end() || ( *i )->data() != seq_ptr->data();
323  if( unreferenced_data )
324  availableList.erase( seq_ptr->data() );
325  else
326  seq_ptr->data()->seqManData.firstSequence = i; // Might be 'i' already
327  }
328 
329  if( lastReferenced == seq_ptr ) lastReferenced = sequenceSet.empty() ? 0 : *sequenceSet.begin();
330 
331  return MB_SUCCESS;
332 }
333 
335  EntityHandle max_end_handle,
336  bool& append_out,
337  int values_per_ent )
338 {
339  for( data_iterator i = availableList.begin(); i != availableList.end(); ++i )
340  {
341  if( ( *( *i )->seqManData.firstSequence )->values_per_entity() != values_per_ent ) continue;
342 
343  if( ( *i )->start_handle() > max_end_handle || ( *i )->end_handle() < min_start_handle ) continue;
344 
345  for( iterator j = ( *i )->seqManData.firstSequence;
346  j != end() && ( *j )->start_handle() <= ( max_end_handle + 1 ) && ( *j )->data() == *i; ++j )
347  {
348  if( ( *j )->end_handle() + 1 < min_start_handle ) continue;
349  if( ( *j )->start_handle() > ( *i )->start_handle() && ( *j )->start_handle() > min_start_handle )
350  {
351  append_out = false;
352  return j;
353  }
354  if( ( *j )->end_handle() < ( *i )->end_handle() && ( *j )->end_handle() < max_end_handle )
355  {
356  append_out = true;
357  return j;
358  }
359  }
360  }
361 
362  return end();
363 }
364 
366  EntityID num_entities,
367  SequenceData*& data_out,
368  int values_per_ent )
369 {
370  data_out = 0;
371  if( empty() ) return true;
372 
373  const_iterator i = lower_bound( start );
374  if( i == end() )
375  {
376  --i; // Safe because already tested empty()
377  // If we don't overlap the last data object...
378  if( ( *i )->data()->end_handle() < start ) return true;
379  data_out = ( *i )->data();
380  if( ( *i )->values_per_entity() != values_per_ent ) return false;
381  // If we overlap a data object, we must be entirely inside of it
382  return start + num_entities - 1 <= ( *i )->data()->end_handle();
383  }
384 
385 #ifndef NDEBUG
386  if( i != begin() )
387  {
388  const_iterator j = i;
389  --j;
390  assert( ( *j )->end_handle() < start );
391  }
392 #endif
393 
394  // Check if we fit in the block of free handles
395  if( start + num_entities > ( *i )->start_handle() ) // start + num + 1 >= i->start
396  return false;
397 
398  // Check if we overlap the data for the next sequence
399  if( start + num_entities > ( *i )->data()->start_handle() )
400  {
401  data_out = ( *i )->data();
402  if( ( *i )->values_per_entity() != values_per_ent ) return false;
403  // If overlap, must be entirely contained
404  return start >= data_out->start_handle() && start + num_entities - 1 <= data_out->end_handle();
405  }
406 
407  // Check if we overlap the data for the previous sequence
408  if( i != begin() )
409  {
410  --i;
411  if( ( *i )->data()->end_handle() >= start )
412  {
413  data_out = ( *i )->data();
414  if( ( *i )->values_per_entity() != values_per_ent ) return false;
415  return start + num_entities - 1 <= ( *i )->data()->end_handle();
416  }
417  }
418 
419  // Unused handle block that overlaps no SequenceData
420  return true;
421 }
422 
424  EntityHandle min_start_handle,
425  EntityHandle max_end_handle )
426 {
427  const_iterator i = lower_bound( min_start_handle );
428  if( i == end() ) return min_start_handle;
429 
430  if( ( *i )->start_handle() < min_start_handle + num_entities ) return min_start_handle;
431 
432  EntityHandle prev_end = ( *i )->end_handle();
433  ++i;
434  for( ; i != end(); prev_end = ( *i )->end_handle(), ++i )
435  {
436  EntityID len = ( *i )->start_handle() - prev_end - 1;
437  if( len >= num_entities ) break;
438  }
439 
440  if( prev_end + num_entities > max_end_handle )
441  return 0;
442  else
443  return prev_end + 1;
444 }
445 
447 {
451 };
452 
453 static bool check_range( const range_data& d, bool prefer_end, EntityHandle& result )
454 {
455  EntityHandle first = std::max( d.min_start_handle, d.first );
456  EntityHandle last = std::min( d.max_end_handle, d.last );
457  if( last < first + d.num_entities - 1 )
458  {
459  result = 0;
460  return false;
461  }
462 
463  result = prefer_end ? last + 1 - d.num_entities : first;
464  return true;
465 }
466 
468  EntityHandle min_start_handle,
469  EntityHandle max_end_handle,
470  SequenceData*& data_out,
471  EntityID& data_size,
472  int num_verts )
473 {
474  if( max_end_handle < min_start_handle + num_entities - 1 ) return 0;
475 
476  EntityHandle result;
477  iterator p, i = lower_bound( min_start_handle );
478  range_data d = { num_entities, min_start_handle, max_end_handle, 0, 0 };
479 
480  if( i == end() )
481  {
482  data_out = 0;
483  return min_start_handle;
484  }
485  else if( i == begin() )
486  {
487  if( ( *i )->values_per_entity() == num_verts )
488  {
489  d.first = ( *i )->data()->start_handle();
490  d.last = ( *i )->start_handle() - 1;
491  if( check_range( d, true, result ) )
492  {
493  data_out = ( *i )->data();
494  return result;
495  }
496  }
497  d.first = min_start_handle;
498  d.last = ( *i )->data()->start_handle() - 1;
499  if( check_range( d, true, result ) )
500  {
501  data_out = 0;
502  // This will back up against the end of the seq data, so
503  // size the data that way
504  data_size = num_entities;
505  return result;
506  }
507  p = i++;
508  }
509  else
510  {
511  p = i;
512  --p;
513  }
514 
515  for( ; i != end() && ( *i )->start_handle() < max_end_handle; p = i++ )
516  {
517  if( ( *p )->data() == ( *i )->data() )
518  {
519  if( ( *p )->values_per_entity() == num_verts )
520  {
521  d.first = ( *p )->end_handle() + 1;
522  d.last = ( *i )->start_handle() - 1;
523  if( check_range( d, false, result ) )
524  {
525  data_out = ( *p )->data();
526  return result;
527  }
528  }
529  }
530  else
531  {
532  if( ( *p )->values_per_entity() == num_verts )
533  {
534  d.first = ( *p )->end_handle() + 1;
535  d.last = ( *p )->data()->end_handle();
536  if( check_range( d, false, result ) )
537  {
538  data_out = ( *p )->data();
539  return result;
540  }
541  }
542  if( ( *i )->values_per_entity() == num_verts )
543  {
544  d.first = ( *i )->data()->start_handle();
545  d.last = ( *i )->start_handle() - 1;
546  if( check_range( d, true, result ) )
547  {
548  data_out = ( *i )->data();
549  return result;
550  }
551  }
552  d.first = ( *p )->data()->end_handle() + 1;
553  d.last = ( *i )->data()->start_handle() - 1;
554  if( check_range( d, false, result ) )
555  {
556  data_out = 0;
557  data_size = d.last - d.first + 1;
558  return result;
559  }
560  }
561  }
562 
563  if( ( *p )->values_per_entity() == num_verts )
564  {
565  d.first = ( *p )->end_handle() + 1;
566  d.last = ( *p )->data()->end_handle();
567  if( check_range( d, false, result ) )
568  {
569  data_out = ( *p )->data();
570  return result;
571  }
572  }
573 
574  d.first = ( *p )->data()->end_handle() + 1;
575  d.last = max_end_handle;
576  if( check_range( d, false, result ) )
577  {
578  data_out = 0;
579  return result;
580  }
581 
582  data_out = 0;
583  return 0;
584 }
585 
587 {
588  int junk;
589  const_iterator it = lower_bound( after_this );
590  if( it == end() )
591  return CREATE_HANDLE( TYPE_FROM_HANDLE( after_this ), MB_END_ID, junk );
592  else if( ( *it )->start_handle() > after_this )
593  {
594  // Need to check against the sequence data first
595  EntityHandle rhandle = ( *it )->data()->start_handle();
596  return rhandle - 1;
597  }
598  else
599  return 0;
600 }
601 
604  EntityHandle last ) const
605 {
607  if( i == end() || ( *i )->start_handle() > first )
608  {
609 #if 0
610  // MB_ENTITY_NOT_FOUND could be a non-error condition, do not call
611  // MB_SET_ERR on it
612  fprintf(
613  stderr,
614  "[Warning]: Invalid entity handle: 0x%lx\n", (unsigned long)first
615  );
616 #endif
617  return MB_ENTITY_NOT_FOUND;
618  }
619 
620  while( ( *i )->end_handle() < last )
621  {
622  EntityHandle prev_end = ( *i )->end_handle();
623  ++i;
624  if( i == end() || prev_end + 1 != ( *i )->start_handle() ) return MB_ENTITY_NOT_FOUND;
625  }
626 
627  return MB_SUCCESS;
628 }
629 
631 {
632  EntitySequence* seq = find( h );
633  if( !seq )
634  {
635 #if 0
636  // MB_ENTITY_NOT_FOUND could be a non-error condition, do not call
637  // MB_SET_ERR on it
638  fprintf(
639  stderr,
640  "[Warning]: Invalid entity handle: 0x%lx\n", (unsigned long)h
641  );
642 #endif
643  return MB_ENTITY_NOT_FOUND;
644  }
645 
646  if( seq->start_handle() == h )
647  {
648  if( seq->end_handle() != h )
649  {
650  if( seq->using_entire_data() ) availableList.insert( seq->data() );
651  seq->pop_front( 1 );
652  return MB_SUCCESS;
653  }
654  SequenceData* data = seq->data();
655  bool delete_data;
656  ErrorCode rval = remove_sequence( seq, delete_data );
657  if( MB_SUCCESS != rval ) return rval;
658  delete seq;
659  if( delete_data ) delete data;
660  }
661  else if( seq->end_handle() == h )
662  {
663  if( seq->using_entire_data() ) availableList.insert( seq->data() );
664  seq->pop_back( 1 );
665  }
666  else
667  {
668  iterator i = lower_bound( h );
669  if( ( *i )->using_entire_data() ) availableList.insert( ( *i )->data() );
670  i = split_sequence( i, h );
671  seq = *i;
672  assert( seq->start_handle() == h );
673  seq->pop_front( 1 );
674  }
675 
676  return MB_SUCCESS;
677 }
678 
680 {
681  // First check that all entities in range are valid
682 
683  ErrorCode rval = check_valid_handles( NULL, first, last );
684  if( MB_SUCCESS != rval ) return rval;
685 
686  // Now remove entities
687 
688  // Get first sequence intersecting range
689  iterator i = lower_bound( first );
690  if( i == end() ) // Shouldn't be possible given check_valid_handles call above.
691  return MB_ENTITY_NOT_FOUND;
692 
693  // If range is entirely in interior of sequence, need to split sequence.
694  if( ( *i )->start_handle() < first && ( *i )->end_handle() > last )
695  {
696  if( ( *i )->using_entire_data() ) availableList.insert( ( *i )->data() );
697  i = split_sequence( i, first );
698  ( *i )->pop_front( last - first + 1 );
699  assert( check_valid_data( *i ) );
700  return MB_SUCCESS;
701  }
702 
703  // If range doesn't entirely contain first sequence, remove some
704  // handles from the end of the sequence and advance to the next
705  // sequence.
706  if( ( *i )->start_handle() < first )
707  {
708  if( ( *i )->using_entire_data() ) availableList.insert( ( *i )->data() );
709  ( *i )->pop_back( ( *i )->end_handle() - first + 1 );
710  ++i;
711  }
712 
713  // Destroy all sequences contained entirely within the range
714  while( i != end() && ( *i )->end_handle() <= last )
715  i = erase( i );
716 
717  // If necessary, remove entities from the beginning of the
718  // last sequence.
719  if( i != end() && ( *i )->start_handle() <= last )
720  {
721  if( ( *i )->using_entire_data() ) availableList.insert( ( *i )->data() );
722  ( *i )->pop_front( last - ( *i )->start_handle() + 1 );
723  assert( check_valid_data( *i ) );
724  }
725 
726  return MB_SUCCESS;
727 }
728 
730 {
731  EntitySequence* seq = ( *i )->split( h );
732  if( !seq ) return end();
733 
734  i = sequenceSet.insert( i, seq );
735  assert( check_valid_data( *i ) );
736 
737  return i;
738 }
739 
741  iterator& seq_iter_out,
742  SequenceData*& data_ptr_out,
743  EntityHandle& block_start,
744  EntityHandle& block_end,
745  int values_per_ent )
746 {
747  int junk;
748  block_start = CREATE_HANDLE( TYPE_FROM_HANDLE( handle ), MB_START_ID, junk );
749  block_end = CREATE_HANDLE( TYPE_FROM_HANDLE( handle ), MB_END_ID, junk );
750 
751  iterator i = lower_bound( handle );
752  if( i != end() )
753  {
754  block_end = ( *i )->start_handle() - 1;
755 
756  // If sequence contains handle, then already allocated
757  if( ( *i )->start_handle() <= handle ) return MB_ALREADY_ALLOCATED;
758 
759  // Handle is not within an existing sequence, but is
760  // within an existing SequenceData...
761  if( ( *i )->data()->start_handle() <= handle )
762  {
763  // If values_per_entity don't match, can't put new entity
764  // in existing SequenceData
765  if( ( *i )->values_per_entity() != values_per_ent ) return MB_ALREADY_ALLOCATED;
766 
767  data_ptr_out = ( *i )->data();
768  if( block_end == handle )
769  {
770  // Prepend to existing sequence
771  seq_iter_out = i;
772  block_start = handle;
773  }
774  else
775  {
776  // Add new sequence to existing SequenceData
777  seq_iter_out = end();
778  if( i == begin() || ( *--i )->data() != data_ptr_out )
779  block_start = data_ptr_out->start_handle();
780  else
781  block_start = ( *i )->end_handle() + 1;
782  }
783  return MB_SUCCESS;
784  }
785  }
786 
787  if( i != begin() )
788  {
789  --i;
790  block_start = ( *i )->end_handle() + 1;
791 
792  // Handle is within previous sequence data...
793  if( ( *i )->data()->end_handle() >= handle )
794  {
795  // If values_per_entity don't match, can't put new entity
796  // in existing SequenceData
797  if( ( *i )->values_per_entity() != values_per_ent ) return MB_ALREADY_ALLOCATED;
798 
799  data_ptr_out = ( *i )->data();
800  if( block_start == handle )
801  {
802  // Append to existing sequence
803  seq_iter_out = i;
804  block_end = handle;
805  }
806  else
807  {
808  // Add new sequence to existing SequenceData
809  seq_iter_out = end();
810  if( ++i == end() || ( *i )->data() != data_ptr_out )
811  block_end = data_ptr_out->end_handle();
812  else
813  block_end = ( *i )->start_handle() - 1;
814  }
815  return MB_SUCCESS;
816  }
817  }
818 
819  seq_iter_out = end();
820  data_ptr_out = 0;
821 
822  return MB_SUCCESS;
823 }
824 
826 {
827  ErrorCode rval = check_merge_next( seq );
828  if( ( *seq )->using_entire_data() ) availableList.erase( ( *seq )->data() );
829 
830  return rval;
831 }
832 
834 {
835  ErrorCode rval = check_merge_prev( seq );
836  if( ( *seq )->using_entire_data() ) availableList.erase( ( *seq )->data() );
837 
838  return rval;
839 }
840 
841 void TypeSequenceManager::get_memory_use( unsigned long long& entity_storage, unsigned long long& total_storage ) const
842 {
843  entity_storage = total_storage = 0;
844  if( empty() ) return;
845 
846  EntityType mytype = TYPE_FROM_HANDLE( lastReferenced->start_handle() );
847  int junk;
848  get_memory_use( CREATE_HANDLE( mytype, MB_START_ID, junk ), CREATE_HANDLE( mytype, MB_END_ID, junk ),
849  entity_storage, total_storage );
850 }
851 
853  EntityHandle last,
854  const SequenceData* data,
855  unsigned long long& entity_storage,
856  unsigned long long& total_storage ) const
857 {
858  const unsigned long allocated_count = data->size();
859 
860  unsigned long bytes_per_ent, seq_size;
862  ( *i )->get_const_memory_use( bytes_per_ent, seq_size );
863 
864  unsigned long other_ent_mem = 0;
865  unsigned long occupied_count = 0, entity_count = 0, sequence_count = 0;
866  for( ; i != end() && ( *i )->data() == data; ++i )
867  {
868  occupied_count += ( *i )->size();
869  ++sequence_count;
870 
871  EntityHandle start = std::max( first, ( *i )->start_handle() );
872  EntityHandle stop = std::min( last, ( *i )->end_handle() );
873  if( stop < start ) continue;
874 
875  entity_count += stop - start + 1;
876  other_ent_mem += ( *i )->get_per_entity_memory_use( start, stop );
877  }
878 
879  unsigned long sum = sequence_count * seq_size + allocated_count * bytes_per_ent;
880 
881  // Watch for overflow
882  assert( entity_count > 0 && occupied_count > 0 && allocated_count > 0 );
883  if( std::numeric_limits< unsigned long >::max() / entity_count <= sum )
884  {
885  total_storage += sum * ( entity_count / occupied_count ) + other_ent_mem;
886  entity_storage += sum * ( entity_count / allocated_count ) + other_ent_mem;
887  }
888  else
889  {
890  total_storage += sum * entity_count / occupied_count + other_ent_mem;
891  entity_storage += sum * entity_count / allocated_count + other_ent_mem;
892  }
893 }
894 
896  EntityHandle last,
897  unsigned long long& entity_storage,
898  unsigned long long& total_storage ) const
899 {
900  entity_storage = total_storage = 0;
901 
902  while( first <= last )
903  {
905  if( i == end() ) return;
906 
907  SequenceData* data = ( *i )->data();
908  if( first < data->end_handle() )
909  {
910  append_memory_use( first, last, data, entity_storage, total_storage );
911  }
912  first = data->end_handle() + 1;
913  }
914 }
915 
917 {
918  EntityID result = 0;
919  for( const_iterator i = data->seqManData.firstSequence; i != end() && ( *i )->data() == data; ++i )
920  result += ( *i )->size();
921 
922  return result;
923 }
924 
925 #ifndef NDEBUG
927 {
928  // Caller passed a sequence that should be contained, so cannot be empty
929  if( empty() ) return false;
930 
931  // Make sure lastReferenced points to something
932  if( !lastReferenced ) return false;
933 
934  const_iterator seqi = sequenceSet.lower_bound( lastReferenced );
935  if( seqi == sequenceSet.end() || *seqi != lastReferenced ) return false;
936 
937  // Make sure passed sequence is in list
938  const EntitySequence* seq2 = find( seq->start_handle() );
939  if( seq2 != seq ) return false;
940 
941  // Check all sequences referencing the same SequenceData
942  const SequenceData* data = seq->data();
943  const_iterator i = lower_bound( data->start_handle() );
944  if( i != data->seqManData.firstSequence ) return false;
945 
946  if( i != begin() )
947  {
948  const_iterator j = i;
949  --j;
950  if( ( *j )->end_handle() >= data->start_handle() ) return false;
951  if( ( *j )->data()->end_handle() >= data->start_handle() ) return false;
952  }
953 
954  for( ;; )
955  {
956  seq2 = *i;
957  ++i;
958  if( i == end() ) return true;
959  if( ( *i )->data() != data ) break;
960 
961  if( seq2->end_handle() >= ( *i )->start_handle() ) return false;
962  }
963 
964  if( ( *i )->start_handle() <= data->end_handle() ) return false;
965  if( ( *i )->data()->start_handle() <= data->end_handle() ) return false;
966 
967  return true;
968 }
969 
970 #endif
971 
972 } // namespace moab