1e64f180233e64c40b56993cfea3696c5b4b16395Brian Duddie/* 2e64f180233e64c40b56993cfea3696c5b4b16395Brian Duddie * Copyright (C) 2016 The Android Open Source Project 3e64f180233e64c40b56993cfea3696c5b4b16395Brian Duddie * 4e64f180233e64c40b56993cfea3696c5b4b16395Brian Duddie * Licensed under the Apache License, Version 2.0 (the "License"); 5e64f180233e64c40b56993cfea3696c5b4b16395Brian Duddie * you may not use this file except in compliance with the License. 6e64f180233e64c40b56993cfea3696c5b4b16395Brian Duddie * You may obtain a copy of the License at 7e64f180233e64c40b56993cfea3696c5b4b16395Brian Duddie * 8e64f180233e64c40b56993cfea3696c5b4b16395Brian Duddie * http://www.apache.org/licenses/LICENSE-2.0 9e64f180233e64c40b56993cfea3696c5b4b16395Brian Duddie * 10e64f180233e64c40b56993cfea3696c5b4b16395Brian Duddie * Unless required by applicable law or agreed to in writing, software 11e64f180233e64c40b56993cfea3696c5b4b16395Brian Duddie * distributed under the License is distributed on an "AS IS" BASIS, 12e64f180233e64c40b56993cfea3696c5b4b16395Brian Duddie * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13e64f180233e64c40b56993cfea3696c5b4b16395Brian Duddie * See the License for the specific language governing permissions and 14e64f180233e64c40b56993cfea3696c5b4b16395Brian Duddie * limitations under the License. 15e64f180233e64c40b56993cfea3696c5b4b16395Brian Duddie */ 16e64f180233e64c40b56993cfea3696c5b4b16395Brian Duddie 17e64f180233e64c40b56993cfea3696c5b4b16395Brian Duddie#ifndef CHRE_UTIL_ARRAY_QUEUE_H_ 18e64f180233e64c40b56993cfea3696c5b4b16395Brian Duddie#define CHRE_UTIL_ARRAY_QUEUE_H_ 19e64f180233e64c40b56993cfea3696c5b4b16395Brian Duddie 20e64f180233e64c40b56993cfea3696c5b4b16395Brian Duddie#include <type_traits> 21e64f180233e64c40b56993cfea3696c5b4b16395Brian Duddie 2289aa0dd2e1f0a7cde9c6ec808f0cdcce33f35a62Andrew Rossignol#include "chre/util/non_copyable.h" 2389aa0dd2e1f0a7cde9c6ec808f0cdcce33f35a62Andrew Rossignol 24e64f180233e64c40b56993cfea3696c5b4b16395Brian Duddienamespace chre { 25e64f180233e64c40b56993cfea3696c5b4b16395Brian Duddie 2689aa0dd2e1f0a7cde9c6ec808f0cdcce33f35a62Andrew Rossignol/** 279b598a5b372a47b8e30113cd5650448ce4ae3418Meng-hsuan Chung * A fixed-size FIFO queue for storing elements. When the FIFO is full, new 289b598a5b372a47b8e30113cd5650448ce4ae3418Meng-hsuan Chung * element will not be able to be pushed in. 2989aa0dd2e1f0a7cde9c6ec808f0cdcce33f35a62Andrew Rossignol */ 300a28dc2f6cbe1c064d95f6ea88bce83401fd8607Meng-hsuan Chungtemplate<typename ElementType, size_t kCapacity> 3189aa0dd2e1f0a7cde9c6ec808f0cdcce33f35a62Andrew Rossignolclass ArrayQueue : public NonCopyable { 32e64f180233e64c40b56993cfea3696c5b4b16395Brian Duddie public: 330a28dc2f6cbe1c064d95f6ea88bce83401fd8607Meng-hsuan Chung /** 340a28dc2f6cbe1c064d95f6ea88bce83401fd8607Meng-hsuan Chung * Calls the destructor of all the elements in the array queue. 350a28dc2f6cbe1c064d95f6ea88bce83401fd8607Meng-hsuan Chung */ 360a28dc2f6cbe1c064d95f6ea88bce83401fd8607Meng-hsuan Chung ~ArrayQueue(); 370a28dc2f6cbe1c064d95f6ea88bce83401fd8607Meng-hsuan Chung 380a28dc2f6cbe1c064d95f6ea88bce83401fd8607Meng-hsuan Chung /** 390a28dc2f6cbe1c064d95f6ea88bce83401fd8607Meng-hsuan Chung * Determines whether the array queue is empty or not. 400a28dc2f6cbe1c064d95f6ea88bce83401fd8607Meng-hsuan Chung * 410a28dc2f6cbe1c064d95f6ea88bce83401fd8607Meng-hsuan Chung * @return true if the array queue is empty. 420a28dc2f6cbe1c064d95f6ea88bce83401fd8607Meng-hsuan Chung */ 430a28dc2f6cbe1c064d95f6ea88bce83401fd8607Meng-hsuan Chung bool empty() const; 440a28dc2f6cbe1c064d95f6ea88bce83401fd8607Meng-hsuan Chung 450a28dc2f6cbe1c064d95f6ea88bce83401fd8607Meng-hsuan Chung /** 465312518f60833ba29ced8109d037f40bf754214fAndrew Rossignol * @return true if the array queue is full. 475312518f60833ba29ced8109d037f40bf754214fAndrew Rossignol */ 485312518f60833ba29ced8109d037f40bf754214fAndrew Rossignol bool full() const; 495312518f60833ba29ced8109d037f40bf754214fAndrew Rossignol 505312518f60833ba29ced8109d037f40bf754214fAndrew Rossignol /** 510a28dc2f6cbe1c064d95f6ea88bce83401fd8607Meng-hsuan Chung * Obtains the number of elements currently stored in the array queue. 520a28dc2f6cbe1c064d95f6ea88bce83401fd8607Meng-hsuan Chung * 530a28dc2f6cbe1c064d95f6ea88bce83401fd8607Meng-hsuan Chung * @return The number of elements currently stored in the array queue. 540a28dc2f6cbe1c064d95f6ea88bce83401fd8607Meng-hsuan Chung */ 550a28dc2f6cbe1c064d95f6ea88bce83401fd8607Meng-hsuan Chung size_t size() const; 560a28dc2f6cbe1c064d95f6ea88bce83401fd8607Meng-hsuan Chung 570a28dc2f6cbe1c064d95f6ea88bce83401fd8607Meng-hsuan Chung /** 580a28dc2f6cbe1c064d95f6ea88bce83401fd8607Meng-hsuan Chung * Obtains the front element of the array queue. It is illegal to access the 590a28dc2f6cbe1c064d95f6ea88bce83401fd8607Meng-hsuan Chung * front element when the array queue is empty. The user of the API must check 600a28dc2f6cbe1c064d95f6ea88bce83401fd8607Meng-hsuan Chung * the size() or empty() function prior to accessing the front element to 610a28dc2f6cbe1c064d95f6ea88bce83401fd8607Meng-hsuan Chung * ensure that they will not read out of bounds. 620a28dc2f6cbe1c064d95f6ea88bce83401fd8607Meng-hsuan Chung * 630a28dc2f6cbe1c064d95f6ea88bce83401fd8607Meng-hsuan Chung * @return The front element. 640a28dc2f6cbe1c064d95f6ea88bce83401fd8607Meng-hsuan Chung */ 650a28dc2f6cbe1c064d95f6ea88bce83401fd8607Meng-hsuan Chung ElementType& front(); 660a28dc2f6cbe1c064d95f6ea88bce83401fd8607Meng-hsuan Chung 670a28dc2f6cbe1c064d95f6ea88bce83401fd8607Meng-hsuan Chung /** 680a28dc2f6cbe1c064d95f6ea88bce83401fd8607Meng-hsuan Chung * Obtains the front element of the array queue. It is illegal to access the 690a28dc2f6cbe1c064d95f6ea88bce83401fd8607Meng-hsuan Chung * front element when the array queue is empty. The user of the API must check 700a28dc2f6cbe1c064d95f6ea88bce83401fd8607Meng-hsuan Chung * the size() or empty() function prior to accessing the front element to 710a28dc2f6cbe1c064d95f6ea88bce83401fd8607Meng-hsuan Chung * ensure that they will not read out of bounds. 720a28dc2f6cbe1c064d95f6ea88bce83401fd8607Meng-hsuan Chung * 730a28dc2f6cbe1c064d95f6ea88bce83401fd8607Meng-hsuan Chung * @return The front element. 740a28dc2f6cbe1c064d95f6ea88bce83401fd8607Meng-hsuan Chung */ 750a28dc2f6cbe1c064d95f6ea88bce83401fd8607Meng-hsuan Chung const ElementType& front() const; 760a28dc2f6cbe1c064d95f6ea88bce83401fd8607Meng-hsuan Chung 770a28dc2f6cbe1c064d95f6ea88bce83401fd8607Meng-hsuan Chung /** 780a28dc2f6cbe1c064d95f6ea88bce83401fd8607Meng-hsuan Chung * Obtains an element of the array queue given an index. It is illegal to 790a28dc2f6cbe1c064d95f6ea88bce83401fd8607Meng-hsuan Chung * index this array queue out of bounds and the user of the API must check the 800a28dc2f6cbe1c064d95f6ea88bce83401fd8607Meng-hsuan Chung * size() function prior to indexing this array queue to ensure that they will 810a28dc2f6cbe1c064d95f6ea88bce83401fd8607Meng-hsuan Chung * not read out of bounds. 820a28dc2f6cbe1c064d95f6ea88bce83401fd8607Meng-hsuan Chung * 830a28dc2f6cbe1c064d95f6ea88bce83401fd8607Meng-hsuan Chung * @param index Requested index in range [0,size()-1] 840a28dc2f6cbe1c064d95f6ea88bce83401fd8607Meng-hsuan Chung * @return The element. 850a28dc2f6cbe1c064d95f6ea88bce83401fd8607Meng-hsuan Chung */ 860a28dc2f6cbe1c064d95f6ea88bce83401fd8607Meng-hsuan Chung ElementType& operator[](size_t index); 870a28dc2f6cbe1c064d95f6ea88bce83401fd8607Meng-hsuan Chung 880a28dc2f6cbe1c064d95f6ea88bce83401fd8607Meng-hsuan Chung /** 890a28dc2f6cbe1c064d95f6ea88bce83401fd8607Meng-hsuan Chung * Obtains an element of the array queue given an index. It is illegal to 900a28dc2f6cbe1c064d95f6ea88bce83401fd8607Meng-hsuan Chung * index this array queue out of bounds and the user of the API must check the 910a28dc2f6cbe1c064d95f6ea88bce83401fd8607Meng-hsuan Chung * size() function prior to indexing this array queue to ensure that they will 920a28dc2f6cbe1c064d95f6ea88bce83401fd8607Meng-hsuan Chung * not read out of bounds. 930a28dc2f6cbe1c064d95f6ea88bce83401fd8607Meng-hsuan Chung * 940a28dc2f6cbe1c064d95f6ea88bce83401fd8607Meng-hsuan Chung * @param index Requested index in range [0,size()-1] 950a28dc2f6cbe1c064d95f6ea88bce83401fd8607Meng-hsuan Chung * @return The element. 960a28dc2f6cbe1c064d95f6ea88bce83401fd8607Meng-hsuan Chung */ 970a28dc2f6cbe1c064d95f6ea88bce83401fd8607Meng-hsuan Chung const ElementType& operator[](size_t index) const; 980a28dc2f6cbe1c064d95f6ea88bce83401fd8607Meng-hsuan Chung 990a28dc2f6cbe1c064d95f6ea88bce83401fd8607Meng-hsuan Chung /** 1008be5eabe6a4fc60c56a3b32794bb6677e26f6eabBrian Duddie * Pushes an element onto the back of the array queue via copy or move 1018be5eabe6a4fc60c56a3b32794bb6677e26f6eabBrian Duddie * construction. It returns false if the array queue is full already and there 1028be5eabe6a4fc60c56a3b32794bb6677e26f6eabBrian Duddie * is no room for the elements. All iterators and references are unaffected. 1030a28dc2f6cbe1c064d95f6ea88bce83401fd8607Meng-hsuan Chung * 1040a28dc2f6cbe1c064d95f6ea88bce83401fd8607Meng-hsuan Chung * @param element The element to push onto the array queue. 1050a28dc2f6cbe1c064d95f6ea88bce83401fd8607Meng-hsuan Chung * @return true if the element is pushed successfully. 1060a28dc2f6cbe1c064d95f6ea88bce83401fd8607Meng-hsuan Chung */ 1070a28dc2f6cbe1c064d95f6ea88bce83401fd8607Meng-hsuan Chung bool push(const ElementType& element); 1088be5eabe6a4fc60c56a3b32794bb6677e26f6eabBrian Duddie bool push(ElementType&& element); 1090a28dc2f6cbe1c064d95f6ea88bce83401fd8607Meng-hsuan Chung 1100a28dc2f6cbe1c064d95f6ea88bce83401fd8607Meng-hsuan Chung /** 1110a28dc2f6cbe1c064d95f6ea88bce83401fd8607Meng-hsuan Chung * Removes the front element from the array queue if the array queue is not 1129b598a5b372a47b8e30113cd5650448ce4ae3418Meng-hsuan Chung * empty. Only iterators and references to the front of the queue are 1139b598a5b372a47b8e30113cd5650448ce4ae3418Meng-hsuan Chung * invalidated. 1140a28dc2f6cbe1c064d95f6ea88bce83401fd8607Meng-hsuan Chung */ 1150a28dc2f6cbe1c064d95f6ea88bce83401fd8607Meng-hsuan Chung void pop(); 1160a28dc2f6cbe1c064d95f6ea88bce83401fd8607Meng-hsuan Chung 1170a28dc2f6cbe1c064d95f6ea88bce83401fd8607Meng-hsuan Chung /** 1189b598a5b372a47b8e30113cd5650448ce4ae3418Meng-hsuan Chung * Removes an element from the array queue given an index. It returns false if 1199b598a5b372a47b8e30113cd5650448ce4ae3418Meng-hsuan Chung * the array queue contains fewer items than the index. All iterators and 1209b598a5b372a47b8e30113cd5650448ce4ae3418Meng-hsuan Chung * references to elements before the removed one are unaffected. Iterators 1219b598a5b372a47b8e30113cd5650448ce4ae3418Meng-hsuan Chung * and references to the removed element or any elements after it are 1229b598a5b372a47b8e30113cd5650448ce4ae3418Meng-hsuan Chung * invalidated. 1230a28dc2f6cbe1c064d95f6ea88bce83401fd8607Meng-hsuan Chung * 1240a28dc2f6cbe1c064d95f6ea88bce83401fd8607Meng-hsuan Chung * @param index Requested index in range [0,size()-1] 1250a28dc2f6cbe1c064d95f6ea88bce83401fd8607Meng-hsuan Chung * @return true if the indexed element has been removed successfully. 1260a28dc2f6cbe1c064d95f6ea88bce83401fd8607Meng-hsuan Chung */ 1270a28dc2f6cbe1c064d95f6ea88bce83401fd8607Meng-hsuan Chung bool remove(size_t index); 1280a28dc2f6cbe1c064d95f6ea88bce83401fd8607Meng-hsuan Chung 1290a28dc2f6cbe1c064d95f6ea88bce83401fd8607Meng-hsuan Chung /** 1309b598a5b372a47b8e30113cd5650448ce4ae3418Meng-hsuan Chung * Constructs an element onto the back of the array queue. All iterators and 1319b598a5b372a47b8e30113cd5650448ce4ae3418Meng-hsuan Chung * references are unaffected. 1320a28dc2f6cbe1c064d95f6ea88bce83401fd8607Meng-hsuan Chung * 1330a28dc2f6cbe1c064d95f6ea88bce83401fd8607Meng-hsuan Chung * @param The arguments to the constructor 1340a28dc2f6cbe1c064d95f6ea88bce83401fd8607Meng-hsuan Chung * @return true if the element is constructed successfully. 1350a28dc2f6cbe1c064d95f6ea88bce83401fd8607Meng-hsuan Chung */ 1360a28dc2f6cbe1c064d95f6ea88bce83401fd8607Meng-hsuan Chung template<typename... Args> 1370a28dc2f6cbe1c064d95f6ea88bce83401fd8607Meng-hsuan Chung bool emplace(Args&&... args); 138e64f180233e64c40b56993cfea3696c5b4b16395Brian Duddie 1399b598a5b372a47b8e30113cd5650448ce4ae3418Meng-hsuan Chung /** 1409b598a5b372a47b8e30113cd5650448ce4ae3418Meng-hsuan Chung * A template class that implements a forward iterator for the array queue. 1419b598a5b372a47b8e30113cd5650448ce4ae3418Meng-hsuan Chung */ 1429b598a5b372a47b8e30113cd5650448ce4ae3418Meng-hsuan Chung template<typename ValueType> 1439b598a5b372a47b8e30113cd5650448ce4ae3418Meng-hsuan Chung class ArrayQueueIterator { 1449b598a5b372a47b8e30113cd5650448ce4ae3418Meng-hsuan Chung public: 1459b598a5b372a47b8e30113cd5650448ce4ae3418Meng-hsuan Chung ArrayQueueIterator( 1469b598a5b372a47b8e30113cd5650448ce4ae3418Meng-hsuan Chung ValueType *pointer, ValueType *base, size_t tail) 1479b598a5b372a47b8e30113cd5650448ce4ae3418Meng-hsuan Chung : mPointer(pointer), mBase(base), mTail(tail) {} 1489b598a5b372a47b8e30113cd5650448ce4ae3418Meng-hsuan Chung 1499b598a5b372a47b8e30113cd5650448ce4ae3418Meng-hsuan Chung bool operator==(const ArrayQueueIterator& right) { 1509b598a5b372a47b8e30113cd5650448ce4ae3418Meng-hsuan Chung return (mPointer == right.mPointer); 1519b598a5b372a47b8e30113cd5650448ce4ae3418Meng-hsuan Chung } 1529b598a5b372a47b8e30113cd5650448ce4ae3418Meng-hsuan Chung 1539b598a5b372a47b8e30113cd5650448ce4ae3418Meng-hsuan Chung bool operator!=(const ArrayQueueIterator& right) { 1549b598a5b372a47b8e30113cd5650448ce4ae3418Meng-hsuan Chung return (mPointer != right.mPointer); 1559b598a5b372a47b8e30113cd5650448ce4ae3418Meng-hsuan Chung } 1569b598a5b372a47b8e30113cd5650448ce4ae3418Meng-hsuan Chung 1579b598a5b372a47b8e30113cd5650448ce4ae3418Meng-hsuan Chung ValueType& operator*() { 1589b598a5b372a47b8e30113cd5650448ce4ae3418Meng-hsuan Chung return *mPointer; 1599b598a5b372a47b8e30113cd5650448ce4ae3418Meng-hsuan Chung } 1609b598a5b372a47b8e30113cd5650448ce4ae3418Meng-hsuan Chung 1619b598a5b372a47b8e30113cd5650448ce4ae3418Meng-hsuan Chung ValueType *operator->() { 1629b598a5b372a47b8e30113cd5650448ce4ae3418Meng-hsuan Chung return mPointer; 1639b598a5b372a47b8e30113cd5650448ce4ae3418Meng-hsuan Chung } 1649b598a5b372a47b8e30113cd5650448ce4ae3418Meng-hsuan Chung 1659b598a5b372a47b8e30113cd5650448ce4ae3418Meng-hsuan Chung ArrayQueueIterator& operator++() { 1669b598a5b372a47b8e30113cd5650448ce4ae3418Meng-hsuan Chung if (mPointer == (mBase + mTail)) { 1679b598a5b372a47b8e30113cd5650448ce4ae3418Meng-hsuan Chung // Jump to end() if at tail 1689b598a5b372a47b8e30113cd5650448ce4ae3418Meng-hsuan Chung mPointer = mBase + kCapacity; 1699b598a5b372a47b8e30113cd5650448ce4ae3418Meng-hsuan Chung } else if (mPointer == (mBase + kCapacity - 1)) { 1709b598a5b372a47b8e30113cd5650448ce4ae3418Meng-hsuan Chung // Wrap around in the memory 1719b598a5b372a47b8e30113cd5650448ce4ae3418Meng-hsuan Chung mPointer = mBase; 1729b598a5b372a47b8e30113cd5650448ce4ae3418Meng-hsuan Chung } else { 1739b598a5b372a47b8e30113cd5650448ce4ae3418Meng-hsuan Chung mPointer++; 1749b598a5b372a47b8e30113cd5650448ce4ae3418Meng-hsuan Chung } 1759b598a5b372a47b8e30113cd5650448ce4ae3418Meng-hsuan Chung return *this; 1769b598a5b372a47b8e30113cd5650448ce4ae3418Meng-hsuan Chung } 1779b598a5b372a47b8e30113cd5650448ce4ae3418Meng-hsuan Chung 1789b598a5b372a47b8e30113cd5650448ce4ae3418Meng-hsuan Chung ArrayQueueIterator operator++(int) { 1799b598a5b372a47b8e30113cd5650448ce4ae3418Meng-hsuan Chung ArrayQueueIterator it(*this); 1809b598a5b372a47b8e30113cd5650448ce4ae3418Meng-hsuan Chung operator++(); 1819b598a5b372a47b8e30113cd5650448ce4ae3418Meng-hsuan Chung return it; 1829b598a5b372a47b8e30113cd5650448ce4ae3418Meng-hsuan Chung } 1839b598a5b372a47b8e30113cd5650448ce4ae3418Meng-hsuan Chung 1849b598a5b372a47b8e30113cd5650448ce4ae3418Meng-hsuan Chung private: 1859b598a5b372a47b8e30113cd5650448ce4ae3418Meng-hsuan Chung //! Pointer of the iterator. 1869b598a5b372a47b8e30113cd5650448ce4ae3418Meng-hsuan Chung ValueType *mPointer; 1879b598a5b372a47b8e30113cd5650448ce4ae3418Meng-hsuan Chung 1889b598a5b372a47b8e30113cd5650448ce4ae3418Meng-hsuan Chung //! The memory base address of this container. 1899b598a5b372a47b8e30113cd5650448ce4ae3418Meng-hsuan Chung ValueType *mBase; 1909b598a5b372a47b8e30113cd5650448ce4ae3418Meng-hsuan Chung 1919b598a5b372a47b8e30113cd5650448ce4ae3418Meng-hsuan Chung //! The tail offset relative to the memory base address. 1929b598a5b372a47b8e30113cd5650448ce4ae3418Meng-hsuan Chung size_t mTail; 1939b598a5b372a47b8e30113cd5650448ce4ae3418Meng-hsuan Chung }; 1949b598a5b372a47b8e30113cd5650448ce4ae3418Meng-hsuan Chung 1959b598a5b372a47b8e30113cd5650448ce4ae3418Meng-hsuan Chung /** 1969b598a5b372a47b8e30113cd5650448ce4ae3418Meng-hsuan Chung * Forward iterator that points to some element in the container. 1979b598a5b372a47b8e30113cd5650448ce4ae3418Meng-hsuan Chung */ 1989b598a5b372a47b8e30113cd5650448ce4ae3418Meng-hsuan Chung typedef ArrayQueueIterator<ElementType> iterator; 1999b598a5b372a47b8e30113cd5650448ce4ae3418Meng-hsuan Chung typedef ArrayQueueIterator<const ElementType> const_iterator; 2009b598a5b372a47b8e30113cd5650448ce4ae3418Meng-hsuan Chung 2019b598a5b372a47b8e30113cd5650448ce4ae3418Meng-hsuan Chung /** 2029b598a5b372a47b8e30113cd5650448ce4ae3418Meng-hsuan Chung * @return A forward iterator to the beginning. 2039b598a5b372a47b8e30113cd5650448ce4ae3418Meng-hsuan Chung */ 2049b598a5b372a47b8e30113cd5650448ce4ae3418Meng-hsuan Chung typename ArrayQueue<ElementType, kCapacity>::iterator begin(); 20548080e341c2a12db12deb086adce1d487a759141Meng-hsuan Chung typename ArrayQueue<ElementType, kCapacity>::const_iterator begin() const; 2069b598a5b372a47b8e30113cd5650448ce4ae3418Meng-hsuan Chung typename ArrayQueue<ElementType, kCapacity>::const_iterator cbegin() const; 2079b598a5b372a47b8e30113cd5650448ce4ae3418Meng-hsuan Chung 2089b598a5b372a47b8e30113cd5650448ce4ae3418Meng-hsuan Chung /** 2099b598a5b372a47b8e30113cd5650448ce4ae3418Meng-hsuan Chung * @return A forward iterator to the end. 2109b598a5b372a47b8e30113cd5650448ce4ae3418Meng-hsuan Chung */ 2119b598a5b372a47b8e30113cd5650448ce4ae3418Meng-hsuan Chung typename ArrayQueue<ElementType, kCapacity>::iterator end(); 21248080e341c2a12db12deb086adce1d487a759141Meng-hsuan Chung typename ArrayQueue<ElementType, kCapacity>::const_iterator end() const; 2139b598a5b372a47b8e30113cd5650448ce4ae3418Meng-hsuan Chung typename ArrayQueue<ElementType, kCapacity>::const_iterator cend() const; 2149b598a5b372a47b8e30113cd5650448ce4ae3418Meng-hsuan Chung 215e64f180233e64c40b56993cfea3696c5b4b16395Brian Duddie private: 2160a28dc2f6cbe1c064d95f6ea88bce83401fd8607Meng-hsuan Chung /** 2170a28dc2f6cbe1c064d95f6ea88bce83401fd8607Meng-hsuan Chung * Storage for array queue elements. To avoid static initialization of 2180a28dc2f6cbe1c064d95f6ea88bce83401fd8607Meng-hsuan Chung * members, std::aligned_storage is used. 2190a28dc2f6cbe1c064d95f6ea88bce83401fd8607Meng-hsuan Chung */ 2200a28dc2f6cbe1c064d95f6ea88bce83401fd8607Meng-hsuan Chung typename std::aligned_storage<sizeof(ElementType), 2210a28dc2f6cbe1c064d95f6ea88bce83401fd8607Meng-hsuan Chung alignof(ElementType)>::type mData[kCapacity]; 2220a28dc2f6cbe1c064d95f6ea88bce83401fd8607Meng-hsuan Chung 2230a28dc2f6cbe1c064d95f6ea88bce83401fd8607Meng-hsuan Chung /* 2240a28dc2f6cbe1c064d95f6ea88bce83401fd8607Meng-hsuan Chung * Initialize mTail to be (kCapacity-1). When an element is pushed in, 2250a28dc2f6cbe1c064d95f6ea88bce83401fd8607Meng-hsuan Chung * mHead and mTail will align. Also, this is consistent with 2260a28dc2f6cbe1c064d95f6ea88bce83401fd8607Meng-hsuan Chung * mSize = (mTail - mHead)%kCapacity + 1 for mSize > 0. 2270a28dc2f6cbe1c064d95f6ea88bce83401fd8607Meng-hsuan Chung */ 2280a28dc2f6cbe1c064d95f6ea88bce83401fd8607Meng-hsuan Chung //! Index of the front element 2290a28dc2f6cbe1c064d95f6ea88bce83401fd8607Meng-hsuan Chung size_t mHead = 0; 2300a28dc2f6cbe1c064d95f6ea88bce83401fd8607Meng-hsuan Chung 2310a28dc2f6cbe1c064d95f6ea88bce83401fd8607Meng-hsuan Chung //! Index of the back element 2320a28dc2f6cbe1c064d95f6ea88bce83401fd8607Meng-hsuan Chung size_t mTail = kCapacity - 1; 2330a28dc2f6cbe1c064d95f6ea88bce83401fd8607Meng-hsuan Chung 2340a28dc2f6cbe1c064d95f6ea88bce83401fd8607Meng-hsuan Chung //! Number of elements in the array queue 2350a28dc2f6cbe1c064d95f6ea88bce83401fd8607Meng-hsuan Chung size_t mSize = 0; 2360a28dc2f6cbe1c064d95f6ea88bce83401fd8607Meng-hsuan Chung 2370a28dc2f6cbe1c064d95f6ea88bce83401fd8607Meng-hsuan Chung /** 2380a28dc2f6cbe1c064d95f6ea88bce83401fd8607Meng-hsuan Chung * Obtains a pointer to the underlying storage for the vector. 2390a28dc2f6cbe1c064d95f6ea88bce83401fd8607Meng-hsuan Chung * 2400a28dc2f6cbe1c064d95f6ea88bce83401fd8607Meng-hsuan Chung * @return A pointer to the storage used for elements in this vector. 2410a28dc2f6cbe1c064d95f6ea88bce83401fd8607Meng-hsuan Chung */ 2420a28dc2f6cbe1c064d95f6ea88bce83401fd8607Meng-hsuan Chung ElementType *data(); 2430a28dc2f6cbe1c064d95f6ea88bce83401fd8607Meng-hsuan Chung 2440a28dc2f6cbe1c064d95f6ea88bce83401fd8607Meng-hsuan Chung /** 2450a28dc2f6cbe1c064d95f6ea88bce83401fd8607Meng-hsuan Chung * Obtains a pointer to the underlying storage for the vector. 2460a28dc2f6cbe1c064d95f6ea88bce83401fd8607Meng-hsuan Chung * 2470a28dc2f6cbe1c064d95f6ea88bce83401fd8607Meng-hsuan Chung * @return A pointer to the storage used for elements in this vector. 2480a28dc2f6cbe1c064d95f6ea88bce83401fd8607Meng-hsuan Chung */ 2490a28dc2f6cbe1c064d95f6ea88bce83401fd8607Meng-hsuan Chung const ElementType *data() const; 2500a28dc2f6cbe1c064d95f6ea88bce83401fd8607Meng-hsuan Chung 2510a28dc2f6cbe1c064d95f6ea88bce83401fd8607Meng-hsuan Chung /** 2520a28dc2f6cbe1c064d95f6ea88bce83401fd8607Meng-hsuan Chung * Converts relative index with respect to mHead to absolute index in the 2530a28dc2f6cbe1c064d95f6ea88bce83401fd8607Meng-hsuan Chung * storage array. 2540a28dc2f6cbe1c064d95f6ea88bce83401fd8607Meng-hsuan Chung * 2550a28dc2f6cbe1c064d95f6ea88bce83401fd8607Meng-hsuan Chung * @param index Relative index in range [0,size()-1] 2560a28dc2f6cbe1c064d95f6ea88bce83401fd8607Meng-hsuan Chung * @return The index of the storage array in range [0,kCapacity-1] 2570a28dc2f6cbe1c064d95f6ea88bce83401fd8607Meng-hsuan Chung */ 2580a28dc2f6cbe1c064d95f6ea88bce83401fd8607Meng-hsuan Chung size_t relativeIndexToAbsolute(size_t index) const; 2590a28dc2f6cbe1c064d95f6ea88bce83401fd8607Meng-hsuan Chung 2600a28dc2f6cbe1c064d95f6ea88bce83401fd8607Meng-hsuan Chung /* 2610a28dc2f6cbe1c064d95f6ea88bce83401fd8607Meng-hsuan Chung * Pulls mHead to the next element in the array queue and decrements mSize 2620a28dc2f6cbe1c064d95f6ea88bce83401fd8607Meng-hsuan Chung * accordingly. It is illegal to call this function on an empty array queue. 2630a28dc2f6cbe1c064d95f6ea88bce83401fd8607Meng-hsuan Chung */ 2640a28dc2f6cbe1c064d95f6ea88bce83401fd8607Meng-hsuan Chung void pullHead(); 2650a28dc2f6cbe1c064d95f6ea88bce83401fd8607Meng-hsuan Chung 2660a28dc2f6cbe1c064d95f6ea88bce83401fd8607Meng-hsuan Chung /* 2670a28dc2f6cbe1c064d95f6ea88bce83401fd8607Meng-hsuan Chung * Pushes mTail to the next available storage space and increments mSize 2680a28dc2f6cbe1c064d95f6ea88bce83401fd8607Meng-hsuan Chung * accordingly. 2690a28dc2f6cbe1c064d95f6ea88bce83401fd8607Meng-hsuan Chung * 2700a28dc2f6cbe1c064d95f6ea88bce83401fd8607Meng-hsuan Chung * @return true if the array queue is not full. 2710a28dc2f6cbe1c064d95f6ea88bce83401fd8607Meng-hsuan Chung */ 2720a28dc2f6cbe1c064d95f6ea88bce83401fd8607Meng-hsuan Chung bool pushTail(); 273e64f180233e64c40b56993cfea3696c5b4b16395Brian Duddie}; 274e64f180233e64c40b56993cfea3696c5b4b16395Brian Duddie 275e64f180233e64c40b56993cfea3696c5b4b16395Brian Duddie} // namespace chre 276e64f180233e64c40b56993cfea3696c5b4b16395Brian Duddie 2770a28dc2f6cbe1c064d95f6ea88bce83401fd8607Meng-hsuan Chung#include "chre/util/array_queue_impl.h" 2780a28dc2f6cbe1c064d95f6ea88bce83401fd8607Meng-hsuan Chung 279e64f180233e64c40b56993cfea3696c5b4b16395Brian Duddie#endif // CHRE_UTIL_ARRAY_QUEUE_H_ 280