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.util.Arrays;
23 
24 /**
25  * A simple ring buffer structure with bounded capacity backed by an array.
26  * Events can always be added at the logical end of the buffer. If the buffer is
27  * full, oldest events are dropped when new events are added.
28  * {@hide}
29  */
30 public class RingBuffer<T> {
31 
32     // Array for storing events.
33     private final T[] mBuffer;
34     // Cursor keeping track of the logical end of the array. This cursor never
35     // wraps and instead keeps track of the total number of append() operations.
36     private long mCursor = 0;
37 
RingBuffer(Class<T> c, int capacity)38     public RingBuffer(Class<T> c, int capacity) {
39         checkArgumentPositive(capacity, "A RingBuffer cannot have 0 capacity");
40         // Java cannot create generic arrays without a runtime hint.
41         mBuffer = (T[]) Array.newInstance(c, capacity);
42     }
43 
size()44     public int size() {
45         return (int) Math.min(mBuffer.length, (long) mCursor);
46     }
47 
isEmpty()48     public boolean isEmpty() {
49         return size() == 0;
50     }
51 
clear()52     public void clear() {
53         for (int i = 0; i < size(); ++i) {
54             mBuffer[i] = null;
55         }
56         mCursor = 0;
57     }
58 
append(T t)59     public void append(T t) {
60         mBuffer[indexOf(mCursor++)] = t;
61     }
62 
63     /**
64      * Returns object of type <T> at the next writable slot, creating one if it is not already
65      * available. In case of any errors while creating the object, <code>null</code> will
66      * be returned.
67      */
getNextSlot()68     public T getNextSlot() {
69         final int nextSlotIdx = indexOf(mCursor++);
70         if (mBuffer[nextSlotIdx] == null) {
71             mBuffer[nextSlotIdx] = createNewItem();
72         }
73         return mBuffer[nextSlotIdx];
74     }
75 
76     /**
77      * @return a new object of type <T> or null if a new object could not be created.
78      */
createNewItem()79     protected T createNewItem() {
80         try {
81             return (T) mBuffer.getClass().getComponentType().newInstance();
82         } catch (IllegalAccessException | InstantiationException e) {
83             return null;
84         }
85     }
86 
toArray()87     public T[] toArray() {
88         // Only generic way to create a T[] from another T[]
89         T[] out = Arrays.copyOf(mBuffer, size(), (Class<T[]>) mBuffer.getClass());
90         // Reverse iteration from youngest event to oldest event.
91         long inCursor = mCursor - 1;
92         int outIdx = out.length - 1;
93         while (outIdx >= 0) {
94             out[outIdx--] = (T) mBuffer[indexOf(inCursor--)];
95         }
96         return out;
97     }
98 
indexOf(long cursor)99     private int indexOf(long cursor) {
100         return (int) Math.abs(cursor % mBuffer.length);
101     }
102 }
103