1 /*
2  * Copyright (c) 2003, 2019, 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.  Oracle designates this
8  * particular file as subject to the "Classpath" exception as provided
9  * by Oracle in the LICENSE file that accompanied this code.
10  *
11  * This code is distributed in the hope that it will be useful, but WITHOUT
12  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
14  * version 2 for more details (a copy is included in the LICENSE file that
15  * accompanied this code).
16  *
17  * You should have received a copy of the GNU General Public License version
18  * 2 along with this work; if not, write to the Free Software Foundation,
19  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
20  *
21  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
22  * or visit www.oracle.com if you need additional information or have any
23  * questions.
24  */
25 
26 package java.util;
27 
28 /**
29  * Private implementation class for EnumSet, for "jumbo" enum types
30  * (i.e., those with more than 64 elements).
31  *
32  * @author Josh Bloch
33  * @since 1.5
34  * @serial exclude
35  */
36 class JumboEnumSet<E extends Enum<E>> extends EnumSet<E> {
37     @java.io.Serial
38     private static final long serialVersionUID = 334349849919042784L;
39 
40     /**
41      * Bit vector representation of this set.  The ith bit of the jth
42      * element of this array represents the  presence of universe[64*j +i]
43      * in this set.
44      */
45     private long elements[];
46 
47     // Redundant - maintained for performance
48     private int size = 0;
49 
JumboEnumSet(Class<E>elementType, Enum<?>[] universe)50     JumboEnumSet(Class<E>elementType, Enum<?>[] universe) {
51         super(elementType, universe);
52         elements = new long[(universe.length + 63) >>> 6];
53     }
54 
addRange(E from, E to)55     void addRange(E from, E to) {
56         int fromIndex = from.ordinal() >>> 6;
57         int toIndex = to.ordinal() >>> 6;
58 
59         if (fromIndex == toIndex) {
60             elements[fromIndex] = (-1L >>>  (from.ordinal() - to.ordinal() - 1))
61                             << from.ordinal();
62         } else {
63             elements[fromIndex] = (-1L << from.ordinal());
64             for (int i = fromIndex + 1; i < toIndex; i++)
65                 elements[i] = -1;
66             elements[toIndex] = -1L >>> (63 - to.ordinal());
67         }
68         size = to.ordinal() - from.ordinal() + 1;
69     }
70 
addAll()71     void addAll() {
72         for (int i = 0; i < elements.length; i++)
73             elements[i] = -1;
74         elements[elements.length - 1] >>>= -universe.length;
75         size = universe.length;
76     }
77 
complement()78     void complement() {
79         for (int i = 0; i < elements.length; i++)
80             elements[i] = ~elements[i];
81         elements[elements.length - 1] &= (-1L >>> -universe.length);
82         size = universe.length - size;
83     }
84 
85     /**
86      * Returns an iterator over the elements contained in this set.  The
87      * iterator traverses the elements in their <i>natural order</i> (which is
88      * the order in which the enum constants are declared). The returned
89      * Iterator is a "weakly consistent" iterator that will never throw {@link
90      * ConcurrentModificationException}.
91      *
92      * @return an iterator over the elements contained in this set
93      */
iterator()94     public Iterator<E> iterator() {
95         return new EnumSetIterator<>();
96     }
97 
98     private class EnumSetIterator<E extends Enum<E>> implements Iterator<E> {
99         /**
100          * A bit vector representing the elements in the current "word"
101          * of the set not yet returned by this iterator.
102          */
103         long unseen;
104 
105         /**
106          * The index corresponding to unseen in the elements array.
107          */
108         int unseenIndex = 0;
109 
110         /**
111          * The bit representing the last element returned by this iterator
112          * but not removed, or zero if no such element exists.
113          */
114         long lastReturned = 0;
115 
116         /**
117          * The index corresponding to lastReturned in the elements array.
118          */
119         int lastReturnedIndex = 0;
120 
EnumSetIterator()121         EnumSetIterator() {
122             unseen = elements[0];
123         }
124 
125         @Override
hasNext()126         public boolean hasNext() {
127             while (unseen == 0 && unseenIndex < elements.length - 1)
128                 unseen = elements[++unseenIndex];
129             return unseen != 0;
130         }
131 
132         @Override
133         @SuppressWarnings("unchecked")
next()134         public E next() {
135             if (!hasNext())
136                 throw new NoSuchElementException();
137             lastReturned = unseen & -unseen;
138             lastReturnedIndex = unseenIndex;
139             unseen -= lastReturned;
140             return (E) universe[(lastReturnedIndex << 6)
141                                 + Long.numberOfTrailingZeros(lastReturned)];
142         }
143 
144         @Override
remove()145         public void remove() {
146             if (lastReturned == 0)
147                 throw new IllegalStateException();
148             final long oldElements = elements[lastReturnedIndex];
149             elements[lastReturnedIndex] &= ~lastReturned;
150             if (oldElements != elements[lastReturnedIndex]) {
151                 size--;
152             }
153             lastReturned = 0;
154         }
155     }
156 
157     /**
158      * Returns the number of elements in this set.
159      *
160      * @return the number of elements in this set
161      */
size()162     public int size() {
163         return size;
164     }
165 
166     /**
167      * Returns {@code true} if this set contains no elements.
168      *
169      * @return {@code true} if this set contains no elements
170      */
isEmpty()171     public boolean isEmpty() {
172         return size == 0;
173     }
174 
175     /**
176      * Returns {@code true} if this set contains the specified element.
177      *
178      * @param e element to be checked for containment in this collection
179      * @return {@code true} if this set contains the specified element
180      */
contains(Object e)181     public boolean contains(Object e) {
182         if (e == null)
183             return false;
184         Class<?> eClass = e.getClass();
185         if (eClass != elementType && eClass.getSuperclass() != elementType)
186             return false;
187 
188         int eOrdinal = ((Enum<?>)e).ordinal();
189         return (elements[eOrdinal >>> 6] & (1L << eOrdinal)) != 0;
190     }
191 
192     // Modification Operations
193 
194     /**
195      * Adds the specified element to this set if it is not already present.
196      *
197      * @param e element to be added to this set
198      * @return {@code true} if the set changed as a result of the call
199      *
200      * @throws NullPointerException if {@code e} is null
201      */
add(E e)202     public boolean add(E e) {
203         typeCheck(e);
204 
205         int eOrdinal = e.ordinal();
206         int eWordNum = eOrdinal >>> 6;
207 
208         long oldElements = elements[eWordNum];
209         elements[eWordNum] |= (1L << eOrdinal);
210         boolean result = (elements[eWordNum] != oldElements);
211         if (result)
212             size++;
213         return result;
214     }
215 
216     /**
217      * Removes the specified element from this set if it is present.
218      *
219      * @param e element to be removed from this set, if present
220      * @return {@code true} if the set contained the specified element
221      */
remove(Object e)222     public boolean remove(Object e) {
223         if (e == null)
224             return false;
225         Class<?> eClass = e.getClass();
226         if (eClass != elementType && eClass.getSuperclass() != elementType)
227             return false;
228         int eOrdinal = ((Enum<?>)e).ordinal();
229         int eWordNum = eOrdinal >>> 6;
230 
231         long oldElements = elements[eWordNum];
232         elements[eWordNum] &= ~(1L << eOrdinal);
233         boolean result = (elements[eWordNum] != oldElements);
234         if (result)
235             size--;
236         return result;
237     }
238 
239     // Bulk Operations
240 
241     /**
242      * Returns {@code true} if this set contains all of the elements
243      * in the specified collection.
244      *
245      * @param c collection to be checked for containment in this set
246      * @return {@code true} if this set contains all of the elements
247      *        in the specified collection
248      * @throws NullPointerException if the specified collection is null
249      */
containsAll(Collection<?> c)250     public boolean containsAll(Collection<?> c) {
251         if (!(c instanceof JumboEnumSet<?> es))
252             return super.containsAll(c);
253 
254         if (es.elementType != elementType)
255             return es.isEmpty();
256 
257         for (int i = 0; i < elements.length; i++)
258             if ((es.elements[i] & ~elements[i]) != 0)
259                 return false;
260         return true;
261     }
262 
263     /**
264      * Adds all of the elements in the specified collection to this set.
265      *
266      * @param c collection whose elements are to be added to this set
267      * @return {@code true} if this set changed as a result of the call
268      * @throws NullPointerException if the specified collection or any of
269      *     its elements are null
270      */
addAll(Collection<? extends E> c)271     public boolean addAll(Collection<? extends E> c) {
272         if (!(c instanceof JumboEnumSet<?> es))
273             return super.addAll(c);
274 
275         if (es.elementType != elementType) {
276             if (es.isEmpty())
277                 return false;
278             else
279                 throw new ClassCastException(
280                     es.elementType + " != " + elementType);
281         }
282 
283         for (int i = 0; i < elements.length; i++)
284             elements[i] |= es.elements[i];
285         return recalculateSize();
286     }
287 
288     /**
289      * Removes from this set all of its elements that are contained in
290      * the specified collection.
291      *
292      * @param c elements to be removed from this set
293      * @return {@code true} if this set changed as a result of the call
294      * @throws NullPointerException if the specified collection is null
295      */
removeAll(Collection<?> c)296     public boolean removeAll(Collection<?> c) {
297         if (!(c instanceof JumboEnumSet<?> es))
298             return super.removeAll(c);
299 
300         if (es.elementType != elementType)
301             return false;
302 
303         for (int i = 0; i < elements.length; i++)
304             elements[i] &= ~es.elements[i];
305         return recalculateSize();
306     }
307 
308     /**
309      * Retains only the elements in this set that are contained in the
310      * specified collection.
311      *
312      * @param c elements to be retained in this set
313      * @return {@code true} if this set changed as a result of the call
314      * @throws NullPointerException if the specified collection is null
315      */
retainAll(Collection<?> c)316     public boolean retainAll(Collection<?> c) {
317         if (!(c instanceof JumboEnumSet<?> es))
318             return super.retainAll(c);
319 
320         if (es.elementType != elementType) {
321             boolean changed = (size != 0);
322             clear();
323             return changed;
324         }
325 
326         for (int i = 0; i < elements.length; i++)
327             elements[i] &= es.elements[i];
328         return recalculateSize();
329     }
330 
331     /**
332      * Removes all of the elements from this set.
333      */
clear()334     public void clear() {
335         Arrays.fill(elements, 0);
336         size = 0;
337     }
338 
339     /**
340      * Compares the specified object with this set for equality.  Returns
341      * {@code true} if the given object is also a set, the two sets have
342      * the same size, and every member of the given set is contained in
343      * this set.
344      *
345      * @param o object to be compared for equality with this set
346      * @return {@code true} if the specified object is equal to this set
347      */
equals(Object o)348     public boolean equals(Object o) {
349         if (!(o instanceof JumboEnumSet<?> es))
350             return super.equals(o);
351 
352         if (es.elementType != elementType)
353             return size == 0 && es.size == 0;
354 
355         return Arrays.equals(es.elements, elements);
356     }
357 
358     /**
359      * Recalculates the size of the set.  Returns true if it's changed.
360      */
recalculateSize()361     private boolean recalculateSize() {
362         int oldSize = size;
363         size = 0;
364         for (long elt : elements)
365             size += Long.bitCount(elt);
366 
367         return size != oldSize;
368     }
369 
clone()370     public EnumSet<E> clone() {
371         JumboEnumSet<E> result = (JumboEnumSet<E>) super.clone();
372         result.elements = result.elements.clone();
373         return result;
374     }
375 }
376