lockfree.h

Go to the documentation of this file.

// SPDX-FileCopyrightText: Copyright (C) 2015 swift Project Community / Contributors
// SPDX-License-Identifier: GPL-3.0-or-later OR LicenseRef-swift-pilot-client-1
 
 
#ifndef SWIFT_MISC_LOCKFREE_H
#define SWIFT_MISC_LOCKFREE_H
 
#include <memory>
#include <tuple>
#include <type_traits>
#include <utility>
 
#include <QString>
#include <QThread>
#include <QtGlobal>
 
// http://www.drdobbs.com/lock-free-data-structures/184401865
// http://en.cppreference.com/w/cpp/memory/shared_ptr/atomic
 
namespace swift::misc
{
 
    template <typename>
    class LockFree;
 
    template <typename T>
    class LockFreeReader
    {
    public:
        const T &get() const { return *m_ptr; }
        const T *operator->() const { return m_ptr.get(); }
        const T &operator*() const { return *m_ptr; }
        operator const T &() const { return *m_ptr; }
 
        LockFreeReader(const LockFreeReader &) = default;
 
        LockFreeReader &operator=(const LockFreeReader &) = default;
 
    private:
        friend class LockFree<std::remove_const_t<T>>;
 
        LockFreeReader(std::shared_ptr<const T> ptr) : m_ptr(ptr) {}
        std::shared_ptr<const T> m_ptr;
    };
 
    template <typename T>
    class LockFreeUniqueWriter
    {
    public:
        T &get() { return *m_ptr; }
        T *operator->() { return m_ptr.get(); }
        T &operator*() { return *m_ptr; }
        operator T &() { return *m_ptr; }
 
        LockFreeUniqueWriter &operator=(const T &other)
        {
            *m_ptr = other;
            return *this;
        }
 
        LockFreeUniqueWriter &operator=(T &&other) noexcept(std::is_nothrow_move_assignable_v<T>)
        {
            *m_ptr = std::move(other);
            return *this;
        }
 
        LockFreeUniqueWriter(const LockFreeUniqueWriter &) = delete;
        LockFreeUniqueWriter &operator=(const LockFreeUniqueWriter &) = delete;
 
        LockFreeUniqueWriter(LockFreeUniqueWriter &&other) noexcept
            : m_old(std::move(other.m_old)), m_now(std::move(other.m_now)), m_ptr(std::move(other.m_ptr))
        {}
 
        LockFreeUniqueWriter &operator=(LockFreeUniqueWriter &&other) noexcept
        {
            std::tie(m_old, m_now, m_ptr) =
                std::forward_as_tuple(std::move(other.m_old), std::move(other.m_now), std::move(other.m_ptr));
            return *this;
        }
 
        ~LockFreeUniqueWriter()
        {
            if (m_ptr.use_count() == 0) { return; } // *this has been moved from
            bool success = std::atomic_compare_exchange_strong(m_now, &m_old, std::shared_ptr<const T>(m_ptr));
            Q_ASSERT_X(success, Q_FUNC_INFO, "UniqueWriter detected simultaneous writes");
            Q_UNUSED(success);
        }
 
    private:
        friend class LockFree<T>;
 
        LockFreeUniqueWriter(std::shared_ptr<const T> ptr, std::shared_ptr<const T> *now)
            : m_old(ptr), m_now(now), m_ptr(std::make_shared<T>(*m_old))
        {}
        std::shared_ptr<const T> m_old;
        std::shared_ptr<const T> *m_now;
        std::shared_ptr<T> m_ptr;
    };
 
    template <typename T>
    class LockFreeSharedWriter
    {
    public:
        T &get() { return *m_ptr; }
        T *operator->() { return m_ptr.get(); }
        T &operator*() { return *m_ptr; }
        operator T &() { return *m_ptr; }
 
        LockFreeSharedWriter &operator=(const T &other)
        {
            *m_ptr = other;
            return *this;
        }
 
        LockFreeSharedWriter &operator=(T &&other) noexcept(std::is_nothrow_move_assignable_v<T>)
        {
            *m_ptr = std::move(other);
            return *this;
        }
 
        bool operator!() { return !operator bool(); }
 
        operator bool()
        {
            Q_ASSERT_X(m_ptr.use_count() > 0, Q_FUNC_INFO, "SharedWriter tried to commit changes twice");
            if (std::atomic_compare_exchange_strong(m_now, &m_old, std::shared_ptr<const T>(m_ptr)))
            {
                m_ptr.reset();
                return true;
            }
            QThread::msleep(1);
            m_old = std::atomic_load(m_now);
            m_ptr = std::make_shared<T>(*m_old);
            return false;
        }
 
        ~LockFreeSharedWriter()
        {
            Q_ASSERT_X(m_ptr.use_count() == 0, Q_FUNC_INFO, "SharedWriter destroyed without committing changes");
        }
 
        LockFreeSharedWriter(const LockFreeSharedWriter &) = delete;
        LockFreeSharedWriter &operator=(const LockFreeSharedWriter &) = delete;
 
        LockFreeSharedWriter(LockFreeSharedWriter &&other) noexcept
            : m_old(std::move(other.m_old)), m_now(std::move(other.m_now)), m_ptr(std::move(other.m_ptr))
        {}
 
        LockFreeSharedWriter &operator=(LockFreeSharedWriter &&other) noexcept
        {
            std::tie(m_old, m_now, m_ptr) =
                std::forward_as_tuple(std::move(other.m_old), std::move(other.m_now), std::move(other.m_ptr));
            return *this;
        }
 
    private:
        friend class LockFree<T>;
 
        LockFreeSharedWriter(std::shared_ptr<const T> ptr, std::shared_ptr<const T> *now)
            : m_old(ptr), m_now(now), m_ptr(std::make_shared<T>(*m_old))
        {}
        std::shared_ptr<const T> m_old;
        std::shared_ptr<const T> *m_now;
        std::shared_ptr<T> m_ptr;
    };
 
    template <typename T>
    class LockFree
    {
    public:
        LockFree() = default;
 
        LockFree(const T &other) : m_ptr(std::make_shared<const T>(other)) {}
 
        LockFree(T &&other) noexcept(std::is_nothrow_move_assignable_v<T>)
            : m_ptr(std::make_shared<const T>(std::move(other)))
        {}
 
        LockFree(const LockFree &) = delete;
        LockFree &operator=(const LockFree &) = delete;
        LockFree(LockFree &&) = delete;
        LockFree &operator=(LockFree &&) = delete;
 
        LockFreeReader<const T> read() const { return { std::atomic_load(&m_ptr) }; }
 
        LockFreeUniqueWriter<T> uniqueWrite() { return { std::atomic_load(&m_ptr), &m_ptr }; }
 
        LockFreeSharedWriter<T> sharedWrite() { return { std::atomic_load(&m_ptr), &m_ptr }; }
 
        template <typename F>
        auto read(F &&inspector)
        {
            return std::forward<F>(inspector)(read().get());
        }
 
        template <typename F>
        void uniqueWrite(F &&mutator)
        {
            std::forward<F>(mutator)(uniqueWrite().get());
        }
 
        template <typename F>
        void sharedWrite(F &&mutator)
        {
            auto writer = sharedWrite();
            do {
                std::forward<F>(mutator)(writer.get());
            }
            while (!writer);
        }
 
    private:
        std::shared_ptr<const T> m_ptr = std::make_shared<const T>();
    };
 
    template <template <typename> class T, typename... Ts>
    class LockFreeMulti
    {
    public:
        LockFreeMulti(std::tuple<T<Ts> &&...> &&tup) : m_tup(std::move(tup)) {}
 
        template <typename F>
        auto operator()(F &&function) &&
        {
            return call(std::forward<F>(function), std::make_index_sequence<sizeof...(Ts)>());
        }
 
    private:
        template <typename F, size_t... Is>
        auto call(F &&function, std::index_sequence<Is...>)
        {
            return std::forward<F>(function)(std::get<Is>(m_tup).get()...);
        }
 
        const std::tuple<T<Ts>...> m_tup;
    };
 
    template <typename... Ts>
    LockFreeMulti<LockFreeReader, const Ts...> multiRead(const LockFree<Ts> &...vs)
    {
        return { std::forward_as_tuple(vs.read()...) };
    }
 
    template <typename... Ts>
    LockFreeMulti<LockFreeUniqueWriter, Ts...> multiUniqueWrite(LockFree<Ts> &...vs)
    {
        return { std::forward_as_tuple(vs.uniqueWrite()...) };
    }
 
 
    template <typename T>
    typename T::const_iterator begin(const LockFreeReader<T> &reader)
    {
        return reader->begin();
    }
 
    template <typename T>
    typename T::const_iterator end(const LockFreeReader<T> &reader)
    {
        return reader->end();
    }
 
    template <typename T>
    typename T::iterator begin(const LockFreeUniqueWriter<T> &writer)
    {
        return writer->begin();
    }
 
    template <typename T>
    typename T::iterator end(const LockFreeUniqueWriter<T> &writer)
    {
        return writer->end();
    }
 
    template <typename T>
    typename T::iterator begin(const LockFreeSharedWriter<T> &writer)
    {
        return writer->begin();
    }
 
    template <typename T>
    typename T::iterator end(const LockFreeSharedWriter<T> &writer)
    {
        return writer->end();
    }
 
 
    template <typename T>
    typename T::const_iterator begin(const LockFreeReader<T> &&) = delete;
 
    template <typename T>
    typename T::const_iterator end(const LockFreeReader<T> &&) = delete;
 
    template <typename T>
    typename T::iterator begin(const LockFreeUniqueWriter<T> &&) = delete;
 
    template <typename T>
    typename T::iterator end(const LockFreeUniqueWriter<T> &&) = delete;
 
    template <typename T>
    typename T::iterator begin(const LockFreeSharedWriter<T> &&) = delete;
 
    template <typename T>
    typename T::iterator end(const LockFreeSharedWriter<T> &&) = delete;
 
} // namespace swift::misc
 
#endif // SWIFT_MISC_LOCKFREE_H