1 /*
   2  * Copyright (c) 2012, 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_UTILITIES_RESOURCEHASH_HPP
  26 #define SHARE_VM_UTILITIES_RESOURCEHASH_HPP
  27 
  28 #include "memory/allocation.hpp"
  29 #include "utilities/top.hpp"
  30 
  31 template<typename K> struct ResourceHashtableFns {
  32     typedef unsigned (*hash_fn)(K const&);
  33     typedef bool (*equals_fn)(K const&, K const&);
  34 };
  35 
  36 template<typename K> unsigned primitive_hash(const K& k) {
  37   unsigned hash = (unsigned)((uintptr_t)k);
  38   return hash ^ (hash > 3); // just in case we're dealing with aligned ptrs
  39 }
  40 
  41 template<typename K> bool primitive_equals(const K& k0, const K& k1) {
  42   return k0 == k1;
  43 }
  44 
  45 template<
  46     typename K, typename V,
  47     // xlC does not compile this:
  48     // http://stackoverflow.com/questions/8532961/template-argument-of-type-that-is-defined-by-inner-typedef-from-other-template-c
  49     //typename ResourceHashtableFns<K>::hash_fn   HASH   = primitive_hash<K>,
  50     //typename ResourceHashtableFns<K>::equals_fn EQUALS = primitive_equals<K>,
  51     unsigned (*HASH)  (K const&)           = primitive_hash<K>,
  52     bool     (*EQUALS)(K const&, K const&) = primitive_equals<K>,
  53     unsigned SIZE = 256
  54     >
  55 class ResourceHashtable : public ResourceObj {
  56  private:
  57 
  58   class Node : public ResourceObj {
  59    public:
  60     unsigned _hash;
  61     K _key;
  62     V _value;
  63     Node* _next;
  64 
  65     Node(unsigned hash, K const& key, V const& value) :
  66         _hash(hash), _key(key), _value(value), _next(NULL) {}
  67   };
  68 
  69   Node* _table[SIZE];
  70 
  71   // Returns a pointer to where the node where the value would reside if
  72   // it's in the table.
  73   Node** lookup_node(unsigned hash, K const& key) {
  74     unsigned index = hash % SIZE;
  75     Node** ptr = &_table[index];
  76     while (*ptr != NULL) {
  77       Node* node = *ptr;
  78       if (node->_hash == hash && EQUALS(key, node->_key)) {
  79         break;
  80       }
  81       ptr = &(node->_next);
  82     }
  83     return ptr;
  84   }
  85 
  86   Node const** lookup_node(unsigned hash, K const& key) const {
  87     return const_cast<Node const**>(
  88         const_cast<ResourceHashtable*>(this)->lookup_node(hash, key));
  89   }
  90 
  91  public:
  92   ResourceHashtable() { memset(_table, 0, SIZE * sizeof(Node*)); }
  93 
  94   bool contains(K const& key) const {
  95     return get(key) != NULL;
  96   }
  97 
  98   V* get(K const& key) const {
  99     unsigned hv = HASH(key);
 100     Node const** ptr = lookup_node(hv, key);
 101     if (*ptr != NULL) {
 102       return const_cast<V*>(&(*ptr)->_value);
 103     } else {
 104       return NULL;
 105     }
 106   }
 107 
 108  /**
 109   * Inserts or replaces a value in the table.
 110   * @return: true:  if a new item is added
 111   *          false: if the item already existed and the value is updated
 112   */
 113   bool put(K const& key, V const& value) {
 114     unsigned hv = HASH(key);
 115     Node** ptr = lookup_node(hv, key);
 116     if (*ptr != NULL) {
 117       (*ptr)->_value = value;
 118       return false;
 119     } else {
 120       *ptr = new Node(hv, key, value);
 121       return true;
 122     }
 123   }
 124 
 125   // ITER contains bool do_entry(K const&, V const&), which will be
 126   // called for each entry in the table.  If do_entry() returns false,
 127   // the iteration is cancelled.
 128   template<class ITER>
 129   void iterate(ITER* iter) const {
 130     Node* const* bucket = _table;
 131     while (bucket < &_table[SIZE]) {
 132       Node* node = *bucket;
 133       while (node != NULL) {
 134         bool cont = iter->do_entry(node->_key, node->_value);
 135         if (!cont) { return; }
 136         node = node->_next;
 137       }
 138       ++bucket;
 139     }
 140   }
 141 };
 142 
 143 
 144 #endif // SHARE_VM_UTILITIES_RESOURCEHASH_HPP