1 /* 2 * Copyright 2018 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 18 #ifndef RHYTHMGAME_LOCKFREEQUEUE_H 19 #define RHYTHMGAME_LOCKFREEQUEUE_H 20 21 #include <cstdint> 22 #include <atomic> 23 24 /** 25 * A lock-free queue for single consumer, single producer. Not thread-safe when using multiple 26 * consumers or producers. 27 * 28 * Example code: 29 * 30 * LockFreeQueue<int, 1024> myQueue; 31 * int value = 123; 32 * myQueue.push(value); 33 * myQueue.pop(value); 34 * 35 * @tparam T - The item type 36 * @tparam CAPACITY - Maximum number of items which can be held in the queue. Must be a power of 2. 37 * Must be less than the maximum value permissible in INDEX_TYPE 38 * @tparam INDEX_TYPE - The internal index type, defaults to uint32_t. Changing this will affect 39 * the maximum capacity. Included for ease of unit testing because testing queue lengths of 40 * UINT32_MAX can be time consuming and is not always possible. 41 */ 42 43 template <typename T, uint32_t CAPACITY, typename INDEX_TYPE = uint32_t> 44 class LockFreeQueue { 45 public: 46 47 /** 48 * Implementation details: 49 * 50 * We have 2 counters: readCounter and writeCounter. Each will increment until it reaches 51 * INDEX_TYPE_MAX, then wrap to zero. Unsigned integer overflow is defined behaviour in C++. 52 * 53 * Each time we need to access our data array we call mask() which gives us the index into the 54 * array. This approach avoids having a "dead item" in the buffer to distinguish between full 55 * and empty states. It also allows us to have a size() method which is easily calculated. 56 * 57 * IMPORTANT: This implementation is only thread-safe with a single reader thread and a single 58 * writer thread. Have more than one of either will result in Bad Things™. 59 */ 60 isPowerOfTwo(uint32_t n)61 static constexpr bool isPowerOfTwo(uint32_t n) { return (n & (n - 1)) == 0; } 62 static_assert(isPowerOfTwo(CAPACITY), "Capacity must be a power of 2"); 63 static_assert(std::is_unsigned<INDEX_TYPE>::value, "Index type must be unsigned"); 64 65 /** 66 * Pop a value off the head of the queue 67 * 68 * @param val - element will be stored in this variable 69 * @return true if value was popped successfully, false if the queue is empty 70 */ pop(T & val)71 bool pop(T &val) { 72 if (isEmpty()){ 73 return false; 74 } else { 75 val = buffer[mask(readCounter)]; 76 ++readCounter; 77 return true; 78 } 79 } 80 81 /** 82 * Add an item to the back of the queue 83 * 84 * @param item - The item to add 85 * @return true if item was added, false if the queue was full 86 */ push(const T & item)87 bool push(const T& item) { 88 if (isFull()){ 89 return false; 90 } else { 91 buffer[mask(writeCounter)] = item; 92 ++writeCounter; 93 return true; 94 } 95 } 96 97 /** 98 * Get the item at the front of the queue but do not remove it 99 * 100 * @param item - item will be stored in this variable 101 * @return true if item was stored, false if the queue was empty 102 */ peek(T & item)103 bool peek(T &item) const { 104 if (isEmpty()){ 105 return false; 106 } else { 107 item = buffer[mask(readCounter)]; 108 return true; 109 } 110 } 111 112 /** 113 * Get the number of items in the queue 114 * 115 * @return number of items in the queue 116 */ size()117 INDEX_TYPE size() const { 118 119 /** 120 * This is worth some explanation: 121 * 122 * Whilst writeCounter is greater than readCounter the result of (write - read) will always 123 * be positive. Simple. 124 * 125 * But when writeCounter is equal to INDEX_TYPE_MAX (e.g. UINT32_MAX) the next push will 126 * wrap it around to zero, the start of the buffer, making writeCounter less than 127 * readCounter so the result of (write - read) will be negative. 128 * 129 * But because we're returning an unsigned type return value will be as follows: 130 * 131 * returnValue = INDEX_TYPE_MAX - (write - read) 132 * 133 * e.g. if write is 0, read is 150 and the INDEX_TYPE is uint8_t where the max value is 134 * 255 the return value will be (255 - (0 - 150)) = 105. 135 * 136 */ 137 return writeCounter - readCounter; 138 }; 139 140 private: 141 isEmpty()142 bool isEmpty() const { return readCounter == writeCounter; } 143 isFull()144 bool isFull() const { return size() == CAPACITY; } 145 mask(INDEX_TYPE n)146 INDEX_TYPE mask(INDEX_TYPE n) const { return static_cast<INDEX_TYPE>(n & (CAPACITY - 1)); } 147 148 T buffer[CAPACITY]; 149 std::atomic<INDEX_TYPE> writeCounter { 0 }; 150 std::atomic<INDEX_TYPE> readCounter { 0 }; 151 152 }; 153 154 #endif //RHYTHMGAME_LOCKFREEQUEUE_H 155