content: /*
   * Copyright (C) 2017 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 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.TrackOutput.CryptoData;
  import com.google.android.exoplayer2.util.Assertions;
  import com.google.android.exoplayer2.util.Util;
  
  /**
   * A queue of metadata describing the contents of a media buffer.
   */
  /* package */ final class SampleMetadataQueue {
  
    /**
     * A holder for sample metadata not held by {@link DecoderInputBuffer}.
     */
    public static final class SampleExtrasHolder {
  
      public int size;
      public long offset;
      public CryptoData cryptoData;
  
    }
  
    private static final int SAMPLE_CAPACITY_INCREMENT = 1000;
  
    private int capacity;
    private int[] sourceIds;
    private long[] offsets;
    private int[] sizes;
    private int[] flags;
    private long[] timesUs;
    private CryptoData[] cryptoDatas;
    private Format[] formats;
  
    private int length;
    private int absoluteFirstIndex;
    private int relativeFirstIndex;
    private int readPosition;
  
    private long largestDiscardedTimestampUs;
    private long largestQueuedTimestampUs;
    private boolean upstreamKeyframeRequired;
    private boolean upstreamFormatRequired;
    private Format upstreamFormat;
    private int upstreamSourceId;
  
    public SampleMetadataQueue() {
      capacity = SAMPLE_CAPACITY_INCREMENT;
      sourceIds = new int[capacity];
      offsets = new long[capacity];
      timesUs = new long[capacity];
      flags = new int[capacity];
      sizes = new int[capacity];
      cryptoDatas = new CryptoData[capacity];
      formats = new Format[capacity];
      largestDiscardedTimestampUs = Long.MIN_VALUE;
      largestQueuedTimestampUs = Long.MIN_VALUE;
      upstreamFormatRequired = true;
      upstreamKeyframeRequired = true;
    }
  
    /**
     * Clears all sample metadata from the queue.
     *
     * @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) {
      length = 0;
      absoluteFirstIndex = 0;
      relativeFirstIndex = 0;
      readPosition = 0;
      upstreamKeyframeRequired = true;
      largestDiscardedTimestampUs = Long.MIN_VALUE;
      largestQueuedTimestampUs = Long.MIN_VALUE;
      if (resetUpstreamFormat) {
        upstreamFormat = null;
        upstreamFormatRequired = true;
      }
    }
  
    /**
     * Returns the current absolute write index.
     */
    public int getWriteIndex() {
      return absoluteFirstIndex + length;
    }
  
    /**
     * Discards samples from the write side of the queue.
     *
     * @param discardFromIndex The absolute index of the first sample to be discarded.
     * @return The reduced total number of bytes written after the samples have been discarded, or 0
     *     if the queue is now empty.
     */
    public long discardUpstreamSamples(int discardFromIndex) {
      int discardCount = getWriteIndex() - discardFromIndex;
      Assertions.checkArgument(0 <= discardCount && discardCount <= (length - readPosition));
      length -= discardCount;
      largestQueuedTimestampUs = Math.max(largestDiscardedTimestampUs, getLargestTimestamp(length));
      if (length == 0) {
        return 0;
      } else {
        int relativeLastWriteIndex = getRelativeIndex(length - 1);
        return offsets[relativeLastWriteIndex] + sizes[relativeLastWriteIndex];
      }
    }
  
    public void sourceId(int sourceId) {
      upstreamSourceId = sourceId;
    }
  
    // Called by the consuming thread.
  
    /**
     * Returns the current absolute start index.
     */
    public int getFirstIndex() {
      return absoluteFirstIndex;
    }
  
    /**
     * Returns the current absolute read index.
     */
    public int getReadIndex() {
      return absoluteFirstIndex + readPosition;
    }
  
    /**
     * 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() {
      int relativeReadIndex = getRelativeIndex(readPosition);
      return hasNextSample() ? sourceIds[relativeReadIndex] : upstreamSourceId;
    }
  
    /**
     * Returns whether a sample is available to be read.
     */
    public synchronized boolean hasNextSample() {
      return readPosition != length;
    }
  
    /**
     * Returns the upstream {@link Format} in which samples are being queued.
     */
    public synchronized Format getUpstreamFormat() {
      return upstreamFormatRequired ? null : upstreamFormat;
    }
  
    /**
     * Returns the largest sample timestamp that has been queued since the last call to
     * {@link #reset(boolean)}.
     * <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 synchronized long getLargestQueuedTimestampUs() {
      return largestQueuedTimestampUs;
    }
  
    /** Returns the timestamp of the first sample, or {@link Long#MIN_VALUE} if the queue is empty. */
    public synchronized long getFirstTimestampUs() {
      return length == 0 ? Long.MIN_VALUE : timesUs[relativeFirstIndex];
    }
  
    /**
     * Rewinds the read position to the first sample retained in the queue.
     */
    public synchronized void rewind() {
      readPosition = 0;
    }
  
    /**
     * 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 a sample is read then the buffer is populated with information
     *     about the sample, but not its data. The size and absolute position of the data in the
     *     rolling buffer is stored in {@code extrasHolder}, along with an encryption id if present
     *     and the absolute position of the first byte that may still be required after the current
     *     sample has been read. May be null if the caller requires that the format of the stream be
     *     read even if it's not changing.
     * @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 downstreamFormat The current downstream {@link Format}. If the format of the next
     *     sample is different to the current downstream format then a format will be read.
     * @param extrasHolder The holder into which extra sample information should be written.
     * @return The result, which can be {@link C#RESULT_NOTHING_READ}, {@link C#RESULT_FORMAT_READ}
     *     or {@link C#RESULT_BUFFER_READ}.
     */
    @SuppressWarnings("ReferenceEquality")
    public synchronized int read(FormatHolder formatHolder, DecoderInputBuffer buffer,
        boolean formatRequired, boolean loadingFinished, Format downstreamFormat,
        SampleExtrasHolder extrasHolder) {
      if (!hasNextSample()) {
        if (loadingFinished) {
          buffer.setFlags(C.BUFFER_FLAG_END_OF_STREAM);
          return C.RESULT_BUFFER_READ;
        } else if (upstreamFormat != null
            && (formatRequired || upstreamFormat != downstreamFormat)) {
          formatHolder.format = upstreamFormat;
          return C.RESULT_FORMAT_READ;
        } else {
          return C.RESULT_NOTHING_READ;
        }
      }
  
      int relativeReadIndex = getRelativeIndex(readPosition);
      if (formatRequired || formats[relativeReadIndex] != downstreamFormat) {
        formatHolder.format = formats[relativeReadIndex];
        return C.RESULT_FORMAT_READ;
      }
  
      if (buffer.isFlagsOnly()) {
        return C.RESULT_NOTHING_READ;
      }
  
      buffer.timeUs = timesUs[relativeReadIndex];
      buffer.setFlags(flags[relativeReadIndex]);
      extrasHolder.size = sizes[relativeReadIndex];
      extrasHolder.offset = offsets[relativeReadIndex];
      extrasHolder.cryptoData = cryptoDatas[relativeReadIndex];
  
      readPosition++;
      return C.RESULT_BUFFER_READ;
    }
  
    /**
     * 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) in the
     *     queue.
     * @return The number of samples that were skipped if the operation was successful, which may be
     *     equal to 0, or {@link SampleQueue#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 synchronized int advanceTo(long timeUs, boolean toKeyframe,
        boolean allowTimeBeyondBuffer) {
      int relativeReadIndex = getRelativeIndex(readPosition);
      if (!hasNextSample() || timeUs < timesUs[relativeReadIndex]
          || (timeUs > largestQueuedTimestampUs && !allowTimeBeyondBuffer)) {
        return SampleQueue.ADVANCE_FAILED;
      }
      int offset = findSampleBefore(relativeReadIndex, length - readPosition, timeUs, toKeyframe);
      if (offset == -1) {
        return SampleQueue.ADVANCE_FAILED;
      }
      readPosition += offset;
      return offset;
    }
  
    /**
     * Advances the read position to the end of the queue.
     *
     * @return The number of samples that were skipped.
     */
    public synchronized int advanceToEnd() {
      int skipCount = length - readPosition;
      readPosition = length;
      return skipCount;
    }
  
    /**
     * 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 synchronized boolean setReadPosition(int sampleIndex) {
      if (absoluteFirstIndex <= sampleIndex && sampleIndex <= absoluteFirstIndex + length) {
        readPosition = sampleIndex - absoluteFirstIndex;
        return true;
      }
      return false;
    }
  
    /**
     * Discards up to but not including the sample immediately before or at the specified time.
     *
     * @param timeUs The time to discard up to.
     * @param toKeyframe If true then discards samples up to the keyframe before or at the specified
     *     time, rather than just 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.
     * @return The corresponding offset up to which data should be discarded, or
     *     {@link C#POSITION_UNSET} if no discarding of data is necessary.
     */
    public synchronized long discardTo(long timeUs, boolean toKeyframe, boolean stopAtReadPosition) {
      if (length == 0 || timeUs < timesUs[relativeFirstIndex]) {
        return C.POSITION_UNSET;
      }
      int searchLength = stopAtReadPosition && readPosition != length ? readPosition + 1 : length;
      int discardCount = findSampleBefore(relativeFirstIndex, searchLength, timeUs, toKeyframe);
      if (discardCount == -1) {
        return C.POSITION_UNSET;
      }
      return discardSamples(discardCount);
    }
  
    /**
     * Discards samples up to but not including the read position.
     *
     * @return The corresponding offset up to which data should be discarded, or
     *     {@link C#POSITION_UNSET} if no discarding of data is necessary.
     */
    public synchronized long discardToRead() {
      if (readPosition == 0) {
        return C.POSITION_UNSET;
      }
      return discardSamples(readPosition);
    }
  
    /**
     * Discards all samples in the queue. The read position is also advanced.
     *
     * @return The corresponding offset up to which data should be discarded, or
     *     {@link C#POSITION_UNSET} if no discarding of data is necessary.
     */
    public synchronized long discardToEnd() {
      if (length == 0) {
        return C.POSITION_UNSET;
      }
      return discardSamples(length);
    }
  
    // Called by the loading thread.
  
    public synchronized boolean format(Format format) {
      if (format == null) {
        upstreamFormatRequired = true;
        return false;
      }
      upstreamFormatRequired = false;
      if (Util.areEqual(format, upstreamFormat)) {
        // Suppress changes between equal formats so we can use referential equality in readData.
        return false;
      } else {
        upstreamFormat = format;
        return true;
      }
    }
  
    public synchronized void commitSample(long timeUs, @C.BufferFlags int sampleFlags, long offset,
        int size, CryptoData cryptoData) {
      if (upstreamKeyframeRequired) {
        if ((sampleFlags & C.BUFFER_FLAG_KEY_FRAME) == 0) {
          return;
        }
        upstreamKeyframeRequired = false;
      }
      Assertions.checkState(!upstreamFormatRequired);
      commitSampleTimestamp(timeUs);
  
      int relativeEndIndex = getRelativeIndex(length);
      timesUs[relativeEndIndex] = timeUs;
      offsets[relativeEndIndex] = offset;
      sizes[relativeEndIndex] = size;
      flags[relativeEndIndex] = sampleFlags;
      cryptoDatas[relativeEndIndex] = cryptoData;
      formats[relativeEndIndex] = upstreamFormat;
      sourceIds[relativeEndIndex] = upstreamSourceId;
  
      length++;
      if (length == capacity) {
        // Increase the capacity.
        int newCapacity = capacity + SAMPLE_CAPACITY_INCREMENT;
        int[] newSourceIds = new int[newCapacity];
        long[] newOffsets = new long[newCapacity];
        long[] newTimesUs = new long[newCapacity];
        int[] newFlags = new int[newCapacity];
        int[] newSizes = new int[newCapacity];
        CryptoData[] newCryptoDatas = new CryptoData[newCapacity];
        Format[] newFormats = new Format[newCapacity];
        int beforeWrap = capacity - relativeFirstIndex;
        System.arraycopy(offsets, relativeFirstIndex, newOffsets, 0, beforeWrap);
        System.arraycopy(timesUs, relativeFirstIndex, newTimesUs, 0, beforeWrap);
        System.arraycopy(flags, relativeFirstIndex, newFlags, 0, beforeWrap);
        System.arraycopy(sizes, relativeFirstIndex, newSizes, 0, beforeWrap);
        System.arraycopy(cryptoDatas, relativeFirstIndex, newCryptoDatas, 0, beforeWrap);
        System.arraycopy(formats, relativeFirstIndex, newFormats, 0, beforeWrap);
        System.arraycopy(sourceIds, relativeFirstIndex, newSourceIds, 0, beforeWrap);
        int afterWrap = relativeFirstIndex;
        System.arraycopy(offsets, 0, newOffsets, beforeWrap, afterWrap);
        System.arraycopy(timesUs, 0, newTimesUs, beforeWrap, afterWrap);
        System.arraycopy(flags, 0, newFlags, beforeWrap, afterWrap);
        System.arraycopy(sizes, 0, newSizes, beforeWrap, afterWrap);
        System.arraycopy(cryptoDatas, 0, newCryptoDatas, beforeWrap, afterWrap);
        System.arraycopy(formats, 0, newFormats, beforeWrap, afterWrap);
        System.arraycopy(sourceIds, 0, newSourceIds, beforeWrap, afterWrap);
        offsets = newOffsets;
        timesUs = newTimesUs;
        flags = newFlags;
        sizes = newSizes;
        cryptoDatas = newCryptoDatas;
        formats = newFormats;
        sourceIds = newSourceIds;
        relativeFirstIndex = 0;
        length = capacity;
        capacity = newCapacity;
      }
    }
  
    public synchronized void commitSampleTimestamp(long timeUs) {
      largestQueuedTimestampUs = Math.max(largestQueuedTimestampUs, timeUs);
    }
  
    /**
     * Attempts to discard samples from the end of the queue to allow samples starting from the
     * specified timestamp to be spliced in. Samples will not be discarded prior to the read position.
     *
     * @param timeUs The timestamp at which the splice occurs.
     * @return Whether the splice was successful.
     */
    public synchronized boolean attemptSplice(long timeUs) {
      if (length == 0) {
        return timeUs > largestDiscardedTimestampUs;
      }
      long largestReadTimestampUs = Math.max(largestDiscardedTimestampUs,
          getLargestTimestamp(readPosition));
      if (largestReadTimestampUs >= timeUs) {
        return false;
      }
      int retainCount = length;
      int relativeSampleIndex = getRelativeIndex(length - 1);
      while (retainCount > readPosition && timesUs[relativeSampleIndex] >= timeUs) {
        retainCount--;
        relativeSampleIndex--;
        if (relativeSampleIndex == -1) {
          relativeSampleIndex = capacity - 1;
        }
      }
      discardUpstreamSamples(absoluteFirstIndex + retainCount);
      return true;
    }
  
    // Internal methods.
  
    /**
     * Finds the sample in the specified range that's before or at the specified time. If
     * {@code keyframe} is {@code true} then the sample is additionally required to be a keyframe.
     *
     * @param relativeStartIndex The relative index from which to start searching.
     * @param length The length of the range being searched.
     * @param timeUs The specified time.
     * @param keyframe Whether only keyframes should be considered.
     * @return The offset from {@code relativeFirstIndex} to the found sample, or -1 if no matching
     *     sample was found.
     */
    private int findSampleBefore(int relativeStartIndex, int length, long timeUs, boolean keyframe) {
      // This could be optimized to use a binary search, however in practice callers to this method
      // normally pass times near to the start of the search region. Hence it's unclear whether
      // switching to a binary search would yield any real benefit.
      int sampleCountToTarget = -1;
      int searchIndex = relativeStartIndex;
      for (int i = 0; i < length && timesUs[searchIndex] <= timeUs; i++) {
        if (!keyframe || (flags[searchIndex] & C.BUFFER_FLAG_KEY_FRAME) != 0) {
          // We've found a suitable sample.
          sampleCountToTarget = i;
        }
        searchIndex++;
        if (searchIndex == capacity) {
          searchIndex = 0;
        }
      }
      return sampleCountToTarget;
    }
  
    /**
     * Discards the specified number of samples.
     *
     * @param discardCount The number of samples to discard.
     * @return The corresponding offset up to which data should be discarded.
     */
    private long discardSamples(int discardCount) {
      largestDiscardedTimestampUs = Math.max(largestDiscardedTimestampUs,
          getLargestTimestamp(discardCount));
      length -= discardCount;
      absoluteFirstIndex += discardCount;
      relativeFirstIndex += discardCount;
      if (relativeFirstIndex >= capacity) {
        relativeFirstIndex -= capacity;
      }
      readPosition -= discardCount;
      if (readPosition < 0) {
        readPosition = 0;
      }
      if (length == 0) {
        int relativeLastDiscardIndex = (relativeFirstIndex == 0 ? capacity : relativeFirstIndex) - 1;
        return offsets[relativeLastDiscardIndex] + sizes[relativeLastDiscardIndex];
      } else {
        return offsets[relativeFirstIndex];
      }
    }
  
    /**
     * Finds the largest timestamp of any sample from the start of the queue up to the specified
     * length, assuming that the timestamps prior to a keyframe are always less than the timestamp of
     * the keyframe itself, and of subsequent frames.
     *
     * @param length The length of the range being searched.
     * @return The largest timestamp, or {@link Long#MIN_VALUE} if {@code length == 0}.
     */
    private long getLargestTimestamp(int length) {
      if (length == 0) {
        return Long.MIN_VALUE;
      }
      long largestTimestampUs = Long.MIN_VALUE;
      int relativeSampleIndex = getRelativeIndex(length - 1);
      for (int i = 0; i < length; i++) {
        largestTimestampUs = Math.max(largestTimestampUs, timesUs[relativeSampleIndex]);
        if ((flags[relativeSampleIndex] & C.BUFFER_FLAG_KEY_FRAME) != 0) {
          break;
        }
        relativeSampleIndex--;
        if (relativeSampleIndex == -1) {
          relativeSampleIndex = capacity - 1;
        }
      }
      return largestTimestampUs;
    }
  
     /**
      * Returns the relative index for a given offset from the start of the queue.
      *
      * @param offset The offset, which must be in the range [0, length].
      */
    private int getRelativeIndex(int offset) {
      int relativeIndex = relativeFirstIndex + offset;
      return relativeIndex < capacity ? relativeIndex : relativeIndex - capacity;
    }
  
  }
  