content: /*
   * Copyright (C) 2016 The Android Open Source Project
   *
   * Licensed under the Apache License, Version 2.0 (the "License");
   * you may not use this file except in compliance with the License.
   * You may obtain a copy of the License at
   *
   *      http://www.apache.org/licenses/LICENSE-2.0
   *
   * Unless required by applicable law or agreed to in writing, software
   * distributed under the License is distributed on an "AS IS" BASIS,
   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
   * See the License for the specific language governing permissions and
   * limitations under the License.
   */
  package com.google.android.exoplayer2.source;
  
  import android.support.annotation.Nullable;
  import com.google.android.exoplayer2.C;
  import com.google.android.exoplayer2.Format;
  import com.google.android.exoplayer2.FormatHolder;
  import com.google.android.exoplayer2.decoder.DecoderInputBuffer;
  import com.google.android.exoplayer2.extractor.ExtractorInput;
  import com.google.android.exoplayer2.extractor.TrackOutput;
  import com.google.android.exoplayer2.source.SampleMetadataQueue.SampleExtrasHolder;
  import com.google.android.exoplayer2.upstream.Allocation;
  import com.google.android.exoplayer2.upstream.Allocator;
  import com.google.android.exoplayer2.util.ParsableByteArray;
  import java.io.EOFException;
  import java.io.IOException;
  import java.nio.ByteBuffer;
  
  /**
   * A queue of media samples.
   */
  public final class SampleQueue implements TrackOutput {
  
    /**
     * A listener for changes to the upstream format.
     */
    public interface UpstreamFormatChangedListener {
  
      /**
       * Called on the loading thread when an upstream format change occurs.
       *
       * @param format The new upstream format.
       */
      void onUpstreamFormatChanged(Format format);
  
    }
  
    public static final int ADVANCE_FAILED = -1;
  
    private static final int INITIAL_SCRATCH_SIZE = 32;
  
    private final Allocator allocator;
    private final int allocationLength;
    private final SampleMetadataQueue metadataQueue;
    private final SampleExtrasHolder extrasHolder;
    private final ParsableByteArray scratch;
  
    // References into the linked list of allocations.
    private AllocationNode firstAllocationNode;
    private AllocationNode readAllocationNode;
    private AllocationNode writeAllocationNode;
  
    // Accessed only by the consuming thread.
    private Format downstreamFormat;
  
    // Accessed only by the loading thread (or the consuming thread when there is no loading thread).
    private boolean pendingFormatAdjustment;
    private Format lastUnadjustedFormat;
    private long sampleOffsetUs;
    private long totalBytesWritten;
    private boolean pendingSplice;
    private UpstreamFormatChangedListener upstreamFormatChangeListener;
  
    /**
     * @param allocator An {@link Allocator} from which allocations for sample data can be obtained.
     */
    public SampleQueue(Allocator allocator) {
      this.allocator = allocator;
      allocationLength = allocator.getIndividualAllocationLength();
      metadataQueue = new SampleMetadataQueue();
      extrasHolder = new SampleExtrasHolder();
      scratch = new ParsableByteArray(INITIAL_SCRATCH_SIZE);
      firstAllocationNode = new AllocationNode(0, allocationLength);
      readAllocationNode = firstAllocationNode;
      writeAllocationNode = firstAllocationNode;
    }
  
    // Called by the consuming thread, but only when there is no loading thread.
  
    /**
     * Resets the output without clearing the upstream format. Equivalent to {@code reset(false)}.
     */
    public void reset() {
      reset(false);
    }
  
    /**
     * Resets the output.
     *
     * @param resetUpstreamFormat Whether the upstream format should be cleared. If set to false,
     *     samples queued after the reset (and before a subsequent call to {@link #format(Format)})
     *     are assumed to have the current upstream format. If set to true, {@link #format(Format)}
     *     must be called after the reset before any more samples can be queued.
     */
    public void reset(boolean resetUpstreamFormat) {
      metadataQueue.reset(resetUpstreamFormat);
      clearAllocationNodes(firstAllocationNode);
      firstAllocationNode = new AllocationNode(0, allocationLength);
      readAllocationNode = firstAllocationNode;
      writeAllocationNode = firstAllocationNode;
      totalBytesWritten = 0;
      allocator.trim();
    }
  
    /**
     * Sets a source identifier for subsequent samples.
     *
     * @param sourceId The source identifier.
     */
    public void sourceId(int sourceId) {
      metadataQueue.sourceId(sourceId);
    }
  
    /**
     * Indicates samples that are subsequently queued should be spliced into those already queued.
     */
    public void splice() {
      pendingSplice = true;
    }
  
    /**
     * Returns the current absolute write index.
     */
    public int getWriteIndex() {
      return metadataQueue.getWriteIndex();
    }
  
    /**
     * Discards samples from the write side of the queue.
     *
     * @param discardFromIndex The absolute index of the first sample to be discarded. Must be in the
     *     range [{@link #getReadIndex()}, {@link #getWriteIndex()}].
     */
    public void discardUpstreamSamples(int discardFromIndex) {
      totalBytesWritten = metadataQueue.discardUpstreamSamples(discardFromIndex);
      if (totalBytesWritten == 0 || totalBytesWritten == firstAllocationNode.startPosition) {
        clearAllocationNodes(firstAllocationNode);
        firstAllocationNode = new AllocationNode(totalBytesWritten, allocationLength);
        readAllocationNode = firstAllocationNode;
        writeAllocationNode = firstAllocationNode;
      } else {
        // Find the last node containing at least 1 byte of data that we need to keep.
        AllocationNode lastNodeToKeep = firstAllocationNode;
        while (totalBytesWritten > lastNodeToKeep.endPosition) {
          lastNodeToKeep = lastNodeToKeep.next;
        }
        // Discard all subsequent nodes.
        AllocationNode firstNodeToDiscard = lastNodeToKeep.next;
        clearAllocationNodes(firstNodeToDiscard);
        // Reset the successor of the last node to be an uninitialized node.
        lastNodeToKeep.next = new AllocationNode(lastNodeToKeep.endPosition, allocationLength);
        // Update writeAllocationNode and readAllocationNode as necessary.
        writeAllocationNode = totalBytesWritten == lastNodeToKeep.endPosition ? lastNodeToKeep.next
            : lastNodeToKeep;
        if (readAllocationNode == firstNodeToDiscard) {
          readAllocationNode = lastNodeToKeep.next;
        }
      }
    }
  
    // Called by the consuming thread.
  
    /**
     * Returns whether a sample is available to be read.
     */
    public boolean hasNextSample() {
      return metadataQueue.hasNextSample();
    }
  
    /**
     * Returns the absolute index of the first sample.
     */
    public int getFirstIndex() {
      return metadataQueue.getFirstIndex();
    }
  
    /**
     * Returns the current absolute read index.
     */
    public int getReadIndex() {
      return metadataQueue.getReadIndex();
    }
  
    /**
     * Peeks the source id of the next sample to be read, or the current upstream source id if the
     * queue is empty or if the read position is at the end of the queue.
     *
     * @return The source id.
     */
    public int peekSourceId() {
      return metadataQueue.peekSourceId();
    }
  
    /**
     * Returns the upstream {@link Format} in which samples are being queued.
     */
    public Format getUpstreamFormat() {
      return metadataQueue.getUpstreamFormat();
    }
  
    /**
     * Returns the largest sample timestamp that has been queued since the last {@link #reset}.
     * <p>
     * Samples that were discarded by calling {@link #discardUpstreamSamples(int)} are not
     * considered as having been queued. Samples that were dequeued from the front of the queue are
     * considered as having been queued.
     *
     * @return The largest sample timestamp that has been queued, or {@link Long#MIN_VALUE} if no
     *     samples have been queued.
     */
    public long getLargestQueuedTimestampUs() {
      return metadataQueue.getLargestQueuedTimestampUs();
    }
  
    /** Returns the timestamp of the first sample, or {@link Long#MIN_VALUE} if the queue is empty. */
    public long getFirstTimestampUs() {
      return metadataQueue.getFirstTimestampUs();
    }
  
    /**
     * Rewinds the read position to the first sample in the queue.
     */
    public void rewind() {
      metadataQueue.rewind();
      readAllocationNode = firstAllocationNode;
    }
  
    /**
     * Discards up to but not including the sample immediately before or at the specified time.
     *
     * @param timeUs The time to discard to.
     * @param toKeyframe If true then discards samples up to the keyframe before or at the specified
     *     time, rather than any sample before or at that time.
     * @param stopAtReadPosition If true then samples are only discarded if they're before the
     *     read position. If false then samples at and beyond the read position may be discarded, in
     *     which case the read position is advanced to the first remaining sample.
     */
    public void discardTo(long timeUs, boolean toKeyframe, boolean stopAtReadPosition) {
      discardDownstreamTo(metadataQueue.discardTo(timeUs, toKeyframe, stopAtReadPosition));
    }
  
    /**
     * Discards up to but not including the read position.
     */
    public void discardToRead() {
      discardDownstreamTo(metadataQueue.discardToRead());
    }
  
    /**
     * Discards to the end of the queue. The read position is also advanced.
     */
    public void discardToEnd() {
      discardDownstreamTo(metadataQueue.discardToEnd());
    }
  
    /**
     * Advances the read position to the end of the queue.
     *
     * @return The number of samples that were skipped.
     */
    public int advanceToEnd() {
      return metadataQueue.advanceToEnd();
    }
  
    /**
     * Attempts to advance the read position to the sample before or at the specified time.
     *
     * @param timeUs The time to advance to.
     * @param toKeyframe If true then attempts to advance to the keyframe before or at the specified
     *     time, rather than to any sample before or at that time.
     * @param allowTimeBeyondBuffer Whether the operation can succeed if {@code timeUs} is beyond the
     *     end of the queue, by advancing the read position to the last sample (or keyframe).
     * @return The number of samples that were skipped if the operation was successful, which may be
     *     equal to 0, or {@link #ADVANCE_FAILED} if the operation was not successful. A successful
     *     advance is one in which the read position was unchanged or advanced, and is now at a sample
     *     meeting the specified criteria.
     */
    public int advanceTo(long timeUs, boolean toKeyframe, boolean allowTimeBeyondBuffer) {
      return metadataQueue.advanceTo(timeUs, toKeyframe, allowTimeBeyondBuffer);
    }
  
    /**
     * Attempts to set the read position to the specified sample index.
     *
     * @param sampleIndex The sample index.
     * @return Whether the read position was set successfully. False is returned if the specified
     *     index is smaller than the index of the first sample in the queue, or larger than the index
     *     of the next sample that will be written.
     */
    public boolean setReadPosition(int sampleIndex) {
      return metadataQueue.setReadPosition(sampleIndex);
    }
  
    /**
     * Attempts to read from the queue.
     *
     * @param formatHolder A {@link FormatHolder} to populate in the case of reading a format.
     * @param buffer A {@link DecoderInputBuffer} to populate in the case of reading a sample or the
     *     end of the stream. If the end of the stream has been reached, the
     *     {@link C#BUFFER_FLAG_END_OF_STREAM} flag will be set on the buffer.
     * @param formatRequired Whether the caller requires that the format of the stream be read even if
     *     it's not changing. A sample will never be read if set to true, however it is still possible
     *     for the end of stream or nothing to be read.
     * @param loadingFinished True if an empty queue should be considered the end of the stream.
     * @param decodeOnlyUntilUs If a buffer is read, the {@link C#BUFFER_FLAG_DECODE_ONLY} flag will
     *     be set if the buffer's timestamp is less than this value.
     * @return The result, which can be {@link C#RESULT_NOTHING_READ}, {@link C#RESULT_FORMAT_READ} or
     *     {@link C#RESULT_BUFFER_READ}.
     */
    public int read(FormatHolder formatHolder, DecoderInputBuffer buffer, boolean formatRequired,
        boolean loadingFinished, long decodeOnlyUntilUs) {
      int result = metadataQueue.read(formatHolder, buffer, formatRequired, loadingFinished,
          downstreamFormat, extrasHolder);
      switch (result) {
        case C.RESULT_FORMAT_READ:
          downstreamFormat = formatHolder.format;
          return C.RESULT_FORMAT_READ;
        case C.RESULT_BUFFER_READ:
          if (!buffer.isEndOfStream()) {
            if (buffer.timeUs < decodeOnlyUntilUs) {
              buffer.addFlag(C.BUFFER_FLAG_DECODE_ONLY);
            }
            // Read encryption data if the sample is encrypted.
            if (buffer.isEncrypted()) {
              readEncryptionData(buffer, extrasHolder);
            }
            // Write the sample data into the holder.
            buffer.ensureSpaceForWrite(extrasHolder.size);
            readData(extrasHolder.offset, buffer.data, extrasHolder.size);
          }
          return C.RESULT_BUFFER_READ;
        case C.RESULT_NOTHING_READ:
          return C.RESULT_NOTHING_READ;
        default:
          throw new IllegalStateException();
      }
    }
  
    /**
     * Reads encryption data for the current sample.
     * <p>
     * The encryption data is written into {@link DecoderInputBuffer#cryptoInfo}, and
     * {@link SampleExtrasHolder#size} is adjusted to subtract the number of bytes that were read. The
     * same value is added to {@link SampleExtrasHolder#offset}.
     *
     * @param buffer The buffer into which the encryption data should be written.
     * @param extrasHolder The extras holder whose offset should be read and subsequently adjusted.
     */
    private void readEncryptionData(DecoderInputBuffer buffer, SampleExtrasHolder extrasHolder) {
      long offset = extrasHolder.offset;
  
      // Read the signal byte.
      scratch.reset(1);
      readData(offset, scratch.data, 1);
      offset++;
      byte signalByte = scratch.data[0];
      boolean subsampleEncryption = (signalByte & 0x80) != 0;
      int ivSize = signalByte & 0x7F;
  
      // Read the initialization vector.
      if (buffer.cryptoInfo.iv == null) {
        buffer.cryptoInfo.iv = new byte[16];
      }
      readData(offset, buffer.cryptoInfo.iv, ivSize);
      offset += ivSize;
  
      // Read the subsample count, if present.
      int subsampleCount;
      if (subsampleEncryption) {
        scratch.reset(2);
        readData(offset, scratch.data, 2);
        offset += 2;
        subsampleCount = scratch.readUnsignedShort();
      } else {
        subsampleCount = 1;
      }
  
      // Write the clear and encrypted subsample sizes.
      int[] clearDataSizes = buffer.cryptoInfo.numBytesOfClearData;
      if (clearDataSizes == null || clearDataSizes.length < subsampleCount) {
        clearDataSizes = new int[subsampleCount];
      }
      int[] encryptedDataSizes = buffer.cryptoInfo.numBytesOfEncryptedData;
      if (encryptedDataSizes == null || encryptedDataSizes.length < subsampleCount) {
        encryptedDataSizes = new int[subsampleCount];
      }
      if (subsampleEncryption) {
        int subsampleDataLength = 6 * subsampleCount;
        scratch.reset(subsampleDataLength);
        readData(offset, scratch.data, subsampleDataLength);
        offset += subsampleDataLength;
        scratch.setPosition(0);
        for (int i = 0; i < subsampleCount; i++) {
          clearDataSizes[i] = scratch.readUnsignedShort();
          encryptedDataSizes[i] = scratch.readUnsignedIntToInt();
        }
      } else {
        clearDataSizes[0] = 0;
        encryptedDataSizes[0] = extrasHolder.size - (int) (offset - extrasHolder.offset);
      }
  
      // Populate the cryptoInfo.
      CryptoData cryptoData = extrasHolder.cryptoData;
      buffer.cryptoInfo.set(subsampleCount, clearDataSizes, encryptedDataSizes,
          cryptoData.encryptionKey, buffer.cryptoInfo.iv, cryptoData.cryptoMode,
          cryptoData.encryptedBlocks, cryptoData.clearBlocks);
  
      // Adjust the offset and size to take into account the bytes read.
      int bytesRead = (int) (offset - extrasHolder.offset);
      extrasHolder.offset += bytesRead;
      extrasHolder.size -= bytesRead;
    }
  
    /**
     * Reads data from the front of the rolling buffer.
     *
     * @param absolutePosition The absolute position from which data should be read.
     * @param target The buffer into which data should be written.
     * @param length The number of bytes to read.
     */
    private void readData(long absolutePosition, ByteBuffer target, int length) {
      advanceReadTo(absolutePosition);
      int remaining = length;
      while (remaining > 0) {
        int toCopy = Math.min(remaining, (int) (readAllocationNode.endPosition - absolutePosition));
        Allocation allocation = readAllocationNode.allocation;
        target.put(allocation.data, readAllocationNode.translateOffset(absolutePosition), toCopy);
        remaining -= toCopy;
        absolutePosition += toCopy;
        if (absolutePosition == readAllocationNode.endPosition) {
          readAllocationNode = readAllocationNode.next;
        }
      }
    }
  
    /**
     * Reads data from the front of the rolling buffer.
     *
     * @param absolutePosition The absolute position from which data should be read.
     * @param target The array into which data should be written.
     * @param length The number of bytes to read.
     */
    private void readData(long absolutePosition, byte[] target, int length) {
      advanceReadTo(absolutePosition);
      int remaining = length;
      while (remaining > 0) {
        int toCopy = Math.min(remaining, (int) (readAllocationNode.endPosition - absolutePosition));
        Allocation allocation = readAllocationNode.allocation;
        System.arraycopy(allocation.data, readAllocationNode.translateOffset(absolutePosition),
            target, length - remaining, toCopy);
        remaining -= toCopy;
        absolutePosition += toCopy;
        if (absolutePosition == readAllocationNode.endPosition) {
          readAllocationNode = readAllocationNode.next;
        }
      }
    }
  
    /**
     * Advances {@link #readAllocationNode} to the specified absolute position.
     *
     * @param absolutePosition The position to which {@link #readAllocationNode} should be advanced.
     */
    private void advanceReadTo(long absolutePosition) {
      while (absolutePosition >= readAllocationNode.endPosition) {
        readAllocationNode = readAllocationNode.next;
      }
    }
  
    /**
     * Advances {@link #firstAllocationNode} to the specified absolute position.
     * {@link #readAllocationNode} is also advanced if necessary to avoid it falling behind
     * {@link #firstAllocationNode}. Nodes that have been advanced past are cleared, and their
     * underlying allocations are returned to the allocator.
     *
     * @param absolutePosition The position to which {@link #firstAllocationNode} should be advanced.
     *     May be {@link C#POSITION_UNSET}, in which case calling this method is a no-op.
     */
    private void discardDownstreamTo(long absolutePosition) {
      if (absolutePosition == C.POSITION_UNSET) {
        return;
      }
      while (absolutePosition >= firstAllocationNode.endPosition) {
        allocator.release(firstAllocationNode.allocation);
        firstAllocationNode = firstAllocationNode.clear();
      }
      // If we discarded the node referenced by readAllocationNode then we need to advance it to the
      // first remaining node.
      if (readAllocationNode.startPosition < firstAllocationNode.startPosition) {
        readAllocationNode = firstAllocationNode;
      }
    }
  
    // Called by the loading thread.
  
    /**
     * Sets a listener to be notified of changes to the upstream format.
     *
     * @param listener The listener.
     */
    public void setUpstreamFormatChangeListener(UpstreamFormatChangedListener listener) {
      upstreamFormatChangeListener = listener;
    }
  
    /**
     * Sets an offset that will be added to the timestamps (and sub-sample timestamps) of samples
     * that are subsequently queued.
     *
     * @param sampleOffsetUs The timestamp offset in microseconds.
     */
    public void setSampleOffsetUs(long sampleOffsetUs) {
      if (this.sampleOffsetUs != sampleOffsetUs) {
        this.sampleOffsetUs = sampleOffsetUs;
        pendingFormatAdjustment = true;
      }
    }
  
    @Override
    public void format(Format format) {
      Format adjustedFormat = getAdjustedSampleFormat(format, sampleOffsetUs);
      boolean formatChanged = metadataQueue.format(adjustedFormat);
      lastUnadjustedFormat = format;
      pendingFormatAdjustment = false;
      if (upstreamFormatChangeListener != null && formatChanged) {
        upstreamFormatChangeListener.onUpstreamFormatChanged(adjustedFormat);
      }
    }
  
    @Override
    public int sampleData(ExtractorInput input, int length, boolean allowEndOfInput)
        throws IOException, InterruptedException {
      length = preAppend(length);
      int bytesAppended = input.read(writeAllocationNode.allocation.data,
          writeAllocationNode.translateOffset(totalBytesWritten), length);
      if (bytesAppended == C.RESULT_END_OF_INPUT) {
        if (allowEndOfInput) {
          return C.RESULT_END_OF_INPUT;
        }
        throw new EOFException();
      }
      postAppend(bytesAppended);
      return bytesAppended;
    }
  
    @Override
    public void sampleData(ParsableByteArray buffer, int length) {
      while (length > 0) {
        int bytesAppended = preAppend(length);
        buffer.readBytes(writeAllocationNode.allocation.data,
            writeAllocationNode.translateOffset(totalBytesWritten), bytesAppended);
        length -= bytesAppended;
        postAppend(bytesAppended);
      }
    }
  
    @Override
    public void sampleMetadata(long timeUs, @C.BufferFlags int flags, int size, int offset,
        CryptoData cryptoData) {
      if (pendingFormatAdjustment) {
        format(lastUnadjustedFormat);
      }
      if (pendingSplice) {
        if ((flags & C.BUFFER_FLAG_KEY_FRAME) == 0 || !metadataQueue.attemptSplice(timeUs)) {
          return;
        }
        pendingSplice = false;
      }
      timeUs += sampleOffsetUs;
      long absoluteOffset = totalBytesWritten - size - offset;
      metadataQueue.commitSample(timeUs, flags, absoluteOffset, size, cryptoData);
    }
  
    // Private methods.
  
    /**
     * Clears allocation nodes starting from {@code fromNode}.
     *
     * @param fromNode The node from which to clear.
     */
    private void clearAllocationNodes(AllocationNode fromNode) {
      if (!fromNode.wasInitialized) {
        return;
      }
      // Bulk release allocations for performance (it's significantly faster when using
      // DefaultAllocator because the allocator's lock only needs to be acquired and released once)
      // [Internal: See b/29542039].
      int allocationCount = (writeAllocationNode.wasInitialized ? 1 : 0)
          + ((int) (writeAllocationNode.startPosition - fromNode.startPosition) / allocationLength);
      Allocation[] allocationsToRelease = new Allocation[allocationCount];
      AllocationNode currentNode = fromNode;
      for (int i = 0; i < allocationsToRelease.length; i++) {
        allocationsToRelease[i] = currentNode.allocation;
        currentNode = currentNode.clear();
      }
      allocator.release(allocationsToRelease);
    }
  
    /**
     * Called before writing sample data to {@link #writeAllocationNode}. May cause
     * {@link #writeAllocationNode} to be initialized.
     *
     * @param length The number of bytes that the caller wishes to write.
     * @return The number of bytes that the caller is permitted to write, which may be less than
     *     {@code length}.
     */
    private int preAppend(int length) {
      if (!writeAllocationNode.wasInitialized) {
        writeAllocationNode.initialize(allocator.allocate(),
            new AllocationNode(writeAllocationNode.endPosition, allocationLength));
      }
      return Math.min(length, (int) (writeAllocationNode.endPosition - totalBytesWritten));
    }
  
    /**
     * Called after writing sample data. May cause {@link #writeAllocationNode} to be advanced.
     *
     * @param length The number of bytes that were written.
     */
    private void postAppend(int length) {
      totalBytesWritten += length;
      if (totalBytesWritten == writeAllocationNode.endPosition) {
        writeAllocationNode = writeAllocationNode.next;
      }
    }
  
    /**
     * Adjusts a {@link Format} to incorporate a sample offset into {@link Format#subsampleOffsetUs}.
     *
     * @param format The {@link Format} to adjust.
     * @param sampleOffsetUs The offset to apply.
     * @return The adjusted {@link Format}.
     */
    private static Format getAdjustedSampleFormat(Format format, long sampleOffsetUs) {
      if (format == null) {
        return null;
      }
      if (sampleOffsetUs != 0 && format.subsampleOffsetUs != Format.OFFSET_SAMPLE_RELATIVE) {
        format = format.copyWithSubsampleOffsetUs(format.subsampleOffsetUs + sampleOffsetUs);
      }
      return format;
    }
  
    /**
     * A node in a linked list of {@link Allocation}s held by the output.
     */
    private static final class AllocationNode {
  
      /**
       * The absolute position of the start of the data (inclusive).
       */
      public final long startPosition;
      /**
       * The absolute position of the end of the data (exclusive).
       */
      public final long endPosition;
      /**
       * Whether the node has been initialized. Remains true after {@link #clear()}.
       */
      public boolean wasInitialized;
      /**
       * The {@link Allocation}, or {@code null} if the node is not initialized.
       */
      @Nullable public Allocation allocation;
      /**
       * The next {@link AllocationNode} in the list, or {@code null} if the node has not been
       * initialized. Remains set after {@link #clear()}.
       */
      @Nullable public AllocationNode next;
  
      /**
       * @param startPosition See {@link #startPosition}.
       * @param allocationLength The length of the {@link Allocation} with which this node will be
       *     initialized.
       */
      public AllocationNode(long startPosition, int allocationLength) {
        this.startPosition = startPosition;
        this.endPosition = startPosition + allocationLength;
      }
  
      /**
       * Initializes the node.
       *
       * @param allocation The node's {@link Allocation}.
       * @param next The next {@link AllocationNode}.
       */
      public void initialize(Allocation allocation, AllocationNode next) {
        this.allocation = allocation;
        this.next = next;
        wasInitialized = true;
      }
  
      /**
       * Gets the offset into the {@link #allocation}'s {@link Allocation#data} that corresponds to
       * the specified absolute position.
       *
       * @param absolutePosition The absolute position.
       * @return The corresponding offset into the allocation's data.
       */
      public int translateOffset(long absolutePosition) {
        return (int) (absolutePosition - startPosition) + allocation.offset;
      }
  
      /**
       * Clears {@link #allocation} and {@link #next}.
       *
       * @return The cleared next {@link AllocationNode}.
       */
      public AllocationNode clear() {
        allocation = null;
        AllocationNode temp = next;
        next = null;
        return temp;
      }
  
    }
  
  }
  