1 /* 2 * Copyright (C) 2017 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.internal.util; 18 19 import static com.android.internal.util.Preconditions.checkArgumentPositive; 20 21 import java.lang.reflect.Array; 22 import java.lang.reflect.InvocationTargetException; 23 import java.util.Arrays; 24 import java.util.function.IntFunction; 25 import java.util.function.Supplier; 26 27 /** 28 * A simple ring buffer structure with bounded capacity backed by an array. 29 * Events can always be added at the logical end of the buffer. If the buffer is 30 * full, oldest events are dropped when new events are added. 31 * {@hide} 32 */ 33 @android.ravenwood.annotation.RavenwoodKeepWholeClass 34 public class RingBuffer<T> { 35 36 private final Supplier<T> mNewItem; 37 // Array for storing events. 38 private final T[] mBuffer; 39 // Cursor keeping track of the logical end of the array. This cursor never 40 // wraps and instead keeps track of the total number of append() operations. 41 private long mCursor = 0; 42 43 /** 44 * @deprecated This uses reflection to create new instances. 45 * Use {@link #RingBuffer(Supplier, IntFunction, int)}} instead. 46 */ 47 @Deprecated RingBuffer(Class<T> c, int capacity)48 public RingBuffer(Class<T> c, int capacity) { 49 this(() -> (T) createNewItem(c), cap -> (T[]) Array.newInstance(c, cap), capacity); 50 } 51 createNewItem(Class c)52 private static Object createNewItem(Class c) { 53 try { 54 return c.getDeclaredConstructor().newInstance(); 55 } catch (IllegalAccessException | InstantiationException | NoSuchMethodException 56 | InvocationTargetException e) { 57 return null; 58 } 59 } 60 RingBuffer(Supplier<T> newItem, IntFunction<T[]> newBacking, int capacity)61 public RingBuffer(Supplier<T> newItem, IntFunction<T[]> newBacking, int capacity) { 62 checkArgumentPositive(capacity, "A RingBuffer cannot have 0 capacity"); 63 mBuffer = newBacking.apply(capacity); 64 mNewItem = newItem; 65 } 66 size()67 public int size() { 68 return (int) Math.min(mBuffer.length, (long) mCursor); 69 } 70 isEmpty()71 public boolean isEmpty() { 72 return size() == 0; 73 } 74 clear()75 public void clear() { 76 for (int i = 0; i < size(); ++i) { 77 mBuffer[i] = null; 78 } 79 mCursor = 0; 80 } 81 append(T t)82 public void append(T t) { 83 mBuffer[indexOf(mCursor++)] = t; 84 } 85 86 /** 87 * Returns object of type <T> at the next writable slot, creating one if it is not already 88 * available. In case of any errors while creating the object, <code>null</code> will 89 * be returned. 90 */ getNextSlot()91 public T getNextSlot() { 92 final int nextSlotIdx = indexOf(mCursor++); 93 if (mBuffer[nextSlotIdx] == null) { 94 mBuffer[nextSlotIdx] = mNewItem.get(); 95 } 96 return mBuffer[nextSlotIdx]; 97 } 98 toArray()99 public T[] toArray() { 100 // Only generic way to create a T[] from another T[] 101 T[] out = Arrays.copyOf(mBuffer, size(), (Class<T[]>) mBuffer.getClass()); 102 // Reverse iteration from youngest event to oldest event. 103 long inCursor = mCursor - 1; 104 int outIdx = out.length - 1; 105 while (outIdx >= 0) { 106 out[outIdx--] = (T) mBuffer[indexOf(inCursor--)]; 107 } 108 return out; 109 } 110 indexOf(long cursor)111 private int indexOf(long cursor) { 112 return (int) Math.abs(cursor % mBuffer.length); 113 } 114 } 115