1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/src/share/vm/utilities/hashtable.hpp Wed Apr 27 01:25:04 2016 +0800
1.3 @@ -0,0 +1,330 @@
1.4 +/*
1.5 + * Copyright (c) 2003, 2014, Oracle and/or its affiliates. All rights reserved.
1.6 + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
1.7 + *
1.8 + * This code is free software; you can redistribute it and/or modify it
1.9 + * under the terms of the GNU General Public License version 2 only, as
1.10 + * published by the Free Software Foundation.
1.11 + *
1.12 + * This code is distributed in the hope that it will be useful, but WITHOUT
1.13 + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
1.14 + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
1.15 + * version 2 for more details (a copy is included in the LICENSE file that
1.16 + * accompanied this code).
1.17 + *
1.18 + * You should have received a copy of the GNU General Public License version
1.19 + * 2 along with this work; if not, write to the Free Software Foundation,
1.20 + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
1.21 + *
1.22 + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
1.23 + * or visit www.oracle.com if you need additional information or have any
1.24 + * questions.
1.25 + *
1.26 + */
1.27 +
1.28 +#ifndef SHARE_VM_UTILITIES_HASHTABLE_HPP
1.29 +#define SHARE_VM_UTILITIES_HASHTABLE_HPP
1.30 +
1.31 +#include "classfile/classLoaderData.hpp"
1.32 +#include "memory/allocation.hpp"
1.33 +#include "oops/oop.hpp"
1.34 +#include "oops/symbol.hpp"
1.35 +#include "runtime/handles.hpp"
1.36 +
1.37 +// This is a generic hashtable, designed to be used for the symbol
1.38 +// and string tables.
1.39 +//
1.40 +// It is implemented as an open hash table with a fixed number of buckets.
1.41 +//
1.42 +// %note:
1.43 +// - TableEntrys are allocated in blocks to reduce the space overhead.
1.44 +
1.45 +
1.46 +
1.47 +template <MEMFLAGS F> class BasicHashtableEntry : public CHeapObj<F> {
1.48 + friend class VMStructs;
1.49 +private:
1.50 + unsigned int _hash; // 32-bit hash for item
1.51 +
1.52 + // Link to next element in the linked list for this bucket. EXCEPT
1.53 + // bit 0 set indicates that this entry is shared and must not be
1.54 + // unlinked from the table. Bit 0 is set during the dumping of the
1.55 + // archive. Since shared entries are immutable, _next fields in the
1.56 + // shared entries will not change. New entries will always be
1.57 + // unshared and since pointers are align, bit 0 will always remain 0
1.58 + // with no extra effort.
1.59 + BasicHashtableEntry<F>* _next;
1.60 +
1.61 + // Windows IA64 compiler requires subclasses to be able to access these
1.62 +protected:
1.63 + // Entry objects should not be created, they should be taken from the
1.64 + // free list with BasicHashtable.new_entry().
1.65 + BasicHashtableEntry() { ShouldNotReachHere(); }
1.66 + // Entry objects should not be destroyed. They should be placed on
1.67 + // the free list instead with BasicHashtable.free_entry().
1.68 + ~BasicHashtableEntry() { ShouldNotReachHere(); }
1.69 +
1.70 +public:
1.71 +
1.72 + unsigned int hash() const { return _hash; }
1.73 + void set_hash(unsigned int hash) { _hash = hash; }
1.74 + unsigned int* hash_addr() { return &_hash; }
1.75 +
1.76 + static BasicHashtableEntry<F>* make_ptr(BasicHashtableEntry<F>* p) {
1.77 + return (BasicHashtableEntry*)((intptr_t)p & -2);
1.78 + }
1.79 +
1.80 + BasicHashtableEntry<F>* next() const {
1.81 + return make_ptr(_next);
1.82 + }
1.83 +
1.84 + void set_next(BasicHashtableEntry<F>* next) {
1.85 + _next = next;
1.86 + }
1.87 +
1.88 + BasicHashtableEntry<F>** next_addr() {
1.89 + return &_next;
1.90 + }
1.91 +
1.92 + bool is_shared() const {
1.93 + return ((intptr_t)_next & 1) != 0;
1.94 + }
1.95 +
1.96 + void set_shared() {
1.97 + _next = (BasicHashtableEntry<F>*)((intptr_t)_next | 1);
1.98 + }
1.99 +};
1.100 +
1.101 +
1.102 +
1.103 +template <class T, MEMFLAGS F> class HashtableEntry : public BasicHashtableEntry<F> {
1.104 + friend class VMStructs;
1.105 +private:
1.106 + T _literal; // ref to item in table.
1.107 +
1.108 +public:
1.109 + // Literal
1.110 + T literal() const { return _literal; }
1.111 + T* literal_addr() { return &_literal; }
1.112 + void set_literal(T s) { _literal = s; }
1.113 +
1.114 + HashtableEntry* next() const {
1.115 + return (HashtableEntry*)BasicHashtableEntry<F>::next();
1.116 + }
1.117 + HashtableEntry** next_addr() {
1.118 + return (HashtableEntry**)BasicHashtableEntry<F>::next_addr();
1.119 + }
1.120 +};
1.121 +
1.122 +
1.123 +
1.124 +template <MEMFLAGS F> class HashtableBucket : public CHeapObj<F> {
1.125 + friend class VMStructs;
1.126 +private:
1.127 + // Instance variable
1.128 + BasicHashtableEntry<F>* _entry;
1.129 +
1.130 +public:
1.131 + // Accessing
1.132 + void clear() { _entry = NULL; }
1.133 +
1.134 + // The following methods use order access methods to avoid race
1.135 + // conditions in multiprocessor systems.
1.136 + BasicHashtableEntry<F>* get_entry() const;
1.137 + void set_entry(BasicHashtableEntry<F>* l);
1.138 +
1.139 + // The following method is not MT-safe and must be done under lock.
1.140 + BasicHashtableEntry<F>** entry_addr() { return &_entry; }
1.141 +};
1.142 +
1.143 +
1.144 +template <MEMFLAGS F> class BasicHashtable : public CHeapObj<F> {
1.145 + friend class VMStructs;
1.146 +
1.147 +public:
1.148 + BasicHashtable(int table_size, int entry_size);
1.149 + BasicHashtable(int table_size, int entry_size,
1.150 + HashtableBucket<F>* buckets, int number_of_entries);
1.151 +
1.152 + // Sharing support.
1.153 + void copy_buckets(char** top, char* end);
1.154 + void copy_table(char** top, char* end);
1.155 +
1.156 + // Bucket handling
1.157 + int hash_to_index(unsigned int full_hash) {
1.158 + int h = full_hash % _table_size;
1.159 + assert(h >= 0 && h < _table_size, "Illegal hash value");
1.160 + return h;
1.161 + }
1.162 +
1.163 + // Reverse the order of elements in each of the buckets.
1.164 + void reverse();
1.165 +
1.166 +private:
1.167 + // Instance variables
1.168 + int _table_size;
1.169 + HashtableBucket<F>* _buckets;
1.170 + BasicHashtableEntry<F>* _free_list;
1.171 + char* _first_free_entry;
1.172 + char* _end_block;
1.173 + int _entry_size;
1.174 + int _number_of_entries;
1.175 +
1.176 +protected:
1.177 +
1.178 +#ifdef ASSERT
1.179 + int _lookup_count;
1.180 + int _lookup_length;
1.181 + void verify_lookup_length(double load);
1.182 +#endif
1.183 +
1.184 + enum {
1.185 + rehash_count = 100,
1.186 + rehash_multiple = 60
1.187 + };
1.188 +
1.189 + void initialize(int table_size, int entry_size, int number_of_entries);
1.190 +
1.191 + // Accessor
1.192 + int entry_size() const { return _entry_size; }
1.193 +
1.194 + // The following method is MT-safe and may be used with caution.
1.195 + BasicHashtableEntry<F>* bucket(int i);
1.196 +
1.197 + // The following method is not MT-safe and must be done under lock.
1.198 + BasicHashtableEntry<F>** bucket_addr(int i) { return _buckets[i].entry_addr(); }
1.199 +
1.200 + // Table entry management
1.201 + BasicHashtableEntry<F>* new_entry(unsigned int hashValue);
1.202 +
1.203 + // Check that the table is unbalanced
1.204 + bool check_rehash_table(int count);
1.205 +
1.206 + // Used when moving the entry to another table
1.207 + // Clean up links, but do not add to free_list
1.208 + void unlink_entry(BasicHashtableEntry<F>* entry) {
1.209 + entry->set_next(NULL);
1.210 + --_number_of_entries;
1.211 + }
1.212 +
1.213 + // Move over freelist and free block for allocation
1.214 + void copy_freelist(BasicHashtable* src) {
1.215 + _free_list = src->_free_list;
1.216 + src->_free_list = NULL;
1.217 + _first_free_entry = src->_first_free_entry;
1.218 + src->_first_free_entry = NULL;
1.219 + _end_block = src->_end_block;
1.220 + src->_end_block = NULL;
1.221 + }
1.222 +
1.223 + // Free the buckets in this hashtable
1.224 + void free_buckets();
1.225 +
1.226 +public:
1.227 + int table_size() { return _table_size; }
1.228 + void set_entry(int index, BasicHashtableEntry<F>* entry);
1.229 +
1.230 + void add_entry(int index, BasicHashtableEntry<F>* entry);
1.231 +
1.232 + void free_entry(BasicHashtableEntry<F>* entry);
1.233 +
1.234 + int number_of_entries() { return _number_of_entries; }
1.235 +
1.236 + void verify() PRODUCT_RETURN;
1.237 +};
1.238 +
1.239 +
1.240 +template <class T, MEMFLAGS F> class Hashtable : public BasicHashtable<F> {
1.241 + friend class VMStructs;
1.242 +
1.243 +public:
1.244 + Hashtable(int table_size, int entry_size)
1.245 + : BasicHashtable<F>(table_size, entry_size) { }
1.246 +
1.247 + Hashtable(int table_size, int entry_size,
1.248 + HashtableBucket<F>* buckets, int number_of_entries)
1.249 + : BasicHashtable<F>(table_size, entry_size, buckets, number_of_entries) { }
1.250 +
1.251 + // Debugging
1.252 + void print() PRODUCT_RETURN;
1.253 +
1.254 + // Reverse the order of elements in each of the buckets. Hashtable
1.255 + // entries which refer to objects at a lower address than 'boundary'
1.256 + // are separated from those which refer to objects at higher
1.257 + // addresses, and appear first in the list.
1.258 + void reverse(void* boundary = NULL);
1.259 +
1.260 +protected:
1.261 +
1.262 + unsigned int compute_hash(Symbol* name) {
1.263 + return (unsigned int) name->identity_hash();
1.264 + }
1.265 +
1.266 + int index_for(Symbol* name) {
1.267 + return this->hash_to_index(compute_hash(name));
1.268 + }
1.269 +
1.270 + // Table entry management
1.271 + HashtableEntry<T, F>* new_entry(unsigned int hashValue, T obj);
1.272 +
1.273 + // The following method is MT-safe and may be used with caution.
1.274 + HashtableEntry<T, F>* bucket(int i) {
1.275 + return (HashtableEntry<T, F>*)BasicHashtable<F>::bucket(i);
1.276 + }
1.277 +
1.278 + // The following method is not MT-safe and must be done under lock.
1.279 + HashtableEntry<T, F>** bucket_addr(int i) {
1.280 + return (HashtableEntry<T, F>**)BasicHashtable<F>::bucket_addr(i);
1.281 + }
1.282 +
1.283 + // Function to move these elements into the new table.
1.284 + void move_to(Hashtable<T, F>* new_table);
1.285 + static bool use_alternate_hashcode() { return _seed != 0; }
1.286 + static juint seed() { return _seed; }
1.287 +
1.288 + static int literal_size(Symbol *symbol);
1.289 + static int literal_size(oop oop);
1.290 +
1.291 + // The following two are currently not used, but are needed anyway because some
1.292 + // C++ compilers (MacOS and Solaris) force the instantiation of
1.293 + // Hashtable<ConstantPool*, mtClass>::dump_table() even though we never call this function
1.294 + // in the VM code.
1.295 + static int literal_size(ConstantPool *cp) {Unimplemented(); return 0;}
1.296 + static int literal_size(Klass *k) {Unimplemented(); return 0;}
1.297 +
1.298 +public:
1.299 + void dump_table(outputStream* st, const char *table_name);
1.300 +
1.301 + private:
1.302 + static juint _seed;
1.303 +};
1.304 +
1.305 +
1.306 +// Verions of hashtable where two handles are used to compute the index.
1.307 +
1.308 +template <class T, MEMFLAGS F> class TwoOopHashtable : public Hashtable<T, F> {
1.309 + friend class VMStructs;
1.310 +protected:
1.311 + TwoOopHashtable(int table_size, int entry_size)
1.312 + : Hashtable<T, F>(table_size, entry_size) {}
1.313 +
1.314 + TwoOopHashtable(int table_size, int entry_size, HashtableBucket<F>* t,
1.315 + int number_of_entries)
1.316 + : Hashtable<T, F>(table_size, entry_size, t, number_of_entries) {}
1.317 +
1.318 +public:
1.319 + unsigned int compute_hash(Symbol* name, ClassLoaderData* loader_data) {
1.320 + unsigned int name_hash = name->identity_hash();
1.321 + // loader is null with CDS
1.322 + assert(loader_data != NULL || UseSharedSpaces || DumpSharedSpaces,
1.323 + "only allowed with shared spaces");
1.324 + unsigned int loader_hash = loader_data == NULL ? 0 : loader_data->identity_hash();
1.325 + return name_hash ^ loader_hash;
1.326 + }
1.327 +
1.328 + int index_for(Symbol* name, ClassLoaderData* loader_data) {
1.329 + return this->hash_to_index(compute_hash(name, loader_data));
1.330 + }
1.331 +};
1.332 +
1.333 +#endif // SHARE_VM_UTILITIES_HASHTABLE_HPP
