src/main/gov/nasa/jpf/util/WeakPool.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.lang.ref.WeakReference;
  21
  22 /**
  23  * This is a simplified hash pool that does not support removal or
  24  * numbering of elements.
  25  */
  26 public class WeakPool<E> {
  27   private static final boolean DEBUG = false;
  28
  29   static final double MAX_LOAD_WIPE = 0.6;
  30   static final double MAX_LOAD_REHASH = 0.4;
  31   static final int DEFAULT_POW = 10;
  32
  33   WeakReference<E>[] table;
  34
  35   int count;
  36   int pow;
  37   int mask;
  38   int nextWipe;
  39   int nextRehash;
  40
  41   /**
  42    * Creates a SimplePool that holds about 716 elements before first
  43    * rehash.
  44    */
  45   public WeakPool() {
  46     this(DEFAULT_POW);
  47   }
  48
  49   /**
  50    * Creates a SimplePool that holds about 0.7 * 2**pow elements before
  51    * first rehash.
  52    */
  53   public WeakPool(int pow) {
  54     this.pow = pow;
  55     newTable();
  56     count = 0;
  57     mask = table.length - 1;
  58     nextWipe = (int)(MAX_LOAD_WIPE * mask);
  59     nextRehash = (int)(MAX_LOAD_REHASH * mask);
  60   }
  61
  62   @SuppressWarnings("unchecked")
  63   protected void newTable() {
  64     table = new WeakReference[1 << pow];
  65   }
  66
  67   // ********************** API as simple hash pool ******************* //
  68
  69   /**
  70    * Asks whether a particular element is already pooled.  NOT A TYPICAL
  71    * OPERATION.
  72    */
  73   public boolean isPooled(E e) {
  74     return e == null || query(e) != null;
  75   }
  76
  77   /**
  78    * Returns the matching element if there is one, null if not.
  79    */
  80   public E query(E e) {
  81     if (e == null) return null;
  82     int code = e.hashCode();
  83     int idx = code & mask;
  84     int delta = (code >> (pow - 1)) | 1; // must be odd!
  85     int oidx = idx;
  86
  87     for(;;) {
  88       WeakReference<E> r = table[idx];
  89       if (r == null) break;
  90       E o = r.get();
  91       if (o != null && e.equals(o)) {
  92         return o; // seen before!
  93       }
  94       idx = (idx + delta) & mask;
  95       assert (idx != oidx); // should never wrap around
  96     }
  97     return null;
  98   }
  99
 100   /**
 101    * Returns a pooled element matching e, which will be e if no match
 102    * has been previously pooled.
 103    */
 104   public E pool(E e) {
 105     if (e == null) return null;
 106     int code = e.hashCode();
 107     int idx = code & mask;
 108     int delta = (code >> (pow - 1)) | 1; // must be odd!
 109     int oidx = idx;
 110
 111     for(;;) {
 112       WeakReference<E> r = table[idx];
 113       if (r == null) break;
 114       E o = r.get();
 115       if (o != null && e.equals(o)) {
 116         return o; // seen before!
 117       }
 118       idx = (idx + delta) & mask;
 119       assert (idx != oidx); // should never wrap around
 120     }
 121     assert (table[idx] == null); // should never fill up
 122     // not seen before; add it
 123
 124     count++;
 125     if (count >= nextWipe) { // too full
 126       // determine if size needs to be increased or just wipe unused weak refs
 127       int oldCount = count;
 128       count = 0;
 129       for (int i = 0; i < table.length; i++) {
 130         if (table[i] != null && table[i].get() != null) {
 131           count++;
 132         }
 133       }
 134       if (DEBUG && oldCount > count) {
 135         System.out.println("Weak references collected: " + (oldCount - count));
 136       }
 137       if (count >= nextRehash) {
 138         pow++; // needs to be increased in size
 139       }
 140       WeakReference<E>[] oldTable = table;
 141       newTable();
 142       mask = table.length - 1;
 143       nextWipe = (int)(MAX_LOAD_WIPE * mask);
 144       nextRehash = (int)(MAX_LOAD_REHASH * mask);
 145
 146       int oldLen = oldTable.length;
 147       for (int i = 0; i < oldLen; i++) {
 148         WeakReference<E> r = oldTable[i];
 149         if (r == null) continue;
 150         E o = r.get();
 151         if (o == null) continue;
 152         // otherwise:
 153         code = o.hashCode();
 154         idx = code & mask;
 155         delta = (code >> (pow - 1)) | 1; // must be odd!
 156         while (table[idx] != null) { // we know enough slots exist
 157           idx = (idx + delta) & mask;
 158         }
 159         table[idx] = r;
 160       }
 161       // done with rehash; now get idx to empty slot
 162       code = e.hashCode();
 163       idx = code & mask;
 164       delta = (code >> (pow - 1)) | 1; // must be odd!
 165       while (table[idx] != null) { // we know enough slots exist & new element
 166         idx = (idx + delta) & mask;
 167       }
 168     } else {
 169       // idx already pointing to empty slot
 170     }
 171
 172     table[idx] = new WeakReference<E>(e);
 173     return e;
 174   }
 175
 176
 177   // ******************* API as add-only weak hash set *************** //
 178
 179   public boolean isMember(E e) {
 180     return query(e) != null;
 181   }
 182
 183   public void add(E e) {
 184     /*(void)*/ pool(e);
 185   }
 186
 187
 188   // ************************** Test main ************************ //
 189
 190   /**
 191    * BROKEN Test main.
 192    */
 193   public static void main(String[] args) {
 194     WeakPool<Integer> pool = new WeakPool<Integer>(4);
 195     for (int i = 0; i < 1000000; i += 42) {
 196       Integer o = new Integer(i);
 197       Integer p = pool.pool(o);
 198       if (o != p) throw new RuntimeException();
 199       Integer q = pool.pool(p);
 200       if (q != p) throw new RuntimeException();
 201     }
 202     for (int i = 0; i < 1000000; i += 42) {
 203       Integer o = new Integer(i);
 204       Integer p = pool.pool(o);
 205       if (o == p) throw new RuntimeException();
 206       if (!o.equals(p)) throw new RuntimeException();
 207     }
 208     for (int i = 1; i < 1000000; i += 42) {
 209       Integer o = new Integer(i);
 210       Integer p = pool.pool(o);
 211       if (o != p) throw new RuntimeException();
 212     }
 213   }
 214 }