1 /* Licensed to the Apache Software Foundation (ASF) under one or more 2 * contributor license agreements. See the NOTICE file distributed with 3 * this work for additional information regarding copyright ownership. 4 * The ASF licenses this file to You under the Apache License, Version 2.0 5 * (the "License"); you may not use this file except in compliance with 6 * the License. You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17 package java.util; 18 19 20 /** 21 * A concrete EnumSet for enums with more than 64 elements. 22 */ 23 @SuppressWarnings("serial") 24 final class HugeEnumSet<E extends Enum<E>> extends EnumSet<E> { 25 26 private static final int BIT_IN_LONG = 64; 27 28 final private E[] enums; 29 30 private long[] bits; 31 32 private int size; 33 34 /** 35 * Constructs an instance. 36 * 37 * @param elementType non-null; type of the elements 38 * @param enums non-null; pre-populated array of constants in ordinal 39 * order 40 */ 41 HugeEnumSet(Class<E> elementType, E[] enums) { 42 super(elementType); 43 this.enums = enums; 44 bits = new long[(enums.length + BIT_IN_LONG - 1) / BIT_IN_LONG]; 45 } 46 47 private class HugeEnumSetIterator implements Iterator<E> { 48 49 /** 50 * The bits yet to be returned for the long in bits[index]. As values from the current index 51 * are returned, their bits are zeroed out. When this reaches zero, the index must be 52 * incremented. 53 */ 54 private long currentBits = bits[0]; 55 56 /** 57 * The index into HugeEnumSet.bits of the next value to return. 58 */ 59 private int index; 60 61 /** 62 * The single bit of the next value to return. 63 */ 64 private long mask; 65 66 /** 67 * The candidate for removal. If null, no value may be removed. 68 */ 69 private E last; 70 71 private HugeEnumSetIterator() { 72 computeNextElement(); 73 } 74 75 /** 76 * Assigns mask and index to the next available value, cycling currentBits as necessary. 77 */ 78 void computeNextElement() { 79 while (true) { 80 if (currentBits != 0) { 81 mask = currentBits & -currentBits; // the lowest 1 bit in currentBits 82 return; 83 } else if (++index < bits.length) { 84 currentBits = bits[index]; 85 } else { 86 mask = 0; 87 return; 88 } 89 } 90 } 91 92 public boolean hasNext() { 93 return mask != 0; 94 } 95 96 public E next() { 97 if (mask == 0) { 98 throw new NoSuchElementException(); 99 } 100 101 int ordinal = Long.numberOfTrailingZeros(mask) + index * BIT_IN_LONG; 102 last = enums[ordinal]; 103 104 currentBits &= ~mask; 105 computeNextElement(); 106 107 return last; 108 } 109 110 public void remove() { 111 if (last == null) { 112 throw new IllegalStateException(); 113 } 114 115 HugeEnumSet.this.remove(last); 116 last = null; 117 } 118 } 119 120 @Override 121 public boolean add(E element) { 122 elementClass.cast(element); // Called to throw ClassCastException. 123 int ordinal = element.ordinal(); 124 int index = ordinal / BIT_IN_LONG; 125 int inBits = ordinal % BIT_IN_LONG; 126 long oldBits = bits[index]; 127 long newBits = oldBits | (1L << inBits); 128 if (oldBits != newBits) { 129 bits[index] = newBits; 130 size++; 131 return true; 132 } 133 return false; 134 } 135 136 @Override 137 public boolean addAll(Collection<? extends E> collection) { 138 if (collection.isEmpty() || collection == this) { 139 return false; 140 } 141 142 if (collection instanceof EnumSet) { 143 EnumSet<?> set = (EnumSet) collection; // raw type due to javac bug 6548436 144 set.elementClass.asSubclass(elementClass); // Called to throw ClassCastException. 145 146 HugeEnumSet<E> hugeSet = (HugeEnumSet<E>) set; 147 boolean changed = false; 148 for (int i = 0; i < bits.length; i++) { 149 long oldBits = bits[i]; 150 long newBits = oldBits | hugeSet.bits[i]; 151 if (oldBits != newBits) { 152 bits[i] = newBits; 153 size += Long.bitCount(newBits) - Long.bitCount(oldBits); 154 changed = true; 155 } 156 } 157 return changed; 158 } 159 return super.addAll(collection); 160 } 161 162 @Override 163 public int size() { 164 return size; 165 } 166 167 @Override 168 public void clear() { 169 Arrays.fill(bits, 0); 170 size = 0; 171 } 172 173 @Override 174 protected void complement() { 175 size = 0; 176 for (int i = 0, length = bits.length; i < length; i++) { 177 long b = ~bits[i]; 178 179 // zero out unused bits on the last element 180 if (i == length - 1) { 181 b &= -1L >>> (BIT_IN_LONG - (enums.length % BIT_IN_LONG)); 182 } 183 184 size += Long.bitCount(b); 185 bits[i] = b; 186 } 187 } 188 189 @Override 190 public boolean contains(Object object) { 191 if (object == null || !isValidType(object.getClass())) { 192 return false; 193 } 194 195 @SuppressWarnings("unchecked") // guarded by isValidType() 196 int ordinal = ((E) object).ordinal(); 197 int index = ordinal / BIT_IN_LONG; 198 int inBits = ordinal % BIT_IN_LONG; 199 return (bits[index] & (1L << inBits)) != 0; 200 } 201 202 @Override 203 public HugeEnumSet<E> clone() { 204 HugeEnumSet<E> set = (HugeEnumSet<E>) super.clone(); 205 set.bits = bits.clone(); 206 return set; 207 } 208 209 @Override 210 public boolean containsAll(Collection<?> collection) { 211 if (collection.isEmpty()) { 212 return true; 213 } 214 if (collection instanceof HugeEnumSet) { 215 HugeEnumSet<?> set = (HugeEnumSet<?>) collection; 216 if (isValidType(set.elementClass)) { 217 for (int i = 0; i < bits.length; i++) { 218 long setBits = set.bits[i]; 219 if ((bits[i] & setBits) != setBits) { 220 return false; 221 } 222 } 223 return true; 224 } 225 } 226 return !(collection instanceof EnumSet) && super.containsAll(collection); 227 } 228 229 @Override 230 public boolean equals(Object object) { 231 if (object == null) { 232 return false; 233 } 234 if (!isValidType(object.getClass())) { 235 return super.equals(object); 236 } 237 return Arrays.equals(bits, ((HugeEnumSet<?>) object).bits); 238 } 239 240 @Override 241 public Iterator<E> iterator() { 242 return new HugeEnumSetIterator(); 243 } 244 245 @Override 246 public boolean remove(Object object) { 247 if (object == null || !isValidType(object.getClass())) { 248 return false; 249 } 250 251 @SuppressWarnings("unchecked") // guarded by isValidType() 252 int ordinal = ((E) object).ordinal(); 253 int index = ordinal / BIT_IN_LONG; 254 int inBits = ordinal % BIT_IN_LONG; 255 long oldBits = bits[index]; 256 long newBits = oldBits & ~(1L << inBits); 257 if (oldBits != newBits) { 258 bits[index] = newBits; 259 size--; 260 return true; 261 } 262 return false; 263 } 264 265 @Override 266 public boolean removeAll(Collection<?> collection) { 267 if (collection.isEmpty()) { 268 return false; 269 } 270 271 if (collection instanceof EnumSet) { 272 EnumSet<?> set = (EnumSet<?>) collection; 273 if (!isValidType(set.elementClass)) { 274 return false; 275 } 276 277 HugeEnumSet<E> hugeSet = (HugeEnumSet<E>) set; 278 boolean changed = false; 279 for (int i = 0; i < bits.length; i++) { 280 long oldBits = bits[i]; 281 long newBits = oldBits & ~hugeSet.bits[i]; 282 if (oldBits != newBits) { 283 bits[i] = newBits; 284 size += Long.bitCount(newBits) - Long.bitCount(oldBits); 285 changed = true; 286 } 287 } 288 return changed; 289 } 290 return super.removeAll(collection); 291 } 292 293 @Override 294 public boolean retainAll(Collection<?> collection) { 295 if (collection instanceof EnumSet) { 296 EnumSet<?> set = (EnumSet<?>) collection; 297 if (!isValidType(set.elementClass)) { 298 if (size > 0) { 299 clear(); 300 return true; 301 } else { 302 return false; 303 } 304 } 305 306 HugeEnumSet<E> hugeSet = (HugeEnumSet<E>) set; 307 boolean changed = false; 308 for (int i = 0; i < bits.length; i++) { 309 long oldBits = bits[i]; 310 long newBits = oldBits & hugeSet.bits[i]; 311 if (oldBits != newBits) { 312 bits[i] = newBits; 313 size += Long.bitCount(newBits) - Long.bitCount(oldBits); 314 changed = true; 315 } 316 } 317 return changed; 318 } 319 return super.retainAll(collection); 320 } 321 322 @Override 323 void setRange(E start, E end) { 324 int startOrdinal = start.ordinal(); 325 int startIndex = startOrdinal / BIT_IN_LONG; 326 int startInBits = startOrdinal % BIT_IN_LONG; 327 328 int endOrdinal = end.ordinal(); 329 int endIndex = endOrdinal / BIT_IN_LONG; 330 int endInBits = endOrdinal % BIT_IN_LONG; 331 332 if (startIndex == endIndex) { 333 long range = (-1L >>> (BIT_IN_LONG -(endInBits - startInBits + 1))) << startInBits; 334 size -= Long.bitCount(bits[startIndex]); 335 bits[startIndex] |= range; 336 size += Long.bitCount(bits[startIndex]); 337 338 } else { 339 long range = (-1L >>> startInBits) << startInBits; 340 size -= Long.bitCount(bits[startIndex]); 341 bits[startIndex] |= range; 342 size += Long.bitCount(bits[startIndex]); 343 344 // endInBits + 1 is the number of consecutive ones. 345 // 63 - endInBits is the following zeros of the right most one. 346 range = -1L >>> (BIT_IN_LONG - (endInBits + 1)); 347 size -= Long.bitCount(bits[endIndex]); 348 bits[endIndex] |= range; 349 size += Long.bitCount(bits[endIndex]); 350 for (int i = (startIndex + 1); i <= (endIndex - 1); i++) { 351 size -= Long.bitCount(bits[i]); 352 bits[i] = -1L; 353 size += Long.bitCount(bits[i]); 354 } 355 } 356 } 357 } 358
