Mercurial > hg > truffle
view graal/com.oracle.max.base/src/com/sun/max/collect/PoolSet128.java @ 4240:394424b7df1a
Disabled certain DaCapo tests for fastdebug testing in the gate.
author | Doug Simon <doug.simon@oracle.com> |
---|---|
date | Fri, 06 Jan 2012 18:35:39 +0100 |
parents | bc8527f3071c |
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.lang.*; /** * A compact and efficient implementation of a {@link PoolSet} for pools with 128 objects or less. * * While it's possible to create an instance of this class directly, the preferred way to create a pool set is described * {@linkplain PoolSet here}. */ public class PoolSet128<T extends PoolObject> extends PoolSet<T> { public static final int MAX_POOL_SIZE = 128; /** * Bit vector representation of the low part of this set. The 2^k bit indicates the presence of _pool.get(k) in this set. */ private long setLow; /** * Bit vector representation of the low part of this set. The 2^k bit indicates the presence of _pool.get(k + 64) in this set. */ private long setHigh; /** * Creates an empty pool set for a pool with 128 objects or less. */ public PoolSet128(Pool<T> pool) { super(pool); assert pool.length() <= MAX_POOL_SIZE : pool.length() + " > " + MAX_POOL_SIZE; } @Override public int size() { return Long.bitCount(setLow) + Long.bitCount(setHigh); } @Override public void clear() { setLow = 0L; setHigh = 0L; } @Override public boolean isEmpty() { return setLow == 0L && setHigh == 0L; } private static int bitToSerial(long bit) { assert bit != 0 && Longs.isPowerOfTwoOrZero(bit); return Long.numberOfTrailingZeros(bit); } private static long serialToBit(int serial) { assert serial >= 0 && serial < MAX_POOL_SIZE; return 1L << serial; } @Override public boolean contains(T value) { if (value == null) { return false; } final int serial = value.serial(); assert pool.get(serial) == value; if (serial < 64) { return (serialToBit(serial) & setLow) != 0; } return (serialToBit(serial - 64) & setHigh) != 0; } @Override public void add(T value) { final int serial = value.serial(); assert pool.get(serial) == value; if (serial < 64) { setLow |= serialToBit(serial); } else { setHigh |= serialToBit(serial - 64); } } @Override public PoolSet128<T> addAll() { final int poolLength = pool.length(); if (poolLength == 0) { return this; } if (poolLength <= 64) { final long highestBit = 1L << poolLength - 1; setLow = highestBit | (highestBit - 1); } else { final long highestBit = 1L << (poolLength - 64) - 1; setHigh = highestBit | (highestBit - 1); setLow = -1L; } assert size() == poolLength; return this; } @Override public void or(PoolSet<T> others) { if (others instanceof PoolSet128) { final PoolSet128 poolSet128 = (PoolSet128) others; setLow |= poolSet128.setLow; setHigh |= poolSet128.setHigh; } else { if (!others.isEmpty()) { for (T element : others) { add(element); } } } } @Override public boolean remove(T value) { if (!isEmpty()) { final int serial = value.serial(); assert pool.get(serial) == value; final boolean present; if (serial < 64) { final long bit = serialToBit(serial); present = (bit & setLow) != 0; setLow &= ~bit; } else { final long bit = serialToBit(serial - 64); present = (bit & setHigh) != 0; setHigh &= ~bit; } return present; } return false; } @Override public T removeOne() { if (isEmpty()) { throw new NoSuchElementException(); } long bit = Long.lowestOneBit(setLow); if (bit != 0) { setLow &= ~bit; return pool.get(bitToSerial(bit)); } bit = Long.lowestOneBit(setHigh); assert bit != 0; setHigh &= ~bit; return pool.get(bitToSerial(bit) + 64); } @Override public void and(PoolSet<T> others) { if (others instanceof PoolSet128) { final PoolSet128 poolSet128 = (PoolSet128) others; setLow &= poolSet128.setLow; setHigh &= poolSet128.setHigh; } else { long oldSetLow = this.setLow; while (oldSetLow != 0) { final long bit = Long.lowestOneBit(oldSetLow); final int serial = bitToSerial(bit); oldSetLow &= ~bit; if (!others.contains(pool.get(serial))) { this.setLow &= ~bit; } } long oldSetHigh = this.setHigh; while (oldSetHigh != 0) { final long bit = Long.lowestOneBit(oldSetHigh); final int serial = bitToSerial(bit) + 64; oldSetHigh &= ~bit; if (!others.contains(pool.get(serial))) { this.setHigh &= ~bit; } } } } @Override public boolean containsAll(PoolSet<T> others) { if (others instanceof PoolSet128) { final PoolSet128 poolSet128 = (PoolSet128) others; return (setLow & poolSet128.setLow) == poolSet128.setLow && (setHigh & poolSet128.setHigh) == poolSet128.setHigh; } return super.containsAll(others); } @Override public PoolSet<T> clone() { final PoolSet128<T> poolSet = new PoolSet128<>(pool); poolSet.setLow = setLow; poolSet.setHigh = setHigh; return poolSet; } /** * Gets an iterator over all the values in this set. */ public Iterator<T> iterator() { return new Iterator<T>() { private int count = size(); private boolean inHighSet; private long current = setLow; private long currentBit = -1L; public boolean hasNext() { return count != 0; } public T next() { if (!hasNext()) { throw new NoSuchElementException(); } currentBit = Long.lowestOneBit(current); if (currentBit == 0) { assert !inHighSet; inHighSet = true; current = setHigh; currentBit = Long.lowestOneBit(current); } final int serial = bitToSerial(currentBit); current &= ~currentBit; count--; if (inHighSet) { return pool.get(serial + 64); } return pool.get(serial); } public void remove() { if (currentBit == -1L) { throw new IllegalStateException(); } if (inHighSet) { setHigh &= ~currentBit; } else { setLow &= ~currentBit; } currentBit = -1; } }; } }