iceoryx_doc  1.0.1
lockfree_queue.hpp
1 // Copyright (c) 2020 by Robert Bosch GmbH, Apex.AI Inc. All rights reserved.
2 //
3 // Licensed under the Apache License, Version 2.0 (the "License");
4 // you may not use this file except in compliance with the License.
5 // You may obtain a copy of the License at
6 //
7 // http://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,
11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 // See the License for the specific language governing permissions and
13 // limitations under the License.
14 //
15 // SPDX-License-Identifier: Apache-2.0
16 
17 #ifndef IOX_UTILS_CONCURRENT_LOCKFREE_QUEUE_HPP
18 #define IOX_UTILS_CONCURRENT_LOCKFREE_QUEUE_HPP
19 
20 #include "iceoryx_utils/cxx/optional.hpp"
21 #include "iceoryx_utils/internal/concurrent/lockfree_queue/buffer.hpp"
22 #include "iceoryx_utils/internal/concurrent/lockfree_queue/index_queue.hpp"
23 
24 #include <atomic>
25 
26 
27 namespace iox
28 {
29 namespace concurrent
30 {
33 template <typename ElementType, uint64_t Capacity>
35 {
36  public:
37  using element_t = ElementType;
38 
40  LockFreeQueue() noexcept;
41 
42  ~LockFreeQueue() = default;
43 
44  // remark: a thread-safe and lockfree implementation of copy seems impossible
45  // but unsafe copying (i.e. where synchronization is up to the user) would be possible
46  // can be implemented when it is needed
47  LockFreeQueue(const LockFreeQueue&) = delete;
48  LockFreeQueue(LockFreeQueue&&) = delete;
49  LockFreeQueue& operator=(const LockFreeQueue&) = delete;
50  LockFreeQueue& operator=(LockFreeQueue&&) = delete;
51 
54  constexpr uint64_t capacity() const noexcept;
55 
60  bool tryPush(ElementType&& value) noexcept;
61 
66  bool tryPush(const ElementType& value) noexcept;
67 
73  iox::cxx::optional<ElementType> push(const ElementType& value) noexcept;
74 
80  iox::cxx::optional<ElementType> push(ElementType&& value) noexcept;
81 
86 
93  bool empty() const noexcept;
94 
100  uint64_t size() const noexcept;
101 
102  protected:
103  using Queue = IndexQueue<Capacity>;
104  using BufferIndex = typename Queue::value_t;
105 
106  // remark: actually m_freeIndices do not have to be in a queue, it could be another
107  // multi-push multi-pop capable lockfree container (e.g. a stack or a list)
108  Queue m_freeIndices;
109 
110  // required to be a queue for LockFreeQueue to exhibit FIFO behaviour
111  Queue m_usedIndices;
112 
114 
115  std::atomic<uint64_t> m_size{0u};
116 
117  // template is needed to distinguish between lvalue and rvalue T references
118  // (universal reference type deduction)
119  template <typename T>
120  void writeBufferAt(const BufferIndex&, T&&);
121 
122  // needed to avoid code duplication (via universal reference type deduction)
123  template <typename T>
124  iox::cxx::optional<ElementType> pushImpl(T&& value) noexcept;
125 
126  cxx::optional<ElementType> readBufferAt(const BufferIndex&);
127 };
128 } // namespace concurrent
129 } // namespace iox
130 
131 #include "iceoryx_utils/internal/concurrent/lockfree_queue/lockfree_queue.inl"
132 
133 #endif // IOX_UTILS_CONCURRENT_LOCKFREE_QUEUE_HPP
lockfree queue capable of storing indices 0,1,... Capacity-1
Definition: index_queue.hpp:40
implements a lock free queue (i.e. container with FIFO order) of elements of type T with a fixed Capa...
Definition: lockfree_queue.hpp:35
bool tryPush(ElementType &&value) noexcept
tries to insert value in FIFO order, moves the value internally
Definition: lockfree_queue.inl:56
bool empty() const noexcept
check whether the queue is empty
Definition: lockfree_queue.inl:140
LockFreeQueue() noexcept
creates and initalizes an empty LockFreeQueue
Definition: lockfree_queue.inl:26
constexpr uint64_t capacity() const noexcept
returns the capacity of the queue
Definition: lockfree_queue.inl:33
uint64_t size() const noexcept
get the number of stored elements in the queue
Definition: lockfree_queue.inl:146
iox::cxx::optional< ElementType > push(const ElementType &value) noexcept
inserts value in FIFO order, always succeeds by removing the oldest value when the queue is detected ...
Definition: lockfree_queue.inl:111
iox::cxx::optional< ElementType > pop() noexcept
tries to remove value in FIFO order
Definition: lockfree_queue.inl:123
Optional implementation from the C++17 standard with C++11. The interface is analog to the C++17 stan...
Definition: optional.hpp:63
building block to easily create free function for logging in a library context
Definition: lockfree_queue.hpp:28