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