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