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