array_queue.h revision e64f180233e64c40b56993cfea3696c5b4b16395 
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_H_
18#define CHRE_UTIL_ARRAY_QUEUE_H_
19
20#include <type_traits>
21
22namespace chre {
23
24// TODO: this code is not done, just left for now as a reference
25
26/*
27 * TODO: need to implement thread-safe fifo queue that doesn't use dynamic
28 * memory... we can have something like this:
29 *  - array of data types
30 *  - head/tail index for data
31 *  - head for free list (only needs to be singly-linked)
32 *    - note that free list will use same array as linkage for active elements
33 *
34 * Don't worry about this for now, just use STL.
35 *
36 * This file is a WIP and probably doesn't work...
37 */
38
39
40// TODO: create a thread-safe wrapper for this, e.g. LockedArrayQueue. Starting
41// with single-threaded implementation for now
42
43template<typename ElementType, uint16_t kSize>
44class ArrayQueue {
45 public:
46  ArrayQueue() {
47    for (size_t i = 0; i < kSize - 1; i++) {
48      mNext[i] = i + 1;
49    }
50    mNext[kSize - 1] = kInvalidItem;
51    mHead = kInvalidItem;
52    mTail = kInvalidItem;
53    mFreeHead = 0;
54  }
55
56  // TODO: assert that T is trivially move/copy constructable?
57
58  static_assert(kSize < UINT16_MAX,
59                "ArrayList only supports up to UINT16_MAX-1 elements");
60  typedef std::conditional<(kSize >= UINT8_MAX), uint16_t, uint8_t>::type
61      IndexType;
62  constexpr IndexType kInvalidItem = (sizeof(IndexType) == sizeof(uint8_t)) ?
63                                     UINT8_MAX : UINT16_MAX;
64
65  bool pushBack(const ElementType &data) {
66    if (mFreeHead != kInvalidItem) {
67      mData[mFreeHead] = data;
68      mNext[mTail] = mFreeHead;
69      mTail = mFreeHead;
70      if (mHead == kInvalidItem) {
71        mHead = mTail;
72      }
73      mFreeHead = mNext[mFreeHead];
74      return true;
75    } else {
76      // todo: no space...
77      LOGE("Tried to push to full queue");
78      return false;
79    }
80  }
81
82  // todo: this queue needs to be single consumer, so we know that front()
83  // will not get freed while we're using it. maybe we add extra debug on here
84  // too like ASSERT(getThreadId() == mLastPopThreadId)...
85
86  bool empty() const {
87    return (mHead == kInvalidItem);
88  }
89
90  ElementType &front() {
91    ASSERT(mHead < kSize);
92    return mData[mHead];
93  }
94
95  const ElementType &front() const {
96    ASSERT(mHead < kSize);
97    return mData[mHead];
98  }
99
100  // general usage semantics
101  // while (!q.empty()) { T x = q.front(); x.doSomething(); q.popFront(); }
102
103  // Unlinks the front item from the list, and marks its storage as available
104  // for pushing new items to the queue.
105  void popFront() {
106    if (mHead != kInvalidItem) {
107      mData[mHead].~ElementType();
108      LinkType newHead = mNext[mHead];
109      mNext[mHead] = mFreeHead;
110      mFreeHead = mHead;
111      mHead = newHead;
112      if (mHead == kInvalidItem) {
113        mTail = kInvalidItem;
114      }
115    } else {
116      LOGE("Tried to pop empty list");
117    }
118  }
119
120 private:
121  ElementType mData[kSize];
122
123  // Contains the index for the "next" element in the queue, or kInvalidItem
124  // if there is no next item. Note that this array contains two
125  // non-overlapping lists, one that identifies which indices in mData are
126  // free (starting from mFreeHead), and another for the active part of the
127  // list (mHead and mTail).
128  IndexType mNext[kSize];
129  IndexType mHead;
130  IndexType mTail;
131  IndexType mFreeHead;
132
133  // TODO: lock
134};
135
136}  // namespace chre
137
138#endif  // CHRE_UTIL_ARRAY_QUEUE_H_
139