Mesh Oriented datABase  (version 5.5.1)
An array-based unstructured mesh library
TypeSequenceManager.hpp
Go to the documentation of this file.
1 #ifndef TYPE_SEQUENCE_MANAGER_HPP
2 #define TYPE_SEQUENCE_MANAGER_HPP
3 
4 #include "EntitySequence.hpp"
5 #include "moab/Range.hpp"
6 
7 #include <set>
8 #include <vector>
9 
10 namespace moab
11 {
12 
13 class Error;
14 
15 /**\brief Maintain data structures organizing EntitySequence instances
16  *
17  * EntitySequenceManager is a composition of instances of TypeSequenceManager,
18  * one instance for each EntityType. The TypeSequenceManager provides
19  * organization, ownership, and querying of EntitySequences for a specific
20  * EntityType.
21  */
23 {
24  public:
25  /**\brief Comparison function used in std::set
26  *
27  * Define less-than comparison for EntitySequence pointers as a comparison
28  * of the entity handles in the pointed-to EntitySequences.
29  */
30  template < class T >
32  {
33  public:
34  inline bool operator()( const T* a, const T* b ) const
35  {
36  return a->end_handle() < b->start_handle();
37  }
38  };
39  /**\brief Dummy EntitySequence for use in querying set container */
41  {
42  public:
43  DummySequence( EntityHandle start ) : EntitySequence( start ) {}
44 
46  {
47  return 0;
48  }
50  {
51  return 0;
52  }
53 
54  void get_const_memory_use( unsigned long& a, unsigned long& b ) const
55  {
56  a = b = 0;
57  }
59  {
60  return 0;
61  }
62  };
63 
64  /**\brief Type of container for organizing EntitySequence instances */
65  typedef std::set< EntitySequence*, SequenceCompare< EntitySequence > > set_type;
66  /**\brief Iterator for set_type */
67  typedef set_type::iterator iterator;
68  /**\brief Iterator for set_type */
69  typedef set_type::const_iterator const_iterator;
70  /**\brief Type of container for organizing SequenceData instances */
71  typedef std::set< SequenceData*, SequenceCompare< SequenceData > > data_set_type;
72  /**\brief iterator type for data_set_type */
73  typedef data_set_type::iterator data_iterator;
74 
76  {
77  private:
78  friend class TypeSequenceManager;
80  };
81 
82  private:
83  mutable EntitySequence* lastReferenced; //!< Last accessed EntitySequence - Null only if no sequences
84  set_type sequenceSet; //!< Set of all managed EntitySequence instances
85  data_set_type availableList; //!< SequenceData containing unused entries
86 
87  iterator erase( iterator i ); //!< Remove a sequence
88 
89  iterator split_sequence( iterator i, EntityHandle h ); //!< split a sequence
90 
92  EntityHandle last,
93  const SequenceData* data,
94  unsigned long long& entity_storage,
95  unsigned long long& total_storage ) const;
96 
97  // check if sequence at passed iterator should be merged with
98  // the subsequent sequence, and if so merge them retaining i.
100  // check if sequence at passed iterator should be merged with
101  // the previous sequence, and if so merge them retaining i.
103  // common code for check_merge_next and check_merge_prev
105 
106 #ifndef NDEBUG
107  bool check_valid_data( const EntitySequence* seq ) const;
108 #endif
109 
110  public:
111  /**\brief Add an entity sequence
112  *
113  * Take ownership of passed EntitySequence, and update relevant
114  * data structures. Sequence may not overlap with any existing
115  * sequence.
116  *
117  * NOTE: Sequence may be merged with other, existing sequences.
118  * This function will always ensure that the passed
119  * EntitySequence* is the remaining one, but the passed
120  * sequence may have modified start and end handles.
121  */
123 
124  /**\brief Remove an entity sequence.
125  *
126  * Give up ownership of specified EntitySequence, and remove it
127  * from all internal data structures. Passes back bool flag to
128  * notify caller that ownership of the corresponding SequenceData
129  * is also relinquished because the specified EntitySequence is
130  * the last one referencing it.
131  */
132  ErrorCode remove_sequence( const EntitySequence* seq_ptr, bool& is_last_user_of_sequence_data );
133 
134  /**\brief Replace sequence or subset of sequence
135  *
136  * Replace one sequence or a subset of one sequence with
137  * another sequence. With fail if a) the existing
138  * sequence is not a subset of an existing sequence or
139  * b) existing sequence shares a SequenceData with the
140  * passed sequence.
141  *
142  * This method is provided for use when changing the
143  * number of nodes in elements.
144  */
145  ErrorCode replace_subsequence( EntitySequence* seq_ptr, const int* tag_sizes, int num_tag_sizes );
146 
148 
150 
151  /**\brief Start of EntitySequence set */
153  {
154  return sequenceSet.begin();
155  }
157  {
158  return sequenceSet.begin();
159  }
160 
161  /**\brief End of EntitySequence set */
163  {
164  return sequenceSet.end();
165  }
167  {
168  return sequenceSet.end();
169  }
170 
171  /**\brief Return EntitySequence for specified handle.
172  *
173  * Return EntitySequence for specified handle, or if
174  * no such sequence, the next one. Returns end() if
175  * all sequences have ranges less than specified handle.
176  */
178  {
179  DummySequence f( h );
180  return sequenceSet.lower_bound( &f );
181  }
183  {
184  DummySequence f( h );
185  return sequenceSet.lower_bound( &f );
186  }
187 
188  /**\brief Return EntitySequence after specified handle.
189  *
190  * Return EntitySequence with smallest start handle
191  * that is greater than input handle. Returns end() if
192  * all sequences have start handles less than specified
193  * handle.
194  */
196  {
197  DummySequence f( h );
198  return sequenceSet.upper_bound( &f );
199  }
200 
201  /**\brief Get EntitySequence for handle.
202  *\return EntitySequence for handle, or NULL if no such sequence.
203  */
204  inline EntitySequence* find( EntityHandle h ) const;
205  inline EntitySequence* find( EntityHandle h );
206  inline ErrorCode find( EntityHandle h, EntitySequence*& );
207  inline ErrorCode find( EntityHandle h, const EntitySequence*& ) const;
208  inline const EntitySequence* get_last_accessed() const;
209 
210  /**\brief Get handles for all entities in all sequences. */
211  inline void get_entities( Range& entities_out ) const;
212 
213  /**\brief Get handles for all entities in all sequences. */
214  inline void get_entities( std::vector< EntityHandle >& entities_out ) const;
215 
216  /**\brief Get number of entities represented by all sequences. */
217  inline EntityID get_number_entities() const;
218 
219  ErrorCode check_valid_handles( Error* error_handler, EntityHandle first, EntityHandle last ) const;
220 
221  /**\brief Remove entities
222  *
223  * Update EntitySequence data as necessary to "delete" the
224  * specified entities (e.g. split sequences, delete sequences,
225  * free SequenceData instances, etc.)
226  */
227  ErrorCode erase( Error* error_handler, EntityHandle first, EntityHandle last );
228  ErrorCode erase( Error* error_handler, EntityHandle entity );
229 
230  /**\brief Test if this instance contains no sequences */
231  bool empty() const
232  {
233  return 0 == lastReferenced;
234  }
235 
236  /**\brief Allocate a handle in an existing entity sequence
237  *
238  * Find an existing entity sequence to which a new handle can
239  * be prepended or appended. The 'append_out' flag indicates
240  * to the caller that the new handle should be appended to the
241  * returned sequence if true, and prepended if false.
242  *
243  * If no appropriate EntitySequence is available, NULL will
244  * be returned. The caller will typically then want to use
245  * find_free_sequence() to find appropriate values for the
246  * creation of a new EntitySequence.
247  */
248  iterator find_free_handle( EntityHandle min_start_handle,
249  EntityHandle max_end_handle,
250  bool& append_out,
251  int values_per_ent = 0 );
252 
253  /**\brief Find block of free handles
254  *
255  * Find block of free handles, such that block does not
256  * overlap any existing EntitySequence.
257  *\return First handle of block, or zero if no block found.
258  */
259  EntityHandle find_free_block( EntityID num_entities, EntityHandle min_start_handle, EntityHandle max_end_handle );
260 
261  /**\brief Find block of free handles
262  *
263  * Find block of free handles, such that block a) does not
264  * overlap any existing EntitySequence and b) is either
265  * entirely within one existing SequenceData or does not
266  * overlap any SequenceData.
267  *\param num_entities Size of handle block.
268  *\param min_start_handle Block may not contain any handle less than this.
269  *\param max_end_handle Block may not contain any handle greater than this.
270  *\param sequence_data_out If block is within an unused portion of an
271  * existing SequenceData, a pointer to that
272  * SequenceData. NULL otherwise.
273  *\return values_per_ent Matched against EntitySequence::values_per_entity.
274  * An existing SequenceData will not be returned if
275  * the existing EntitySequences using have a different
276  * value than the passed one.
277  */
279  EntityHandle min_start_handle,
280  EntityHandle max_end_handle,
281  SequenceData*& sequence_data_out,
282  EntityID& sequence_data_size,
283  int values_per_ent = 0 );
284 
285  /**\brief Check if block of handles is free.
286  *
287  * Check if block of handles is free and can be allocated
288  * as a single EntitySequence. If the block of handles
289  * is contained within an unused portion of a SequenceData,
290  * the SequenceData is returned.
291  */
292  bool is_free_sequence( EntityHandle start_handle,
293  EntityID num_entities,
294  SequenceData*& sequence_data_out,
295  int values_per_ent = 0 );
296 
297  /**\brief Check if specific handle is free for allocation
298  *
299  * Check if a specific handle is not currently allocated
300  * and can be allocated with the passed value of values_per_ent.
301  * For example, the handle may not be allocated, but it may
302  * fall within an existing SequenceData. In that case, it
303  * must be possible to store the specified values_per_ent
304  * in the existing SequenceData.
305  *
306  * There are four possible return 'states' from this function:
307  *
308  * - handle is not available or cannot be allocated with specified
309  * values_per_ent. Returned error code is MB_ALREADY_ALLOCATED.
310  *
311  * - handle can be appended or prepended to an existing sequence.
312  * seq_ptr_out is set to the sequence the handle should be added to.
313  *
314  * - handle cannot be appended to an existing sequence but falls
315  * within an existing SequenceData. The caller is expected
316  * to create a new sequence referencing that SequenceData. seq_ptr_out
317  * is NULL and data_ptr_out is set to existing SequenceData.
318  *
319  * - handle does not correspond to any existing sequence or data.
320  * The caller is expected to create a new sequence and SequenceData.
321  * Both seq_ptr_out and data_ptr_out are set to NULL.
322  * block_start and block_end are set to start and end handles of the
323  * largest sequence that can be allocated and contain the input handle.
324  *
325  *\param handle The handle the caller wishes to allocate as a new entity
326  *\param seq_ptr_out Output: pointer to sequence to append or prepend to
327  * to allocate handle. end() if no such sequence.
328  *\param data_ptr_out Output: Pointer to existing SequenceData containing input
329  * handle, or NULL if no such SequenceData.
330  *\param block_start Output: Smallest possible start handle for new sequence.
331  *\param block_end Output: Largest possible end handle for new sequence.
332  */
334  iterator& seq_ptr_out,
335  SequenceData*& data_ptr_out,
336  EntityHandle& block_start,
337  EntityHandle& block_end,
338  int values_per_ent = 0 );
339 
340  EntityHandle last_free_handle( EntityHandle after_this ) const;
341 
342  /**\brief Notify that sequence was prepended to
343  *
344  * Notify of sequence modifications so we can check if
345  * sequence needs to be merged.
346  */
348 
349  /**\brief Notify that sequence was appended to
350  *
351  * Notify of sequence modifications so we can check if
352  * sequence needs to be merged.
353  */
355 
356  void get_memory_use( unsigned long long& total_entity_storage, unsigned long long& total_storage ) const;
357 
358  void get_memory_use( EntityHandle start,
360  unsigned long long& total_entity_storage,
361  unsigned long long& total_amortized_storage ) const;
362 
363  unsigned long get_sequence_count() const
364  {
365  return sequenceSet.size();
366  }
367 
368  /**\brief Get used size of SequenceData
369  *
370  * Get the sum of the size of all EntitySequences referencing
371  * a SequenceData. Used for memory use calculations.
372  */
373  EntityID get_occupied_size( const SequenceData* ) const;
374 };
375 
377 {
378  if( !lastReferenced ) // only null if empty
379  return 0;
380  else if( h >= lastReferenced->start_handle() && h <= lastReferenced->end_handle() )
381  return lastReferenced;
382  else
383  {
384  DummySequence seq( h );
385  const_iterator i = sequenceSet.find( &seq );
386  return i == end() ? 0 : ( lastReferenced = *i );
387  }
388 }
390 {
391  if( !lastReferenced ) // only null if empty
392  return 0;
393  else if( h >= lastReferenced->start_handle() && h <= lastReferenced->end_handle() )
394  return lastReferenced;
395  else
396  {
397  DummySequence seq( h );
398  iterator i = sequenceSet.find( &seq );
399  return i == end() ? 0 : ( lastReferenced = *i );
400  }
401 }
402 
404 {
405  if( !lastReferenced )
406  { // only null if empty
407  seq = 0;
408  return MB_ENTITY_NOT_FOUND;
409  }
410 
411  seq = lastReferenced;
412  if( h >= seq->start_handle() && h <= seq->end_handle() )
413  {
414  return MB_SUCCESS;
415  }
416 
417  DummySequence ds( h );
418  iterator i = sequenceSet.lower_bound( &ds );
419  if( i == end() || ( *i )->start_handle() > h )
420  {
421  seq = 0;
422  return MB_ENTITY_NOT_FOUND;
423  }
424  seq = *i;
425  lastReferenced = *i;
426  return MB_SUCCESS;
427 }
428 
430 {
431  if( !lastReferenced )
432  { // only null if empty
433  seq = 0;
434  return MB_ENTITY_NOT_FOUND;
435  }
436 
437  seq = lastReferenced;
438  if( h >= seq->start_handle() && h <= seq->end_handle() )
439  {
440  return MB_SUCCESS;
441  }
442 
443  DummySequence ds( h );
444  iterator i = sequenceSet.lower_bound( &ds );
445  if( i == end() || ( *i )->start_handle() > h )
446  {
447  seq = 0;
448  return MB_ENTITY_NOT_FOUND;
449  }
450  seq = *i;
451  lastReferenced = *i;
452  return MB_SUCCESS;
453 }
454 
456 {
457  return lastReferenced; /* only NULL if TypeSequenceManager is empty */
458 }
459 
460 inline void TypeSequenceManager::get_entities( Range& entities_out ) const
461 {
462  Range::iterator in = entities_out.begin();
463  for( const_iterator i = begin(); i != end(); ++i )
464  in = entities_out.insert( in, ( *i )->start_handle(), ( *i )->end_handle() );
465 }
466 
467 inline void TypeSequenceManager::get_entities( std::vector< EntityHandle >& entities_out ) const
468 {
469  for( const_iterator i = begin(); i != end(); ++i )
470  for( EntityHandle j = ( *i )->start_handle(); j <= ( *i )->end_handle(); ++j )
471  entities_out.push_back( j );
472 }
473 
475 {
476  EntityID count = 0;
477  for( const_iterator i = begin(); i != end(); ++i )
478  count += ( *i )->size();
479  return count;
480 }
481 
482 } // namespace moab
483 
484 #endif