annotate hotspot/src/share/vm/utilities/hashtable.cpp @ 13342:76a5de64aa62

7186278: Build error after CR#6995781 / 7151532 with GCC 4.7.0 Summary: Templates need this object if not using template parameter in call Reviewed-by: coleenp, kamg, dholmes
author andrew
date Tue, 31 Jul 2012 16:01:56 -0400
parents 025b0984feea
children 882756847a04
rev   line source
duke@1 1 /*
coleenp@13087 2 * Copyright (c) 2003, 2012, Oracle and/or its affiliates. All rights reserved.
duke@1 3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
duke@1 4 *
duke@1 5 * This code is free software; you can redistribute it and/or modify it
duke@1 6 * under the terms of the GNU General Public License version 2 only, as
duke@1 7 * published by the Free Software Foundation.
duke@1 8 *
duke@1 9 * This code is distributed in the hope that it will be useful, but WITHOUT
duke@1 10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
duke@1 11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
duke@1 12 * version 2 for more details (a copy is included in the LICENSE file that
duke@1 13 * accompanied this code).
duke@1 14 *
duke@1 15 * You should have received a copy of the GNU General Public License version
duke@1 16 * 2 along with this work; if not, write to the Free Software Foundation,
duke@1 17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
duke@1 18 *
trims@5547 19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
trims@5547 20 * or visit www.oracle.com if you need additional information or have any
trims@5547 21 * questions.
duke@1 22 *
duke@1 23 */
duke@1 24
stefank@7397 25 #include "precompiled.hpp"
coleenp@13199 26 #include "classfile/altHashing.hpp"
coleenp@13199 27 #include "classfile/javaClasses.hpp"
stefank@7397 28 #include "memory/allocation.inline.hpp"
coleenp@13097 29 #include "memory/filemap.hpp"
stefank@7397 30 #include "memory/resourceArea.hpp"
stefank@7397 31 #include "oops/oop.inline.hpp"
stefank@7397 32 #include "runtime/safepoint.hpp"
stefank@7397 33 #include "utilities/dtrace.hpp"
stefank@7397 34 #include "utilities/hashtable.hpp"
stefank@7397 35 #include "utilities/hashtable.inline.hpp"
duke@1 36
coleenp@8076 37
duke@1 38 // This is a generic hashtable, designed to be used for the symbol
duke@1 39 // and string tables.
duke@1 40 //
duke@1 41 // It is implemented as an open hash table with a fixed number of buckets.
duke@1 42 //
duke@1 43 // %note:
duke@1 44 // - HashtableEntrys are allocated in blocks to reduce the space overhead.
duke@1 45
zgu@13195 46 template <MEMFLAGS F> BasicHashtableEntry<F>* BasicHashtable<F>::new_entry(unsigned int hashValue) {
zgu@13195 47 BasicHashtableEntry<F>* entry;
duke@1 48
duke@1 49 if (_free_list) {
duke@1 50 entry = _free_list;
duke@1 51 _free_list = _free_list->next();
duke@1 52 } else {
jrose@1551 53 if (_first_free_entry + _entry_size >= _end_block) {
jrose@1551 54 int block_size = MIN2(512, MAX2((int)_table_size / 2, (int)_number_of_entries));
duke@1 55 int len = _entry_size * block_size;
jrose@1551 56 len = 1 << log2_intptr(len); // round down to power of 2
jrose@1551 57 assert(len >= _entry_size, "");
zgu@13195 58 _first_free_entry = NEW_C_HEAP_ARRAY2(char, len, F, CURRENT_PC);
duke@1 59 _end_block = _first_free_entry + len;
duke@1 60 }
zgu@13195 61 entry = (BasicHashtableEntry<F>*)_first_free_entry;
duke@1 62 _first_free_entry += _entry_size;
duke@1 63 }
duke@1 64
jrose@1551 65 assert(_entry_size % HeapWordSize == 0, "");
duke@1 66 entry->set_hash(hashValue);
duke@1 67 return entry;
duke@1 68 }
duke@1 69
duke@1 70
zgu@13195 71 template <class T, MEMFLAGS F> HashtableEntry<T, F>* Hashtable<T, F>::new_entry(unsigned int hashValue, T obj) {
zgu@13195 72 HashtableEntry<T, F>* entry;
duke@1 73
zgu@13195 74 entry = (HashtableEntry<T, F>*)BasicHashtable<F>::new_entry(hashValue);
coleenp@8076 75 entry->set_literal(obj);
duke@1 76 return entry;
duke@1 77 }
duke@1 78
coleenp@13087 79 // Check to see if the hashtable is unbalanced. The caller set a flag to
coleenp@13087 80 // rehash at the next safepoint. If this bucket is 60 times greater than the
coleenp@13087 81 // expected average bucket length, it's an unbalanced hashtable.
coleenp@13087 82 // This is somewhat an arbitrary heuristic but if one bucket gets to
coleenp@13087 83 // rehash_count which is currently 100, there's probably something wrong.
coleenp@13087 84
zgu@13195 85 template <MEMFLAGS F> bool BasicHashtable<F>::check_rehash_table(int count) {
coleenp@13087 86 assert(table_size() != 0, "underflow");
coleenp@13087 87 if (count > (((double)number_of_entries()/(double)table_size())*rehash_multiple)) {
coleenp@13087 88 // Set a flag for the next safepoint, which should be at some guaranteed
coleenp@13087 89 // safepoint interval.
coleenp@13087 90 return true;
coleenp@13087 91 }
coleenp@13087 92 return false;
coleenp@13087 93 }
coleenp@13087 94
coleenp@13199 95 template <class T, MEMFLAGS F> jint Hashtable<T, F>::_seed = 0;
coleenp@13199 96
coleenp@13199 97 template <class T, MEMFLAGS F> unsigned int Hashtable<T, F>::new_hash(Symbol* sym) {
coleenp@13199 98 ResourceMark rm;
coleenp@13199 99 // Use alternate hashing algorithm on this symbol.
coleenp@13199 100 return AltHashing::murmur3_32(seed(), (const jbyte*)sym->as_C_string(), sym->utf8_length());
coleenp@13199 101 }
coleenp@13199 102
coleenp@13199 103 template <class T, MEMFLAGS F> unsigned int Hashtable<T, F>::new_hash(oop string) {
coleenp@13199 104 ResourceMark rm;
coleenp@13199 105 int length;
coleenp@13199 106 jchar* chars = java_lang_String::as_unicode_string(string, length);
coleenp@13199 107 // Use alternate hashing algorithm on the string
coleenp@13199 108 return AltHashing::murmur3_32(seed(), chars, length);
coleenp@13199 109 }
coleenp@13199 110
coleenp@13087 111 // Create a new table and using alternate hash code, populate the new table
coleenp@13087 112 // with the existing elements. This can be used to change the hash code
coleenp@13087 113 // and could in the future change the size of the table.
coleenp@13087 114
zgu@13195 115 template <class T, MEMFLAGS F> void Hashtable<T, F>::move_to(Hashtable<T, F>* new_table) {
coleenp@13199 116
coleenp@13199 117 // Initialize the global seed for hashing.
coleenp@13199 118 _seed = AltHashing::compute_seed();
coleenp@13199 119 assert(seed() != 0, "shouldn't be zero");
coleenp@13199 120
coleenp@13199 121 int saved_entry_count = this->number_of_entries();
coleenp@13087 122
coleenp@13087 123 // Iterate through the table and create a new entry for the new table
coleenp@13087 124 for (int i = 0; i < new_table->table_size(); ++i) {
zgu@13195 125 for (HashtableEntry<T, F>* p = bucket(i); p != NULL; ) {
zgu@13195 126 HashtableEntry<T, F>* next = p->next();
coleenp@13087 127 T string = p->literal();
coleenp@13087 128 // Use alternate hashing algorithm on the symbol in the first table
coleenp@13087 129 unsigned int hashValue = new_hash(string);
coleenp@13087 130 // Get a new index relative to the new table (can also change size)
coleenp@13087 131 int index = new_table->hash_to_index(hashValue);
coleenp@13087 132 p->set_hash(hashValue);
coleenp@13097 133 // Keep the shared bit in the Hashtable entry to indicate that this entry
coleenp@13097 134 // can't be deleted. The shared bit is the LSB in the _next field so
coleenp@13097 135 // walking the hashtable past these entries requires
coleenp@13097 136 // BasicHashtableEntry::make_ptr() call.
coleenp@13097 137 bool keep_shared = p->is_shared();
andrew@13342 138 this->unlink_entry(p);
coleenp@13087 139 new_table->add_entry(index, p);
coleenp@13097 140 if (keep_shared) {
coleenp@13097 141 p->set_shared();
coleenp@13097 142 }
coleenp@13087 143 p = next;
coleenp@13087 144 }
coleenp@13087 145 }
coleenp@13087 146 // give the new table the free list as well
coleenp@13087 147 new_table->copy_freelist(this);
coleenp@13087 148 assert(new_table->number_of_entries() == saved_entry_count, "lost entry on dictionary copy?");
coleenp@13087 149
coleenp@13087 150 // Destroy memory used by the buckets in the hashtable. The memory
coleenp@13087 151 // for the elements has been used in a new table and is not
coleenp@13087 152 // destroyed. The memory reuse will benefit resizing the SystemDictionary
coleenp@13087 153 // to avoid a memory allocation spike at safepoint.
zgu@13195 154 BasicHashtable<F>::free_buckets();
coleenp@13087 155 }
coleenp@13087 156
zgu@13195 157 template <MEMFLAGS F> void BasicHashtable<F>::free_buckets() {
coleenp@13097 158 if (NULL != _buckets) {
coleenp@13097 159 // Don't delete the buckets in the shared space. They aren't
coleenp@13097 160 // allocated by os::malloc
coleenp@13097 161 if (!UseSharedSpaces ||
coleenp@13097 162 !FileMapInfo::current_info()->is_in_shared_space(_buckets)) {
zgu@13195 163 FREE_C_HEAP_ARRAY(HashtableBucket, _buckets, F);
coleenp@13097 164 }
coleenp@13097 165 _buckets = NULL;
coleenp@13097 166 }
coleenp@13097 167 }
coleenp@13097 168
coleenp@13097 169
duke@1 170 // Reverse the order of elements in the hash buckets.
duke@1 171
zgu@13195 172 template <MEMFLAGS F> void BasicHashtable<F>::reverse() {
duke@1 173
duke@1 174 for (int i = 0; i < _table_size; ++i) {
zgu@13195 175 BasicHashtableEntry<F>* new_list = NULL;
zgu@13195 176 BasicHashtableEntry<F>* p = bucket(i);
duke@1 177 while (p != NULL) {
zgu@13195 178 BasicHashtableEntry<F>* next = p->next();
duke@1 179 p->set_next(new_list);
duke@1 180 new_list = p;
duke@1 181 p = next;
duke@1 182 }
duke@1 183 *bucket_addr(i) = new_list;
duke@1 184 }
duke@1 185 }
duke@1 186
duke@1 187
duke@1 188 // Copy the table to the shared space.
duke@1 189
zgu@13195 190 template <MEMFLAGS F> void BasicHashtable<F>::copy_table(char** top, char* end) {
duke@1 191
duke@1 192 // Dump the hash table entries.
duke@1 193
duke@1 194 intptr_t *plen = (intptr_t*)(*top);
duke@1 195 *top += sizeof(*plen);
duke@1 196
duke@1 197 int i;
duke@1 198 for (i = 0; i < _table_size; ++i) {
zgu@13195 199 for (BasicHashtableEntry<F>** p = _buckets[i].entry_addr();
duke@1 200 *p != NULL;
duke@1 201 p = (*p)->next_addr()) {
duke@1 202 if (*top + entry_size() > end) {
coleenp@8076 203 report_out_of_shared_space(SharedMiscData);
duke@1 204 }
zgu@13195 205 *p = (BasicHashtableEntry<F>*)memcpy(*top, *p, entry_size());
duke@1 206 *top += entry_size();
duke@1 207 }
duke@1 208 }
duke@1 209 *plen = (char*)(*top) - (char*)plen - sizeof(*plen);
duke@1 210
duke@1 211 // Set the shared bit.
duke@1 212
duke@1 213 for (i = 0; i < _table_size; ++i) {
zgu@13195 214 for (BasicHashtableEntry<F>* p = bucket(i); p != NULL; p = p->next()) {
duke@1 215 p->set_shared();
duke@1 216 }
duke@1 217 }
duke@1 218 }
duke@1 219
duke@1 220
duke@1 221
duke@1 222 // Reverse the order of elements in the hash buckets.
duke@1 223
zgu@13195 224 template <class T, MEMFLAGS F> void Hashtable<T, F>::reverse(void* boundary) {
duke@1 225
zgu@13195 226 for (int i = 0; i < this->table_size(); ++i) {
zgu@13195 227 HashtableEntry<T, F>* high_list = NULL;
zgu@13195 228 HashtableEntry<T, F>* low_list = NULL;
zgu@13195 229 HashtableEntry<T, F>* last_low_entry = NULL;
zgu@13195 230 HashtableEntry<T, F>* p = bucket(i);
duke@1 231 while (p != NULL) {
zgu@13195 232 HashtableEntry<T, F>* next = p->next();
duke@1 233 if ((void*)p->literal() >= boundary) {
duke@1 234 p->set_next(high_list);
duke@1 235 high_list = p;
duke@1 236 } else {
duke@1 237 p->set_next(low_list);
duke@1 238 low_list = p;
duke@1 239 if (last_low_entry == NULL) {
duke@1 240 last_low_entry = p;
duke@1 241 }
duke@1 242 }
duke@1 243 p = next;
duke@1 244 }
duke@1 245 if (low_list != NULL) {
duke@1 246 *bucket_addr(i) = low_list;
duke@1 247 last_low_entry->set_next(high_list);
duke@1 248 } else {
duke@1 249 *bucket_addr(i) = high_list;
duke@1 250 }
duke@1 251 }
duke@1 252 }
duke@1 253
duke@1 254
duke@1 255 // Dump the hash table buckets.
duke@1 256
zgu@13195 257 template <MEMFLAGS F> void BasicHashtable<F>::copy_buckets(char** top, char* end) {
zgu@13195 258 intptr_t len = _table_size * sizeof(HashtableBucket<F>);
duke@1 259 *(intptr_t*)(*top) = len;
duke@1 260 *top += sizeof(intptr_t);
duke@1 261
duke@1 262 *(intptr_t*)(*top) = _number_of_entries;
duke@1 263 *top += sizeof(intptr_t);
duke@1 264
duke@1 265 if (*top + len > end) {
coleenp@8076 266 report_out_of_shared_space(SharedMiscData);
duke@1 267 }
zgu@13195 268 _buckets = (HashtableBucket<F>*)memcpy(*top, _buckets, len);
duke@1 269 *top += len;
duke@1 270 }
duke@1 271
duke@1 272
duke@1 273 #ifndef PRODUCT
duke@1 274
zgu@13195 275 template <class T, MEMFLAGS F> void Hashtable<T, F>::print() {
duke@1 276 ResourceMark rm;
duke@1 277
zgu@13195 278 for (int i = 0; i < BasicHashtable<F>::table_size(); i++) {
zgu@13195 279 HashtableEntry<T, F>* entry = bucket(i);
duke@1 280 while(entry != NULL) {
duke@1 281 tty->print("%d : ", i);
duke@1 282 entry->literal()->print();
duke@1 283 tty->cr();
duke@1 284 entry = entry->next();
duke@1 285 }
duke@1 286 }
duke@1 287 }
duke@1 288
duke@1 289
zgu@13195 290 template <MEMFLAGS F> void BasicHashtable<F>::verify() {
duke@1 291 int count = 0;
duke@1 292 for (int i = 0; i < table_size(); i++) {
zgu@13195 293 for (BasicHashtableEntry<F>* p = bucket(i); p != NULL; p = p->next()) {
duke@1 294 ++count;
duke@1 295 }
duke@1 296 }
duke@1 297 assert(count == number_of_entries(), "number of hashtable entries incorrect");
duke@1 298 }
duke@1 299
duke@1 300
duke@1 301 #endif // PRODUCT
duke@1 302
duke@1 303
duke@1 304 #ifdef ASSERT
duke@1 305
zgu@13195 306 template <MEMFLAGS F> void BasicHashtable<F>::verify_lookup_length(double load) {
duke@1 307 if ((double)_lookup_length / (double)_lookup_count > load * 2.0) {
duke@1 308 warning("Performance bug: SystemDictionary lookup_count=%d "
duke@1 309 "lookup_length=%d average=%lf load=%f",
duke@1 310 _lookup_count, _lookup_length,
duke@1 311 (double) _lookup_length / _lookup_count, load);
duke@1 312 }
duke@1 313 }
duke@1 314
duke@1 315 #endif
coleenp@8076 316 // Explicitly instantiate these types
zgu@13195 317 template class Hashtable<constantPoolOop, mtClass>;
zgu@13195 318 template class Hashtable<Symbol*, mtSymbol>;
zgu@13195 319 template class Hashtable<klassOop, mtClass>;
zgu@13195 320 template class Hashtable<oop, mtClass>;
zgu@13195 321 #ifdef SOLARIS
zgu@13195 322 template class Hashtable<oop, mtSymbol>;
zgu@13195 323 #endif
zgu@13195 324 template class Hashtable<oopDesc*, mtSymbol>;
zgu@13195 325 template class Hashtable<Symbol*, mtClass>;
zgu@13195 326 template class HashtableEntry<Symbol*, mtSymbol>;
zgu@13195 327 template class HashtableEntry<Symbol*, mtClass>;
zgu@13195 328 template class HashtableEntry<oop, mtSymbol>;
zgu@13195 329 template class BasicHashtableEntry<mtSymbol>;
zgu@13195 330 template class BasicHashtableEntry<mtCode>;
zgu@13195 331 template class BasicHashtable<mtClass>;
zgu@13195 332 template class BasicHashtable<mtSymbol>;
zgu@13195 333 template class BasicHashtable<mtCode>;
zgu@13195 334 template class BasicHashtable<mtInternal>;