annotate src/share/vm/utilities/hashtable.cpp @ 3528:5e2dc722e70d

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