|
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 // This is a generic hashtable, designed to be used for the symbol
|
|
|
26 // and string tables.
|
|
|
27 //
|
|
|
28 // It is implemented as an open hash table with a fixed number of buckets.
|
|
|
29 //
|
|
|
30 // %note:
|
|
|
31 // - TableEntrys are allocated in blocks to reduce the space overhead.
|
|
|
32
|
|
|
33
|
|
|
34
|
|
|
35 class BasicHashtableEntry : public CHeapObj {
|
|
|
36 friend class VMStructs;
|
|
|
37 private:
|
|
|
38 unsigned int _hash; // 32-bit hash for item
|
|
|
39
|
|
|
40 // Link to next element in the linked list for this bucket. EXCEPT
|
|
|
41 // bit 0 set indicates that this entry is shared and must not be
|
|
|
42 // unlinked from the table. Bit 0 is set during the dumping of the
|
|
|
43 // archive. Since shared entries are immutable, _next fields in the
|
|
|
44 // shared entries will not change. New entries will always be
|
|
|
45 // unshared and since pointers are align, bit 0 will always remain 0
|
|
|
46 // with no extra effort.
|
|
|
47 BasicHashtableEntry* _next;
|
|
|
48
|
|
|
49 // Windows IA64 compiler requires subclasses to be able to access these
|
|
|
50 protected:
|
|
|
51 // Entry objects should not be created, they should be taken from the
|
|
|
52 // free list with BasicHashtable.new_entry().
|
|
|
53 BasicHashtableEntry() { ShouldNotReachHere(); }
|
|
|
54 // Entry objects should not be destroyed. They should be placed on
|
|
|
55 // the free list instead with BasicHashtable.free_entry().
|
|
|
56 ~BasicHashtableEntry() { ShouldNotReachHere(); }
|
|
|
57
|
|
|
58 public:
|
|
|
59
|
|
|
60 unsigned int hash() const { return _hash; }
|
|
|
61 void set_hash(unsigned int hash) { _hash = hash; }
|
|
|
62 unsigned int* hash_addr() { return &_hash; }
|
|
|
63
|
|
|
64 static BasicHashtableEntry* make_ptr(BasicHashtableEntry* p) {
|
|
|
65 return (BasicHashtableEntry*)((intptr_t)p & -2);
|
|
|
66 }
|
|
|
67
|
|
|
68 BasicHashtableEntry* next() const {
|
|
|
69 return make_ptr(_next);
|
|
|
70 }
|
|
|
71
|
|
|
72 void set_next(BasicHashtableEntry* next) {
|
|
|
73 _next = next;
|
|
|
74 }
|
|
|
75
|
|
|
76 BasicHashtableEntry** next_addr() {
|
|
|
77 return &_next;
|
|
|
78 }
|
|
|
79
|
|
|
80 bool is_shared() const {
|
|
|
81 return ((intptr_t)_next & 1) != 0;
|
|
|
82 }
|
|
|
83
|
|
|
84 void set_shared() {
|
|
|
85 _next = (BasicHashtableEntry*)((intptr_t)_next | 1);
|
|
|
86 }
|
|
|
87 };
|
|
|
88
|
|
|
89
|
|
|
90
|
|
|
91 class HashtableEntry : public BasicHashtableEntry {
|
|
|
92 friend class VMStructs;
|
|
|
93 private:
|
|
|
94 oop _literal; // ref to item in table.
|
|
|
95
|
|
|
96 public:
|
|
|
97 // Literal
|
|
|
98 oop literal() const { return _literal; }
|
|
|
99 oop* literal_addr() { return &_literal; }
|
|
|
100 void set_literal(oop s) { _literal = s; }
|
|
|
101
|
|
|
102 HashtableEntry* next() const {
|
|
|
103 return (HashtableEntry*)BasicHashtableEntry::next();
|
|
|
104 }
|
|
|
105 HashtableEntry** next_addr() {
|
|
|
106 return (HashtableEntry**)BasicHashtableEntry::next_addr();
|
|
|
107 }
|
|
|
108 };
|
|
|
109
|
|
|
110
|
|
|
111
|
|
|
112 class HashtableBucket : public CHeapObj {
|
|
|
113 friend class VMStructs;
|
|
|
114 private:
|
|
|
115 // Instance variable
|
|
|
116 BasicHashtableEntry* _entry;
|
|
|
117
|
|
|
118 public:
|
|
|
119 // Accessing
|
|
|
120 void clear() { _entry = NULL; }
|
|
|
121
|
|
|
122 // The following methods use order access methods to avoid race
|
|
|
123 // conditions in multiprocessor systems.
|
|
|
124 BasicHashtableEntry* get_entry() const;
|
|
|
125 void set_entry(BasicHashtableEntry* l);
|
|
|
126
|
|
|
127 // The following method is not MT-safe and must be done under lock.
|
|
|
128 BasicHashtableEntry** entry_addr() { return &_entry; }
|
|
|
129 };
|
|
|
130
|
|
|
131
|
|
|
132 class BasicHashtable : public CHeapObj {
|
|
|
133 friend class VMStructs;
|
|
|
134
|
|
|
135 public:
|
|
|
136 BasicHashtable(int table_size, int entry_size);
|
|
|
137 BasicHashtable(int table_size, int entry_size,
|
|
|
138 HashtableBucket* buckets, int number_of_entries);
|
|
|
139
|
|
|
140 // Sharing support.
|
|
|
141 void copy_buckets(char** top, char* end);
|
|
|
142 void copy_table(char** top, char* end);
|
|
|
143
|
|
|
144 // Bucket handling
|
|
|
145 int hash_to_index(unsigned int full_hash) {
|
|
|
146 int h = full_hash % _table_size;
|
|
|
147 assert(h >= 0 && h < _table_size, "Illegal hash value");
|
|
|
148 return h;
|
|
|
149 }
|
|
|
150
|
|
|
151 // Reverse the order of elements in each of the buckets.
|
|
|
152 void reverse();
|
|
|
153
|
|
|
154 private:
|
|
|
155 // Instance variables
|
|
|
156 int _table_size;
|
|
|
157 HashtableBucket* _buckets;
|
|
|
158 BasicHashtableEntry* _free_list;
|
|
|
159 char* _first_free_entry;
|
|
|
160 char* _end_block;
|
|
|
161 int _entry_size;
|
|
|
162 int _number_of_entries;
|
|
|
163
|
|
|
164 protected:
|
|
|
165
|
|
|
166 #ifdef ASSERT
|
|
|
167 int _lookup_count;
|
|
|
168 int _lookup_length;
|
|
|
169 void verify_lookup_length(double load);
|
|
|
170 #endif
|
|
|
171
|
|
|
172 void initialize(int table_size, int entry_size, int number_of_entries);
|
|
|
173
|
|
|
174 // Accessor
|
|
|
175 int entry_size() const { return _entry_size; }
|
|
|
176 int table_size() { return _table_size; }
|
|
|
177
|
|
|
178 // The following method is MT-safe and may be used with caution.
|
|
|
179 BasicHashtableEntry* bucket(int i);
|
|
|
180
|
|
|
181 // The following method is not MT-safe and must be done under lock.
|
|
|
182 BasicHashtableEntry** bucket_addr(int i) { return _buckets[i].entry_addr(); }
|
|
|
183
|
|
|
184 // Table entry management
|
|
|
185 BasicHashtableEntry* new_entry(unsigned int hashValue);
|
|
|
186
|
|
|
187 public:
|
|
|
188 void set_entry(int index, BasicHashtableEntry* entry);
|
|
|
189
|
|
|
190 void add_entry(int index, BasicHashtableEntry* entry);
|
|
|
191
|
|
|
192 void free_entry(BasicHashtableEntry* entry);
|
|
|
193
|
|
|
194 int number_of_entries() { return _number_of_entries; }
|
|
|
195
|
|
|
196 void verify() PRODUCT_RETURN;
|
|
|
197 };
|
|
|
198
|
|
|
199
|
|
|
200 class Hashtable : public BasicHashtable {
|
|
|
201 friend class VMStructs;
|
|
|
202
|
|
|
203 public:
|
|
|
204 Hashtable(int table_size, int entry_size)
|
|
|
205 : BasicHashtable(table_size, entry_size) { }
|
|
|
206
|
|
|
207 Hashtable(int table_size, int entry_size,
|
|
|
208 HashtableBucket* buckets, int number_of_entries)
|
|
|
209 : BasicHashtable(table_size, entry_size, buckets, number_of_entries) { }
|
|
|
210
|
|
|
211 // Invoke "f->do_oop" on the locations of all oops in the table.
|
|
|
212 void oops_do(OopClosure* f);
|
|
|
213
|
|
|
214 // Debugging
|
|
|
215 void print() PRODUCT_RETURN;
|
|
|
216
|
|
|
217 // GC support
|
|
|
218 // Delete pointers to otherwise-unreachable objects.
|
|
|
219 void unlink(BoolObjectClosure* cl);
|
|
|
220
|
|
|
221 // Reverse the order of elements in each of the buckets. Hashtable
|
|
|
222 // entries which refer to objects at a lower address than 'boundary'
|
|
|
223 // are separated from those which refer to objects at higher
|
|
|
224 // addresses, and appear first in the list.
|
|
|
225 void reverse(void* boundary = NULL);
|
|
|
226
|
|
|
227 protected:
|
|
|
228
|
|
|
229 static unsigned int hash_symbol(const char* s, int len);
|
|
|
230
|
|
|
231 unsigned int compute_hash(symbolHandle name) {
|
|
|
232 return (unsigned int) name->identity_hash();
|
|
|
233 }
|
|
|
234
|
|
|
235 int index_for(symbolHandle name) {
|
|
|
236 return hash_to_index(compute_hash(name));
|
|
|
237 }
|
|
|
238
|
|
|
239 // Table entry management
|
|
|
240 HashtableEntry* new_entry(unsigned int hashValue, oop obj);
|
|
|
241
|
|
|
242 // The following method is MT-safe and may be used with caution.
|
|
|
243 HashtableEntry* bucket(int i) {
|
|
|
244 return (HashtableEntry*)BasicHashtable::bucket(i);
|
|
|
245 }
|
|
|
246
|
|
|
247 // The following method is not MT-safe and must be done under lock.
|
|
|
248 HashtableEntry** bucket_addr(int i) {
|
|
|
249 return (HashtableEntry**)BasicHashtable::bucket_addr(i);
|
|
|
250 }
|
|
|
251 };
|
|
|
252
|
|
|
253
|
|
|
254 // Verions of hashtable where two handles are used to compute the index.
|
|
|
255
|
|
|
256 class TwoOopHashtable : public Hashtable {
|
|
|
257 friend class VMStructs;
|
|
|
258 protected:
|
|
|
259 TwoOopHashtable(int table_size, int entry_size)
|
|
|
260 : Hashtable(table_size, entry_size) {}
|
|
|
261
|
|
|
262 TwoOopHashtable(int table_size, int entry_size, HashtableBucket* t,
|
|
|
263 int number_of_entries)
|
|
|
264 : Hashtable(table_size, entry_size, t, number_of_entries) {}
|
|
|
265
|
|
|
266 public:
|
|
|
267 unsigned int compute_hash(symbolHandle name, Handle loader) {
|
|
|
268 // Be careful with identity_hash(), it can safepoint and if this
|
|
|
269 // were one expression, the compiler could choose to unhandle each
|
|
|
270 // oop before calling identity_hash() for either of them. If the first
|
|
|
271 // causes a GC, the next would fail.
|
|
|
272 unsigned int name_hash = name->identity_hash();
|
|
|
273 unsigned int loader_hash = loader.is_null() ? 0 : loader->identity_hash();
|
|
|
274 return name_hash ^ loader_hash;
|
|
|
275 }
|
|
|
276
|
|
|
277 int index_for(symbolHandle name, Handle loader) {
|
|
|
278 return hash_to_index(compute_hash(name, loader));
|
|
|
279 }
|
|
|
280 };
|
