0N/A

1879N/A#include "precompiled.hpp"

1879N/A#include "memory/allocation.inline.hpp"

3460N/A#include "memory/filemap.hpp"

1879N/A#include "memory/resourceArea.hpp"

1879N/A#include "oops/oop.inline.hpp"

1879N/A#include "runtime/safepoint.hpp"

1879N/A#include "utilities/dtrace.hpp"

1879N/A#include "utilities/hashtable.hpp"

1879N/A#include "utilities/hashtable.inline.hpp"

0N/A

2062N/A

2842N/A#ifndef USDT2

0N/AHS_DTRACE_PROBE_DECL4(hs_private, hashtable__new_entry,

2062N/A void*, unsigned int, void*, void*);

2842N/A#endif /* !USDT2 */

0N/A

0N/A

0N/ABasicHashtableEntry* BasicHashtable::new_entry(unsigned int hashValue) {

0N/A BasicHashtableEntry* entry;

0N/A

0N/A if (_free_list) {

0N/A entry = _free_list;

0N/A _free_list = _free_list->next();

0N/A } else {

432N/A if (_first_free_entry + _entry_size >= _end_block) {

432N/A int block_size = MIN2(512, MAX2((int)_table_size / 2, (int)_number_of_entries));

0N/A int len = _entry_size * block_size;

432N/A len = 1 << log2_intptr(len); // round down to power of 2

432N/A assert(len >= _entry_size, "");

0N/A _first_free_entry = NEW_C_HEAP_ARRAY(char, len);

0N/A _end_block = _first_free_entry + len;

0N/A }

0N/A entry = (BasicHashtableEntry*)_first_free_entry;

0N/A _first_free_entry += _entry_size;

0N/A }

0N/A

432N/A assert(_entry_size % HeapWordSize == 0, "");

0N/A entry->set_hash(hashValue);

0N/A return entry;

0N/A}

0N/A

0N/A

2062N/Atemplate <class T> HashtableEntry<T>* Hashtable<T>::new_entry(unsigned int hashValue, T obj) {

2062N/A HashtableEntry<T>* entry;

0N/A

2062N/A entry = (HashtableEntry<T>*)BasicHashtable::new_entry(hashValue);

2062N/A entry->set_literal(obj);

2842N/A#ifndef USDT2

0N/A HS_DTRACE_PROBE4(hs_private, hashtable__new_entry,

0N/A this, hashValue, obj, entry);

2842N/A#else /* USDT2 */

2842N/A HS_PRIVATE_HASHTABLE_NEW_ENTRY(

2842N/A this, hashValue, (uintptr_t) obj, entry);

2842N/A#endif /* USDT2 */

0N/A return entry;

0N/A}

0N/A

0N/A

3448N/A

3448N/Abool BasicHashtable::check_rehash_table(int count) {

3448N/A assert(table_size() != 0, "underflow");

3448N/A if (count > (((double)number_of_entries()/(double)table_size())*rehash_multiple)) {

3448N/A // Set a flag for the next safepoint, which should be at some guaranteed

3448N/A // safepoint interval.

3448N/A return true;

3448N/A }

3448N/A return false;

3448N/A}

3448N/A

3448N/A

3448N/Atemplate <class T> void Hashtable<T>::move_to(Hashtable<T>* new_table) {

3448N/A int saved_entry_count = number_of_entries();

3448N/A

3448N/A // Iterate through the table and create a new entry for the new table

3448N/A for (int i = 0; i < new_table->table_size(); ++i) {

3448N/A for (HashtableEntry<T>* p = bucket(i); p != NULL; ) {

3448N/A HashtableEntry<T>* next = p->next();

3448N/A T string = p->literal();

3448N/A // Use alternate hashing algorithm on the symbol in the first table

3448N/A unsigned int hashValue = new_hash(string);

3448N/A // Get a new index relative to the new table (can also change size)

3448N/A int index = new_table->hash_to_index(hashValue);

3448N/A p->set_hash(hashValue);

3460N/A // Keep the shared bit in the Hashtable entry to indicate that this entry

3460N/A // can't be deleted. The shared bit is the LSB in the _next field so

3460N/A // walking the hashtable past these entries requires

3460N/A // BasicHashtableEntry::make_ptr() call.

3460N/A bool keep_shared = p->is_shared();

3448N/A unlink_entry(p);

3448N/A new_table->add_entry(index, p);

3460N/A if (keep_shared) {

3460N/A p->set_shared();

3460N/A }

3448N/A p = next;

3448N/A }

3448N/A }

3448N/A // give the new table the free list as well

3448N/A new_table->copy_freelist(this);

3448N/A assert(new_table->number_of_entries() == saved_entry_count, "lost entry on dictionary copy?");

3448N/A

3448N/A // Destroy memory used by the buckets in the hashtable. The memory

3448N/A // for the elements has been used in a new table and is not

3448N/A // destroyed. The memory reuse will benefit resizing the SystemDictionary

3448N/A // to avoid a memory allocation spike at safepoint.

3448N/A free_buckets();

3448N/A}

3448N/A

3460N/Avoid BasicHashtable::free_buckets() {

3460N/A if (NULL != _buckets) {

3460N/A // Don't delete the buckets in the shared space. They aren't

3460N/A // allocated by os::malloc

3460N/A if (!UseSharedSpaces ||

3460N/A !FileMapInfo::current_info()->is_in_shared_space(_buckets)) {

3460N/A FREE_C_HEAP_ARRAY(HashtableBucket, _buckets);

3460N/A }

3460N/A _buckets = NULL;

3460N/A }

3460N/A}

3460N/A

3460N/A

0N/A

0N/Avoid BasicHashtable::reverse() {

0N/A

0N/A for (int i = 0; i < _table_size; ++i) {

0N/A BasicHashtableEntry* new_list = NULL;

0N/A BasicHashtableEntry* p = bucket(i);

0N/A while (p != NULL) {

0N/A BasicHashtableEntry* next = p->next();

0N/A p->set_next(new_list);

0N/A new_list = p;

0N/A p = next;

0N/A }

0N/A *bucket_addr(i) = new_list;

0N/A }

0N/A}

0N/A

0N/A

0N/A

0N/Avoid BasicHashtable::copy_table(char** top, char* end) {

0N/A

0N/A // Dump the hash table entries.

0N/A

0N/A intptr_t *plen = (intptr_t*)(*top);

0N/A *top += sizeof(*plen);

0N/A

0N/A int i;

0N/A for (i = 0; i < _table_size; ++i) {

0N/A for (BasicHashtableEntry** p = _buckets[i].entry_addr();

0N/A *p != NULL;

0N/A p = (*p)->next_addr()) {

0N/A if (*top + entry_size() > end) {

2062N/A report_out_of_shared_space(SharedMiscData);

0N/A }

0N/A *p = (BasicHashtableEntry*)memcpy(*top, *p, entry_size());

0N/A *top += entry_size();

0N/A }

0N/A }

0N/A *plen = (char*)(*top) - (char*)plen - sizeof(*plen);

0N/A

0N/A // Set the shared bit.

0N/A

0N/A for (i = 0; i < _table_size; ++i) {

0N/A for (BasicHashtableEntry* p = bucket(i); p != NULL; p = p->next()) {

0N/A p->set_shared();

0N/A }

0N/A }

0N/A}

0N/A

0N/A

0N/A

0N/A

2062N/Atemplate <class T> void Hashtable<T>::reverse(void* boundary) {

0N/A

0N/A for (int i = 0; i < table_size(); ++i) {

2062N/A HashtableEntry<T>* high_list = NULL;

2062N/A HashtableEntry<T>* low_list = NULL;

2062N/A HashtableEntry<T>* last_low_entry = NULL;

2062N/A HashtableEntry<T>* p = bucket(i);

0N/A while (p != NULL) {

2062N/A HashtableEntry<T>* next = p->next();

0N/A if ((void*)p->literal() >= boundary) {

0N/A p->set_next(high_list);

0N/A high_list = p;

0N/A } else {

0N/A p->set_next(low_list);

0N/A low_list = p;

0N/A if (last_low_entry == NULL) {

0N/A last_low_entry = p;

0N/A }

0N/A }

0N/A p = next;

0N/A }

0N/A if (low_list != NULL) {

0N/A *bucket_addr(i) = low_list;

0N/A last_low_entry->set_next(high_list);

0N/A } else {

0N/A *bucket_addr(i) = high_list;

0N/A }

0N/A }

0N/A}

0N/A

0N/A

0N/A

0N/Avoid BasicHashtable::copy_buckets(char** top, char* end) {

0N/A intptr_t len = _table_size * sizeof(HashtableBucket);

0N/A *(intptr_t*)(*top) = len;

0N/A *top += sizeof(intptr_t);

0N/A

0N/A *(intptr_t*)(*top) = _number_of_entries;

0N/A *top += sizeof(intptr_t);

0N/A

0N/A if (*top + len > end) {

2062N/A report_out_of_shared_space(SharedMiscData);

0N/A }

0N/A _buckets = (HashtableBucket*)memcpy(*top, _buckets, len);

0N/A *top += len;

0N/A}

0N/A

0N/A

0N/A#ifndef PRODUCT

0N/A

2062N/Atemplate <class T> void Hashtable<T>::print() {

0N/A ResourceMark rm;

0N/A

0N/A for (int i = 0; i < table_size(); i++) {

2062N/A HashtableEntry<T>* entry = bucket(i);

0N/A while(entry != NULL) {

0N/A tty->print("%d : ", i);

0N/A entry->literal()->print();

0N/A tty->cr();

0N/A entry = entry->next();

0N/A }

0N/A }

0N/A}

0N/A

0N/A

0N/Avoid BasicHashtable::verify() {

0N/A int count = 0;

0N/A for (int i = 0; i < table_size(); i++) {

0N/A for (BasicHashtableEntry* p = bucket(i); p != NULL; p = p->next()) {

0N/A ++count;

0N/A }

0N/A }

0N/A assert(count == number_of_entries(), "number of hashtable entries incorrect");

0N/A}

0N/A

0N/A

0N/A#endif // PRODUCT

0N/A

0N/A

0N/A#ifdef ASSERT

0N/A

0N/Avoid BasicHashtable::verify_lookup_length(double load) {

0N/A if ((double)_lookup_length / (double)_lookup_count > load * 2.0) {

0N/A warning("Performance bug: SystemDictionary lookup_count=%d "

0N/A "lookup_length=%d average=%lf load=%f",

0N/A _lookup_count, _lookup_length,

0N/A (double) _lookup_length / _lookup_count, load);

0N/A }

0N/A}

0N/A

0N/A#endif

2062N/A

2062N/Atemplate class Hashtable<constantPoolOop>;

2062N/Atemplate class Hashtable<Symbol*>;

2062N/Atemplate class Hashtable<klassOop>;

2062N/Atemplate class Hashtable<oop>;

2062N/A