/*

 * Copyright (c) 2012, 2015 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_VM_UTILITIES_RESOURCEHASH_HPP

#define SHARE_VM_UTILITIES_RESOURCEHASH_HPP

#include "memory/allocation.hpp"

#include "utilities/top.hpp"

template<typename K> struct ResourceHashtableFns {

    typedef unsigned (*hash_fn)(K const&);

    typedef bool (*equals_fn)(K const&, K const&);

};

template<typename K> unsigned primitive_hash(const K& k) {

  unsigned hash = (unsigned)((uintptr_t)k);

  return hash ^ (hash >> 3); // just in case we're dealing with aligned ptrs

}

template<typename K> bool primitive_equals(const K& k0, const K& k1) {

  return k0 == k1;

}

template<

    typename K, typename V,

    // xlC does not compile this:

    // http://stackoverflow.com/questions/8532961/template-argument-of-type-that-is-defined-by-inner-typedef-from-other-template-c

    //typename ResourceHashtableFns<K>::hash_fn   HASH   = primitive_hash<K>,

    //typename ResourceHashtableFns<K>::equals_fn EQUALS = primitive_equals<K>,

    unsigned (*HASH)  (K const&)           = primitive_hash<K>,

    bool     (*EQUALS)(K const&, K const&) = primitive_equals<K>,

    unsigned SIZE = 256,

    ResourceObj::allocation_type ALLOC_TYPE = ResourceObj::RESOURCE_AREA,

    MEMFLAGS MEM_TYPE = mtInternal

    >

class ResourceHashtable : public ResourceObj {

 private:

  class Node : public ResourceObj {

   public:

    unsigned _hash;

    K _key;

    V _value;

    Node* _next;

    Node(unsigned hash, K const& key, V const& value) :

        _hash(hash), _key(key), _value(value), _next(NULL) {}

  };

  Node* _table[SIZE];

  // Returns a pointer to where the node where the value would reside if

  // it's in the table.

  Node** lookup_node(unsigned hash, K const& key) {

    unsigned index = hash % SIZE;

    Node** ptr = &_table[index];

    while (*ptr != NULL) {

      Node* node = *ptr;

      if (node->_hash == hash && EQUALS(key, node->_key)) {

        break;

      }

      ptr = &(node->_next);

    }

    return ptr;

  }

  Node const** lookup_node(unsigned hash, K const& key) const {

    return const_cast<Node const**>(

        const_cast<ResourceHashtable*>(this)->lookup_node(hash, key));

  }

 public:

  ResourceHashtable() { memset(_table, 0, SIZE * sizeof(Node*)); }

  ~ResourceHashtable() {

    if (ALLOC_TYPE == C_HEAP) {

      Node* const* bucket = _table;

      while (bucket < &_table[SIZE]) {

        Node* node = *bucket;

        while (node != NULL) {

          Node* cur = node;

          node = node->_next;

          delete cur;

        }

        ++bucket;

      }

    }

  }

  bool contains(K const& key) const {

    return get(key) != NULL;

  }

  V* get(K const& key) const {

    unsigned hv = HASH(key);

    Node const** ptr = lookup_node(hv, key);

    if (*ptr != NULL) {

      return const_cast<V*>(&(*ptr)->_value);

    } else {

      return NULL;

    }

  }

 /**

  * Inserts or replaces a value in the table.

  * @return: true:  if a new item is added

  *          false: if the item already existed and the value is updated

  */

  bool put(K const& key, V const& value) {

    unsigned hv = HASH(key);

    Node** ptr = lookup_node(hv, key);

    if (*ptr != NULL) {

      (*ptr)->_value = value;

      return false;

    } else {

      *ptr = new (ALLOC_TYPE, MEM_TYPE) Node(hv, key, value);

      return true;

    }

  }

  bool remove(K const& key) {

    unsigned hv = HASH(key);

    Node** ptr = lookup_node(hv, key);

    Node* node = *ptr;

    if (node != NULL) {

      *ptr = node->_next;

      if (ALLOC_TYPE == C_HEAP) {

        delete node;

      }

      return true;

    }

    return false;

  }

  // ITER contains bool do_entry(K const&, V const&), which will be

  // called for each entry in the table.  If do_entry() returns false,

  // the iteration is cancelled.

  template<class ITER>

  void iterate(ITER* iter) const {

    Node* const* bucket = _table;

    while (bucket < &_table[SIZE]) {

      Node* node = *bucket;

      while (node != NULL) {

        bool cont = iter->do_entry(node->_key, node->_value);

        if (!cont) { return; }

        node = node->_next;

      }

      ++bucket;

    }

  }

  static size_t node_size() {

    return sizeof(Node);

  }

};

#endif // SHARE_VM_UTILITIES_RESOURCEHASH_HPP