1 /*
2  * Copyright (C) 2022 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.systemui.common.buffer
18 
19 import kotlin.math.max
20 
21 /**
22  * A simple ring buffer of recycled items
23  *
24  * Use [advance] to add items to the buffer.
25  *
26  * As the buffer is used, it will grow, allocating new instances of T using [factory] until it
27  * reaches [maxSize]. After this point, no new instances will be created. Instead, calls to
28  * [advance] will recycle the "oldest" instance from the start of the buffer, placing it at the end.
29  *
30  * The items in the buffer are "recycled" in that they are reused, but it is up to the caller of
31  * [advance] to properly reset any data that was previously stored on those items.
32  *
33  * @param maxSize The maximum size the buffer can grow to before it begins functioning as a ring.
34  * @param factory A function that creates a fresh instance of T. Used by the buffer while it's
35  *   growing to [maxSize].
36  */
37 class RingBuffer<T>(private val maxSize: Int, private val factory: () -> T) : Iterable<T> {
38 
<lambda>null39     private val buffer = MutableList<T?>(maxSize) { null }
40 
41     /**
42      * An abstract representation that points to the "end" of the buffer, i.e. one beyond the
43      * location of the last item. Increments every time [advance] is called and is never wrapped.
44      *
45      * Use [indexOf] to calculate the associated index into the backing array. Before the buffer has
46      * been completely filled, this will point to the next empty slot to fill; afterwards it will
47      * point to the next item that should be recycled (which, because the buffer is a ring, is the
48      * "start" of the buffer).
49      *
50      * This value is unlikely to overflow. Assuming [advance] is called at rate of 100 calls/ms,
51      * omega will overflow after a little under three million years of continuous operation.
52      */
53     private var omega: Long = 0
54 
55     /**
56      * The number of items currently stored in the buffer. Calls to [advance] will cause this value
57      * to increase by one until it reaches [maxSize].
58      */
59     val size: Int
60         get() = if (omega < maxSize) omega.toInt() else maxSize
61 
62     /**
63      * Adds an item to the end of the buffer. The caller should reset the returned item's contents
64      * and then fill it with appropriate data.
65      *
66      * If the buffer is not yet full, uses [factory] to create a new item. Otherwise, it recycles
67      * the oldest item from the front of the buffer and moves it to the end.
68      *
69      * Importantly, recycled items are returned as-is, without being reset. They will retain any
70      * data that was previously stored on them. Callers must make sure to clear any historical data,
71      * if necessary.
72      */
advancenull73     fun advance(): T {
74         val index = indexOf(omega)
75         omega += 1
76         val entry = buffer[index] ?: factory().also { buffer[index] = it }
77         return entry
78     }
79 
80     /**
81      * Returns the value stored at [index], which can range from 0 (the "start", or oldest element
82      * of the buffer) to [size] - 1 (the "end", or newest element of the buffer).
83      */
getnull84     operator fun get(index: Int): T {
85         if (index < 0 || index >= size) {
86             throw IndexOutOfBoundsException("Index $index is out of bounds")
87         }
88 
89         // If omega is larger than the maxSize, then the buffer is full, and omega is equivalent
90         // to the "start" of the buffer. If omega is smaller than the maxSize, then the buffer is
91         // not yet full and our start should be 0. However, in modspace, maxSize and 0 are
92         // equivalent, so we can get away with using it as the start value instead.
93         val start = max(omega, maxSize.toLong())
94 
95         return buffer[indexOf(start + index)]!!
96     }
97 
iteratornull98     override fun iterator(): Iterator<T> {
99         return object : Iterator<T> {
100             private var position: Int = 0
101 
102             override fun next(): T {
103                 if (position >= size) {
104                     throw NoSuchElementException()
105                 }
106                 return get(position).also { position += 1 }
107             }
108 
109             override fun hasNext(): Boolean {
110                 return position < size
111             }
112         }
113     }
114 
indexOfnull115     private fun indexOf(position: Long): Int {
116         return (position % maxSize).toInt()
117     }
118 }
119