src/share/vm/utilities/hashtable.cpp
Index Unified diffs Context diffs Sdiffs Patch New Old Previous File Next File JDK-8034839 Sdiff src/share/vm/utilities

src/share/vm/utilities/hashtable.cpp

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 #include "precompiled.hpp"
  26 #include "classfile/altHashing.hpp"
  27 #include "classfile/javaClasses.hpp"

  28 #include "memory/allocation.inline.hpp"
  29 #include "memory/filemap.hpp"
  30 #include "memory/resourceArea.hpp"
  31 #include "oops/oop.inline.hpp"
  32 #include "runtime/safepoint.hpp"
  33 #include "utilities/dtrace.hpp"
  34 #include "utilities/hashtable.hpp"
  35 #include "utilities/hashtable.inline.hpp"
  36 #include "utilities/numberSeq.hpp"
  37 
  38 
  39 // This is a generic hashtable, designed to be used for the symbol
  40 // and string tables.
  41 //
  42 // It is implemented as an open hash table with a fixed number of buckets.
  43 //
  44 // %note:
  45 //  - HashtableEntrys are allocated in blocks to reduce the space overhead.
  46 
  47 template <MEMFLAGS F> BasicHashtableEntry<F>* BasicHashtable<F>::new_entry(unsigned int hashValue) {


 321       tty->cr();
 322       entry = entry->next();
 323     }
 324   }
 325 }
 326 
 327 
 328 template <MEMFLAGS F> void BasicHashtable<F>::verify() {
 329   int count = 0;
 330   for (int i = 0; i < table_size(); i++) {
 331     for (BasicHashtableEntry<F>* p = bucket(i); p != NULL; p = p->next()) {
 332       ++count;
 333     }
 334   }
 335   assert(count == number_of_entries(), "number of hashtable entries incorrect");
 336 }
 337 
 338 
 339 #endif // PRODUCT
 340 
 341 
 342 #ifdef ASSERT
 343 
 344 template <MEMFLAGS F> void BasicHashtable<F>::verify_lookup_length(double load) {
 345   if ((double)_lookup_length / (double)_lookup_count > load * 2.0) {
 346     warning("Performance bug: SystemDictionary lookup_count=%d "
 347             "lookup_length=%d average=%lf load=%f",
 348             _lookup_count, _lookup_length,
 349             (double) _lookup_length / _lookup_count, load);
 350   }
 351 }
 352 
 353 #endif
















































































































 354 // Explicitly instantiate these types
 355 template class Hashtable<ConstantPool*, mtClass>;
 356 template class Hashtable<Symbol*, mtSymbol>;
 357 template class Hashtable<Klass*, mtClass>;
 358 template class Hashtable<oop, mtClass>;
 359 #if defined(SOLARIS) || defined(CHECK_UNHANDLED_OOPS)
 360 template class Hashtable<oop, mtSymbol>;
 361 #endif // SOLARIS || CHECK_UNHANDLED_OOPS
 362 template class Hashtable<oopDesc*, mtSymbol>;
 363 template class Hashtable<Symbol*, mtClass>;
 364 template class HashtableEntry<Symbol*, mtSymbol>;
 365 template class HashtableEntry<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<mtSymbol>;
 371 template class BasicHashtable<mtCode>;
 372 template class BasicHashtable<mtInternal>;




   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 #include "precompiled.hpp"
  26 #include "classfile/altHashing.hpp"
  27 #include "classfile/javaClasses.hpp"
  28 #include "code/dependencies.hpp"
  29 #include "memory/allocation.inline.hpp"
  30 #include "memory/filemap.hpp"
  31 #include "memory/resourceArea.hpp"
  32 #include "oops/oop.inline.hpp"
  33 #include "runtime/safepoint.hpp"
  34 #include "utilities/dtrace.hpp"
  35 #include "utilities/hashtable.hpp"
  36 #include "utilities/hashtable.inline.hpp"
  37 #include "utilities/numberSeq.hpp"
  38 
  39 
  40 // This is a generic hashtable, designed to be used for the symbol
  41 // and string tables.
  42 //
  43 // It is implemented as an open hash table with a fixed number of buckets.
  44 //
  45 // %note:
  46 //  - HashtableEntrys are allocated in blocks to reduce the space overhead.
  47 
  48 template <MEMFLAGS F> BasicHashtableEntry<F>* BasicHashtable<F>::new_entry(unsigned int hashValue) {


 322       tty->cr();
 323       entry = entry->next();
 324     }
 325   }
 326 }
 327 
 328 
 329 template <MEMFLAGS F> void BasicHashtable<F>::verify() {
 330   int count = 0;
 331   for (int i = 0; i < table_size(); i++) {
 332     for (BasicHashtableEntry<F>* p = bucket(i); p != NULL; p = p->next()) {
 333       ++count;
 334     }
 335   }
 336   assert(count == number_of_entries(), "number of hashtable entries incorrect");
 337 }
 338 
 339 
 340 #endif // PRODUCT
 341 

 342 #ifdef ASSERT
 343 
 344 template <MEMFLAGS F> void BasicHashtable<F>::verify_lookup_length(double load) {
 345   if ((double)_lookup_length / (double)_lookup_count > load * 2.0) {
 346     warning("Performance bug: SystemDictionary lookup_count=%d "
 347             "lookup_length=%d average=%lf load=%f",
 348             _lookup_count, _lookup_length,
 349             (double) _lookup_length / _lookup_count, load);
 350   }
 351 }
 352 
 353 #endif
 354 
 355 
 356 template<class T, class M> GenericHashtable<T, M>::GenericHashtable(int size, bool C_heap, MEMFLAGS memflag) {
 357   assert(size > 0, " Invalid hashtable size");
 358   _size    = size;
 359   _C_heap  = C_heap;
 360   _memflag = memflag;
 361   // Perform subtype-specific resource allocation
 362   _items = (C_heap) ?  NEW_C_HEAP_ARRAY(T*, size, memflag) : NEW_RESOURCE_ARRAY(T*, size);
 363   memset(_items, 0, sizeof(T*) * size);
 364 
 365   DEBUG_ONLY(_num_items = 0;)
 366 }
 367 
 368 template<class T, class M> GenericHashtable<T, M>::~GenericHashtable() {
 369   if (on_C_heap()) {
 370     // Check backing array
 371     for (int i = 0; i < size(); i++) {
 372       T* item = head(i);
 373       // Delete all items in linked list
 374       while (item != NULL) {
 375         T* next_item = item->next();
 376         delete item;
 377         DEBUG_ONLY(_num_items--);
 378         item = next_item;
 379       }
 380     }
 381     FREE_C_HEAP_ARRAY(T*, _items, _memflag);
 382     _items = NULL;
 383     assert (_num_items == 0, "Not all memory released");
 384   }
 385 }
 386 
 387 /**
 388  * Return a pointer to the item 'I' that is stored in the hashtable for
 389  * which match_item->equals(I) == true. If no such item is found, NULL
 390  * is returned.
 391  */
 392 template<class T, class F> T* GenericHashtable<T, F>::contains(T* match_item) {
 393   if (match_item != NULL) {
 394     int idx = index(match_item);
 395     return contains_impl(match_item, idx);
 396   }
 397   return NULL;
 398 }
 399 
 400 /**
 401  * Add item to the hashtable. Return 'true' if the item was added
 402  * and false otherwise.
 403  */
 404 template<class T, class F> bool GenericHashtable<T, F>::add(T* item) {
 405   if (item != NULL) {
 406     int idx = index(item);
 407     T* found_item = contains_impl(item, idx);
 408     if (found_item == NULL) {
 409       T* list_head = head(idx);
 410       item->set_next(list_head);
 411       item->set_prev(NULL);
 412 
 413       if (list_head != NULL) {
 414         list_head->set_prev(item);
 415       }
 416       set_head(item, idx);
 417       DEBUG_ONLY(_num_items++);
 418       return true;
 419     }
 420   }
 421   return false;
 422 }
 423 
 424 /**
 425  * Removes an item 'I' from the hashtable, if present. 'I' is removed, if
 426  * match_item->equals(I) == true. Removing an item from the hashtable does
 427  * not free memory.
 428  */
 429 template<class T, class F> T* GenericHashtable<T, F>::remove(T* match_item) {
 430   if (match_item != NULL) {
 431     int idx = index(match_item);
 432     T* found_item = contains_impl(match_item, idx);
 433     if (found_item != NULL) {
 434       // Remove item from linked list
 435       T* prev = found_item->prev();
 436       T* next = found_item->next();
 437       if (prev != NULL) {
 438         prev->set_next(next);
 439       } else {
 440         set_head(next, idx);
 441       }
 442       if (next != NULL) {
 443         next->set_prev(prev);
 444       }
 445 
 446       DEBUG_ONLY(_num_items--);
 447       return found_item;
 448     }
 449   }
 450   return NULL;
 451 }
 452 
 453 
 454 template<class T, class F> T* GenericHashtable<T, F>::contains_impl(T* item, int idx) {
 455   T* current_item = head(idx);
 456   while (current_item != NULL) {
 457     if (current_item->equals(item)) {
 458       return current_item;
 459     }
 460     current_item = current_item->next();
 461   }
 462   return NULL;
 463 }
 464 
 465 
 466 // Explicitly instantiate these types
 467 template class Hashtable<ConstantPool*, mtClass>;
 468 template class Hashtable<Symbol*, mtSymbol>;
 469 template class Hashtable<Klass*, mtClass>;
 470 template class Hashtable<oop, mtClass>;
 471 #if defined(SOLARIS) || defined(CHECK_UNHANDLED_OOPS)
 472 template class Hashtable<oop, mtSymbol>;
 473 #endif // SOLARIS || CHECK_UNHANDLED_OOPS
 474 template class Hashtable<oopDesc*, mtSymbol>;
 475 template class Hashtable<Symbol*, mtClass>;
 476 template class HashtableEntry<Symbol*, mtSymbol>;
 477 template class HashtableEntry<Symbol*, mtClass>;
 478 template class HashtableEntry<oop, mtSymbol>;
 479 template class BasicHashtableEntry<mtSymbol>;
 480 template class BasicHashtableEntry<mtCode>;
 481 template class BasicHashtable<mtClass>;
 482 template class BasicHashtable<mtSymbol>;
 483 template class BasicHashtable<mtCode>;
 484 template class BasicHashtable<mtInternal>;
 485 
 486 template class GenericHashtable<DependencySignature, ResourceObj>;
src/share/vm/utilities/hashtable.cpp
Index Unified diffs Context diffs Sdiffs Patch New Old Previous File Next File