1 // Copyright(c) 2015-present, Gabi Melman & spdlog contributors.
2 // Distributed under the MIT License (http://opensource.org/licenses/MIT)
3 
4 // circular q view of std::vector.
5 #pragma once
6 
7 #include <vector>
8 #include <cassert>
9 
10 namespace spdlog {
11 namespace details {
12 template<typename T>
13 class circular_q
14 {
15     size_t max_items_ = 0;
16     typename std::vector<T>::size_type head_ = 0;
17     typename std::vector<T>::size_type tail_ = 0;
18     size_t overrun_counter_ = 0;
19     std::vector<T> v_;
20 
21 public:
22     using value_type = T;
23 
24     // empty ctor - create a disabled queue with no elements allocated at all
25     circular_q() = default;
26 
circular_q(size_t max_items)27     explicit circular_q(size_t max_items)
28         : max_items_(max_items + 1) // one item is reserved as marker for full q
29         , v_(max_items_)
30     {}
31 
32     circular_q(const circular_q &) = default;
33     circular_q &operator=(const circular_q &) = default;
34 
35     // move cannot be default,
36     // since we need to reset head_, tail_, etc to zero in the moved object
circular_q(circular_q && other)37     circular_q(circular_q &&other) SPDLOG_NOEXCEPT
38     {
39         copy_moveable(std::move(other));
40     }
41 
42     circular_q &operator=(circular_q &&other) SPDLOG_NOEXCEPT
43     {
44         copy_moveable(std::move(other));
45         return *this;
46     }
47 
48     // push back, overrun (oldest) item if no room left
push_back(T && item)49     void push_back(T &&item)
50     {
51         if (max_items_ > 0)
52         {
53             v_[tail_] = std::move(item);
54             tail_ = (tail_ + 1) % max_items_;
55 
56             if (tail_ == head_) // overrun last item if full
57             {
58                 head_ = (head_ + 1) % max_items_;
59                 ++overrun_counter_;
60             }
61         }
62     }
63 
64     // Return reference to the front item.
65     // If there are no elements in the container, the behavior is undefined.
front()66     const T &front() const
67     {
68         return v_[head_];
69     }
70 
front()71     T &front()
72     {
73         return v_[head_];
74     }
75 
76     // Return number of elements actually stored
size()77     size_t size() const
78     {
79         if (tail_ >= head_)
80         {
81             return tail_ - head_;
82         }
83         else
84         {
85             return max_items_ - (head_ - tail_);
86         }
87     }
88 
89     // Return const reference to item by index.
90     // If index is out of range 0…size()-1, the behavior is undefined.
at(size_t i)91     const T &at(size_t i) const
92     {
93         assert(i < size());
94         return v_[(head_ + i) % max_items_];
95     }
96 
97     // Pop item from front.
98     // If there are no elements in the container, the behavior is undefined.
pop_front()99     void pop_front()
100     {
101         head_ = (head_ + 1) % max_items_;
102     }
103 
empty()104     bool empty() const
105     {
106         return tail_ == head_;
107     }
108 
full()109     bool full() const
110     {
111         // head is ahead of the tail by 1
112         if (max_items_ > 0)
113         {
114             return ((tail_ + 1) % max_items_) == head_;
115         }
116         return false;
117     }
118 
overrun_counter()119     size_t overrun_counter() const
120     {
121         return overrun_counter_;
122     }
123 
124 private:
125     // copy from other&& and reset it to disabled state
copy_moveable(circular_q && other)126     void copy_moveable(circular_q &&other) SPDLOG_NOEXCEPT
127     {
128         max_items_ = other.max_items_;
129         head_ = other.head_;
130         tail_ = other.tail_;
131         overrun_counter_ = other.overrun_counter_;
132         v_ = std::move(other.v_);
133 
134         // put &&other in disabled, but valid state
135         other.max_items_ = 0;
136         other.head_ = other.tail_ = 0;
137         other.overrun_counter_ = 0;
138     }
139 };
140 } // namespace details
141 } // namespace spdlog
142