1 /*

     2  * Copyright (c) 2016, 2018, 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_VM_JFR_UTILITIES_JFRHASHTABLE_HPP

    26 #define SHARE_VM_JFR_UTILITIES_JFRHASHTABLE_HPP

    27 

    28 #include "memory/allocation.inline.hpp"

    29 #include "runtime/orderAccess.inline.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_VM_JFR_UTILITIES_JFRHASHTABLE_HPP