1 /*
2 * Copyright (c) 2012, 2023, 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 #ifndef SHARE_UTILITIES_RESOURCEHASH_HPP
26 #define SHARE_UTILITIES_RESOURCEHASH_HPP
27
28 #include "memory/allocation.hpp"
29 #include "utilities/globalDefinitions.hpp"
30 #include "utilities/numberSeq.hpp"
31 #include "utilities/tableStatistics.hpp"
32
33 #include <type_traits>
34
35 template<typename K, typename V>
36 class ResourceHashtableNode : public AnyObj {
37 public:
38 unsigned _hash;
39 K _key;
40 V _value;
41 ResourceHashtableNode* _next;
42
43 ResourceHashtableNode(unsigned hash, K const& key, V const& value,
44 ResourceHashtableNode* next = nullptr) :
45 _hash(hash), _key(key), _value(value), _next(next) {}
46
47 // Create a node with a default-constructed value.
48 ResourceHashtableNode(unsigned hash, K const& key,
49 ResourceHashtableNode* next = nullptr) :
50 _hash(hash), _key(key), _value(), _next(next) {}
51 };
52
53 template<
54 class STORAGE,
55 typename K, typename V,
56 AnyObj::allocation_type ALLOC_TYPE,
57 MEMFLAGS MEM_TYPE,
58 unsigned (*HASH) (K const&),
59 bool (*EQUALS)(K const&, K const&)
60 >
61 class ResourceHashtableBase : public STORAGE {
62 static_assert(ALLOC_TYPE == AnyObj::C_HEAP || std::is_trivially_destructible<K>::value,
63 "Destructor for K is only called with C_HEAP");
64 static_assert(ALLOC_TYPE == AnyObj::C_HEAP || std::is_trivially_destructible<V>::value,
65 "Destructor for V is only called with C_HEAP");
66 using Node = ResourceHashtableNode<K, V>;
67 private:
68 int _number_of_entries;
69
70 Node** bucket_at(unsigned index) {
71 Node** t = table();
72 return &t[index];
73 }
74
75 const Node* const* bucket_at(unsigned index) const {
76 Node** t = table();
77 return &t[index];
78 }
79
80 // Returns a pointer to where the node where the value would reside if
81 // it's in the table.
82 Node** lookup_node(unsigned hash, K const& key) {
83 unsigned index = hash % table_size();
84 Node** ptr = bucket_at(index);
85 while (*ptr != nullptr) {
86 Node* node = *ptr;
87 if (node->_hash == hash && EQUALS(key, node->_key)) {
88 break;
89 }
90 ptr = &(node->_next);
91 }
92 return ptr;
93 }
94
95 Node const** lookup_node(unsigned hash, K const& key) const {
96 return const_cast<Node const**>(
97 const_cast<ResourceHashtableBase*>(this)->lookup_node(hash, key));
98 }
99
100 protected:
101 Node** table() const { return STORAGE::table(); }
102
103 ResourceHashtableBase() : STORAGE(), _number_of_entries(0) {}
104 ResourceHashtableBase(unsigned size) : STORAGE(size), _number_of_entries(0) {}
105 NONCOPYABLE(ResourceHashtableBase);
106
107 ~ResourceHashtableBase() {
108 if (ALLOC_TYPE == AnyObj::C_HEAP) {
109 Node* const* bucket = table();
110 const unsigned sz = table_size();
111 while (bucket < bucket_at(sz)) {
112 Node* node = *bucket;
113 while (node != nullptr) {
114 Node* cur = node;
115 node = node->_next;
116 delete cur;
117 }
118 ++bucket;
119 }
120 }
121 }
122
123 public:
124 unsigned table_size() const { return STORAGE::table_size(); }
125 int number_of_entries() const { return _number_of_entries; }
126
127 bool contains(K const& key) const {
128 return get(key) != nullptr;
129 }
130
131 V* get(K const& key) const {
132 unsigned hv = HASH(key);
133 Node const** ptr = lookup_node(hv, key);
134 if (*ptr != nullptr) {
135 return const_cast<V*>(&(*ptr)->_value);
136 } else {
137 return nullptr;
138 }
139 }
140
141 /**
142 * Inserts a value in the front of the table, assuming that
143 * the entry is absent.
144 * The table must be locked for the get or test that the entry
145 * is absent, and for this operation.
146 * This is a faster variant of put_if_absent because it adds to the
147 * head of the bucket, and doesn't search the bucket.
148 * @return: true: a new item is always added
149 */
150 bool put_when_absent(K const& key, V const& value) {
151 unsigned hv = HASH(key);
152 unsigned index = hv % table_size();
153 assert(*lookup_node(hv, key) == nullptr, "use put_if_absent");
154 Node** ptr = bucket_at(index);
155 if (ALLOC_TYPE == AnyObj::C_HEAP) {
156 *ptr = new (MEM_TYPE) Node(hv, key, value, *ptr);
157 } else {
158 *ptr = new Node(hv, key, value, *ptr);
159 }
160 _number_of_entries ++;
161 return true;
162 }
163
164 /**
165 * Inserts or replaces a value in the table.
166 * @return: true: if a new item is added
167 * false: if the item already existed and the value is updated
168 */
169 bool put(K const& key, V const& value) {
170 unsigned hv = HASH(key);
171 Node** ptr = lookup_node(hv, key);
172 if (*ptr != nullptr) {
173 (*ptr)->_value = value;
174 return false;
175 } else {
176 if (ALLOC_TYPE == AnyObj::C_HEAP) {
177 *ptr = new (MEM_TYPE) Node(hv, key, value);
178 } else {
179 *ptr = new Node(hv, key, value);
180 }
181 _number_of_entries ++;
182 return true;
183 }
184 }
185
186 // Look up the key.
187 // If an entry for the key exists, leave map unchanged and return a pointer to its value.
188 // If no entry for the key exists, create a new entry from key and a default-created value
189 // and return a pointer to the value.
190 // *p_created is true if entry was created, false if entry pre-existed.
191 V* put_if_absent(K const& key, bool* p_created) {
192 unsigned hv = HASH(key);
193 Node** ptr = lookup_node(hv, key);
194 if (*ptr == nullptr) {
195 if (ALLOC_TYPE == AnyObj::C_HEAP) {
196 *ptr = new (MEM_TYPE) Node(hv, key);
197 } else {
198 *ptr = new Node(hv, key);
199 }
200 *p_created = true;
201 _number_of_entries ++;
202 } else {
203 *p_created = false;
204 }
205 return &(*ptr)->_value;
206 }
207
208 // Look up the key.
209 // If an entry for the key exists, leave map unchanged and return a pointer to its value.
210 // If no entry for the key exists, create a new entry from key and value and return a
211 // pointer to the value.
212 // *p_created is true if entry was created, false if entry pre-existed.
213 V* put_if_absent(K const& key, V const& value, bool* p_created) {
214 unsigned hv = HASH(key);
215 Node** ptr = lookup_node(hv, key);
216 if (*ptr == nullptr) {
217 if (ALLOC_TYPE == AnyObj::C_HEAP) {
218 *ptr = new (MEM_TYPE) Node(hv, key, value);
219 } else {
220 *ptr = new Node(hv, key, value);
221 }
222 *p_created = true;
223 _number_of_entries ++;
224 } else {
225 *p_created = false;
226 }
227 return &(*ptr)->_value;
228 }
229
230 template<typename Function>
231 bool remove(K const& key, Function function) {
232 unsigned hv = HASH(key);
233 Node** ptr = lookup_node(hv, key);
234
235 Node* node = *ptr;
236 if (node != nullptr) {
237 *ptr = node->_next;
238 function(node->_key, node->_value);
239 if (ALLOC_TYPE == AnyObj::C_HEAP) {
240 delete node;
241 }
242 _number_of_entries --;
243 return true;
244 }
245 return false;
246 }
247
248 bool remove(K const& key) {
249 auto dummy = [&] (K& k, V& v) { };
250 return remove(key, dummy);
251 }
252
253 // ITER contains bool do_entry(K const&, V const&), which will be
254 // called for each entry in the table. If do_entry() returns false,
255 // the iteration is cancelled.
256 template<class ITER>
257 void iterate(ITER* iter) const {
258 auto function = [&] (K& k, V& v) {
259 return iter->do_entry(k, v);
260 };
261 iterate(function);
262 }
263
264 template<typename Function>
265 void iterate(Function function) const { // lambda enabled API
266 Node* const* bucket = table();
267 const unsigned sz = table_size();
268 int cnt = _number_of_entries;
269
270 while (cnt > 0 && bucket < bucket_at(sz)) {
271 Node* node = *bucket;
272 while (node != nullptr) {
273 bool cont = function(node->_key, node->_value);
274 if (!cont) { return; }
275 node = node->_next;
276 --cnt;
277 }
278 ++bucket;
279 }
280 }
281
282 // same as above, but unconditionally iterate all entries
283 template<typename Function>
284 void iterate_all(Function function) const { // lambda enabled API
285 auto wrapper = [&] (K& k, V& v) {
286 function(k, v);
287 return true;
288 };
289 iterate(wrapper);
290 }
291
292 // ITER contains bool do_entry(K const&, V const&), which will be
293 // called for each entry in the table. If do_entry() returns true,
294 // the entry is deleted.
295 template<class ITER>
296 void unlink(ITER* iter) {
297 const unsigned sz = table_size();
298 for (unsigned index = 0; index < sz; index++) {
299 Node** ptr = bucket_at(index);
300 while (*ptr != nullptr) {
301 Node* node = *ptr;
302 // do_entry must clean up the key and value in Node.
303 bool clean = iter->do_entry(node->_key, node->_value);
304 if (clean) {
305 *ptr = node->_next;
306 if (ALLOC_TYPE == AnyObj::C_HEAP) {
307 delete node;
308 }
309 _number_of_entries --;
310 } else {
311 ptr = &(node->_next);
312 }
313 }
314 }
315 }
316
317 template<typename Function>
318 TableStatistics statistics_calculate(Function size_function) const {
319 NumberSeq summary;
320 size_t literal_bytes = 0;
321 Node* const* bucket = table();
322 const unsigned sz = table_size();
323 while (bucket < bucket_at(sz)) {
324 Node* node = *bucket;
325 int count = 0;
326 while (node != nullptr) {
327 literal_bytes += size_function(node->_key, node->_value);
328 count++;
329 node = node->_next;
330 }
331 summary.add((double)count);
332 ++bucket;
333 }
334 return TableStatistics(summary, literal_bytes, sizeof(Node*), sizeof(Node));
335 }
336
337 // This method calculates the "shallow" size. If you want the recursive size, use statistics_calculate.
338 size_t mem_size() const {
339 return sizeof(*this) +
340 table_size() * sizeof(Node*) +
341 number_of_entries() * sizeof(Node);
342 }
343 };
344
345 template<unsigned TABLE_SIZE, typename K, typename V>
346 class FixedResourceHashtableStorage : public AnyObj {
347 using Node = ResourceHashtableNode<K, V>;
348
349 Node* _table[TABLE_SIZE];
350 protected:
351 FixedResourceHashtableStorage() { memset(_table, 0, sizeof(_table)); }
352 ~FixedResourceHashtableStorage() = default;
353
354 constexpr unsigned table_size() const {
355 return TABLE_SIZE;
356 }
357
358 Node** table() const {
359 return const_cast<Node**>(_table);
360 }
361 };
362
363 template<
364 typename K, typename V,
365 unsigned SIZE = 256,
366 AnyObj::allocation_type ALLOC_TYPE = AnyObj::RESOURCE_AREA,
367 MEMFLAGS MEM_TYPE = mtInternal,
368 unsigned (*HASH) (K const&) = primitive_hash<K>,
369 bool (*EQUALS)(K const&, K const&) = primitive_equals<K>
370 >
371 class ResourceHashtable : public ResourceHashtableBase<
372 FixedResourceHashtableStorage<SIZE, K, V>,
373 K, V, ALLOC_TYPE, MEM_TYPE, HASH, EQUALS> {
374 NONCOPYABLE(ResourceHashtable);
375 public:
376 ResourceHashtable() : ResourceHashtableBase<FixedResourceHashtableStorage<SIZE, K, V>,
377 K, V, ALLOC_TYPE, MEM_TYPE, HASH, EQUALS>() {}
378 };
379
380 #endif // SHARE_UTILITIES_RESOURCEHASH_HPP