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
17package com.android.internal.util;
18
19import static com.android.internal.util.Preconditions.checkArgumentPositive;
20
21import java.lang.reflect.Array;
22import 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 */
30public 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
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
44    public int size() {
45        return (int) Math.min(mBuffer.length, (long) mCursor);
46    }
47
48    public boolean isEmpty() {
49        return size() == 0;
50    }
51
52    public void clear() {
53        for (int i = 0; i < size(); ++i) {
54            mBuffer[i] = null;
55        }
56        mCursor = 0;
57    }
58
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     */
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     */
79    protected T createNewItem() {
80        try {
81            return (T) mBuffer.getClass().getComponentType().newInstance();
82        } catch (IllegalAccessException | InstantiationException e) {
83            return null;
84        }
85    }
86
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
99    private int indexOf(long cursor) {
100        return (int) Math.abs(cursor % mBuffer.length);
101    }
102}
103