2 * Copyright (C) 2014, United States Government, as represented by the
3 * Administrator of the National Aeronautics and Space Administration.
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
10 * http://www.apache.org/licenses/LICENSE-2.0.
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.
18 package gov.nasa.jpf.util;
20 import static java.lang.Integer.MIN_VALUE;
22 import java.util.Arrays;
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.
28 public class SparseObjVector<E> {
29 private static final boolean DEBUG = false;
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;
35 int[] idxTable; // MIN_VALUE => unoccupied
36 Object[] valTable; // can be bound to null
46 * Creates a SimplePool that holds about 716 elements before first
49 public SparseObjVector() {
54 * Creates a SimplePool that holds about 0.7 * 2**pow elements before
57 public SparseObjVector(int pow) {
61 mask = valTable.length - 1;
62 nextWipe = (int)(MAX_LOAD_WIPE * mask);
63 nextRehash = (int)(MAX_LOAD_REHASH * mask);
70 mask = valTable.length - 1;
71 nextWipe = (int) (MAX_LOAD_WIPE * mask);
72 nextRehash = (int) (MAX_LOAD_REHASH * mask);
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);
84 protected int mix(int x) {
87 y += (x >> 8) + (x << 3);
88 x ^= (y >> 5) + (y << 2);
93 // ********************* Public API ******************** //
96 @SuppressWarnings("unchecked")
97 public E get(int idx) {
99 int pos = code & mask;
100 int delta = (code >> (pow - 1)) | 1; // must be odd!
104 int tidx = idxTable[pos];
105 if (tidx == MIN_VALUE) {
109 return (E) valTable[pos];
111 pos = (pos + delta) & mask;
112 assert (pos != oidx); // should never wrap around
116 public void set(int idx, E e) {
118 int pos = code & mask;
119 int delta = (code >> (pow - 1)) | 1; // must be odd!
123 int tidx = idxTable[pos];
124 if (tidx == MIN_VALUE) {
128 valTable[pos] = e; // update
129 return; // and we're done
131 pos = (pos + delta) & mask;
132 assert (pos != oidx); // should never wrap around
134 // idx not in table; add it
136 if ((count+1) >= nextWipe) { // too full
137 if (count >= nextRehash) {
142 // determine if size needs to be increased or just wipe null blocks
143 int oldCount = count;
145 for (int i = 0; i < idxTable.length; i++) {
146 if (idxTable[i] != MIN_VALUE && valTable[i] != null) {
150 if (count >= nextRehash) {
151 pow++; // needs to be increased in size
153 System.out.println("Rehash to capacity: 2**" + pow);
157 System.out.println("Rehash reclaiming this many nulls: " + (oldCount - count));
162 Object[] oldValTable = valTable;
163 int[] oldIdxTable = idxTable;
165 mask = idxTable.length - 1;
166 nextWipe = (int)(MAX_LOAD_WIPE * mask);
167 nextRehash = (int)(MAX_LOAD_REHASH * mask);
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;
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;
182 idxTable[pos] = tidx;
185 // done with rehash; now get idx to empty slot
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;
193 // pos already pointing to empty slot
202 public void remove(int idx) {
207 // ************************** Test main ************************ //
209 public static void main(String[] args) {
210 SparseObjVector<Integer> vect = new SparseObjVector<Integer>(3);
213 for (int i = -4200; i < 4200; i += 10) {
214 vect.set(i, new Integer(i));
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();
224 for (int i = -4205; i < 4200; i += 10) {
225 Integer v = vect.get(i);
227 throw new IllegalStateException();
232 for (int i = -4201; i < 4200; i += 10) {
233 vect.set(i, new Integer(i));
237 for (int i = -4200; i < 4200; i += 10) {
238 Integer v = vect.get(i);
239 if (v.intValue() != i) {
240 throw new IllegalStateException();
243 for (int i = -4201; i < 4200; i += 10) {
244 Integer v = vect.get(i);
245 if (v.intValue() != i) {
246 throw new IllegalStateException();
251 for (int i = -4200; i < 4200; i += 10) {
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();
262 for (int i = -4200; i < 4200; i += 10) {
263 Integer v = vect.get(i);
265 throw new IllegalStateException();
270 for (int i = -4203; i < 4200; i += 10) {
271 vect.set(i, new Integer(i));
273 for (int i = -4204; i < 4200; i += 10) {
274 vect.set(i, new Integer(i));