lockfree_queue.hpp

// Copyright (c) 2020 by Robert Bosch GmbH. All rights reserved.
// Copyright (c) 2020 - 2021 by Apex.AI Inc. All rights reserved.
//
// 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.
//
// SPDX-License-Identifier: Apache-2.0
 
#ifndef IOX_HOOFS_CONCURRENT_LOCKFREE_QUEUE_HPP
#define IOX_HOOFS_CONCURRENT_LOCKFREE_QUEUE_HPP
 
#include "iceoryx_hoofs/cxx/optional.hpp"
#include "iceoryx_hoofs/internal/concurrent/lockfree_queue/buffer.hpp"
#include "iceoryx_hoofs/internal/concurrent/lockfree_queue/index_queue.hpp"
 
#include <atomic>
 
 
namespace iox
{
namespace concurrent
{
template <typename ElementType, uint64_t Capacity>
class LockFreeQueue
{
  public:
    using element_t = ElementType;

    LockFreeQueue() noexcept;
 
    ~LockFreeQueue() noexcept = default;
 
    // remark: a thread-safe and lockfree implementation of copy seems impossible
    // but unsafe copying (i.e. where synchronization is up to the user) would be possible
    // can be implemented when it is needed
    LockFreeQueue(const LockFreeQueue&) = delete;
    LockFreeQueue(LockFreeQueue&&) = delete;
    LockFreeQueue& operator=(const LockFreeQueue&) = delete;
    LockFreeQueue& operator=(LockFreeQueue&&) = delete;

    constexpr uint64_t capacity() const noexcept;

    bool tryPush(ElementType&& value) noexcept;

    bool tryPush(const ElementType& value) noexcept;

    iox::cxx::optional<ElementType> push(const ElementType& value) noexcept;

    iox::cxx::optional<ElementType> push(ElementType&& value) noexcept;

    iox::cxx::optional<ElementType> pop() noexcept;

    bool empty() const noexcept;

    uint64_t size() const noexcept;
 
  protected:
    using Queue = IndexQueue<Capacity>;
    using BufferIndex = typename Queue::value_t;
 
    // remark: actually m_freeIndices do not have to be in a queue, it could be another
    // multi-push multi-pop capable lockfree container (e.g. a stack or a list)
    Queue m_freeIndices;
 
    // required to be a queue for LockFreeQueue to exhibit FIFO behaviour
    Queue m_usedIndices;
 
    Buffer<ElementType, Capacity, BufferIndex> m_buffer;
 
    std::atomic<uint64_t> m_size{0u};
 
    // template is needed to distinguish between lvalue and rvalue T references
    // (universal reference type deduction)
    template <typename T>
    void writeBufferAt(const BufferIndex&, T&&) noexcept;
 
    // needed to avoid code duplication (via universal reference type deduction)
    template <typename T>
    iox::cxx::optional<ElementType> pushImpl(T&& value) noexcept;
 
    cxx::optional<ElementType> readBufferAt(const BufferIndex&) noexcept;
};
} // namespace concurrent
} // namespace iox
 
#include "iceoryx_hoofs/internal/concurrent/lockfree_queue/lockfree_queue.inl"
 
#endif // IOX_HOOFS_CONCURRENT_LOCKFREE_QUEUE_HPP