|
0
|
1 /*
|
|
|
2 * Copyright 2003-2005 Sun Microsystems, Inc. All Rights Reserved.
|
|
|
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
|
|
|
4 *
|
|
|
5 * This code is free software; you can redistribute it and/or modify it
|
|
|
6 * under the terms of the GNU General Public License version 2 only, as
|
|
|
7 * published by the Free Software Foundation.
|
|
|
8 *
|
|
|
9 * This code is distributed in the hope that it will be useful, but WITHOUT
|
|
|
10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
|
|
|
11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
|
|
|
12 * version 2 for more details (a copy is included in the LICENSE file that
|
|
|
13 * accompanied this code).
|
|
|
14 *
|
|
|
15 * You should have received a copy of the GNU General Public License version
|
|
|
16 * 2 along with this work; if not, write to the Free Software Foundation,
|
|
|
17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
|
|
|
18 *
|
|
|
19 * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
|
|
|
20 * CA 95054 USA or visit www.sun.com if you need additional information or
|
|
|
21 * have any questions.
|
|
|
22 *
|
|
|
23 */
|
|
|
24
|
|
|
25 # include "incls/_precompiled.incl"
|
|
|
26 # include "incls/_hashtable.cpp.incl"
|
|
|
27
|
|
|
28 HS_DTRACE_PROBE_DECL4(hs_private, hashtable__new_entry,
|
|
|
29 void*, unsigned int, oop, void*);
|
|
|
30
|
|
|
31 // This is a generic hashtable, designed to be used for the symbol
|
|
|
32 // and string tables.
|
|
|
33 //
|
|
|
34 // It is implemented as an open hash table with a fixed number of buckets.
|
|
|
35 //
|
|
|
36 // %note:
|
|
|
37 // - HashtableEntrys are allocated in blocks to reduce the space overhead.
|
|
|
38
|
|
|
39 BasicHashtableEntry* BasicHashtable::new_entry(unsigned int hashValue) {
|
|
|
40 BasicHashtableEntry* entry;
|
|
|
41
|
|
|
42 if (_free_list) {
|
|
|
43 entry = _free_list;
|
|
|
44 _free_list = _free_list->next();
|
|
|
45 } else {
|
|
|
46 const int block_size = 500;
|
|
|
47 if (_first_free_entry == _end_block) {
|
|
|
48 int len = _entry_size * block_size;
|
|
|
49 _first_free_entry = NEW_C_HEAP_ARRAY(char, len);
|
|
|
50 _end_block = _first_free_entry + len;
|
|
|
51 }
|
|
|
52 entry = (BasicHashtableEntry*)_first_free_entry;
|
|
|
53 _first_free_entry += _entry_size;
|
|
|
54 }
|
|
|
55
|
|
|
56 entry->set_hash(hashValue);
|
|
|
57 return entry;
|
|
|
58 }
|
|
|
59
|
|
|
60
|
|
|
61 HashtableEntry* Hashtable::new_entry(unsigned int hashValue, oop obj) {
|
|
|
62 HashtableEntry* entry;
|
|
|
63
|
|
|
64 entry = (HashtableEntry*)BasicHashtable::new_entry(hashValue);
|
|
|
65 entry->set_literal(obj); // clears literal string field
|
|
|
66 HS_DTRACE_PROBE4(hs_private, hashtable__new_entry,
|
|
|
67 this, hashValue, obj, entry);
|
|
|
68 return entry;
|
|
|
69 }
|
|
|
70
|
|
|
71
|
|
|
72 // GC support
|
|
|
73
|
|
|
74 void Hashtable::unlink(BoolObjectClosure* is_alive) {
|
|
|
75 // Readers of the table are unlocked, so we should only be removing
|
|
|
76 // entries at a safepoint.
|
|
|
77 assert(SafepointSynchronize::is_at_safepoint(), "must be at safepoint");
|
|
|
78 for (int i = 0; i < table_size(); ++i) {
|
|
|
79 for (HashtableEntry** p = bucket_addr(i); *p != NULL; ) {
|
|
|
80 HashtableEntry* entry = *p;
|
|
|
81 if (entry->is_shared()) {
|
|
|
82 break;
|
|
|
83 }
|
|
|
84 assert(entry->literal() != NULL, "just checking");
|
|
|
85 if (is_alive->do_object_b(entry->literal())) {
|
|
|
86 p = entry->next_addr();
|
|
|
87 } else {
|
|
|
88 *p = entry->next();
|
|
|
89 free_entry(entry);
|
|
|
90 }
|
|
|
91 }
|
|
|
92 }
|
|
|
93 }
|
|
|
94
|
|
|
95
|
|
|
96 void Hashtable::oops_do(OopClosure* f) {
|
|
|
97 for (int i = 0; i < table_size(); ++i) {
|
|
|
98 HashtableEntry** p = bucket_addr(i);
|
|
|
99 HashtableEntry* entry = bucket(i);
|
|
|
100 while (entry != NULL) {
|
|
|
101 f->do_oop(entry->literal_addr());
|
|
|
102
|
|
|
103 // Did the closure remove the literal from the table?
|
|
|
104 if (entry->literal() == NULL) {
|
|
|
105 assert(!entry->is_shared(), "immutable hashtable entry?");
|
|
|
106 *p = entry->next();
|
|
|
107 free_entry(entry);
|
|
|
108 } else {
|
|
|
109 p = entry->next_addr();
|
|
|
110 }
|
|
|
111 entry = (HashtableEntry*)HashtableEntry::make_ptr(*p);
|
|
|
112 }
|
|
|
113 }
|
|
|
114 }
|
|
|
115
|
|
|
116
|
|
|
117 // Reverse the order of elements in the hash buckets.
|
|
|
118
|
|
|
119 void BasicHashtable::reverse() {
|
|
|
120
|
|
|
121 for (int i = 0; i < _table_size; ++i) {
|
|
|
122 BasicHashtableEntry* new_list = NULL;
|
|
|
123 BasicHashtableEntry* p = bucket(i);
|
|
|
124 while (p != NULL) {
|
|
|
125 BasicHashtableEntry* next = p->next();
|
|
|
126 p->set_next(new_list);
|
|
|
127 new_list = p;
|
|
|
128 p = next;
|
|
|
129 }
|
|
|
130 *bucket_addr(i) = new_list;
|
|
|
131 }
|
|
|
132 }
|
|
|
133
|
|
|
134
|
|
|
135 // Copy the table to the shared space.
|
|
|
136
|
|
|
137 void BasicHashtable::copy_table(char** top, char* end) {
|
|
|
138
|
|
|
139 // Dump the hash table entries.
|
|
|
140
|
|
|
141 intptr_t *plen = (intptr_t*)(*top);
|
|
|
142 *top += sizeof(*plen);
|
|
|
143
|
|
|
144 int i;
|
|
|
145 for (i = 0; i < _table_size; ++i) {
|
|
|
146 for (BasicHashtableEntry** p = _buckets[i].entry_addr();
|
|
|
147 *p != NULL;
|
|
|
148 p = (*p)->next_addr()) {
|
|
|
149 if (*top + entry_size() > end) {
|
|
|
150 warning("\nThe shared miscellaneous data space is not large "
|
|
|
151 "enough to \npreload requested classes. Use "
|
|
|
152 "-XX:SharedMiscDataSize= to increase \nthe initial "
|
|
|
153 "size of the miscellaneous data space.\n");
|
|
|
154 exit(2);
|
|
|
155 }
|
|
|
156 *p = (BasicHashtableEntry*)memcpy(*top, *p, entry_size());
|
|
|
157 *top += entry_size();
|
|
|
158 }
|
|
|
159 }
|
|
|
160 *plen = (char*)(*top) - (char*)plen - sizeof(*plen);
|
|
|
161
|
|
|
162 // Set the shared bit.
|
|
|
163
|
|
|
164 for (i = 0; i < _table_size; ++i) {
|
|
|
165 for (BasicHashtableEntry* p = bucket(i); p != NULL; p = p->next()) {
|
|
|
166 p->set_shared();
|
|
|
167 }
|
|
|
168 }
|
|
|
169 }
|
|
|
170
|
|
|
171
|
|
|
172
|
|
|
173 // Reverse the order of elements in the hash buckets.
|
|
|
174
|
|
|
175 void Hashtable::reverse(void* boundary) {
|
|
|
176
|
|
|
177 for (int i = 0; i < table_size(); ++i) {
|
|
|
178 HashtableEntry* high_list = NULL;
|
|
|
179 HashtableEntry* low_list = NULL;
|
|
|
180 HashtableEntry* last_low_entry = NULL;
|
|
|
181 HashtableEntry* p = bucket(i);
|
|
|
182 while (p != NULL) {
|
|
|
183 HashtableEntry* next = p->next();
|
|
|
184 if ((void*)p->literal() >= boundary) {
|
|
|
185 p->set_next(high_list);
|
|
|
186 high_list = p;
|
|
|
187 } else {
|
|
|
188 p->set_next(low_list);
|
|
|
189 low_list = p;
|
|
|
190 if (last_low_entry == NULL) {
|
|
|
191 last_low_entry = p;
|
|
|
192 }
|
|
|
193 }
|
|
|
194 p = next;
|
|
|
195 }
|
|
|
196 if (low_list != NULL) {
|
|
|
197 *bucket_addr(i) = low_list;
|
|
|
198 last_low_entry->set_next(high_list);
|
|
|
199 } else {
|
|
|
200 *bucket_addr(i) = high_list;
|
|
|
201 }
|
|
|
202 }
|
|
|
203 }
|
|
|
204
|
|
|
205
|
|
|
206 // Dump the hash table buckets.
|
|
|
207
|
|
|
208 void BasicHashtable::copy_buckets(char** top, char* end) {
|
|
|
209 intptr_t len = _table_size * sizeof(HashtableBucket);
|
|
|
210 *(intptr_t*)(*top) = len;
|
|
|
211 *top += sizeof(intptr_t);
|
|
|
212
|
|
|
213 *(intptr_t*)(*top) = _number_of_entries;
|
|
|
214 *top += sizeof(intptr_t);
|
|
|
215
|
|
|
216 if (*top + len > end) {
|
|
|
217 warning("\nThe shared miscellaneous data space is not large "
|
|
|
218 "enough to \npreload requested classes. Use "
|
|
|
219 "-XX:SharedMiscDataSize= to increase \nthe initial "
|
|
|
220 "size of the miscellaneous data space.\n");
|
|
|
221 exit(2);
|
|
|
222 }
|
|
|
223 _buckets = (HashtableBucket*)memcpy(*top, _buckets, len);
|
|
|
224 *top += len;
|
|
|
225 }
|
|
|
226
|
|
|
227
|
|
|
228 #ifndef PRODUCT
|
|
|
229
|
|
|
230 void Hashtable::print() {
|
|
|
231 ResourceMark rm;
|
|
|
232
|
|
|
233 for (int i = 0; i < table_size(); i++) {
|
|
|
234 HashtableEntry* entry = bucket(i);
|
|
|
235 while(entry != NULL) {
|
|
|
236 tty->print("%d : ", i);
|
|
|
237 entry->literal()->print();
|
|
|
238 tty->cr();
|
|
|
239 entry = entry->next();
|
|
|
240 }
|
|
|
241 }
|
|
|
242 }
|
|
|
243
|
|
|
244
|
|
|
245 void BasicHashtable::verify() {
|
|
|
246 int count = 0;
|
|
|
247 for (int i = 0; i < table_size(); i++) {
|
|
|
248 for (BasicHashtableEntry* p = bucket(i); p != NULL; p = p->next()) {
|
|
|
249 ++count;
|
|
|
250 }
|
|
|
251 }
|
|
|
252 assert(count == number_of_entries(), "number of hashtable entries incorrect");
|
|
|
253 }
|
|
|
254
|
|
|
255
|
|
|
256 #endif // PRODUCT
|
|
|
257
|
|
|
258
|
|
|
259 #ifdef ASSERT
|
|
|
260
|
|
|
261 void BasicHashtable::verify_lookup_length(double load) {
|
|
|
262 if ((double)_lookup_length / (double)_lookup_count > load * 2.0) {
|
|
|
263 warning("Performance bug: SystemDictionary lookup_count=%d "
|
|
|
264 "lookup_length=%d average=%lf load=%f",
|
|
|
265 _lookup_count, _lookup_length,
|
|
|
266 (double) _lookup_length / _lookup_count, load);
|
|
|
267 }
|
|
|
268 }
|
|
|
269
|
|
|
270 #endif
|
