Sierra Toolkit Version of the Day
BucketRepository.cpp
00001 /*------------------------------------------------------------------------*/
00002 /*                 Copyright 2010 Sandia Corporation.                     */
00003 /*  Under terms of Contract DE-AC04-94AL85000, there is a non-exclusive   */
00004 /*  license for use of this work by or on behalf of the U.S. Government.  */
00005 /*  Export of this program may require a license from the                 */
00006 /*  United States Government.                                             */
00007 /*------------------------------------------------------------------------*/
00008 
00009 #include <sstream>
00010 #include <cstdlib>
00011 #include <stdexcept>
00012 
00013 #include <stk_mesh/baseImpl/BucketRepository.hpp>
00014 #include <stk_mesh/baseImpl/EntityRepository.hpp>
00015 #include <stk_mesh/base/BulkData.hpp>
00016 #include <stk_mesh/base/Bucket.hpp>
00017 #include <stk_mesh/base/Trace.hpp>
00018 
00019 namespace stk {
00020 namespace mesh {
00021 namespace impl {
00022 
00023 //----------------------------------------------------------------------
00024 
00025 
00026 BucketRepository::BucketRepository(
00027     BulkData & mesh,
00028     unsigned bucket_capacity,
00029     unsigned entity_rank_count,
00030     EntityRepository & entity_repo
00031     )
00032   :m_mesh(mesh),
00033    m_bucket_capacity(bucket_capacity),
00034    m_buckets(entity_rank_count),
00035    m_nil_bucket(NULL),
00036    m_entity_repo(entity_repo)
00037 {
00038 }
00039 
00040 
00041 BucketRepository::~BucketRepository()
00042 {
00043   // Destroy buckets, which were *not* allocated by the set.
00044 
00045   try {
00046     for ( std::vector< std::vector<Bucket*> >::iterator
00047           i = m_buckets.end() ; i != m_buckets.begin() ; ) {
00048       try {
00049         std::vector<Bucket*> & kset = *--i ;
00050 
00051         while ( ! kset.empty() ) {
00052           try { destroy_bucket( kset.back() ); } catch(...) {}
00053           kset.pop_back();
00054         }
00055         kset.clear();
00056       } catch(...) {}
00057     }
00058     m_buckets.clear();
00059   } catch(...) {}
00060 
00061   try { if ( m_nil_bucket ) destroy_bucket( m_nil_bucket ); } catch(...) {}
00062 }
00063 
00064 
00065 //----------------------------------------------------------------------
00066 // The current 'last' bucket in a family is to be deleted.
00067 // The previous 'last' bucket becomes the new 'last' bucket in the family.
00068 
00069 void BucketRepository::destroy_bucket( const unsigned & entity_rank , Bucket * bucket_to_be_deleted )
00070 {
00071   TraceIfWatching("stk::mesh::impl::BucketRepository::destroy_bucket", LOG_BUCKET, bucket_to_be_deleted);
00072 
00073   ThrowRequireMsg(MetaData::get(m_mesh).check_rank(entity_rank),
00074                   "Entity rank " << entity_rank << " is invalid");
00075 
00076   std::vector<Bucket *> & bucket_set = m_buckets[entity_rank];
00077 
00078   // Get the first bucket in the same family as the bucket being deleted
00079   Bucket * const first = bucket_to_be_deleted->m_bucketImpl.first_bucket_in_family();
00080 
00081   ThrowRequireMsg( bucket_to_be_deleted->equivalent(*first), "Logic error - bucket_to_be_deleted is not in same family as first_bucket_in_family");
00082   ThrowRequireMsg( first->equivalent(*bucket_to_be_deleted), "Logic error - first_bucket_in_family is not in same family as bucket_to_be_deleted");
00083 
00084   ThrowRequireMsg( bucket_to_be_deleted->size() == 0,
00085       "Destroying non-empty bucket " << *(bucket_to_be_deleted->key()) );
00086 
00087   ThrowRequireMsg( bucket_to_be_deleted == first->m_bucketImpl.get_bucket_family_pointer(),
00088                    "Destroying bucket family") ;
00089 
00090   std::vector<Bucket*>::iterator ik = lower_bound(bucket_set, bucket_to_be_deleted->key());
00091   ThrowRequireMsg( ik != bucket_set.end() && bucket_to_be_deleted == *ik,
00092       "Bucket not found in bucket set for entity rank " << entity_rank );
00093 
00094   ik = bucket_set.erase( ik );
00095 
00096   if ( first != bucket_to_be_deleted ) {
00097 
00098     ThrowRequireMsg( ik != bucket_set.begin(),
00099                      "Where did first bucket go?" );
00100 
00101     first->m_bucketImpl.set_last_bucket_in_family( *--ik );
00102 
00103     ThrowRequireMsg ( first->m_bucketImpl.get_bucket_family_pointer()->size() != 0,
00104                       "TODO: Explain" );
00105   }
00106 
00107   destroy_bucket( bucket_to_be_deleted );
00108 }
00109 
00110 //----------------------------------------------------------------------
00111 void BucketRepository::destroy_bucket( Bucket * bucket )
00112 {
00113   TraceIfWatching("stk::mesh::impl::BucketRepository::destroy_bucket", LOG_BUCKET, bucket);
00114 
00115   delete bucket;
00116 }
00117 
00118 //
00119 //----------------------------------------------------------------------
00120 // The input part ordinals are complete and contain all supersets.
00121 void
00122 BucketRepository::declare_nil_bucket()
00123 {
00124   TraceIf("stk::mesh::impl::BucketRepository::declare_nil_bucket", LOG_BUCKET);
00125 
00126   if (m_nil_bucket == NULL) {
00127     // Key layout:
00128     // { part_count + 1 , { part_ordinals } , family_count }
00129 
00130     std::vector<unsigned> new_key(2);
00131     new_key[0] = 1 ; // part_count + 1
00132     new_key[1] = 0 ; // family_count
00133 
00134     Bucket * bucket =
00135       new Bucket(m_mesh, InvalidEntityRank, new_key, 0);
00136 
00137     bucket->m_bucketImpl.set_bucket_family_pointer( bucket );
00138 
00139     //----------------------------------
00140 
00141     m_nil_bucket = bucket;
00142   }
00143 }
00144 
00145 
00168 //----------------------------------------------------------------------
00169 // The input part ordinals are complete and contain all supersets.
00170 Bucket *
00171 BucketRepository::declare_bucket(
00172                         const unsigned arg_entity_rank ,
00173                         const unsigned part_count ,
00174                         const unsigned part_ord[] ,
00175                         const std::vector< FieldBase * > & field_set
00176                               )
00177 {
00178   enum { KEY_TMP_BUFFER_SIZE = 64 };
00179 
00180   TraceIf("stk::mesh::impl::BucketRepository::declare_bucket", LOG_BUCKET);
00181 
00182   const unsigned max = static_cast<unsigned>(-1);
00183 
00184   ThrowRequireMsg(MetaData::get(m_mesh).check_rank(arg_entity_rank),
00185                   "Entity rank " << arg_entity_rank << " is invalid");
00186 
00187   ThrowRequireMsg( !m_buckets.empty(),
00188     "m_buckets is empty! Did you forget to initialize MetaData before creating BulkData?");
00189   std::vector<Bucket *> & bucket_set = m_buckets[ arg_entity_rank ];
00190 
00191 
00192   std::vector<unsigned> key(2+part_count) ;
00193 
00194   //----------------------------------
00195   // Key layout:
00196   // { part_count + 1 , { part_ordinals } , family_count }
00197   // Thus family_count = key[ key[0] ]
00198   //
00199   // for upper bound search use the maximum key.
00200 
00201   key[0] = part_count+1;
00202   key[ key[0] ] = max ;
00203 
00204   {
00205     for ( unsigned i = 0 ; i < part_count ; ++i ) { key[i+1] = part_ord[i] ; }
00206   }
00207 
00208   //----------------------------------
00209   // Bucket family has all of the same parts.
00210   // Look for the last bucket in this family:
00211 
00212   const std::vector<Bucket*>::iterator ik = lower_bound( bucket_set , &key[0] );
00213 
00214   //----------------------------------
00215   // If a member of the bucket family has space, it is the last one
00216   // since buckets are kept packed.
00217   const bool bucket_family_exists =
00218     ik != bucket_set.begin() && bucket_part_equal( ik[-1]->key() , &key[0] );
00219 
00220   Bucket * const last_bucket = bucket_family_exists ? ik[-1] : NULL ;
00221 
00222   Bucket          * bucket    = NULL ;
00223 
00224   if ( last_bucket == NULL ) { // First bucket in this family
00225     key[ key[0] ] = 0 ; // Set the key's family count to zero
00226   }
00227   else { // Last bucket present, can it hold one more entity?
00228 
00229     ThrowRequireMsg( last_bucket->size() != 0,
00230                      "Last bucket should not be empty.");
00231 
00232     //field_map = last_bucket->m_bucketImpl.get_field_map();
00233 
00234     const unsigned last_count = last_bucket->key()[ key[0] ];
00235 
00236     const unsigned cap = last_bucket->capacity();
00237 
00238     if ( last_bucket->size() < cap ) {
00239       bucket = last_bucket ;
00240     }
00241     else if ( last_count < max ) {
00242       key[ key[0] ] = 1 + last_count ; // Increment the key's family count.
00243     }
00244     else {
00245       // ERROR insane number of buckets!
00246       ThrowRequireMsg( false, "Insanely large number of buckets" );
00247     }
00248   }
00249 
00250 
00251   //----------------------------------
00252 
00253   //Required bucket does not exist
00254   if ( NULL == bucket )
00255   {
00256     bucket = new Bucket( m_mesh, arg_entity_rank, key, m_bucket_capacity);
00257 
00258     Bucket * first_bucket = last_bucket ? last_bucket->m_bucketImpl.first_bucket_in_family() : bucket ;
00259 
00260     bucket->m_bucketImpl.set_first_bucket_in_family(first_bucket); // Family members point to first bucket
00261 
00262     first_bucket->m_bucketImpl.set_last_bucket_in_family(bucket); // First bucket points to new last bucket
00263 
00264     bucket_set.insert( ik , bucket );
00265   }
00266 
00267   //----------------------------------
00268 
00269   ThrowRequireMsg( bucket->equivalent(*bucket->m_bucketImpl.first_bucket_in_family()), "Logic error - new bucket is not in same family as first_bucket_in_family");
00270   ThrowRequireMsg( bucket->m_bucketImpl.first_bucket_in_family()->equivalent(*bucket), "Logic error - first_bucket_in_family is not in same family as new bucket");
00271 
00272   return bucket ;
00273 }
00274 
00275 //----------------------------------------------------------------------
00276 
00277 void BucketRepository::initialize_fields( Bucket & k_dst , unsigned i_dst )
00278 {
00279   TraceIfWatching("stk::mesh::impl::BucketRepository::initialize_fields", LOG_BUCKET, &k_dst);
00280   k_dst.m_bucketImpl.initialize_fields(i_dst);
00281 }
00282 
00283 //----------------------------------------------------------------------
00284 
00285 void BucketRepository::update_field_data_states() const
00286 {
00287   TraceIf("stk::mesh::impl::BucketRepository::update_field_data_states", LOG_BUCKET);
00288 
00289   for ( std::vector< std::vector<Bucket*> >::const_iterator
00290         i = m_buckets.begin() ; i != m_buckets.end() ; ++i ) {
00291 
00292     const std::vector<Bucket*> & kset = *i ;
00293 
00294     for ( std::vector<Bucket*>::const_iterator
00295           ik = kset.begin() ; ik != kset.end() ; ++ik ) {
00296       (*ik)->m_bucketImpl.update_state();
00297     }
00298   }
00299 }
00300 
00301 
00302 //----------------------------------------------------------------------
00303 
00304 
00305 void BucketRepository::internal_sort_bucket_entities()
00306 {
00307   TraceIf("stk::mesh::impl::BucketRepository::internal_sort_bucket_entities", LOG_BUCKET);
00308 
00309   for ( EntityRank entity_rank = 0 ;
00310         entity_rank < m_buckets.size() ; ++entity_rank ) {
00311 
00312     std::vector<Bucket*> & buckets = m_buckets[ entity_rank ];
00313 
00314     size_t bk = 0 ; // Offset to first bucket of the family
00315     size_t ek = 0 ; // Offset to end   bucket of the family
00316 
00317     for ( ; bk < buckets.size() ; bk = ek ) {
00318       Bucket * b_scratch = NULL ;
00319       Bucket * ik_vacant = buckets[bk]->m_bucketImpl.last_bucket_in_family();
00320       unsigned ie_vacant = ik_vacant->size();
00321 
00322       if ( ik_vacant->capacity() <= ie_vacant ) {
00323         // Have to create a bucket just for the scratch space...
00324         const unsigned * const bucket_key = buckets[bk]->key() ;
00325         const unsigned         part_count = bucket_key[0] - 1 ;
00326         const unsigned * const part_ord   = bucket_key + 1 ;
00327 
00328         b_scratch = declare_bucket( entity_rank ,
00329             part_count , part_ord ,
00330             MetaData::get(m_mesh).get_fields() );
00331 
00332         ik_vacant = b_scratch ;
00333         ie_vacant = 0 ;
00334       }
00335 
00336       ik_vacant->m_bucketImpl.replace_entity( ie_vacant , NULL ) ;
00337 
00338       // Determine offset to the end bucket in this family:
00339       while ( ek < buckets.size() && ik_vacant != buckets[ek] ) { ++ek ; }
00340       if (ek < buckets.size()) ++ek ;
00341 
00342       unsigned count = 0 ;
00343       for ( size_t ik = bk ; ik != ek ; ++ik ) {
00344         count += buckets[ik]->size();
00345       }
00346 
00347       std::vector<Entity*> entities( count );
00348 
00349       std::vector<Entity*>::iterator j = entities.begin();
00350 
00351       for ( size_t ik = bk ; ik != ek ; ++ik ) {
00352         Bucket & b = * buckets[ik];
00353         const unsigned n = b.size();
00354         for ( unsigned i = 0 ; i < n ; ++i , ++j ) {
00355           *j = & b[i] ;
00356         }
00357       }
00358 
00359       std::sort( entities.begin() , entities.end() , EntityLess() );
00360 
00361       j = entities.begin();
00362 
00363       bool change_this_family = false ;
00364 
00365       for ( size_t ik = bk ; ik != ek ; ++ik ) {
00366         Bucket & b = * buckets[ik];
00367         const unsigned n = b.size();
00368         for ( unsigned i = 0 ; i < n ; ++i , ++j ) {
00369           Entity * const current = & b[i] ;
00370 
00371           if ( current != *j ) {
00372 
00373             if ( current ) {
00374               // Move current entity to the vacant spot
00375               copy_fields( *ik_vacant , ie_vacant , b, i );
00376               m_entity_repo.change_entity_bucket(*ik_vacant, *current, ie_vacant);
00377               ik_vacant->m_bucketImpl.replace_entity( ie_vacant , current ) ;
00378             }
00379 
00380             // Set the vacant spot to where the required entity is now.
00381             ik_vacant = & ((*j)->bucket()) ;
00382             ie_vacant = (*j)->bucket_ordinal() ;
00383             ik_vacant->m_bucketImpl.replace_entity( ie_vacant , NULL ) ;
00384 
00385             // Move required entity to the required spot
00386             copy_fields( b, i, *ik_vacant , ie_vacant );
00387             m_entity_repo.change_entity_bucket( b, **j, i);
00388             b.m_bucketImpl.replace_entity( i, *j );
00389 
00390             change_this_family = true ;
00391           }
00392 
00393           // Once a change has occured then need to propagate the
00394           // relocation for the remainder of the family.
00395           // This allows the propagation to be performed once per
00396           // entity as opposed to both times the entity is moved.
00397 
00398           if ( change_this_family ) { internal_propagate_relocation( **j ); }
00399         }
00400       }
00401 
00402       if ( b_scratch ) {
00403         // Created a last bucket, now have to destroy it.
00404         destroy_bucket( entity_rank , b_scratch );
00405         --ek ;
00406       }
00407     }
00408   }
00409 }
00410 
00411 void BucketRepository::optimize_buckets()
00412 {
00413   TraceIf("stk::mesh::impl::BucketRepository::optimize_buckets", LOG_BUCKET);
00414 
00415   for ( EntityRank entity_rank = 0 ;
00416       entity_rank < m_buckets.size() ; ++entity_rank )
00417   {
00418 
00419     std::vector<Bucket*> & buckets = m_buckets[ entity_rank ];
00420 
00421     std::vector<Bucket*> tmp_buckets;
00422 
00423     size_t begin_family = 0 ; // Offset to first bucket of the family
00424     size_t end_family = 0 ; // Offset to end   bucket of the family
00425 
00426     //loop over families
00427     for ( ; begin_family < buckets.size() ; begin_family = end_family ) {
00428       Bucket * last_bucket_in_family  = buckets[begin_family]->m_bucketImpl.last_bucket_in_family();
00429 
00430       // Determine offset to the end bucket in this family:
00431       while ( end_family < buckets.size() && last_bucket_in_family != buckets[end_family] ) { ++end_family ; }
00432       if (end_family < buckets.size())  ++end_family ; //increment past the end
00433 
00434       //if compressed and sorted go to the next family
00435       const bool is_compressed =    (end_family-begin_family == 1)
00436                                  && (buckets[begin_family]->size() == buckets[begin_family]->capacity());
00437       if (is_compressed) {
00438         const Bucket & b = *buckets[begin_family];
00439         bool is_sorted = true;
00440         for (size_t i=0, end=b.size()-1; i<end && is_sorted; ++i)
00441         {
00442           if(b[i].key() >= b[i+1].key()) is_sorted = false;
00443         }
00444         if (is_sorted) {
00445           tmp_buckets.push_back(buckets[begin_family]);
00446           continue;
00447         }
00448       }
00449 
00450       std::vector<unsigned> new_key = buckets[begin_family]->m_bucketImpl.key_vector();
00451       //index of bucket in family
00452       new_key[ new_key[0] ] = 0;
00453 
00454       unsigned new_capacity = 0 ;
00455       for ( size_t i = begin_family ; i != end_family ; ++i ) {
00456         new_capacity += buckets[i]->m_bucketImpl.size();
00457       }
00458 
00459       std::vector<Entity*> entities;
00460       entities.reserve(new_capacity);
00461 
00462       for ( size_t i = begin_family ; i != end_family ; ++i ) {
00463         Bucket& b = *buckets[i];
00464         for(size_t j=0; j<b.size(); ++j) {
00465           entities.push_back(&b[j]);
00466         }
00467       }
00468 
00469       std::sort( entities.begin(), entities.end(), EntityLess() );
00470 
00471       Bucket * new_bucket = new Bucket( m_mesh,
00472           entity_rank,
00473           new_key,
00474           new_capacity
00475           );
00476 
00477       new_bucket->m_bucketImpl.set_first_bucket_in_family(new_bucket); // Family members point to first bucket
00478       new_bucket->m_bucketImpl.set_last_bucket_in_family(new_bucket); // First bucket points to new last bucket
00479 
00480       tmp_buckets.push_back(new_bucket);
00481 
00482       for(size_t new_ordinal=0; new_ordinal<entities.size(); ++new_ordinal) {
00483         //increase size of the new_bucket
00484         new_bucket->m_bucketImpl.increment_size();
00485 
00486         Entity & entity = *entities[new_ordinal];
00487         Bucket& old_bucket = entity.bucket();
00488         unsigned old_ordinal = entity.bucket_ordinal();
00489 
00490         //copy field data from old to new
00491         copy_fields( *new_bucket, new_ordinal, old_bucket, old_ordinal);
00492         m_entity_repo.change_entity_bucket( *new_bucket, entity, new_ordinal);
00493         new_bucket->m_bucketImpl.replace_entity( new_ordinal , &entity ) ;
00494         internal_propagate_relocation(entity);
00495       }
00496 
00497       for (size_t ik = begin_family; ik != end_family; ++ik) {
00498         delete buckets[ik];
00499         buckets[ik] = NULL;
00500       }
00501     }
00502 
00503     buckets.swap(tmp_buckets);
00504   }
00505 }
00506 //----------------------------------------------------------------------
00507 
00508 void BucketRepository::remove_entity( Bucket * k , unsigned i )
00509 {
00510   TraceIfWatching("stk::mesh::impl::BucketRepository::remove_entity", LOG_BUCKET, k);
00511 
00512   ThrowRequireMsg( k != m_nil_bucket, "Cannot remove entity from nil_bucket" );
00513 
00514   const EntityRank entity_rank = k->entity_rank();
00515 
00516   // Last bucket in the family of buckets with the same parts.
00517   // The last bucket is the only non-full bucket in the family.
00518 
00519   Bucket * const last = k->m_bucketImpl.last_bucket_in_family();
00520 
00521   ThrowRequireMsg( last->equivalent(*k), "Logic error - last bucket in family not equivalent to bucket");
00522   ThrowRequireMsg( k->equivalent(*last), "Logic error - bucket not equivalent to last bucket in family");
00523 
00524   // Fill in the gap if it is not the last entity being removed
00525 
00526   if ( last != k || k->size() != i + 1 ) {
00527 
00528     // Copy last entity in last bucket to bucket *k slot i
00529 
00530     Entity & entity = (*last)[ last->size() - 1 ];
00531 
00532     copy_fields( *k , i , *last , last->size() - 1 );
00533 
00534     k->m_bucketImpl.replace_entity(i, & entity ) ;
00535     m_entity_repo.change_entity_bucket( *k, entity, i);
00536 
00537     // Entity field data has relocated
00538 
00539     internal_propagate_relocation( entity );
00540   }
00541 
00542   last->m_bucketImpl.decrement_size();
00543 
00544   last->m_bucketImpl.replace_entity( last->size() , NULL ) ;
00545 
00546   if ( 0 == last->size() ) {
00547     destroy_bucket( entity_rank , last );
00548   }
00549 }
00550 
00551 //----------------------------------------------------------------------
00552 
00553 void BucketRepository::internal_propagate_relocation( Entity & entity )
00554 {
00555   TraceIf("stk::mesh::impl::BucketRepository::internal_propagate_relocation", LOG_BUCKET);
00556 
00557   const EntityRank erank = entity.entity_rank();
00558   PairIterRelation rel = entity.relations();
00559 
00560   for ( ; ! rel.empty() ; ++rel ) {
00561     const EntityRank rel_rank = rel->entity_rank();
00562     if ( rel_rank < erank ) {
00563       Entity & e_to = * rel->entity();
00564 
00565       set_field_relations( entity, e_to, rel->identifier() );
00566     }
00567     else if ( erank < rel_rank ) {
00568       Entity & e_from = * rel->entity();
00569 
00570       set_field_relations( e_from, entity, rel->identifier() );
00571     }
00572   }
00573 }
00574 
00575 
00576 } // namespace impl
00577 } // namespace mesh
00578 } // namespace stk
00579 
00580 
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines