Mercurial > hg > truffle
comparison graal/com.oracle.max.base/src/com/sun/max/collect/OpenAddressingHashMapping.java @ 3733:e233f5660da4
Added Java files from Maxine project.
author | Thomas Wuerthinger <thomas.wuerthinger@oracle.com> |
---|---|
date | Sat, 17 Dec 2011 19:59:18 +0100 |
parents | |
children |
comparison
equal
deleted
inserted
replaced
3732:3e2e8b8abdaf | 3733:e233f5660da4 |
---|---|
1 /* | |
2 * Copyright (c) 2007, 2011, Oracle and/or its affiliates. All rights reserved. | |
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. | |
4 * | |
5 * This code is free software; you can redistribute it and/or modify it | |
6 * under the terms of the GNU General Public License version 2 only, as | |
7 * published by the Free Software Foundation. | |
8 * | |
9 * This code is distributed in the hope that it will be useful, but WITHOUT | |
10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or | |
11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License | |
12 * version 2 for more details (a copy is included in the LICENSE file that | |
13 * accompanied this code). | |
14 * | |
15 * You should have received a copy of the GNU General Public License version | |
16 * 2 along with this work; if not, write to the Free Software Foundation, | |
17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. | |
18 * | |
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA | |
20 * or visit www.oracle.com if you need additional information or have any | |
21 * questions. | |
22 */ | |
23 package com.sun.max.collect; | |
24 | |
25 import java.util.*; | |
26 | |
27 import com.sun.max.*; | |
28 import com.sun.max.lang.*; | |
29 | |
30 /** | |
31 * An open addressing hash table with liner probe hash collision resolution. | |
32 */ | |
33 public class OpenAddressingHashMapping<K, V> extends HashMapping<K, V> implements Mapping<K, V> { | |
34 | |
35 // Note: this implementation is partly derived from java.util.IdentityHashMap in the standard JDK | |
36 | |
37 /** | |
38 * The initial capacity used by the no-args constructor. | |
39 * MUST be a power of two. The value 32 corresponds to the | |
40 * (specified) expected maximum size of 21, given a load factor | |
41 * of 2/3. | |
42 */ | |
43 private static final int DEFAULT_CAPACITY = 32; | |
44 | |
45 /** | |
46 * The minimum capacity, used if a lower value is implicitly specified | |
47 * by either of the constructors with arguments. The value 4 corresponds | |
48 * to an expected maximum size of 2, given a load factor of 2/3. | |
49 * MUST be a power of two. | |
50 */ | |
51 private static final int MINIMUM_CAPACITY = 4; | |
52 | |
53 /** | |
54 * The maximum capacity, used if a higher value is implicitly specified | |
55 * by either of the constructors with arguments. | |
56 * MUST be a power of two <= 1<<29. | |
57 */ | |
58 private static final int MAXIMUM_CAPACITY = 1 << 29; | |
59 | |
60 /** | |
61 * The table, resized as necessary. Length MUST always be a power of two. | |
62 */ | |
63 private Object[] table; | |
64 | |
65 /** | |
66 * Returns the appropriate capacity for the specified expected maximum | |
67 * size. Returns the smallest power of two between MINIMUM_CAPACITY | |
68 * and MAXIMUM_CAPACITY, inclusive, that is greater than | |
69 * (3 * expectedMaxSize)/2, if such a number exists. Otherwise | |
70 * returns MAXIMUM_CAPACITY. If (3 * expectedMaxSize)/2 is negative, it | |
71 * is assumed that overflow has occurred, and MAXIMUM_CAPACITY is returned. | |
72 */ | |
73 private static int capacity(int expectedMaxSize) { | |
74 // Compute minimum capacity for expectedMaxSize given a load factor of 2/3 | |
75 final int minimumCapacity = (3 * expectedMaxSize) >> 1; | |
76 | |
77 // Compute the appropriate capacity | |
78 int result; | |
79 if (minimumCapacity > MAXIMUM_CAPACITY || minimumCapacity < 0) { | |
80 result = MAXIMUM_CAPACITY; | |
81 } else { | |
82 result = MINIMUM_CAPACITY; | |
83 while (result < minimumCapacity) { | |
84 result <<= 1; | |
85 } | |
86 } | |
87 return result; | |
88 } | |
89 | |
90 /** | |
91 * Constructs a new, empty open addressing hash table with {@linkplain HashEquality equality} key semantics and a | |
92 * default expected maximum size of 21. | |
93 */ | |
94 public OpenAddressingHashMapping() { | |
95 this(null); | |
96 } | |
97 | |
98 /** | |
99 * Constructs a new, empty open addressing hash table with a default expected maximum size of 21. | |
100 * | |
101 * @param equivalence | |
102 * the semantics to be used for comparing keys. If {@code null} is provided, then {@link HashEquality} is | |
103 * used. | |
104 */ | |
105 public OpenAddressingHashMapping(HashEquivalence<K> equivalence) { | |
106 this(equivalence, (DEFAULT_CAPACITY * 2) / 3); | |
107 } | |
108 | |
109 /** | |
110 * Constructs a new, empty open addressing hash table with {@linkplain HashEquality equality} key semantics. | |
111 * | |
112 * @param expectedMaximumSize | |
113 * the expected maximum size of the map | |
114 */ | |
115 public OpenAddressingHashMapping(int expectedMaximumSize) { | |
116 this(null, expectedMaximumSize); | |
117 } | |
118 | |
119 /** | |
120 * Constructs a new, empty open addressing hash table with the specified expected maximum size. Putting more than | |
121 * the expected number of key-value mappings into the map may cause the internal data structure to grow, which may | |
122 * be somewhat time-consuming. | |
123 * | |
124 * @param equivalence | |
125 * the semantics to be used for comparing keys. If {@code null} is provided, then {@link HashEquality} is | |
126 * used. | |
127 * @param expectedMaximumSize | |
128 * the expected maximum size of the map | |
129 * @throws IllegalArgumentException | |
130 * if {@code expectedMaximumSize} is negative | |
131 */ | |
132 public OpenAddressingHashMapping(HashEquivalence<K> equivalence, int expectedMaximumSize) { | |
133 super(equivalence); | |
134 if (expectedMaximumSize < 0) { | |
135 throw new IllegalArgumentException("Illegal initial capacity: " + expectedMaximumSize); | |
136 } | |
137 | |
138 // Find a power of 2 >= initialCapacity | |
139 final int capacity = capacity(expectedMaximumSize); | |
140 threshold = (capacity * 2) / 3; | |
141 table = new Object[capacity * 2]; | |
142 } | |
143 | |
144 private int numberOfEntries; | |
145 private int threshold; | |
146 | |
147 public int length() { | |
148 return numberOfEntries; | |
149 } | |
150 | |
151 /** | |
152 * Applies a supplemental hash function to a given hashCode, which | |
153 * defends against poor quality hash functions. This is critical | |
154 * because BuckHashMapping uses power-of-two length hash tables, that | |
155 * otherwise encounter collisions for hashCodes that do not differ | |
156 * in lower bits. | |
157 */ | |
158 static int hash(int hash) { | |
159 // This function ensures that hashCodes that differ only by | |
160 // constant multiples at each bit position have a bounded | |
161 // number of collisions (approximately 8 at default load factor). | |
162 final int h = hash ^ ((hash >>> 20) ^ (hash >>> 12)); | |
163 return h ^ (h >>> 7) ^ (h >>> 4); | |
164 } | |
165 | |
166 /** | |
167 * Returns index for hash code h. | |
168 */ | |
169 static int indexFor(int h, int length) { | |
170 // Multiply by -127, and left-shift to use least bit as part of hash | |
171 final int index = ((h << 1) - (h << 8)) & (length - 1); | |
172 assert (index & 1) == 0 : "index must be even"; | |
173 return index; | |
174 } | |
175 | |
176 /** | |
177 * Circularly traverses table of size {@code length}. | |
178 */ | |
179 private static int nextKeyIndex(int i, int length) { | |
180 return i + 2 < length ? i + 2 : 0; | |
181 } | |
182 | |
183 public V get(K key) { | |
184 if (key == null) { | |
185 throw new IllegalArgumentException("Key cannot be null"); | |
186 } | |
187 | |
188 final Object[] tbl = this.table; | |
189 final int length = tbl.length; | |
190 final int hash = hash(hashCode(key)); | |
191 int index = indexFor(hash, tbl.length); | |
192 while (true) { | |
193 final Object item = tbl[index]; | |
194 final Class<K> keyType = null; | |
195 final K entryKey = Utils.cast(keyType, item); | |
196 if (equivalent(entryKey, key)) { | |
197 final Class<V> valueType = null; | |
198 return Utils.cast(valueType, tbl[index + 1]); | |
199 } | |
200 if (item == null) { | |
201 return null; | |
202 } | |
203 index = nextKeyIndex(index, length); | |
204 } | |
205 } | |
206 | |
207 public V put(K key, V value) { | |
208 if (key == null) { | |
209 throw new IllegalArgumentException("Key cannot be null"); | |
210 } | |
211 if (value == null) { | |
212 throw new IllegalArgumentException("Value cannot be null"); | |
213 } | |
214 | |
215 final Object[] tbl = this.table; | |
216 final int length = tbl.length; | |
217 final int hash = hash(hashCode(key)); | |
218 int index = indexFor(hash, tbl.length); | |
219 | |
220 Object item = tbl[index]; | |
221 while (item != null) { | |
222 final Class<K> keyType = null; | |
223 final K entryKey = Utils.cast(keyType, item); | |
224 if (equivalent(entryKey, key)) { | |
225 final Class<V> valueType = null; | |
226 final V oldValue = Utils.cast(valueType, tbl[index + 1]); | |
227 tbl[index + 1] = value; | |
228 return oldValue; | |
229 } | |
230 index = nextKeyIndex(index, length); | |
231 item = tbl[index]; | |
232 } | |
233 | |
234 tbl[index] = key; | |
235 tbl[index + 1] = value; | |
236 if (numberOfEntries++ >= threshold) { | |
237 resize(length); // length == 2 * current capacity. | |
238 } | |
239 return null; | |
240 | |
241 } | |
242 | |
243 public V remove(K key) { | |
244 if (key == null) { | |
245 throw new IllegalArgumentException("Key cannot be null"); | |
246 } | |
247 | |
248 final Object[] tbl = this.table; | |
249 final int length = tbl.length; | |
250 final int hash = hash(hashCode(key)); | |
251 int index = indexFor(hash, tbl.length); | |
252 | |
253 while (true) { | |
254 final Object item = tbl[index]; | |
255 final Class<K> keyType = null; | |
256 final K entryKey = Utils.cast(keyType, item); | |
257 if (equivalent(entryKey, key)) { | |
258 numberOfEntries--; | |
259 final Class<V> valueType = null; | |
260 final V oldValue = Utils.cast(valueType, tbl[index + 1]); | |
261 tbl[index + 1] = null; | |
262 tbl[index] = null; | |
263 return oldValue; | |
264 } | |
265 if (item == null) { | |
266 return null; | |
267 } | |
268 index = nextKeyIndex(index, length); | |
269 } | |
270 } | |
271 | |
272 public void clear() { | |
273 for (int i = 0; i != table.length; ++i) { | |
274 table[i] = null; | |
275 } | |
276 numberOfEntries = 0; | |
277 } | |
278 | |
279 /** | |
280 * Resize the table to hold given capacity. | |
281 * | |
282 * @param newCapacity the new capacity, must be a power of two. | |
283 */ | |
284 private void resize(int newCapacity) { | |
285 assert Ints.isPowerOfTwoOrZero(newCapacity) : "newCapacity must be a power of 2"; | |
286 final int newLength = newCapacity * 2; | |
287 | |
288 final Object[] oldTable = table; | |
289 final int oldLength = oldTable.length; | |
290 if (oldLength == 2 * MAXIMUM_CAPACITY) { // can't expand any further | |
291 if (threshold == MAXIMUM_CAPACITY - 1) { | |
292 throw new IllegalStateException("Capacity exhausted."); | |
293 } | |
294 threshold = MAXIMUM_CAPACITY - 1; // Gigantic map! | |
295 return; | |
296 } | |
297 if (oldLength >= newLength) { | |
298 return; | |
299 } | |
300 | |
301 final Object[] newTable = new Object[newLength]; | |
302 threshold = newLength / 3; | |
303 | |
304 for (int i = 0; i < oldLength; i += 2) { | |
305 final Class<K> keyType = null; | |
306 final K key = Utils.cast(keyType, oldTable[i]); | |
307 if (key != null) { | |
308 final Object value = oldTable[i + 1]; | |
309 oldTable[i] = null; | |
310 oldTable[i + 1] = null; | |
311 final int hash = hash(hashCode(key)); | |
312 int index = indexFor(hash, newLength); | |
313 while (newTable[index] != null) { | |
314 index = nextKeyIndex(index, newLength); | |
315 } | |
316 newTable[index] = key; | |
317 newTable[index + 1] = value; | |
318 } | |
319 } | |
320 table = newTable; | |
321 } | |
322 | |
323 private abstract class HashIterator<Type> implements Iterator<Type> { | |
324 | |
325 /** | |
326 * Current slot. | |
327 */ | |
328 int index = numberOfEntries != 0 ? 0 : table.length; | |
329 | |
330 /** | |
331 * To avoid unnecessary next computation. | |
332 */ | |
333 boolean indexIsValid; | |
334 | |
335 public boolean hasNext() { | |
336 for (int i = index; i < table.length; i += 2) { | |
337 final Object key = table[i]; | |
338 if (key != null) { | |
339 index = i; | |
340 indexIsValid = true; | |
341 return true; | |
342 } | |
343 } | |
344 index = table.length; | |
345 return false; | |
346 } | |
347 | |
348 protected int nextIndex() { | |
349 if (!indexIsValid && !hasNext()) { | |
350 throw new NoSuchElementException(); | |
351 } | |
352 | |
353 indexIsValid = false; | |
354 final int lastReturnedIndex = index; | |
355 index += 2; | |
356 return lastReturnedIndex; | |
357 } | |
358 | |
359 public void remove() { | |
360 throw new UnsupportedOperationException(); | |
361 } | |
362 } | |
363 | |
364 private class KeyIterator extends HashIterator<K> { | |
365 public K next() { | |
366 final Class<K> keyType = null; | |
367 return Utils.cast(keyType, table[nextIndex()]); | |
368 } | |
369 } | |
370 | |
371 private class ValueIterator extends HashIterator<V> { | |
372 public V next() { | |
373 final Class<V> valueType = null; | |
374 return Utils.cast(valueType, table[nextIndex() + 1]); | |
375 } | |
376 } | |
377 | |
378 public IterableWithLength<K> keys() { | |
379 return new HashMappingIterable<K>() { | |
380 public Iterator<K> iterator() { | |
381 return new KeyIterator(); | |
382 } | |
383 }; | |
384 } | |
385 | |
386 @Override | |
387 public IterableWithLength<V> values() { | |
388 return new HashMappingIterable<V>() { | |
389 public Iterator<V> iterator() { | |
390 return new ValueIterator(); | |
391 } | |
392 }; | |
393 } | |
394 } |