diff options
| -rw-r--r-- | service/java/com/android/server/wifi/util/ByteArrayRingBuffer.java | 82 | ||||
| -rw-r--r-- | tests/wifitests/src/com/android/server/wifi/ByteArrayRingBufferTest.java | 153 |
2 files changed, 235 insertions, 0 deletions
diff --git a/service/java/com/android/server/wifi/util/ByteArrayRingBuffer.java b/service/java/com/android/server/wifi/util/ByteArrayRingBuffer.java new file mode 100644 index 000000000..8fa9a47df --- /dev/null +++ b/service/java/com/android/server/wifi/util/ByteArrayRingBuffer.java @@ -0,0 +1,82 @@ +/* + * Copyright (C) 2016 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.server.wifi.util; + +import java.util.ArrayList; + +/** + * A ring buffer where each element of the ring is itself a byte array. + */ +public class ByteArrayRingBuffer { + private ArrayList<byte[]> mArrayList; + private final int mMaxBytes; + private int mBytesUsed; + + /** + * Creates a ring buffer that holds at most |maxBytes| of data. The overhead for each element + * is not included in this limit. + * @param maxBytes upper bound on the amount of data held + */ + public ByteArrayRingBuffer(int maxBytes) { + mArrayList = new ArrayList<byte[]>(); + mMaxBytes = maxBytes; + mBytesUsed = 0; + } + + /** + * Adds |newData| to the ring buffer. Removes existing entries to make room, if necessary. + * Existing entries are removed in FIFO order. + * <p><b>Note:</b> will fail if |newData| itself exceeds the size limit for this buffer. + * Will first remove all existing entries in this case. (This guarantees that the ring buffer + * always represents a contiguous sequence of data.) + * @param newData data to be added to the ring + * @return true if the data was added + */ + public boolean appendBuffer(byte[] newData) { + // Loop is O(n^2), but |n| is expected to be small. + while (mBytesUsed + newData.length > mMaxBytes + && !mArrayList.isEmpty()) { + mBytesUsed -= mArrayList.get(0).length; + mArrayList.remove(0); + } + + if (mBytesUsed + newData.length > mMaxBytes) { + return false; + } + + mArrayList.add(newData); + mBytesUsed += newData.length; + return true; + } + + /** + * Returns the |i|-th element of the ring. The element retains its position in the ring. + * @param i + * @return the requested element + */ + public byte[] getBuffer(int i) { + return mArrayList.get(i); + } + + /** + * Returns the number of elements present in the ring. + * @return the number of elements present + */ + public int getNumBuffers() { + return mArrayList.size(); + } +} diff --git a/tests/wifitests/src/com/android/server/wifi/ByteArrayRingBufferTest.java b/tests/wifitests/src/com/android/server/wifi/ByteArrayRingBufferTest.java new file mode 100644 index 000000000..dcf4cfbd4 --- /dev/null +++ b/tests/wifitests/src/com/android/server/wifi/ByteArrayRingBufferTest.java @@ -0,0 +1,153 @@ +/* + * Copyright (C) 2016 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.server.wifi.util; + +import static org.junit.Assert.assertEquals; +import static org.junit.Assert.assertFalse; +import static org.junit.Assert.assertSame; +import static org.junit.Assert.assertTrue; + +import android.test.suitebuilder.annotation.SmallTest; + +import org.junit.Test; + + +/** + * Unit tests for {@link com.android.server.wifi.util.ByteArrayRingBuffer}. + */ +@SmallTest +public class ByteArrayRingBufferTest { + private static final int MAX_BYTES = 10; + + @Test + public void ctorCreatesEmptyRingBuffer() { + final ByteArrayRingBuffer rb = new ByteArrayRingBuffer(MAX_BYTES); + assertEquals(0, rb.getNumBuffers()); + } + + @Test + public void canAddAndRetrieveSingleElement() { + final ByteArrayRingBuffer rb = new ByteArrayRingBuffer(MAX_BYTES); + final byte[] data = {0}; + assertTrue(rb.appendBuffer(data)); + assertEquals(1, rb.getNumBuffers()); + assertSame(data, rb.getBuffer(0)); + } + + @Test + public void canAddAndRetrieveMultipleElements() { + final ByteArrayRingBuffer rb = new ByteArrayRingBuffer(MAX_BYTES); + final byte[] data1 = {0}; + final byte[] data2 = {1}; + assertTrue(rb.appendBuffer(data1)); + assertTrue(rb.appendBuffer(data2)); + assertEquals(2, rb.getNumBuffers()); + assertSame(data1, rb.getBuffer(0)); + assertSame(data2, rb.getBuffer(1)); + } + + @Test + public void canFillToCapacityWithMultipleElements() { + final ByteArrayRingBuffer rb = new ByteArrayRingBuffer(MAX_BYTES); + final byte[] data1 = {1, 2, 3, 4, 5}; + final byte[] data2 = {6, 7, 8, 9, 10}; + assertEquals(MAX_BYTES, data1.length + data2.length); + assertTrue(rb.appendBuffer(data1)); + assertTrue(rb.appendBuffer(data2)); + assertEquals(2, rb.getNumBuffers()); + } + + @Test + public void canFillToCapacityWithSingleElement() { + final ByteArrayRingBuffer rb = new ByteArrayRingBuffer(MAX_BYTES); + final byte[] data = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; + assertEquals(MAX_BYTES, data.length); + assertTrue(rb.appendBuffer(data)); + } + + @Test + public void canNotOverfillWithSingleElement() { + final ByteArrayRingBuffer rb = new ByteArrayRingBuffer(MAX_BYTES); + final byte[] data = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11}; + assertTrue(data.length > MAX_BYTES); + assertFalse(rb.appendBuffer(data)); + assertEquals(0, rb.getNumBuffers()); + } + + @Test + public void appendPrunesBufferIfNecessary() { + final ByteArrayRingBuffer rb = new ByteArrayRingBuffer(MAX_BYTES); + final byte[] data1 = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; + assertTrue(rb.appendBuffer(data1)); + + final byte[] data2 = {11}; + assertTrue(rb.appendBuffer(data2)); + assertEquals(1, rb.getNumBuffers()); + assertSame(data2, rb.getBuffer(0)); + } + + @Test + public void appendPrunesMultipleBuffersIfNecessary() { + final ByteArrayRingBuffer rb = new ByteArrayRingBuffer(MAX_BYTES); + final byte[] data1 = {1, 2, 3, 4, 5}; + final byte[] data2 = {6, 7, 8, 9, 10}; + assertTrue(rb.appendBuffer(data1)); + assertTrue(rb.appendBuffer(data2)); + + final byte[] data3 = {11, 12, 13, 14, 15, 16}; + assertTrue(rb.appendBuffer(data3)); + assertEquals(1, rb.getNumBuffers()); + assertSame(data3, rb.getBuffer(0)); + } + + @Test + public void appendPrunesOnlyWhenNecessary() { + final ByteArrayRingBuffer rb = new ByteArrayRingBuffer(MAX_BYTES); + final byte[] data1 = {1, 2, 3, 4, 5}; + assertTrue(rb.appendBuffer(data1)); + + final byte[] data2 = {6}; + assertTrue(rb.appendBuffer(data2)); + assertEquals(2, rb.getNumBuffers()); + } + + @Test + public void appendPrunesInFifoOrder() { + final ByteArrayRingBuffer rb = new ByteArrayRingBuffer(MAX_BYTES); + final byte[] data1 = {1, 2, 3, 4, 5}; + final byte[] data2 = {6, 7, 8, 9, 10}; + assertTrue(rb.appendBuffer(data1)); + assertTrue(rb.appendBuffer(data2)); + + final byte[] data3 = {11}; + assertTrue(rb.appendBuffer(data3)); + assertEquals(2, rb.getNumBuffers()); + assertSame(data2, rb.getBuffer(0)); + assertSame(data3, rb.getBuffer(1)); + } + + @Test + public void appendPrunesEvenWhenNewDataCanNotFit() { + final ByteArrayRingBuffer rb = new ByteArrayRingBuffer(MAX_BYTES); + final byte[] data1 = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; + assertTrue(rb.appendBuffer(data1)); + + final byte[] data2 = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11}; + assertFalse(rb.appendBuffer(data2)); + assertEquals(0, rb.getNumBuffers()); + } +} |