Mercurial > hg > truffle

comparison graal/com.oracle.max.base/src/com/sun/max/collect/OpenAddressingHashMapping.java @ 3733:e233f5660da4

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
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 }