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 = (absoluteIndex == 0) ? (kCapacity - 1) : (absoluteIndex - 1);
162 data()[absoluteIndex] = data()[prev];
163 absoluteIndex = prev;
164 }
165
166 pullHead();
167 success = true;
168 }
169 return success;
170 }
171
172 template<typename ElementType, size_t kCapacity>
173 template<typename... Args>
emplace(Args &&...args)174 bool ArrayQueue<ElementType, kCapacity>::emplace(Args&&... args) {
175 bool success = pushTail();
176 if (success) {
177 new (&data()[mTail]) ElementType(std::forward<Args>(args)...);
178 }
179 return success;
180 }
181
182 template<typename ElementType, size_t kCapacity>
clear()183 void ArrayQueue<ElementType, kCapacity>::clear() {
184 if (!std::is_trivially_destructible<ElementType>::value) {
185 while (!empty()) {
186 pop();
187 }
188 } else {
189 mSize = 0;
190 mHead = 0;
191 mTail = kCapacity - 1;
192 }
193 }
194
195 template<typename ElementType, size_t kCapacity>
196 typename ArrayQueue<ElementType, kCapacity>::iterator
begin()197 ArrayQueue<ElementType, kCapacity>::begin() {
198 // Align begin() and end() outside of the memory block when empty.
199 return empty() ? end() : iterator(data() + mHead, data(), mTail);
200 }
201
202 template<typename ElementType, size_t kCapacity>
203 typename ArrayQueue<ElementType, kCapacity>::iterator
end()204 ArrayQueue<ElementType, kCapacity>::end() {
205 return iterator(data() + kCapacity, data(), mTail);
206 }
207
208 template<typename ElementType, size_t kCapacity>
209 typename ArrayQueue<ElementType, kCapacity>::const_iterator
begin()210 ArrayQueue<ElementType, kCapacity>::begin() const {
211 return cbegin();
212 }
213
214 template<typename ElementType, size_t kCapacity>
215 typename ArrayQueue<ElementType, kCapacity>::const_iterator
end()216 ArrayQueue<ElementType, kCapacity>::end() const {
217 return cend();
218 }
219
220 template<typename ElementType, size_t kCapacity>
221 typename ArrayQueue<ElementType, kCapacity>::const_iterator
cbegin()222 ArrayQueue<ElementType, kCapacity>::cbegin() const {
223 // Align begin() and end() outside of the memory block when empty.
224 return empty() ? cend() : const_iterator(data() + mHead, data(), mTail);
225 }
226
227 template<typename ElementType, size_t kCapacity>
228 typename ArrayQueue<ElementType, kCapacity>::const_iterator
cend()229 ArrayQueue<ElementType, kCapacity>::cend() const {
230 return const_iterator(data() + kCapacity, data(), mTail);
231 }
232
233 template<typename ElementType, size_t kCapacity>
data()234 ElementType *ArrayQueue<ElementType, kCapacity>::data() {
235 return reinterpret_cast<ElementType *>(mData);
236 }
237
238 template<typename ElementType, size_t kCapacity>
data()239 const ElementType *ArrayQueue<ElementType, kCapacity>::data() const {
240 return reinterpret_cast<const ElementType *>(mData);
241 }
242
243 template<typename ElementType, size_t kCapacity>
relativeIndexToAbsolute(size_t index)244 size_t ArrayQueue<ElementType, kCapacity>::relativeIndexToAbsolute(
245 size_t index) const {
246 size_t absoluteIndex = mHead + index;
247 if (absoluteIndex >= kCapacity) {
248 absoluteIndex -= kCapacity;
249 }
250 return absoluteIndex;
251 }
252
253 template<typename ElementType, size_t kCapacity>
pullHead()254 void ArrayQueue<ElementType, kCapacity>::pullHead() {
255 CHRE_ASSERT(mSize > 0);
256 if (++mHead == kCapacity) {
257 mHead = 0;
258 }
259 mSize--;
260 }
261
262 template<typename ElementType, size_t kCapacity>
pullTail()263 void ArrayQueue<ElementType, kCapacity>::pullTail() {
264 CHRE_ASSERT(mSize > 0);
265 if (mTail == 0) {
266 mTail = kCapacity - 1;
267 } else {
268 mTail--;
269 }
270 mSize--;
271 }
272
273 template<typename ElementType, size_t kCapacity>
pushTail()274 bool ArrayQueue<ElementType, kCapacity>::pushTail() {
275 bool success;
276 if (mSize >= kCapacity) {
277 success = false;
278 } else {
279 if (++mTail == kCapacity) {
280 mTail = 0;
281 }
282 mSize++;
283 success = true;
284 }
285 return success;
286 }
287
288 } // namespace chre
289
290 #endif // CHRE_UTIL_ARRAY_QUEUE_IMPL_H_
291