src/share/vm/utilities/hashtable.cpp

rev 6680 : 8056084: Refactor Hashtable to allow implementations without rehashing support
Reviewed-by: gziemski, jmasa, brutisso, coleenp, tschatzl

@@ -34,25 +34,26 @@
 #include "utilities/hashtable.hpp"
 #include "utilities/hashtable.inline.hpp"
 #include "utilities/numberSeq.hpp"
 
 
-// This is a generic hashtable, designed to be used for the symbol
-// and string tables.
-//
-// It is implemented as an open hash table with a fixed number of buckets.
-//
-// %note:
-//  - HashtableEntrys are allocated in blocks to reduce the space overhead.
-
-template <MEMFLAGS F> BasicHashtableEntry<F>* BasicHashtable<F>::new_entry(unsigned int hashValue) {
-  BasicHashtableEntry<F>* entry;
+// This hashtable is implemented as an open hash table with a fixed number of buckets.
 
-  if (_free_list) {
+template <MEMFLAGS F> BasicHashtableEntry<F>* BasicHashtable<F>::new_entry_free_list() {
+  BasicHashtableEntry<F>* entry = NULL;
+  if (_free_list != NULL) {
     entry = _free_list;
     _free_list = _free_list->next();
-  } else {
+  }
+  return entry;
+}
+
+// HashtableEntrys are allocated in blocks to reduce the space overhead.
+template <MEMFLAGS F> BasicHashtableEntry<F>* BasicHashtable<F>::new_entry(unsigned int hashValue) {
+  BasicHashtableEntry<F>* entry = new_entry_free_list();
+
+  if (entry == NULL) {
     if (_first_free_entry + _entry_size >= _end_block) {
       int block_size = MIN2(512, MAX2((int)_table_size / 2, (int)_number_of_entries));
       int len = _entry_size * block_size;
       len = 1 << log2_intptr(len); // round down to power of 2
       assert(len >= _entry_size, "");

@@ -81,37 +82,37 @@
 // rehash at the next safepoint.  If this bucket is 60 times greater than the
 // expected average bucket length, it's an unbalanced hashtable.
 // This is somewhat an arbitrary heuristic but if one bucket gets to
 // rehash_count which is currently 100, there's probably something wrong.
 
-template <MEMFLAGS F> bool BasicHashtable<F>::check_rehash_table(int count) {
-  assert(table_size() != 0, "underflow");
-  if (count > (((double)number_of_entries()/(double)table_size())*rehash_multiple)) {
+template <class T, MEMFLAGS F> bool RehashableHashtable<T, F>::check_rehash_table(int count) {
+  assert(this->table_size() != 0, "underflow");
+  if (count > (((double)this->number_of_entries()/(double)this->table_size())*rehash_multiple)) {
     // Set a flag for the next safepoint, which should be at some guaranteed
     // safepoint interval.
     return true;
   }
   return false;
 }
 
-template <class T, MEMFLAGS F> juint Hashtable<T, F>::_seed = 0;
+template <class T, MEMFLAGS F> juint RehashableHashtable<T, F>::_seed = 0;
 
 // Create a new table and using alternate hash code, populate the new table
 // with the existing elements.   This can be used to change the hash code
 // and could in the future change the size of the table.
 
-template <class T, MEMFLAGS F> void Hashtable<T, F>::move_to(Hashtable<T, F>* new_table) {
+template <class T, MEMFLAGS F> void RehashableHashtable<T, F>::move_to(RehashableHashtable<T, F>* new_table) {
 
   // Initialize the global seed for hashing.
   _seed = AltHashing::compute_seed();
   assert(seed() != 0, "shouldn't be zero");
 
   int saved_entry_count = this->number_of_entries();
 
   // Iterate through the table and create a new entry for the new table
   for (int i = 0; i < new_table->table_size(); ++i) {
-    for (HashtableEntry<T, F>* p = bucket(i); p != NULL; ) {
+    for (HashtableEntry<T, F>* p = this->bucket(i); p != NULL; ) {
       HashtableEntry<T, F>* next = p->next();
       T string = p->literal();
       // Use alternate hashing algorithm on the symbol in the first table
       unsigned int hashValue = string->new_hash(seed());
       // Get a new index relative to the new table (can also change size)

@@ -236,15 +237,15 @@
       *bucket_addr(i) = high_list;
     }
   }
 }
 
-template <class T, MEMFLAGS F> int Hashtable<T, F>::literal_size(Symbol *symbol) {
+template <class T, MEMFLAGS F> int RehashableHashtable<T, F>::literal_size(Symbol *symbol) {
   return symbol->size() * HeapWordSize;
 }
 
-template <class T, MEMFLAGS F> int Hashtable<T, F>::literal_size(oop oop) {
+template <class T, MEMFLAGS F> int RehashableHashtable<T, F>::literal_size(oop oop) {
   // NOTE: this would over-count if (pre-JDK8) java_lang_Class::has_offset_field() is true,
   // and the String.value array is shared by several Strings. However, starting from JDK8,
   // the String.value array is not shared anymore.
   assert(oop != NULL && oop->klass() == SystemDictionary::String_klass(), "only strings are supported");
   return (oop->size() + java_lang_String::value(oop)->size()) * HeapWordSize;

@@ -253,26 +254,26 @@
 // Dump footprint and bucket length statistics
 //
 // Note: if you create a new subclass of Hashtable<MyNewType, F>, you will need to
 // add a new function Hashtable<T, F>::literal_size(MyNewType lit)
 
-template <class T, MEMFLAGS F> void Hashtable<T, F>::dump_table(outputStream* st, const char *table_name) {
+template <class T, MEMFLAGS F> void RehashableHashtable<T, F>::dump_table(outputStream* st, const char *table_name) {
   NumberSeq summary;
   int literal_bytes = 0;
   for (int i = 0; i < this->table_size(); ++i) {
     int count = 0;
-    for (HashtableEntry<T, F>* e = bucket(i);
+    for (HashtableEntry<T, F>* e = this->bucket(i);
        e != NULL; e = e->next()) {
       count++;
       literal_bytes += literal_size(e->literal());
     }
     summary.add((double)count);
   }
   double num_buckets = summary.num();
   double num_entries = summary.sum();
 
-  int bucket_bytes = (int)num_buckets * sizeof(bucket(0));
+  int bucket_bytes = (int)num_buckets * sizeof(HashtableBucket<F>);
   int entry_bytes  = (int)num_entries * sizeof(HashtableEntry<T, F>);
   int total_bytes = literal_bytes +  bucket_bytes + entry_bytes;
 
   double bucket_avg  = (num_buckets <= 0) ? 0 : (bucket_bytes  / num_buckets);
   double entry_avg   = (num_entries <= 0) ? 0 : (entry_bytes   / num_entries);

@@ -351,15 +352,18 @@
 }
 
 #endif
 // Explicitly instantiate these types
 template class Hashtable<ConstantPool*, mtClass>;
+template class RehashableHashtable<Symbol*, mtSymbol>;
+template class RehashableHashtable<oopDesc*, mtSymbol>;
 template class Hashtable<Symbol*, mtSymbol>;
 template class Hashtable<Klass*, mtClass>;
 template class Hashtable<oop, mtClass>;
 #if defined(SOLARIS) || defined(CHECK_UNHANDLED_OOPS)
 template class Hashtable<oop, mtSymbol>;
+template class RehashableHashtable<oop, mtSymbol>;
 #endif // SOLARIS || CHECK_UNHANDLED_OOPS
 template class Hashtable<oopDesc*, mtSymbol>;
 template class Hashtable<Symbol*, mtClass>;
 template class HashtableEntry<Symbol*, mtSymbol>;
 template class HashtableEntry<Symbol*, mtClass>;