1 /*
2 * Copyright (c) 2003, 2005, Oracle and/or its affiliates. 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 Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
20 * or visit www.oracle.com if you need additional information or have any
21 * 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 };