1 /*
2  * Copyright (C) 2019 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 
17 package com.android.server.display.utils;
18 
19 /**
20  * A buffer that supports adding new values and truncating old ones.
21  */
22 public class RollingBuffer {
23 
24     private static final int INITIAL_SIZE = 50;
25 
26     private int mSize;
27     private int mCount;
28     private int mStart;
29     private int mEnd;
30 
31     private long[] mTimes; // Milliseconds
32     private float[] mValues;
33 
RollingBuffer()34     public RollingBuffer() {
35         mSize = INITIAL_SIZE;
36         mTimes = new long[INITIAL_SIZE];
37         mValues = new float[INITIAL_SIZE];
38         clear();
39     }
40 
41     /**
42      * Add a value at a given time.
43      *
44      * @param time
45      *      The time (in milliseconds).
46      * @param value
47      *      The value.
48      */
add(long time, float value)49     public void add(long time, float value) {
50         if (mCount >= mSize) {
51             expandBuffer();
52         }
53         mTimes[mEnd] = time;
54         mValues[mEnd] = value;
55         mEnd = (mEnd + 1) % mSize;
56         mCount++;
57     }
58 
59     /**
60      * Get the size of the buffer.
61      *
62      * @return The size of the buffer.
63      */
size()64     public int size() {
65         return mCount;
66     }
67 
68     /**
69      * Return whether the buffer is empty or not.
70      *
71      * @return Whether the buffer is empty or not.
72      */
isEmpty()73     public boolean isEmpty() {
74         return size() == 0;
75     }
76 
77     /**
78      * Get a time.
79      *
80      * @param index
81      *      The index of the time.
82      *
83      * @return The time.
84      */
getTime(int index)85     public long getTime(int index) {
86         return mTimes[offsetOf(index)];
87     }
88 
89     /**
90      * Get a value.
91      *
92      * @param index
93      *      The index of the value.
94      *
95      * @return The value.
96      */
getValue(int index)97     public float getValue(int index) {
98         return mValues[offsetOf(index)];
99     }
100 
101     /**
102      * Truncate old values.
103      *
104      * @param minTime
105      *      The minimum time (all values older than this time are truncated).
106      */
truncate(long minTime)107     public void truncate(long minTime) {
108         if (isEmpty() || getTime(0) >= minTime) {
109             return;
110         }
111         final int index = getLatestIndexBefore(minTime);
112         mStart = offsetOf(index);
113         mCount -= index;
114         // Remove everything that happened before mTimes[index], but set the index-th value time to
115         // minTime rather than dropping it, as that would've been the value between the minTime and
116         // mTimes[index+1].
117         //
118         // -*---*---|---*---*- => xxxxxxxxx|*--*---*- rather than xxxxxxxxx|???*---*-
119         //      ^       ^                   ^  ^                               ^
120         //      i      i+1                  i i+1                             i+1
121         mTimes[mStart] = minTime;
122     }
123 
124     /**
125      * Clears the buffer.
126      */
clear()127     public void clear() {
128         mCount = 0;
129         mStart = 0;
130         mEnd = 0;
131     }
132 
133     /**
134      * Convert the buffer to string.
135      *
136      * @return The buffer as string.
137      */
toString()138     public String toString() {
139         StringBuilder sb = new StringBuilder();
140         sb.append("[");
141         for (int i = 0; i < mCount; i++) {
142             final int index = offsetOf(i);
143             sb.append(mValues[index] + " @ " + mTimes[index]);
144             if (i + 1 != mCount) {
145                 sb.append(", ");
146             }
147         }
148         sb.append("]");
149         return sb.toString();
150     }
151 
offsetOf(int index)152     private int offsetOf(int index) {
153         if (index < 0 || index >= mCount) {
154             throw new ArrayIndexOutOfBoundsException("invalid index: " + index + ", mCount= "
155                     + mCount);
156         }
157         return (mStart + index) % mSize;
158     }
159 
expandBuffer()160     private void expandBuffer() {
161         final int size = mSize * 2;
162         long[] times = new long[size];
163         float[] values = new float[size];
164         System.arraycopy(mTimes, mStart, times, 0, mCount - mStart);
165         System.arraycopy(mTimes, 0, times, mCount - mStart, mStart);
166         System.arraycopy(mValues, mStart, values, 0, mCount - mStart);
167         System.arraycopy(mValues, 0, values, mCount - mStart, mStart);
168         mSize = size;
169         mStart = 0;
170         mEnd = mCount;
171         mTimes = times;
172         mValues = values;
173     }
174 
getLatestIndexBefore(long time)175     private int getLatestIndexBefore(long time) {
176         for (int i = 1; i < mCount; i++) {
177             if (mTimes[offsetOf(i)] > time) {
178                 return i - 1;
179             }
180         }
181         return mCount - 1;
182     }
183 
184 }
185