/*

 * Copyright (c) 2016, 2019, Oracle and/or its affiliates. All rights reserved.

 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.

 *

 * This code is free software; you can redistribute it and/or modify it

 * under the terms of the GNU General Public License version 2 only, as

 * published by the Free Software Foundation.

 *

 * This code is distributed in the hope that it will be useful, but WITHOUT

 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or

 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License

 * version 2 for more details (a copy is included in the LICENSE file that

 * accompanied this code).

 *

 * You should have received a copy of the GNU General Public License version

 * 2 along with this work; if not, write to the Free Software Foundation,

 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.

 *

 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA

 * or visit www.oracle.com if you need additional information or have any

 * questions.

 *

 */

#ifndef SHARE_JFR_UTILITIES_JFRHASHTABLE_HPP

#define SHARE_JFR_UTILITIES_JFRHASHTABLE_HPP

#include "jfr/utilities/jfrAllocation.hpp"

#include "utilities/debug.hpp"

#include "utilities/macros.hpp"

template <typename T>

class JfrBasicHashtableEntry : public JfrCHeapObj {

 private:

  typedef JfrBasicHashtableEntry<T> Entry;

  Entry* _next;

  T _literal;          // ref to item in table.

  uintptr_t _hash;

 public:

  JfrBasicHashtableEntry(uintptr_t hash, const T& data) : _next(NULL), _literal(data), _hash(hash) {}

  uintptr_t hash() const { return _hash; }

  T literal() const { return _literal; }

  T* literal_addr() { return &_literal; }

  void set_literal(T s) { _literal = s; }

  void set_next(Entry* next) { _next = next; }

  Entry* next() const { return _next; }

  Entry** next_addr() { return &_next; }

};

template <typename T>

class JfrHashtableBucket : public CHeapObj<mtTracing> {

  template <typename>

  friend class JfrBasicHashtable;

 private:

  typedef JfrBasicHashtableEntry<T> TableEntry;

  TableEntry* _entry;

  TableEntry* get_entry() const {

    return (TableEntry*)Atomic::load_acquire(&_entry);

  }

  void set_entry(TableEntry* entry) { Atomic::release_store(&_entry, entry);}

  TableEntry** entry_addr() { return &_entry; }

};

template <typename T>

class JfrBasicHashtable : public CHeapObj<mtTracing> {

 private:

  typedef JfrHashtableBucket<T> Bucket;

  typedef JfrBasicHashtableEntry<T> TableEntry;

  Bucket* _buckets;

  uintptr_t _table_size;

  const size_t _entry_size;

  size_t _number_of_entries;

 protected:

  JfrBasicHashtable(uintptr_t table_size, size_t entry_size) :

    _buckets(NULL), _table_size(table_size), _entry_size(entry_size), _number_of_entries(0) {

    _buckets = NEW_C_HEAP_ARRAY2(Bucket, table_size, mtTracing, CURRENT_PC);

    memset((void*)_buckets, 0, table_size * sizeof(Bucket));

  }

  size_t hash_to_index(uintptr_t full_hash) const {

    const uintptr_t h = full_hash % _table_size;

    assert(h >= 0 && h < _table_size, "Illegal hash value");

    return (size_t)h;

  }

  size_t entry_size() const { return _entry_size; }

  void unlink_entry(TableEntry* entry) {

    entry->set_next(NULL);

    --_number_of_entries;

  }

  void free_buckets() {

    FREE_C_HEAP_ARRAY(Bucket, _buckets);

  }

  TableEntry* bucket(size_t i) { return _buckets[i].get_entry();}

  TableEntry** bucket_addr(size_t i) { return _buckets[i].entry_addr(); }

  uintptr_t table_size() const { return _table_size; }

  size_t number_of_entries() const { return _number_of_entries; }

  void add_entry(size_t index, TableEntry* entry) {

    assert(entry != NULL, "invariant");

    entry->set_next(bucket(index));

    _buckets[index].set_entry(entry);

    ++_number_of_entries;

  }

};

template <typename IdType, typename Entry, typename T>

class AscendingId : public JfrCHeapObj  {

 private:

  IdType _id;

 public:

  AscendingId() : _id(0) {}

  // callbacks

  void on_link(Entry* entry) {

    assert(entry != NULL, "invariant");

    assert(entry->id() == 0, "invariant");

    entry->set_id(++_id);

  }

  bool on_equals(uintptr_t hash, const Entry* entry) {

    assert(entry->hash() == hash, "invariant");

    return true;

  }

};

// IdType must be scalar

template <typename T, typename IdType>

class JfrHashtableEntry : public JfrBasicHashtableEntry<T> {

 public:

  JfrHashtableEntry(uintptr_t hash, const T& data) : JfrBasicHashtableEntry<T>(hash, data), _id(0) {}

  typedef IdType ID;

  ID id() const { return _id; }

  void set_id(ID id) const { _id = id; }

  T& value() const { return *const_cast<JfrHashtableEntry*>(this)->literal_addr();}

  const T* value_addr() const { return const_cast<JfrHashtableEntry*>(this)->literal_addr(); }

 private:

  mutable ID _id;

};

template <typename T, typename IdType, template <typename, typename> class Entry,

          typename Callback = AscendingId<IdType, Entry<T, IdType>, T> ,

          size_t TABLE_SIZE = 1009>

class HashTableHost : public JfrBasicHashtable<T> {

 public:

  typedef Entry<T, IdType> HashEntry;

  HashTableHost(size_t size = 0) : JfrBasicHashtable<T>(size == 0 ? TABLE_SIZE : size, sizeof(HashEntry)), _callback(new Callback()) {}

  HashTableHost(Callback* cb, size_t size = 0) : JfrBasicHashtable<T>(size == 0 ? TABLE_SIZE : size, sizeof(HashEntry)), _callback(cb) {}

  ~HashTableHost() {

    this->clear_entries();

    this->free_buckets();

  }

  // direct insert assumes non-existing entry

  HashEntry& put(uintptr_t hash, const T& data);

  // lookup entry, will put if not found

  HashEntry& lookup_put(uintptr_t hash, const T& data) {

    HashEntry* entry = lookup_only(hash);

    return entry == NULL ? put(hash, data) : *entry;

  }

  HashEntry* lookup_only(uintptr_t hash);

  // id retrieval

  IdType id(uintptr_t hash, const T& data) {

    assert(data != NULL, "invariant");

    const HashEntry& entry = lookup_put(hash, data);

    assert(entry.id() > 0, "invariant");

    return entry.id();

  }

  template <typename Functor>

  void iterate_value(Functor& f);

  template <typename Functor>

  void iterate_entry(Functor& f);

  size_t cardinality() const { return this->number_of_entries(); }

  bool has_entries() const { return this->cardinality() > 0; }

  void clear_entries();

  // removal and deallocation

  void free_entry(HashEntry* entry) {

    assert(entry != NULL, "invariant");

    JfrBasicHashtable<T>::unlink_entry(entry);

    _callback->on_unlink(entry);

    delete entry;

  }

 private:

  Callback* _callback;

  size_t index_for(uintptr_t hash) { return this->hash_to_index(hash); }

  HashEntry* new_entry(uintptr_t hash, const T& data);

  void add_entry(size_t index, HashEntry* new_entry) {

    assert(new_entry != NULL, "invariant");

    _callback->on_link(new_entry);

    assert(new_entry->id() > 0, "invariant");

    JfrBasicHashtable<T>::add_entry(index, new_entry);

  }

};

template <typename T, typename IdType, template <typename, typename> class Entry, typename Callback, size_t TABLE_SIZE>

Entry<T, IdType>& HashTableHost<T, IdType, Entry, Callback, TABLE_SIZE>::put(uintptr_t hash, const T& data) {

  assert(lookup_only(hash) == NULL, "use lookup_put()");

  HashEntry* const entry = new_entry(hash, data);

  add_entry(index_for(hash), entry);

  return *entry;

}

template <typename T, typename IdType, template <typename, typename> class Entry, typename Callback, size_t TABLE_SIZE>

Entry<T, IdType>* HashTableHost<T, IdType, Entry, Callback, TABLE_SIZE>::lookup_only(uintptr_t hash) {

  HashEntry* entry = (HashEntry*)this->bucket(index_for(hash));

  while (entry != NULL) {

    if (entry->hash() == hash && _callback->on_equals(hash, entry)) {

      return entry;

    }

    entry = (HashEntry*)entry->next();

  }

  return NULL;

}

template <typename T, typename IdType, template <typename, typename> class Entry, typename Callback, size_t TABLE_SIZE>

template <typename Functor>

void HashTableHost<T, IdType, Entry, Callback, TABLE_SIZE>::iterate_value(Functor& f) {

  for (size_t i = 0; i < this->table_size(); ++i) {

    const HashEntry* entry = (const HashEntry*)this->bucket(i);

    while (entry != NULL) {

      if (!f(entry->value())) {

        break;

      }

      entry = (HashEntry*)entry->next();

    }

  }

}

template <typename T, typename IdType, template <typename, typename> class Entry, typename Callback, size_t TABLE_SIZE>

template <typename Functor>

void HashTableHost<T, IdType, Entry, Callback, TABLE_SIZE>::iterate_entry(Functor& f) {

  for (size_t i = 0; i < this->table_size(); ++i) {

    const HashEntry* entry = (const HashEntry*)this->bucket(i);

    while (entry != NULL) {

      if (!f(entry)) {

        break;

      }

      entry = (const HashEntry*)entry->next();

    }

  }

}

template <typename T, typename IdType, template <typename, typename> class Entry, typename Callback, size_t TABLE_SIZE>

void HashTableHost<T, IdType, Entry, Callback, TABLE_SIZE>::clear_entries() {

  for (size_t i = 0; i < this->table_size(); ++i) {

    HashEntry** bucket = (HashEntry**)this->bucket_addr(i);

    HashEntry* entry = *bucket;

    while (entry != NULL) {

      HashEntry* entry_to_remove = entry;

      entry = (HashEntry*)entry->next();

      this->free_entry(entry_to_remove);

    }

    *bucket = NULL;

  }

  assert(this->number_of_entries() == 0, "should have removed all entries");

}

template <typename T, typename IdType, template <typename, typename> class Entry, typename Callback, size_t TABLE_SIZE>

Entry<T, IdType>* HashTableHost<T, IdType, Entry, Callback, TABLE_SIZE>::new_entry(uintptr_t hash, const T& data) {

  assert(sizeof(HashEntry) == this->entry_size(), "invariant");

  HashEntry* const entry = new HashEntry(hash, data);

  assert(entry != NULL, "invariant");

  assert(0 == entry->id(), "invariant");

  return entry;

}

#endif // SHARE_JFR_UTILITIES_JFRHASHTABLE_HPP