Sierra Toolkit  Version of the Day
BucketRepository.cpp
1 /*------------------------------------------------------------------------*/
2 /* Copyright 2010 Sandia Corporation. */
3 /* Under terms of Contract DE-AC04-94AL85000, there is a non-exclusive */
4 /* license for use of this work by or on behalf of the U.S. Government. */
5 /* Export of this program may require a license from the */
6 /* United States Government. */
7 /*------------------------------------------------------------------------*/
8 
9 #include <sstream>
10 #include <cstdlib>
11 #include <stdexcept>
12 
13 #include <stk_mesh/baseImpl/BucketRepository.hpp>
14 #include <stk_mesh/baseImpl/EntityRepository.hpp>
15 #include <stk_mesh/base/BulkData.hpp>
16 #include <stk_mesh/base/Bucket.hpp>
17 #include <stk_mesh/base/Trace.hpp>
18 
19 namespace stk_classic {
20 namespace mesh {
21 namespace impl {
22 
23 //----------------------------------------------------------------------
24 
25 
26 BucketRepository::BucketRepository(
27  BulkData & mesh,
28  unsigned bucket_capacity,
29  unsigned entity_rank_count,
30  EntityRepository & entity_repo
31  )
32  :m_mesh(mesh),
33  m_bucket_capacity(bucket_capacity),
34  m_buckets(entity_rank_count),
35  m_nil_bucket(NULL),
36  m_entity_repo(entity_repo)
37 {
38 }
39 
40 
41 BucketRepository::~BucketRepository()
42 {
43  // Destroy buckets, which were *not* allocated by the set.
44 
45  try {
46  for ( std::vector< std::vector<Bucket*> >::iterator
47  i = m_buckets.end() ; i != m_buckets.begin() ; ) {
48  try {
49  std::vector<Bucket*> & kset = *--i ;
50 
51  while ( ! kset.empty() ) {
52  try { destroy_bucket( kset.back() ); } catch(...) {}
53  kset.pop_back();
54  }
55  kset.clear();
56  } catch(...) {}
57  }
58  m_buckets.clear();
59  } catch(...) {}
60 
61  try { if ( m_nil_bucket ) destroy_bucket( m_nil_bucket ); } catch(...) {}
62 }
63 
64 
65 //----------------------------------------------------------------------
66 // The current 'last' bucket in a family is to be deleted.
67 // The previous 'last' bucket becomes the new 'last' bucket in the family.
68 
69 void BucketRepository::destroy_bucket( const unsigned & entity_rank , Bucket * bucket_to_be_deleted )
70 {
71  TraceIfWatching("stk_classic::mesh::impl::BucketRepository::destroy_bucket", LOG_BUCKET, bucket_to_be_deleted);
72 
73  ThrowRequireMsg(MetaData::get(m_mesh).check_rank(entity_rank),
74  "Entity rank " << entity_rank << " is invalid");
75 
76  std::vector<Bucket *> & bucket_set = m_buckets[entity_rank];
77 
78  // Get the first bucket in the same family as the bucket being deleted
79  Bucket * const first = bucket_to_be_deleted->m_bucketImpl.first_bucket_in_family();
80 
81  ThrowRequireMsg( bucket_to_be_deleted->equivalent(*first), "Logic error - bucket_to_be_deleted is not in same family as first_bucket_in_family");
82  ThrowRequireMsg( first->equivalent(*bucket_to_be_deleted), "Logic error - first_bucket_in_family is not in same family as bucket_to_be_deleted");
83 
84  ThrowRequireMsg( bucket_to_be_deleted->size() == 0,
85  "Destroying non-empty bucket " << *(bucket_to_be_deleted->key()) );
86 
87  ThrowRequireMsg( bucket_to_be_deleted == first->m_bucketImpl.get_bucket_family_pointer(),
88  "Destroying bucket family") ;
89 
90  std::vector<Bucket*>::iterator ik = lower_bound(bucket_set, bucket_to_be_deleted->key());
91  ThrowRequireMsg( ik != bucket_set.end() && bucket_to_be_deleted == *ik,
92  "Bucket not found in bucket set for entity rank " << entity_rank );
93 
94  ik = bucket_set.erase( ik );
95 
96  if ( first != bucket_to_be_deleted ) {
97 
98  ThrowRequireMsg( ik != bucket_set.begin(),
99  "Where did first bucket go?" );
100 
101  first->m_bucketImpl.set_last_bucket_in_family( *--ik );
102 
103  ThrowRequireMsg ( first->m_bucketImpl.get_bucket_family_pointer()->size() != 0,
104  "TODO: Explain" );
105  }
106 
107  destroy_bucket( bucket_to_be_deleted );
108 }
109 
110 //----------------------------------------------------------------------
111 void BucketRepository::destroy_bucket( Bucket * bucket )
112 {
113  TraceIfWatching("stk_classic::mesh::impl::BucketRepository::destroy_bucket", LOG_BUCKET, bucket);
114 
115  delete bucket;
116 }
117 
118 //
119 //----------------------------------------------------------------------
120 // The input part ordinals are complete and contain all supersets.
121 void
122 BucketRepository::declare_nil_bucket()
123 {
124  TraceIf("stk_classic::mesh::impl::BucketRepository::declare_nil_bucket", LOG_BUCKET);
125 
126  if (m_nil_bucket == NULL) {
127  // Key layout:
128  // { part_count + 1 , { part_ordinals } , family_count }
129 
130  std::vector<unsigned> new_key(2);
131  new_key[0] = 1 ; // part_count + 1
132  new_key[1] = 0 ; // family_count
133 
134  Bucket * bucket =
135  new Bucket(m_mesh, InvalidEntityRank, new_key, 0);
136 
137  bucket->m_bucketImpl.set_bucket_family_pointer( bucket );
138 
139  //----------------------------------
140 
141  m_nil_bucket = bucket;
142  }
143 }
144 
145 
168 //----------------------------------------------------------------------
169 // The input part ordinals are complete and contain all supersets.
170 Bucket *
171 BucketRepository::declare_bucket(
172  const unsigned arg_entity_rank ,
173  const unsigned part_count ,
174  const unsigned part_ord[] ,
175  const std::vector< FieldBase * > & field_set
176  )
177 {
178  enum { KEY_TMP_BUFFER_SIZE = 64 };
179 
180  TraceIf("stk_classic::mesh::impl::BucketRepository::declare_bucket", LOG_BUCKET);
181 
182  const unsigned max = static_cast<unsigned>(-1);
183 
184  ThrowRequireMsg(MetaData::get(m_mesh).check_rank(arg_entity_rank),
185  "Entity rank " << arg_entity_rank << " is invalid");
186 
187  ThrowRequireMsg( !m_buckets.empty(),
188  "m_buckets is empty! Did you forget to initialize MetaData before creating BulkData?");
189  std::vector<Bucket *> & bucket_set = m_buckets[ arg_entity_rank ];
190 
191 
192  std::vector<unsigned> key(2+part_count) ;
193 
194  //----------------------------------
195  // Key layout:
196  // { part_count + 1 , { part_ordinals } , family_count }
197  // Thus family_count = key[ key[0] ]
198  //
199  // for upper bound search use the maximum key.
200 
201  key[0] = part_count+1;
202  key[ key[0] ] = max ;
203 
204  {
205  for ( unsigned i = 0 ; i < part_count ; ++i ) { key[i+1] = part_ord[i] ; }
206  }
207 
208  //----------------------------------
209  // Bucket family has all of the same parts.
210  // Look for the last bucket in this family:
211 
212  const std::vector<Bucket*>::iterator ik = lower_bound( bucket_set , &key[0] );
213 
214  //----------------------------------
215  // If a member of the bucket family has space, it is the last one
216  // since buckets are kept packed.
217  const bool bucket_family_exists =
218  ik != bucket_set.begin() && bucket_part_equal( ik[-1]->key() , &key[0] );
219 
220  Bucket * const last_bucket = bucket_family_exists ? ik[-1] : NULL ;
221 
222  Bucket * bucket = NULL ;
223 
224  if ( last_bucket == NULL ) { // First bucket in this family
225  key[ key[0] ] = 0 ; // Set the key's family count to zero
226  }
227  else { // Last bucket present, can it hold one more entity?
228 
229  ThrowRequireMsg( last_bucket->size() != 0,
230  "Last bucket should not be empty.");
231 
232  //field_map = last_bucket->m_bucketImpl.get_field_map();
233 
234  const unsigned last_count = last_bucket->key()[ key[0] ];
235 
236  const unsigned cap = last_bucket->capacity();
237 
238  if ( last_bucket->size() < cap ) {
239  bucket = last_bucket ;
240  }
241  else if ( last_count < max ) {
242  key[ key[0] ] = 1 + last_count ; // Increment the key's family count.
243  }
244  else {
245  // ERROR insane number of buckets!
246  ThrowRequireMsg( false, "Insanely large number of buckets" );
247  }
248  }
249 
250 
251  //----------------------------------
252 
253  //Required bucket does not exist
254  if ( NULL == bucket )
255  {
256  bucket = new Bucket( m_mesh, arg_entity_rank, key, m_bucket_capacity);
257 
258  Bucket * first_bucket = last_bucket ? last_bucket->m_bucketImpl.first_bucket_in_family() : bucket ;
259 
260  bucket->m_bucketImpl.set_first_bucket_in_family(first_bucket); // Family members point to first bucket
261 
262  first_bucket->m_bucketImpl.set_last_bucket_in_family(bucket); // First bucket points to new last bucket
263 
264  bucket_set.insert( ik , bucket );
265  }
266 
267  //----------------------------------
268 
269  ThrowRequireMsg( bucket->equivalent(*bucket->m_bucketImpl.first_bucket_in_family()), "Logic error - new bucket is not in same family as first_bucket_in_family");
270  ThrowRequireMsg( bucket->m_bucketImpl.first_bucket_in_family()->equivalent(*bucket), "Logic error - first_bucket_in_family is not in same family as new bucket");
271 
272  return bucket ;
273 }
274 
275 //----------------------------------------------------------------------
276 
277 void BucketRepository::initialize_fields( Bucket & k_dst , unsigned i_dst )
278 {
279  TraceIfWatching("stk_classic::mesh::impl::BucketRepository::initialize_fields", LOG_BUCKET, &k_dst);
280  k_dst.m_bucketImpl.initialize_fields(i_dst);
281 }
282 
283 //----------------------------------------------------------------------
284 
285 void BucketRepository::update_field_data_states() const
286 {
287  TraceIf("stk_classic::mesh::impl::BucketRepository::update_field_data_states", LOG_BUCKET);
288 
289  for ( std::vector< std::vector<Bucket*> >::const_iterator
290  i = m_buckets.begin() ; i != m_buckets.end() ; ++i ) {
291 
292  const std::vector<Bucket*> & kset = *i ;
293 
294  for ( std::vector<Bucket*>::const_iterator
295  ik = kset.begin() ; ik != kset.end() ; ++ik ) {
296  (*ik)->m_bucketImpl.update_state();
297  }
298  }
299 }
300 
301 
302 //----------------------------------------------------------------------
303 
304 
305 void BucketRepository::internal_sort_bucket_entities()
306 {
307  TraceIf("stk_classic::mesh::impl::BucketRepository::internal_sort_bucket_entities", LOG_BUCKET);
308 
309  for ( EntityRank entity_rank = 0 ;
310  entity_rank < m_buckets.size() ; ++entity_rank ) {
311 
312  std::vector<Bucket*> & buckets = m_buckets[ entity_rank ];
313 
314  size_t bk = 0 ; // Offset to first bucket of the family
315  size_t ek = 0 ; // Offset to end bucket of the family
316 
317  for ( ; bk < buckets.size() ; bk = ek ) {
318  Bucket * b_scratch = NULL ;
319  Bucket * ik_vacant = buckets[bk]->m_bucketImpl.last_bucket_in_family();
320  unsigned ie_vacant = ik_vacant->size();
321 
322  if ( ik_vacant->capacity() <= ie_vacant ) {
323  // Have to create a bucket just for the scratch space...
324  const unsigned * const bucket_key = buckets[bk]->key() ;
325  const unsigned part_count = bucket_key[0] - 1 ;
326  const unsigned * const part_ord = bucket_key + 1 ;
327 
328  b_scratch = declare_bucket( entity_rank ,
329  part_count , part_ord ,
330  MetaData::get(m_mesh).get_fields() );
331 
332  ik_vacant = b_scratch ;
333  ie_vacant = 0 ;
334  }
335 
336  ik_vacant->m_bucketImpl.replace_entity( ie_vacant , NULL ) ;
337 
338  // Determine offset to the end bucket in this family:
339  while ( ek < buckets.size() && ik_vacant != buckets[ek] ) { ++ek ; }
340  if (ek < buckets.size()) ++ek ;
341 
342  unsigned count = 0 ;
343  for ( size_t ik = bk ; ik != ek ; ++ik ) {
344  count += buckets[ik]->size();
345  }
346 
347  std::vector<Entity*> entities( count );
348 
349  std::vector<Entity*>::iterator j = entities.begin();
350 
351  for ( size_t ik = bk ; ik != ek ; ++ik ) {
352  Bucket & b = * buckets[ik];
353  const unsigned n = b.size();
354  for ( unsigned i = 0 ; i < n ; ++i , ++j ) {
355  *j = & b[i] ;
356  }
357  }
358 
359  std::sort( entities.begin() , entities.end() , EntityLess() );
360 
361  j = entities.begin();
362 
363  bool change_this_family = false ;
364 
365  for ( size_t ik = bk ; ik != ek ; ++ik ) {
366  Bucket & b = * buckets[ik];
367  const unsigned n = b.size();
368  for ( unsigned i = 0 ; i < n ; ++i , ++j ) {
369  Entity * const current = & b[i] ;
370 
371  if ( current != *j ) {
372 
373  if ( current ) {
374  // Move current entity to the vacant spot
375  copy_fields( *ik_vacant , ie_vacant , b, i );
376  m_entity_repo.change_entity_bucket(*ik_vacant, *current, ie_vacant);
377  ik_vacant->m_bucketImpl.replace_entity( ie_vacant , current ) ;
378  }
379 
380  // Set the vacant spot to where the required entity is now.
381  ik_vacant = & ((*j)->bucket()) ;
382  ie_vacant = (*j)->bucket_ordinal() ;
383  ik_vacant->m_bucketImpl.replace_entity( ie_vacant , NULL ) ;
384 
385  // Move required entity to the required spot
386  copy_fields( b, i, *ik_vacant , ie_vacant );
387  m_entity_repo.change_entity_bucket( b, **j, i);
388  b.m_bucketImpl.replace_entity( i, *j );
389 
390  change_this_family = true ;
391  }
392 
393  // Once a change has occured then need to propagate the
394  // relocation for the remainder of the family.
395  // This allows the propagation to be performed once per
396  // entity as opposed to both times the entity is moved.
397 
398  if ( change_this_family ) { internal_propagate_relocation( **j ); }
399  }
400  }
401 
402  if ( b_scratch ) {
403  // Created a last bucket, now have to destroy it.
404  destroy_bucket( entity_rank , b_scratch );
405  --ek ;
406  }
407  }
408  }
409 }
410 
411 void BucketRepository::optimize_buckets()
412 {
413  TraceIf("stk_classic::mesh::impl::BucketRepository::optimize_buckets", LOG_BUCKET);
414 
415  for ( EntityRank entity_rank = 0 ;
416  entity_rank < m_buckets.size() ; ++entity_rank )
417  {
418 
419  std::vector<Bucket*> & buckets = m_buckets[ entity_rank ];
420 
421  std::vector<Bucket*> tmp_buckets;
422 
423  size_t begin_family = 0 ; // Offset to first bucket of the family
424  size_t end_family = 0 ; // Offset to end bucket of the family
425 
426  //loop over families
427  for ( ; begin_family < buckets.size() ; begin_family = end_family ) {
428  Bucket * last_bucket_in_family = buckets[begin_family]->m_bucketImpl.last_bucket_in_family();
429 
430  // Determine offset to the end bucket in this family:
431  while ( end_family < buckets.size() && last_bucket_in_family != buckets[end_family] ) { ++end_family ; }
432  if (end_family < buckets.size()) ++end_family ; //increment past the end
433 
434  //if compressed and sorted go to the next family
435  const bool is_compressed = (end_family-begin_family == 1)
436  && (buckets[begin_family]->size() == buckets[begin_family]->capacity());
437  if (is_compressed) {
438  const Bucket & b = *buckets[begin_family];
439  bool is_sorted = true;
440  for (size_t i=0, end=b.size()-1; i<end && is_sorted; ++i)
441  {
442  if(b[i].key() >= b[i+1].key()) is_sorted = false;
443  }
444  if (is_sorted) {
445  tmp_buckets.push_back(buckets[begin_family]);
446  continue;
447  }
448  }
449 
450  std::vector<unsigned> new_key = buckets[begin_family]->m_bucketImpl.key_vector();
451  //index of bucket in family
452  new_key[ new_key[0] ] = 0;
453 
454  unsigned new_capacity = 0 ;
455  for ( size_t i = begin_family ; i != end_family ; ++i ) {
456  new_capacity += buckets[i]->m_bucketImpl.size();
457  }
458 
459  std::vector<Entity*> entities;
460  entities.reserve(new_capacity);
461 
462  for ( size_t i = begin_family ; i != end_family ; ++i ) {
463  Bucket& b = *buckets[i];
464  for(size_t j=0; j<b.size(); ++j) {
465  entities.push_back(&b[j]);
466  }
467  }
468 
469  std::sort( entities.begin(), entities.end(), EntityLess() );
470 
471  Bucket * new_bucket = new Bucket( m_mesh,
472  entity_rank,
473  new_key,
474  new_capacity
475  );
476 
477  new_bucket->m_bucketImpl.set_first_bucket_in_family(new_bucket); // Family members point to first bucket
478  new_bucket->m_bucketImpl.set_last_bucket_in_family(new_bucket); // First bucket points to new last bucket
479 
480  tmp_buckets.push_back(new_bucket);
481 
482  for(size_t new_ordinal=0; new_ordinal<entities.size(); ++new_ordinal) {
483  //increase size of the new_bucket
484  new_bucket->m_bucketImpl.increment_size();
485 
486  Entity & entity = *entities[new_ordinal];
487  Bucket& old_bucket = entity.bucket();
488  unsigned old_ordinal = entity.bucket_ordinal();
489 
490  //copy field data from old to new
491  copy_fields( *new_bucket, new_ordinal, old_bucket, old_ordinal);
492  m_entity_repo.change_entity_bucket( *new_bucket, entity, new_ordinal);
493  new_bucket->m_bucketImpl.replace_entity( new_ordinal , &entity ) ;
494  internal_propagate_relocation(entity);
495  }
496 
497  for (size_t ik = begin_family; ik != end_family; ++ik) {
498  delete buckets[ik];
499  buckets[ik] = NULL;
500  }
501  }
502 
503  buckets.swap(tmp_buckets);
504  }
505 }
506 //----------------------------------------------------------------------
507 
508 void BucketRepository::remove_entity( Bucket * k , unsigned i )
509 {
510  TraceIfWatching("stk_classic::mesh::impl::BucketRepository::remove_entity", LOG_BUCKET, k);
511 
512  ThrowRequireMsg( k != m_nil_bucket, "Cannot remove entity from nil_bucket" );
513 
514  const EntityRank entity_rank = k->entity_rank();
515 
516  // Last bucket in the family of buckets with the same parts.
517  // The last bucket is the only non-full bucket in the family.
518 
519  Bucket * const last = k->m_bucketImpl.last_bucket_in_family();
520 
521  ThrowRequireMsg( last->equivalent(*k), "Logic error - last bucket in family not equivalent to bucket");
522  ThrowRequireMsg( k->equivalent(*last), "Logic error - bucket not equivalent to last bucket in family");
523 
524  // Fill in the gap if it is not the last entity being removed
525 
526  if ( last != k || k->size() != i + 1 ) {
527 
528  // Copy last entity in last bucket to bucket *k slot i
529 
530  Entity & entity = (*last)[ last->size() - 1 ];
531 
532  copy_fields( *k , i , *last , last->size() - 1 );
533 
534  k->m_bucketImpl.replace_entity(i, & entity ) ;
535  m_entity_repo.change_entity_bucket( *k, entity, i);
536 
537  // Entity field data has relocated
538 
539  internal_propagate_relocation( entity );
540  }
541 
542  last->m_bucketImpl.decrement_size();
543 
544  last->m_bucketImpl.replace_entity( last->size() , NULL ) ;
545 
546  if ( 0 == last->size() ) {
547  destroy_bucket( entity_rank , last );
548  }
549 }
550 
551 //----------------------------------------------------------------------
552 
553 void BucketRepository::internal_propagate_relocation( Entity & entity )
554 {
555  TraceIf("stk_classic::mesh::impl::BucketRepository::internal_propagate_relocation", LOG_BUCKET);
556 
557  const EntityRank erank = entity.entity_rank();
558  PairIterRelation rel = entity.relations();
559 
560  for ( ; ! rel.empty() ; ++rel ) {
561  const EntityRank rel_rank = rel->entity_rank();
562  if ( rel_rank < erank ) {
563  Entity & e_to = * rel->entity();
564 
565  set_field_relations( entity, e_to, rel->identifier() );
566  }
567  else if ( erank < rel_rank ) {
568  Entity & e_from = * rel->entity();
569 
570  set_field_relations( e_from, entity, rel->identifier() );
571  }
572  }
573 }
574 
575 
576 } // namespace impl
577 } // namespace mesh
578 } // namespace stk_classic
579 
580 
unsigned bucket_ordinal() const
The ordinal for this entity within its bucket.
Definition: Entity.hpp:145
Bucket & bucket() const
The bucket which holds this mesh entity&#39;s field data.
Definition: Entity.hpp:141
PairIterRelation relations() const
All Entity relations for which this entity is a member. The relations are ordered from lowest entity-...
Definition: Entity.hpp:161
Sierra Toolkit.
EntityRank entity_rank() const
The rank of this entity.
Definition: Entity.hpp:128
EntityRank entity_rank(const EntityKey &key)
Given an entity key, return an entity type (rank).
eastl::iterator_traits< InputIterator >::difference_type count(InputIterator first, InputIterator last, const T &value)