< prev index next >

src/hotspot/share/utilities/hashtable.hpp

Print this page


   8  *
   9  * This code is distributed in the hope that it will be useful, but WITHOUT
  10  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  11  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  12  * version 2 for more details (a copy is included in the LICENSE file that
  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_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 


 216     BucketUnlinkContext() : _num_processed(0), _num_removed(0), _removed_head(NULL), _removed_tail(NULL) {
 217     }
 218 
 219     void free_entry(BasicHashtableEntry<F>* entry);
 220   };
 221   // Add of bucket entries linked together in the given context to the global free list. This method
 222   // is mt-safe wrt. to other calls of this method.
 223   void bulk_free_entries(BucketUnlinkContext* context);
 224 public:
 225   int table_size() const { return _table_size; }
 226   void set_entry(int index, BasicHashtableEntry<F>* entry);
 227 
 228   void add_entry(int index, BasicHashtableEntry<F>* entry);
 229 
 230   void free_entry(BasicHashtableEntry<F>* entry);
 231 
 232   int number_of_entries() const { return _number_of_entries; }
 233 
 234   bool resize(int new_size);
 235 










 236   template <class T> void verify_table(const char* table_name) PRODUCT_RETURN;
 237 };
 238 
 239 
 240 template <class T, MEMFLAGS F> class Hashtable : public BasicHashtable<F> {
 241   friend class VMStructs;
 242 
 243 public:
 244   Hashtable(int table_size, int entry_size)
 245     : BasicHashtable<F>(table_size, entry_size) { }
 246 
 247   Hashtable(int table_size, int entry_size,
 248                    HashtableBucket<F>* buckets, int number_of_entries)
 249     : BasicHashtable<F>(table_size, entry_size, buckets, number_of_entries) { }
 250 
 251   // Debugging
 252   void print()               PRODUCT_RETURN;
 253 
 254   unsigned int compute_hash(const Symbol* name) const {
 255     return (unsigned int) name->identity_hash();


 261 
 262   void print_table_statistics(outputStream* st, const char *table_name, T (*literal_load_barrier)(HashtableEntry<T, F>*) = NULL);
 263 
 264  protected:
 265 
 266   // Table entry management
 267   HashtableEntry<T, F>* new_entry(unsigned int hashValue, T obj);
 268   // Don't create and use freelist of HashtableEntry.
 269   HashtableEntry<T, F>* allocate_new_entry(unsigned int hashValue, T obj);
 270 
 271   // The following method is MT-safe and may be used with caution.
 272   HashtableEntry<T, F>* bucket(int i) const {
 273     return (HashtableEntry<T, F>*)BasicHashtable<F>::bucket(i);
 274   }
 275 
 276   // The following method is not MT-safe and must be done under lock.
 277   HashtableEntry<T, F>** bucket_addr(int i) {
 278     return (HashtableEntry<T, F>**)BasicHashtable<F>::bucket_addr(i);
 279   }
 280 };




















































 281 
 282 #endif // SHARE_VM_UTILITIES_HASHTABLE_HPP


   8  *
   9  * This code is distributed in the hope that it will be useful, but WITHOUT
  10  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  11  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  12  * version 2 for more details (a copy is included in the LICENSE file that
  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_VM_UTILITIES_HASHTABLE_HPP
  26 #define SHARE_VM_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 
  33 // This is a generic hashtable, designed to be used for the symbol
  34 // and string tables.
  35 //
  36 // It is implemented as an open hash table with a fixed number of buckets.
  37 //
  38 // %note:
  39 //  - TableEntrys are allocated in blocks to reduce the space overhead.
  40 
  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 


 215     BucketUnlinkContext() : _num_processed(0), _num_removed(0), _removed_head(NULL), _removed_tail(NULL) {
 216     }
 217 
 218     void free_entry(BasicHashtableEntry<F>* entry);
 219   };
 220   // Add of bucket entries linked together in the given context to the global free list. This method
 221   // is mt-safe wrt. to other calls of this method.
 222   void bulk_free_entries(BucketUnlinkContext* context);
 223 public:
 224   int table_size() const { return _table_size; }
 225   void set_entry(int index, BasicHashtableEntry<F>* entry);
 226 
 227   void add_entry(int index, BasicHashtableEntry<F>* entry);
 228 
 229   void free_entry(BasicHashtableEntry<F>* entry);
 230 
 231   int number_of_entries() const { return _number_of_entries; }
 232 
 233   bool resize(int new_size);
 234 
 235   // Grow the number of buckets if the average entries per bucket is over the load_factor
 236   bool maybe_grow(int load_factor = 8) {
 237     if (number_of_entries() / table_size() > load_factor) {
 238       resize(table_size() * 2);
 239       return true;
 240     } else {
 241       return false;
 242     }
 243   }
 244 
 245   template <class T> void verify_table(const char* table_name) PRODUCT_RETURN;
 246 };
 247 
 248 
 249 template <class T, MEMFLAGS F> class Hashtable : public BasicHashtable<F> {
 250   friend class VMStructs;
 251 
 252 public:
 253   Hashtable(int table_size, int entry_size)
 254     : BasicHashtable<F>(table_size, entry_size) { }
 255 
 256   Hashtable(int table_size, int entry_size,
 257                    HashtableBucket<F>* buckets, int number_of_entries)
 258     : BasicHashtable<F>(table_size, entry_size, buckets, number_of_entries) { }
 259 
 260   // Debugging
 261   void print()               PRODUCT_RETURN;
 262 
 263   unsigned int compute_hash(const Symbol* name) const {
 264     return (unsigned int) name->identity_hash();


 270 
 271   void print_table_statistics(outputStream* st, const char *table_name, T (*literal_load_barrier)(HashtableEntry<T, F>*) = NULL);
 272 
 273  protected:
 274 
 275   // Table entry management
 276   HashtableEntry<T, F>* new_entry(unsigned int hashValue, T obj);
 277   // Don't create and use freelist of HashtableEntry.
 278   HashtableEntry<T, F>* allocate_new_entry(unsigned int hashValue, T obj);
 279 
 280   // The following method is MT-safe and may be used with caution.
 281   HashtableEntry<T, F>* bucket(int i) const {
 282     return (HashtableEntry<T, F>*)BasicHashtable<F>::bucket(i);
 283   }
 284 
 285   // The following method is not MT-safe and must be done under lock.
 286   HashtableEntry<T, F>** bucket_addr(int i) {
 287     return (HashtableEntry<T, F>**)BasicHashtable<F>::bucket_addr(i);
 288   }
 289 };
 290 
 291 // A subclass of BasicHashtable that allows you to do a simple K -> V mapping
 292 // without using tons of boilerplate code.
 293 template<
 294     typename K, typename V,
 295     MEMFLAGS F = mtInternal,
 296     unsigned (*HASH)  (K const&)           = primitive_hash<K>,
 297     bool     (*EQUALS)(K const&, K const&) = primitive_equals<K>
 298     >
 299 class KVHashtable : public BasicHashtable<F> {
 300   class KVHashtableEntry : public BasicHashtableEntry<F> {
 301   public:
 302     K _key;
 303     V _value;
 304     KVHashtableEntry* next() {
 305       return (KVHashtableEntry*)BasicHashtableEntry<F>::next();
 306     }
 307   };
 308 
 309 protected:
 310   KVHashtableEntry* bucket(int i) const {
 311     return (KVHashtableEntry*)BasicHashtable<F>::bucket(i);
 312   }
 313 
 314   KVHashtableEntry* new_entry(unsigned int hashValue, K key, V value) {
 315     KVHashtableEntry* entry = (KVHashtableEntry*)BasicHashtable<F>::new_entry(hashValue);
 316     entry->_key   = key;
 317     entry->_value = value;
 318     return entry;
 319   }
 320 
 321 public:
 322   KVHashtable(int table_size) : BasicHashtable<F>(table_size, sizeof(KVHashtableEntry)) {}
 323 
 324   void add(K key, V value) {
 325     unsigned int hash = HASH(key);
 326     KVHashtableEntry* entry = new_entry(hash, key, value);
 327     BasicHashtable<F>::add_entry(BasicHashtable<F>::hash_to_index(hash), entry);
 328   }
 329 
 330   V* lookup(K key) {
 331     unsigned int hash = HASH(key);
 332     int index = BasicHashtable<F>::hash_to_index(hash);
 333     for (KVHashtableEntry* e = bucket(index); e != NULL; e = e->next()) {
 334       if (e->hash() == hash && e->_key == key) {
 335         return &(e->_value);
 336       }
 337     }
 338     return NULL;
 339   }
 340 };
 341 
 342 
 343 #endif // SHARE_VM_UTILITIES_HASHTABLE_HPP
< prev index next >