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