annotate src/share/vm/utilities/hashtable.hpp @ 20804:7848fc12602b

Merge with jdk8u40-b25
author Gilles Duboscq <gilles.m.duboscq@oracle.com>
date Tue, 07 Apr 2015 14:58:49 +0200
parents 52b4284cb496 152cf4afc11f
children
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
0
a61af66fc99e Initial load
duke
parents:
diff changeset
1 /*
14340
cd6b3f1a94ff 8033792: AltHashing used jint for imprecise bit shifting
minqi
parents: 14223
diff changeset
2 * Copyright (c) 2003, 2014, Oracle and/or its affiliates. All rights reserved.
0
a61af66fc99e Initial load
duke
parents:
diff changeset
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
a61af66fc99e Initial load
duke
parents:
diff changeset
4 *
a61af66fc99e Initial load
duke
parents:
diff changeset
5 * This code is free software; you can redistribute it and/or modify it
a61af66fc99e Initial load
duke
parents:
diff changeset
6 * under the terms of the GNU General Public License version 2 only, as
a61af66fc99e Initial load
duke
parents:
diff changeset
7 * published by the Free Software Foundation.
a61af66fc99e Initial load
duke
parents:
diff changeset
8 *
a61af66fc99e Initial load
duke
parents:
diff changeset
9 * This code is distributed in the hope that it will be useful, but WITHOUT
a61af66fc99e Initial load
duke
parents:
diff changeset
10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
a61af66fc99e Initial load
duke
parents:
diff changeset
11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
a61af66fc99e Initial load
duke
parents:
diff changeset
12 * version 2 for more details (a copy is included in the LICENSE file that
a61af66fc99e Initial load
duke
parents:
diff changeset
13 * accompanied this code).
a61af66fc99e Initial load
duke
parents:
diff changeset
14 *
a61af66fc99e Initial load
duke
parents:
diff changeset
15 * You should have received a copy of the GNU General Public License version
a61af66fc99e Initial load
duke
parents:
diff changeset
16 * 2 along with this work; if not, write to the Free Software Foundation,
a61af66fc99e Initial load
duke
parents:
diff changeset
17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
a61af66fc99e Initial load
duke
parents:
diff changeset
18 *
1552
c18cbe5936b8 6941466: Oracle rebranding changes for Hotspot repositories
trims
parents: 0
diff changeset
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
c18cbe5936b8 6941466: Oracle rebranding changes for Hotspot repositories
trims
parents: 0
diff changeset
20 * or visit www.oracle.com if you need additional information or have any
c18cbe5936b8 6941466: Oracle rebranding changes for Hotspot repositories
trims
parents: 0
diff changeset
21 * questions.
0
a61af66fc99e Initial load
duke
parents:
diff changeset
22 *
a61af66fc99e Initial load
duke
parents:
diff changeset
23 */
a61af66fc99e Initial load
duke
parents:
diff changeset
24
1972
f95d63e2154a 6989984: Use standard include model for Hospot
stefank
parents: 1552
diff changeset
25 #ifndef SHARE_VM_UTILITIES_HASHTABLE_HPP
f95d63e2154a 6989984: Use standard include model for Hospot
stefank
parents: 1552
diff changeset
26 #define SHARE_VM_UTILITIES_HASHTABLE_HPP
f95d63e2154a 6989984: Use standard include model for Hospot
stefank
parents: 1552
diff changeset
27
6725
da91efe96a93 6964458: Reimplement class meta-data storage to use native memory
coleenp
parents: 6260
diff changeset
28 #include "classfile/classLoaderData.hpp"
1972
f95d63e2154a 6989984: Use standard include model for Hospot
stefank
parents: 1552
diff changeset
29 #include "memory/allocation.hpp"
f95d63e2154a 6989984: Use standard include model for Hospot
stefank
parents: 1552
diff changeset
30 #include "oops/oop.hpp"
2177
3582bf76420e 6990754: Use native memory and reference counting to implement SymbolTable
coleenp
parents: 1972
diff changeset
31 #include "oops/symbol.hpp"
1972
f95d63e2154a 6989984: Use standard include model for Hospot
stefank
parents: 1552
diff changeset
32 #include "runtime/handles.hpp"
f95d63e2154a 6989984: Use standard include model for Hospot
stefank
parents: 1552
diff changeset
33
0
a61af66fc99e Initial load
duke
parents:
diff changeset
34 // This is a generic hashtable, designed to be used for the symbol
a61af66fc99e Initial load
duke
parents:
diff changeset
35 // and string tables.
a61af66fc99e Initial load
duke
parents:
diff changeset
36 //
a61af66fc99e Initial load
duke
parents:
diff changeset
37 // It is implemented as an open hash table with a fixed number of buckets.
a61af66fc99e Initial load
duke
parents:
diff changeset
38 //
a61af66fc99e Initial load
duke
parents:
diff changeset
39 // %note:
a61af66fc99e Initial load
duke
parents:
diff changeset
40 // - TableEntrys are allocated in blocks to reduce the space overhead.
a61af66fc99e Initial load
duke
parents:
diff changeset
41
a61af66fc99e Initial load
duke
parents:
diff changeset
42
a61af66fc99e Initial load
duke
parents:
diff changeset
43
6197
d2a62e0f25eb 6995781: Native Memory Tracking (Phase 1)
zgu
parents: 6172
diff changeset
44 template <MEMFLAGS F> class BasicHashtableEntry : public CHeapObj<F> {
0
a61af66fc99e Initial load
duke
parents:
diff changeset
45 friend class VMStructs;
a61af66fc99e Initial load
duke
parents:
diff changeset
46 private:
a61af66fc99e Initial load
duke
parents:
diff changeset
47 unsigned int _hash; // 32-bit hash for item
a61af66fc99e Initial load
duke
parents:
diff changeset
48
a61af66fc99e Initial load
duke
parents:
diff changeset
49 // Link to next element in the linked list for this bucket. EXCEPT
a61af66fc99e Initial load
duke
parents:
diff changeset
50 // bit 0 set indicates that this entry is shared and must not be
a61af66fc99e Initial load
duke
parents:
diff changeset
51 // unlinked from the table. Bit 0 is set during the dumping of the
a61af66fc99e Initial load
duke
parents:
diff changeset
52 // archive. Since shared entries are immutable, _next fields in the
a61af66fc99e Initial load
duke
parents:
diff changeset
53 // shared entries will not change. New entries will always be
a61af66fc99e Initial load
duke
parents:
diff changeset
54 // unshared and since pointers are align, bit 0 will always remain 0
a61af66fc99e Initial load
duke
parents:
diff changeset
55 // with no extra effort.
6197
d2a62e0f25eb 6995781: Native Memory Tracking (Phase 1)
zgu
parents: 6172
diff changeset
56 BasicHashtableEntry<F>* _next;
0
a61af66fc99e Initial load
duke
parents:
diff changeset
57
a61af66fc99e Initial load
duke
parents:
diff changeset
58 // Windows IA64 compiler requires subclasses to be able to access these
a61af66fc99e Initial load
duke
parents:
diff changeset
59 protected:
a61af66fc99e Initial load
duke
parents:
diff changeset
60 // Entry objects should not be created, they should be taken from the
a61af66fc99e Initial load
duke
parents:
diff changeset
61 // free list with BasicHashtable.new_entry().
a61af66fc99e Initial load
duke
parents:
diff changeset
62 BasicHashtableEntry() { ShouldNotReachHere(); }
a61af66fc99e Initial load
duke
parents:
diff changeset
63 // Entry objects should not be destroyed. They should be placed on
a61af66fc99e Initial load
duke
parents:
diff changeset
64 // the free list instead with BasicHashtable.free_entry().
a61af66fc99e Initial load
duke
parents:
diff changeset
65 ~BasicHashtableEntry() { ShouldNotReachHere(); }
a61af66fc99e Initial load
duke
parents:
diff changeset
66
a61af66fc99e Initial load
duke
parents:
diff changeset
67 public:
a61af66fc99e Initial load
duke
parents:
diff changeset
68
a61af66fc99e Initial load
duke
parents:
diff changeset
69 unsigned int hash() const { return _hash; }
a61af66fc99e Initial load
duke
parents:
diff changeset
70 void set_hash(unsigned int hash) { _hash = hash; }
a61af66fc99e Initial load
duke
parents:
diff changeset
71 unsigned int* hash_addr() { return &_hash; }
a61af66fc99e Initial load
duke
parents:
diff changeset
72
6197
d2a62e0f25eb 6995781: Native Memory Tracking (Phase 1)
zgu
parents: 6172
diff changeset
73 static BasicHashtableEntry<F>* make_ptr(BasicHashtableEntry<F>* p) {
0
a61af66fc99e Initial load
duke
parents:
diff changeset
74 return (BasicHashtableEntry*)((intptr_t)p & -2);
a61af66fc99e Initial load
duke
parents:
diff changeset
75 }
a61af66fc99e Initial load
duke
parents:
diff changeset
76
6197
d2a62e0f25eb 6995781: Native Memory Tracking (Phase 1)
zgu
parents: 6172
diff changeset
77 BasicHashtableEntry<F>* next() const {
0
a61af66fc99e Initial load
duke
parents:
diff changeset
78 return make_ptr(_next);
a61af66fc99e Initial load
duke
parents:
diff changeset
79 }
a61af66fc99e Initial load
duke
parents:
diff changeset
80
6197
d2a62e0f25eb 6995781: Native Memory Tracking (Phase 1)
zgu
parents: 6172
diff changeset
81 void set_next(BasicHashtableEntry<F>* next) {
0
a61af66fc99e Initial load
duke
parents:
diff changeset
82 _next = next;
a61af66fc99e Initial load
duke
parents:
diff changeset
83 }
a61af66fc99e Initial load
duke
parents:
diff changeset
84
6197
d2a62e0f25eb 6995781: Native Memory Tracking (Phase 1)
zgu
parents: 6172
diff changeset
85 BasicHashtableEntry<F>** next_addr() {
0
a61af66fc99e Initial load
duke
parents:
diff changeset
86 return &_next;
a61af66fc99e Initial load
duke
parents:
diff changeset
87 }
a61af66fc99e Initial load
duke
parents:
diff changeset
88
a61af66fc99e Initial load
duke
parents:
diff changeset
89 bool is_shared() const {
a61af66fc99e Initial load
duke
parents:
diff changeset
90 return ((intptr_t)_next & 1) != 0;
a61af66fc99e Initial load
duke
parents:
diff changeset
91 }
a61af66fc99e Initial load
duke
parents:
diff changeset
92
a61af66fc99e Initial load
duke
parents:
diff changeset
93 void set_shared() {
6197
d2a62e0f25eb 6995781: Native Memory Tracking (Phase 1)
zgu
parents: 6172
diff changeset
94 _next = (BasicHashtableEntry<F>*)((intptr_t)_next | 1);
0
a61af66fc99e Initial load
duke
parents:
diff changeset
95 }
a61af66fc99e Initial load
duke
parents:
diff changeset
96 };
a61af66fc99e Initial load
duke
parents:
diff changeset
97
a61af66fc99e Initial load
duke
parents:
diff changeset
98
a61af66fc99e Initial load
duke
parents:
diff changeset
99
6197
d2a62e0f25eb 6995781: Native Memory Tracking (Phase 1)
zgu
parents: 6172
diff changeset
100 template <class T, MEMFLAGS F> class HashtableEntry : public BasicHashtableEntry<F> {
0
a61af66fc99e Initial load
duke
parents:
diff changeset
101 friend class VMStructs;
a61af66fc99e Initial load
duke
parents:
diff changeset
102 private:
2177
3582bf76420e 6990754: Use native memory and reference counting to implement SymbolTable
coleenp
parents: 1972
diff changeset
103 T _literal; // ref to item in table.
0
a61af66fc99e Initial load
duke
parents:
diff changeset
104
a61af66fc99e Initial load
duke
parents:
diff changeset
105 public:
a61af66fc99e Initial load
duke
parents:
diff changeset
106 // Literal
2177
3582bf76420e 6990754: Use native memory and reference counting to implement SymbolTable
coleenp
parents: 1972
diff changeset
107 T literal() const { return _literal; }
3582bf76420e 6990754: Use native memory and reference counting to implement SymbolTable
coleenp
parents: 1972
diff changeset
108 T* literal_addr() { return &_literal; }
3582bf76420e 6990754: Use native memory and reference counting to implement SymbolTable
coleenp
parents: 1972
diff changeset
109 void set_literal(T s) { _literal = s; }
0
a61af66fc99e Initial load
duke
parents:
diff changeset
110
a61af66fc99e Initial load
duke
parents:
diff changeset
111 HashtableEntry* next() const {
6197
d2a62e0f25eb 6995781: Native Memory Tracking (Phase 1)
zgu
parents: 6172
diff changeset
112 return (HashtableEntry*)BasicHashtableEntry<F>::next();
0
a61af66fc99e Initial load
duke
parents:
diff changeset
113 }
a61af66fc99e Initial load
duke
parents:
diff changeset
114 HashtableEntry** next_addr() {
6197
d2a62e0f25eb 6995781: Native Memory Tracking (Phase 1)
zgu
parents: 6172
diff changeset
115 return (HashtableEntry**)BasicHashtableEntry<F>::next_addr();
0
a61af66fc99e Initial load
duke
parents:
diff changeset
116 }
a61af66fc99e Initial load
duke
parents:
diff changeset
117 };
a61af66fc99e Initial load
duke
parents:
diff changeset
118
a61af66fc99e Initial load
duke
parents:
diff changeset
119
a61af66fc99e Initial load
duke
parents:
diff changeset
120
6197
d2a62e0f25eb 6995781: Native Memory Tracking (Phase 1)
zgu
parents: 6172
diff changeset
121 template <MEMFLAGS F> class HashtableBucket : public CHeapObj<F> {
0
a61af66fc99e Initial load
duke
parents:
diff changeset
122 friend class VMStructs;
a61af66fc99e Initial load
duke
parents:
diff changeset
123 private:
a61af66fc99e Initial load
duke
parents:
diff changeset
124 // Instance variable
6197
d2a62e0f25eb 6995781: Native Memory Tracking (Phase 1)
zgu
parents: 6172
diff changeset
125 BasicHashtableEntry<F>* _entry;
0
a61af66fc99e Initial load
duke
parents:
diff changeset
126
a61af66fc99e Initial load
duke
parents:
diff changeset
127 public:
a61af66fc99e Initial load
duke
parents:
diff changeset
128 // Accessing
a61af66fc99e Initial load
duke
parents:
diff changeset
129 void clear() { _entry = NULL; }
a61af66fc99e Initial load
duke
parents:
diff changeset
130
a61af66fc99e Initial load
duke
parents:
diff changeset
131 // The following methods use order access methods to avoid race
a61af66fc99e Initial load
duke
parents:
diff changeset
132 // conditions in multiprocessor systems.
6197
d2a62e0f25eb 6995781: Native Memory Tracking (Phase 1)
zgu
parents: 6172
diff changeset
133 BasicHashtableEntry<F>* get_entry() const;
d2a62e0f25eb 6995781: Native Memory Tracking (Phase 1)
zgu
parents: 6172
diff changeset
134 void set_entry(BasicHashtableEntry<F>* l);
0
a61af66fc99e Initial load
duke
parents:
diff changeset
135
a61af66fc99e Initial load
duke
parents:
diff changeset
136 // The following method is not MT-safe and must be done under lock.
6197
d2a62e0f25eb 6995781: Native Memory Tracking (Phase 1)
zgu
parents: 6172
diff changeset
137 BasicHashtableEntry<F>** entry_addr() { return &_entry; }
0
a61af66fc99e Initial load
duke
parents:
diff changeset
138 };
a61af66fc99e Initial load
duke
parents:
diff changeset
139
a61af66fc99e Initial load
duke
parents:
diff changeset
140
6197
d2a62e0f25eb 6995781: Native Memory Tracking (Phase 1)
zgu
parents: 6172
diff changeset
141 template <MEMFLAGS F> class BasicHashtable : public CHeapObj<F> {
0
a61af66fc99e Initial load
duke
parents:
diff changeset
142 friend class VMStructs;
a61af66fc99e Initial load
duke
parents:
diff changeset
143
a61af66fc99e Initial load
duke
parents:
diff changeset
144 public:
a61af66fc99e Initial load
duke
parents:
diff changeset
145 BasicHashtable(int table_size, int entry_size);
a61af66fc99e Initial load
duke
parents:
diff changeset
146 BasicHashtable(int table_size, int entry_size,
6197
d2a62e0f25eb 6995781: Native Memory Tracking (Phase 1)
zgu
parents: 6172
diff changeset
147 HashtableBucket<F>* buckets, int number_of_entries);
0
a61af66fc99e Initial load
duke
parents:
diff changeset
148
a61af66fc99e Initial load
duke
parents:
diff changeset
149 // Sharing support.
a61af66fc99e Initial load
duke
parents:
diff changeset
150 void copy_buckets(char** top, char* end);
a61af66fc99e Initial load
duke
parents:
diff changeset
151 void copy_table(char** top, char* end);
a61af66fc99e Initial load
duke
parents:
diff changeset
152
a61af66fc99e Initial load
duke
parents:
diff changeset
153 // Bucket handling
a61af66fc99e Initial load
duke
parents:
diff changeset
154 int hash_to_index(unsigned int full_hash) {
a61af66fc99e Initial load
duke
parents:
diff changeset
155 int h = full_hash % _table_size;
a61af66fc99e Initial load
duke
parents:
diff changeset
156 assert(h >= 0 && h < _table_size, "Illegal hash value");
a61af66fc99e Initial load
duke
parents:
diff changeset
157 return h;
a61af66fc99e Initial load
duke
parents:
diff changeset
158 }
a61af66fc99e Initial load
duke
parents:
diff changeset
159
a61af66fc99e Initial load
duke
parents:
diff changeset
160 // Reverse the order of elements in each of the buckets.
a61af66fc99e Initial load
duke
parents:
diff changeset
161 void reverse();
a61af66fc99e Initial load
duke
parents:
diff changeset
162
a61af66fc99e Initial load
duke
parents:
diff changeset
163 private:
a61af66fc99e Initial load
duke
parents:
diff changeset
164 // Instance variables
a61af66fc99e Initial load
duke
parents:
diff changeset
165 int _table_size;
6197
d2a62e0f25eb 6995781: Native Memory Tracking (Phase 1)
zgu
parents: 6172
diff changeset
166 HashtableBucket<F>* _buckets;
d2a62e0f25eb 6995781: Native Memory Tracking (Phase 1)
zgu
parents: 6172
diff changeset
167 BasicHashtableEntry<F>* _free_list;
0
a61af66fc99e Initial load
duke
parents:
diff changeset
168 char* _first_free_entry;
a61af66fc99e Initial load
duke
parents:
diff changeset
169 char* _end_block;
a61af66fc99e Initial load
duke
parents:
diff changeset
170 int _entry_size;
a61af66fc99e Initial load
duke
parents:
diff changeset
171 int _number_of_entries;
a61af66fc99e Initial load
duke
parents:
diff changeset
172
a61af66fc99e Initial load
duke
parents:
diff changeset
173 protected:
a61af66fc99e Initial load
duke
parents:
diff changeset
174
a61af66fc99e Initial load
duke
parents:
diff changeset
175 #ifdef ASSERT
a61af66fc99e Initial load
duke
parents:
diff changeset
176 int _lookup_count;
a61af66fc99e Initial load
duke
parents:
diff changeset
177 int _lookup_length;
a61af66fc99e Initial load
duke
parents:
diff changeset
178 void verify_lookup_length(double load);
a61af66fc99e Initial load
duke
parents:
diff changeset
179 #endif
a61af66fc99e Initial load
duke
parents:
diff changeset
180
a61af66fc99e Initial load
duke
parents:
diff changeset
181 void initialize(int table_size, int entry_size, int number_of_entries);
a61af66fc99e Initial load
duke
parents:
diff changeset
182
a61af66fc99e Initial load
duke
parents:
diff changeset
183 // Accessor
a61af66fc99e Initial load
duke
parents:
diff changeset
184 int entry_size() const { return _entry_size; }
a61af66fc99e Initial load
duke
parents:
diff changeset
185
a61af66fc99e Initial load
duke
parents:
diff changeset
186 // The following method is MT-safe and may be used with caution.
6197
d2a62e0f25eb 6995781: Native Memory Tracking (Phase 1)
zgu
parents: 6172
diff changeset
187 BasicHashtableEntry<F>* bucket(int i);
0
a61af66fc99e Initial load
duke
parents:
diff changeset
188
a61af66fc99e Initial load
duke
parents:
diff changeset
189 // The following method is not MT-safe and must be done under lock.
6197
d2a62e0f25eb 6995781: Native Memory Tracking (Phase 1)
zgu
parents: 6172
diff changeset
190 BasicHashtableEntry<F>** bucket_addr(int i) { return _buckets[i].entry_addr(); }
0
a61af66fc99e Initial load
duke
parents:
diff changeset
191
20493
152cf4afc11f 8056084: Refactor Hashtable to allow implementations without rehashing support
mgerdin
parents: 14340
diff changeset
192 // Attempt to get an entry from the free list
152cf4afc11f 8056084: Refactor Hashtable to allow implementations without rehashing support
mgerdin
parents: 14340
diff changeset
193 BasicHashtableEntry<F>* new_entry_free_list();
152cf4afc11f 8056084: Refactor Hashtable to allow implementations without rehashing support
mgerdin
parents: 14340
diff changeset
194
0
a61af66fc99e Initial load
duke
parents:
diff changeset
195 // Table entry management
6197
d2a62e0f25eb 6995781: Native Memory Tracking (Phase 1)
zgu
parents: 6172
diff changeset
196 BasicHashtableEntry<F>* new_entry(unsigned int hashValue);
0
a61af66fc99e Initial load
duke
parents:
diff changeset
197
6162
e9140bf80b4a 7158800: Improve storage of symbol tables
coleenp
parents: 4864
diff changeset
198 // Used when moving the entry to another table
e9140bf80b4a 7158800: Improve storage of symbol tables
coleenp
parents: 4864
diff changeset
199 // Clean up links, but do not add to free_list
6197
d2a62e0f25eb 6995781: Native Memory Tracking (Phase 1)
zgu
parents: 6172
diff changeset
200 void unlink_entry(BasicHashtableEntry<F>* entry) {
6162
e9140bf80b4a 7158800: Improve storage of symbol tables
coleenp
parents: 4864
diff changeset
201 entry->set_next(NULL);
e9140bf80b4a 7158800: Improve storage of symbol tables
coleenp
parents: 4864
diff changeset
202 --_number_of_entries;
e9140bf80b4a 7158800: Improve storage of symbol tables
coleenp
parents: 4864
diff changeset
203 }
e9140bf80b4a 7158800: Improve storage of symbol tables
coleenp
parents: 4864
diff changeset
204
e9140bf80b4a 7158800: Improve storage of symbol tables
coleenp
parents: 4864
diff changeset
205 // Move over freelist and free block for allocation
e9140bf80b4a 7158800: Improve storage of symbol tables
coleenp
parents: 4864
diff changeset
206 void copy_freelist(BasicHashtable* src) {
e9140bf80b4a 7158800: Improve storage of symbol tables
coleenp
parents: 4864
diff changeset
207 _free_list = src->_free_list;
e9140bf80b4a 7158800: Improve storage of symbol tables
coleenp
parents: 4864
diff changeset
208 src->_free_list = NULL;
e9140bf80b4a 7158800: Improve storage of symbol tables
coleenp
parents: 4864
diff changeset
209 _first_free_entry = src->_first_free_entry;
e9140bf80b4a 7158800: Improve storage of symbol tables
coleenp
parents: 4864
diff changeset
210 src->_first_free_entry = NULL;
e9140bf80b4a 7158800: Improve storage of symbol tables
coleenp
parents: 4864
diff changeset
211 _end_block = src->_end_block;
e9140bf80b4a 7158800: Improve storage of symbol tables
coleenp
parents: 4864
diff changeset
212 src->_end_block = NULL;
e9140bf80b4a 7158800: Improve storage of symbol tables
coleenp
parents: 4864
diff changeset
213 }
e9140bf80b4a 7158800: Improve storage of symbol tables
coleenp
parents: 4864
diff changeset
214
e9140bf80b4a 7158800: Improve storage of symbol tables
coleenp
parents: 4864
diff changeset
215 // Free the buckets in this hashtable
6172
246d977b51f2 7178670: runtime/7158800/BadUtf8.java fails in SymbolTable::rehash_table
coleenp
parents: 6162
diff changeset
216 void free_buckets();
6162
e9140bf80b4a 7158800: Improve storage of symbol tables
coleenp
parents: 4864
diff changeset
217
0
a61af66fc99e Initial load
duke
parents:
diff changeset
218 public:
4864
b2cd0ee8f778 7114376: Make system dictionary hashtable bucket array size configurable
acorn
parents: 2426
diff changeset
219 int table_size() { return _table_size; }
6197
d2a62e0f25eb 6995781: Native Memory Tracking (Phase 1)
zgu
parents: 6172
diff changeset
220 void set_entry(int index, BasicHashtableEntry<F>* entry);
0
a61af66fc99e Initial load
duke
parents:
diff changeset
221
6197
d2a62e0f25eb 6995781: Native Memory Tracking (Phase 1)
zgu
parents: 6172
diff changeset
222 void add_entry(int index, BasicHashtableEntry<F>* entry);
0
a61af66fc99e Initial load
duke
parents:
diff changeset
223
6197
d2a62e0f25eb 6995781: Native Memory Tracking (Phase 1)
zgu
parents: 6172
diff changeset
224 void free_entry(BasicHashtableEntry<F>* entry);
0
a61af66fc99e Initial load
duke
parents:
diff changeset
225
a61af66fc99e Initial load
duke
parents:
diff changeset
226 int number_of_entries() { return _number_of_entries; }
a61af66fc99e Initial load
duke
parents:
diff changeset
227
a61af66fc99e Initial load
duke
parents:
diff changeset
228 void verify() PRODUCT_RETURN;
a61af66fc99e Initial load
duke
parents:
diff changeset
229 };
a61af66fc99e Initial load
duke
parents:
diff changeset
230
a61af66fc99e Initial load
duke
parents:
diff changeset
231
6197
d2a62e0f25eb 6995781: Native Memory Tracking (Phase 1)
zgu
parents: 6172
diff changeset
232 template <class T, MEMFLAGS F> class Hashtable : public BasicHashtable<F> {
0
a61af66fc99e Initial load
duke
parents:
diff changeset
233 friend class VMStructs;
a61af66fc99e Initial load
duke
parents:
diff changeset
234
a61af66fc99e Initial load
duke
parents:
diff changeset
235 public:
a61af66fc99e Initial load
duke
parents:
diff changeset
236 Hashtable(int table_size, int entry_size)
6197
d2a62e0f25eb 6995781: Native Memory Tracking (Phase 1)
zgu
parents: 6172
diff changeset
237 : BasicHashtable<F>(table_size, entry_size) { }
0
a61af66fc99e Initial load
duke
parents:
diff changeset
238
a61af66fc99e Initial load
duke
parents:
diff changeset
239 Hashtable(int table_size, int entry_size,
6197
d2a62e0f25eb 6995781: Native Memory Tracking (Phase 1)
zgu
parents: 6172
diff changeset
240 HashtableBucket<F>* buckets, int number_of_entries)
d2a62e0f25eb 6995781: Native Memory Tracking (Phase 1)
zgu
parents: 6172
diff changeset
241 : BasicHashtable<F>(table_size, entry_size, buckets, number_of_entries) { }
0
a61af66fc99e Initial load
duke
parents:
diff changeset
242
a61af66fc99e Initial load
duke
parents:
diff changeset
243 // Debugging
a61af66fc99e Initial load
duke
parents:
diff changeset
244 void print() PRODUCT_RETURN;
a61af66fc99e Initial load
duke
parents:
diff changeset
245
a61af66fc99e Initial load
duke
parents:
diff changeset
246 // Reverse the order of elements in each of the buckets. Hashtable
a61af66fc99e Initial load
duke
parents:
diff changeset
247 // entries which refer to objects at a lower address than 'boundary'
a61af66fc99e Initial load
duke
parents:
diff changeset
248 // are separated from those which refer to objects at higher
a61af66fc99e Initial load
duke
parents:
diff changeset
249 // addresses, and appear first in the list.
a61af66fc99e Initial load
duke
parents:
diff changeset
250 void reverse(void* boundary = NULL);
a61af66fc99e Initial load
duke
parents:
diff changeset
251
a61af66fc99e Initial load
duke
parents:
diff changeset
252 protected:
a61af66fc99e Initial load
duke
parents:
diff changeset
253
2177
3582bf76420e 6990754: Use native memory and reference counting to implement SymbolTable
coleenp
parents: 1972
diff changeset
254 unsigned int compute_hash(Symbol* name) {
0
a61af66fc99e Initial load
duke
parents:
diff changeset
255 return (unsigned int) name->identity_hash();
a61af66fc99e Initial load
duke
parents:
diff changeset
256 }
a61af66fc99e Initial load
duke
parents:
diff changeset
257
2177
3582bf76420e 6990754: Use native memory and reference counting to implement SymbolTable
coleenp
parents: 1972
diff changeset
258 int index_for(Symbol* name) {
6260
5e2dc722e70d 7186278: Build error after CR#6995781 / 7151532 with GCC 4.7.0
andrew
parents: 6201
diff changeset
259 return this->hash_to_index(compute_hash(name));
0
a61af66fc99e Initial load
duke
parents:
diff changeset
260 }
a61af66fc99e Initial load
duke
parents:
diff changeset
261
a61af66fc99e Initial load
duke
parents:
diff changeset
262 // Table entry management
6197
d2a62e0f25eb 6995781: Native Memory Tracking (Phase 1)
zgu
parents: 6172
diff changeset
263 HashtableEntry<T, F>* new_entry(unsigned int hashValue, T obj);
0
a61af66fc99e Initial load
duke
parents:
diff changeset
264
a61af66fc99e Initial load
duke
parents:
diff changeset
265 // The following method is MT-safe and may be used with caution.
6197
d2a62e0f25eb 6995781: Native Memory Tracking (Phase 1)
zgu
parents: 6172
diff changeset
266 HashtableEntry<T, F>* bucket(int i) {
d2a62e0f25eb 6995781: Native Memory Tracking (Phase 1)
zgu
parents: 6172
diff changeset
267 return (HashtableEntry<T, F>*)BasicHashtable<F>::bucket(i);
0
a61af66fc99e Initial load
duke
parents:
diff changeset
268 }
a61af66fc99e Initial load
duke
parents:
diff changeset
269
a61af66fc99e Initial load
duke
parents:
diff changeset
270 // The following method is not MT-safe and must be done under lock.
6197
d2a62e0f25eb 6995781: Native Memory Tracking (Phase 1)
zgu
parents: 6172
diff changeset
271 HashtableEntry<T, F>** bucket_addr(int i) {
d2a62e0f25eb 6995781: Native Memory Tracking (Phase 1)
zgu
parents: 6172
diff changeset
272 return (HashtableEntry<T, F>**)BasicHashtable<F>::bucket_addr(i);
0
a61af66fc99e Initial load
duke
parents:
diff changeset
273 }
6162
e9140bf80b4a 7158800: Improve storage of symbol tables
coleenp
parents: 4864
diff changeset
274
20493
152cf4afc11f 8056084: Refactor Hashtable to allow implementations without rehashing support
mgerdin
parents: 14340
diff changeset
275 };
152cf4afc11f 8056084: Refactor Hashtable to allow implementations without rehashing support
mgerdin
parents: 14340
diff changeset
276
152cf4afc11f 8056084: Refactor Hashtable to allow implementations without rehashing support
mgerdin
parents: 14340
diff changeset
277 template <class T, MEMFLAGS F> class RehashableHashtable : public Hashtable<T, F> {
152cf4afc11f 8056084: Refactor Hashtable to allow implementations without rehashing support
mgerdin
parents: 14340
diff changeset
278 protected:
152cf4afc11f 8056084: Refactor Hashtable to allow implementations without rehashing support
mgerdin
parents: 14340
diff changeset
279
152cf4afc11f 8056084: Refactor Hashtable to allow implementations without rehashing support
mgerdin
parents: 14340
diff changeset
280 enum {
152cf4afc11f 8056084: Refactor Hashtable to allow implementations without rehashing support
mgerdin
parents: 14340
diff changeset
281 rehash_count = 100,
152cf4afc11f 8056084: Refactor Hashtable to allow implementations without rehashing support
mgerdin
parents: 14340
diff changeset
282 rehash_multiple = 60
152cf4afc11f 8056084: Refactor Hashtable to allow implementations without rehashing support
mgerdin
parents: 14340
diff changeset
283 };
152cf4afc11f 8056084: Refactor Hashtable to allow implementations without rehashing support
mgerdin
parents: 14340
diff changeset
284
152cf4afc11f 8056084: Refactor Hashtable to allow implementations without rehashing support
mgerdin
parents: 14340
diff changeset
285 // Check that the table is unbalanced
152cf4afc11f 8056084: Refactor Hashtable to allow implementations without rehashing support
mgerdin
parents: 14340
diff changeset
286 bool check_rehash_table(int count);
152cf4afc11f 8056084: Refactor Hashtable to allow implementations without rehashing support
mgerdin
parents: 14340
diff changeset
287
152cf4afc11f 8056084: Refactor Hashtable to allow implementations without rehashing support
mgerdin
parents: 14340
diff changeset
288 public:
152cf4afc11f 8056084: Refactor Hashtable to allow implementations without rehashing support
mgerdin
parents: 14340
diff changeset
289 RehashableHashtable(int table_size, int entry_size)
152cf4afc11f 8056084: Refactor Hashtable to allow implementations without rehashing support
mgerdin
parents: 14340
diff changeset
290 : Hashtable<T, F>(table_size, entry_size) { }
152cf4afc11f 8056084: Refactor Hashtable to allow implementations without rehashing support
mgerdin
parents: 14340
diff changeset
291
152cf4afc11f 8056084: Refactor Hashtable to allow implementations without rehashing support
mgerdin
parents: 14340
diff changeset
292 RehashableHashtable(int table_size, int entry_size,
152cf4afc11f 8056084: Refactor Hashtable to allow implementations without rehashing support
mgerdin
parents: 14340
diff changeset
293 HashtableBucket<F>* buckets, int number_of_entries)
152cf4afc11f 8056084: Refactor Hashtable to allow implementations without rehashing support
mgerdin
parents: 14340
diff changeset
294 : Hashtable<T, F>(table_size, entry_size, buckets, number_of_entries) { }
152cf4afc11f 8056084: Refactor Hashtable to allow implementations without rehashing support
mgerdin
parents: 14340
diff changeset
295
152cf4afc11f 8056084: Refactor Hashtable to allow implementations without rehashing support
mgerdin
parents: 14340
diff changeset
296
6162
e9140bf80b4a 7158800: Improve storage of symbol tables
coleenp
parents: 4864
diff changeset
297 // Function to move these elements into the new table.
20493
152cf4afc11f 8056084: Refactor Hashtable to allow implementations without rehashing support
mgerdin
parents: 14340
diff changeset
298 void move_to(RehashableHashtable<T, F>* new_table);
6201
ace99a6ffc83 7181200: JVM new hashing code breaks SA in product mode
coleenp
parents: 6197
diff changeset
299 static bool use_alternate_hashcode() { return _seed != 0; }
14340
cd6b3f1a94ff 8033792: AltHashing used jint for imprecise bit shifting
minqi
parents: 14223
diff changeset
300 static juint seed() { return _seed; }
6201
ace99a6ffc83 7181200: JVM new hashing code breaks SA in product mode
coleenp
parents: 6197
diff changeset
301
10312
a5d6f0c3585f 8014262: PrintStringTableStatistics should include more footprint info
iklam
parents: 6725
diff changeset
302 static int literal_size(Symbol *symbol);
a5d6f0c3585f 8014262: PrintStringTableStatistics should include more footprint info
iklam
parents: 6725
diff changeset
303 static int literal_size(oop oop);
a5d6f0c3585f 8014262: PrintStringTableStatistics should include more footprint info
iklam
parents: 6725
diff changeset
304
a5d6f0c3585f 8014262: PrintStringTableStatistics should include more footprint info
iklam
parents: 6725
diff changeset
305 // The following two are currently not used, but are needed anyway because some
a5d6f0c3585f 8014262: PrintStringTableStatistics should include more footprint info
iklam
parents: 6725
diff changeset
306 // C++ compilers (MacOS and Solaris) force the instantiation of
a5d6f0c3585f 8014262: PrintStringTableStatistics should include more footprint info
iklam
parents: 6725
diff changeset
307 // Hashtable<ConstantPool*, mtClass>::dump_table() even though we never call this function
a5d6f0c3585f 8014262: PrintStringTableStatistics should include more footprint info
iklam
parents: 6725
diff changeset
308 // in the VM code.
a5d6f0c3585f 8014262: PrintStringTableStatistics should include more footprint info
iklam
parents: 6725
diff changeset
309 static int literal_size(ConstantPool *cp) {Unimplemented(); return 0;}
a5d6f0c3585f 8014262: PrintStringTableStatistics should include more footprint info
iklam
parents: 6725
diff changeset
310 static int literal_size(Klass *k) {Unimplemented(); return 0;}
a5d6f0c3585f 8014262: PrintStringTableStatistics should include more footprint info
iklam
parents: 6725
diff changeset
311
a5d6f0c3585f 8014262: PrintStringTableStatistics should include more footprint info
iklam
parents: 6725
diff changeset
312 void dump_table(outputStream* st, const char *table_name);
a5d6f0c3585f 8014262: PrintStringTableStatistics should include more footprint info
iklam
parents: 6725
diff changeset
313
6201
ace99a6ffc83 7181200: JVM new hashing code breaks SA in product mode
coleenp
parents: 6197
diff changeset
314 private:
14340
cd6b3f1a94ff 8033792: AltHashing used jint for imprecise bit shifting
minqi
parents: 14223
diff changeset
315 static juint _seed;
0
a61af66fc99e Initial load
duke
parents:
diff changeset
316 };
a61af66fc99e Initial load
duke
parents:
diff changeset
317
a61af66fc99e Initial load
duke
parents:
diff changeset
318
a61af66fc99e Initial load
duke
parents:
diff changeset
319 // Verions of hashtable where two handles are used to compute the index.
a61af66fc99e Initial load
duke
parents:
diff changeset
320
6197
d2a62e0f25eb 6995781: Native Memory Tracking (Phase 1)
zgu
parents: 6172
diff changeset
321 template <class T, MEMFLAGS F> class TwoOopHashtable : public Hashtable<T, F> {
0
a61af66fc99e Initial load
duke
parents:
diff changeset
322 friend class VMStructs;
a61af66fc99e Initial load
duke
parents:
diff changeset
323 protected:
a61af66fc99e Initial load
duke
parents:
diff changeset
324 TwoOopHashtable(int table_size, int entry_size)
6197
d2a62e0f25eb 6995781: Native Memory Tracking (Phase 1)
zgu
parents: 6172
diff changeset
325 : Hashtable<T, F>(table_size, entry_size) {}
0
a61af66fc99e Initial load
duke
parents:
diff changeset
326
6197
d2a62e0f25eb 6995781: Native Memory Tracking (Phase 1)
zgu
parents: 6172
diff changeset
327 TwoOopHashtable(int table_size, int entry_size, HashtableBucket<F>* t,
0
a61af66fc99e Initial load
duke
parents:
diff changeset
328 int number_of_entries)
6197
d2a62e0f25eb 6995781: Native Memory Tracking (Phase 1)
zgu
parents: 6172
diff changeset
329 : Hashtable<T, F>(table_size, entry_size, t, number_of_entries) {}
0
a61af66fc99e Initial load
duke
parents:
diff changeset
330
a61af66fc99e Initial load
duke
parents:
diff changeset
331 public:
6725
da91efe96a93 6964458: Reimplement class meta-data storage to use native memory
coleenp
parents: 6260
diff changeset
332 unsigned int compute_hash(Symbol* name, ClassLoaderData* loader_data) {
0
a61af66fc99e Initial load
duke
parents:
diff changeset
333 unsigned int name_hash = name->identity_hash();
6725
da91efe96a93 6964458: Reimplement class meta-data storage to use native memory
coleenp
parents: 6260
diff changeset
334 // loader is null with CDS
da91efe96a93 6964458: Reimplement class meta-data storage to use native memory
coleenp
parents: 6260
diff changeset
335 assert(loader_data != NULL || UseSharedSpaces || DumpSharedSpaces,
da91efe96a93 6964458: Reimplement class meta-data storage to use native memory
coleenp
parents: 6260
diff changeset
336 "only allowed with shared spaces");
da91efe96a93 6964458: Reimplement class meta-data storage to use native memory
coleenp
parents: 6260
diff changeset
337 unsigned int loader_hash = loader_data == NULL ? 0 : loader_data->identity_hash();
0
a61af66fc99e Initial load
duke
parents:
diff changeset
338 return name_hash ^ loader_hash;
a61af66fc99e Initial load
duke
parents:
diff changeset
339 }
a61af66fc99e Initial load
duke
parents:
diff changeset
340
6725
da91efe96a93 6964458: Reimplement class meta-data storage to use native memory
coleenp
parents: 6260
diff changeset
341 int index_for(Symbol* name, ClassLoaderData* loader_data) {
da91efe96a93 6964458: Reimplement class meta-data storage to use native memory
coleenp
parents: 6260
diff changeset
342 return this->hash_to_index(compute_hash(name, loader_data));
0
a61af66fc99e Initial load
duke
parents:
diff changeset
343 }
a61af66fc99e Initial load
duke
parents:
diff changeset
344 };
1972
f95d63e2154a 6989984: Use standard include model for Hospot
stefank
parents: 1552
diff changeset
345
f95d63e2154a 6989984: Use standard include model for Hospot
stefank
parents: 1552
diff changeset
346 #endif // SHARE_VM_UTILITIES_HASHTABLE_HPP