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 26namespace chre { 27 28template<typename ElementType, size_t kCapacity> 29ArrayQueue<ElementType, kCapacity>::~ArrayQueue() { 30 while (!empty()) { 31 pop(); 32 } 33} 34 35template<typename ElementType, size_t kCapacity> 36bool ArrayQueue<ElementType, kCapacity>::empty() const { 37 return (mSize == 0); 38} 39 40template<typename ElementType, size_t kCapacity> 41bool ArrayQueue<ElementType, kCapacity>::full() const { 42 return (mSize == kCapacity); 43} 44 45template<typename ElementType, size_t kCapacity> 46size_t ArrayQueue<ElementType, kCapacity>::size() const { 47 return mSize; 48} 49 50template<typename ElementType, size_t kCapacity> 51ElementType& ArrayQueue<ElementType, kCapacity>::front() { 52 CHRE_ASSERT(mSize > 0); 53 return data()[mHead]; 54} 55 56template<typename ElementType, size_t kCapacity> 57const ElementType& ArrayQueue<ElementType, kCapacity>::front() const { 58 CHRE_ASSERT(mSize > 0); 59 return data()[mHead]; 60} 61 62template<typename ElementType, size_t kCapacity> 63ElementType& ArrayQueue<ElementType, kCapacity>::back() { 64 CHRE_ASSERT(mSize > 0); 65 return data()[mTail]; 66} 67 68template<typename ElementType, size_t kCapacity> 69const ElementType& ArrayQueue<ElementType, kCapacity>::back() const { 70 CHRE_ASSERT(mSize > 0); 71 return data()[mTail]; 72} 73 74template<typename ElementType, size_t kCapacity> 75ElementType& ArrayQueue<ElementType, kCapacity>::operator[](size_t index) { 76 CHRE_ASSERT(index < mSize); 77 return data()[relativeIndexToAbsolute(index)]; 78} 79 80template<typename ElementType, size_t kCapacity> 81const ElementType& ArrayQueue<ElementType, kCapacity>::operator[]( 82 size_t index) const { 83 CHRE_ASSERT(index < mSize); 84 return data()[relativeIndexToAbsolute(index)]; 85} 86 87template<typename ElementType, size_t kCapacity> 88bool 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 96template<typename ElementType, size_t kCapacity> 97bool 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 105template<typename ElementType, size_t kCapacity> 106void ArrayQueue<ElementType, kCapacity>::pop() { 107 if (mSize > 0) { 108 data()[mHead].~ElementType(); 109 pullHead(); 110 } 111} 112 113template<typename ElementType, size_t kCapacity> 114void 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. 124template<typename ElementType, size_t kCapacity> 125bool 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 158template<typename ElementType, size_t kCapacity> 159template<typename... Args> 160bool 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 168template<typename ElementType, size_t kCapacity> 169typename ArrayQueue<ElementType, kCapacity>::iterator 170ArrayQueue<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 175template<typename ElementType, size_t kCapacity> 176typename ArrayQueue<ElementType, kCapacity>::iterator 177 ArrayQueue<ElementType, kCapacity>::end() { 178 return iterator(data() + kCapacity, data(), mTail); 179} 180 181template<typename ElementType, size_t kCapacity> 182typename ArrayQueue<ElementType, kCapacity>::const_iterator 183ArrayQueue<ElementType, kCapacity>::begin() const { 184 return cbegin(); 185} 186 187template<typename ElementType, size_t kCapacity> 188typename ArrayQueue<ElementType, kCapacity>::const_iterator 189 ArrayQueue<ElementType, kCapacity>::end() const { 190 return cend(); 191} 192 193template<typename ElementType, size_t kCapacity> 194typename ArrayQueue<ElementType, kCapacity>::const_iterator 195ArrayQueue<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 200template<typename ElementType, size_t kCapacity> 201typename ArrayQueue<ElementType, kCapacity>::const_iterator 202 ArrayQueue<ElementType, kCapacity>::cend() const { 203 return const_iterator(data() + kCapacity, data(), mTail); 204} 205 206template<typename ElementType, size_t kCapacity> 207ElementType *ArrayQueue<ElementType, kCapacity>::data() { 208 return reinterpret_cast<ElementType *>(mData); 209} 210 211template<typename ElementType, size_t kCapacity> 212const ElementType *ArrayQueue<ElementType, kCapacity>::data() const { 213 return reinterpret_cast<const ElementType *>(mData); 214} 215 216template<typename ElementType, size_t kCapacity> 217size_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 226template<typename ElementType, size_t kCapacity> 227void ArrayQueue<ElementType, kCapacity>::pullHead() { 228 CHRE_ASSERT(mSize > 0); 229 if (++mHead == kCapacity) { 230 mHead = 0; 231 } 232 mSize--; 233} 234 235template<typename ElementType, size_t kCapacity> 236void 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 246template<typename ElementType, size_t kCapacity> 247bool 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