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