< prev index next >

src/share/vm/utilities/hashtable.cpp

Print this page




  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 #include "precompiled.hpp"
  26 #include "classfile/altHashing.hpp"
  27 #include "classfile/dictionary.hpp"
  28 #include "classfile/javaClasses.inline.hpp"
  29 #include "classfile/moduleEntry.hpp"
  30 #include "classfile/packageEntry.hpp"

  31 #include "classfile/protectionDomainCache.hpp"
  32 #include "classfile/stringTable.hpp"
  33 #include "memory/allocation.inline.hpp"
  34 #include "memory/filemap.hpp"
  35 #include "memory/resourceArea.hpp"
  36 #include "oops/oop.inline.hpp"
  37 #include "runtime/safepoint.hpp"
  38 #include "utilities/dtrace.hpp"
  39 #include "utilities/hashtable.hpp"
  40 #include "utilities/hashtable.inline.hpp"
  41 #include "utilities/numberSeq.hpp"
  42 
  43 
  44 // This hashtable is implemented as an open hash table with a fixed number of buckets.
  45 
  46 template <MEMFLAGS F> BasicHashtableEntry<F>* BasicHashtable<F>::new_entry_free_list() {
  47   BasicHashtableEntry<F>* entry = NULL;
  48   if (_free_list != NULL) {
  49     entry = _free_list;
  50     _free_list = _free_list->next();


 290   *top += len;
 291 }
 292 
 293 
 294 #ifndef PRODUCT
 295 
 296 template <class T, MEMFLAGS F> void Hashtable<T, F>::print() {
 297   ResourceMark rm;
 298 
 299   for (int i = 0; i < BasicHashtable<F>::table_size(); i++) {
 300     HashtableEntry<T, F>* entry = bucket(i);
 301     while(entry != NULL) {
 302       tty->print("%d : ", i);
 303       entry->literal()->print();
 304       tty->cr();
 305       entry = entry->next();
 306     }
 307   }
 308 }
 309 
 310 
 311 template <MEMFLAGS F>
 312 template <class T> void BasicHashtable<F>::verify_table(const char* table_name) {
 313   int element_count = 0;
 314   int max_bucket_count = 0;

 315   for (int index = 0; index < table_size(); index++) {
 316     int bucket_count = 0;
 317     for (T* probe = (T*)bucket(index); probe != NULL; probe = probe->next()) {
 318       probe->verify();
 319       bucket_count++;
 320     }
 321     element_count += bucket_count;
 322     max_bucket_count = MAX2(max_bucket_count, bucket_count);



 323   }
 324   guarantee(number_of_entries() == element_count,
 325             "Verify of %s failed", table_name);
 326   DEBUG_ONLY(verify_lookup_length(max_bucket_count, table_name));
 327 }
 328 
 329 
 330 #endif // PRODUCT
 331 
 332 #ifdef ASSERT
 333 
 334 // Assert if the longest bucket is 10x longer than the average bucket size.
 335 // Could change back to a warning, but warnings are not noticed.
 336 template <MEMFLAGS F> void BasicHashtable<F>::verify_lookup_length(int max_bucket_count, const char *table_name) {
 337   log_info(hashtables)("%s max bucket size %d element count %d table size %d", table_name,
 338                        max_bucket_count, _number_of_entries, _table_size);
 339   assert (max_bucket_count < ((1 + number_of_entries()/table_size())*10), "Table is unbalanced");









 340 }
 341 
 342 #endif
 343 
 344 
 345 // Explicitly instantiate these types
 346 #if INCLUDE_ALL_GCS
 347 template class Hashtable<nmethod*, mtGC>;
 348 template class HashtableEntry<nmethod*, mtGC>;
 349 template class BasicHashtable<mtGC>;
 350 #endif
 351 template class Hashtable<ConstantPool*, mtClass>;
 352 template class RehashableHashtable<Symbol*, mtSymbol>;
 353 template class RehashableHashtable<oopDesc*, mtSymbol>;
 354 template class Hashtable<Symbol*, mtSymbol>;
 355 template class Hashtable<Klass*, mtClass>;
 356 template class Hashtable<InstanceKlass*, mtClass>;
 357 template class Hashtable<oop, mtClass>;
 358 #if defined(SOLARIS) || defined(CHECK_UNHANDLED_OOPS)
 359 template class Hashtable<oop, mtSymbol>;
 360 template class RehashableHashtable<oop, mtSymbol>;
 361 #endif // SOLARIS || CHECK_UNHANDLED_OOPS
 362 template class Hashtable<oopDesc*, mtSymbol>;
 363 template class Hashtable<Symbol*, mtClass>;


 366 template class HashtableEntry<oop, mtSymbol>;
 367 template class BasicHashtableEntry<mtSymbol>;
 368 template class BasicHashtableEntry<mtCode>;
 369 template class BasicHashtable<mtClass>;
 370 template class BasicHashtable<mtClassShared>;
 371 template class BasicHashtable<mtSymbol>;
 372 template class BasicHashtable<mtCode>;
 373 template class BasicHashtable<mtInternal>;
 374 template class BasicHashtable<mtModule>;
 375 #if INCLUDE_TRACE
 376 template class Hashtable<Symbol*, mtTracing>;
 377 template class HashtableEntry<Symbol*, mtTracing>;
 378 template class BasicHashtable<mtTracing>;
 379 #endif
 380 template class BasicHashtable<mtCompiler>;
 381 
 382 template void BasicHashtable<mtClass>::verify_table<DictionaryEntry>(char const*);
 383 template void BasicHashtable<mtModule>::verify_table<ModuleEntry>(char const*);
 384 template void BasicHashtable<mtModule>::verify_table<PackageEntry>(char const*);
 385 template void BasicHashtable<mtClass>::verify_table<ProtectionDomainCacheEntry>(char const*);




  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 #include "precompiled.hpp"
  26 #include "classfile/altHashing.hpp"
  27 #include "classfile/dictionary.hpp"
  28 #include "classfile/javaClasses.inline.hpp"
  29 #include "classfile/moduleEntry.hpp"
  30 #include "classfile/packageEntry.hpp"
  31 #include "classfile/placeholders.hpp"
  32 #include "classfile/protectionDomainCache.hpp"
  33 #include "classfile/stringTable.hpp"
  34 #include "memory/allocation.inline.hpp"
  35 #include "memory/filemap.hpp"
  36 #include "memory/resourceArea.hpp"
  37 #include "oops/oop.inline.hpp"
  38 #include "runtime/safepoint.hpp"
  39 #include "utilities/dtrace.hpp"
  40 #include "utilities/hashtable.hpp"
  41 #include "utilities/hashtable.inline.hpp"
  42 #include "utilities/numberSeq.hpp"
  43 
  44 
  45 // This hashtable is implemented as an open hash table with a fixed number of buckets.
  46 
  47 template <MEMFLAGS F> BasicHashtableEntry<F>* BasicHashtable<F>::new_entry_free_list() {
  48   BasicHashtableEntry<F>* entry = NULL;
  49   if (_free_list != NULL) {
  50     entry = _free_list;
  51     _free_list = _free_list->next();


 291   *top += len;
 292 }
 293 
 294 
 295 #ifndef PRODUCT
 296 
 297 template <class T, MEMFLAGS F> void Hashtable<T, F>::print() {
 298   ResourceMark rm;
 299 
 300   for (int i = 0; i < BasicHashtable<F>::table_size(); i++) {
 301     HashtableEntry<T, F>* entry = bucket(i);
 302     while(entry != NULL) {
 303       tty->print("%d : ", i);
 304       entry->literal()->print();
 305       tty->cr();
 306       entry = entry->next();
 307     }
 308   }
 309 }
 310 

 311 template <MEMFLAGS F>
 312 template <class T> void BasicHashtable<F>::verify_table(const char* table_name) {
 313   int element_count = 0;
 314   int max_bucket_count = 0;
 315   int max_bucket_number = 0;
 316   for (int index = 0; index < table_size(); index++) {
 317     int bucket_count = 0;
 318     for (T* probe = (T*)bucket(index); probe != NULL; probe = probe->next()) {
 319       probe->verify();
 320       bucket_count++;
 321     }
 322     element_count += bucket_count;
 323     if (bucket_count > max_bucket_count) {
 324       max_bucket_count = bucket_count;
 325       max_bucket_number = index;
 326     }
 327   }
 328   guarantee(number_of_entries() == element_count,
 329             "Verify of %s failed", table_name);







 330 
 331   // Log some statistics about the hashtable
 332   log_info(hashtables)("%s max bucket size %d bucket %d element count %d table size %d", table_name,
 333                        max_bucket_count, max_bucket_number, _number_of_entries, _table_size);
 334   if (_number_of_entries > 0 && log_is_enabled(Debug, hashtables)) {
 335     for (int index = 0; index < table_size(); index++) {
 336       int bucket_count = 0;
 337       for (T* probe = (T*)bucket(index); probe != NULL; probe = probe->next()) {
 338         log_debug(hashtables)("bucket %d hash " INTPTR_FORMAT, index, (intptr_t)probe->hash());
 339         bucket_count++;
 340       }
 341       if (bucket_count > 0) {
 342         log_debug(hashtables)("bucket %d count %d", index, bucket_count);
 343       }
 344     }
 345   }
 346 }
 347 #endif // PRODUCT


 348 
 349 // Explicitly instantiate these types
 350 #if INCLUDE_ALL_GCS
 351 template class Hashtable<nmethod*, mtGC>;
 352 template class HashtableEntry<nmethod*, mtGC>;
 353 template class BasicHashtable<mtGC>;
 354 #endif
 355 template class Hashtable<ConstantPool*, mtClass>;
 356 template class RehashableHashtable<Symbol*, mtSymbol>;
 357 template class RehashableHashtable<oopDesc*, mtSymbol>;
 358 template class Hashtable<Symbol*, mtSymbol>;
 359 template class Hashtable<Klass*, mtClass>;
 360 template class Hashtable<InstanceKlass*, mtClass>;
 361 template class Hashtable<oop, mtClass>;
 362 #if defined(SOLARIS) || defined(CHECK_UNHANDLED_OOPS)
 363 template class Hashtable<oop, mtSymbol>;
 364 template class RehashableHashtable<oop, mtSymbol>;
 365 #endif // SOLARIS || CHECK_UNHANDLED_OOPS
 366 template class Hashtable<oopDesc*, mtSymbol>;
 367 template class Hashtable<Symbol*, mtClass>;


 370 template class HashtableEntry<oop, mtSymbol>;
 371 template class BasicHashtableEntry<mtSymbol>;
 372 template class BasicHashtableEntry<mtCode>;
 373 template class BasicHashtable<mtClass>;
 374 template class BasicHashtable<mtClassShared>;
 375 template class BasicHashtable<mtSymbol>;
 376 template class BasicHashtable<mtCode>;
 377 template class BasicHashtable<mtInternal>;
 378 template class BasicHashtable<mtModule>;
 379 #if INCLUDE_TRACE
 380 template class Hashtable<Symbol*, mtTracing>;
 381 template class HashtableEntry<Symbol*, mtTracing>;
 382 template class BasicHashtable<mtTracing>;
 383 #endif
 384 template class BasicHashtable<mtCompiler>;
 385 
 386 template void BasicHashtable<mtClass>::verify_table<DictionaryEntry>(char const*);
 387 template void BasicHashtable<mtModule>::verify_table<ModuleEntry>(char const*);
 388 template void BasicHashtable<mtModule>::verify_table<PackageEntry>(char const*);
 389 template void BasicHashtable<mtClass>::verify_table<ProtectionDomainCacheEntry>(char const*);
 390 template void BasicHashtable<mtClass>::verify_table<PlaceholderEntry>(char const*);
 391 
< prev index next >