From b99e03eb41d8eadee751e027da67e86871e7782c Mon Sep 17 00:00:00 2001 From: nanbor Date: Mon, 30 Dec 2002 17:32:48 +0000 Subject: *** empty log message *** --- ace/Hash_Map_Manager_RT.cpp | 2 +- ace/Hash_Map_Manager_RT_T.cpp | 352 ++++++++++++++------------- ace/Hash_Map_Manager_RT_T.h | 476 ++++++++++++++++++++++--------------- ace/Hash_Map_Manager_RT_T.inl | 237 ++++++++++-------- tests/Hash_Map_Manager_RT_Test.cpp | 16 +- 5 files changed, 619 insertions(+), 464 deletions(-) diff --git a/ace/Hash_Map_Manager_RT.cpp b/ace/Hash_Map_Manager_RT.cpp index de2bc12dd7f..d9e263318ac 100644 --- a/ace/Hash_Map_Manager_RT.cpp +++ b/ace/Hash_Map_Manager_RT.cpp @@ -13,6 +13,6 @@ // // ============================================================================ -#include "ace/Hash_Map_Manager_RT.h" +#include "Hash_Map_Manager_RT.h" ACE_RCSID(ace, Hash_Map_Manager_RT, "$Id$") diff --git a/ace/Hash_Map_Manager_RT_T.cpp b/ace/Hash_Map_Manager_RT_T.cpp index 62000df2e33..c34bd819162 100644 --- a/ace/Hash_Map_Manager_RT_T.cpp +++ b/ace/Hash_Map_Manager_RT_T.cpp @@ -28,10 +28,10 @@ #include "Synch.h" #include "Service_Config.h" #include "Malloc.h" -#include +#include ACE_RCSID(ace, Hash_Map_Manager_RT_T, "$Id$") - + //***************************************************************/ ACE_Hash_Map_RT_Coord::ACE_Hash_Map_RT_Coord (int table, @@ -47,33 +47,33 @@ ACE_Hash_Map_RT_Coord::~ACE_Hash_Map_RT_Coord (void) //***************************************************************/ -template -ACE_Hash_Map_RT_Hash_Function::ACE_Hash_Map_RT_Hash_Function (int number_of_tables, +template +ACE_Hash_Map_RT_Hash_Function::ACE_Hash_Map_RT_Hash_Function (int number_of_tables, int buckets_per_table) : max_tables_ (number_of_tables), buckets_per_table_ (buckets_per_table) { } -template -ACE_Hash_Map_RT_Hash_Function::~ACE_Hash_Map_RT_Hash_Function (void) +template +ACE_Hash_Map_RT_Hash_Function::~ACE_Hash_Map_RT_Hash_Function (void) { } -template int -ACE_Hash_Map_RT_Hash_Function::hash (const EXT_ID& ext_id, +template int +ACE_Hash_Map_RT_Hash_Function::hash (const EXT_ID& ext_id, ACE_Hash_Map_RT_Coord& coord) { int hashCode = hash_key_ (ext_id); if ( hashCode < 0 ) hashCode *= -1; - + this->hash_i (hashCode, coord); - + return 0; } -template int -ACE_Hash_Map_RT_Hash_Function::hash_i (int key, +template int +ACE_Hash_Map_RT_Hash_Function::hash_i (int key, ACE_Hash_Map_RT_Coord& coord) { // Have you thought about precisions in all the platforms that @@ -81,95 +81,95 @@ ACE_Hash_Map_RT_Hash_Function::hash_i (int key, double prod = (key * 0.618033988) - (size_t)(key * 0.618033988); size_t u = (int)(this->max_tables_ * this->buckets_per_table_ * prod); - + coord.set_table(u / this->buckets_per_table_); coord.set_bucket(u % this->buckets_per_table_); - + return 0; } //***************************************************************/ -template -ACE_Hash_Map_RT_POD::ACE_Hash_Map_RT_POD (int num_tables, - ACE_Hash_Map_RT_Hash_Function& func) +template +ACE_Hash_Map_RT_POD::ACE_Hash_Map_RT_POD (int num_tables, + ACE_Hash_Map_RT_Hash_Function& func) : num_tables_ (num_tables), func_ (func) { } -template -ACE_Hash_Map_RT_POD::~ACE_Hash_Map_RT_POD (void) +template +ACE_Hash_Map_RT_POD::~ACE_Hash_Map_RT_POD (void) { } //***************************************************************/ -template -ACE_Hash_Map_RT_ListItem::ACE_Hash_Map_RT_ListItem (ENTRY* entry, +template +ACE_Hash_Map_RT_ListItem::ACE_Hash_Map_RT_ListItem (ENTRY* entry, LITEM* next) : entry_ (entry), next_ (next) { } -template -ACE_Hash_Map_RT_ListItem::ACE_Hash_Map_RT_ListItem () +template +ACE_Hash_Map_RT_ListItem::ACE_Hash_Map_RT_ListItem () : entry_ (0), next_ (0) { } -template -ACE_Hash_Map_RT_ListItem::~ACE_Hash_Map_RT_ListItem (void) +template +ACE_Hash_Map_RT_ListItem::~ACE_Hash_Map_RT_ListItem (void) { } //***************************************************************/ -template -ACE_Hash_Map_RT_Entry::ACE_Hash_Map_RT_Entry (const EXT_ID& ext_id, +template +ACE_Hash_Map_RT_Entry::ACE_Hash_Map_RT_Entry (const EXT_ID& ext_id, const INT_ID& int_id) : ext_id_ (ext_id), int_id_ (int_id) { } -template -ACE_Hash_Map_RT_Entry::ACE_Hash_Map_RT_Entry () -{ +template +ACE_Hash_Map_RT_Entry::ACE_Hash_Map_RT_Entry () +{ } # if ! defined (ACE_HAS_BROKEN_NOOP_DTORS) -template -ACE_Hash_Map_RT_Entry::~ACE_Hash_Map_RT_Entry (void) +template +ACE_Hash_Map_RT_Entry::~ACE_Hash_Map_RT_Entry (void) { } # endif /* ! defined (ACE_HAS_BROKEN_NOOP_DTORS) */ //***************************************************************/ -template -ACE_Hash_Map_RT_Bucket::ACE_Hash_Map_RT_Bucket (POD* pod) +template +ACE_Hash_Map_RT_Bucket::ACE_Hash_Map_RT_Bucket (POD* pod) : curPOD_ (pod) { init_bucket_i(pod); } -template -ACE_Hash_Map_RT_Bucket::ACE_Hash_Map_RT_Bucket (void) +template +ACE_Hash_Map_RT_Bucket::ACE_Hash_Map_RT_Bucket (void) { } -template -ACE_Hash_Map_RT_Bucket::~ACE_Hash_Map_RT_Bucket (void) +template +ACE_Hash_Map_RT_Bucket::~ACE_Hash_Map_RT_Bucket (void) { - // The "if" second argument results in a no-op instead of deallocation. - ACE_DES_FREE_TEMPLATE2 (this->curPOD_, + // The "if" second argument results in a no-op instead of deallocation. + ACE_DES_FREE_TEMPLATE2 (this->curPOD_, ACE_NOOP, - ACE_Hash_Map_RT_POD, - EXT_ID, + ACE_Hash_Map_RT_POD, + EXT_ID, INT_ID); this->curPOD_ = 0; @@ -179,16 +179,17 @@ ACE_Hash_Map_RT_Bucket::~ACE_Hash_Map_RT_Bucket (void) this->last_ = 0; } -template int -ACE_Hash_Map_RT_Bucket::init_bucket_i (POD* pod) +template int +ACE_Hash_Map_RT_Bucket::init_bucket_i (POD* pod) { this->head_ = new LITEM(); this->last_ = head_; + this->curPOD_ = pod; return 0; } -template int -ACE_Hash_Map_RT_Bucket::prepend (ENTRY& entry) +template int +ACE_Hash_Map_RT_Bucket::prepend (ENTRY& entry) { this->head_->next_ = new LITEM((new ENTRY(entry.get_ext_id(), @@ -202,57 +203,69 @@ ACE_Hash_Map_RT_Bucket::prepend (ENTRY& entry) //***************************************************************/ -template -ACE_Hash_Map_RT_Table::ACE_Hash_Map_RT_Table () +template +ACE_Hash_Map_RT_Table::ACE_Hash_Map_RT_Table () { } -template -ACE_Hash_Map_RT_Table::ACE_Hash_Map_RT_Table (ACE_Allocator *allocator, +template +ACE_Hash_Map_RT_Table::ACE_Hash_Map_RT_Table (ACE_Allocator *allocator, size_t buckets_per_table, POD* pod) { init_table_i(allocator, buckets_per_table, pod); } -template -ACE_Hash_Map_RT_Table::~ACE_Hash_Map_RT_Table (void) +template +ACE_Hash_Map_RT_Table::~ACE_Hash_Map_RT_Table (void) { // } -template int -ACE_Hash_Map_RT_Table::init_table_i (ACE_Allocator *allocator, +template int +ACE_Hash_Map_RT_Table::init_table_i (ACE_Allocator *allocator, size_t buckets_per_table, POD* pod) { size_t bytes = buckets_per_table * sizeof (BUCKET); void *ptr; - + ACE_ALLOCATOR_RETURN (ptr, allocator->malloc (bytes), -1); - + this->buckets_ = (BUCKET *) ptr; - + for (size_t i = 0; i < buckets_per_table; i++) new (&this->buckets_[i]) BUCKET(pod); - + return 0; }; //***************************************************************/ -ACE_Hash_Map_RT_StatsManager::ACE_Hash_Map_RT_StatsManager (void) +template +ACE_Hash_Map_RT_StatsManager::ACE_Hash_Map_RT_StatsManager (void) : max_chain_ (0), total_elements_ (0) { } -ACE_Hash_Map_RT_StatsManager::~ACE_Hash_Map_RT_StatsManager (void) +template +ACE_Hash_Map_RT_StatsManager::~ACE_Hash_Map_RT_StatsManager (void) +{ +} + +/*ACE_Hash_Map_RT_StatsManager::ACE_Hash_Map_RT_StatsManager (void) + : max_chain_ (0), + total_elements_ (0) { } +ACE_Hash_Map_RT_StatsManager::~ACE_Hash_Map_RT_StatsManager (void) +{ +}*/ + //***************************************************************/ template @@ -265,35 +278,44 @@ ACE_Hash_Map_RT_Clean_Manager: template ACE_Hash_Map_RT_Clean_Visitor::ACE_Hash_Map_RT_Clean_Visitor (ACE_Hash_Map_RT_Manager_Ex* thismanager) -{ +{ this->manager_ = thismanager; } +template +ACE_Hash_Map_RT_Clean_Visitor::~ACE_Hash_Map_RT_Clean_Visitor (void) +{ + this->dead_bucket = 0; + this->manager_ = 0; + this->found_ = 0; + this->mtfPrev_ = 0; +} + template ACE_Hash_Map_RT_Clean_Manager* ACE_Hash_Map_RT_Clean_Manager::incremental_clean (void) { if (more_to_do()) { - BUCKET& bucket = manager_->get_table(cur_table_).get_bucket(cur_bucket_); + BUCKET& bucket = manager_->get_table(cur_table_).get_bucket(cur_bucket_); if (!bucket.is_clean(*manager_->curPOD_)) manager_->clean_vis_->process_bucket(bucket); - ++cur_bucket_; - if (cur_bucket_ >= manager_->buckets_per_table_) + ++cur_bucket_; + if (cur_bucket_ >= manager_->buckets_per_table_) { - ++cur_table_; - cur_bucket_ = 0; - } - } - if (cur_table_ < manager_->oldPOD_->get_num_tables()) + ++cur_table_; + cur_bucket_ = 0; + } + } + if (cur_table_ < manager_->oldPOD_->get_num_tables()) return this; - else + else { - this->manager_->oldPOD_ = 0; + this->manager_->oldPOD_ = 0; this->cur_table_ = 0; this->manager_->stats_->reset_max_chain(); - return 0; - } + return 0; + } } template int @@ -323,31 +345,31 @@ ACE_Hash_Map_RT_Manager_Ex::AC template ACE_Hash_Map_RT_Manager_Ex::~ACE_Hash_Map_RT_Manager_Ex (void) { - close_manager(); + close(); } template int -ACE_Hash_Map_RT_Manager_Ex::open_i (size_t buckets_per_table, +ACE_Hash_Map_RT_Manager_Ex::open_i (size_t buckets_per_table, ACE_Allocator *alloc) { void *ptr, *ptr2; - + ACE_ALLOCATOR_RETURN (ptr, - allocator_->malloc (sizeof(ACE_Hash_Map_RT_POD)), + allocator_->malloc (sizeof(ACE_Hash_Map_RT_POD)), -1); - + ACE_ALLOCATOR_RETURN (ptr2, - allocator_->malloc (sizeof(ACE_Hash_Map_RT_Hash_Function)), + allocator_->malloc (sizeof(ACE_Hash_Map_RT_Hash_Function)), -1); - - this->curPOD_ = new (ptr) ACE_Hash_Map_RT_POD(1, *(new (ptr2) ACE_Hash_Map_RT_Hash_Function(1, this->buckets_per_table_))); + + this->curPOD_ = new (ptr) ACE_Hash_Map_RT_POD(1, *(new (ptr2) ACE_Hash_Map_RT_Hash_Function(1, this->buckets_per_table_))); this->oldPOD_ = 0; ACE_ALLOCATOR_RETURN (ptr, - allocator_->malloc (sizeof(ACE_Hash_Map_RT_StatsManager)), + allocator_->malloc (sizeof(ACE_Hash_Map_RT_StatsManager)), -1); - this->stats_ = new (ptr) ACE_Hash_Map_RT_StatsManager(); + this->stats_ = new (ptr) ACE_Hash_Map_RT_StatsManager(); ACE_ALLOCATOR_RETURN (ptr, allocator_->malloc (sizeof(ACE_Hash_Map_RT_Clean_Manager)), @@ -362,28 +384,28 @@ ACE_Hash_Map_RT_Manager_Ex::op this->clean_vis_ = new (ptr) ACE_Hash_Map_RT_Clean_Visitor(this); ACE_WRITE_GUARD_RETURN (ACE_LOCK, ace_mon, this->lock_, -1); - + if (alloc == 0) alloc = ACE_Allocator::instance (); this->allocator_ = alloc; - + size_t bytes = this->max_tables_ * sizeof(TABLE); - + ACE_ALLOCATOR_RETURN (ptr, allocator_->malloc (bytes), -1); - + this->table_ = (TABLE *) ptr; - + for (size_t i = 0; i < max_tables_; i++) new (&this->get_table(i)) TABLE(allocator_, buckets_per_table, this->curPOD_); - + return 0; } template int -ACE_Hash_Map_RT_Manager_Ex::close_manager (void) +ACE_Hash_Map_RT_Manager_Ex::close (void) { ACE_WRITE_GUARD_RETURN (ACE_LOCK, ace_mon, this->lock_, -1); @@ -399,68 +421,68 @@ ACE_Hash_Map_RT_Manager_Ex::cl { // Remove all the entries. this->remove_all_i (); - + // Iterate through the buckets for (size_t i = 0; i < this->max_tables_; i++) { for (size_t j = 0; j < this->buckets_per_table_; j++) { BUCKET *temp_bkt = &(this->get_table(i).get_bucket(j)); - + // The "if" second argument results in a no-op instead of - // deallocation. - ACE_DES_FREE_TEMPLATE2 (temp_bkt, + // deallocation. + ACE_DES_FREE_TEMPLATE2 (temp_bkt, ACE_NOOP, - ACE_Hash_Map_RT_Bucket, - EXT_ID, + ACE_Hash_Map_RT_Bucket, + EXT_ID, INT_ID); temp_bkt = 0; } TABLE *temp_tbl = &(this->get_table(i)); // The "if" second argument results in a no-op instead of - // deallocation. - ACE_DES_FREE_TEMPLATE2 (temp_tbl, + // deallocation. + ACE_DES_FREE_TEMPLATE2 (temp_tbl, ACE_NOOP, - ACE_Hash_Map_RT_Table, - EXT_ID, + ACE_Hash_Map_RT_Table, + EXT_ID, INT_ID); temp_tbl = 0; } POD *pod = (this->get_POD()); - ACE_DES_FREE_TEMPLATE2 (pod, + ACE_DES_FREE_TEMPLATE2 (pod, ACE_NOOP, - ACE_Hash_Map_RT_POD, - EXT_ID, + ACE_Hash_Map_RT_POD, + EXT_ID, INT_ID); pod = 0; delete this->oldPOD_; this->oldPOD_ = 0; - - ACE_Hash_Map_RT_StatsManager *stats = (this->stats_); - ACE_DES_FREE_TEMPLATE2 (stats, + + ACE_Hash_Map_RT_StatsManager *stats = (this->stats_); + ACE_DES_FREE_TEMPLATE2 (stats, ACE_NOOP, - ACE_Hash_Map_RT_StatsManager, - EXT_ID, + ACE_Hash_Map_RT_StatsManager, + EXT_ID, INT_ID); stats = 0; CLEAN *clean = (this->clean_); - ACE_DES_FREE_TEMPLATE2 (clean, + ACE_DES_FREE_TEMPLATE2 (clean, ACE_NOOP, - ACE_Hash_Map_RT_Clean_Manager, - EXT_ID, + ACE_Hash_Map_RT_Clean_Manager, + EXT_ID, INT_ID); clean = 0; - + CLEANV *cleanv = (this->clean_vis_); - ACE_DES_FREE_TEMPLATE2 (cleanv, + ACE_DES_FREE_TEMPLATE2 (cleanv, ACE_NOOP, ACE_Hash_Map_RT_Clean_Visitor, - EXT_ID, + EXT_ID, INT_ID); cleanv = 0; @@ -470,7 +492,7 @@ ACE_Hash_Map_RT_Manager_Ex::cl // Should be done last... this->table_ = 0; } - + return 0; } @@ -479,7 +501,7 @@ template ::remove_all_i (void) { // Iterate through the entire map calling the destuctor of each . - + for (size_t i = 0; i < this->max_tables_; i++) { for (size_t j = 0; j < this->buckets_per_table_; j++) @@ -492,7 +514,7 @@ ACE_Hash_Map_RT_Manager_Ex::re temp_ptr = temp_ptr->next_; delete hold_ptr; hold_ptr = 0; - + /// Explicitly call the destructor. ACE_DES_FREE_TEMPLATE2 (hold_ptr, this->allocator_->free, @@ -500,7 +522,7 @@ ACE_Hash_Map_RT_Manager_Ex::re EXT_ID, INT_ID); } - } + } //done with the bucket this->get_table(i).get_bucket(j).set_length(0); } @@ -509,7 +531,7 @@ ACE_Hash_Map_RT_Manager_Ex::re } //this->cur_size_ = 0; - + return 0; } @@ -520,13 +542,13 @@ ACE_Hash_Map_RT_Manager_Ex::lo { ACE_Hash_Map_RT_Coord oldcoord = ACE_Hash_Map_RT_Coord(0,0); ACE_Hash_Map_RT_Coord newCoord = ACE_Hash_Map_RT_Coord(0,0); - + BUCKET& new_bucket = find_bucket(this->curPOD_, ext_id); - + if (is_stable() == 1) { int_id = 0; - + size_t num_cleaned = 0; if (!find_bucket(this->oldPOD_, ext_id).is_clean(*this->curPOD_)) { @@ -546,27 +568,27 @@ ACE_Hash_Map_RT_Manager_Ex::lo if (clean_ == 0) clean_ = new ACE_Hash_Map_RT_Clean_Manager (this); } - + else { visitor.process_bucket(new_bucket); } - + if (visitor.is_found() == 1) - { + { ENTRY& temp = *(visitor.get_found()).entry_; if (temp.get_int_id() != 0) - { - int_id = temp.get_int_id(); - return 0; - } + { + int_id = temp.get_int_id(); + return 0; + } } - + // we looped without finding the bucket return -1; } -template ACE_Hash_Map_RT_POD* +template ACE_Hash_Map_RT_POD* ACE_Hash_Map_RT_Manager_Ex::create_POD (void) { int bucketsPerTable = buckets_per_table_; @@ -575,33 +597,33 @@ ACE_Hash_Map_RT_Manager_Ex::cr double tuningKnob = 0.000; int new_num_of_tables = 0; - int currNumBuckets = bucketsPerTable * currNumTables; - double new_num_of_buckets = currNumBuckets + (double)(currNumBuckets+1)/(RTL_-1); - double idealLoadFactor = RTL_ - 1; - - double currNumElements = (double)(stats_->get_total_elements ()); - double currentLoadFactor = currNumElements / currNumBuckets; - double addPercentage = (idealLoadFactor - currentLoadFactor) / idealLoadFactor; - - new_num_of_tables = (int)(ceil(new_num_of_buckets / (double)bucketsPerTable)); - - double extraFraction = addPercentage * new_num_of_buckets; + int currNumBuckets = bucketsPerTable * currNumTables; + double new_num_of_buckets = currNumBuckets + (double)(currNumBuckets+1)/(RTL_-1); + double idealLoadFactor = RTL_ - 1; + + double currNumElements = (double)(stats_->get_total_elements ()); + double currentLoadFactor = currNumElements / currNumBuckets; + double addPercentage = (idealLoadFactor - currentLoadFactor) / idealLoadFactor; + + new_num_of_tables = (int)(ceil(new_num_of_buckets / (double)bucketsPerTable)); + + double extraFraction = addPercentage * new_num_of_buckets; if (extraFraction < 0) extraFraction *= -1; - - new_num_of_buckets = (int)(ceil(new_num_of_buckets + extraFraction * tuningKnob)); - new_num_of_tables = (int)(ceil(new_num_of_buckets / (double)bucketsPerTable)); - - if(new_num_of_tables > this->max_tables_) + + new_num_of_buckets = (int)(ceil(new_num_of_buckets + extraFraction * tuningKnob)); + new_num_of_tables = (int)(ceil(new_num_of_buckets / (double)bucketsPerTable)); + + if(new_num_of_tables > (int)this->max_tables_) new_num_of_tables = this->max_tables_; if(new_num_of_buckets > this->buckets_per_table_) new_num_of_buckets = this->buckets_per_table_; - this->number_of_tables_ = new_num_of_tables; - this->buckets_per_table_ = new_num_of_buckets; + this->number_of_tables_ = (size_t)new_num_of_tables; + this->buckets_per_table_ = (size_t)new_num_of_buckets; - return (new ACE_Hash_Map_RT_POD (new_num_of_tables, *(new ACE_Hash_Map_RT_Hash_Function(new_num_of_tables, bucketsPerTable)))); + return (new ACE_Hash_Map_RT_POD (new_num_of_tables, *(new ACE_Hash_Map_RT_Hash_Function(new_num_of_tables, bucketsPerTable)))); } template size_t @@ -621,19 +643,19 @@ ACE_Hash_Map_RT_Visitor::proce LITEM* item = bucket.head_; // head doesnt have an entry this->mtfPrev_ = bucket.head_; // prev is head until we step forward - + while( item != (bucket.last_) ) // all ListItems have a next except last { item = item->next_; visit(item); // so let's visit that next_ ListItem - + if(is_found() == 0) // If we havent found the one we are looking for, this->mtfPrev_ = item; // then save the one we are on (the 'previous'). - // After we find the one we want, we dont want to overwrite + // After we find the one we want, we dont want to overwrite // our mtfPrev_ ptr anymore } done(bucket); - + return 0; } @@ -691,12 +713,12 @@ ACE_Hash_Map_RT_Put_Visitor::d if (is_found() == 0) // if we havent found what we're looking for { // then bind a new one ENTRY entry = ENTRY(this->ext_id_, - this->int_id_); - + this->int_id_); + bucket.prepend(entry); - + LITEM litem = LITEM (&entry, - bucket.head_->next_); + bucket.head_->next_); found_key(&litem); @@ -704,17 +726,17 @@ ACE_Hash_Map_RT_Put_Visitor::d if (manager_->is_stable() == 0) { - this->manager_->stats_->compare_max_chain(bucket.get_length()); + this->manager_->stats_->compare_max_chain(bucket.get_length()); if (bucket.get_length() >= this->manager_->RTL_) { POD* pod = this->manager_->create_POD(); if (pod != 0) this->manager_->change_POD(*pod); - } + } } return 0; } - + return -1; } @@ -748,16 +770,16 @@ ACE_Hash_Map_RT_Remove_Visitor { if (this->found_ == bucket.last_) bucket.last_ = this->mtfPrev_; - + this->mtfPrev_->next_ = this->get_found().next_; - + delete this->found_; this->found_ = 0; - + bucket.decr_length(); this->manager_->stats_->decr_total_elements(); } - + return 0; } diff --git a/ace/Hash_Map_Manager_RT_T.h b/ace/Hash_Map_Manager_RT_T.h index a873d4940f1..7f4606dc9b1 100644 --- a/ace/Hash_Map_Manager_RT_T.h +++ b/ace/Hash_Map_Manager_RT_T.h @@ -24,6 +24,17 @@ #include "Functor.h" #include "Log_Msg.h" +// forward declarations +class ACE_Allocator; +template class ACE_Hash_Map_RT_Manager_Ex; +template class ACE_Hash_Map_RT_Clean_Manager; +template class ACE_Hash_Map_RT_Put_Visitor; +template class ACE_Hash_Map_RT_Clean_Visitor; +template class ACE_Hash_Map_RT_Remove_Visitor; +template class ACE_Hash_Map_RT_Searching_Visitor; +template class ACE_Hash_Map_RT_Visitor; +template class ACE_Hash_Map_RT_Bucket; + /** * @class ACE_Hash_Map_RT_Coord * @@ -35,27 +46,27 @@ public: // = Initialization and termination methods. /// Constructor ACE_Hash_Map_RT_Coord (int table, int bucket); - + /// Destructor ~ACE_Hash_Map_RT_Coord (void); - + // = Accessor and mutator methods /// Return int table int get_table (void); - + /// Return int bucket int get_bucket (void); - + /// Set int table to new_table_number, return 0 for sucess. int set_table (int new_table_number); - + /// Set int bucket to new_bucket_number, return 0 for sucess. int set_bucket (int new_bucket_number); - + private: /// Position relative to the hash_map of which table the ListItem is in. int table_; - + /// Position relative to the table_ of which Bucket the ListItem is in. int bucket_; }; @@ -65,7 +76,7 @@ private: * * @brief A class that holds the templated HASH_KEY and does the actual hashing. */ -template +template class ACE_Hash_Map_RT_Hash_Function { public: @@ -74,25 +85,25 @@ public: /// Constructor ACE_Hash_Map_RT_Hash_Function (int number_of_tables, int buckets_per_table); - + /// Destructor ~ACE_Hash_Map_RT_Hash_Function (void); /// Take an EXT_ID and hash it, returning a ACE_Hash_Map_RT_Coord& int hash (const EXT_ID& ext_id, ACE_Hash_Map_RT_Coord& coord); - + private: /// Internal function that does the actual hashing int hash_i (int key, ACE_Hash_Map_RT_Coord& coord); - + /// The number of tables that are available. size_t max_tables_; - + /// Number of buckets in each table. size_t buckets_per_table_; - + /// Function object used for hashing keys. HASH_KEY hash_key_; }; @@ -100,11 +111,11 @@ private: /** * @class ACE_Hash_Map_RT_POD * - * @brief "Point Of Design" knows when to change Hash_Functions, and how many - * tables there are currently. A nre POD is created when the number + * @brief "Point Of Design" knows when to change Hash_Functions, and how many + * tables there are currently. A nre POD is created when the number * of tables is no longer enough. */ -template +template class ACE_Hash_Map_RT_POD { @@ -112,27 +123,27 @@ public: // = Initialization and termination methods. /// Constructor ACE_Hash_Map_RT_POD (int num_of_tables, - ACE_Hash_Map_RT_Hash_Function& func); - + ACE_Hash_Map_RT_Hash_Function& func); + /// Destructor ~ACE_Hash_Map_RT_POD (void); - - /// All hash requests will come through the POD, which will pass them to the + + /// All hash requests will come through the POD, which will pass them to the /// ACE_Hash_Map_RT_Hash_Function int hash (const EXT_ID& exit_id, ACE_Hash_Map_RT_Coord& coord); - + // = Accessor and mutator methods /// Get the number of available tables of this POD size_t get_num_tables(void); - + private: /// The number of available tables int num_tables_; - + /// the ACE_Hash_Map_RT_Hash_Function that does the hashing for this POD - ACE_Hash_Map_RT_Hash_Function& func_; - + ACE_Hash_Map_RT_Hash_Function& func_; + }; /** @@ -142,7 +153,7 @@ private: * Each Entry will be contained inside a ACE_Hash_Map_RT_ListItem, and * a Bucket is a list of ACE_Hash_Map_RT_ListItem s. */ -template +template class ACE_Hash_Map_RT_Entry { public: @@ -150,26 +161,26 @@ public: /// Constructor. ACE_Hash_Map_RT_Entry (const EXT_ID& ext_id, const INT_ID& int_id); - + ACE_Hash_Map_RT_Entry (void); - + # if ! defined (ACE_HAS_BROKEN_NOOP_DTORS) /// Destructor. ~ACE_Hash_Map_RT_Entry (void); #endif /* ! defined (ACE_HAS_BROKEN_NOOP_DTORS) */ - - // = Accessor and mutator methods + + // = Accessor and mutator methods EXT_ID& get_ext_id (void); - + INT_ID& get_int_id (void); - + void set_ext_id (EXT_ID); - + void set_int_id (INT_ID); - + /// Key used to look up an entry. EXT_ID ext_id_; - + /// The contents (value) of the entry. INT_ID int_id_; }; @@ -180,46 +191,61 @@ public: * @brief Has an Entry, and a pointer to the next ListItem in the Bucket. * A Bucket stores ListItems. A ListItem has an Entry. Entries have (key, value). */ -template +template class ACE_Hash_Map_RT_ListItem { -public: - typedef ACE_Hash_Map_RT_ListItem LITEM; - typedef ACE_Hash_Map_RT_Entry ENTRY; - + typedef ACE_Hash_Map_RT_ListItem LITEM; + typedef ACE_Hash_Map_RT_Entry ENTRY; + + friend class ACE_Hash_Map_RT_Manager_Ex; + friend class ACE_Hash_Map_RT_Put_Visitor; + friend class ACE_Hash_Map_RT_Clean_Visitor; + friend class ACE_Hash_Map_RT_Visitor; + friend class ACE_Hash_Map_RT_Remove_Visitor; + friend class ACE_Hash_Map_RT_Searching_Visitor; + friend class ACE_Hash_Map_RT_Bucket; + +protected: // = Initialization and termination methods. /// Constructors ACE_Hash_Map_RT_ListItem (ENTRY* entry, LITEM* next); - + // Default constructor ACE_Hash_Map_RT_ListItem (void); /// Destructor ~ACE_Hash_Map_RT_ListItem (void); - + /// The Entry object ENTRY* entry_; - + /// Pointer to the next item - ACE_Hash_Map_RT_ListItem* next_; - + ACE_Hash_Map_RT_ListItem* next_; + }; + /** * @class ACE_Hash_Map_RT_Bucket * * @brief A Bucket has a list of ListItems. * A ListItem has an Entry. Entries have (key, value). */ -template +template class ACE_Hash_Map_RT_Bucket { + + typedef ACE_Hash_Map_RT_POD POD; + typedef ACE_Hash_Map_RT_ListItem LITEM; + typedef ACE_Hash_Map_RT_Entry ENTRY; + + friend class ACE_Hash_Map_RT_Manager_Ex; + friend class ACE_Hash_Map_RT_Visitor; + friend class ACE_Hash_Map_RT_Put_Visitor; + friend class ACE_Hash_Map_RT_Remove_Visitor; + public: - - typedef ACE_Hash_Map_RT_POD POD; - typedef ACE_Hash_Map_RT_ListItem LITEM; - typedef ACE_Hash_Map_RT_Entry ENTRY; // = Initialization and termination methods. /// Constructors @@ -229,43 +255,45 @@ public: /// Destructor ~ACE_Hash_Map_RT_Bucket (void); - + // = Accessor and mutator methods /// Get the current length of the Bucket (that is, how many ListItems are present) size_t get_length (void); int set_length (int new_length); - + /// Incr the current length by one. int incr_length (void); - + /// Decr the current length by one. int decr_length (void); int is_clean (POD& manager_POD); - /// Add a new ListItem (which will contain the passed Entry) to the front of this + /// Add a new ListItem (which will contain the passed Entry) to the front of this /// Bucket's list int prepend (ENTRY& entry); /// Return the POD //POD get_POD (void); - + /// Set the POD void set_POD (POD* pod); - + /// Create a new head, and set the POD to the passed one. int empty_bucket (POD* new_POD); - + +protected: + /// Pointer to the first element in the Bucket. /// This ListItem will never have a key, value. LITEM* head_; - + /// A pointer to the last ListItem in the Bucket. /// Initially this is set to the head_ LITEM* last_; -protected: + /// Initialises this Bucket, allocating memory int init_bucket_i (POD* pod); @@ -275,11 +303,9 @@ private: /// This Bucket's POD POD* curPOD_; - + }; -// forward declare -class ACE_Allocator; /** * @class ACE_Hash_Map_RT_Table @@ -288,20 +314,23 @@ class ACE_Allocator; * A hashmap has an array of Tables, a Table has an array of Buckets. * A Bucket stores ListItems. A ListItem has Entries. Entries have (key, value) */ -template +template class ACE_Hash_Map_RT_Table { + + typedef ACE_Hash_Map_RT_POD POD; + typedef ACE_Hash_Map_RT_Bucket BUCKET; + + friend class ACE_Hash_Map_RT_Bucket; + friend class ACE_Hash_Map_RT_Clean_Manager; + friend class ACE_Hash_Map_RT_Manager_Ex; + public: - - typedef ACE_Hash_Map_RT_POD POD; - typedef ACE_Hash_Map_RT_ListItem LITEM; - typedef ACE_Hash_Map_RT_Entry ENTRY; - typedef ACE_Hash_Map_RT_Bucket BUCKET; - - friend class ACE_Hash_Map_RT_Bucket; - + +protected: + // = Initialization and termination methods. - //. Constructor + //. Constructor ACE_Hash_Map_RT_Table (ACE_Allocator* allocator, size_t buckets_per_table, POD* pod); @@ -311,27 +340,23 @@ public: /// Destructor ~ACE_Hash_Map_RT_Table(void); - + // = Accessor and mutator methods /// Pass the Bucket at Table[loc] back through the BUCKET& bucket, return 0 for sucess. int get_bucket (int loc, BUCKET& bucket); - /// Return the Bucket at Table[loc] - BUCKET& get_bucket (int loc); - int get_tablesize (void); /// Increase tablesize by one. void incr_tablesize (void); - + /// Decrease tablesize by num_removed void set_tablesize (int num_removed); - - /// Get the array of Buckets - BUCKET* get_bucket_array (void); -protected: + /// Return the Bucket at Table[loc] + BUCKET& get_bucket (int loc); + /// Initialise the Table, allocating memory and calling constructors for the Buckets int init_table_i (ACE_Allocator* allocator, size_t buckets_per_table, @@ -344,13 +369,50 @@ private: int numBuckets; }; -// forward decl the manager -template class ACE_Hash_Map_RT_Manager_Ex; + /* + * @class ACE_Hash_Map_RT_Clean_Manager + * + * @brief This class walks through the tables, and buckets looking for ListItems that are in the wrong + * position according to the current POD. When it reaches the end (more_to_do() = false) it is + * killed, and another one is created which starts from the beginning all over again. + * + */ +template +class ACE_Hash_Map_RT_Clean_Manager +{ + typedef ACE_Hash_Map_RT_Bucket BUCKET; + + friend class ACE_Hash_Map_RT_Manager_Ex; + +public: + +protected: + + ///Constructor + ACE_Hash_Map_RT_Clean_Manager (ACE_Hash_Map_RT_Manager_Ex* thismanager); + + /// calls clean visitor.process_bucket on the next bucket in the current table. then goes to the next table, and + /// continues until more_to_do() == false + ACE_Hash_Map_RT_Clean_Manager* incremental_clean (void); + +private: + /// if we havent retired the old POD and we're not done with the last table, then there is more to do. + int more_to_do (void); + + /// A reference to the ACE_Hash_Map_RT_Manager_Ex + ACE_Hash_Map_RT_Manager_Ex* manager_; + + /// the current table which is being cleaned + size_t cur_table_; + + /// the current bucket in cur_table_ that is being cleaned. + size_t cur_bucket_; +}; /** * @class ACE_Hash_Map_RT_Visitor * - * @brief Parent class of all visitors that will traverse the Tables and Buckets. The visitors walk through the buckets looking for + * @brief Parent class of all visitors that will traverse the Tables and Buckets. The visitors walk through the buckets looking for * a certain key, and when (if) it is found, the appropritate visitor takes action (by returning the value, or deleting for example.). * The Visitors are responsible for the actual inserting or deleting that bind() or unbind() do. * These are not iterators, the simply perform their respective function at the appropriate place in the map. @@ -358,33 +420,34 @@ template class ACE_Hash_Map_RT_Visitor { + typedef ACE_Hash_Map_RT_ListItemLITEM; + typedef ACE_Hash_Map_RT_Bucket BUCKET; + + friend class ACE_Hash_Map_RT_Manager_Ex; + friend class ACE_Hash_Map_RT_Clean_Manager; + public: - typedef ACE_Hash_Map_RT_POD POD; - typedef ACE_Hash_Map_RT_ListItemLITEM; - typedef ACE_Hash_Map_RT_EntryENTRY; - typedef ACE_Hash_Map_RT_Table TABLE; - typedef ACE_Hash_Map_RT_Bucket BUCKET; +protected: virtual BUCKET* start(BUCKET* bucket) = 0; virtual int visit(LITEM* litem) = 0; - + virtual int done(BUCKET& bucket) = 0; - + virtual void found_key (LITEM* litem); /// Walks through the bucket, calling start() (then visit() only if the appropriate key has been found) - /// then done() on each ListItem. start and done only modify the map if is_found() is true, indicating + /// then done() on each ListItem. start and done only modify the map if is_found() is true, indicating /// that the key has been found. int process_bucket(BUCKET& bucket); /// Returns 0 for false, 1 for true by comparing found_ to '0' int is_found (void); - + /// return found_ LITEM& get_found (void); -protected: /// A pointer to the last ListItem we touched. /// As we search for the element we are looking for, this pointer is incremented accordingly. /// Its used for removing ListItems from the Bucket without keeping @@ -407,9 +470,18 @@ protected: template class ACE_Hash_Map_RT_Clean_Visitor : public ACE_Hash_Map_RT_Visitor { + typedef ACE_Hash_Map_RT_ListItemLITEM; + typedef ACE_Hash_Map_RT_Bucket BUCKET; + + friend class ACE_Hash_Map_RT_Manager_Ex; + public: + +protected: ACE_Hash_Map_RT_Clean_Visitor (ACE_Hash_Map_RT_Manager_Ex* thismanager); + virtual ~ACE_Hash_Map_RT_Clean_Visitor (void); + /// Returns a copy of the contents of that Bucket right before it empties the Bucket. BUCKET* start (BUCKET* bucket); @@ -431,31 +503,40 @@ public: template class ACE_Hash_Map_RT_Searching_Visitor : public ACE_Hash_Map_RT_Visitor { + typedef ACE_Hash_Map_RT_POD POD; + typedef ACE_Hash_Map_RT_ListItemLITEM; + typedef ACE_Hash_Map_RT_EntryENTRY; + typedef ACE_Hash_Map_RT_Bucket BUCKET; + + friend class ACE_Hash_Map_RT_Manager_Ex; + public: +protected: + // = Initialization and termination methods. /// Constructor ACE_Hash_Map_RT_Searching_Visitor (const EXT_ID& entry, ACE_Hash_Map_RT_Manager_Ex* manager); - + /// Default constructor ACE_Hash_Map_RT_Searching_Visitor (void); - + /// Does nothing. BUCKET* start (BUCKET* bucket); - + /// Looks at the ListItem to see if its the one we are looking for. int visit (LITEM* litem); - + /// Does nothing. int done (BUCKET& bucket); /// the key that we're looking for const EXT_ID& ext_id_; - + ACE_Hash_Map_RT_Manager_Ex* manager_; }; - + /** * @class ACE_Hash_Map_RT_Put_Visitor * @@ -464,43 +545,61 @@ public: template class ACE_Hash_Map_RT_Put_Visitor : public ACE_Hash_Map_RT_Searching_Visitor { + typedef ACE_Hash_Map_RT_POD POD; + typedef ACE_Hash_Map_RT_ListItemLITEM; + typedef ACE_Hash_Map_RT_EntryENTRY; + typedef ACE_Hash_Map_RT_Bucket BUCKET; + + friend class ACE_Hash_Map_RT_Manager_Ex; + public: +protected: + // = Initialization and termination methods. /// Constructor - ACE_Hash_Map_RT_Put_Visitor(const EXT_ID& ext_id, + ACE_Hash_Map_RT_Put_Visitor(const EXT_ID& ext_id, const INT_ID& int_id, ACE_Hash_Map_RT_Manager_Ex* thismanager); - + virtual void found_key (LITEM* litem); - + /// Prepends the Entry that we want to insert onto the Bucket int done (BUCKET& bucket); - + private: - const INT_ID& int_id_; + const INT_ID& int_id_; }; /** - * @class ACE_Hash_Map_RT_Put_Visitor + * @class ACE_Hash_Map_RT_Get_Visitor * * @brief Gets the INT_ID from the Bucket where Searching_Visitor finds it. */ template class ACE_Hash_Map_RT_Get_Visitor : public ACE_Hash_Map_RT_Searching_Visitor { + typedef ACE_Hash_Map_RT_POD POD; + typedef ACE_Hash_Map_RT_ListItemLITEM; + typedef ACE_Hash_Map_RT_EntryENTRY; + typedef ACE_Hash_Map_RT_Bucket BUCKET; + + friend class ACE_Hash_Map_RT_Manager_Ex; + public: - + +protected: + // = Initialization and termination methods. /// Constructor - ACE_Hash_Map_RT_Get_Visitor(const EXT_ID& ext_id, + ACE_Hash_Map_RT_Get_Visitor(const EXT_ID& ext_id, INT_ID& int_id, ACE_Hash_Map_RT_Manager_Ex* thismanager); /// Calls compareMaxChain int done (BUCKET& bucket); - + private: INT_ID& int_id_; }; @@ -513,89 +612,77 @@ private: template class ACE_Hash_Map_RT_Remove_Visitor : public ACE_Hash_Map_RT_Searching_Visitor { + typedef ACE_Hash_Map_RT_POD POD; + typedef ACE_Hash_Map_RT_ListItemLITEM; + typedef ACE_Hash_Map_RT_EntryENTRY; + typedef ACE_Hash_Map_RT_Bucket BUCKET; + + friend class ACE_Hash_Map_RT_Manager_Ex; + public: +protected: + // = Initialization and termination methods. /// Constructor ACE_Hash_Map_RT_Remove_Visitor(const EXT_ID& ext_id, ACE_Hash_Map_RT_Manager_Ex* thismanager); - + /// Deletes the ListItem that we are looking for from the Bucket int done (BUCKET& bucket); - + }; + /* + * @class + * + * @brief + * + */ +template class ACE_Hash_Map_RT_StatsManager { + + friend class ACE_Hash_Map_RT_Manager_Ex; + friend class ACE_Hash_Map_RT_Put_Visitor; + friend class ACE_Hash_Map_RT_Get_Visitor; + friend class ACE_Hash_Map_RT_Remove_Visitor; + friend class ACE_Hash_Map_RT_Clean_Manager; + public: +protected: + // = Initialization and termination methods. /// Constructor ACE_Hash_Map_RT_StatsManager (void); /// Destructor ~ACE_Hash_Map_RT_StatsManager (void); - + int get_total_elements (void); - + int get_max_chain (void); - + /// Stores the greater of chain_size and the stats_manager's max_chain_ in the stats_manager's max_chain_ void compare_max_chain (int chain_size); - + /// max_chain_ = 0; void reset_max_chain (void); int incr_total_elements (void); - + int decr_total_elements (void); - + private: /// the longest list (which translates to the biggest Bucket's size) int max_chain_; - + /// the Sum of all the elements in all the Buckets (not including any Bucket->head_ because they dont hold an Entry) int total_elements_; }; - /* - * @class ACE_Hash_Map_RT_Clean_Manager - * - * @brief This class walks through the tables, and buckets looking for ListItems that are in the wrong - * position according to the current POD. When it reaches the end (more_to_do() = false) it is - * killed, and another one is created which starts from the beginning all over again. - * - */ -template -class ACE_Hash_Map_RT_Clean_Manager -{ - typedef ACE_Hash_Map_RT_Table TABLE; - typedef ACE_Hash_Map_RT_Bucket BUCKET; - -public: - - ///Constructor - ACE_Hash_Map_RT_Clean_Manager (ACE_Hash_Map_RT_Manager_Ex* thismanager); - - /// calls clean visitor.process_bucket on the next bucket in the current table. then goes to the next table, and - /// continues until more_to_do() == false - ACE_Hash_Map_RT_Clean_Manager* incremental_clean (void); - -private: - /// if we havent retired the old POD and we're not done with the last table, then there is more to do. - int more_to_do (void); - - /// A reference to the ACE_Hash_Map_RT_Manager_Ex - ACE_Hash_Map_RT_Manager_Ex* manager_; - - /// the current table which is being cleaned - size_t cur_table_; - - /// the current bucket in cur_table_ that is being cleaned. - size_t cur_bucket_; -}; - // Forward decl. class ACE_Allocator; @@ -615,15 +702,15 @@ class ACE_Allocator; template class ACE_Hash_Map_RT_Manager_Ex { -public: + typedef EXT_ID KEY; typedef INT_ID VALUE; typedef ACE_Hash_Map_RT_Coord COORD; - typedef ACE_Hash_Map_RT_POD POD; - typedef ACE_Hash_Map_RT_Entry ENTRY; - typedef ACE_Hash_Map_RT_Table TABLE; - typedef ACE_Hash_Map_RT_Bucket BUCKET; - typedef ACE_Hash_Map_RT_ListItem LITEM; + typedef ACE_Hash_Map_RT_POD POD; + typedef ACE_Hash_Map_RT_Entry ENTRY; + typedef ACE_Hash_Map_RT_Table TABLE; + typedef ACE_Hash_Map_RT_Bucket BUCKET; + typedef ACE_Hash_Map_RT_ListItem LITEM; typedef ACE_Hash_Map_RT_Clean_Manager CLEAN; typedef ACE_Hash_Map_RT_Clean_Visitor CLEANV; @@ -633,15 +720,17 @@ public: friend class ACE_Hash_Map_RT_Remove_Visitor; friend class ACE_Hash_Map_RT_Clean_Visitor; +public: + // = Initialization and termination methods. - + /// Initialize a with default size. - ACE_Hash_Map_RT_Manager_Ex (size_t buckets_per_table, + ACE_Hash_Map_RT_Manager_Ex (size_t buckets_per_table, size_t RTL, size_t max_tables, ACE_Allocator *alloc = 0, size_t clean_rate = 3); - + /// Cleanup the . ~ACE_Hash_Map_RT_Manager_Ex (void); @@ -653,40 +742,40 @@ public: */ int bind (const EXT_ID &item, const INT_ID &int_id); - + /// Return the value associated with the key. int find (const EXT_ID &ext_id, INT_ID &int_id); - + /// Remove a key, value pair from the map int unbind (const EXT_ID &ext_id); - + /// find a the coord of the bucket where item is located according to this POD int find_bucket (POD* pod, const EXT_ID &item, COORD& coord); - + + /// True if this->oldPOD_ != 0 + int is_stable (void); + + size_t get_cleaning_rate (void); + + /// Calls close_i while holding a write lock + int close (void); + +protected: /// Return the bucket where the item is located according to this POD BUCKET& find_bucket (POD* pod, const EXT_ID &item); - - POD* get_POD (void); - /// True if this->oldPOD_ != 0 - int is_stable (void); - /// Return table at table_[loc] TABLE& get_table (size_t loc); - size_t get_cleaning_rate (void); + POD* get_POD (void); -protected: /// Retire the POD to old_POD and make this new_POD be the current POD for the hashmap int change_POD (POD& new_POD); - /// Calls close_i while holding a write lock - int close_manager (void); - ///Iterate through the entire map calling the destuctor of each . int remove_all_i (void); @@ -705,7 +794,7 @@ protected: ///de allocates the buckets and the table array int close_i (void); - + ///finds the item, then lets the visitor do its thing (bind, unbind, find) int locate_i (const EXT_ID& item, ACE_Hash_Map_RT_Searching_Visitor& visitor, @@ -714,11 +803,8 @@ protected: /// allocates memory and creates all tables and local variables. int open_i (size_t buckets_per_table, ACE_Allocator *alloc); - - /// Pointer to a memory allocator. - ACE_Allocator *allocator_; - ACE_Hash_Map_RT_StatsManager* stats_; + ACE_Hash_Map_RT_StatsManager* stats_; private: /// a math function that gets the smallest size_t larger than the double @@ -734,23 +820,27 @@ private: /// Rehash Trigger Length size_t RTL_; - - /// how many tables we have room for + + /// how many tables we have room for size_t max_tables_; - - POD* curPOD_; - - POD* oldPOD_; - - ACE_Hash_Map_RT_Clean_Visitor* clean_vis_; - ACE_Hash_Map_RT_Clean_Manager* clean_; + /// Pointer to a memory allocator. + ACE_Allocator *allocator_; /// If the user is willing to put up with increased overhead in order /// to clean the table in fewer operations, this will tell the /// CleanManager to rehash additional buckets on each operation. size_t cleaning_rate_; - + + + POD* curPOD_; + + POD* oldPOD_; + + ACE_Hash_Map_RT_Clean_Visitor* clean_vis_; + + ACE_Hash_Map_RT_Clean_Manager* clean_; + /// Synchronization variable for the MT_SAFE . ACE_LOCK lock_; diff --git a/ace/Hash_Map_Manager_RT_T.inl b/ace/Hash_Map_Manager_RT_T.inl index befcc8ce428..54ee6360c78 100644 --- a/ace/Hash_Map_Manager_RT_T.inl +++ b/ace/Hash_Map_Manager_RT_T.inl @@ -6,21 +6,21 @@ #include "Synch.h" -ACE_INLINE +ACE_INLINE int ACE_Hash_Map_RT_Coord::get_table (void) { return this->table_; } -ACE_INLINE +ACE_INLINE int ACE_Hash_Map_RT_Coord::get_bucket (void) { return this->bucket_; } -ACE_INLINE +ACE_INLINE int ACE_Hash_Map_RT_Coord::set_table (int newtables) { @@ -28,7 +28,7 @@ ACE_Hash_Map_RT_Coord::set_table (int newtables) return 0; } -ACE_INLINE +ACE_INLINE int ACE_Hash_Map_RT_Coord::set_bucket (int newbuckets) { @@ -39,94 +39,94 @@ ACE_Hash_Map_RT_Coord::set_bucket (int newbuckets) //***************************************************************/ -template ACE_INLINE +template ACE_INLINE int -ACE_Hash_Map_RT_POD::hash (const EXT_ID& ext_id, ACE_Hash_Map_RT_Coord& coord) +ACE_Hash_Map_RT_POD::hash (const EXT_ID& ext_id, ACE_Hash_Map_RT_Coord& coord) { return this->func_.hash(ext_id, coord); } -template ACE_INLINE +template ACE_INLINE size_t -ACE_Hash_Map_RT_POD::get_num_tables() +ACE_Hash_Map_RT_POD::get_num_tables() { return this->num_tables_; } //***************************************************************/ -template ACE_INLINE +template ACE_INLINE void -ACE_Hash_Map_RT_Entry::set_ext_id (EXT_ID id) -{ +ACE_Hash_Map_RT_Entry::set_ext_id (EXT_ID id) +{ this->ext_id_ = id; } -template ACE_INLINE +template ACE_INLINE void -ACE_Hash_Map_RT_Entry::set_int_id (INT_ID id) -{ +ACE_Hash_Map_RT_Entry::set_int_id (INT_ID id) +{ this->int_id_ = id; } -template ACE_INLINE +template ACE_INLINE EXT_ID& -ACE_Hash_Map_RT_Entry::get_ext_id () -{ +ACE_Hash_Map_RT_Entry::get_ext_id () +{ return this->ext_id_; } -template ACE_INLINE +template ACE_INLINE INT_ID& -ACE_Hash_Map_RT_Entry::get_int_id () -{ +ACE_Hash_Map_RT_Entry::get_int_id () +{ return this->int_id_; } //***************************************************************/ -template ACE_INLINE +template ACE_INLINE size_t -ACE_Hash_Map_RT_Bucket::get_length (void) +ACE_Hash_Map_RT_Bucket::get_length (void) { return this->length_; } -template ACE_INLINE +template ACE_INLINE int -ACE_Hash_Map_RT_Bucket::set_length (int new_length) +ACE_Hash_Map_RT_Bucket::set_length (int new_length) { this->length_ = new_length; return 0; } -template ACE_INLINE +template ACE_INLINE int -ACE_Hash_Map_RT_Bucket::incr_length (void) +ACE_Hash_Map_RT_Bucket::incr_length (void) { return ++this->length_; } -template ACE_INLINE +template ACE_INLINE int -ACE_Hash_Map_RT_Bucket::decr_length (void) +ACE_Hash_Map_RT_Bucket::decr_length (void) { return --this->length_; } -template ACE_INLINE +template ACE_INLINE int -ACE_Hash_Map_RT_Bucket::is_clean (POD& manager_POD) +ACE_Hash_Map_RT_Bucket::is_clean (POD& manager_POD) { return curPOD_ == &manager_POD; } -template ACE_INLINE +template ACE_INLINE int -ACE_Hash_Map_RT_Bucket::empty_bucket (POD* newPOD) +ACE_Hash_Map_RT_Bucket::empty_bucket (POD* newPOD) { this->head_ = new LITEM(); - this->last_ = this->head_; + this->last_ = this->head_; this->length_ = 0; curPOD_ = newPOD; @@ -134,77 +134,116 @@ ACE_Hash_Map_RT_Bucket::empty_bucket (POD* newPOD) return 0; } -template ACE_INLINE +template ACE_INLINE void -ACE_Hash_Map_RT_Bucket::set_POD (POD* pod) +ACE_Hash_Map_RT_Bucket::set_POD (POD* pod) { curPOD_ = pod; } //***************************************************************/ -template ACE_INLINE +template ACE_INLINE int -ACE_Hash_Map_RT_Table::get_bucket (int loc, +ACE_Hash_Map_RT_Table::get_bucket (int loc, BUCKET& bucket) { bucket = get_bucket(loc); return 0; } -template ACE_INLINE +template ACE_INLINE void -ACE_Hash_Map_RT_Table::incr_tablesize (void) +ACE_Hash_Map_RT_Table::incr_tablesize (void) { ++this->numBuckets; } -template ACE_INLINE +template ACE_INLINE int -ACE_Hash_Map_RT_Table::get_tablesize (void) +ACE_Hash_Map_RT_Table::get_tablesize (void) { return this->numBuckets; } -template ACE_INLINE +template ACE_INLINE void -ACE_Hash_Map_RT_Table::set_tablesize (int numRemoved) +ACE_Hash_Map_RT_Table::set_tablesize (int numRemoved) { this->numBuckets = numRemoved; } -template ACE_INLINE -ACE_Hash_Map_RT_Bucket& -ACE_Hash_Map_RT_Table::get_bucket (int loc) +template ACE_INLINE +ACE_Hash_Map_RT_Bucket& +ACE_Hash_Map_RT_Table::get_bucket (int loc) { return this->buckets_[loc]; } -template ACE_INLINE -ACE_Hash_Map_RT_Bucket* -ACE_Hash_Map_RT_Table::get_bucket_array (void) + +//***************************************************************/ + +template ACE_INLINE +int +ACE_Hash_Map_RT_StatsManager::get_total_elements (void) { - return this->buckets_; + return this->total_elements_; } +template ACE_INLINE +int +ACE_Hash_Map_RT_StatsManager::get_max_chain (void) +{ + return this->max_chain_; +} -//***************************************************************/ +template ACE_INLINE +void +ACE_Hash_Map_RT_StatsManager::compare_max_chain (int chainSize) +{ + if (chainSize > this->max_chain_) + this->max_chain_ = chainSize; +} -ACE_INLINE +template ACE_INLINE +void +ACE_Hash_Map_RT_StatsManager::reset_max_chain (void) +{ + this->max_chain_ = 0; +} + +template ACE_INLINE +int +ACE_Hash_Map_RT_StatsManager::incr_total_elements (void) +{ + compare_max_chain (++this->total_elements_); + return this->total_elements_; +} + +template ACE_INLINE +int +ACE_Hash_Map_RT_StatsManager::decr_total_elements (void) +{ + return --this->total_elements_; +} + + +/* +ACE_INLINE int ACE_Hash_Map_RT_StatsManager::get_total_elements (void) { return this->total_elements_; } -ACE_INLINE +ACE_INLINE int ACE_Hash_Map_RT_StatsManager::get_max_chain (void) { return this->max_chain_; } -ACE_INLINE +ACE_INLINE void ACE_Hash_Map_RT_StatsManager::compare_max_chain (int chainSize) { @@ -212,14 +251,14 @@ ACE_Hash_Map_RT_StatsManager::compare_max_chain (int chainSize) this->max_chain_ = chainSize; } -ACE_INLINE +ACE_INLINE void ACE_Hash_Map_RT_StatsManager::reset_max_chain (void) { this->max_chain_ = 0; } -ACE_INLINE +ACE_INLINE int ACE_Hash_Map_RT_StatsManager::incr_total_elements (void) { @@ -227,16 +266,16 @@ ACE_Hash_Map_RT_StatsManager::incr_total_elements (void) return this->total_elements_; } -ACE_INLINE +ACE_INLINE int ACE_Hash_Map_RT_StatsManager::decr_total_elements (void) { return --this->total_elements_; } - +*/ //***************************************************************/ -template ACE_INLINE +template ACE_INLINE int ACE_Hash_Map_RT_Manager_Ex::size (void) { @@ -253,22 +292,22 @@ ACE_Hash_Map_RT_Manager_Ex::bi INT_ID dummy = int_id; ACE_Hash_Map_RT_Put_Visitor visitor (ext_id, - int_id, - this); + int_id, + this); return locate_i(ext_id, - visitor, + visitor, dummy); return 0; } -template ACE_INLINE -ACE_Hash_Map_RT_Table& +template ACE_INLINE +ACE_Hash_Map_RT_Table& ACE_Hash_Map_RT_Manager_Ex::get_table (size_t loc) { return table_[loc]; } -template ACE_INLINE +template ACE_INLINE int ACE_Hash_Map_RT_Manager_Ex::find (const EXT_ID &ext_id, INT_ID &int_id) @@ -276,30 +315,30 @@ ACE_Hash_Map_RT_Manager_Ex::fi ACE_READ_GUARD_RETURN (ACE_LOCK, ace_mon, this->lock_, -1); - ACE_Hash_Map_RT_Get_Visitor visitor (ext_id, - int_id, - this); - return locate_i(ext_id, + ACE_Hash_Map_RT_Get_Visitor visitor (ext_id, + int_id, + this); + return locate_i(ext_id, visitor, int_id); } -template ACE_INLINE +template ACE_INLINE int ACE_Hash_Map_RT_Manager_Ex::unbind (const EXT_ID &ext_id) { ACE_WRITE_GUARD_RETURN (ACE_LOCK, ace_mon, this->lock_, -1); - + INT_ID dummy; ACE_Hash_Map_RT_Remove_Visitor visitor (ext_id, - this); - return locate_i(ext_id, + this); + return locate_i(ext_id, visitor, dummy); } -template ACE_INLINE +template ACE_INLINE int ACE_Hash_Map_RT_Manager_Ex::find_bucket (POD* pod, const EXT_ID &ext_id, @@ -309,34 +348,34 @@ ACE_Hash_Map_RT_Manager_Ex::fi return 1; } -template ACE_INLINE -ACE_Hash_Map_RT_Bucket& +template ACE_INLINE +ACE_Hash_Map_RT_Bucket& ACE_Hash_Map_RT_Manager_Ex::find_bucket (POD* pod, const EXT_ID &ext_id) { ACE_Hash_Map_RT_Coord coord = ACE_Hash_Map_RT_Coord(0,0); pod->hash(ext_id, coord); - return get_table(coord.get_table()).get_bucket(coord.get_bucket()); + return this->get_table(coord.get_table()).get_bucket(coord.get_bucket()); } -template ACE_INLINE +template ACE_INLINE int -ACE_Hash_Map_RT_Manager_Ex::change_POD (ACE_Hash_Map_RT_POD& newPOD) +ACE_Hash_Map_RT_Manager_Ex::change_POD (ACE_Hash_Map_RT_POD& newPOD) { this->oldPOD_ = this->curPOD_; this->curPOD_ = &newPOD; return 0; } -template ACE_INLINE -ACE_Hash_Map_RT_POD* +template ACE_INLINE +ACE_Hash_Map_RT_POD* ACE_Hash_Map_RT_Manager_Ex::get_POD (void) { return curPOD_; } -template ACE_INLINE +template ACE_INLINE int ACE_Hash_Map_RT_Manager_Ex::is_stable (void) { @@ -352,14 +391,14 @@ ACE_Hash_Map_RT_Manager_Ex::ha } template ACE_INLINE -int +int ACE_Hash_Map_RT_Manager_Ex::rehash (ENTRY& entry) { find_bucket(curPOD_, entry.get_ext_id()).prepend(entry); return 0; } -template ACE_INLINE +template ACE_INLINE size_t ACE_Hash_Map_RT_Manager_Ex::get_cleaning_rate (void) { @@ -368,22 +407,22 @@ ACE_Hash_Map_RT_Manager_Ex::ge //***************************************************************/ -template ACE_INLINE +template ACE_INLINE int ACE_Hash_Map_RT_Visitor::is_found (void) { return (this->found_ != 0); } -template ACE_INLINE +template ACE_INLINE void ACE_Hash_Map_RT_Visitor::found_key (LITEM* litem) { this->found_ = litem; } -template ACE_INLINE -ACE_Hash_Map_RT_ListItem& +template ACE_INLINE +ACE_Hash_Map_RT_ListItem& ACE_Hash_Map_RT_Visitor::get_found (void) { return *this->found_; @@ -391,7 +430,7 @@ ACE_Hash_Map_RT_Visitor::get_f //***************************************************************/ -template ACE_INLINE +template ACE_INLINE int ACE_Hash_Map_RT_Clean_Visitor::visit (LITEM* litem) { @@ -399,18 +438,18 @@ ACE_Hash_Map_RT_Clean_Visitor: return 0; } -template ACE_INLINE -ACE_Hash_Map_RT_Bucket* +template ACE_INLINE +ACE_Hash_Map_RT_Bucket* ACE_Hash_Map_RT_Clean_Visitor::start (BUCKET* bucket) -{ +{ dead_bucket = *bucket; - + (*bucket).empty_bucket(this->manager_->get_POD()); - + return &dead_bucket; } -template ACE_INLINE +template ACE_INLINE int ACE_Hash_Map_RT_Clean_Visitor::done (BUCKET& bucket) { @@ -420,14 +459,14 @@ ACE_Hash_Map_RT_Clean_Visitor: //***************************************************************/ -template ACE_INLINE -ACE_Hash_Map_RT_Bucket* +template ACE_INLINE +ACE_Hash_Map_RT_Bucket* ACE_Hash_Map_RT_Searching_Visitor::start (BUCKET* bucket) { return bucket; } -template ACE_INLINE +template ACE_INLINE int ACE_Hash_Map_RT_Searching_Visitor::done (BUCKET&) { @@ -436,7 +475,7 @@ ACE_Hash_Map_RT_Searching_Visitor ACE_INLINE +template ACE_INLINE int ACE_Hash_Map_RT_Get_Visitor::done (BUCKET& bucket) { diff --git a/tests/Hash_Map_Manager_RT_Test.cpp b/tests/Hash_Map_Manager_RT_Test.cpp index 35af0786d91..9b52b0ff0de 100644 --- a/tests/Hash_Map_Manager_RT_Test.cpp +++ b/tests/Hash_Map_Manager_RT_Test.cpp @@ -14,16 +14,20 @@ #include "ace/Malloc_T.h" #include "ace/Synch.h" -ACE_RCSID(tests, Hash_Map_Manager_Test, "$Id$") +ACE_RCSID(tests, Hash_Map_Manager_RT_Test, "$Id$") static const size_t STRING_TABLE_ENTRIES = 18; static const size_t MAX_HASH = 18; typedef ACE_Hash_Map_RT_Table HASH_STRING_TABLE; typedef ACE_Hash_Map_RT_Bucket HASH_STRING_BUCKET; @@ -198,7 +202,7 @@ static String_Table string_table[] = { ACE_TEXT ("thirfour"), ACE_TEXT ("343434") - }, + }, { ACE_TEXT ("thirfive"), ACE_TEXT ("353535") @@ -263,7 +267,7 @@ static String_Table string_table[] = ACE_TEXT ("goodbye "), ACE_TEXT ("auf wiedersehen") }, - { + { 0, 0 } @@ -323,7 +327,7 @@ run_test (void) ACE_DEBUG ((LM_DEBUG, ACE_TEXT ("\n"))); - + // remove the first element hash.unbind (string_table[0].key_); ACE_DEBUG ((LM_DEBUG, @@ -358,7 +362,7 @@ run_test (void) ACE_TEXT ("%p failed for %s \n"), ACE_TEXT ("bind"), string_table[5].key_), -1); - + ACE_DEBUG ((LM_DEBUG, ACE_TEXT ("putting five back \n\n"))); @@ -386,7 +390,7 @@ run_test (void) int ACE_TMAIN (int, ACE_TCHAR *[]) { - ACE_START_TEST (ACE_TEXT ("Hash_Map_Manager_Test")); + ACE_START_TEST (ACE_TEXT ("Hash_Map_Manager_RT_Test")); run_test (); -- cgit v1.2.1