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