1 /* 2 * Copyright (C) 2018 The Android Open Source Project 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * 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 package org.mozilla.thirdparty.com.google.android.exoplayer2.util; 17 18 import androidx.annotation.Nullable; 19 import java.util.Arrays; 20 import org.checkerframework.checker.nullness.compatqual.NullableType; 21 22 /** A utility class to keep a queue of values with timestamps. This class is thread safe. */ 23 public final class TimedValueQueue<V> { 24 private static final int INITIAL_BUFFER_SIZE = 10; 25 26 // Looping buffer for timestamps and values 27 private long[] timestamps; 28 private @NullableType V[] values; 29 private int first; 30 private int size; 31 TimedValueQueue()32 public TimedValueQueue() { 33 this(INITIAL_BUFFER_SIZE); 34 } 35 36 /** Creates a TimedValueBuffer with the given initial buffer size. */ TimedValueQueue(int initialBufferSize)37 public TimedValueQueue(int initialBufferSize) { 38 timestamps = new long[initialBufferSize]; 39 values = newArray(initialBufferSize); 40 } 41 42 /** 43 * Associates the specified value with the specified timestamp. All new values should have a 44 * greater timestamp than the previously added values. Otherwise all values are removed before 45 * adding the new one. 46 */ add(long timestamp, V value)47 public synchronized void add(long timestamp, V value) { 48 clearBufferOnTimeDiscontinuity(timestamp); 49 doubleCapacityIfFull(); 50 addUnchecked(timestamp, value); 51 } 52 53 /** Removes all of the values. */ clear()54 public synchronized void clear() { 55 first = 0; 56 size = 0; 57 Arrays.fill(values, null); 58 } 59 60 /** Returns number of the values buffered. */ size()61 public synchronized int size() { 62 return size; 63 } 64 65 /** 66 * Returns the value with the greatest timestamp which is less than or equal to the given 67 * timestamp. Removes all older values and the returned one from the buffer. 68 * 69 * @param timestamp The timestamp value. 70 * @return The value with the greatest timestamp which is less than or equal to the given 71 * timestamp or null if there is no such value. 72 * @see #poll(long) 73 */ pollFloor(long timestamp)74 public synchronized @Nullable V pollFloor(long timestamp) { 75 return poll(timestamp, /* onlyOlder= */ true); 76 } 77 78 /** 79 * Returns the value with the closest timestamp to the given timestamp. Removes all older values 80 * including the returned one from the buffer. 81 * 82 * @param timestamp The timestamp value. 83 * @return The value with the closest timestamp or null if the buffer is empty. 84 * @see #pollFloor(long) 85 */ poll(long timestamp)86 public synchronized @Nullable V poll(long timestamp) { 87 return poll(timestamp, /* onlyOlder= */ false); 88 } 89 90 /** 91 * Returns the value with the closest timestamp to the given timestamp. Removes all older values 92 * including the returned one from the buffer. 93 * 94 * @param timestamp The timestamp value. 95 * @param onlyOlder Whether this method can return a new value in case its timestamp value is 96 * closest to {@code timestamp}. 97 * @return The value with the closest timestamp or null if the buffer is empty or there is no 98 * older value and {@code onlyOlder} is true. 99 */ 100 @Nullable poll(long timestamp, boolean onlyOlder)101 private V poll(long timestamp, boolean onlyOlder) { 102 V value = null; 103 long previousTimeDiff = Long.MAX_VALUE; 104 while (size > 0) { 105 long timeDiff = timestamp - timestamps[first]; 106 if (timeDiff < 0 && (onlyOlder || -timeDiff >= previousTimeDiff)) { 107 break; 108 } 109 previousTimeDiff = timeDiff; 110 value = values[first]; 111 values[first] = null; 112 first = (first + 1) % values.length; 113 size--; 114 } 115 return value; 116 } 117 clearBufferOnTimeDiscontinuity(long timestamp)118 private void clearBufferOnTimeDiscontinuity(long timestamp) { 119 if (size > 0) { 120 int last = (first + size - 1) % values.length; 121 if (timestamp <= timestamps[last]) { 122 clear(); 123 } 124 } 125 } 126 doubleCapacityIfFull()127 private void doubleCapacityIfFull() { 128 int capacity = values.length; 129 if (size < capacity) { 130 return; 131 } 132 int newCapacity = capacity * 2; 133 long[] newTimestamps = new long[newCapacity]; 134 V[] newValues = newArray(newCapacity); 135 // Reset the loop starting index to 0 while coping to the new buffer. 136 // First copy the values from 'first' index to the end of original array. 137 int length = capacity - first; 138 System.arraycopy(timestamps, first, newTimestamps, 0, length); 139 System.arraycopy(values, first, newValues, 0, length); 140 // Then the values from index 0 to 'first' index. 141 if (first > 0) { 142 System.arraycopy(timestamps, 0, newTimestamps, length, first); 143 System.arraycopy(values, 0, newValues, length, first); 144 } 145 timestamps = newTimestamps; 146 values = newValues; 147 first = 0; 148 } 149 addUnchecked(long timestamp, V value)150 private void addUnchecked(long timestamp, V value) { 151 int next = (first + size) % values.length; 152 timestamps[next] = timestamp; 153 values[next] = value; 154 size++; 155 } 156 157 @SuppressWarnings("unchecked") newArray(int length)158 private static <V> V[] newArray(int length) { 159 return (V[]) new Object[length]; 160 } 161 } 162