Branch data Line data Source code
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 : : */
22 : : class TypeSequenceManager
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 >
31 : : class SequenceCompare
32 : : {
33 : : public:
34 : 7082764 : inline bool operator()( const T* a, const T* b ) const
35 : : {
36 : 7082764 : return a->end_handle() < b->start_handle();
37 : : }
38 : : };
39 : : /**\brief Dummy EntitySequence for use in querying set container */
40 [ - + ]: 4336310 : class DummySequence : public EntitySequence
41 : : {
42 : : public:
43 : 4336310 : DummySequence( EntityHandle start ) : EntitySequence( start ) {}
44 : :
45 : 0 : EntitySequence* split( EntityHandle )
46 : : {
47 : 0 : return 0;
48 : : }
49 : 0 : SequenceData* create_data_subset( EntityHandle, EntityHandle ) const
50 : : {
51 : 0 : return 0;
52 : : }
53 : :
54 : 0 : void get_const_memory_use( unsigned long& a, unsigned long& b ) const
55 : : {
56 : 0 : a = b = 0;
57 : 0 : }
58 : 0 : unsigned long get_per_entity_memory_use( EntityHandle, EntityHandle ) const
59 : : {
60 : 0 : 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 : :
75 : 3024 : struct SequenceDataPtr
76 : : {
77 : : private:
78 : : friend class TypeSequenceManager;
79 : : TypeSequenceManager::iterator firstSequence;
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 : :
91 : : void append_memory_use( EntityHandle first, EntityHandle last, const SequenceData* data,
92 : : unsigned long long& entity_storage, unsigned long long& total_storage ) const;
93 : :
94 : : // check if sequence at passed iterator should be merged with
95 : : // the subsequent sequence, and if so merge them retaining i.
96 : : ErrorCode check_merge_next( iterator i );
97 : : // check if sequence at passed iterator should be merged with
98 : : // the previous sequence, and if so merge them retaining i.
99 : : ErrorCode check_merge_prev( iterator i );
100 : : // common code for check_merge_next and check_merge_prev
101 : : ErrorCode merge_internal( iterator keep, iterator dead );
102 : :
103 : : #ifndef NDEBUG
104 : : bool check_valid_data( const EntitySequence* seq ) const;
105 : : #endif
106 : :
107 : : public:
108 : : /**\brief Add an entity sequence
109 : : *
110 : : * Take ownership of passed EntitySequence, and update relevant
111 : : * data structures. Sequence may not overlap with any existing
112 : : * sequence.
113 : : *
114 : : * NOTE: Sequence may be merged with other, existing sequences.
115 : : * This function will always ensure that the passed
116 : : * EntitySequence* is the remaining one, but the passed
117 : : * sequence may have modified start and end handles.
118 : : */
119 : : ErrorCode insert_sequence( EntitySequence* seq_ptr );
120 : :
121 : : /**\brief Remove an entity sequence.
122 : : *
123 : : * Give up ownership of specified EntitySequence, and remove it
124 : : * from all internal data structures. Passes back bool flag to
125 : : * notify caller that ownership of the corresponding SequenceData
126 : : * is also relinquished because the specified EntitySequence is
127 : : * the last one referencing it.
128 : : */
129 : : ErrorCode remove_sequence( const EntitySequence* seq_ptr, bool& is_last_user_of_sequence_data );
130 : :
131 : : /**\brief Replace sequence or subset of sequence
132 : : *
133 : : * Replace one sequence or a subset of one sequence with
134 : : * another sequence. With fail if a) the existing
135 : : * sequence is not a subset of an existing sequence or
136 : : * b) existing sequence shares a SequenceData with the
137 : : * passed sequence.
138 : : *
139 : : * This method is provided for use when changing the
140 : : * number of nodes in elements.
141 : : */
142 : : ErrorCode replace_subsequence( EntitySequence* seq_ptr, const int* tag_sizes, int num_tag_sizes );
143 : :
144 [ + - ]: 5284 : TypeSequenceManager() : lastReferenced( 0 ) {}
145 : :
146 : : ~TypeSequenceManager();
147 : :
148 : : /**\brief Start of EntitySequence set */
149 : 59937 : const_iterator begin() const
150 : : {
151 : 59937 : return sequenceSet.begin();
152 : : }
153 : 22193 : iterator begin()
154 : : {
155 : 22193 : return sequenceSet.begin();
156 : : }
157 : :
158 : : /**\brief End of EntitySequence set */
159 : 8217614 : const_iterator end() const
160 : : {
161 : 8217614 : return sequenceSet.end();
162 : : }
163 : 7944428 : iterator end()
164 : : {
165 : 7944428 : return sequenceSet.end();
166 : : }
167 : :
168 : : /**\brief Return EntitySequence for specified handle.
169 : : *
170 : : * Return EntitySequence for specified handle, or if
171 : : * no such sequence, the next one. Returns end() if
172 : : * all sequences have ranges less than specified handle.
173 : : */
174 : 1300157 : const_iterator lower_bound( EntityHandle h ) const
175 : : {
176 [ + - ]: 1300157 : DummySequence f( h );
177 [ + - ]: 1300157 : return sequenceSet.lower_bound( &f );
178 : : }
179 : 36176 : iterator lower_bound( EntityHandle h )
180 : : {
181 [ + - ]: 36176 : DummySequence f( h );
182 [ + - ]: 36176 : return sequenceSet.lower_bound( &f );
183 : : }
184 : :
185 : : /**\brief Return EntitySequence after specified handle.
186 : : *
187 : : * Return EntitySequence with smallest start handle
188 : : * that is greater than input handle. Returns end() if
189 : : * all sequences have start handles less than specified
190 : : * handle.
191 : : */
192 : 19 : const_iterator upper_bound( EntityHandle h ) const
193 : : {
194 [ + - ]: 19 : DummySequence f( h );
195 [ + - ]: 19 : return sequenceSet.upper_bound( &f );
196 : : }
197 : :
198 : : /**\brief Get EntitySequence for handle.
199 : : *\return EntitySequence for handle, or NULL if no such sequence.
200 : : */
201 : : inline EntitySequence* find( EntityHandle h ) const;
202 : : inline EntitySequence* find( EntityHandle h );
203 : : inline ErrorCode find( EntityHandle h, EntitySequence*& );
204 : : inline ErrorCode find( EntityHandle h, const EntitySequence*& ) const;
205 : : inline const EntitySequence* get_last_accessed() const;
206 : :
207 : : /**\brief Get handles for all entities in all sequences. */
208 : : inline void get_entities( Range& entities_out ) const;
209 : :
210 : : /**\brief Get handles for all entities in all sequences. */
211 : : inline void get_entities( std::vector< EntityHandle >& entities_out ) const;
212 : :
213 : : /**\brief Get number of entities represented by all sequences. */
214 : : inline EntityID get_number_entities() const;
215 : :
216 : : ErrorCode check_valid_handles( Error* error_handler, EntityHandle first, EntityHandle last ) const;
217 : :
218 : : /**\brief Remove entities
219 : : *
220 : : * Update EntitySequence data as necessary to "delete" the
221 : : * specified entities (e.g. split sequences, delete sequences,
222 : : * free SequenceData instances, etc.)
223 : : */
224 : : ErrorCode erase( Error* error_handler, EntityHandle first, EntityHandle last );
225 : : ErrorCode erase( Error* error_handler, EntityHandle entity );
226 : :
227 : : /**\brief Test if this instance contains no sequences */
228 : 33561 : bool empty() const
229 : : {
230 : 33561 : return 0 == lastReferenced;
231 : : }
232 : :
233 : : /**\brief Allocate a handle in an existing entity sequence
234 : : *
235 : : * Find an existing entity sequence to which a new handle can
236 : : * be prepended or appended. The 'append_out' flag indicates
237 : : * to the caller that the new handle should be appended to the
238 : : * returned sequence if true, and prepended if false.
239 : : *
240 : : * If no appropriate EntitySequence is available, NULL will
241 : : * be returned. The caller will typically then want to use
242 : : * find_free_sequence() to find appropriate values for the
243 : : * creation of a new EntitySequence.
244 : : */
245 : : iterator find_free_handle( EntityHandle min_start_handle, EntityHandle max_end_handle, bool& append_out,
246 : : int values_per_ent = 0 );
247 : :
248 : : /**\brief Find block of free handles
249 : : *
250 : : * Find block of free handles, such that block does not
251 : : * overlap any existing EntitySequence.
252 : : *\return First handle of block, or zero if no block found.
253 : : */
254 : : EntityHandle find_free_block( EntityID num_entities, EntityHandle min_start_handle, EntityHandle max_end_handle );
255 : :
256 : : /**\brief Find block of free handles
257 : : *
258 : : * Find block of free handles, such that block a) does not
259 : : * overlap any existing EntitySequence and b) is either
260 : : * entirely within one existing SequenceData or does not
261 : : * overlap any SequenceData.
262 : : *\param num_entities Size of handle block.
263 : : *\param min_start_handle Block may not contain any handle less than this.
264 : : *\param max_end_handle Block may not contain any handle greater than this.
265 : : *\param sequence_data_out If block is within an unused portion of an
266 : : * existing SequenceData, a pointer to that
267 : : * SequenceData. NULL otherwise.
268 : : *\return values_per_ent Matched against EntitySequence::values_per_entity.
269 : : * An existing SequenceData will not be returned if
270 : : * the existing EntitySequences using have a different
271 : : * value than the passed one.
272 : : */
273 : : EntityHandle find_free_sequence( EntityID num_entities, EntityHandle min_start_handle, EntityHandle max_end_handle,
274 : : SequenceData*& sequence_data_out, EntityID& sequence_data_size,
275 : : int values_per_ent = 0 );
276 : :
277 : : /**\brief Check if block of handles is free.
278 : : *
279 : : * Check if block of handles is free and can be allocated
280 : : * as a single EntitySequence. If the block of handles
281 : : * is contained within an unused portion of a SequenceData,
282 : : * the SequenceData is returned.
283 : : */
284 : : bool is_free_sequence( EntityHandle start_handle, EntityID num_entities, SequenceData*& sequence_data_out,
285 : : int values_per_ent = 0 );
286 : :
287 : : /**\brief Check if specific handle is free for allocation
288 : : *
289 : : * Check if a specific handle is not currently allocated
290 : : * and can be allocated with the passed value of values_per_ent.
291 : : * For example, the handle may not be allocated, but it may
292 : : * fall within an existing SequenceData. In that case, it
293 : : * must be possible to store the specified values_per_ent
294 : : * in the existing SequenceData.
295 : : *
296 : : * There are four possible return 'states' from this function:
297 : : *
298 : : * - handle is not available or cannot be allocated with specified
299 : : * values_per_ent. Returned error code is MB_ALREADY_ALLOCATED.
300 : : *
301 : : * - handle can be appended or prepended to an existing sequence.
302 : : * seq_ptr_out is set to the sequence the handle should be added to.
303 : : *
304 : : * - handle cannot be appended to an existing sequence but falls
305 : : * within an existing SequenceData. The caller is expected
306 : : * to create a new sequence referencing that SequenceData. seq_ptr_out
307 : : * is NULL and data_ptr_out is set to existing SequenceData.
308 : : *
309 : : * - handle does not correspond to any existing sequence or data.
310 : : * The caller is expected to create a new sequence and SequenceData.
311 : : * Both seq_ptr_out and data_ptr_out are set to NULL.
312 : : * block_start and block_end are set to start and end handles of the
313 : : * largest sequence that can be allocated and contain the input handle.
314 : : *
315 : : *\param handle The handle the caller wishes to allocate as a new entity
316 : : *\param seq_ptr_out Output: pointer to sequence to append or prepend to
317 : : * to allocate handle. end() if no such sequence.
318 : : *\param data_ptr_out Output: Pointer to existing SequenceData containing input
319 : : * handle, or NULL if no such SequenceData.
320 : : *\param block_start Output: Smallest possible start handle for new sequence.
321 : : *\param block_end Output: Largest possible end handle for new sequence.
322 : : */
323 : : ErrorCode is_free_handle( EntityHandle handle, iterator& seq_ptr_out, SequenceData*& data_ptr_out,
324 : : EntityHandle& block_start, EntityHandle& block_end, int values_per_ent = 0 );
325 : :
326 : : EntityHandle last_free_handle( EntityHandle after_this ) const;
327 : :
328 : : /**\brief Notify that sequence was prepended to
329 : : *
330 : : * Notify of sequence modifications so we can check if
331 : : * sequence needs to be merged.
332 : : */
333 : : ErrorCode notify_prepended( iterator seq );
334 : :
335 : : /**\brief Notify that sequence was appended to
336 : : *
337 : : * Notify of sequence modifications so we can check if
338 : : * sequence needs to be merged.
339 : : */
340 : : ErrorCode notify_appended( iterator seq );
341 : :
342 : : void get_memory_use( unsigned long long& total_entity_storage, unsigned long long& total_storage ) const;
343 : :
344 : : void get_memory_use( EntityHandle start, EntityHandle end, unsigned long long& total_entity_storage,
345 : : unsigned long long& total_amortized_storage ) const;
346 : :
347 : : unsigned long get_sequence_count() const
348 : : {
349 : : return sequenceSet.size();
350 : : }
351 : :
352 : : /**\brief Get used size of SequenceData
353 : : *
354 : : * Get the sum of the size of all EntitySequences referencing
355 : : * a SequenceData. Used for memory use calculations.
356 : : */
357 : : EntityID get_occupied_size( const SequenceData* ) const;
358 : : };
359 : :
360 : 33178 : inline EntitySequence* TypeSequenceManager::find( EntityHandle h ) const
361 : : {
362 [ - + ]: 33178 : if( !lastReferenced ) // only null if empty
363 : 0 : return 0;
364 [ + + ][ + + ]: 33178 : else if( h >= lastReferenced->start_handle() && h <= lastReferenced->end_handle() )
[ + + ]
365 : 13578 : return lastReferenced;
366 : : else
367 : : {
368 [ + - ]: 19600 : DummySequence seq( h );
369 [ + - ]: 19600 : const_iterator i = sequenceSet.find( &seq );
370 [ + - ][ + - ]: 33178 : return i == end() ? 0 : ( lastReferenced = *i );
[ - + ][ + - ]
371 : : }
372 : : }
373 : 30137 : inline EntitySequence* TypeSequenceManager::find( EntityHandle h )
374 : : {
375 [ + + ]: 30137 : if( !lastReferenced ) // only null if empty
376 : 5 : return 0;
377 [ + + ][ + + ]: 30132 : else if( h >= lastReferenced->start_handle() && h <= lastReferenced->end_handle() )
[ + + ]
378 : 28212 : return lastReferenced;
379 : : else
380 : : {
381 [ + - ]: 1920 : DummySequence seq( h );
382 [ + - ]: 1920 : iterator i = sequenceSet.find( &seq );
383 [ + - ][ + - ]: 30137 : return i == end() ? 0 : ( lastReferenced = *i );
[ + + ][ + - ]
384 : : }
385 : : }
386 : :
387 : 7298435 : inline ErrorCode TypeSequenceManager::find( EntityHandle h, EntitySequence*& seq )
388 : : {
389 [ + + ]: 7298435 : if( !lastReferenced )
390 : : { // only null if empty
391 : 7 : seq = 0;
392 : 7 : return MB_ENTITY_NOT_FOUND;
393 : : }
394 [ + + ][ + + ]: 7298428 : else if( h >= lastReferenced->start_handle() && h <= lastReferenced->end_handle() )
[ + + ]
395 : : {
396 : 7113340 : seq = lastReferenced;
397 : 7113340 : return MB_SUCCESS;
398 : : }
399 : : else
400 : : {
401 [ + - ]: 185088 : DummySequence ds( h );
402 [ + - ]: 185088 : iterator i = sequenceSet.lower_bound( &ds );
403 [ + - ][ + - ]: 185088 : if( i == end() || ( *i )->start_handle() > h )
[ + + ][ + - ]
[ + - ][ + + ]
[ + - ]
[ + + # # ]
404 : : {
405 : 111 : seq = 0;
406 : 111 : return MB_ENTITY_NOT_FOUND;
407 : : }
408 : : else
409 : : {
410 [ + - ]: 184977 : seq = lastReferenced = *i;
411 : 184977 : return MB_SUCCESS;
412 : 7298435 : }
413 : : }
414 : : }
415 : :
416 : 54166632 : inline ErrorCode TypeSequenceManager::find( EntityHandle h, const EntitySequence*& seq ) const
417 : : {
418 [ + + ]: 54166632 : if( !lastReferenced )
419 : : { // only null if empty
420 : 51 : seq = 0;
421 : 51 : return MB_ENTITY_NOT_FOUND;
422 : : }
423 [ + + ][ + + ]: 54166581 : else if( h >= lastReferenced->start_handle() && h <= lastReferenced->end_handle() )
[ + + ]
424 : : {
425 : 53541386 : seq = lastReferenced;
426 : 53541386 : return MB_SUCCESS;
427 : : }
428 : : else
429 : : {
430 [ + - ]: 625195 : DummySequence ds( h );
431 [ + - ]: 625195 : const_iterator i = sequenceSet.lower_bound( &ds );
432 [ + - ][ + - ]: 625195 : if( i == end() || ( *i )->start_handle() > h )
[ + + ][ + - ]
[ + - ][ + + ]
[ + - ]
[ + + # # ]
433 : : {
434 : 22602 : seq = 0;
435 : 22602 : return MB_ENTITY_NOT_FOUND;
436 : : }
437 : : else
438 : : {
439 [ + - ]: 602593 : seq = lastReferenced = *i;
440 : 602593 : return MB_SUCCESS;
441 : 54166632 : }
442 : : }
443 : : }
444 : :
445 : 5892279 : inline const EntitySequence* TypeSequenceManager::get_last_accessed() const
446 : : {
447 : 5892279 : return lastReferenced; /* only NULL if TypeSequenceManager is empty */
448 : : }
449 : :
450 : 22920 : inline void TypeSequenceManager::get_entities( Range& entities_out ) const
451 : : {
452 [ + - ]: 22920 : Range::iterator in = entities_out.begin();
453 [ + - ][ + - ]: 47290 : for( const_iterator i = begin(); i != end(); ++i )
[ + - ][ + - ]
[ + + ]
454 [ + - ][ + - ]: 24370 : in = entities_out.insert( in, ( *i )->start_handle(), ( *i )->end_handle() );
[ + - ][ + - ]
[ + - ]
455 : 22920 : }
456 : :
457 : 153 : inline void TypeSequenceManager::get_entities( std::vector< EntityHandle >& entities_out ) const
458 : : {
459 [ + - ][ + - ]: 231 : for( const_iterator i = begin(); i != end(); ++i )
[ + - ][ + - ]
[ + + ]
460 [ + - ][ + - ]: 41776 : for( EntityHandle j = ( *i )->start_handle(); j <= ( *i )->end_handle(); ++j )
[ + - ][ + - ]
[ + + ]
461 [ + - ]: 41698 : entities_out.push_back( j );
462 : 153 : }
463 : :
464 : 2388 : inline EntityID TypeSequenceManager::get_number_entities() const
465 : : {
466 : 2388 : EntityID count = 0;
467 [ + - ][ + - ]: 3433 : for( const_iterator i = begin(); i != end(); ++i )
[ + - ][ + - ]
[ + + ]
468 [ + - ][ + - ]: 1045 : count += ( *i )->size();
469 : 2388 : return count;
470 : : }
471 : :
472 : : } // namespace moab
473 : :
474 : : #endif
|
