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