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 #ifndef SHARE_VM_UTILITIES_HASHTABLE_HPP
26 #define SHARE_VM_UTILITIES_HASHTABLE_HPP
27
28 #include "classfile/classLoaderData.hpp"
29 #include "memory/allocation.hpp"
30 #include "oops/oop.hpp"
31 #include "oops/symbol.hpp"
32 #include "runtime/handles.hpp"
33
34 // This is a generic hashtable, designed to be used for the symbol
35 // and string tables.
36 //
37 // It is implemented as an open hash table with a fixed number of buckets.
38 //
39 // %note:
40 // - TableEntrys are allocated in blocks to reduce the space overhead.
41
42
43
44 template <MEMFLAGS F> class BasicHashtableEntry : public CHeapObj<F> {
45 friend class VMStructs;
46 private:
47 unsigned int _hash; // 32-bit hash for item
48
49 // Link to next element in the linked list for this bucket. EXCEPT
50 // bit 0 set indicates that this entry is shared and must not be
51 // unlinked from the table. Bit 0 is set during the dumping of the
52 // archive. Since shared entries are immutable, _next fields in the
155
156 // Bucket handling
157 int hash_to_index(unsigned int full_hash) const {
158 int h = full_hash % _table_size;
159 assert(h >= 0 && h < _table_size, "Illegal hash value");
160 return h;
161 }
162
163 private:
164 // Instance variables
165 int _table_size;
166 HashtableBucket<F>* _buckets;
167 BasicHashtableEntry<F>* volatile _free_list;
168 char* _first_free_entry;
169 char* _end_block;
170 int _entry_size;
171 volatile int _number_of_entries;
172
173 protected:
174
175 void initialize(int table_size, int entry_size, int number_of_entries);
176
177 // Accessor
178 int entry_size() const { return _entry_size; }
179
180 // The following method is MT-safe and may be used with caution.
181 BasicHashtableEntry<F>* bucket(int i) const;
182
183 // The following method is not MT-safe and must be done under lock.
184 BasicHashtableEntry<F>** bucket_addr(int i) { return _buckets[i].entry_addr(); }
185
186 // Attempt to get an entry from the free list
187 BasicHashtableEntry<F>* new_entry_free_list();
188
189 // Table entry management
190 BasicHashtableEntry<F>* new_entry(unsigned int hashValue);
191
192 // Used when moving the entry to another table
193 // Clean up links, but do not add to free_list
194 void unlink_entry(BasicHashtableEntry<F>* entry) {
248
249 public:
250 Hashtable(int table_size, int entry_size)
251 : BasicHashtable<F>(table_size, entry_size) { }
252
253 Hashtable(int table_size, int entry_size,
254 HashtableBucket<F>* buckets, int number_of_entries)
255 : BasicHashtable<F>(table_size, entry_size, buckets, number_of_entries) { }
256
257 // Debugging
258 void print() PRODUCT_RETURN;
259
260 unsigned int compute_hash(const Symbol* name) const {
261 return (unsigned int) name->identity_hash();
262 }
263
264 int index_for(const Symbol* name) const {
265 return this->hash_to_index(compute_hash(name));
266 }
267
268 void print_table_statistics(outputStream* st, const char *table_name, T (*literal_load_barrier)(HashtableEntry<T, F>*) = NULL);
269
270 protected:
271
272 // Table entry management
273 HashtableEntry<T, F>* new_entry(unsigned int hashValue, T obj);
274 // Don't create and use freelist of HashtableEntry.
275 HashtableEntry<T, F>* allocate_new_entry(unsigned int hashValue, T obj);
276
277 // The following method is MT-safe and may be used with caution.
278 HashtableEntry<T, F>* bucket(int i) const {
279 return (HashtableEntry<T, F>*)BasicHashtable<F>::bucket(i);
280 }
281
282 // The following method is not MT-safe and must be done under lock.
283 HashtableEntry<T, F>** bucket_addr(int i) {
284 return (HashtableEntry<T, F>**)BasicHashtable<F>::bucket_addr(i);
285 }
286 };
287
|
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 #ifndef SHARE_VM_UTILITIES_HASHTABLE_HPP
26 #define SHARE_VM_UTILITIES_HASHTABLE_HPP
27
28 #include "classfile/classLoaderData.hpp"
29 #include "memory/allocation.hpp"
30 #include "oops/oop.hpp"
31 #include "oops/symbol.hpp"
32 #include "runtime/handles.hpp"
33 #include "utilities/tableStatistics.hpp"
34
35 // This is a generic hashtable, designed to be used for the symbol
36 // and string tables.
37 //
38 // It is implemented as an open hash table with a fixed number of buckets.
39 //
40 // %note:
41 // - TableEntrys are allocated in blocks to reduce the space overhead.
42
43
44
45 template <MEMFLAGS F> class BasicHashtableEntry : public CHeapObj<F> {
46 friend class VMStructs;
47 private:
48 unsigned int _hash; // 32-bit hash for item
49
50 // Link to next element in the linked list for this bucket. EXCEPT
51 // bit 0 set indicates that this entry is shared and must not be
52 // unlinked from the table. Bit 0 is set during the dumping of the
53 // archive. Since shared entries are immutable, _next fields in the
156
157 // Bucket handling
158 int hash_to_index(unsigned int full_hash) const {
159 int h = full_hash % _table_size;
160 assert(h >= 0 && h < _table_size, "Illegal hash value");
161 return h;
162 }
163
164 private:
165 // Instance variables
166 int _table_size;
167 HashtableBucket<F>* _buckets;
168 BasicHashtableEntry<F>* volatile _free_list;
169 char* _first_free_entry;
170 char* _end_block;
171 int _entry_size;
172 volatile int _number_of_entries;
173
174 protected:
175
176 TableRateStatistics _stats_rate;
177
178 void initialize(int table_size, int entry_size, int number_of_entries);
179
180 // Accessor
181 int entry_size() const { return _entry_size; }
182
183 // The following method is MT-safe and may be used with caution.
184 BasicHashtableEntry<F>* bucket(int i) const;
185
186 // The following method is not MT-safe and must be done under lock.
187 BasicHashtableEntry<F>** bucket_addr(int i) { return _buckets[i].entry_addr(); }
188
189 // Attempt to get an entry from the free list
190 BasicHashtableEntry<F>* new_entry_free_list();
191
192 // Table entry management
193 BasicHashtableEntry<F>* new_entry(unsigned int hashValue);
194
195 // Used when moving the entry to another table
196 // Clean up links, but do not add to free_list
197 void unlink_entry(BasicHashtableEntry<F>* entry) {
251
252 public:
253 Hashtable(int table_size, int entry_size)
254 : BasicHashtable<F>(table_size, entry_size) { }
255
256 Hashtable(int table_size, int entry_size,
257 HashtableBucket<F>* buckets, int number_of_entries)
258 : BasicHashtable<F>(table_size, entry_size, buckets, number_of_entries) { }
259
260 // Debugging
261 void print() PRODUCT_RETURN;
262
263 unsigned int compute_hash(const Symbol* name) const {
264 return (unsigned int) name->identity_hash();
265 }
266
267 int index_for(const Symbol* name) const {
268 return this->hash_to_index(compute_hash(name));
269 }
270
271 TableStatistics statistics_calculate(T (*literal_load_barrier)(HashtableEntry<T, F>*) = NULL);
272 void print_table_statistics(outputStream* st, const char *table_name, T (*literal_load_barrier)(HashtableEntry<T, F>*) = NULL);
273
274 protected:
275
276 // Table entry management
277 HashtableEntry<T, F>* new_entry(unsigned int hashValue, T obj);
278 // Don't create and use freelist of HashtableEntry.
279 HashtableEntry<T, F>* allocate_new_entry(unsigned int hashValue, T obj);
280
281 // The following method is MT-safe and may be used with caution.
282 HashtableEntry<T, F>* bucket(int i) const {
283 return (HashtableEntry<T, F>*)BasicHashtable<F>::bucket(i);
284 }
285
286 // The following method is not MT-safe and must be done under lock.
287 HashtableEntry<T, F>** bucket_addr(int i) {
288 return (HashtableEntry<T, F>**)BasicHashtable<F>::bucket_addr(i);
289 }
290 };
291
|