C++ Logo

std-proposals

Advanced search

Container with non-blocking iteration.

From: Ben Crowhurst <ben.crowhurst_at_[hidden]>
Date: Thu, 19 Aug 2021 11:13:42 +1000
All,

I'd like to discuss a proposal for a non-blocking iterable container type
with behaviour similar to std::array.

Given an application has a collection of long-lived resources that require
attention over its lifespan e.g networked connections. It is beneficial to
have multiple worker threads iterate over the collection simultaneously
without blocking each other on individual contained items. In the event of
a locked item, the iterator sources an alternative further down the
sequence or container::end if none is found.
std::contingent<SocketListener, 100> {
    SocketListener("1.1.1.1", "1"),
    SocketListener("2.2.2.2", "2),
    ...
    SocketListener("99.99.99.99", "99"),
};

for (auto& socket : sockets) {
    //we have locked the individual item; safe to modify.
    socket->accept();
    ...
    socket = new Socket();
} //lock released

A const container would offer lock-free readonly access.

Basic concept:

template <typename Type, std::size_t Size, typename Locakable = std::mutex>
class contingent final
{
public:
    using value_type = Type;
    using size_type = decltype(Size);
    using difference_type = std::ptrdiff_t;
    using reference = value_type&;
    using const_reference = const value_type&;

    using pointer = value_type*;
    using const_pointer = const value_type*;
private:
    std::array<Type, Size> _values;
    std::array<Locakable, Size> _guards;

    class iterator final
    {
    public:
        using value_type = Type;
        using pointer = value_type *;
        using reference = value_type &;
        using difference_type = std::ptrdiff_t;
        using iterator_category = std::forward_iterator_tag;

        iterator(decltype(_values)& values,decltype(_guards)& guards,
size_type index = 0)
          : values(values)
          , guards(guards)
          , index(index)
        { return; }

        ~iterator(void) {
            if (index != Size)
                guards[index].unlock();
        }

        value_type& operator*(void)
        { return values[index]; }

        value_type* operator->(void)
        { return &values[index]; }

        iterator& operator++(void) {
            if (index == Size) return *this;
            else guards[index].unlock();

            while (++index != Size) {
                if (guards[index].try_lock())
                    break;
            }

            return *this;
        }

        friend bool operator!=(const iterator &lhs, const iterator &rhs)
noexcept
        { return lhs.index != rhs.index; }

    private:
        decltype(_values)& values;
        decltype(_guards)& guards;
        decltype(_guards)::size_type index;
    };

    template <typename T, std::size_t N, std::size_t... Ns>
    std::array<T, N> make_array(std::initializer_list<T> t,
std::index_sequence<Ns...>)
    { return std::array<T, N>{*(t.begin() + Ns)...}; }

public:
    constexpr explicit contingent(std::initializer_list<Type> values)
      : _values()
      , _guards() {
        if (values.size() != Size)
            throw std::out_of_range("contingent: expected N items, found
X");
        _values = make_array<Type, Size>(values,
std::make_index_sequence<Size>());
    }

    constexpr iterator begin(void) noexcept {
        for (auto index = 0; index != Size; index++)
            if (_guards[index].try_lock())
                return iterator(_values, _guards, index);
        return end();
    }

    //[[blocking]]
    constexpr reference at( size_type pos ) {
        _guards.at(pos).lock();
        return _values.at(pos);
    }

    //[[blocking]]
    constexpr reference operator[]( size_type pos ) {
        _guards[pos].lock();
        return _values[pos];
    }

    constexpr iterator end(void) noexcept
    { return iterator(_values, _guards, Size); }

    [[nodiscard]] constexpr bool empty(void) const noexcept
    { return _values.empty(); }

    constexpr size_type size(void) const noexcept
    { return Size; }

    constexpr size_type max_size(void) const noexcept
    { return Size; }
};

Regards,
Ben

Received on 2021-08-18 20:14:00