diff options
| -rw-r--r-- | packages/SystemUI/src/com/android/systemui/util/collection/RingBuffer.kt | 122 | ||||
| -rw-r--r-- | packages/SystemUI/tests/src/com/android/systemui/util/collection/RingBufferTest.kt | 131 |
2 files changed, 253 insertions, 0 deletions
diff --git a/packages/SystemUI/src/com/android/systemui/util/collection/RingBuffer.kt b/packages/SystemUI/src/com/android/systemui/util/collection/RingBuffer.kt new file mode 100644 index 000000000000..97dc842ec699 --- /dev/null +++ b/packages/SystemUI/src/com/android/systemui/util/collection/RingBuffer.kt @@ -0,0 +1,122 @@ +/* + * Copyright (C) 2022 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.android.systemui.util.collection + +import kotlin.math.max + +/** + * A simple ring buffer implementation + * + * Use [advance] to get the least recent item in the buffer (and then presumably fill it with + * appropriate data). This will cause it to become the most recent item. + * + * As the buffer is used, it will grow, allocating new instances of T using [factory] until it + * reaches [maxSize]. After this point, no new instances will be created. Instead, the "oldest" + * instances will be recycled from the back of the buffer and placed at the front. + * + * @param maxSize The maximum size the buffer can grow to before it begins functioning as a ring. + * @param factory A function that creates a fresh instance of T. Used by the buffer while it's + * growing to [maxSize]. + */ +class RingBuffer<T>( + private val maxSize: Int, + private val factory: () -> T +) : Iterable<T> { + + private val buffer = MutableList<T?>(maxSize) { null } + + /** + * An abstract representation that points to the "end" of the buffer. Increments every time + * [advance] is called and never wraps. Use [indexOf] to calculate the associated index into + * the backing array. Always points to the "next" available slot in the buffer. Before the + * buffer has completely filled, the value pointed to will be null. Afterward, it will be the + * value at the "beginning" of the buffer. + * + * This value is unlikely to overflow. Assuming [advance] is called at rate of 100 calls/ms, + * omega will overflow after a little under three million years of continuous operation. + */ + private var omega: Long = 0 + + /** + * The number of items currently stored in the buffer. Calls to [advance] will cause this value + * to increase by one until it reaches [maxSize]. + */ + val size: Int + get() = if (omega < maxSize) omega.toInt() else maxSize + + /** + * Advances the buffer's position by one and returns the value that is now present at the "end" + * of the buffer. If the buffer is not yet full, uses [factory] to create a new item. + * Otherwise, reuses the value that was previously at the "beginning" of the buffer. + * + * IMPORTANT: The value is returned as-is, without being reset. It will retain any data that + * was previously stored on it. + */ + fun advance(): T { + val index = indexOf(omega) + omega += 1 + val entry = buffer[index] ?: factory().also { + buffer[index] = it + } + return entry + } + + /** + * Returns the value stored at [index], which can range from 0 (the "start", or oldest element + * of the buffer) to [size] - 1 (the "end", or newest element of the buffer). + */ + operator fun get(index: Int): T { + if (index < 0 || index >= size) { + throw IndexOutOfBoundsException("Index $index is out of bounds") + } + + // If omega is larger than the maxSize, then the buffer is full, and omega is equivalent + // to the "start" of the buffer. If omega is smaller than the maxSize, then the buffer is + // not yet full and our start should be 0. However, in modspace, maxSize and 0 are + // equivalent, so we can get away with using it as the start value instead. + val start = max(omega, maxSize.toLong()) + + return buffer[indexOf(start + index)]!! + } + + inline fun forEach(action: (T) -> Unit) { + for (i in 0 until size) { + action(get(i)) + } + } + + override fun iterator(): Iterator<T> { + return object : Iterator<T> { + private var position: Int = 0 + + override fun next(): T { + if (position >= size) { + throw NoSuchElementException() + } + return get(position).also { position += 1 } + } + + override fun hasNext(): Boolean { + return position < size + } + } + } + + private fun indexOf(position: Long): Int { + return (position % maxSize).toInt() + } +} diff --git a/packages/SystemUI/tests/src/com/android/systemui/util/collection/RingBufferTest.kt b/packages/SystemUI/tests/src/com/android/systemui/util/collection/RingBufferTest.kt new file mode 100644 index 000000000000..5e09b81da4e8 --- /dev/null +++ b/packages/SystemUI/tests/src/com/android/systemui/util/collection/RingBufferTest.kt @@ -0,0 +1,131 @@ +/* + * Copyright (C) 2022 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.android.systemui.util.collection + +import android.testing.AndroidTestingRunner +import androidx.test.filters.SmallTest +import com.android.systemui.SysuiTestCase +import org.junit.Assert.assertEquals +import org.junit.Assert.assertFalse +import org.junit.Assert.assertSame +import org.junit.Assert.assertThrows +import org.junit.Before +import org.junit.Test +import org.junit.runner.RunWith +import org.mockito.MockitoAnnotations + +@SmallTest +@RunWith(AndroidTestingRunner::class) +class RingBufferTest : SysuiTestCase() { + + private val buffer = RingBuffer(5) { TestElement() } + + private val history = mutableListOf<TestElement>() + + @Before + fun setUp() { + MockitoAnnotations.initMocks(this) + } + + @Test + fun testBarelyFillBuffer() { + fillBuffer(5) + + assertEquals(0, buffer[0].id) + assertEquals(1, buffer[1].id) + assertEquals(2, buffer[2].id) + assertEquals(3, buffer[3].id) + assertEquals(4, buffer[4].id) + } + + @Test + fun testPartiallyFillBuffer() { + fillBuffer(3) + + assertEquals(3, buffer.size) + + assertEquals(0, buffer[0].id) + assertEquals(1, buffer[1].id) + assertEquals(2, buffer[2].id) + + assertThrows(IndexOutOfBoundsException::class.java) { buffer[3] } + assertThrows(IndexOutOfBoundsException::class.java) { buffer[4] } + } + + @Test + fun testSpinBuffer() { + fillBuffer(277) + + assertEquals(272, buffer[0].id) + assertEquals(273, buffer[1].id) + assertEquals(274, buffer[2].id) + assertEquals(275, buffer[3].id) + assertEquals(276, buffer[4].id) + assertThrows(IndexOutOfBoundsException::class.java) { buffer[5] } + + assertEquals(5, buffer.size) + } + + @Test + fun testElementsAreRecycled() { + fillBuffer(23) + + assertSame(history[4], buffer[1]) + assertSame(history[9], buffer[1]) + assertSame(history[14], buffer[1]) + assertSame(history[19], buffer[1]) + } + + @Test + fun testIterator() { + fillBuffer(13) + + val iterator = buffer.iterator() + + for (i in 0 until 5) { + assertEquals(history[8 + i], iterator.next()) + } + assertFalse(iterator.hasNext()) + assertThrows(NoSuchElementException::class.java) { iterator.next() } + } + + @Test + fun testForEach() { + fillBuffer(13) + var i = 8 + + buffer.forEach { + assertEquals(history[i], it) + i++ + } + assertEquals(13, i) + } + + private fun fillBuffer(count: Int) { + for (i in 0 until count) { + val elem = buffer.advance() + elem.id = history.size + history.add(elem) + } + } +} + +private class TestElement(var id: Int = 0) { + override fun toString(): String { + return "{TestElement $id}" + } +}
\ No newline at end of file |