Mercurial > hg > truffle

comparison graal/com.oracle.max.base/src/com/sun/max/collect/PoolSet64.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 bc8527f3071c
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.lang.*;
28
29 /**
30 * A compact and efficient implementation of a {@link PoolSet} for pools with 64 objects or less.
31 *
32 * While it's possible to create an instance of this class directly, the preferred way to create a pool set is described
33 * {@linkplain PoolSet here}.
34 */
35 public class PoolSet64<T extends PoolObject> extends PoolSet<T> {
36
37 public static final int MAX_POOL_SIZE = 64;
38
39 /**
40 * Bit vector representation of this set. The 2^k bit indicates the presence of _pool.get(k) in this set.
41 */
42 private long set;
43
44 /**
45 * Creates an empty pool set for a pool with 64objects or less.
46 */
47 public PoolSet64(Pool<T> pool) {
48 super(pool);
49 assert pool.length() <= MAX_POOL_SIZE : pool.length() + " > " + MAX_POOL_SIZE;
50 }
51
52 @Override
53 public int size() {
54 return Long.bitCount(set);
55 }
56
57 @Override
58 public void clear() {
59 set = 0L;
60 }
61
62 @Override
63 public boolean isEmpty() {
64 return set == 0L;
65 }
66
67 private static int bitToSerial(long bit) {
68 assert bit != 0 && Longs.isPowerOfTwoOrZero(bit);
69 return Long.numberOfTrailingZeros(bit);
70 }
71
72 private static long serialToBit(int serial) {
73 assert serial >= 0 && serial < MAX_POOL_SIZE;
74 return 1L << serial;
75 }
76
77 @Override
78 public boolean contains(T value) {
79 if (value == null) {
80 return false;
81 }
82
83 final int serial = value.serial();
84 assert pool.get(serial) == value;
85 return (serialToBit(serial) & set) != 0;
86 }
87
88 @Override
89 public void add(T value) {
90 final int serial = value.serial();
91 assert pool.get(serial) == value;
92 set |= serialToBit(serial);
93 }
94
95 @Override
96 public PoolSet64<T> addAll() {
97 final int poolLength = pool.length();
98 if (poolLength != 0) {
99 final long highestBit = 1L << poolLength - 1;
100 set = highestBit | (highestBit - 1);
101 assert size() == poolLength;
102 }
103 return this;
104 }
105
106 @Override
107 public void or(PoolSet<T> others) {
108 if (others instanceof PoolSet64) {
109 final PoolSet64 poolSet64 = (PoolSet64) others;
110 set |= poolSet64.set;
111 } else {
112 if (!others.isEmpty()) {
113 for (T element : others) {
114 add(element);
115 }
116 }
117 }
118 }
119
120 @Override
121 public boolean remove(T value) {
122 if (!isEmpty()) {
123 final int serial = value.serial();
124 assert pool.get(serial) == value;
125 final long bit = serialToBit(serial);
126 final boolean present = (set & bit) != 0;
127 set &= ~bit;
128 return present;
129 }
130 return false;
131 }
132
133 @Override
134 public T removeOne() {
135 if (isEmpty()) {
136 throw new NoSuchElementException();
137 }
138 final long bit = Long.lowestOneBit(set);
139 set &= ~bit;
140 return pool.get(bitToSerial(bit));
141 }
142
143 @Override
144 public void and(PoolSet<T> others) {
145 if (others instanceof PoolSet64) {
146 final PoolSet64 poolSet64 = (PoolSet64) others;
147 set &= poolSet64.set;
148 } else {
149 long oldSet = this.set;
150 while (oldSet != 0) {
151 final long bit = Long.lowestOneBit(oldSet);
152 final int serial = bitToSerial(bit);
153 oldSet &= ~bit;
154 if (!others.contains(pool.get(serial))) {
155 this.set &= ~bit;
156 }
157 }
158 }
159 }
160
161 @Override
162 public boolean containsAll(PoolSet<T> others) {
163 if (others instanceof PoolSet64) {
164 final PoolSet64 poolSet64 = (PoolSet64) others;
165 return (set & poolSet64.set) == poolSet64.set;
166 }
167 return super.containsAll(others);
168 }
169
170 @Override
171 public PoolSet<T> clone() {
172 final PoolSet64<T> clone = new PoolSet64<T>(pool);
173 clone.set = set;
174 return clone;
175 }
176
177 /**
178 * Gets an iterator over all the values in this set.
179 */
180 public Iterator<T> iterator() {
181 return new Iterator<T>() {
182
183 private long current = set;
184 private long currentBit = -1L;
185 private long nextSetBit = Long.lowestOneBit(set);
186
187 public boolean hasNext() {
188 return current != 0;
189 }
190
191 public T next() {
192 if (!hasNext()) {
193 throw new NoSuchElementException();
194 }
195
196 currentBit = Long.lowestOneBit(current);
197 final int serial = bitToSerial(currentBit);
198 current &= ~currentBit;
199 return pool.get(serial);
200 }
201
202 public void remove() {
203 if (currentBit == -1L) {
204 throw new IllegalStateException();
205 }
206
207 set &= ~currentBit;
208 currentBit = -1;
209 }
210 };
211 }
212 }