1 /*
   2  * Copyright (c) 2012, 2015, 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_EXPANDABLERESOURCEHASH_HPP
  26 #define SHARE_VM_UTILITIES_EXPANDABLERESOURCEHASH_HPP
  27 
  28 #include "logging/log.hpp"
  29 #include "utilities/resourceHash.hpp"
  30 
  31 // This table can expand dynamically when there are too many entries
  32 template<
  33     typename K, typename V,
  34     // xlC does not compile this:
  35     // http://stackoverflow.com/questions/8532961/template-argument-of-type-that-is-defined-by-inner-typedef-from-other-template-c
  36     //typename ResourceHashtableFns<K>::hash_fn   HASH   = primitive_hash<K>,
  37     //typename ResourceHashtableFns<K>::equals_fn EQUALS = primitive_equals<K>,
  38     unsigned (*HASH)  (K const&)           = primitive_hash<K>,
  39     bool     (*EQUALS)(K const&, K const&) = primitive_equals<K>,
  40     unsigned INITIAL_SIZE = 256,
  41     unsigned EXPAND_FACTOR = 8, // expand the table if the average entry per bucket has increased over this number
  42     ResourceObj::allocation_type ALLOC_TYPE = ResourceObj::RESOURCE_AREA,
  43     MEMFLAGS MEM_TYPE = mtInternal
  44     >
  45 class ExpandableResourceHashtable : public ResourceObj {
  46   typedef ResourceHashtable<K, V, HASH, EQUALS, CONFIGURABLE_SIZE, ALLOC_TYPE, MEM_TYPE> InternalTable;
  47   unsigned _count;
  48   InternalTable *_internal_table;
  49 
  50  public:
  51   ExpandableResourceHashtable() : _count(0) {
  52     _internal_table = new (ALLOC_TYPE, MEM_TYPE) InternalTable(INITIAL_SIZE);
  53   }
  54 
  55   ~ExpandableResourceHashtable() {
  56     if (ALLOC_TYPE == C_HEAP) {
  57       delete _internal_table;
  58     }
  59   }
  60 
  61   bool contains(K const& key) const {
  62     return _internal_table->contains(key);
  63   }
  64 
  65   V* get(K const& key) const {
  66     return _internal_table->get(key);
  67   }
  68 
  69   class TableCopier {
  70   public:
  71     InternalTable* _new_table;
  72     TableCopier(unsigned new_size) {
  73       _new_table = new (ALLOC_TYPE, MEM_TYPE) InternalTable(new_size);
  74     }
  75     bool do_entry(K const& key, V const& value) {
  76       _new_table->put(key, value);
  77       return true; // keep on iterating
  78     }
  79   };
  80 
  81   bool put(K const& key, V const& value) {
  82     _count ++;
  83     unsigned old_size = _internal_table->size();
  84     if ((_count / old_size ) > EXPAND_FACTOR) {
  85       unsigned new_size = old_size * 2;
  86       log_info(hashtables)("ExpandableResourceHashtable @ " PTR_FORMAT ": expanding to %d", p2i(this), new_size);
  87       TableCopier copier(new_size);
  88       _internal_table->iterate(&copier);
  89       if (ALLOC_TYPE == C_HEAP) {
  90         delete _internal_table;
  91       }
  92       _internal_table = copier._new_table;
  93     }
  94     return _internal_table->put(key, value);
  95   }
  96 
  97   bool remove(K const& key) {
  98     _count --;
  99     return _internal_table->remove(key);
 100   }
 101 
 102   template<class ITER>
 103   void iterate(ITER* iter) const {
 104     _internal_table->iterate(iter);
 105   }
 106 
 107   static size_t node_size() {
 108     return InternalTable::node_size();
 109   }
 110 };
 111 
 112 
 113 #endif // SHARE_VM_UTILITIES_EXPANDABLERESOURCEHASH_HPP