Mercurial > hg > truffle
comparison graal/com.oracle.max.base/src/com/sun/max/collect/PoolSet64.java @ 3733:e233f5660da4
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 } |