annotate hotspot/src/share/vm/utilities/hashtable.cpp @ 5547:f4b087cbb361

6941466: Oracle rebranding changes for Hotspot repositories Summary: Change all the Sun copyrights to Oracle copyright Reviewed-by: ohair
author trims
date Thu, 27 May 2010 19:08:38 -0700
parents a0dd9009e992
children 5b173b4ca846
rev   line source
duke@1 1 /*
trims@5547 2 * Copyright (c) 2003, 2008, 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
duke@1 25 # include "incls/_precompiled.incl"
duke@1 26 # include "incls/_hashtable.cpp.incl"
duke@1 27
duke@1 28 HS_DTRACE_PROBE_DECL4(hs_private, hashtable__new_entry,
duke@1 29 void*, unsigned int, oop, void*);
duke@1 30
duke@1 31 // This is a generic hashtable, designed to be used for the symbol
duke@1 32 // and string tables.
duke@1 33 //
duke@1 34 // It is implemented as an open hash table with a fixed number of buckets.
duke@1 35 //
duke@1 36 // %note:
duke@1 37 // - HashtableEntrys are allocated in blocks to reduce the space overhead.
duke@1 38
duke@1 39 BasicHashtableEntry* BasicHashtable::new_entry(unsigned int hashValue) {
duke@1 40 BasicHashtableEntry* entry;
duke@1 41
duke@1 42 if (_free_list) {
duke@1 43 entry = _free_list;
duke@1 44 _free_list = _free_list->next();
duke@1 45 } else {
jrose@1551 46 if (_first_free_entry + _entry_size >= _end_block) {
jrose@1551 47 int block_size = MIN2(512, MAX2((int)_table_size / 2, (int)_number_of_entries));
duke@1 48 int len = _entry_size * block_size;
jrose@1551 49 len = 1 << log2_intptr(len); // round down to power of 2
jrose@1551 50 assert(len >= _entry_size, "");
duke@1 51 _first_free_entry = NEW_C_HEAP_ARRAY(char, len);
duke@1 52 _end_block = _first_free_entry + len;
duke@1 53 }
duke@1 54 entry = (BasicHashtableEntry*)_first_free_entry;
duke@1 55 _first_free_entry += _entry_size;
duke@1 56 }
duke@1 57
jrose@1551 58 assert(_entry_size % HeapWordSize == 0, "");
duke@1 59 entry->set_hash(hashValue);
duke@1 60 return entry;
duke@1 61 }
duke@1 62
duke@1 63
duke@1 64 HashtableEntry* Hashtable::new_entry(unsigned int hashValue, oop obj) {
duke@1 65 HashtableEntry* entry;
duke@1 66
duke@1 67 entry = (HashtableEntry*)BasicHashtable::new_entry(hashValue);
duke@1 68 entry->set_literal(obj); // clears literal string field
duke@1 69 HS_DTRACE_PROBE4(hs_private, hashtable__new_entry,
duke@1 70 this, hashValue, obj, entry);
duke@1 71 return entry;
duke@1 72 }
duke@1 73
duke@1 74
duke@1 75 // GC support
duke@1 76
duke@1 77 void Hashtable::unlink(BoolObjectClosure* is_alive) {
duke@1 78 // Readers of the table are unlocked, so we should only be removing
duke@1 79 // entries at a safepoint.
duke@1 80 assert(SafepointSynchronize::is_at_safepoint(), "must be at safepoint");
duke@1 81 for (int i = 0; i < table_size(); ++i) {
duke@1 82 for (HashtableEntry** p = bucket_addr(i); *p != NULL; ) {
duke@1 83 HashtableEntry* entry = *p;
duke@1 84 if (entry->is_shared()) {
duke@1 85 break;
duke@1 86 }
duke@1 87 assert(entry->literal() != NULL, "just checking");
duke@1 88 if (is_alive->do_object_b(entry->literal())) {
duke@1 89 p = entry->next_addr();
duke@1 90 } else {
duke@1 91 *p = entry->next();
duke@1 92 free_entry(entry);
duke@1 93 }
duke@1 94 }
duke@1 95 }
duke@1 96 }
duke@1 97
duke@1 98
duke@1 99 void Hashtable::oops_do(OopClosure* f) {
duke@1 100 for (int i = 0; i < table_size(); ++i) {
duke@1 101 HashtableEntry** p = bucket_addr(i);
duke@1 102 HashtableEntry* entry = bucket(i);
duke@1 103 while (entry != NULL) {
duke@1 104 f->do_oop(entry->literal_addr());
duke@1 105
duke@1 106 // Did the closure remove the literal from the table?
duke@1 107 if (entry->literal() == NULL) {
duke@1 108 assert(!entry->is_shared(), "immutable hashtable entry?");
duke@1 109 *p = entry->next();
duke@1 110 free_entry(entry);
duke@1 111 } else {
duke@1 112 p = entry->next_addr();
duke@1 113 }
duke@1 114 entry = (HashtableEntry*)HashtableEntry::make_ptr(*p);
duke@1 115 }
duke@1 116 }
duke@1 117 }
duke@1 118
duke@1 119
duke@1 120 // Reverse the order of elements in the hash buckets.
duke@1 121
duke@1 122 void BasicHashtable::reverse() {
duke@1 123
duke@1 124 for (int i = 0; i < _table_size; ++i) {
duke@1 125 BasicHashtableEntry* new_list = NULL;
duke@1 126 BasicHashtableEntry* p = bucket(i);
duke@1 127 while (p != NULL) {
duke@1 128 BasicHashtableEntry* next = p->next();
duke@1 129 p->set_next(new_list);
duke@1 130 new_list = p;
duke@1 131 p = next;
duke@1 132 }
duke@1 133 *bucket_addr(i) = new_list;
duke@1 134 }
duke@1 135 }
duke@1 136
duke@1 137
duke@1 138 // Copy the table to the shared space.
duke@1 139
duke@1 140 void BasicHashtable::copy_table(char** top, char* end) {
duke@1 141
duke@1 142 // Dump the hash table entries.
duke@1 143
duke@1 144 intptr_t *plen = (intptr_t*)(*top);
duke@1 145 *top += sizeof(*plen);
duke@1 146
duke@1 147 int i;
duke@1 148 for (i = 0; i < _table_size; ++i) {
duke@1 149 for (BasicHashtableEntry** p = _buckets[i].entry_addr();
duke@1 150 *p != NULL;
duke@1 151 p = (*p)->next_addr()) {
duke@1 152 if (*top + entry_size() > end) {
duke@1 153 warning("\nThe shared miscellaneous data space is not large "
duke@1 154 "enough to \npreload requested classes. Use "
duke@1 155 "-XX:SharedMiscDataSize= to increase \nthe initial "
duke@1 156 "size of the miscellaneous data space.\n");
duke@1 157 exit(2);
duke@1 158 }
duke@1 159 *p = (BasicHashtableEntry*)memcpy(*top, *p, entry_size());
duke@1 160 *top += entry_size();
duke@1 161 }
duke@1 162 }
duke@1 163 *plen = (char*)(*top) - (char*)plen - sizeof(*plen);
duke@1 164
duke@1 165 // Set the shared bit.
duke@1 166
duke@1 167 for (i = 0; i < _table_size; ++i) {
duke@1 168 for (BasicHashtableEntry* p = bucket(i); p != NULL; p = p->next()) {
duke@1 169 p->set_shared();
duke@1 170 }
duke@1 171 }
duke@1 172 }
duke@1 173
duke@1 174
duke@1 175
duke@1 176 // Reverse the order of elements in the hash buckets.
duke@1 177
duke@1 178 void Hashtable::reverse(void* boundary) {
duke@1 179
duke@1 180 for (int i = 0; i < table_size(); ++i) {
duke@1 181 HashtableEntry* high_list = NULL;
duke@1 182 HashtableEntry* low_list = NULL;
duke@1 183 HashtableEntry* last_low_entry = NULL;
duke@1 184 HashtableEntry* p = bucket(i);
duke@1 185 while (p != NULL) {
duke@1 186 HashtableEntry* next = p->next();
duke@1 187 if ((void*)p->literal() >= boundary) {
duke@1 188 p->set_next(high_list);
duke@1 189 high_list = p;
duke@1 190 } else {
duke@1 191 p->set_next(low_list);
duke@1 192 low_list = p;
duke@1 193 if (last_low_entry == NULL) {
duke@1 194 last_low_entry = p;
duke@1 195 }
duke@1 196 }
duke@1 197 p = next;
duke@1 198 }
duke@1 199 if (low_list != NULL) {
duke@1 200 *bucket_addr(i) = low_list;
duke@1 201 last_low_entry->set_next(high_list);
duke@1 202 } else {
duke@1 203 *bucket_addr(i) = high_list;
duke@1 204 }
duke@1 205 }
duke@1 206 }
duke@1 207
duke@1 208
duke@1 209 // Dump the hash table buckets.
duke@1 210
duke@1 211 void BasicHashtable::copy_buckets(char** top, char* end) {
duke@1 212 intptr_t len = _table_size * sizeof(HashtableBucket);
duke@1 213 *(intptr_t*)(*top) = len;
duke@1 214 *top += sizeof(intptr_t);
duke@1 215
duke@1 216 *(intptr_t*)(*top) = _number_of_entries;
duke@1 217 *top += sizeof(intptr_t);
duke@1 218
duke@1 219 if (*top + len > end) {
duke@1 220 warning("\nThe shared miscellaneous data space is not large "
duke@1 221 "enough to \npreload requested classes. Use "
duke@1 222 "-XX:SharedMiscDataSize= to increase \nthe initial "
duke@1 223 "size of the miscellaneous data space.\n");
duke@1 224 exit(2);
duke@1 225 }
duke@1 226 _buckets = (HashtableBucket*)memcpy(*top, _buckets, len);
duke@1 227 *top += len;
duke@1 228 }
duke@1 229
duke@1 230
duke@1 231 #ifndef PRODUCT
duke@1 232
duke@1 233 void Hashtable::print() {
duke@1 234 ResourceMark rm;
duke@1 235
duke@1 236 for (int i = 0; i < table_size(); i++) {
duke@1 237 HashtableEntry* entry = bucket(i);
duke@1 238 while(entry != NULL) {
duke@1 239 tty->print("%d : ", i);
duke@1 240 entry->literal()->print();
duke@1 241 tty->cr();
duke@1 242 entry = entry->next();
duke@1 243 }
duke@1 244 }
duke@1 245 }
duke@1 246
duke@1 247
duke@1 248 void BasicHashtable::verify() {
duke@1 249 int count = 0;
duke@1 250 for (int i = 0; i < table_size(); i++) {
duke@1 251 for (BasicHashtableEntry* p = bucket(i); p != NULL; p = p->next()) {
duke@1 252 ++count;
duke@1 253 }
duke@1 254 }
duke@1 255 assert(count == number_of_entries(), "number of hashtable entries incorrect");
duke@1 256 }
duke@1 257
duke@1 258
duke@1 259 #endif // PRODUCT
duke@1 260
duke@1 261
duke@1 262 #ifdef ASSERT
duke@1 263
duke@1 264 void BasicHashtable::verify_lookup_length(double load) {
duke@1 265 if ((double)_lookup_length / (double)_lookup_count > load * 2.0) {
duke@1 266 warning("Performance bug: SystemDictionary lookup_count=%d "
duke@1 267 "lookup_length=%d average=%lf load=%f",
duke@1 268 _lookup_count, _lookup_length,
duke@1 269 (double) _lookup_length / _lookup_count, load);
duke@1 270 }
duke@1 271 }
duke@1 272
duke@1 273 #endif