0N/A/*
3149N/A * Copyright (c) 2003, 2012, Oracle and/or its affiliates. All rights reserved.
0N/A * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
0N/A *
0N/A * This code is free software; you can redistribute it and/or modify it
0N/A * under the terms of the GNU General Public License version 2 only, as
0N/A * published by the Free Software Foundation.
0N/A *
0N/A * This code is distributed in the hope that it will be useful, but WITHOUT
0N/A * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
0N/A * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
0N/A * version 2 for more details (a copy is included in the LICENSE file that
0N/A * accompanied this code).
0N/A *
0N/A * You should have received a copy of the GNU General Public License version
0N/A * 2 along with this work; if not, write to the Free Software Foundation,
0N/A * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
0N/A *
1472N/A * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
1472N/A * or visit www.oracle.com if you need additional information or have any
1472N/A * questions.
0N/A *
0N/A */
0N/A
1879N/A#ifndef SHARE_VM_UTILITIES_HASHTABLE_HPP
1879N/A#define SHARE_VM_UTILITIES_HASHTABLE_HPP
1879N/A
1879N/A#include "memory/allocation.hpp"
1879N/A#include "oops/oop.hpp"
2062N/A#include "oops/symbol.hpp"
1879N/A#include "runtime/handles.hpp"
1879N/A
0N/A// This is a generic hashtable, designed to be used for the symbol
0N/A// and string tables.
0N/A//
0N/A// It is implemented as an open hash table with a fixed number of buckets.
0N/A//
0N/A// %note:
0N/A// - TableEntrys are allocated in blocks to reduce the space overhead.
0N/A
0N/A
0N/A
3863N/Atemplate <MEMFLAGS F> class BasicHashtableEntry : public CHeapObj<F> {
0N/A friend class VMStructs;
0N/Aprivate:
0N/A unsigned int _hash; // 32-bit hash for item
0N/A
0N/A // Link to next element in the linked list for this bucket. EXCEPT
0N/A // bit 0 set indicates that this entry is shared and must not be
0N/A // unlinked from the table. Bit 0 is set during the dumping of the
0N/A // archive. Since shared entries are immutable, _next fields in the
0N/A // shared entries will not change. New entries will always be
0N/A // unshared and since pointers are align, bit 0 will always remain 0
0N/A // with no extra effort.
3863N/A BasicHashtableEntry<F>* _next;
0N/A
0N/A // Windows IA64 compiler requires subclasses to be able to access these
0N/Aprotected:
0N/A // Entry objects should not be created, they should be taken from the
0N/A // free list with BasicHashtable.new_entry().
0N/A BasicHashtableEntry() { ShouldNotReachHere(); }
0N/A // Entry objects should not be destroyed. They should be placed on
0N/A // the free list instead with BasicHashtable.free_entry().
0N/A ~BasicHashtableEntry() { ShouldNotReachHere(); }
0N/A
0N/Apublic:
0N/A
0N/A unsigned int hash() const { return _hash; }
0N/A void set_hash(unsigned int hash) { _hash = hash; }
0N/A unsigned int* hash_addr() { return &_hash; }
0N/A
3863N/A static BasicHashtableEntry<F>* make_ptr(BasicHashtableEntry<F>* p) {
0N/A return (BasicHashtableEntry*)((intptr_t)p & -2);
0N/A }
0N/A
3863N/A BasicHashtableEntry<F>* next() const {
0N/A return make_ptr(_next);
0N/A }
0N/A
3863N/A void set_next(BasicHashtableEntry<F>* next) {
0N/A _next = next;
0N/A }
0N/A
3863N/A BasicHashtableEntry<F>** next_addr() {
0N/A return &_next;
0N/A }
0N/A
0N/A bool is_shared() const {
0N/A return ((intptr_t)_next & 1) != 0;
0N/A }
0N/A
0N/A void set_shared() {
3863N/A _next = (BasicHashtableEntry<F>*)((intptr_t)_next | 1);
0N/A }
0N/A};
0N/A
0N/A
0N/A
3863N/Atemplate <class T, MEMFLAGS F> class HashtableEntry : public BasicHashtableEntry<F> {
0N/A friend class VMStructs;
0N/Aprivate:
2062N/A T _literal; // ref to item in table.
0N/A
0N/Apublic:
0N/A // Literal
2062N/A T literal() const { return _literal; }
2062N/A T* literal_addr() { return &_literal; }
2062N/A void set_literal(T s) { _literal = s; }
0N/A
0N/A HashtableEntry* next() const {
3863N/A return (HashtableEntry*)BasicHashtableEntry<F>::next();
0N/A }
0N/A HashtableEntry** next_addr() {
3863N/A return (HashtableEntry**)BasicHashtableEntry<F>::next_addr();
0N/A }
0N/A};
0N/A
0N/A
0N/A
3863N/Atemplate <MEMFLAGS F> class HashtableBucket : public CHeapObj<F> {
0N/A friend class VMStructs;
0N/Aprivate:
0N/A // Instance variable
3863N/A BasicHashtableEntry<F>* _entry;
0N/A
0N/Apublic:
0N/A // Accessing
0N/A void clear() { _entry = NULL; }
0N/A
0N/A // The following methods use order access methods to avoid race
0N/A // conditions in multiprocessor systems.
3863N/A BasicHashtableEntry<F>* get_entry() const;
3863N/A void set_entry(BasicHashtableEntry<F>* l);
0N/A
0N/A // The following method is not MT-safe and must be done under lock.
3863N/A BasicHashtableEntry<F>** entry_addr() { return &_entry; }
0N/A};
0N/A
0N/A
3863N/Atemplate <MEMFLAGS F> class BasicHashtable : public CHeapObj<F> {
0N/A friend class VMStructs;
0N/A
0N/Apublic:
0N/A BasicHashtable(int table_size, int entry_size);
0N/A BasicHashtable(int table_size, int entry_size,
3863N/A HashtableBucket<F>* buckets, int number_of_entries);
0N/A
0N/A // Sharing support.
0N/A void copy_buckets(char** top, char* end);
0N/A void copy_table(char** top, char* end);
0N/A
0N/A // Bucket handling
0N/A int hash_to_index(unsigned int full_hash) {
0N/A int h = full_hash % _table_size;
0N/A assert(h >= 0 && h < _table_size, "Illegal hash value");
0N/A return h;
0N/A }
0N/A
0N/A // Reverse the order of elements in each of the buckets.
0N/A void reverse();
0N/A
0N/Aprivate:
0N/A // Instance variables
0N/A int _table_size;
3863N/A HashtableBucket<F>* _buckets;
3863N/A BasicHashtableEntry<F>* _free_list;
0N/A char* _first_free_entry;
0N/A char* _end_block;
0N/A int _entry_size;
0N/A int _number_of_entries;
0N/A
0N/Aprotected:
0N/A
0N/A#ifdef ASSERT
0N/A int _lookup_count;
0N/A int _lookup_length;
0N/A void verify_lookup_length(double load);
0N/A#endif
0N/A
3448N/A enum {
3448N/A rehash_count = 100,
3448N/A rehash_multiple = 60
3448N/A };
3448N/A
0N/A void initialize(int table_size, int entry_size, int number_of_entries);
0N/A
0N/A // Accessor
0N/A int entry_size() const { return _entry_size; }
0N/A
0N/A // The following method is MT-safe and may be used with caution.
3863N/A BasicHashtableEntry<F>* bucket(int i);
0N/A
0N/A // The following method is not MT-safe and must be done under lock.
3863N/A BasicHashtableEntry<F>** bucket_addr(int i) { return _buckets[i].entry_addr(); }
0N/A
0N/A // Table entry management
3863N/A BasicHashtableEntry<F>* new_entry(unsigned int hashValue);
0N/A
3448N/A // Check that the table is unbalanced
3448N/A bool check_rehash_table(int count);
3448N/A
3448N/A // Used when moving the entry to another table
3448N/A // Clean up links, but do not add to free_list
3863N/A void unlink_entry(BasicHashtableEntry<F>* entry) {
3448N/A entry->set_next(NULL);
3448N/A --_number_of_entries;
3448N/A }
3448N/A
3448N/A // Move over freelist and free block for allocation
3448N/A void copy_freelist(BasicHashtable* src) {
3448N/A _free_list = src->_free_list;
3448N/A src->_free_list = NULL;
3448N/A _first_free_entry = src->_first_free_entry;
3448N/A src->_first_free_entry = NULL;
3448N/A _end_block = src->_end_block;
3448N/A src->_end_block = NULL;
3448N/A }
3448N/A
3448N/A // Free the buckets in this hashtable
3460N/A void free_buckets();
3448N/A
0N/Apublic:
3149N/A int table_size() { return _table_size; }
3863N/A void set_entry(int index, BasicHashtableEntry<F>* entry);
0N/A
3863N/A void add_entry(int index, BasicHashtableEntry<F>* entry);
0N/A
3863N/A void free_entry(BasicHashtableEntry<F>* entry);
0N/A
0N/A int number_of_entries() { return _number_of_entries; }
0N/A
0N/A void verify() PRODUCT_RETURN;
0N/A};
0N/A
0N/A
3863N/Atemplate <class T, MEMFLAGS F> class Hashtable : public BasicHashtable<F> {
0N/A friend class VMStructs;
0N/A
0N/Apublic:
0N/A Hashtable(int table_size, int entry_size)
3863N/A : BasicHashtable<F>(table_size, entry_size) { }
0N/A
0N/A Hashtable(int table_size, int entry_size,
3863N/A HashtableBucket<F>* buckets, int number_of_entries)
3863N/A : BasicHashtable<F>(table_size, entry_size, buckets, number_of_entries) { }
0N/A
0N/A // Debugging
0N/A void print() PRODUCT_RETURN;
0N/A
0N/A // Reverse the order of elements in each of the buckets. Hashtable
0N/A // entries which refer to objects at a lower address than 'boundary'
0N/A // are separated from those which refer to objects at higher
0N/A // addresses, and appear first in the list.
0N/A void reverse(void* boundary = NULL);
0N/A
0N/Aprotected:
0N/A
2062N/A unsigned int compute_hash(Symbol* name) {
0N/A return (unsigned int) name->identity_hash();
0N/A }
0N/A
2062N/A int index_for(Symbol* name) {
3926N/A return this->hash_to_index(compute_hash(name));
0N/A }
0N/A
0N/A // Table entry management
3863N/A HashtableEntry<T, F>* new_entry(unsigned int hashValue, T obj);
0N/A
0N/A // The following method is MT-safe and may be used with caution.
3863N/A HashtableEntry<T, F>* bucket(int i) {
3863N/A return (HashtableEntry<T, F>*)BasicHashtable<F>::bucket(i);
0N/A }
0N/A
0N/A // The following method is not MT-safe and must be done under lock.
3863N/A HashtableEntry<T, F>** bucket_addr(int i) {
3863N/A return (HashtableEntry<T, F>**)BasicHashtable<F>::bucket_addr(i);
0N/A }
3448N/A
3448N/A // Function to move these elements into the new table.
3863N/A void move_to(Hashtable<T, F>* new_table);
3867N/A static bool use_alternate_hashcode() { return _seed != 0; }
3867N/A static jint seed() { return _seed; }
3867N/A
3867N/A private:
3867N/A static jint _seed;
3867N/A
3867N/A unsigned int new_hash(Symbol* s);
3867N/A unsigned int new_hash(oop string);
0N/A};
0N/A
0N/A
0N/A// Verions of hashtable where two handles are used to compute the index.
0N/A
3863N/Atemplate <class T, MEMFLAGS F> class TwoOopHashtable : public Hashtable<T, F> {
0N/A friend class VMStructs;
0N/Aprotected:
0N/A TwoOopHashtable(int table_size, int entry_size)
3863N/A : Hashtable<T, F>(table_size, entry_size) {}
0N/A
3863N/A TwoOopHashtable(int table_size, int entry_size, HashtableBucket<F>* t,
0N/A int number_of_entries)
3863N/A : Hashtable<T, F>(table_size, entry_size, t, number_of_entries) {}
0N/A
0N/Apublic:
2062N/A unsigned int compute_hash(Symbol* name, Handle loader) {
0N/A // Be careful with identity_hash(), it can safepoint and if this
0N/A // were one expression, the compiler could choose to unhandle each
0N/A // oop before calling identity_hash() for either of them. If the first
0N/A // causes a GC, the next would fail.
0N/A unsigned int name_hash = name->identity_hash();
0N/A unsigned int loader_hash = loader.is_null() ? 0 : loader->identity_hash();
0N/A return name_hash ^ loader_hash;
0N/A }
0N/A
2062N/A int index_for(Symbol* name, Handle loader) {
2112N/A return this->hash_to_index(compute_hash(name, loader));
0N/A }
0N/A};
1879N/A
1879N/A#endif // SHARE_VM_UTILITIES_HASHTABLE_HPP