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 unlink_all();
110 }
111 }
112
113 public:
114 unsigned table_size() const { return STORAGE::table_size(); }
115 int number_of_entries() const { return _number_of_entries; }
116
117 bool contains(K const& key) const {
118 return get(key) != nullptr;
119 }
120
121 V* get(K const& key) const {
122 unsigned hv = HASH(key);
123 Node const** ptr = lookup_node(hv, key);
124 if (*ptr != nullptr) {
125 return const_cast<V*>(&(*ptr)->_value);
126 } else {
127 return nullptr;
128 }
129 }
130
131 /**
132 * Inserts a value in the front of the table, assuming that
133 * the entry is absent.
134 * The table must be locked for the get or test that the entry
135 * is absent, and for this operation.
136 * This is a faster variant of put_if_absent because it adds to the
137 * head of the bucket, and doesn't search the bucket.
138 * @return: true: a new item is always added
139 */
140 bool put_when_absent(K const& key, V const& value) {
141 unsigned hv = HASH(key);
142 unsigned index = hv % table_size();
143 assert(*lookup_node(hv, key) == nullptr, "use put_if_absent");
144 Node** ptr = bucket_at(index);
145 if (ALLOC_TYPE == AnyObj::C_HEAP) {
146 *ptr = new (MEM_TYPE) Node(hv, key, value, *ptr);
147 } else {
148 *ptr = new Node(hv, key, value, *ptr);
149 }
150 _number_of_entries ++;
151 return true;
152 }
153
154 /**
155 * Inserts or replaces a value in the table.
156 * @return: true: if a new item is added
157 * false: if the item already existed and the value is updated
158 */
159 bool put(K const& key, V const& value) {
160 unsigned hv = HASH(key);
161 Node** ptr = lookup_node(hv, key);
162 if (*ptr != nullptr) {
163 (*ptr)->_value = value;
164 return false;
165 } else {
166 if (ALLOC_TYPE == AnyObj::C_HEAP) {
167 *ptr = new (MEM_TYPE) Node(hv, key, value);
168 } else {
169 *ptr = new Node(hv, key, value);
170 }
171 _number_of_entries ++;
172 return true;
173 }
174 }
175
176 // Look up the key.
177 // If an entry for the key exists, leave map unchanged and return a pointer to its value.
178 // If no entry for the key exists, create a new entry from key and a default-created value
179 // and return a pointer to the value.
180 // *p_created is true if entry was created, false if entry pre-existed.
181 V* put_if_absent(K const& key, bool* p_created) {
182 unsigned hv = HASH(key);
183 Node** ptr = lookup_node(hv, key);
184 if (*ptr == nullptr) {
185 if (ALLOC_TYPE == AnyObj::C_HEAP) {
186 *ptr = new (MEM_TYPE) Node(hv, key);
187 } else {
188 *ptr = new Node(hv, key);
189 }
190 *p_created = true;
191 _number_of_entries ++;
192 } else {
193 *p_created = false;
194 }
195 return &(*ptr)->_value;
196 }
197
198 // Look up the key.
199 // If an entry for the key exists, leave map unchanged and return a pointer to its value.
200 // If no entry for the key exists, create a new entry from key and value and return a
201 // pointer to the value.
202 // *p_created is true if entry was created, false if entry pre-existed.
203 V* put_if_absent(K const& key, V const& value, bool* p_created) {
204 unsigned hv = HASH(key);
205 Node** ptr = lookup_node(hv, key);
206 if (*ptr == nullptr) {
207 if (ALLOC_TYPE == AnyObj::C_HEAP) {
208 *ptr = new (MEM_TYPE) Node(hv, key, value);
209 } else {
210 *ptr = new Node(hv, key, value);
211 }
212 *p_created = true;
213 _number_of_entries ++;
214 } else {
215 *p_created = false;
216 }
217 return &(*ptr)->_value;
218 }
219
220 template<typename Function>
221 bool remove(K const& key, Function function) {
222 unsigned hv = HASH(key);
223 Node** ptr = lookup_node(hv, key);
224
225 Node* node = *ptr;
226 if (node != nullptr) {
227 *ptr = node->_next;
228 function(node->_key, node->_value);
229 if (ALLOC_TYPE == AnyObj::C_HEAP) {
230 delete node;
231 }
232 _number_of_entries --;
233 return true;
234 }
235 return false;
236 }
237
238 bool remove(K const& key) {
239 auto dummy = [&] (K& k, V& v) { };
240 return remove(key, dummy);
241 }
242
243 // ITER contains bool do_entry(K const&, V const&), which will be
244 // called for each entry in the table. If do_entry() returns false,
245 // the iteration is cancelled.
246 template<class ITER>
247 void iterate(ITER* iter) const {
248 auto function = [&] (K& k, V& v) {
249 return iter->do_entry(k, v);
250 };
251 iterate(function);
252 }
253
254 template<typename Function>
255 void iterate(Function function) const { // lambda enabled API
256 Node* const* bucket = table();
257 const unsigned sz = table_size();
258 int cnt = _number_of_entries;
259
260 while (cnt > 0 && bucket < bucket_at(sz)) {
261 Node* node = *bucket;
262 while (node != nullptr) {
263 bool cont = function(node->_key, node->_value);
264 if (!cont) { return; }
265 node = node->_next;
266 --cnt;
267 }
268 ++bucket;
269 }
270 }
271
272 // same as above, but unconditionally iterate all entries
273 template<typename Function>
274 void iterate_all(Function function) const { // lambda enabled API
275 auto wrapper = [&] (K& k, V& v) {
276 function(k, v);
277 return true;
278 };
279 iterate(wrapper);
280 }
281
282 // ITER contains bool do_entry(K const&, V const&), which will be
283 // called for each entry in the table. If do_entry() returns true,
284 // the entry is deleted.
285 template<class ITER>
286 void unlink(ITER* iter) {
287 const unsigned sz = table_size();
288 int cnt = _number_of_entries;
289
290 for (unsigned index = 0; cnt > 0 && index < sz; ++index) {
291 Node** ptr = bucket_at(index);
292
293 while (*ptr != nullptr) {
294 Node* node = *ptr;
295 // do_entry must clean up the key and value in Node.
296 bool clean = iter->do_entry(node->_key, node->_value);
297 if (clean) {
298 *ptr = node->_next;
299 if (ALLOC_TYPE == AnyObj::C_HEAP) {
300 delete node;
301 }
302 _number_of_entries --;
303 } else {
304 ptr = &(node->_next);
305 }
306 if (--cnt <= 0) return;
307 }
308 }
309 }
310
311 // unlink_all() is a specialized version of unlink() when we decide to remove all elements.
312 // It can not replace unlink(ITER* iter) if user-provided iter releases key/value
313 void unlink_all() {
314 Node** bucket = table();
315 const unsigned sz = table_size();
316
317 while (_number_of_entries > 0 && bucket < bucket_at(sz)) {
318 Node* node = *bucket;
319 int n = 0;
320
321 while (node != NULL) {
322 Node* cur = node;
323 node = node->_next;
324 if (ALLOC_TYPE == AnyObj::C_HEAP) {
325 delete cur;
326 }
327 n++;
328 }
329
330 if (n > 0) {
331 *bucket = nullptr;
332 _number_of_entries -= n;
333 }
334 bucket++;
335 }
336
337 assert(_number_of_entries == 0, "sanity check");
338 }
339
340 template<typename Function>
341 TableStatistics statistics_calculate(Function size_function) const {
342 NumberSeq summary;
343 size_t literal_bytes = 0;
344 Node* const* bucket = table();
345 const unsigned sz = table_size();
346 while (bucket < bucket_at(sz)) {
347 Node* node = *bucket;
348 int count = 0;
349 while (node != nullptr) {
350 literal_bytes += size_function(node->_key, node->_value);
351 count++;
352 node = node->_next;
353 }
354 summary.add((double)count);
355 ++bucket;
356 }
357 return TableStatistics(summary, literal_bytes, sizeof(Node*), sizeof(Node));
358 }
359
360 // This method calculates the "shallow" size. If you want the recursive size, use statistics_calculate.
361 size_t mem_size() const {
362 return sizeof(*this) +
363 table_size() * sizeof(Node*) +
364 number_of_entries() * sizeof(Node);
365 }
366 };
367
368 template<unsigned TABLE_SIZE, typename K, typename V>
369 class FixedResourceHashtableStorage : public AnyObj {
370 using Node = ResourceHashtableNode<K, V>;
371
372 Node* _table[TABLE_SIZE];
373 protected:
374 FixedResourceHashtableStorage() { memset(_table, 0, sizeof(_table)); }
375 ~FixedResourceHashtableStorage() = default;
376
377 constexpr unsigned table_size() const {
378 return TABLE_SIZE;
379 }
380
381 Node** table() const {
382 return const_cast<Node**>(_table);
383 }
384 };
385
386 template<
387 typename K, typename V,
388 unsigned SIZE = 256,
389 AnyObj::allocation_type ALLOC_TYPE = AnyObj::RESOURCE_AREA,
390 MEMFLAGS MEM_TYPE = mtInternal,
391 unsigned (*HASH) (K const&) = primitive_hash<K>,
392 bool (*EQUALS)(K const&, K const&) = primitive_equals<K>
393 >
394 class ResourceHashtable : public ResourceHashtableBase<
395 FixedResourceHashtableStorage<SIZE, K, V>,
396 K, V, ALLOC_TYPE, MEM_TYPE, HASH, EQUALS> {
397 NONCOPYABLE(ResourceHashtable);
398 public:
399 ResourceHashtable() : ResourceHashtableBase<FixedResourceHashtableStorage<SIZE, K, V>,
400 K, V, ALLOC_TYPE, MEM_TYPE, HASH, EQUALS>() {}
401 };
402
403 #endif // SHARE_UTILITIES_RESOURCEHASH_HPP