1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
|
/*
* Copyright (c) 2017-2019 Cisco and/or its affiliates.
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
* You may obtain a copy of the License at:
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/
#pragma once
#include <atomic>
#include <cstddef>
namespace utils {
/**
* NOTE: Single consumer single producer ring buffer
*/
template <typename Element, std::size_t Size>
class CircularFifo {
public:
enum { Capacity = Size + 1 };
CircularFifo() : tail_(0), head_(0), size_(0) {}
virtual ~CircularFifo() {}
bool push(const Element& item);
bool push(Element&& item);
bool pop(Element& item);
bool wasEmpty() const;
bool wasFull() const;
bool isLockFree() const;
std::size_t size() const;
private:
std::size_t increment(std::size_t idx) const;
std::atomic<std::size_t> tail_; // tail(input) index
Element array_[Capacity];
std::atomic<std::size_t> head_; // head(output) index
std::atomic<std::size_t> size_;
};
template <typename Element, std::size_t Size>
bool CircularFifo<Element, Size>::push(const Element& item) {
const auto current_tail = tail_.load(std::memory_order_relaxed);
const auto next_tail = increment(current_tail);
if (next_tail != head_.load(std::memory_order_acquire)) {
array_[current_tail] = item;
tail_.store(next_tail, std::memory_order_release);
size_++;
return true;
}
// full queue
return false;
}
/**
* Push by move
*/
template <typename Element, std::size_t Size>
bool CircularFifo<Element, Size>::push(Element&& item) {
const auto current_tail = tail_.load(std::memory_order_relaxed);
const auto next_tail = increment(current_tail);
if (next_tail != head_.load(std::memory_order_acquire)) {
array_[current_tail] = std::move(item);
tail_.store(next_tail, std::memory_order_release);
size_++;
return true;
}
// full queue
return false;
}
// Pop by Consumer can only update the head
// (load with relaxed, store with release)
// the tail must be accessed with at least acquire
template <typename Element, std::size_t Size>
bool CircularFifo<Element, Size>::pop(Element& item) {
const auto current_head = head_.load(std::memory_order_relaxed);
if (current_head == tail_.load(std::memory_order_acquire)) {
return false; // empty queue
}
item = std::move(array_[current_head]);
head_.store(increment(current_head), std::memory_order_release);
size_--;
return true;
}
template <typename Element, std::size_t Size>
bool CircularFifo<Element, Size>::wasEmpty() const {
// snapshot with acceptance of that this comparison operation is not atomic
return (head_.load() == tail_.load());
}
// snapshot with acceptance that this comparison is not atomic
template <typename Element, std::size_t Size>
bool CircularFifo<Element, Size>::wasFull() const {
const auto next_tail =
increment(tail_.load()); // acquire, we dont know who call
return (next_tail == head_.load());
}
template <typename Element, std::size_t Size>
bool CircularFifo<Element, Size>::isLockFree() const {
return (tail_.is_lock_free() && head_.is_lock_free());
}
template <typename Element, std::size_t Size>
std::size_t CircularFifo<Element, Size>::increment(std::size_t idx) const {
return (idx + 1) % Capacity;
}
template <typename Element, std::size_t Size>
std::size_t CircularFifo<Element, Size>::size() const {
return size_.load(std::memory_order_relaxed);
}
} // namespace utils
|
