< prev index next >

src/hotspot/share/utilities/hashtable.hpp

Print this page




  13  * accompanied this code).
  14  *
  15  * You should have received a copy of the GNU General Public License version
  16  * 2 along with this work; if not, write to the Free Software Foundation,
  17  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
  18  *
  19  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
  20  * or visit www.oracle.com if you need additional information or have any
  21  * questions.
  22  *
  23  */
  24 
  25 #ifndef SHARE_UTILITIES_HASHTABLE_HPP
  26 #define SHARE_UTILITIES_HASHTABLE_HPP
  27 
  28 #include "memory/allocation.hpp"
  29 #include "oops/oop.hpp"
  30 #include "oops/symbol.hpp"
  31 #include "runtime/handles.hpp"
  32 #include "utilities/growableArray.hpp"

  33 
  34 // This is a generic hashtable, designed to be used for the symbol
  35 // and string tables.
  36 //
  37 // It is implemented as an open hash table with a fixed number of buckets.
  38 //
  39 // %note:
  40 //  - TableEntrys are allocated in blocks to reduce the space overhead.
  41 
  42 
  43 
  44 template <MEMFLAGS F> class BasicHashtableEntry : public CHeapObj<F> {
  45   friend class VMStructs;
  46 private:
  47   unsigned int         _hash;           // 32-bit hash for item
  48 
  49   // Link to next element in the linked list for this bucket.  EXCEPT
  50   // bit 0 set indicates that this entry is shared and must not be
  51   // unlinked from the table. Bit 0 is set during the dumping of the
  52   // archive. Since shared entries are immutable, _next fields in the


 151   // Bucket handling
 152   int hash_to_index(unsigned int full_hash) const {
 153     int h = full_hash % _table_size;
 154     assert(h >= 0 && h < _table_size, "Illegal hash value");
 155     return h;
 156   }
 157 
 158 private:
 159   // Instance variables
 160   int               _table_size;
 161   HashtableBucket<F>*     _buckets;
 162   BasicHashtableEntry<F>* volatile _free_list;
 163   char*             _first_free_entry;
 164   char*             _end_block;
 165   int               _entry_size;
 166   volatile int      _number_of_entries;
 167   GrowableArray<char*>* _entry_blocks;
 168 
 169 protected:
 170 


 171   void initialize(int table_size, int entry_size, int number_of_entries);
 172 
 173   // Accessor
 174   int entry_size() const { return _entry_size; }
 175 
 176   // The following method is MT-safe and may be used with caution.
 177   BasicHashtableEntry<F>* bucket(int i) const;
 178 
 179   // The following method is not MT-safe and must be done under lock.
 180   BasicHashtableEntry<F>** bucket_addr(int i) { return _buckets[i].entry_addr(); }
 181 
 182   // Attempt to get an entry from the free list
 183   BasicHashtableEntry<F>* new_entry_free_list();
 184 
 185   // Table entry management
 186   BasicHashtableEntry<F>* new_entry(unsigned int hashValue);
 187 
 188   // Used when moving the entry to another table
 189   // Clean up links, but do not add to free_list
 190   void unlink_entry(BasicHashtableEntry<F>* entry) {


 228 
 229 public:
 230   Hashtable(int table_size, int entry_size)
 231     : BasicHashtable<F>(table_size, entry_size) { }
 232 
 233   Hashtable(int table_size, int entry_size,
 234                    HashtableBucket<F>* buckets, int number_of_entries)
 235     : BasicHashtable<F>(table_size, entry_size, buckets, number_of_entries) { }
 236 
 237   // Debugging
 238   void print()               PRODUCT_RETURN;
 239 
 240   unsigned int compute_hash(const Symbol* name) const {
 241     return (unsigned int) name->identity_hash();
 242   }
 243 
 244   int index_for(const Symbol* name) const {
 245     return this->hash_to_index(compute_hash(name));
 246   }
 247 

 248   void print_table_statistics(outputStream* st, const char *table_name, T (*literal_load_barrier)(HashtableEntry<T, F>*) = NULL);
 249 
 250  protected:
 251 
 252   // Table entry management
 253   HashtableEntry<T, F>* new_entry(unsigned int hashValue, T obj);
 254   // Don't create and use freelist of HashtableEntry.
 255   HashtableEntry<T, F>* allocate_new_entry(unsigned int hashValue, T obj);
 256 
 257   // The following method is MT-safe and may be used with caution.
 258   HashtableEntry<T, F>* bucket(int i) const {
 259     return (HashtableEntry<T, F>*)BasicHashtable<F>::bucket(i);
 260   }
 261 
 262   // The following method is not MT-safe and must be done under lock.
 263   HashtableEntry<T, F>** bucket_addr(int i) {
 264     return (HashtableEntry<T, F>**)BasicHashtable<F>::bucket_addr(i);
 265   }
 266 };
 267 




  13  * accompanied this code).
  14  *
  15  * You should have received a copy of the GNU General Public License version
  16  * 2 along with this work; if not, write to the Free Software Foundation,
  17  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
  18  *
  19  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
  20  * or visit www.oracle.com if you need additional information or have any
  21  * questions.
  22  *
  23  */
  24 
  25 #ifndef SHARE_UTILITIES_HASHTABLE_HPP
  26 #define SHARE_UTILITIES_HASHTABLE_HPP
  27 
  28 #include "memory/allocation.hpp"
  29 #include "oops/oop.hpp"
  30 #include "oops/symbol.hpp"
  31 #include "runtime/handles.hpp"
  32 #include "utilities/growableArray.hpp"
  33 #include "utilities/tableStatistics.hpp"
  34 
  35 // This is a generic hashtable, designed to be used for the symbol
  36 // and string tables.
  37 //
  38 // It is implemented as an open hash table with a fixed number of buckets.
  39 //
  40 // %note:
  41 //  - TableEntrys are allocated in blocks to reduce the space overhead.
  42 
  43 
  44 
  45 template <MEMFLAGS F> class BasicHashtableEntry : public CHeapObj<F> {
  46   friend class VMStructs;
  47 private:
  48   unsigned int         _hash;           // 32-bit hash for item
  49 
  50   // Link to next element in the linked list for this bucket.  EXCEPT
  51   // bit 0 set indicates that this entry is shared and must not be
  52   // unlinked from the table. Bit 0 is set during the dumping of the
  53   // archive. Since shared entries are immutable, _next fields in the


 152   // Bucket handling
 153   int hash_to_index(unsigned int full_hash) const {
 154     int h = full_hash % _table_size;
 155     assert(h >= 0 && h < _table_size, "Illegal hash value");
 156     return h;
 157   }
 158 
 159 private:
 160   // Instance variables
 161   int               _table_size;
 162   HashtableBucket<F>*     _buckets;
 163   BasicHashtableEntry<F>* volatile _free_list;
 164   char*             _first_free_entry;
 165   char*             _end_block;
 166   int               _entry_size;
 167   volatile int      _number_of_entries;
 168   GrowableArray<char*>* _entry_blocks;
 169 
 170 protected:
 171 
 172   TableRateStatistics _stats_rate;
 173 
 174   void initialize(int table_size, int entry_size, int number_of_entries);
 175 
 176   // Accessor
 177   int entry_size() const { return _entry_size; }
 178 
 179   // The following method is MT-safe and may be used with caution.
 180   BasicHashtableEntry<F>* bucket(int i) const;
 181 
 182   // The following method is not MT-safe and must be done under lock.
 183   BasicHashtableEntry<F>** bucket_addr(int i) { return _buckets[i].entry_addr(); }
 184 
 185   // Attempt to get an entry from the free list
 186   BasicHashtableEntry<F>* new_entry_free_list();
 187 
 188   // Table entry management
 189   BasicHashtableEntry<F>* new_entry(unsigned int hashValue);
 190 
 191   // Used when moving the entry to another table
 192   // Clean up links, but do not add to free_list
 193   void unlink_entry(BasicHashtableEntry<F>* entry) {


 231 
 232 public:
 233   Hashtable(int table_size, int entry_size)
 234     : BasicHashtable<F>(table_size, entry_size) { }
 235 
 236   Hashtable(int table_size, int entry_size,
 237                    HashtableBucket<F>* buckets, int number_of_entries)
 238     : BasicHashtable<F>(table_size, entry_size, buckets, number_of_entries) { }
 239 
 240   // Debugging
 241   void print()               PRODUCT_RETURN;
 242 
 243   unsigned int compute_hash(const Symbol* name) const {
 244     return (unsigned int) name->identity_hash();
 245   }
 246 
 247   int index_for(const Symbol* name) const {
 248     return this->hash_to_index(compute_hash(name));
 249   }
 250 
 251   TableStatistics statistics_calculate(T (*literal_load_barrier)(HashtableEntry<T, F>*) = NULL);
 252   void print_table_statistics(outputStream* st, const char *table_name, T (*literal_load_barrier)(HashtableEntry<T, F>*) = NULL);
 253 
 254  protected:
 255 
 256   // Table entry management
 257   HashtableEntry<T, F>* new_entry(unsigned int hashValue, T obj);
 258   // Don't create and use freelist of HashtableEntry.
 259   HashtableEntry<T, F>* allocate_new_entry(unsigned int hashValue, T obj);
 260 
 261   // The following method is MT-safe and may be used with caution.
 262   HashtableEntry<T, F>* bucket(int i) const {
 263     return (HashtableEntry<T, F>*)BasicHashtable<F>::bucket(i);
 264   }
 265 
 266   // The following method is not MT-safe and must be done under lock.
 267   HashtableEntry<T, F>** bucket_addr(int i) {
 268     return (HashtableEntry<T, F>**)BasicHashtable<F>::bucket_addr(i);
 269   }
 270 };
 271 


< prev index next >