src/share/vm/utilities/hashtable.hpp
Index Unified diffs Context diffs Sdiffs Wdiffs Patch New Old Previous File Next File

## src/share/vm/utilities/hashtable.hpp

Print this page

      23  */
      24
      25 #ifndef SHARE_VM_UTILITIES_HASHTABLE_HPP
      26 #define SHARE_VM_UTILITIES_HASHTABLE_HPP
      27
      28 #include "classfile/classLoaderData.hpp"
      29 #include "memory/allocation.hpp"
      30 #include "oops/oop.hpp"
      31 #include "oops/symbol.hpp"
      32 #include "runtime/handles.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
      53   // shared entries will not change.  New entries will always be
      54   // unshared and since pointers are align, bit 0 will always remain 0
      55   // with no extra effort.
      56   BasicHashtableEntry<F>* _next;
      57
      58   // Windows IA64 compiler requires subclasses to be able to access these
      59 protected:
      60   // Entry objects should not be created, they should be taken from the
      61   // free list with BasicHashtable.new_entry().
      62   BasicHashtableEntry() { ShouldNotReachHere(); }
      63   // Entry objects should not be destroyed.  They should be placed on
      64   // the free list instead with BasicHashtable.free_entry().
      65   ~BasicHashtableEntry() { ShouldNotReachHere(); }
      66
      67 public:
      99
     100 template <class T, MEMFLAGS F> class HashtableEntry : public BasicHashtableEntry<F> {
     101   friend class VMStructs;
     102 private:
     103   T               _literal;          // ref to item in table.
     104
     105 public:
     106   // Literal
     107   T literal() const                   { return _literal; }
     108   T* literal_addr()                   { return &_literal; }
     109   void set_literal(T s)               { _literal = s; }
     110
     111   HashtableEntry* next() const {
     112     return (HashtableEntry*)BasicHashtableEntry<F>::next();
     113   }
     114   HashtableEntry** next_addr() {
     115     return (HashtableEntry**)BasicHashtableEntry<F>::next_addr();
     116   }
     117 };
     118
     119
     120
     121 template <MEMFLAGS F> class HashtableBucket : public CHeapObj<F> {
     122   friend class VMStructs;
     123 private:
     124   // Instance variable
     125   BasicHashtableEntry<F>*       _entry;
     126
     127 public:
     128   // Accessing
     129   void clear()                        { _entry = NULL; }
     130
     131   // The following methods use order access methods to avoid race
     132   // conditions in multiprocessor systems.
     133   BasicHashtableEntry<F>* get_entry() const;
     134   void set_entry(BasicHashtableEntry<F>* l);
     135
     136   // The following method is not MT-safe and must be done under lock.
     137   BasicHashtableEntry<F>** entry_addr()  { return &_entry; }
     138 };
     139

     140
     141 template <MEMFLAGS F> class BasicHashtable : public CHeapObj<F> {
     142   friend class VMStructs;
     143
     144 public:
     145   BasicHashtable(int table_size, int entry_size);
     146   BasicHashtable(int table_size, int entry_size,
     147                  HashtableBucket<F>* buckets, int number_of_entries);
     148
     149   // Sharing support.
     150   void copy_buckets(char** top, char* end);
     151   void copy_table(char** top, char* end);
     152

     153   // Bucket handling
     154   int hash_to_index(unsigned int full_hash) {
     155     int h = full_hash % _table_size;
     156     assert(h >= 0 && h < _table_size, "Illegal hash value");
     157     return h;
     158   }
     159
     160   // Reverse the order of elements in each of the buckets.
     161   void reverse();
     162
     163 private:
     164   // Instance variables
     165   int               _table_size;
     166   HashtableBucket<F>*     _buckets;
     167   BasicHashtableEntry<F>* _free_list;
     168   char*             _first_free_entry;
     169   char*             _end_block;
     170   int               _entry_size;
     171   int               _number_of_entries;
     172
     173 protected:
     174

     175 #ifdef ASSERT
     176   int               _lookup_count;
     177   int               _lookup_length;
     178   void verify_lookup_length(double load);
     179 #endif
     180
     181   void initialize(int table_size, int entry_size, int number_of_entries);
     182
     183   // Accessor
     184   int entry_size() const { return _entry_size; }
     185
     186   // The following method is MT-safe and may be used with caution.
     187   BasicHashtableEntry<F>* bucket(int i);
     188
     189   // The following method is not MT-safe and must be done under lock.
     190   BasicHashtableEntry<F>** bucket_addr(int i) { return _buckets[i].entry_addr(); }
     191
     192   // Attempt to get an entry from the free list
     193   BasicHashtableEntry<F>* new_entry_free_list();
     194
     209     _first_free_entry = src->_first_free_entry;
     210     src->_first_free_entry = NULL;
     211     _end_block = src->_end_block;
     212     src->_end_block = NULL;
     213   }
     214
     215   // Free the buckets in this hashtable
     216   void free_buckets();
     217
     218 public:
     219   int table_size() { return _table_size; }
     220   void set_entry(int index, BasicHashtableEntry<F>* entry);
     221
     222   void add_entry(int index, BasicHashtableEntry<F>* entry);
     223
     224   void free_entry(BasicHashtableEntry<F>* entry);
     225
     226   int number_of_entries() { return _number_of_entries; }
     227
     228   void verify() PRODUCT_RETURN;

     229 };
     230
     231
     232 template <class T, MEMFLAGS F> class Hashtable : public BasicHashtable<F> {
     233   friend class VMStructs;
     234
     235 public:
     236   Hashtable(int table_size, int entry_size)
     237     : BasicHashtable<F>(table_size, entry_size) { }
     238
     239   Hashtable(int table_size, int entry_size,
     240                    HashtableBucket<F>* buckets, int number_of_entries)
     241     : BasicHashtable<F>(table_size, entry_size, buckets, number_of_entries) { }
     242
     243   // Debugging
     244   void print()               PRODUCT_RETURN;
     245
     246   // Reverse the order of elements in each of the buckets. Hashtable
     247   // entries which refer to objects at a lower address than 'boundary'
     248   // are separated from those which refer to objects at higher
     255     return (unsigned int) name->identity_hash();
     256   }
     257
     258   int index_for(Symbol* name) {
     259     return this->hash_to_index(compute_hash(name));
     260   }
     261
     262   // Table entry management
     263   HashtableEntry<T, F>* new_entry(unsigned int hashValue, T obj);
     264
     265   // The following method is MT-safe and may be used with caution.
     266   HashtableEntry<T, F>* bucket(int i) {
     267     return (HashtableEntry<T, F>*)BasicHashtable<F>::bucket(i);
     268   }
     269
     270   // The following method is not MT-safe and must be done under lock.
     271   HashtableEntry<T, F>** bucket_addr(int i) {
     272     return (HashtableEntry<T, F>**)BasicHashtable<F>::bucket_addr(i);
     273   }
     274

     275 };
     276
     277 template <class T, MEMFLAGS F> class RehashableHashtable : public Hashtable<T, F> {
     278  protected:
     279
     280   enum {
     281     rehash_count = 100,
     282     rehash_multiple = 60
     283   };
     284
     285   // Check that the table is unbalanced
     286   bool check_rehash_table(int count);
     287
     288  public:
     289   RehashableHashtable(int table_size, int entry_size)
     290     : Hashtable<T, F>(table_size, entry_size) { }
     291
     292   RehashableHashtable(int table_size, int entry_size,
     293                    HashtableBucket<F>* buckets, int number_of_entries)
     294     : Hashtable<T, F>(table_size, entry_size, buckets, number_of_entries) { }
     295
     296
     297   // Function to move these elements into the new table.
     298   void move_to(RehashableHashtable<T, F>* new_table);
     299   static bool use_alternate_hashcode()  { return _seed != 0; }
     300   static juint seed()                    { return _seed; }
     301
     302   static int literal_size(Symbol *symbol);
     303   static int literal_size(oop oop);
     304
     305   // The following two are currently not used, but are needed anyway because some
     306   // C++ compilers (MacOS and Solaris) force the instantiation of
     307   // Hashtable<ConstantPool*, mtClass>::dump_table() even though we never call this function
     308   // in the VM code.
     309   static int literal_size(ConstantPool *cp) {Unimplemented(); return 0;}
     310   static int literal_size(Klass *k)         {Unimplemented(); return 0;}
     311
     312   void dump_table(outputStream* st, const char *table_name);
     313
     314  private:
     315   static juint _seed;
     316 };
     317
     318
     319 //  Verions of hashtable where two handles are used to compute the index.
     320
     321 template <class T, MEMFLAGS F> class TwoOopHashtable : public Hashtable<T, F> {
     322   friend class VMStructs;
     323 protected:
     324   TwoOopHashtable(int table_size, int entry_size)
     325     : Hashtable<T, F>(table_size, entry_size) {}
     326
     327   TwoOopHashtable(int table_size, int entry_size, HashtableBucket<F>* t,
     328                   int number_of_entries)
     329     : Hashtable<T, F>(table_size, entry_size, t, number_of_entries) {}
     330
     331 public:
     332   unsigned int compute_hash(Symbol* name, ClassLoaderData* loader_data) {
     333     unsigned int name_hash = name->identity_hash();
      23  */
      24
      25 #ifndef SHARE_VM_UTILITIES_HASHTABLE_HPP
      26 #define SHARE_VM_UTILITIES_HASHTABLE_HPP
      27
      28 #include "classfile/classLoaderData.hpp"
      29 #include "memory/allocation.hpp"
      30 #include "oops/oop.hpp"
      31 #include "oops/symbol.hpp"
      32 #include "runtime/handles.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 template <MEMFLAGS F> class BasicHashtableEntry : public CHeapObj<F> {
      44   friend class VMStructs;
      45 private:
      46   unsigned int        _hash;           // 32-bit hash for item
      47   public:
      48   int                 _debug_lookups;
      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
      54   // shared entries will not change.  New entries will always be
      55   // unshared and since pointers are align, bit 0 will always remain 0
      56   // with no extra effort.
      57   BasicHashtableEntry<F>* _next;
      58
      59   // Windows IA64 compiler requires subclasses to be able to access these
      60 protected:
      61   // Entry objects should not be created, they should be taken from the
      62   // free list with BasicHashtable.new_entry().
      63   BasicHashtableEntry() { ShouldNotReachHere(); }
      64   // Entry objects should not be destroyed.  They should be placed on
      65   // the free list instead with BasicHashtable.free_entry().
      66   ~BasicHashtableEntry() { ShouldNotReachHere(); }
      67
      68 public:
     100
     101 template <class T, MEMFLAGS F> class HashtableEntry : public BasicHashtableEntry<F> {
     102   friend class VMStructs;
     103 private:
     104   T               _literal;          // ref to item in table.
     105
     106 public:
     107   // Literal
     108   T literal() const                   { return _literal; }
     109   T* literal_addr()                   { return &_literal; }
     110   void set_literal(T s)               { _literal = s; }
     111
     112   HashtableEntry* next() const {
     113     return (HashtableEntry*)BasicHashtableEntry<F>::next();
     114   }
     115   HashtableEntry** next_addr() {
     116     return (HashtableEntry**)BasicHashtableEntry<F>::next_addr();
     117   }
     118 };
     119

     120 template <MEMFLAGS F> class HashtableBucket : public CHeapObj<F> {
     121   friend class VMStructs;
     122 private:
     123   // Instance variable
     124   BasicHashtableEntry<F>*       _entry;
     125
     126 public:
     127   // Accessing
     128   void clear()                        { _entry = NULL; }
     129
     130   // The following methods use order access methods to avoid race
     131   // conditions in multiprocessor systems.
     132   BasicHashtableEntry<F>* get_entry() const;
     133   void set_entry(BasicHashtableEntry<F>* l);
     134
     135   // The following method is not MT-safe and must be done under lock.
     136   BasicHashtableEntry<F>** entry_addr()  { return &_entry; }
     137 };
     138
     139 typedef struct
     140 {
     141   bool resized;
     142   unsigned int old_size;
     143   unsigned int new_size;
     144 } ResizeHashtableStats;
     145
     146 template <MEMFLAGS F> class BasicHashtable : public CHeapObj<F> {
     147   friend class VMStructs;
     148
     149 public:
     150   BasicHashtable(int table_size, int entry_size);
     151   BasicHashtable(int table_size, int entry_size,
     152                  HashtableBucket<F>* buckets, int number_of_entries);
     153
     154   // Sharing support.
     155   void copy_buckets(char** top, char* end);
     156   void copy_table(char** top, char* end);
     157
     158   // Resizing support.
     159   ResizeHashtableStats resize_table(Monitor* lock, float trigger, float desired);
     160
     161   // Bucket handling
     162   int hash_to_index(unsigned int full_hash) {
     163     int h = full_hash % _table_size;
     164     assert(h >= 0 && h < _table_size, "Illegal hash value");
     165     return h;
     166   }
     167
     168   // Reverse the order of elements in each of the buckets.
     169   void reverse();
     170
     171 private:
     172   // Instance variables
     173   int               _table_size;
     174   HashtableBucket<F>*     _buckets;
     175   BasicHashtableEntry<F>* _free_list;
     176   char*             _first_free_entry;
     177   char*             _end_block;
     178   int               _entry_size;
     179   int               _number_of_entries;
     180
     181 protected:
     182
     183   julong            _debug_resize_fire; // FORCE_RESIZE
     184
     185 #ifndef PRODUCT
     186 //#ifdef PRODUCT_TEST
     187
     188   long              _debug_table_threads[1024];
     189
     190   // statistics kept through life of VM per table type
     191   julong            _debug_all_lookup_count;
     192   julong            _debug_all_insertion_count;
     193
     194   // statistics per table's duration of life
     195   julong            _debug_lookup_count;
     196   julong            _debug_insertion_count;
     197   julong            _debug_lookup_found_count;
     198   julong            _debug_lookup_found_max_duration;
     199   julong            _debug_lookup_found_total_duration;
     200   julong            _debug_chain_found_maximum_length;
     201   julong            _debug_chain_found_total_length;
     202   julong            _debug_lookup_failed_count;
     203   julong            _debug_lookup_failed_max_duration;
     204   julong            _debug_lookup_failed_total_duration;
     205   julong            _debug_chain_failed_maximum_length;
     206   julong            _debug_chain_failed_total_length;
     207   julong            _debug_resize_max_duration;
     208   julong            _debug_resize_total_duration;
     209   julong            _debug_resize_total_count;
     210 #endif
     211
     212 #ifdef ASSERT
     213   int               _lookup_count;
     214   int               _lookup_length;
     215   void verify_lookup_length(double load);
     216 #endif
     217
     218   void initialize(int table_size, int entry_size, int number_of_entries);
     219
     220   // Accessor
     221   int entry_size() const { return _entry_size; }
     222
     223   // The following method is MT-safe and may be used with caution.
     224   BasicHashtableEntry<F>* bucket(int i);
     225
     226   // The following method is not MT-safe and must be done under lock.
     227   BasicHashtableEntry<F>** bucket_addr(int i) { return _buckets[i].entry_addr(); }
     228
     229   // Attempt to get an entry from the free list
     230   BasicHashtableEntry<F>* new_entry_free_list();
     231
     246     _first_free_entry = src->_first_free_entry;
     247     src->_first_free_entry = NULL;
     248     _end_block = src->_end_block;
     249     src->_end_block = NULL;
     250   }
     251
     252   // Free the buckets in this hashtable
     253   void free_buckets();
     254
     255 public:
     256   int table_size() { return _table_size; }
     257   void set_entry(int index, BasicHashtableEntry<F>* entry);
     258
     259   void add_entry(int index, BasicHashtableEntry<F>* entry);
     260
     261   void free_entry(BasicHashtableEntry<F>* entry);
     262
     263   int number_of_entries() { return _number_of_entries; }
     264
     265   void verify() PRODUCT_RETURN;
     266
     267   void dump(outputStream* st, const char* table_name) { tty->print("BasicHashtable\n"); };
     268 };
     269
     270
     271 template <class T, MEMFLAGS F> class Hashtable : public BasicHashtable<F> {
     272   friend class VMStructs;
     273
     274 public:
     275   Hashtable(int table_size, int entry_size)
     276     : BasicHashtable<F>(table_size, entry_size) { }
     277
     278   Hashtable(int table_size, int entry_size,
     279                    HashtableBucket<F>* buckets, int number_of_entries)
     280     : BasicHashtable<F>(table_size, entry_size, buckets, number_of_entries) { }
     281
     282   // Debugging
     283   void print()               PRODUCT_RETURN;
     284
     285   // Reverse the order of elements in each of the buckets. Hashtable
     286   // entries which refer to objects at a lower address than 'boundary'
     287   // are separated from those which refer to objects at higher
     294     return (unsigned int) name->identity_hash();
     295   }
     296
     297   int index_for(Symbol* name) {
     298     return this->hash_to_index(compute_hash(name));
     299   }
     300
     301   // Table entry management
     302   HashtableEntry<T, F>* new_entry(unsigned int hashValue, T obj);
     303
     304   // The following method is MT-safe and may be used with caution.
     305   HashtableEntry<T, F>* bucket(int i) {
     306     return (HashtableEntry<T, F>*)BasicHashtable<F>::bucket(i);
     307   }
     308
     309   // The following method is not MT-safe and must be done under lock.
     310   HashtableEntry<T, F>** bucket_addr(int i) {
     311     return (HashtableEntry<T, F>**)BasicHashtable<F>::bucket_addr(i);
     312   }
     313
     314   static int literal_size(Symbol *symbol);
     315   static int literal_size(oop oop);
     316   static int literal_size(Klass *k);
     317
     318   // The following ones are currently not used, but are needed anyway because some
     319   // C++ compilers (MacOS and Solaris) force the instantiation of
     320   // Hashtable<ConstantPool*, mtClass>::dump_table() even though we never call this function
     321   // in the VM code.
     322   static int literal_size(ConstantPool *cp) {Unimplemented(); return 0;}
     323   static int literal_size(nmethod *nm) {Unimplemented(); return 0;}
     324
     325 public:
     326   void dump_table(outputStream* st, const char *table_name);
     327   void dump(outputStream* st, const char* table_name);
     328 };
     329
     330 template <class T, MEMFLAGS F> class RehashableHashtable : public Hashtable<T, F> {
     331  protected:
     332
     333   enum {
     334     rehash_count = 100,
     335     rehash_multiple = 60
     336   };
     337
     338   // Check that the table is unbalanced
     339   bool check_rehash_table(int count);
     340
     341  public:
     342   RehashableHashtable(int table_size, int entry_size)
     343     : Hashtable<T, F>(table_size, entry_size) { }
     344
     345   RehashableHashtable(int table_size, int entry_size,
     346                    HashtableBucket<F>* buckets, int number_of_entries)
     347     : Hashtable<T, F>(table_size, entry_size, buckets, number_of_entries) { }
     348
     349
     350   // Function to move these elements into the new table.
     351   void move_to(RehashableHashtable<T, F>* new_table);
     352   static bool use_alternate_hashcode()  { return _seed != 0; }
     353   static juint seed()                    { return _seed; }
     354

     355  private:
     356   static juint _seed;
     357 };
     358
     359
     360 //  Verions of hashtable where two handles are used to compute the index.
     361
     362 template <class T, MEMFLAGS F> class TwoOopHashtable : public Hashtable<T, F> {
     363   friend class VMStructs;
     364 protected:
     365   TwoOopHashtable(int table_size, int entry_size)
     366     : Hashtable<T, F>(table_size, entry_size) {}
     367
     368   TwoOopHashtable(int table_size, int entry_size, HashtableBucket<F>* t,
     369                   int number_of_entries)
     370     : Hashtable<T, F>(table_size, entry_size, t, number_of_entries) {}
     371
     372 public:
     373   unsigned int compute_hash(Symbol* name, ClassLoaderData* loader_data) {
     374     unsigned int name_hash = name->identity_hash();

src/share/vm/utilities/hashtable.hpp
Index Unified diffs Context diffs Sdiffs Wdiffs Patch New Old Previous File Next File