1 // Copyright 2021 The Pigweed Authors 2 // 3 // Licensed under the Apache License, Version 2.0 (the "License"); you may not 4 // use this file except in compliance with the License. You may obtain a copy of 5 // the License at 6 // 7 // https://www.apache.org/licenses/LICENSE-2.0 8 // 9 // Unless required by applicable law or agreed to in writing, software 10 // distributed under the License is distributed on an "AS IS" BASIS, WITHOUT 11 // WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the 12 // License for the specific language governing permissions and limitations under 13 // the License. 14 15 #pragma once 16 17 #include <cstdint> 18 #include <optional> 19 #include <span> 20 21 namespace pw::work_queue::internal { 22 23 // TODO(hepler): Replace this with a std::deque like container. 24 template <typename T> 25 class CircularBuffer { 26 public: CircularBuffer(std::span<T> buffer)27 explicit constexpr CircularBuffer(std::span<T> buffer) 28 : buffer_(buffer), head_(0), tail_(0), count_(0) {} 29 empty()30 bool empty() const { return count_ == 0; } full()31 bool full() const { return count_ == buffer_.size(); } size()32 size_t size() const { return count_; } capacity()33 size_t capacity() const { return buffer_.size(); } 34 35 template <typename Ty> Push(Ty && value)36 bool Push(Ty&& value) { 37 PW_DASSERT(tail_ < buffer_.size()); 38 39 if (full()) { 40 return false; 41 } 42 43 buffer_[tail_] = std::forward<Ty>(value); 44 IncrementWithWrap(tail_); 45 ++count_; 46 return true; 47 } 48 Pop()49 std::optional<T> Pop() { 50 PW_DASSERT(head_ < buffer_.size()); 51 52 if (empty()) { 53 return std::nullopt; 54 } 55 56 T entry = std::move(buffer_[head_]); 57 IncrementWithWrap(head_); 58 --count_; 59 return entry; 60 } 61 62 private: IncrementWithWrap(size_t & index)63 void IncrementWithWrap(size_t& index) const { 64 index++; 65 // Note: branch is faster than mod (%) on common embedded architectures. 66 if (index == buffer_.size()) { 67 index = 0; 68 } 69 } 70 71 std::span<T> buffer_; 72 73 size_t head_; 74 size_t tail_; 75 size_t count_; 76 }; 77 78 } // namespace pw::work_queue::internal 79