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_UTILITIES_HASHTABLE_HPP
26 #define SHARE_UTILITIES_HASHTABLE_HPP
27
28 #include "memory/allocation.hpp"
29 #include "oops/oop.hpp"
30 #include "oops/symbol.hpp"
31 #include "runtime/handles.hpp"
32 #include "utilities/growableArray.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
151 // Bucket handling
152 int hash_to_index(unsigned int full_hash) const {
153 int h = full_hash % _table_size;
154 assert(h >= 0 && h < _table_size, "Illegal hash value");
155 return h;
156 }
157
158 private:
159 // Instance variables
160 int _table_size;
161 HashtableBucket<F>* _buckets;
162 BasicHashtableEntry<F>* volatile _free_list;
163 char* _first_free_entry;
164 char* _end_block;
165 int _entry_size;
166 volatile int _number_of_entries;
167 GrowableArray<char*>* _entry_blocks;
168
169 protected:
170
171 void initialize(int table_size, int entry_size, int number_of_entries);
172
173 // Accessor
174 int entry_size() const { return _entry_size; }
175
176 // The following method is MT-safe and may be used with caution.
177 BasicHashtableEntry<F>* bucket(int i) const;
178
179 // The following method is not MT-safe and must be done under lock.
180 BasicHashtableEntry<F>** bucket_addr(int i) { return _buckets[i].entry_addr(); }
181
182 // Attempt to get an entry from the free list
183 BasicHashtableEntry<F>* new_entry_free_list();
184
185 // Table entry management
186 BasicHashtableEntry<F>* new_entry(unsigned int hashValue);
187
188 // Used when moving the entry to another table
189 // Clean up links, but do not add to free_list
190 void unlink_entry(BasicHashtableEntry<F>* entry) {
228
229 public:
230 Hashtable(int table_size, int entry_size)
231 : BasicHashtable<F>(table_size, entry_size) { }
232
233 Hashtable(int table_size, int entry_size,
234 HashtableBucket<F>* buckets, int number_of_entries)
235 : BasicHashtable<F>(table_size, entry_size, buckets, number_of_entries) { }
236
237 // Debugging
238 void print() PRODUCT_RETURN;
239
240 unsigned int compute_hash(const Symbol* name) const {
241 return (unsigned int) name->identity_hash();
242 }
243
244 int index_for(const Symbol* name) const {
245 return this->hash_to_index(compute_hash(name));
246 }
247
248 void print_table_statistics(outputStream* st, const char *table_name, T (*literal_load_barrier)(HashtableEntry<T, F>*) = NULL);
249
250 protected:
251
252 // Table entry management
253 HashtableEntry<T, F>* new_entry(unsigned int hashValue, T obj);
254 // Don't create and use freelist of HashtableEntry.
255 HashtableEntry<T, F>* allocate_new_entry(unsigned int hashValue, T obj);
256
257 // The following method is MT-safe and may be used with caution.
258 HashtableEntry<T, F>* bucket(int i) const {
259 return (HashtableEntry<T, F>*)BasicHashtable<F>::bucket(i);
260 }
261
262 // The following method is not MT-safe and must be done under lock.
263 HashtableEntry<T, F>** bucket_addr(int i) {
264 return (HashtableEntry<T, F>**)BasicHashtable<F>::bucket_addr(i);
265 }
266 };
267
|
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_UTILITIES_HASHTABLE_HPP
26 #define SHARE_UTILITIES_HASHTABLE_HPP
27
28 #include "memory/allocation.hpp"
29 #include "oops/oop.hpp"
30 #include "oops/symbol.hpp"
31 #include "runtime/handles.hpp"
32 #include "utilities/growableArray.hpp"
33 #include "utilities/statistics.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
152 // Bucket handling
153 int hash_to_index(unsigned int full_hash) const {
154 int h = full_hash % _table_size;
155 assert(h >= 0 && h < _table_size, "Illegal hash value");
156 return h;
157 }
158
159 private:
160 // Instance variables
161 int _table_size;
162 HashtableBucket<F>* _buckets;
163 BasicHashtableEntry<F>* volatile _free_list;
164 char* _first_free_entry;
165 char* _end_block;
166 int _entry_size;
167 volatile int _number_of_entries;
168 GrowableArray<char*>* _entry_blocks;
169
170 protected:
171
172 TableRateStatistics _stats_rate;
173
174 void initialize(int table_size, int entry_size, int number_of_entries);
175
176 // Accessor
177 int entry_size() const { return _entry_size; }
178
179 // The following method is MT-safe and may be used with caution.
180 BasicHashtableEntry<F>* bucket(int i) const;
181
182 // The following method is not MT-safe and must be done under lock.
183 BasicHashtableEntry<F>** bucket_addr(int i) { return _buckets[i].entry_addr(); }
184
185 // Attempt to get an entry from the free list
186 BasicHashtableEntry<F>* new_entry_free_list();
187
188 // Table entry management
189 BasicHashtableEntry<F>* new_entry(unsigned int hashValue);
190
191 // Used when moving the entry to another table
192 // Clean up links, but do not add to free_list
193 void unlink_entry(BasicHashtableEntry<F>* entry) {
231
232 public:
233 Hashtable(int table_size, int entry_size)
234 : BasicHashtable<F>(table_size, entry_size) { }
235
236 Hashtable(int table_size, int entry_size,
237 HashtableBucket<F>* buckets, int number_of_entries)
238 : BasicHashtable<F>(table_size, entry_size, buckets, number_of_entries) { }
239
240 // Debugging
241 void print() PRODUCT_RETURN;
242
243 unsigned int compute_hash(const Symbol* name) const {
244 return (unsigned int) name->identity_hash();
245 }
246
247 int index_for(const Symbol* name) const {
248 return this->hash_to_index(compute_hash(name));
249 }
250
251 TableStatistics statistics_calculate(T (*literal_load_barrier)(HashtableEntry<T, F>*) = NULL);
252 void print_table_statistics(outputStream* st, const char *table_name, T (*literal_load_barrier)(HashtableEntry<T, F>*) = NULL);
253
254 protected:
255
256 // Table entry management
257 HashtableEntry<T, F>* new_entry(unsigned int hashValue, T obj);
258 // Don't create and use freelist of HashtableEntry.
259 HashtableEntry<T, F>* allocate_new_entry(unsigned int hashValue, T obj);
260
261 // The following method is MT-safe and may be used with caution.
262 HashtableEntry<T, F>* bucket(int i) const {
263 return (HashtableEntry<T, F>*)BasicHashtable<F>::bucket(i);
264 }
265
266 // The following method is not MT-safe and must be done under lock.
267 HashtableEntry<T, F>** bucket_addr(int i) {
268 return (HashtableEntry<T, F>**)BasicHashtable<F>::bucket_addr(i);
269 }
270 };
271
|