src/main/gov/nasa/jpf/util/HashPool.java

   1 /*
   2  * Copyright (C) 2014, United States Government, as represented by the
   3  * Administrator of the National Aeronautics and Space Administration.
   4  * All rights reserved.
   5  *
   6  * The Java Pathfinder core (jpf-core) platform is licensed under the
   7  * Apache License, Version 2.0 (the "License"); you may not use this file except
   8  * in compliance with the License. You may obtain a copy of the License at
   9  *
  10  *        http://www.apache.org/licenses/LICENSE-2.0.
  11  *
  12  * Unless required by applicable law or agreed to in writing, software
  13  * distributed under the License is distributed on an "AS IS" BASIS,
  14  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  15  * See the License for the specific language governing permissions and
  16  * limitations under the License.
  17  */
  18 package gov.nasa.jpf.util;
  19
  20 import java.util.ArrayList;
  21
  22
  23 /**
  24  * data structure used to do hash collapsing. All the major state components
  25  * (fields, Monitors, StackFrames, uThreadData) are stored in pools to
  26  * determine if they are new. Only the pool index values are used to
  27  * compute hash values.
  28  * <p>
  29  * 2006-06-14 - major rewrite by pcd
  30  */
  31 public final class HashPool<V> {
  32   private IntTable<V> pool;
  33   private ArrayList<V> vect;
  34
  35   public HashPool() {
  36     this(8); // default to 256 slots
  37   }
  38
  39   public HashPool(int pow) {
  40     pool = new IntTable<V>(pow);
  41     vect = new ArrayList<V>(1 << pow);
  42   }
  43
  44   /** optionally called only once after creation to link null to 0. */
  45   public HashPool<V> addNull() {
  46     if (size() == 0) {
  47       pool.add(null, 0);
  48       vect.add(null);
  49       return this;
  50     } else {
  51       throw new IllegalStateException();
  52     }
  53   }
  54
  55   public IntTable.Entry<V> getEntry (V o) {
  56     int sz = pool.size(); // == vect.size();
  57
  58     IntTable.Entry<V> e = pool.pool(o);
  59     if (e.val == sz) {
  60       vect.add(o);
  61     }
  62     return e;
  63   }
  64
  65   public int getIndex (V o) {
  66     return getEntry(o).val;
  67   }
  68
  69   public V get (V o) {
  70     return getEntry(o).key;
  71   }
  72
  73   public V getObject (int idx) {
  74     return vect.get(idx);
  75   }
  76
  77   public void print () {
  78     System.out.println("{");
  79
  80     for (IntTable.Entry<V> entry : pool) {
  81       System.out.println("\t" + entry);
  82     }
  83
  84     System.out.println("}");
  85   }
  86
  87   public int size () {
  88     return pool.size();
  89   }
  90 }