hashtable.cpp revision 3867
/*
* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
*
* under the terms of the GNU General Public License version 2 only, as
* published by the Free Software Foundation.
*
* This code is distributed in the hope that it will be useful, but WITHOUT
* ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
* FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
* version 2 for more details (a copy is included in the LICENSE file that
* accompanied this code).
*
* You should have received a copy of the GNU General Public License version
* 2 along with this work; if not, write to the Free Software Foundation,
* Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
*
* Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
* or visit www.oracle.com if you need additional information or have any
* questions.
*
*/
#include "precompiled.hpp"
#include "classfile/altHashing.hpp"
#include "classfile/javaClasses.hpp"
#include "memory/allocation.inline.hpp"
#include "memory/filemap.hpp"
#include "memory/resourceArea.hpp"
#include "oops/oop.inline.hpp"
#include "runtime/safepoint.hpp"
#include "utilities/dtrace.hpp"
#include "utilities/hashtable.hpp"
#include "utilities/hashtable.inline.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;
if (_free_list) {
entry = _free_list;
} else {
}
}
return entry;
}
template <class T, MEMFLAGS F> HashtableEntry<T, F>* Hashtable<T, F>::new_entry(unsigned int hashValue, T obj) {
HashtableEntry<T, F>* entry;
return entry;
}
// Check to see if the hashtable is unbalanced. The caller set a flag to
// 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.
// Set a flag for the next safepoint, which should be at some guaranteed
// safepoint interval.
return true;
}
return false;
}
// Use alternate hashing algorithm on this symbol.
}
int length;
// Use alternate hashing algorithm on the string
}
// 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.
// Initialize the global seed for hashing.
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) {
// Use alternate hashing algorithm on the symbol in the first table
// Get a new index relative to the new table (can also change size)
// Keep the shared bit in the Hashtable entry to indicate that this entry
// can't be deleted. The shared bit is the LSB in the _next field so
// walking the hashtable past these entries requires
// BasicHashtableEntry::make_ptr() call.
bool keep_shared = p->is_shared();
unlink_entry(p);
if (keep_shared) {
p->set_shared();
}
p = next;
}
}
// give the new table the free list as well
new_table->copy_freelist(this);
// Destroy memory used by the buckets in the hashtable. The memory
// for the elements has been used in a new table and is not
// destroyed. The memory reuse will benefit resizing the SystemDictionary
// to avoid a memory allocation spike at safepoint.
BasicHashtable<F>::free_buckets();
}
// Don't delete the buckets in the shared space. They aren't
// allocated by os::malloc
if (!UseSharedSpaces ||
}
}
}
// Reverse the order of elements in the hash buckets.
for (int i = 0; i < _table_size; ++i) {
BasicHashtableEntry<F>* p = bucket(i);
while (p != NULL) {
new_list = p;
p = next;
}
*bucket_addr(i) = new_list;
}
}
// Copy the table to the shared space.
// Dump the hash table entries.
int i;
for (i = 0; i < _table_size; ++i) {
*p != NULL;
p = (*p)->next_addr()) {
}
*top += entry_size();
}
}
// Set the shared bit.
for (i = 0; i < _table_size; ++i) {
p->set_shared();
}
}
}
// Reverse the order of elements in the hash buckets.
for (int i = 0; i < this->table_size(); ++i) {
HashtableEntry<T, F>* p = bucket(i);
while (p != NULL) {
high_list = p;
} else {
low_list = p;
if (last_low_entry == NULL) {
last_low_entry = p;
}
}
p = next;
}
*bucket_addr(i) = low_list;
} else {
*bucket_addr(i) = high_list;
}
}
}
// Dump the hash table buckets.
}
}
#ifndef PRODUCT
for (int i = 0; i < BasicHashtable<F>::table_size(); i++) {
}
}
}
int count = 0;
for (int i = 0; i < table_size(); i++) {
++count;
}
}
}
#endif // PRODUCT
#ifdef ASSERT
warning("Performance bug: SystemDictionary lookup_count=%d "
"lookup_length=%d average=%lf load=%f",
}
}
#endif
// Explicitly instantiate these types
#ifdef SOLARIS
#endif
template class BasicHashtableEntry<mtSymbol>;
template class BasicHashtableEntry<mtCode>;
template class BasicHashtable<mtClass>;
template class BasicHashtable<mtSymbol>;
template class BasicHashtable<mtCode>;
template class BasicHashtable<mtInternal>;