1 /*
  2  * Copyright (c) 2016, 2019, 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_JFR_UTILITIES_JFRHASHTABLE_HPP
 26 #define SHARE_JFR_UTILITIES_JFRHASHTABLE_HPP
 27 
 28 #include "memory/allocation.inline.hpp"
 29 #include "runtime/orderAccess.hpp"
 30 #include "utilities/debug.hpp"
 31 #include "utilities/macros.hpp"
 32 
 33 template <typename T>
 34 class JfrBasicHashtableEntry {
 35  private:
 36   typedef JfrBasicHashtableEntry<T> Entry;
 37   Entry* _next;
 38   T _literal;          // ref to item in table.
 39   uintptr_t _hash;
 40 
 41  public:
 42   uintptr_t hash() const { return _hash; }
 43   void set_hash(uintptr_t hash) { _hash = hash; }
 44   T literal() const { return _literal; }
 45   T* literal_addr() { return &_literal; }
 46   void set_literal(T s) { _literal = s; }
 47   void set_next(Entry* next) { _next = next; }
 48   Entry* next() const { return _next; }
 49   Entry** next_addr() { return &_next; }
 50 };
 51 
 52 template <typename T>
 53 class JfrHashtableBucket : public CHeapObj<mtTracing> {
 54   template <typename>
 55   friend class JfrBasicHashtable;
 56  private:
 57   typedef JfrBasicHashtableEntry<T> TableEntry;
 58   TableEntry* _entry;
 59 
 60   TableEntry* get_entry() const {
 61     return (TableEntry*)OrderAccess::load_acquire(&_entry);
 62   }
 63   void set_entry(TableEntry* entry) { OrderAccess::release_store(&_entry, entry);}
 64   TableEntry** entry_addr() { return &_entry; }
 65 };
 66 
 67 template <typename T>
 68 class JfrBasicHashtable : public CHeapObj<mtTracing> {
 69  private:
 70   typedef JfrHashtableBucket<T> Bucket;
 71   typedef JfrBasicHashtableEntry<T> TableEntry;
 72   Bucket* _buckets;
 73   uintptr_t _table_size;
 74   const size_t _entry_size;
 75   size_t _number_of_entries;
 76 
 77  protected:
 78   JfrBasicHashtable(uintptr_t table_size, size_t entry_size) :
 79     _buckets(NULL), _table_size(table_size), _entry_size(entry_size), _number_of_entries(0) {
 80     _buckets = NEW_C_HEAP_ARRAY2(Bucket, table_size, mtTracing, CURRENT_PC);
 81     memset((void*)_buckets, 0, table_size * sizeof(Bucket));
 82   }
 83 
 84   size_t hash_to_index(uintptr_t full_hash) const {
 85     const uintptr_t h = full_hash % _table_size;
 86     assert(h >= 0 && h < _table_size, "Illegal hash value");
 87     return (size_t)h;
 88   }
 89   size_t entry_size() const { return _entry_size; }
 90   void unlink_entry(TableEntry* entry) {
 91     entry->set_next(NULL);
 92     --_number_of_entries;
 93   }
 94   void free_buckets() {
 95     if (NULL != _buckets) {
 96       FREE_C_HEAP_ARRAY(Bucket, _buckets);
 97       _buckets = NULL;
 98     }
 99   }
100   TableEntry* bucket(size_t i) { return _buckets[i].get_entry();}
101   TableEntry** bucket_addr(size_t i) { return _buckets[i].entry_addr(); }
102   uintptr_t table_size() const { return _table_size; }
103   size_t number_of_entries() const { return _number_of_entries; }
104   void add_entry(size_t index, TableEntry* entry) {
105     assert(entry != NULL, "invariant");
106     entry->set_next(bucket(index));
107     _buckets[index].set_entry(entry);
108     ++_number_of_entries;
109   }
110 };
111 
112 template <typename IdType, typename Entry, typename T>
113 class AscendingId : public CHeapObj<mtTracing>  {
114  private:
115   IdType _id;
116  public:
117   AscendingId() : _id(0) {}
118   // callbacks
119   void assign_id(Entry* entry) {
120     assert(entry != NULL, "invariant");
121     assert(entry->id() == 0, "invariant");
122     entry->set_id(++_id);
123   }
124   bool equals(const T& data, uintptr_t hash, const Entry* entry) {
125     assert(entry->hash() == hash, "invariant");
126     return true;
127   }
128 };
129 
130 // IdType must be scalar
131 template <typename T, typename IdType>
132 class Entry : public JfrBasicHashtableEntry<T> {
133  public:
134   typedef IdType ID;
135   void init() { _id = 0; }
136   ID id() const { return _id; }
137   void set_id(ID id) { _id = id; }
138   void set_value(const T& value) { this->set_literal(value); }
139   T& value() const { return *const_cast<Entry*>(this)->literal_addr();}
140   const T* value_addr() const { return const_cast<Entry*>(this)->literal_addr(); }
141 
142  private:
143   ID _id;
144 };
145 
146 template <typename T, typename IdType, template <typename, typename> class Entry,
147           typename Callback = AscendingId<IdType, Entry<T, IdType>, T> ,
148           size_t TABLE_SIZE = 1009>
149 class HashTableHost : public JfrBasicHashtable<T> {
150  public:
151   typedef Entry<T, IdType> HashEntry;
152   HashTableHost() : _callback(new Callback()) {}
153   HashTableHost(Callback* cb) : JfrBasicHashtable<T>(TABLE_SIZE, sizeof(HashEntry)), _callback(cb) {}
154   ~HashTableHost() {
155     this->clear_entries();
156     this->free_buckets();
157   }
158 
159   // direct insert assumes non-existing entry
160   HashEntry& put(const T& data, uintptr_t hash);
161 
162   // lookup entry, will put if not found
163   HashEntry& lookup_put(const T& data, uintptr_t hash) {
164     HashEntry* entry = lookup_only(data, hash);
165     return entry == NULL ? put(data, hash) : *entry;
166   }
167 
168   // read-only lookup
169   HashEntry* lookup_only(const T& query, uintptr_t hash);
170 
171   // id retrieval
172   IdType id(const T& data, uintptr_t hash) {
173     assert(data != NULL, "invariant");
174     const HashEntry& entry = lookup_put(data, hash);
175     assert(entry.id() > 0, "invariant");
176     return entry.id();
177   }
178 
179   template <typename Functor>
180   void iterate_value(Functor& f);
181 
182   template <typename Functor>
183   void iterate_entry(Functor& f);
184 
185   size_t cardinality() const { return this->number_of_entries(); }
186   bool has_entries() const { return this->cardinality() > 0; }
187   void clear_entries();
188 
189   // removal and deallocation
190   void free_entry(HashEntry* entry) {
191     assert(entry != NULL, "invariant");
192     JfrBasicHashtable<T>::unlink_entry(entry);
193     FREE_C_HEAP_ARRAY(char, entry);
194   }
195 
196  private:
197   Callback* _callback;
198   size_t index_for(uintptr_t hash) { return this->hash_to_index(hash); }
199   HashEntry* new_entry(const T& data, uintptr_t hash);
200   void add_entry(size_t index, HashEntry* new_entry) {
201     assert(new_entry != NULL, "invariant");
202     _callback->assign_id(new_entry);
203     assert(new_entry->id() > 0, "invariant");
204     JfrBasicHashtable<T>::add_entry(index, new_entry);
205   }
206 };
207 
208 template <typename T, typename IdType, template <typename, typename> class Entry, typename Callback, size_t TABLE_SIZE>
209 Entry<T, IdType>& HashTableHost<T, IdType, Entry, Callback, TABLE_SIZE>::put(const T& data, uintptr_t hash) {
210   assert(lookup_only(data, hash) == NULL, "use lookup_put()");
211   HashEntry* const entry = new_entry(data, hash);
212   add_entry(index_for(hash), entry);
213   return *entry;
214 }
215 
216 template <typename T, typename IdType, template <typename, typename> class Entry, typename Callback, size_t TABLE_SIZE>
217 Entry<T, IdType>* HashTableHost<T, IdType, Entry, Callback, TABLE_SIZE>::lookup_only(const T& query, uintptr_t hash) {
218   HashEntry* entry = (HashEntry*)this->bucket(index_for(hash));
219   while (entry != NULL) {
220     if (entry->hash() == hash && _callback->equals(query, hash, entry)) {
221       return entry;
222     }
223     entry = (HashEntry*)entry->next();
224   }
225   return NULL;
226 }
227 
228 template <typename T, typename IdType, template <typename, typename> class Entry, typename Callback, size_t TABLE_SIZE>
229 template <typename Functor>
230 void HashTableHost<T, IdType, Entry, Callback, TABLE_SIZE>::iterate_value(Functor& f) {
231   for (size_t i = 0; i < this->table_size(); ++i) {
232     const HashEntry* entry = (const HashEntry*)this->bucket(i);
233     while (entry != NULL) {
234       if (!f(entry->value())) {
235         break;
236       }
237       entry = (HashEntry*)entry->next();
238     }
239   }
240 }
241 
242 template <typename T, typename IdType, template <typename, typename> class Entry, typename Callback, size_t TABLE_SIZE>
243 template <typename Functor>
244 void HashTableHost<T, IdType, Entry, Callback, TABLE_SIZE>::iterate_entry(Functor& f) {
245   for (size_t i = 0; i < this->table_size(); ++i) {
246     const HashEntry* entry = (const HashEntry*)this->bucket(i);
247     while (entry != NULL) {
248       if (!f(entry)) {
249         break;
250       }
251       entry = (const HashEntry*)entry->next();
252     }
253   }
254 }
255 
256 template <typename T, typename IdType, template <typename, typename> class Entry, typename Callback, size_t TABLE_SIZE>
257 void HashTableHost<T, IdType, Entry, Callback, TABLE_SIZE>::clear_entries() {
258   for (size_t i = 0; i < this->table_size(); ++i) {
259     HashEntry** bucket = (HashEntry**)this->bucket_addr(i);
260     HashEntry* entry = *bucket;
261     while (entry != NULL) {
262       HashEntry* entry_to_remove = entry;
263       entry = (HashEntry*)entry->next();
264       this->free_entry(entry_to_remove);
265     }
266     *bucket = NULL;
267   }
268   assert(this->number_of_entries() == 0, "should have removed all entries");
269 }
270 
271 template <typename T, typename IdType, template <typename, typename> class Entry, typename Callback, size_t TABLE_SIZE>
272 Entry<T, IdType>* HashTableHost<T, IdType, Entry, Callback, TABLE_SIZE>::new_entry(const T& data, uintptr_t hash) {
273   assert(sizeof(HashEntry) == this->entry_size(), "invariant");
274   HashEntry* const entry = (HashEntry*) NEW_C_HEAP_ARRAY2(char, this->entry_size(), mtTracing, CURRENT_PC);
275   entry->init();
276   entry->set_hash(hash);
277   entry->set_value(data);
278   entry->set_next(NULL);
279   assert(0 == entry->id(), "invariant");
280   return entry;
281 }
282 
283 #endif // SHARE_JFR_UTILITIES_JFRHASHTABLE_HPP