/* * Copyright (c) 2012, 2013 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. Oracle designates this * particular file as subject to the "Classpath" exception as provided * by Oracle in the LICENSE file that accompanied this code. * * 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 java.util.stream; import java.util.EnumMap; import java.util.Map; /** * Flags corresponding to characteristics of streams and operations. Flags are utilized by the stream * framework to control, specialize or optimize computation. * *
* Stream flags may be used to describe characteristics of several different entities associated with streams: * stream sources, intermediate operations, and terminal operations. Not all stream flags are meaningful for all * entities; the following table summarizes which flags are meaningful in what contexts: *
* DISTINCT SORTED ORDERED SIZED SHORT_CIRCUIT PARALLEL * Stream source Y Y Y Y N Y * Intermediate operation PCI PCI PCI PC PI PC * Terminal operation N N PC N PI N ** *
In the above table, "PCI" means "may preserve, clear, or inject"; "PC" means "may preserve or clear", * "PI" means "may preserve or inject", and "N" means "not valid". * *
Stream flags are represented by unioned bit sets, so that a single word may describe all the * characteristics of a given stream entity, and that, for example, the flags for a stream source can be * efficiently combined with the flags for later operations on that stream. * *
The bit masks {@link #STREAM_MASK}, {@link #OP_MASK}, and {@link #TERMINAL_OP_MASK} can be ANDed with * a bit set of stream flags to produce a mask containing only the valid flags for that entity type. * *
When describing a stream source, one only need describe what characteristics that stream has; when describing * a stream operation, one need describe whether the operation preserves, injects, or clears that characteristic. * Accordingly, two bits are used for each flag, so as to allow representing not only the presence of of a * characteristic, but how an operation modifies that characteristic. There are two common forms in which * flag bits are combined into an {@code int} bit set. Stream flags are a unioned bit set constructed by * ORing the enum characteristic values of {@link #set()} (or, more commonly, ORing the corresponding static named * constants prefixed with {@code IS_}). Operation flags are a unioned bit set constructed by * ORing the enum characteristic values of {@link #set()} or {@link #clear()} (to inject, or clear, respectively, * the corresponding flag), or more commonly ORing the corresponding named constants prefixed with {@code IS_} * or {@code NOT_}. Flags that are not marked with {@code IS_} or {@code NOT_} are implicitly treated as preserved. * Care must be taken when combining bitsets that the correct combining operations are applied in the correct order. * *
* With the exception of {@link #PARALLEL}, stream characteristics can be derived from the equivalent * {@link java.util.Spliterator} characteristics: {@link java.util.Spliterator#DISTINCT}, * {@link java.util.Spliterator#SORTED}, {@link java.util.Spliterator#ORDERED}, and * {@link java.util.Spliterator#SIZED}. A spliterator characteristics bit set can be converted to stream flags * using the method {@link #fromCharacteristics(int)} and converted back using {@link #toCharacteristics(int)}. * (The bit set {@link #SPLITERATOR_CHARACTERISTICS_MASK} is used to AND with a bit set to produce a valid * spliterator characteristics bit set that can be converted to stream flags.) * *
* The source of a stream encapsulates a spliterator. The characteristics of that source * spliterator when transformed to stream flags will be a proper subset of stream flags of that stream. * For example: *
{@code * Spliterator s = ...; * Stream stream = Streams.stream(s); * flagsFromSpliterator = fromCharacteristics(s.characteristics()); * assert(flagsFromSpliterator & stream.getStreamFlags() == flagsFromSpliterator); * }* *
* An intermediate operation, performed on an input stream to create a new output stream, * may preserve, clear or inject stream or operation characteristics. * Similarly, a terminal operation, performed on an input stream to produce an output result * may preserve, clear or inject stream or operation characteristics. * Preservation means that if that characteristic is present on the input, then it is * also present on the output. Clearing means that the characteristic is not present on the output regardless * of the input. Injection means that the characteristic is present on the output regardless of the input. * If a characteristic is not cleared or injected then it is implicitly preserved. * *
* A pipeline consists of a stream source encapsulating a spliterator, one or more intermediate operations, * and finally a terminal operation that produces a result. At each stage of the pipeline, a combined * stream and operation flags can be calculated, using {@link #combineOpFlags(int, int)}. * Such flags ensure that preservation, clearing and injecting information is retained at each stage. * * The combined stream and operation flags for the source stage of the pipeline is calculated as * follows: *
{@code * int flagsForSourceStage = combineOpFlags(sourceFlags, INITIAL_OPS_VALUE); * }* * The combined stream and operation flags of each subsequent intermediate operation stage in the pipeline is * calculated as follows: *
{@code * int flagsForThisStage = combineOpFlags(flagsForPreviousStage, thisOpFlags); * }* * Finally the flags output from the last intermediate operation of the pipeline are combined with the operation flags * of the terminal operation to produce the flags output from the pipeline. * *
Those flags can then be used to apply optimizations. For example, if {@code SIZED.isKnown(flags)} returns true * then the stream size remains constant throughout the pipeline, this information can be utilized to pre-allocate data * structures and combined with {@link java.util.Spliterator#SUBSIZED} that information can be utilized to perform * concurrent in-place updates into a shared array. * * For specific details see the {@link AbstractPipeline} constructors. * * @since 1.8 */ // @@@ When a new flag is added what should happen for existing operations? // Need to move to a builder approach used by ops where the masks for the new flag are // taken into account for default behaviour. enum StreamOpFlag { /* * Each characteristic takes up 2 bits in a bit set to accommodate preserving, clearing and * setting/injecting information. * * This applies to stream flags, intermediate/terminal operation flags, and combined stream and * operation flags. Even though the former only requires 1 bit of information per characteristic, * is it more efficient when combining flags to align set and inject bits. * * Characteristics belong to certain types, see the Type enum. Bit masks for the types are * constructed as per the following table: * * DISTINCT SORTED ORDERED SIZED SHORT_CIRCUIT PARALLEL * SPLITERATOR 01 01 01 01 00 00 * STREAM 01 01 01 01 00 01 * OP 11 11 11 10 01 10 * TERMINAL_OP 00 00 10 00 01 00 * UPSTREAM_TERMINAL_OP 00 00 10 00 00 00 * * 01 = set/inject * 10 = clear * 11 = preserve * * Construction of the columns is performed using a simple builder for non-zero values. */ // The following flags correspond to characteristics on Spliterator // and the values MUST be equal. // /** * Characteristic value signifying that, for each pair of * encountered elements in a stream {@code x, y}, {@code !x.equals(y)}. *
* A stream may have this value or an intermediate operation can preserve, clear or inject * this value. */ // 0, 0x00000001 // Matches Spliterator.DISTINCT DISTINCT(0, set(Type.SPLITERATOR).set(Type.STREAM).setAndClear(Type.OP)), /** * Characteristic value signifying that encounter order follows a * defined sort order. *
* A stream can have this value or an intermediate operation can preserve, clear or inject * this value. */ // 1, 0x00000004 // Matches Spliterator.SORTED SORTED(1, set(Type.SPLITERATOR).set(Type.STREAM).setAndClear(Type.OP)), /** * Characteristic value signifying that an encounter order is * defined for stream elements. *
* A stream can have this value, an intermediate operation can preserve, clear or inject * this value, or a terminal operation can preserve or clear this value. */ // 2, 0x00000010 // Matches Spliterator.ORDERED ORDERED(2, set(Type.SPLITERATOR).set(Type.STREAM).setAndClear(Type.OP).clear(Type.TERMINAL_OP) .clear(Type.UPSTREAM_TERMINAL_OP)), /** * Characteristic value signifying that size of the stream * is of a known finite size that is equal to the known finite * size of the source spliterator input to the first stream * in the pipeline. *
* A stream can have this value or an intermediate operation can preserve or clear * this value. */ // 3, 0x00000040 // Matches Spliterator.SIZED SIZED(3, set(Type.SPLITERATOR).set(Type.STREAM).clear(Type.OP)), // The following Spliterator characteristics are not currently used but a // gap in the bit set is deliberately retained to enable corresponding stream // flags if//when required without modification to other flag values. // // 4, 0x00000100 INFINITE(4, ... // 5, 0x00000400 NONNULL(5, ... // 6, 0x00001000 IMMUTABLE(6, ... // 7, 0x00004000 CONCURRENT(7, ... // 8, 0x00010000 SUBSIZED(8, ...) // The following 3 flags are currently undefined and a free for any further // spliterator characteristics. // // 9, 0x00040000 // 10, 0x00100000 // 11, 0x00400000 // The following flags are specific to streams and operations // /** * Characteristic value signifying that an operation may short-circuit the stream. *
* An intermediate operation can preserve or inject this value, * or a terminal operation can preserve or inject this value. */ // 12, 0x01000000 SHORT_CIRCUIT(12, set(Type.OP).set(Type.TERMINAL_OP)), /** * Characteristic value signifying that the stream is to be evaluated in parallel rather than * sequentially. *
* A stream can have this value or an intermediate operation can preserve or clear
* this value.
*/
// 13, 0x04000000
PARALLEL(13,
set(Type.STREAM).clear(Type.OP));
// The following 2 flags are currently undefined and a free for any further
// stream flags if/when required
//
// 14, 0x10000000
// 15, 0x40000000
/**
* Type of a flag
*/
enum Type {
/** The flag is associated with spliterator characteristics. */
SPLITERATOR,
/** The flag is associated with stream flags. */
STREAM,
/** The flag is associated with intermediate operation flags. */
OP,
/** The flag is associated with terminal operation flags. */
TERMINAL_OP,
/**
* The flag is associated with terminal operation flags that are propagated upstream
* across the last stateful operation boundary
*/
UPSTREAM_TERMINAL_OP
}
/**
* The bit pattern for setting/injecting a flag.
*/
private static final int SET_BITS = 0b01;
/**
* The bit pattern for clearing a flag.
*/
private static final int CLEAR_BITS = 0b10;
/**
* The bit pattern for preserving a flag.
*/
private static final int PRESERVE_BITS = 0b11;
private static MaskBuilder set(Type t) {
return new MaskBuilder(new EnumMap<>(Type.class)).set(t);
}
private static class MaskBuilder {
final Map
* A flag set on stream flags or injected on operation flags,
* and injected combined stream and operation flags,
* will be injected on the updated combined stream and operation flags.
*
* A flag set on stream flags or injected on operation flags,
* and cleared on the combined stream and operation flags,
* will be cleared on the updated combined stream and operation flags.
*
* A flag set on the stream flags or injected on operation flags,
* and preserved on the combined stream and operation flags,
* will be injected on the updated combined stream and operation flags.
*
* A flag not set on the stream flags or cleared/preserved on operation flags,
* and injected on the combined stream and operation flags,
* will be injected on the updated combined stream and operation flags.
*
* A flag not set on the stream flags or cleared/preserved on operation flags,
* and cleared on the combined stream and operation flags,
* will be cleared on the updated combined stream and operation flags.
*
* A flag not set on the stream flags,
* and preserved on the combined stream and operation flags
* will be preserved on the updated combined stream and operation flags.
*
* A flag cleared on operation flags,
* and preserved on the combined stream and operation flags
* will be cleared on the updated combined stream and operation flags.
*
* A flag preserved on operation flags,
* and preserved on the combined stream and operation flags
* will be preserved on the updated combined stream and operation flags.
* Each flag injected on the combined stream and operation flags will be set on the stream flags.
*
* @param combOpFlags the combined stream and operation flags.
* @return the stream flags.
*/
static int toStreamFlags(int combOpFlags) {
// By flipping the nibbles 0x11 become 0x00 and 0x01 become 0x10
// Shift left 1 to restore set flags and mask off anything other than the set flags
return ((~combOpFlags) >> 1) & FLAG_MASK_IS & combOpFlags;
}
/**
* Convert stream flags to a spliterator characteristic bit set.
*
* @param streamFlags the stream flags.
* @return the spliterator characteristic bit set.
*/
static int toCharacteristics(int streamFlags) {
return streamFlags & SPLITERATOR_CHARACTERISTICS_MASK;
}
/**
* Convert a spliterator characteristic bit set to stream flags.
*
* @param characteristics the spliterator characteristic bit set.
* @return the stream flags.
*/
static int fromCharacteristics(int characteristics) {
return characteristics & SPLITERATOR_CHARACTERISTICS_MASK;
}
}