Mercurial > hg > truffle
view graal/com.oracle.max.base/src/com/sun/max/collect/IdentitySet.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.*; /** * Similar to IdentityHashSet, but not recording 'null' as a set member * and not providing any element removal operations. * * (IdentityHashSet's iterator seems to return 'null' as a member even if it has never been entered.) */ public class IdentitySet<T> implements Iterable<T> { /** * The default initial capacity - MUST be a power of two. */ public static final int DEFAULT_INITIAL_CAPACITY = 16; /** * 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<<30. */ public static final int MAXIMUM_CAPACITY = 1 << 30; // Note: this implementation is partly derived from java.util.HashMap in the standard JDK // In particular, it uses a table whose length is guaranteed to be a power of 2. /** * The number of key-value mappings contained in this map. */ private int numberOfElements; /** * Gets the number of key-value mappings contained in this map. */ public int numberOfElements() { return numberOfElements; } /** * The table, resized as necessary. Length MUST Always be a power of two. */ private T[] table; /** * The next size value at which to resize (capacity * load factor). */ private int threshold; private void setThreshold() { if (table.length == 0) { threshold = -1; } else { threshold = (table.length >> 2) * 3; } } /** * Constructs a new, empty IdentitySet. */ public IdentitySet() { this(DEFAULT_INITIAL_CAPACITY); } /** * Constructs a new, empty IdentitySet. * @param initialCapacity the initial capacity of the Set * @throws {@code IllegalArgumentException} if {@code initialCapacity} is less than zero} */ public IdentitySet(int initialCapacity) { if (initialCapacity < 0) { throw new IllegalArgumentException(); } // Find a power of 2 >= initialCapacity int capacity = Integer.highestOneBit(Math.max(Math.min(MAXIMUM_CAPACITY, initialCapacity), 1)); if (capacity < initialCapacity) { capacity <<= 1; } final Class<T[]> type = null; table = Utils.cast(type, new Object[capacity]); setThreshold(); } private void resize(int newTableLength) { final T[] oldTable = table; final Class<T[]> type = null; table = Utils.cast(type, new Object[newTableLength]); setThreshold(); numberOfElements = 0; for (int i = 0; i < oldTable.length; i++) { final T oldValue = oldTable[i]; if (oldValue != null) { add(oldValue); } } } /** * 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) { return h & (length - 1); } /** * Adds a given element to this set. * * @param element the element to add * @throws IllegalArgumentException if {@code element == null} */ public void add(T element) { if (element == null) { throw new IllegalArgumentException("Element cannot be null"); } if (numberOfElements > threshold) { resize(table.length * 2); } final int start = indexFor(System.identityHashCode(element), table.length); int i = start; do { final T entry = table[i]; if (entry == null) { table[i] = element; numberOfElements++; return; } if (entry == element) { return; } if (++i == table.length) { i = 0; } } while (i != start); } /** * Determines if a given element is a member of this set. * * @param element the element to test for membership in this set * @return {@code true} if {@code element} is in this set, {@code false} otherwise * @throws IllegalArgumentException if {@code element == null} */ public boolean contains(T element) { if (element == null) { throw new IllegalArgumentException("Element cannot be null"); } if (numberOfElements == 0) { return false; } final int start = indexFor(System.identityHashCode(element), table.length); int i = start; while (true) { final T entry = table[i]; if (entry == element) { return true; } if (entry == null) { return false; } if (++i == table.length) { i = 0; } assert i != start; } } public Iterator<T> iterator() { final Class<T[]> type = null; final T[] array = Utils.cast(type, new Object[numberOfElements()]); int j = 0; for (int i = 0; i < table.length; i++) { final T element = table[i]; if (element != null) { array[j++] = element; } } return Arrays.asList(array).iterator(); } }