Mercurial > hg > Members > kono > jpf-core

comparison src/main/gov/nasa/jpf/util/SimplePool.java @ 0:61d41facf527

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
initial v8 import (history reset)
author Peter Mehlitz <Peter.C.Mehlitz@nasa.gov>
date Fri, 23 Jan 2015 10:14:01 -0800
parents
children
comparison
equal deleted inserted replaced
-1:000000000000 0:61d41facf527
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 /**
21 * This is a simplified hash pool that does not support removal or
22 * numbering of elements.
23 */
24 @SuppressWarnings("unchecked")
25 public class SimplePool<E> {
26 static final double MAX_LOAD = 0.7;
27 static final int DEFAULT_POW = 10;
28
29 Object[] table;
30
31 int count;
32 int pow;
33 int mask;
34 int nextRehash;
35
36 /**
37 * Creates a SimplePool that holds about 716 elements before first
38 * rehash.
39 */
40 public SimplePool() {
41 this(DEFAULT_POW);
42 }
43
44 /**
45 * Creates a SimplePool that holds about 0.7 * 2**pow elements before
46 * first rehash.
47 */
48 public SimplePool(int pow) {
49 table = new Object[1 << pow];
50 count = 0;
51 this.pow = pow;
52 mask = table.length - 1;
53 nextRehash = (int)(MAX_LOAD * mask);
54 }
55
56 // ********************** API as simple hash pool ******************* //
57
58 /**
59 * Asks whether a particular element is already pooled. NOT A TYPICAL
60 * OPERATION.
61 */
62 public boolean isPooled(E e) {
63 return e == null || query(e) != null;
64 }
65
66 /**
67 * Returns the matching element if there is one, null if not.
68 */
69 public E query(E e) {
70 if (e == null) return null;
71 int code = e.hashCode();
72 int idx = code & mask;
73 int delta = (code >> (pow - 1)) | 1; // must be odd!
74 int oidx = idx;
75
76 for(;;) {
77 Object o = table[idx];
78 if (o == null) break;
79 if (e.equals(o)) {
80 return (E) o; // seen before!
81 }
82 idx = (idx + delta) & mask;
83 assert (idx != oidx); // should never wrap around
84 }
85 return null;
86 }
87
88 /**
89 * Returns a pooled element matching e, which will be e if no match
90 * has been previously pooled.
91 */
92 public E pool(E e) {
93 if (e == null) return null;
94 int code = e.hashCode();
95 int idx = code & mask;
96 int delta = (code >> (pow - 1)) | 1; // must be odd!
97 int oidx = idx;
98
99 for(;;) {
100 Object o = table[idx];
101 if (o == null) break;
102 if (e.equals(o)) {
103 return (E) o; // seen before!
104 }
105 idx = (idx + delta) & mask;
106 assert (idx != oidx); // should never wrap around
107 }
108 assert (table[idx] == null); // should never fill up
109 // not seen before; add it
110
111 count++;
112 if (count >= nextRehash) { // too full
113 Object[] oldTable = table;
114 pow++;
115 table = new Object[1 << pow];
116 mask = table.length - 1;
117 nextRehash = (int)(MAX_LOAD * mask);
118
119 int oldLen = oldTable.length;
120 for (int i = 0; i < oldLen; i++) {
121 Object o = oldTable[i];
122 if (o != null) {
123 code = o.hashCode();
124 idx = code & mask;
125 delta = (code >> (pow - 1)) | 1; // must be odd!
126 while (table[idx] != null) { // we know enough slots exist
127 idx = (idx + delta) & mask;
128 }
129 table[idx] = o;
130 }
131 }
132 // done with rehash; now get idx to empty slot
133 code = e.hashCode();
134 idx = code & mask;
135 delta = (code >> (pow - 1)) | 1; // must be odd!
136 while (table[idx] != null) { // we know enough slots exist & new element
137 idx = (idx + delta) & mask;
138 }
139 } else {
140 // idx already pointing to empty slot
141 }
142
143 table[idx] = e;
144 return e;
145 }
146
147
148 // ******************* API as add-only hash set *************** //
149
150 public boolean isMember(E e) {
151 return query(e) != null;
152 }
153
154 public void add(E e) {
155 /*(void)*/ pool(e);
156 }
157
158
159 // ************************** Test main ************************ //
160
161 /**
162 * Test main.
163 */
164 public static void main(String[] args) {
165 SimplePool<Integer> pool = new SimplePool<Integer>(4);
166 for (int i = 0; i < 1000000; i += 42) {
167 Integer o = new Integer(i);
168 Integer p = pool.pool(o);
169 if (o != p) throw new RuntimeException();
170 Integer q = pool.pool(p);
171 if (q != p) throw new RuntimeException();
172 }
173 for (int i = 0; i < 1000000; i += 42) {
174 Integer o = new Integer(i);
175 Integer p = pool.pool(o);
176 if (o == p) throw new RuntimeException();
177 if (!o.equals(p)) throw new RuntimeException();
178 }
179 for (int i = 1; i < 1000000; i += 42) {
180 Integer o = new Integer(i);
181 Integer p = pool.pool(o);
182 if (o != p) throw new RuntimeException();
183 }
184 }
185 }