src/main/gov/nasa/jpf/util/SparseObjVector.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 static java.lang.Integer.MIN_VALUE;
  21
  22 import java.util.Arrays;
  23
  24 /**
  25  * This has approximately the interface of ObjVector but uses a hash table
  26  * instead of an array.  Also, does not require allocation with each add.
  27  */
  28 public class SparseObjVector<E> {
  29   private static final boolean DEBUG = false;
  30
  31   static final double MAX_LOAD_WIPE = 0.6;
  32   static final double MAX_LOAD_REHASH = 0.4;
  33   static final int DEFAULT_POW = 10;
  34
  35   int[]    idxTable;  // MIN_VALUE => unoccupied
  36   Object[] valTable;  // can be bound to null
  37
  38   int count;
  39   int pow;
  40   int mask;
  41   int nextWipe;
  42   int nextRehash;
  43
  44
  45   /**
  46    * Creates a SimplePool that holds about 716 elements before first
  47    * rehash.
  48    */
  49   public SparseObjVector() {
  50     this(DEFAULT_POW);
  51   }
  52
  53   /**
  54    * Creates a SimplePool that holds about 0.7 * 2**pow elements before
  55    * first rehash.
  56    */
  57   public SparseObjVector(int pow) {
  58     this.pow = pow;
  59     newTable();
  60     count = 0;
  61     mask = valTable.length - 1;
  62     nextWipe = (int)(MAX_LOAD_WIPE * mask);
  63     nextRehash = (int)(MAX_LOAD_REHASH * mask);
  64   }
  65
  66   public void clear() {
  67     pow = DEFAULT_POW;
  68     newTable();
  69     count = 0;
  70     mask = valTable.length - 1;
  71     nextWipe = (int) (MAX_LOAD_WIPE * mask);
  72     nextRehash = (int) (MAX_LOAD_REHASH * mask);
  73   }
  74
  75   // INTERNAL //
  76
  77   @SuppressWarnings("unchecked")
  78   protected void newTable() {
  79     valTable = new Object[1 << pow];
  80     idxTable = new int[1 << pow];
  81     Arrays.fill(idxTable, MIN_VALUE);
  82   }
  83
  84   protected int mix(int x) {
  85     int y = 0x9e3779b9;
  86     x ^= 0x510fb60d;
  87     y += (x >> 8) + (x << 3);
  88     x ^= (y >> 5) + (y << 2);
  89     return y - x;
  90   }
  91
  92
  93   // ********************* Public API ******************** //
  94
  95
  96   @SuppressWarnings("unchecked")
  97   public E get(int idx) {
  98     int code = mix(idx);
  99     int pos = code & mask;
 100     int delta = (code >> (pow - 1)) | 1; // must be odd!
 101     int oidx = pos;
 102
 103     for(;;) {
 104       int tidx = idxTable[pos];
 105       if (tidx == MIN_VALUE) {
 106         return null;
 107       }
 108       if (tidx == idx) {
 109         return (E) valTable[pos];
 110       }
 111       pos = (pos + delta) & mask;
 112       assert (pos != oidx); // should never wrap around
 113     }
 114   }
 115
 116   public void set(int idx, E e) {
 117     int code = mix(idx);
 118     int pos = code & mask;
 119     int delta = (code >> (pow - 1)) | 1; // must be odd!
 120     int oidx = pos;
 121
 122     for(;;) {
 123       int tidx = idxTable[pos];
 124       if (tidx == MIN_VALUE) {
 125         break;
 126       }
 127       if (tidx == idx) {
 128         valTable[pos] = e; // update
 129         return;            // and we're done
 130       }
 131       pos = (pos + delta) & mask;
 132       assert (pos != oidx); // should never wrap around
 133     }
 134     // idx not in table; add it
 135
 136     if ((count+1) >= nextWipe) { // too full
 137       if (count >= nextRehash) {
 138         pow++;
 139       }
 140
 141       /**
 142       // determine if size needs to be increased or just wipe null blocks
 143       int oldCount = count;
 144       count = 0;
 145       for (int i = 0; i < idxTable.length; i++) {
 146         if (idxTable[i] != MIN_VALUE && valTable[i] != null) {
 147           count++;
 148         }
 149       }
 150       if (count >= nextRehash) {
 151         pow++; // needs to be increased in size
 152         if (DEBUG) {
 153           System.out.println("Rehash to capacity: 2**" + pow);
 154         }
 155       } else {
 156         if (DEBUG) {
 157           System.out.println("Rehash reclaiming this many nulls: " + (oldCount - count));
 158         }
 159       }
 160       **/
 161
 162       Object[] oldValTable = valTable;
 163       int[] oldIdxTable = idxTable;
 164       newTable();
 165       mask = idxTable.length - 1;
 166       nextWipe = (int)(MAX_LOAD_WIPE * mask);
 167       nextRehash = (int)(MAX_LOAD_REHASH * mask);
 168
 169       int oldLen = oldIdxTable.length;
 170       for (int i = 0; i < oldLen; i++) {
 171         int tidx = oldIdxTable[i];
 172         if (tidx == MIN_VALUE) continue;
 173         Object o = oldValTable[i];
 174         //if (o == null) continue;
 175         // otherwise:
 176         code = mix(tidx);
 177         pos = code & mask;
 178         delta = (code >> (pow - 1)) | 1; // must be odd!
 179         while (idxTable[pos] != MIN_VALUE) { // we know enough slots exist
 180           pos = (pos + delta) & mask;
 181         }
 182         idxTable[pos] = tidx;
 183         valTable[pos] = o;
 184       }
 185       // done with rehash; now get idx to empty slot
 186       code = mix(idx);
 187       pos = code & mask;
 188       delta = (code >> (pow - 1)) | 1; // must be odd!
 189       while (idxTable[pos] != MIN_VALUE) { // we know enough slots exist
 190         pos = (pos + delta) & mask;
 191       }
 192     } else {
 193       // pos already pointing to empty slot
 194     }
 195
 196     count++;
 197
 198     idxTable[pos] = idx;
 199     valTable[pos] = e;
 200   }
 201
 202   public void remove(int idx) {
 203     set(idx, null);
 204   }
 205
 206
 207   // ************************** Test main ************************ //
 208
 209   public static void main(String[] args) {
 210     SparseObjVector<Integer> vect = new SparseObjVector<Integer>(3);
 211
 212     // add some
 213     for (int i = -4200; i < 4200; i += 10) {
 214       vect.set(i, new Integer(i));
 215     }
 216
 217     // check for added & non-added
 218     for (int i = -4200; i < 4200; i += 10) {
 219       Integer v = vect.get(i);
 220       if (v.intValue() != i) {
 221         throw new IllegalStateException();
 222       }
 223     }
 224     for (int i = -4205; i < 4200; i += 10) {
 225       Integer v = vect.get(i);
 226       if (v != null) {
 227         throw new IllegalStateException();
 228       }
 229     }
 230
 231     // add some more
 232     for (int i = -4201; i < 4200; i += 10) {
 233       vect.set(i, new Integer(i));
 234     }
 235
 236     // check all added
 237     for (int i = -4200; i < 4200; i += 10) {
 238       Integer v = vect.get(i);
 239       if (v.intValue() != i) {
 240         throw new IllegalStateException();
 241       }
 242     }
 243     for (int i = -4201; i < 4200; i += 10) {
 244       Integer v = vect.get(i);
 245       if (v.intValue() != i) {
 246         throw new IllegalStateException();
 247       }
 248     }
 249
 250     // "remove" some
 251     for (int i = -4200; i < 4200; i += 10) {
 252       vect.remove(i);
 253     }
 254
 255     // check for added & non-added
 256     for (int i = -4201; i < 4200; i += 10) {
 257       Integer v = vect.get(i);
 258       if (v.intValue() != i) {
 259         throw new IllegalStateException();
 260       }
 261     }
 262     for (int i = -4200; i < 4200; i += 10) {
 263       Integer v = vect.get(i);
 264       if (v != null) {
 265         throw new IllegalStateException();
 266       }
 267     }
 268
 269     // add even more
 270     for (int i = -4203; i < 4200; i += 10) {
 271       vect.set(i, new Integer(i));
 272     }
 273     for (int i = -4204; i < 4200; i += 10) {
 274       vect.set(i, new Integer(i));
 275     }
 276   }
 277 }