array_queue_impl.h revision 8be5eabe6a4fc60c56a3b32794bb6677e26f6eab 
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/platform/assert.h"
24#include "chre/util/array_queue.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>::operator[](size_t index) {
64  CHRE_ASSERT(index < mSize);
65  return data()[relativeIndexToAbsolute(index)];
66}
67
68template<typename ElementType, size_t kCapacity>
69const ElementType& ArrayQueue<ElementType, kCapacity>::operator[](
70    size_t index) const {
71  CHRE_ASSERT(index < mSize);
72  return data()[relativeIndexToAbsolute(index)];
73}
74
75template<typename ElementType, size_t kCapacity>
76bool ArrayQueue<ElementType, kCapacity>::push(const ElementType& element) {
77  bool success = pushTail();
78  if (success) {
79    new (&data()[mTail]) ElementType(element);
80  }
81  return success;
82}
83
84template<typename ElementType, size_t kCapacity>
85bool ArrayQueue<ElementType, kCapacity>::push(ElementType&& element) {
86  bool success = pushTail();
87  if (success) {
88    new (&data()[mTail]) ElementType(std::move(element));
89  }
90  return success;
91}
92
93template<typename ElementType, size_t kCapacity>
94void ArrayQueue<ElementType, kCapacity>::pop() {
95  if (mSize > 0) {
96    data()[mHead].~ElementType();
97    pullHead();
98  }
99}
100
101// Assuming popping from the middle of the queue is rare, part of the
102// array is copied over.
103template<typename ElementType, size_t kCapacity>
104bool ArrayQueue<ElementType, kCapacity>::remove(size_t index) {
105  // If we used memmove to shift the array down when removing an element in the
106  // middle of the queue, then we'd need to add this somewhere:
107  // static_assert(std::is_trivially_copyable<ElementType>::value,
108  //               "Elements within ArrayQueue must be trivially copyable");
109
110  bool success;
111  if (index >= mSize) {
112    success = false;
113  } else {
114    // Number of elements before the one to be popped
115    size_t headLength = index;
116
117    size_t absoluteIndex = relativeIndexToAbsolute(index);
118    data()[absoluteIndex].~ElementType();
119
120    // Move all the elements before the one just popped to the next storage
121    // space.
122    // TODO: optimize by comparing headLength to mSize/2.
123    // If headLength < mSize/2, pull heads towards tail.
124    // Otherwise, pull tails towards head.
125    for (size_t i = 0; i < headLength; ++i) {
126      size_t prev = (absoluteIndex == 0) ? (kCapacity - 1) : (absoluteIndex - 1);
127      data()[absoluteIndex] = data()[prev];
128      absoluteIndex = prev;
129    }
130
131    pullHead();
132    success = true;
133  }
134  return success;
135}
136
137template<typename ElementType, size_t kCapacity>
138template<typename... Args>
139bool ArrayQueue<ElementType, kCapacity>::emplace(Args&&... args) {
140  bool success = pushTail();
141  if (success) {
142    new (&data()[mTail]) ElementType(std::forward<Args>(args)...);
143  }
144  return success;
145}
146
147template<typename ElementType, size_t kCapacity>
148typename ArrayQueue<ElementType, kCapacity>::iterator
149ArrayQueue<ElementType, kCapacity>::begin() {
150  // Align begin() and end() outside of the memory block when empty.
151  return empty() ? end() : iterator(data() + mHead, data(), mTail);
152}
153
154template<typename ElementType, size_t kCapacity>
155typename ArrayQueue<ElementType, kCapacity>::iterator
156    ArrayQueue<ElementType, kCapacity>::end() {
157  return iterator(data() + kCapacity, data(), mTail);
158}
159
160template<typename ElementType, size_t kCapacity>
161typename ArrayQueue<ElementType, kCapacity>::const_iterator
162ArrayQueue<ElementType, kCapacity>::begin() const {
163  return cbegin();
164}
165
166template<typename ElementType, size_t kCapacity>
167typename ArrayQueue<ElementType, kCapacity>::const_iterator
168    ArrayQueue<ElementType, kCapacity>::end() const {
169  return cend();
170}
171
172template<typename ElementType, size_t kCapacity>
173typename ArrayQueue<ElementType, kCapacity>::const_iterator
174ArrayQueue<ElementType, kCapacity>::cbegin() const {
175  // Align begin() and end() outside of the memory block when empty.
176  return empty() ? cend() : const_iterator(data() + mHead, data(), mTail);
177}
178
179template<typename ElementType, size_t kCapacity>
180typename ArrayQueue<ElementType, kCapacity>::const_iterator
181    ArrayQueue<ElementType, kCapacity>::cend() const {
182  return const_iterator(data() + kCapacity, data(), mTail);
183}
184
185template<typename ElementType, size_t kCapacity>
186ElementType *ArrayQueue<ElementType, kCapacity>::data() {
187  return reinterpret_cast<ElementType *>(mData);
188}
189
190template<typename ElementType, size_t kCapacity>
191const ElementType *ArrayQueue<ElementType, kCapacity>::data() const {
192  return reinterpret_cast<const ElementType *>(mData);
193}
194
195template<typename ElementType, size_t kCapacity>
196size_t ArrayQueue<ElementType, kCapacity>::relativeIndexToAbsolute(
197    size_t index) const {
198  size_t absoluteIndex = mHead + index;
199  if (absoluteIndex >= kCapacity) {
200    absoluteIndex -= kCapacity;
201  }
202  return absoluteIndex;
203}
204
205template<typename ElementType, size_t kCapacity>
206void ArrayQueue<ElementType, kCapacity>::pullHead() {
207  CHRE_ASSERT(mSize > 0);
208  if (++mHead == kCapacity) {
209      mHead = 0;
210  }
211  mSize--;
212}
213
214template<typename ElementType, size_t kCapacity>
215bool ArrayQueue<ElementType, kCapacity>::pushTail() {
216  bool success;
217  if (mSize >= kCapacity) {
218    success = false;
219  } else {
220    if (++mTail == kCapacity) {
221      mTail = 0;
222    }
223    mSize++;
224    success = true;
225  }
226  return success;
227}
228
229}  // namespace chre
230
231#endif  // CHRE_UTIL_ARRAY_QUEUE_IMPL_H_
232