diff options
Diffstat (limited to 'ace/Hash_Map_Manager_RT_T.h')
-rw-r--r-- | ace/Hash_Map_Manager_RT_T.h | 476 |
1 files changed, 283 insertions, 193 deletions
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 EXT_ID, class INT_ID, class HASH_KEY, class COMPARE_KEYS, class ACE_LOCK> class ACE_Hash_Map_RT_Manager_Ex; +template <class EXT_ID, class INT_ID, class HASH_KEY, class COMPARE_KEYS, class ACE_LOCK> class ACE_Hash_Map_RT_Clean_Manager; +template <class EXT_ID, class INT_ID, class HASH_KEY, class COMPARE_KEYS, class ACE_LOCK> class ACE_Hash_Map_RT_Put_Visitor; +template <class EXT_ID, class INT_ID, class HASH_KEY, class COMPARE_KEYS, class ACE_LOCK> class ACE_Hash_Map_RT_Clean_Visitor; +template <class EXT_ID, class INT_ID, class HASH_KEY, class COMPARE_KEYS, class ACE_LOCK> class ACE_Hash_Map_RT_Remove_Visitor; +template <class EXT_ID, class INT_ID, class HASH_KEY, class COMPARE_KEYS, class ACE_LOCK> class ACE_Hash_Map_RT_Searching_Visitor; +template <class EXT_ID, class INT_ID, class HASH_KEY, class COMPARE_KEYS, class ACE_LOCK> class ACE_Hash_Map_RT_Visitor; +template <class EXT_ID, class INT_ID, class HASH_KEY, class COMPARE_KEYS, class ACE_LOCK> 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 <class EXT_ID, class INT_ID, class HASH_KEY> +template <class EXT_ID, class INT_ID, class HASH_KEY, class COMPARE_KEYS, class ACE_LOCK> 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 <class EXT_ID, class INT_ID, class HASH_KEY> +template <class EXT_ID, class INT_ID, class HASH_KEY, class COMPARE_KEYS, class ACE_LOCK> 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<EXT_ID, INT_ID, HASH_KEY>& func); - + ACE_Hash_Map_RT_Hash_Function<EXT_ID, INT_ID, HASH_KEY, COMPARE_KEYS, ACE_LOCK>& 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<EXT_ID, INT_ID, HASH_KEY>& func_; - + ACE_Hash_Map_RT_Hash_Function<EXT_ID, INT_ID, HASH_KEY, COMPARE_KEYS, ACE_LOCK>& 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 <class EXT_ID, class INT_ID> +template <class EXT_ID, class INT_ID, class HASH_KEY, class COMPARE_KEYS, class ACE_LOCK> 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 <class EXT_ID, class INT_ID> +template <class EXT_ID, class INT_ID, class HASH_KEY, class COMPARE_KEYS, class ACE_LOCK> class ACE_Hash_Map_RT_ListItem { -public: - typedef ACE_Hash_Map_RT_ListItem<EXT_ID, INT_ID> LITEM; - typedef ACE_Hash_Map_RT_Entry<EXT_ID, INT_ID> ENTRY; - + typedef ACE_Hash_Map_RT_ListItem<EXT_ID, INT_ID, HASH_KEY, COMPARE_KEYS, ACE_LOCK> LITEM; + typedef ACE_Hash_Map_RT_Entry<EXT_ID, INT_ID, HASH_KEY, COMPARE_KEYS, ACE_LOCK> ENTRY; + + friend class ACE_Hash_Map_RT_Manager_Ex<EXT_ID, INT_ID, HASH_KEY, COMPARE_KEYS, ACE_LOCK>; + friend class ACE_Hash_Map_RT_Put_Visitor<EXT_ID, INT_ID, HASH_KEY, COMPARE_KEYS, ACE_LOCK>; + friend class ACE_Hash_Map_RT_Clean_Visitor<EXT_ID, INT_ID, HASH_KEY, COMPARE_KEYS, ACE_LOCK>; + friend class ACE_Hash_Map_RT_Visitor<EXT_ID, INT_ID, HASH_KEY, COMPARE_KEYS, ACE_LOCK>; + friend class ACE_Hash_Map_RT_Remove_Visitor<EXT_ID, INT_ID, HASH_KEY, COMPARE_KEYS, ACE_LOCK>; + friend class ACE_Hash_Map_RT_Searching_Visitor<EXT_ID, INT_ID, HASH_KEY, COMPARE_KEYS, ACE_LOCK>; + friend class ACE_Hash_Map_RT_Bucket<EXT_ID, INT_ID, HASH_KEY, COMPARE_KEYS, ACE_LOCK>; + +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<EXT_ID, INT_ID>* next_; - + ACE_Hash_Map_RT_ListItem<EXT_ID, INT_ID, HASH_KEY, COMPARE_KEYS, ACE_LOCK>* 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 <class EXT_ID, class INT_ID, class HASH_KEY> +template <class EXT_ID, class INT_ID, class HASH_KEY, class COMPARE_KEYS, class ACE_LOCK> class ACE_Hash_Map_RT_Bucket { + + typedef ACE_Hash_Map_RT_POD<EXT_ID, INT_ID, HASH_KEY, COMPARE_KEYS, ACE_LOCK> POD; + typedef ACE_Hash_Map_RT_ListItem<EXT_ID, INT_ID, HASH_KEY, COMPARE_KEYS, ACE_LOCK> LITEM; + typedef ACE_Hash_Map_RT_Entry<EXT_ID, INT_ID, HASH_KEY, COMPARE_KEYS, ACE_LOCK> ENTRY; + + friend class ACE_Hash_Map_RT_Manager_Ex<EXT_ID, INT_ID, HASH_KEY, COMPARE_KEYS, ACE_LOCK>; + friend class ACE_Hash_Map_RT_Visitor<EXT_ID, INT_ID, HASH_KEY, COMPARE_KEYS, ACE_LOCK>; + friend class ACE_Hash_Map_RT_Put_Visitor<EXT_ID, INT_ID, HASH_KEY, COMPARE_KEYS, ACE_LOCK>; + friend class ACE_Hash_Map_RT_Remove_Visitor<EXT_ID, INT_ID, HASH_KEY, COMPARE_KEYS, ACE_LOCK>; + public: - - typedef ACE_Hash_Map_RT_POD<EXT_ID, INT_ID, HASH_KEY> POD; - typedef ACE_Hash_Map_RT_ListItem<EXT_ID, INT_ID> LITEM; - typedef ACE_Hash_Map_RT_Entry<EXT_ID, INT_ID> 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 <class EXT_ID, class INT_ID, class HASH_KEY> +template <class EXT_ID, class INT_ID, class HASH_KEY, class COMPARE_KEYS, class ACE_LOCK> class ACE_Hash_Map_RT_Table { + + typedef ACE_Hash_Map_RT_POD<EXT_ID, INT_ID, HASH_KEY, COMPARE_KEYS, ACE_LOCK> POD; + typedef ACE_Hash_Map_RT_Bucket<EXT_ID, INT_ID, HASH_KEY, COMPARE_KEYS, ACE_LOCK> BUCKET; + + friend class ACE_Hash_Map_RT_Bucket<EXT_ID, INT_ID, HASH_KEY, COMPARE_KEYS, ACE_LOCK>; + friend class ACE_Hash_Map_RT_Clean_Manager<EXT_ID, INT_ID, HASH_KEY, COMPARE_KEYS, ACE_LOCK>; + friend class ACE_Hash_Map_RT_Manager_Ex<EXT_ID, INT_ID, HASH_KEY, COMPARE_KEYS, ACE_LOCK>; + public: - - typedef ACE_Hash_Map_RT_POD<EXT_ID, INT_ID, HASH_KEY> POD; - typedef ACE_Hash_Map_RT_ListItem<EXT_ID, INT_ID> LITEM; - typedef ACE_Hash_Map_RT_Entry<EXT_ID, INT_ID> ENTRY; - typedef ACE_Hash_Map_RT_Bucket<EXT_ID, INT_ID, HASH_KEY> BUCKET; - - friend class ACE_Hash_Map_RT_Bucket<EXT_ID, INT_ID, HASH_KEY>; - + +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 EXT_ID, class INT_ID, class HASH_KEY, class COMPARE_KEYS, class ACE_LOCK> 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 EXT_ID, class INT_ID, class HASH_KEY, class COMPARE_KEYS, class ACE_LOCK> +class ACE_Hash_Map_RT_Clean_Manager +{ + typedef ACE_Hash_Map_RT_Bucket<EXT_ID, INT_ID, HASH_KEY, COMPARE_KEYS, ACE_LOCK> BUCKET; + + friend class ACE_Hash_Map_RT_Manager_Ex<EXT_ID, INT_ID, HASH_KEY, COMPARE_KEYS, ACE_LOCK>; + +public: + +protected: + + ///Constructor + ACE_Hash_Map_RT_Clean_Manager (ACE_Hash_Map_RT_Manager_Ex<EXT_ID, INT_ID, HASH_KEY, COMPARE_KEYS, ACE_LOCK>* 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<EXT_ID, INT_ID, HASH_KEY, COMPARE_KEYS, ACE_LOCK>* 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<EXT_ID, INT_ID, HASH_KEY, COMPARE_KEYS, ACE_LOCK>* 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 EXT_ID, class INT_ID, class HASH_KEY, class COMPARE_KEYS, class template <class EXT_ID, class INT_ID, class HASH_KEY, class COMPARE_KEYS, class ACE_LOCK> class ACE_Hash_Map_RT_Visitor { + typedef ACE_Hash_Map_RT_ListItem<EXT_ID, INT_ID, HASH_KEY, COMPARE_KEYS, ACE_LOCK>LITEM; + typedef ACE_Hash_Map_RT_Bucket<EXT_ID, INT_ID, HASH_KEY, COMPARE_KEYS, ACE_LOCK> BUCKET; + + friend class ACE_Hash_Map_RT_Manager_Ex<EXT_ID, INT_ID, HASH_KEY, COMPARE_KEYS, ACE_LOCK>; + friend class ACE_Hash_Map_RT_Clean_Manager<EXT_ID, INT_ID, HASH_KEY, COMPARE_KEYS, ACE_LOCK>; + public: - typedef ACE_Hash_Map_RT_POD<EXT_ID, INT_ID, HASH_KEY> POD; - typedef ACE_Hash_Map_RT_ListItem<EXT_ID, INT_ID>LITEM; - typedef ACE_Hash_Map_RT_Entry<EXT_ID, INT_ID>ENTRY; - typedef ACE_Hash_Map_RT_Table<EXT_ID, INT_ID, HASH_KEY> TABLE; - typedef ACE_Hash_Map_RT_Bucket<EXT_ID, INT_ID, HASH_KEY> 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 EXT_ID, class INT_ID, class HASH_KEY, class COMPARE_KEYS, class ACE_LOCK> class ACE_Hash_Map_RT_Clean_Visitor : public ACE_Hash_Map_RT_Visitor<EXT_ID, INT_ID, HASH_KEY, COMPARE_KEYS, ACE_LOCK> { + typedef ACE_Hash_Map_RT_ListItem<EXT_ID, INT_ID, HASH_KEY, COMPARE_KEYS, ACE_LOCK>LITEM; + typedef ACE_Hash_Map_RT_Bucket<EXT_ID, INT_ID, HASH_KEY, COMPARE_KEYS, ACE_LOCK> BUCKET; + + friend class ACE_Hash_Map_RT_Manager_Ex<EXT_ID, INT_ID, HASH_KEY, COMPARE_KEYS, ACE_LOCK>; + public: + +protected: ACE_Hash_Map_RT_Clean_Visitor (ACE_Hash_Map_RT_Manager_Ex<EXT_ID, INT_ID, HASH_KEY, COMPARE_KEYS, ACE_LOCK>* 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 EXT_ID, class INT_ID, class HASH_KEY, class COMPARE_KEYS, class ACE_LOCK> class ACE_Hash_Map_RT_Searching_Visitor : public ACE_Hash_Map_RT_Visitor<EXT_ID, INT_ID, HASH_KEY, COMPARE_KEYS, ACE_LOCK> { + typedef ACE_Hash_Map_RT_POD<EXT_ID, INT_ID, HASH_KEY, COMPARE_KEYS, ACE_LOCK> POD; + typedef ACE_Hash_Map_RT_ListItem<EXT_ID, INT_ID, HASH_KEY, COMPARE_KEYS, ACE_LOCK>LITEM; + typedef ACE_Hash_Map_RT_Entry<EXT_ID, INT_ID, HASH_KEY, COMPARE_KEYS, ACE_LOCK>ENTRY; + typedef ACE_Hash_Map_RT_Bucket<EXT_ID, INT_ID, HASH_KEY, COMPARE_KEYS, ACE_LOCK> BUCKET; + + friend class ACE_Hash_Map_RT_Manager_Ex<EXT_ID, INT_ID, HASH_KEY, COMPARE_KEYS, ACE_LOCK>; + public: +protected: + // = Initialization and termination methods. /// Constructor ACE_Hash_Map_RT_Searching_Visitor (const EXT_ID& entry, ACE_Hash_Map_RT_Manager_Ex<EXT_ID, INT_ID, HASH_KEY, COMPARE_KEYS, ACE_LOCK>* 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<EXT_ID, INT_ID, HASH_KEY, COMPARE_KEYS, ACE_LOCK>* manager_; }; - + /** * @class ACE_Hash_Map_RT_Put_Visitor * @@ -464,43 +545,61 @@ public: template <class EXT_ID, class INT_ID, class HASH_KEY, class COMPARE_KEYS, class ACE_LOCK> class ACE_Hash_Map_RT_Put_Visitor : public ACE_Hash_Map_RT_Searching_Visitor<EXT_ID, INT_ID, HASH_KEY, COMPARE_KEYS, ACE_LOCK> { + typedef ACE_Hash_Map_RT_POD<EXT_ID, INT_ID, HASH_KEY, COMPARE_KEYS, ACE_LOCK> POD; + typedef ACE_Hash_Map_RT_ListItem<EXT_ID, INT_ID, HASH_KEY, COMPARE_KEYS, ACE_LOCK>LITEM; + typedef ACE_Hash_Map_RT_Entry<EXT_ID, INT_ID, HASH_KEY, COMPARE_KEYS, ACE_LOCK>ENTRY; + typedef ACE_Hash_Map_RT_Bucket<EXT_ID, INT_ID, HASH_KEY, COMPARE_KEYS, ACE_LOCK> BUCKET; + + friend class ACE_Hash_Map_RT_Manager_Ex<EXT_ID, INT_ID, HASH_KEY, COMPARE_KEYS, ACE_LOCK>; + 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<EXT_ID, INT_ID, HASH_KEY, COMPARE_KEYS, ACE_LOCK>* 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 EXT_ID, class INT_ID, class HASH_KEY, class COMPARE_KEYS, class ACE_LOCK> class ACE_Hash_Map_RT_Get_Visitor : public ACE_Hash_Map_RT_Searching_Visitor<EXT_ID, INT_ID, HASH_KEY, COMPARE_KEYS, ACE_LOCK> { + typedef ACE_Hash_Map_RT_POD<EXT_ID, INT_ID, HASH_KEY, COMPARE_KEYS, ACE_LOCK> POD; + typedef ACE_Hash_Map_RT_ListItem<EXT_ID, INT_ID, HASH_KEY, COMPARE_KEYS, ACE_LOCK>LITEM; + typedef ACE_Hash_Map_RT_Entry<EXT_ID, INT_ID, HASH_KEY, COMPARE_KEYS, ACE_LOCK>ENTRY; + typedef ACE_Hash_Map_RT_Bucket<EXT_ID, INT_ID, HASH_KEY, COMPARE_KEYS, ACE_LOCK> BUCKET; + + friend class ACE_Hash_Map_RT_Manager_Ex<EXT_ID, INT_ID, HASH_KEY, COMPARE_KEYS, ACE_LOCK>; + 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<EXT_ID, INT_ID, HASH_KEY, COMPARE_KEYS, ACE_LOCK>* thismanager); /// Calls compareMaxChain int done (BUCKET& bucket); - + private: INT_ID& int_id_; }; @@ -513,89 +612,77 @@ private: template <class EXT_ID, class INT_ID, class HASH_KEY, class COMPARE_KEYS, class ACE_LOCK> class ACE_Hash_Map_RT_Remove_Visitor : public ACE_Hash_Map_RT_Searching_Visitor<EXT_ID, INT_ID, HASH_KEY, COMPARE_KEYS, ACE_LOCK> { + typedef ACE_Hash_Map_RT_POD<EXT_ID, INT_ID, HASH_KEY, COMPARE_KEYS, ACE_LOCK> POD; + typedef ACE_Hash_Map_RT_ListItem<EXT_ID, INT_ID, HASH_KEY, COMPARE_KEYS, ACE_LOCK>LITEM; + typedef ACE_Hash_Map_RT_Entry<EXT_ID, INT_ID, HASH_KEY, COMPARE_KEYS, ACE_LOCK>ENTRY; + typedef ACE_Hash_Map_RT_Bucket<EXT_ID, INT_ID, HASH_KEY, COMPARE_KEYS, ACE_LOCK> BUCKET; + + friend class ACE_Hash_Map_RT_Manager_Ex<EXT_ID, INT_ID, HASH_KEY, COMPARE_KEYS, ACE_LOCK>; + public: +protected: + // = Initialization and termination methods. /// Constructor ACE_Hash_Map_RT_Remove_Visitor(const EXT_ID& ext_id, ACE_Hash_Map_RT_Manager_Ex<EXT_ID, INT_ID, HASH_KEY, COMPARE_KEYS, ACE_LOCK>* thismanager); - + /// Deletes the ListItem that we are looking for from the Bucket int done (BUCKET& bucket); - + }; + /* + * @class + * + * @brief + * + */ +template <class EXT_ID, class INT_ID, class HASH_KEY, class COMPARE_KEYS, class ACE_LOCK> class ACE_Hash_Map_RT_StatsManager { + + friend class ACE_Hash_Map_RT_Manager_Ex<EXT_ID, INT_ID, HASH_KEY, COMPARE_KEYS, ACE_LOCK>; + friend class ACE_Hash_Map_RT_Put_Visitor<EXT_ID, INT_ID, HASH_KEY, COMPARE_KEYS, ACE_LOCK>; + friend class ACE_Hash_Map_RT_Get_Visitor<EXT_ID, INT_ID, HASH_KEY, COMPARE_KEYS, ACE_LOCK>; + friend class ACE_Hash_Map_RT_Remove_Visitor<EXT_ID, INT_ID, HASH_KEY, COMPARE_KEYS, ACE_LOCK>; + friend class ACE_Hash_Map_RT_Clean_Manager<EXT_ID, INT_ID, HASH_KEY, COMPARE_KEYS, ACE_LOCK>; + 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 EXT_ID, class INT_ID, class HASH_KEY, class COMPARE_KEYS, class ACE_LOCK> -class ACE_Hash_Map_RT_Clean_Manager -{ - typedef ACE_Hash_Map_RT_Table<EXT_ID, INT_ID, HASH_KEY> TABLE; - typedef ACE_Hash_Map_RT_Bucket<EXT_ID, INT_ID, HASH_KEY> BUCKET; - -public: - - ///Constructor - ACE_Hash_Map_RT_Clean_Manager (ACE_Hash_Map_RT_Manager_Ex<EXT_ID, INT_ID, HASH_KEY, COMPARE_KEYS, ACE_LOCK>* 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<EXT_ID, INT_ID, HASH_KEY, COMPARE_KEYS, ACE_LOCK>* 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<EXT_ID, INT_ID, HASH_KEY, COMPARE_KEYS, ACE_LOCK>* 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 EXT_ID, class INT_ID, class HASH_KEY, class COMPARE_KEYS, class ACE_LOCK> 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<EXT_ID, INT_ID, HASH_KEY> POD; - typedef ACE_Hash_Map_RT_Entry<EXT_ID, INT_ID> ENTRY; - typedef ACE_Hash_Map_RT_Table<EXT_ID, INT_ID, HASH_KEY> TABLE; - typedef ACE_Hash_Map_RT_Bucket<EXT_ID, INT_ID, HASH_KEY> BUCKET; - typedef ACE_Hash_Map_RT_ListItem<EXT_ID, INT_ID> LITEM; + typedef ACE_Hash_Map_RT_POD<EXT_ID, INT_ID, HASH_KEY, COMPARE_KEYS, ACE_LOCK> POD; + typedef ACE_Hash_Map_RT_Entry<EXT_ID, INT_ID, HASH_KEY, COMPARE_KEYS, ACE_LOCK> ENTRY; + typedef ACE_Hash_Map_RT_Table<EXT_ID, INT_ID, HASH_KEY, COMPARE_KEYS, ACE_LOCK> TABLE; + typedef ACE_Hash_Map_RT_Bucket<EXT_ID, INT_ID, HASH_KEY, COMPARE_KEYS, ACE_LOCK> BUCKET; + typedef ACE_Hash_Map_RT_ListItem<EXT_ID, INT_ID, HASH_KEY, COMPARE_KEYS, ACE_LOCK> LITEM; typedef ACE_Hash_Map_RT_Clean_Manager<EXT_ID, INT_ID, HASH_KEY, COMPARE_KEYS, ACE_LOCK> CLEAN; typedef ACE_Hash_Map_RT_Clean_Visitor<EXT_ID, INT_ID, HASH_KEY, COMPARE_KEYS, ACE_LOCK> CLEANV; @@ -633,15 +720,17 @@ public: friend class ACE_Hash_Map_RT_Remove_Visitor<EXT_ID, INT_ID, HASH_KEY, COMPARE_KEYS, ACE_LOCK>; friend class ACE_Hash_Map_RT_Clean_Visitor<EXT_ID, INT_ID, HASH_KEY, COMPARE_KEYS, ACE_LOCK>; +public: + // = Initialization and termination methods. - + /// Initialize a <Hash_Map_Manager_Ex> 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 <Hash_Map_Manager_Ex>. ~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 <ACE_Hash_Map_ListItem>. 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<EXT_ID, INT_ID, HASH_KEY, COMPARE_KEYS, ACE_LOCK>& 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<EXT_ID, INT_ID, HASH_KEY, COMPARE_KEYS, ACE_LOCK>* 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<EXT_ID, INT_ID, HASH_KEY, COMPARE_KEYS, ACE_LOCK>* clean_vis_; - ACE_Hash_Map_RT_Clean_Manager<EXT_ID, INT_ID, HASH_KEY, COMPARE_KEYS, ACE_LOCK>* 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<EXT_ID, INT_ID, HASH_KEY, COMPARE_KEYS, ACE_LOCK>* clean_vis_; + + ACE_Hash_Map_RT_Clean_Manager<EXT_ID, INT_ID, HASH_KEY, COMPARE_KEYS, ACE_LOCK>* clean_; + /// Synchronization variable for the MT_SAFE <ACE_Hash_Map_Manager_Ex>. ACE_LOCK lock_; |