kamg@4245: /*
kamg@4245:  * Copyright (c) 2012, Oracle and/or its affiliates. All rights reserved.
kamg@4245:  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
kamg@4245:  *
kamg@4245:  * This code is free software; you can redistribute it and/or modify it
kamg@4245:  * under the terms of the GNU General Public License version 2 only, as
kamg@4245:  * published by the Free Software Foundation.
kamg@4245:  *
kamg@4245:  * This code is distributed in the hope that it will be useful, but WITHOUT
kamg@4245:  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
kamg@4245:  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
kamg@4245:  * version 2 for more details (a copy is included in the LICENSE file that
kamg@4245:  * accompanied this code).
kamg@4245:  *
kamg@4245:  * You should have received a copy of the GNU General Public License version
kamg@4245:  * 2 along with this work; if not, write to the Free Software Foundation,
kamg@4245:  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
kamg@4245:  *
kamg@4245:  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
kamg@4245:  * or visit www.oracle.com if you need additional information or have any
kamg@4245:  * questions.
kamg@4245:  *
kamg@4245:  */
kamg@4245: 
kamg@4245: #ifndef SHARE_VM_UTILITIES_RESOURCEHASH_HPP
kamg@4245: #define SHARE_VM_UTILITIES_RESOURCEHASH_HPP
kamg@4245: 
kamg@4245: #include "memory/allocation.hpp"
kamg@4245: #include "utilities/top.hpp"
kamg@4245: 
kamg@4245: template<typename K> struct ResourceHashtableFns {
kamg@4245:     typedef unsigned (*hash_fn)(K const&);
kamg@4245:     typedef bool (*equals_fn)(K const&, K const&);
kamg@4245: };
kamg@4245: 
kamg@4245: template<typename K> unsigned primitive_hash(const K& k) {
kamg@4245:   unsigned hash = (unsigned)((uintptr_t)k);
kamg@4245:   return hash ^ (hash > 3); // just in case we're dealing with aligned ptrs
kamg@4245: }
kamg@4245: 
kamg@4245: template<typename K> bool primitive_equals(const K& k0, const K& k1) {
kamg@4245:   return k0 == k1;
kamg@4245: }
kamg@4245: 
kamg@4245: template<
kamg@4245:     typename K, typename V,
kamg@4245:     typename ResourceHashtableFns<K>::hash_fn   HASH   = primitive_hash<K>,
kamg@4245:     typename ResourceHashtableFns<K>::equals_fn EQUALS = primitive_equals<K>,
kamg@4245:     unsigned SIZE = 256
kamg@4245:     >
kamg@4245: class ResourceHashtable : public ResourceObj {
kamg@4245:  private:
kamg@4245: 
kamg@4245:   class Node : public ResourceObj {
kamg@4245:    public:
kamg@4245:     unsigned _hash;
kamg@4245:     K _key;
kamg@4245:     V _value;
kamg@4245:     Node* _next;
kamg@4245: 
kamg@4245:     Node(unsigned hash, K const& key, V const& value) :
kamg@4245:         _hash(hash), _key(key), _value(value), _next(NULL) {}
kamg@4245:   };
kamg@4245: 
kamg@4245:   Node* _table[SIZE];
kamg@4245: 
kamg@4245:   // Returns a pointer to where the node where the value would reside if
kamg@4245:   // it's in the table.
kamg@4245:   Node** lookup_node(unsigned hash, K const& key) {
kamg@4245:     unsigned index = hash % SIZE;
kamg@4245:     Node** ptr = &_table[index];
kamg@4245:     while (*ptr != NULL) {
kamg@4245:       Node* node = *ptr;
kamg@4245:       if (node->_hash == hash && EQUALS(key, node->_key)) {
kamg@4245:         break;
kamg@4245:       }
kamg@4245:       ptr = &(node->_next);
kamg@4245:     }
kamg@4245:     return ptr;
kamg@4245:   }
kamg@4245: 
kamg@4245:   Node const** lookup_node(unsigned hash, K const& key) const {
kamg@4245:     return const_cast<Node const**>(
kamg@4245:         const_cast<ResourceHashtable*>(this)->lookup_node(hash, key));
kamg@4245:   }
kamg@4245: 
kamg@4245:  public:
kamg@4245:   ResourceHashtable() { memset(_table, 0, SIZE * sizeof(Node*)); }
kamg@4245: 
kamg@4245:   bool contains(K const& key) const {
kamg@4245:     return get(key) != NULL;
kamg@4245:   }
kamg@4245: 
kamg@4245:   V* get(K const& key) const {
kamg@4245:     unsigned hv = HASH(key);
kamg@4245:     Node const** ptr = lookup_node(hv, key);
kamg@4245:     if (*ptr != NULL) {
kamg@4245:       return const_cast<V*>(&(*ptr)->_value);
kamg@4245:     } else {
kamg@4245:       return NULL;
kamg@4245:     }
kamg@4245:   }
kamg@4245: 
kamg@4245:   // Inserts or replaces a value in the table
kamg@4245:   void put(K const& key, V const& value) {
kamg@4245:     unsigned hv = HASH(key);
kamg@4245:     Node** ptr = lookup_node(hv, key);
kamg@4245:     if (*ptr != NULL) {
kamg@4245:       (*ptr)->_value = value;
kamg@4245:     } else {
kamg@4245:       *ptr = new Node(hv, key, value);
kamg@4245:     }
kamg@4245:   }
kamg@4245: 
kamg@4245:   // ITER contains bool do_entry(K const&, V const&), which will be
kamg@4245:   // called for each entry in the table.  If do_entry() returns false,
kamg@4245:   // the iteration is cancelled.
kamg@4245:   template<class ITER>
kamg@4245:   void iterate(ITER* iter) const {
kamg@4245:     Node* const* bucket = _table;
kamg@4245:     while (bucket < &_table[SIZE]) {
kamg@4245:       Node* node = *bucket;
kamg@4245:       while (node != NULL) {
kamg@4245:         bool cont = iter->do_entry(node->_key, node->_value);
kamg@4245:         if (!cont) { return; }
kamg@4245:         node = node->_next;
kamg@4245:       }
kamg@4245:       ++bucket;
kamg@4245:     }
kamg@4245:   }
kamg@4245: };
kamg@4245: 
kamg@4245: 
kamg@4245: #endif // SHARE_VM_UTILITIES_RESOURCEHASH_HPP