Mercurial > hg > truffle
view graal/com.oracle.max.base/src/com/sun/max/collect/OpenAddressingHashMapping.java @ 4266:e2499e6d8aa7
Merge
author | Lukas Stadler <lukas.stadler@jku.at> |
---|---|
date | Wed, 11 Jan 2012 16:31:46 +0100 |
parents | e233f5660da4 |
children |
line wrap: on
line source
/* * Copyright (c) 2007, 2011, Oracle and/or its affiliates. All rights reserved. * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. * * This code is free software; you can redistribute it and/or modify it * under the terms of the GNU General Public License version 2 only, as * published by the Free Software Foundation. * * This code is distributed in the hope that it will be useful, but WITHOUT * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License * version 2 for more details (a copy is included in the LICENSE file that * accompanied this code). * * You should have received a copy of the GNU General Public License version * 2 along with this work; if not, write to the Free Software Foundation, * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. * * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA * or visit www.oracle.com if you need additional information or have any * questions. */ package com.sun.max.collect; import java.util.*; import com.sun.max.*; import com.sun.max.lang.*; /** * An open addressing hash table with liner probe hash collision resolution. */ public class OpenAddressingHashMapping<K, V> extends HashMapping<K, V> implements Mapping<K, V> { // Note: this implementation is partly derived from java.util.IdentityHashMap in the standard JDK /** * The initial capacity used by the no-args constructor. * MUST be a power of two. The value 32 corresponds to the * (specified) expected maximum size of 21, given a load factor * of 2/3. */ private static final int DEFAULT_CAPACITY = 32; /** * The minimum capacity, used if a lower value is implicitly specified * by either of the constructors with arguments. The value 4 corresponds * to an expected maximum size of 2, given a load factor of 2/3. * MUST be a power of two. */ private static final int MINIMUM_CAPACITY = 4; /** * The maximum capacity, used if a higher value is implicitly specified * by either of the constructors with arguments. * MUST be a power of two <= 1<<29. */ private static final int MAXIMUM_CAPACITY = 1 << 29; /** * The table, resized as necessary. Length MUST always be a power of two. */ private Object[] table; /** * Returns the appropriate capacity for the specified expected maximum * size. Returns the smallest power of two between MINIMUM_CAPACITY * and MAXIMUM_CAPACITY, inclusive, that is greater than * (3 * expectedMaxSize)/2, if such a number exists. Otherwise * returns MAXIMUM_CAPACITY. If (3 * expectedMaxSize)/2 is negative, it * is assumed that overflow has occurred, and MAXIMUM_CAPACITY is returned. */ private static int capacity(int expectedMaxSize) { // Compute minimum capacity for expectedMaxSize given a load factor of 2/3 final int minimumCapacity = (3 * expectedMaxSize) >> 1; // Compute the appropriate capacity int result; if (minimumCapacity > MAXIMUM_CAPACITY || minimumCapacity < 0) { result = MAXIMUM_CAPACITY; } else { result = MINIMUM_CAPACITY; while (result < minimumCapacity) { result <<= 1; } } return result; } /** * Constructs a new, empty open addressing hash table with {@linkplain HashEquality equality} key semantics and a * default expected maximum size of 21. */ public OpenAddressingHashMapping() { this(null); } /** * Constructs a new, empty open addressing hash table with a default expected maximum size of 21. * * @param equivalence * the semantics to be used for comparing keys. If {@code null} is provided, then {@link HashEquality} is * used. */ public OpenAddressingHashMapping(HashEquivalence<K> equivalence) { this(equivalence, (DEFAULT_CAPACITY * 2) / 3); } /** * Constructs a new, empty open addressing hash table with {@linkplain HashEquality equality} key semantics. * * @param expectedMaximumSize * the expected maximum size of the map */ public OpenAddressingHashMapping(int expectedMaximumSize) { this(null, expectedMaximumSize); } /** * Constructs a new, empty open addressing hash table with the specified expected maximum size. Putting more than * the expected number of key-value mappings into the map may cause the internal data structure to grow, which may * be somewhat time-consuming. * * @param equivalence * the semantics to be used for comparing keys. If {@code null} is provided, then {@link HashEquality} is * used. * @param expectedMaximumSize * the expected maximum size of the map * @throws IllegalArgumentException * if {@code expectedMaximumSize} is negative */ public OpenAddressingHashMapping(HashEquivalence<K> equivalence, int expectedMaximumSize) { super(equivalence); if (expectedMaximumSize < 0) { throw new IllegalArgumentException("Illegal initial capacity: " + expectedMaximumSize); } // Find a power of 2 >= initialCapacity final int capacity = capacity(expectedMaximumSize); threshold = (capacity * 2) / 3; table = new Object[capacity * 2]; } private int numberOfEntries; private int threshold; public int length() { return numberOfEntries; } /** * Applies a supplemental hash function to a given hashCode, which * defends against poor quality hash functions. This is critical * because BuckHashMapping uses power-of-two length hash tables, that * otherwise encounter collisions for hashCodes that do not differ * in lower bits. */ static int hash(int hash) { // This function ensures that hashCodes that differ only by // constant multiples at each bit position have a bounded // number of collisions (approximately 8 at default load factor). final int h = hash ^ ((hash >>> 20) ^ (hash >>> 12)); return h ^ (h >>> 7) ^ (h >>> 4); } /** * Returns index for hash code h. */ static int indexFor(int h, int length) { // Multiply by -127, and left-shift to use least bit as part of hash final int index = ((h << 1) - (h << 8)) & (length - 1); assert (index & 1) == 0 : "index must be even"; return index; } /** * Circularly traverses table of size {@code length}. */ private static int nextKeyIndex(int i, int length) { return i + 2 < length ? i + 2 : 0; } public V get(K key) { if (key == null) { throw new IllegalArgumentException("Key cannot be null"); } final Object[] tbl = this.table; final int length = tbl.length; final int hash = hash(hashCode(key)); int index = indexFor(hash, tbl.length); while (true) { final Object item = tbl[index]; final Class<K> keyType = null; final K entryKey = Utils.cast(keyType, item); if (equivalent(entryKey, key)) { final Class<V> valueType = null; return Utils.cast(valueType, tbl[index + 1]); } if (item == null) { return null; } index = nextKeyIndex(index, length); } } public V put(K key, V value) { if (key == null) { throw new IllegalArgumentException("Key cannot be null"); } if (value == null) { throw new IllegalArgumentException("Value cannot be null"); } final Object[] tbl = this.table; final int length = tbl.length; final int hash = hash(hashCode(key)); int index = indexFor(hash, tbl.length); Object item = tbl[index]; while (item != null) { final Class<K> keyType = null; final K entryKey = Utils.cast(keyType, item); if (equivalent(entryKey, key)) { final Class<V> valueType = null; final V oldValue = Utils.cast(valueType, tbl[index + 1]); tbl[index + 1] = value; return oldValue; } index = nextKeyIndex(index, length); item = tbl[index]; } tbl[index] = key; tbl[index + 1] = value; if (numberOfEntries++ >= threshold) { resize(length); // length == 2 * current capacity. } return null; } public V remove(K key) { if (key == null) { throw new IllegalArgumentException("Key cannot be null"); } final Object[] tbl = this.table; final int length = tbl.length; final int hash = hash(hashCode(key)); int index = indexFor(hash, tbl.length); while (true) { final Object item = tbl[index]; final Class<K> keyType = null; final K entryKey = Utils.cast(keyType, item); if (equivalent(entryKey, key)) { numberOfEntries--; final Class<V> valueType = null; final V oldValue = Utils.cast(valueType, tbl[index + 1]); tbl[index + 1] = null; tbl[index] = null; return oldValue; } if (item == null) { return null; } index = nextKeyIndex(index, length); } } public void clear() { for (int i = 0; i != table.length; ++i) { table[i] = null; } numberOfEntries = 0; } /** * Resize the table to hold given capacity. * * @param newCapacity the new capacity, must be a power of two. */ private void resize(int newCapacity) { assert Ints.isPowerOfTwoOrZero(newCapacity) : "newCapacity must be a power of 2"; final int newLength = newCapacity * 2; final Object[] oldTable = table; final int oldLength = oldTable.length; if (oldLength == 2 * MAXIMUM_CAPACITY) { // can't expand any further if (threshold == MAXIMUM_CAPACITY - 1) { throw new IllegalStateException("Capacity exhausted."); } threshold = MAXIMUM_CAPACITY - 1; // Gigantic map! return; } if (oldLength >= newLength) { return; } final Object[] newTable = new Object[newLength]; threshold = newLength / 3; for (int i = 0; i < oldLength; i += 2) { final Class<K> keyType = null; final K key = Utils.cast(keyType, oldTable[i]); if (key != null) { final Object value = oldTable[i + 1]; oldTable[i] = null; oldTable[i + 1] = null; final int hash = hash(hashCode(key)); int index = indexFor(hash, newLength); while (newTable[index] != null) { index = nextKeyIndex(index, newLength); } newTable[index] = key; newTable[index + 1] = value; } } table = newTable; } private abstract class HashIterator<Type> implements Iterator<Type> { /** * Current slot. */ int index = numberOfEntries != 0 ? 0 : table.length; /** * To avoid unnecessary next computation. */ boolean indexIsValid; public boolean hasNext() { for (int i = index; i < table.length; i += 2) { final Object key = table[i]; if (key != null) { index = i; indexIsValid = true; return true; } } index = table.length; return false; } protected int nextIndex() { if (!indexIsValid && !hasNext()) { throw new NoSuchElementException(); } indexIsValid = false; final int lastReturnedIndex = index; index += 2; return lastReturnedIndex; } public void remove() { throw new UnsupportedOperationException(); } } private class KeyIterator extends HashIterator<K> { public K next() { final Class<K> keyType = null; return Utils.cast(keyType, table[nextIndex()]); } } private class ValueIterator extends HashIterator<V> { public V next() { final Class<V> valueType = null; return Utils.cast(valueType, table[nextIndex() + 1]); } } public IterableWithLength<K> keys() { return new HashMappingIterable<K>() { public Iterator<K> iterator() { return new KeyIterator(); } }; } @Override public IterableWithLength<V> values() { return new HashMappingIterable<V>() { public Iterator<V> iterator() { return new ValueIterator(); } }; } }