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