annotate hotspot/src/share/vm/utilities/hashtable.cpp @ 1:489c9b5090e2

Initial load
author duke
date Sat, 01 Dec 2007 00:00:00 +0000
parents
children b431de37a22c
rev   line source
duke@1 1 /*
duke@1 2 * Copyright 2003-2005 Sun Microsystems, Inc. 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 *
duke@1 19 * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
duke@1 20 * CA 95054 USA or visit www.sun.com if you need additional information or
duke@1 21 * have any 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 {
duke@1 46 const int block_size = 500;
duke@1 47 if (_first_free_entry == _end_block) {
duke@1 48 int len = _entry_size * block_size;
duke@1 49 _first_free_entry = NEW_C_HEAP_ARRAY(char, len);
duke@1 50 _end_block = _first_free_entry + len;
duke@1 51 }
duke@1 52 entry = (BasicHashtableEntry*)_first_free_entry;
duke@1 53 _first_free_entry += _entry_size;
duke@1 54 }
duke@1 55
duke@1 56 entry->set_hash(hashValue);
duke@1 57 return entry;
duke@1 58 }
duke@1 59
duke@1 60
duke@1 61 HashtableEntry* Hashtable::new_entry(unsigned int hashValue, oop obj) {
duke@1 62 HashtableEntry* entry;
duke@1 63
duke@1 64 entry = (HashtableEntry*)BasicHashtable::new_entry(hashValue);
duke@1 65 entry->set_literal(obj); // clears literal string field
duke@1 66 HS_DTRACE_PROBE4(hs_private, hashtable__new_entry,
duke@1 67 this, hashValue, obj, entry);
duke@1 68 return entry;
duke@1 69 }
duke@1 70
duke@1 71
duke@1 72 // GC support
duke@1 73
duke@1 74 void Hashtable::unlink(BoolObjectClosure* is_alive) {
duke@1 75 // Readers of the table are unlocked, so we should only be removing
duke@1 76 // entries at a safepoint.
duke@1 77 assert(SafepointSynchronize::is_at_safepoint(), "must be at safepoint");
duke@1 78 for (int i = 0; i < table_size(); ++i) {
duke@1 79 for (HashtableEntry** p = bucket_addr(i); *p != NULL; ) {
duke@1 80 HashtableEntry* entry = *p;
duke@1 81 if (entry->is_shared()) {
duke@1 82 break;
duke@1 83 }
duke@1 84 assert(entry->literal() != NULL, "just checking");
duke@1 85 if (is_alive->do_object_b(entry->literal())) {
duke@1 86 p = entry->next_addr();
duke@1 87 } else {
duke@1 88 *p = entry->next();
duke@1 89 free_entry(entry);
duke@1 90 }
duke@1 91 }
duke@1 92 }
duke@1 93 }
duke@1 94
duke@1 95
duke@1 96 void Hashtable::oops_do(OopClosure* f) {
duke@1 97 for (int i = 0; i < table_size(); ++i) {
duke@1 98 HashtableEntry** p = bucket_addr(i);
duke@1 99 HashtableEntry* entry = bucket(i);
duke@1 100 while (entry != NULL) {
duke@1 101 f->do_oop(entry->literal_addr());
duke@1 102
duke@1 103 // Did the closure remove the literal from the table?
duke@1 104 if (entry->literal() == NULL) {
duke@1 105 assert(!entry->is_shared(), "immutable hashtable entry?");
duke@1 106 *p = entry->next();
duke@1 107 free_entry(entry);
duke@1 108 } else {
duke@1 109 p = entry->next_addr();
duke@1 110 }
duke@1 111 entry = (HashtableEntry*)HashtableEntry::make_ptr(*p);
duke@1 112 }
duke@1 113 }
duke@1 114 }
duke@1 115
duke@1 116
duke@1 117 // Reverse the order of elements in the hash buckets.
duke@1 118
duke@1 119 void BasicHashtable::reverse() {
duke@1 120
duke@1 121 for (int i = 0; i < _table_size; ++i) {
duke@1 122 BasicHashtableEntry* new_list = NULL;
duke@1 123 BasicHashtableEntry* p = bucket(i);
duke@1 124 while (p != NULL) {
duke@1 125 BasicHashtableEntry* next = p->next();
duke@1 126 p->set_next(new_list);
duke@1 127 new_list = p;
duke@1 128 p = next;
duke@1 129 }
duke@1 130 *bucket_addr(i) = new_list;
duke@1 131 }
duke@1 132 }
duke@1 133
duke@1 134
duke@1 135 // Copy the table to the shared space.
duke@1 136
duke@1 137 void BasicHashtable::copy_table(char** top, char* end) {
duke@1 138
duke@1 139 // Dump the hash table entries.
duke@1 140
duke@1 141 intptr_t *plen = (intptr_t*)(*top);
duke@1 142 *top += sizeof(*plen);
duke@1 143
duke@1 144 int i;
duke@1 145 for (i = 0; i < _table_size; ++i) {
duke@1 146 for (BasicHashtableEntry** p = _buckets[i].entry_addr();
duke@1 147 *p != NULL;
duke@1 148 p = (*p)->next_addr()) {
duke@1 149 if (*top + entry_size() > end) {
duke@1 150 warning("\nThe shared miscellaneous data space is not large "
duke@1 151 "enough to \npreload requested classes. Use "
duke@1 152 "-XX:SharedMiscDataSize= to increase \nthe initial "
duke@1 153 "size of the miscellaneous data space.\n");
duke@1 154 exit(2);
duke@1 155 }
duke@1 156 *p = (BasicHashtableEntry*)memcpy(*top, *p, entry_size());
duke@1 157 *top += entry_size();
duke@1 158 }
duke@1 159 }
duke@1 160 *plen = (char*)(*top) - (char*)plen - sizeof(*plen);
duke@1 161
duke@1 162 // Set the shared bit.
duke@1 163
duke@1 164 for (i = 0; i < _table_size; ++i) {
duke@1 165 for (BasicHashtableEntry* p = bucket(i); p != NULL; p = p->next()) {
duke@1 166 p->set_shared();
duke@1 167 }
duke@1 168 }
duke@1 169 }
duke@1 170
duke@1 171
duke@1 172
duke@1 173 // Reverse the order of elements in the hash buckets.
duke@1 174
duke@1 175 void Hashtable::reverse(void* boundary) {
duke@1 176
duke@1 177 for (int i = 0; i < table_size(); ++i) {
duke@1 178 HashtableEntry* high_list = NULL;
duke@1 179 HashtableEntry* low_list = NULL;
duke@1 180 HashtableEntry* last_low_entry = NULL;
duke@1 181 HashtableEntry* p = bucket(i);
duke@1 182 while (p != NULL) {
duke@1 183 HashtableEntry* next = p->next();
duke@1 184 if ((void*)p->literal() >= boundary) {
duke@1 185 p->set_next(high_list);
duke@1 186 high_list = p;
duke@1 187 } else {
duke@1 188 p->set_next(low_list);
duke@1 189 low_list = p;
duke@1 190 if (last_low_entry == NULL) {
duke@1 191 last_low_entry = p;
duke@1 192 }
duke@1 193 }
duke@1 194 p = next;
duke@1 195 }
duke@1 196 if (low_list != NULL) {
duke@1 197 *bucket_addr(i) = low_list;
duke@1 198 last_low_entry->set_next(high_list);
duke@1 199 } else {
duke@1 200 *bucket_addr(i) = high_list;
duke@1 201 }
duke@1 202 }
duke@1 203 }
duke@1 204
duke@1 205
duke@1 206 // Dump the hash table buckets.
duke@1 207
duke@1 208 void BasicHashtable::copy_buckets(char** top, char* end) {
duke@1 209 intptr_t len = _table_size * sizeof(HashtableBucket);
duke@1 210 *(intptr_t*)(*top) = len;
duke@1 211 *top += sizeof(intptr_t);
duke@1 212
duke@1 213 *(intptr_t*)(*top) = _number_of_entries;
duke@1 214 *top += sizeof(intptr_t);
duke@1 215
duke@1 216 if (*top + len > end) {
duke@1 217 warning("\nThe shared miscellaneous data space is not large "
duke@1 218 "enough to \npreload requested classes. Use "
duke@1 219 "-XX:SharedMiscDataSize= to increase \nthe initial "
duke@1 220 "size of the miscellaneous data space.\n");
duke@1 221 exit(2);
duke@1 222 }
duke@1 223 _buckets = (HashtableBucket*)memcpy(*top, _buckets, len);
duke@1 224 *top += len;
duke@1 225 }
duke@1 226
duke@1 227
duke@1 228 #ifndef PRODUCT
duke@1 229
duke@1 230 void Hashtable::print() {
duke@1 231 ResourceMark rm;
duke@1 232
duke@1 233 for (int i = 0; i < table_size(); i++) {
duke@1 234 HashtableEntry* entry = bucket(i);
duke@1 235 while(entry != NULL) {
duke@1 236 tty->print("%d : ", i);
duke@1 237 entry->literal()->print();
duke@1 238 tty->cr();
duke@1 239 entry = entry->next();
duke@1 240 }
duke@1 241 }
duke@1 242 }
duke@1 243
duke@1 244
duke@1 245 void BasicHashtable::verify() {
duke@1 246 int count = 0;
duke@1 247 for (int i = 0; i < table_size(); i++) {
duke@1 248 for (BasicHashtableEntry* p = bucket(i); p != NULL; p = p->next()) {
duke@1 249 ++count;
duke@1 250 }
duke@1 251 }
duke@1 252 assert(count == number_of_entries(), "number of hashtable entries incorrect");
duke@1 253 }
duke@1 254
duke@1 255
duke@1 256 #endif // PRODUCT
duke@1 257
duke@1 258
duke@1 259 #ifdef ASSERT
duke@1 260
duke@1 261 void BasicHashtable::verify_lookup_length(double load) {
duke@1 262 if ((double)_lookup_length / (double)_lookup_count > load * 2.0) {
duke@1 263 warning("Performance bug: SystemDictionary lookup_count=%d "
duke@1 264 "lookup_length=%d average=%lf load=%f",
duke@1 265 _lookup_count, _lookup_length,
duke@1 266 (double) _lookup_length / _lookup_count, load);
duke@1 267 }
duke@1 268 }
duke@1 269
duke@1 270 #endif