1/*
2 * Copyright (C) 2016 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#ifndef CHRE_UTIL_ARRAY_QUEUE_IMPL_H_
18#define CHRE_UTIL_ARRAY_QUEUE_IMPL_H_
19
20#include <new>
21#include <utility>
22
23#include "chre/util/array_queue.h"
24#include "chre/util/container_support.h"
25
26namespace chre {
27
28template<typename ElementType, size_t kCapacity>
29ArrayQueue<ElementType, kCapacity>::~ArrayQueue() {
30  while (!empty()) {
31    pop();
32  }
33}
34
35template<typename ElementType, size_t kCapacity>
36bool ArrayQueue<ElementType, kCapacity>::empty() const {
37  return (mSize == 0);
38}
39
40template<typename ElementType, size_t kCapacity>
41bool ArrayQueue<ElementType, kCapacity>::full() const {
42  return (mSize == kCapacity);
43}
44
45template<typename ElementType, size_t kCapacity>
46size_t ArrayQueue<ElementType, kCapacity>::size() const {
47  return mSize;
48}
49
50template<typename ElementType, size_t kCapacity>
51ElementType& ArrayQueue<ElementType, kCapacity>::front() {
52  CHRE_ASSERT(mSize > 0);
53  return data()[mHead];
54}
55
56template<typename ElementType, size_t kCapacity>
57const ElementType& ArrayQueue<ElementType, kCapacity>::front() const {
58  CHRE_ASSERT(mSize > 0);
59  return data()[mHead];
60}
61
62template<typename ElementType, size_t kCapacity>
63ElementType& ArrayQueue<ElementType, kCapacity>::back() {
64  CHRE_ASSERT(mSize > 0);
65  return data()[mTail];
66}
67
68template<typename ElementType, size_t kCapacity>
69const ElementType& ArrayQueue<ElementType, kCapacity>::back() const {
70  CHRE_ASSERT(mSize > 0);
71  return data()[mTail];
72}
73
74template<typename ElementType, size_t kCapacity>
75ElementType& ArrayQueue<ElementType, kCapacity>::operator[](size_t index) {
76  CHRE_ASSERT(index < mSize);
77  return data()[relativeIndexToAbsolute(index)];
78}
79
80template<typename ElementType, size_t kCapacity>
81const ElementType& ArrayQueue<ElementType, kCapacity>::operator[](
82    size_t index) const {
83  CHRE_ASSERT(index < mSize);
84  return data()[relativeIndexToAbsolute(index)];
85}
86
87template<typename ElementType, size_t kCapacity>
88bool ArrayQueue<ElementType, kCapacity>::push(const ElementType& element) {
89  bool success = pushTail();
90  if (success) {
91    new (&data()[mTail]) ElementType(element);
92  }
93  return success;
94}
95
96template<typename ElementType, size_t kCapacity>
97bool ArrayQueue<ElementType, kCapacity>::push(ElementType&& element) {
98  bool success = pushTail();
99  if (success) {
100    new (&data()[mTail]) ElementType(std::move(element));
101  }
102  return success;
103}
104
105template<typename ElementType, size_t kCapacity>
106void ArrayQueue<ElementType, kCapacity>::pop() {
107  if (mSize > 0) {
108    data()[mHead].~ElementType();
109    pullHead();
110  }
111}
112
113template<typename ElementType, size_t kCapacity>
114void ArrayQueue<ElementType, kCapacity>::pop_back() {
115  if (mSize > 0) {
116    size_t absoluteIndex = relativeIndexToAbsolute(mSize - 1);
117    data()[absoluteIndex].~ElementType();
118    pullTail();
119  }
120}
121
122// Assuming popping from the middle of the queue is rare, part of the
123// array is copied over.
124template<typename ElementType, size_t kCapacity>
125bool ArrayQueue<ElementType, kCapacity>::remove(size_t index) {
126  // If we used memmove to shift the array down when removing an element in the
127  // middle of the queue, then we'd need to add this somewhere:
128  // static_assert(std::is_trivially_copyable<ElementType>::value,
129  //               "Elements within ArrayQueue must be trivially copyable");
130
131  bool success;
132  if (index >= mSize) {
133    success = false;
134  } else {
135    // Number of elements before the one to be popped
136    size_t headLength = index;
137
138    size_t absoluteIndex = relativeIndexToAbsolute(index);
139    data()[absoluteIndex].~ElementType();
140
141    // Move all the elements before the one just popped to the next storage
142    // space.
143    // TODO: optimize by comparing headLength to mSize/2.
144    // If headLength < mSize/2, pull heads towards tail.
145    // Otherwise, pull tails towards head.
146    for (size_t i = 0; i < headLength; ++i) {
147      size_t prev = (absoluteIndex == 0) ? (kCapacity - 1) : (absoluteIndex - 1);
148      data()[absoluteIndex] = data()[prev];
149      absoluteIndex = prev;
150    }
151
152    pullHead();
153    success = true;
154  }
155  return success;
156}
157
158template<typename ElementType, size_t kCapacity>
159template<typename... Args>
160bool ArrayQueue<ElementType, kCapacity>::emplace(Args&&... args) {
161  bool success = pushTail();
162  if (success) {
163    new (&data()[mTail]) ElementType(std::forward<Args>(args)...);
164  }
165  return success;
166}
167
168template<typename ElementType, size_t kCapacity>
169typename ArrayQueue<ElementType, kCapacity>::iterator
170ArrayQueue<ElementType, kCapacity>::begin() {
171  // Align begin() and end() outside of the memory block when empty.
172  return empty() ? end() : iterator(data() + mHead, data(), mTail);
173}
174
175template<typename ElementType, size_t kCapacity>
176typename ArrayQueue<ElementType, kCapacity>::iterator
177    ArrayQueue<ElementType, kCapacity>::end() {
178  return iterator(data() + kCapacity, data(), mTail);
179}
180
181template<typename ElementType, size_t kCapacity>
182typename ArrayQueue<ElementType, kCapacity>::const_iterator
183ArrayQueue<ElementType, kCapacity>::begin() const {
184  return cbegin();
185}
186
187template<typename ElementType, size_t kCapacity>
188typename ArrayQueue<ElementType, kCapacity>::const_iterator
189    ArrayQueue<ElementType, kCapacity>::end() const {
190  return cend();
191}
192
193template<typename ElementType, size_t kCapacity>
194typename ArrayQueue<ElementType, kCapacity>::const_iterator
195ArrayQueue<ElementType, kCapacity>::cbegin() const {
196  // Align begin() and end() outside of the memory block when empty.
197  return empty() ? cend() : const_iterator(data() + mHead, data(), mTail);
198}
199
200template<typename ElementType, size_t kCapacity>
201typename ArrayQueue<ElementType, kCapacity>::const_iterator
202    ArrayQueue<ElementType, kCapacity>::cend() const {
203  return const_iterator(data() + kCapacity, data(), mTail);
204}
205
206template<typename ElementType, size_t kCapacity>
207ElementType *ArrayQueue<ElementType, kCapacity>::data() {
208  return reinterpret_cast<ElementType *>(mData);
209}
210
211template<typename ElementType, size_t kCapacity>
212const ElementType *ArrayQueue<ElementType, kCapacity>::data() const {
213  return reinterpret_cast<const ElementType *>(mData);
214}
215
216template<typename ElementType, size_t kCapacity>
217size_t ArrayQueue<ElementType, kCapacity>::relativeIndexToAbsolute(
218    size_t index) const {
219  size_t absoluteIndex = mHead + index;
220  if (absoluteIndex >= kCapacity) {
221    absoluteIndex -= kCapacity;
222  }
223  return absoluteIndex;
224}
225
226template<typename ElementType, size_t kCapacity>
227void ArrayQueue<ElementType, kCapacity>::pullHead() {
228  CHRE_ASSERT(mSize > 0);
229  if (++mHead == kCapacity) {
230      mHead = 0;
231  }
232  mSize--;
233}
234
235template<typename ElementType, size_t kCapacity>
236void ArrayQueue<ElementType, kCapacity>::pullTail() {
237  CHRE_ASSERT(mSize > 0);
238  if (mTail == 0) {
239    mTail = kCapacity - 1;
240  } else {
241    mTail--;
242  }
243  mSize--;
244}
245
246template<typename ElementType, size_t kCapacity>
247bool ArrayQueue<ElementType, kCapacity>::pushTail() {
248  bool success;
249  if (mSize >= kCapacity) {
250    success = false;
251  } else {
252    if (++mTail == kCapacity) {
253      mTail = 0;
254    }
255    mSize++;
256    success = true;
257  }
258  return success;
259}
260
261}  // namespace chre
262
263#endif  // CHRE_UTIL_ARRAY_QUEUE_IMPL_H_
264