--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/graal/com.oracle.max.base/src/com/sun/max/collect/OpenAddressingHashMapping.java	Sat Dec 17 19:59:18 2011 +0100
@@ -0,0 +1,394 @@
+/*
+ * 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();
+            }
+        };
+    }
+}