kcenon::thread::lockfree::circular_array< T > Class Template Reference

Dynamic circular array for work-stealing deque. More...

#include <work_stealing_deque.h>

Inheritance diagram for kcenon::thread::lockfree::circular_array< T >:

Collaboration diagram for kcenon::thread::lockfree::circular_array< T >:

Public Member Functions
	circular_array (std::size_t log_size)
	Constructs a circular array with given capacity.
	~circular_array ()
	circular_array (const circular_array &)=delete
circular_array &	operator= (const circular_array &)=delete
std::size_t	size () const noexcept
	Get the capacity of the array.
T	get (std::int64_t index) const noexcept
	Get element at index with relaxed memory ordering.
void	put (std::int64_t index, T value) noexcept
	Store element at index with relaxed memory ordering.
circular_array *	grow (std::int64_t bottom, std::int64_t top) const
	Create a new array with double the capacity, copying elements.

Private Attributes
std::size_t	log_size_
std::size_t	size_
std::size_t	mask_
std::atomic< T > *	buffer_

Detailed Description

template<typename T>
class kcenon::thread::lockfree::circular_array< T >

Dynamic circular array for work-stealing deque.

This class provides a resizable circular buffer used internally by the work-stealing deque. It supports lock-free growth operations.

Template Parameters

T	Element type stored in the array

Definition at line 33 of file work_stealing_deque.h.

Constructor & Destructor Documentation

circular_array() [1/2]

template<typename T >

kcenon::thread::lockfree::circular_array< T >::circular_array ( std::size_t log_size )

inlineexplicit

Constructs a circular array with given capacity.

Parameters

log_size

Log base 2 of the capacity (capacity = 2^log_size)

Definition at line 39 of file work_stealing_deque.h.

        : log_size_(log_size)
        , size_(1ULL << log_size)
        , mask_(size_ - 1)
        , buffer_(new std::atomic<T>[size_]) {
        for (std::size_t i = 0; i < size_; ++i) {
            buffer_[i].store(T{}, std::memory_order_relaxed);
        }
    }

References kcenon::thread::lockfree::circular_array< T >::buffer_, and kcenon::thread::lockfree::circular_array< T >::size_.

Referenced by kcenon::thread::lockfree::circular_array< T >::grow().

Here is the caller graph for this function:

~circular_array()

template<typename T >

kcenon::thread::lockfree::circular_array< T >::~circular_array ( )

inline

Definition at line 49 of file work_stealing_deque.h.

                      {
        delete[] buffer_;
    }

References kcenon::thread::lockfree::circular_array< T >::buffer_.

circular_array() [2/2]

template<typename T >

kcenon::thread::lockfree::circular_array< T >::circular_array ( const circular_array< T > & )

delete

Member Function Documentation

get()

template<typename T >

T kcenon::thread::lockfree::circular_array< T >::get ( std::int64_t index ) const

inlinenodiscardnoexcept

Get element at index with relaxed memory ordering.

Parameters

index

Array index (will be masked for circular access)

Returns

Element at the given index

Definition at line 70 of file work_stealing_deque.h.

                                                         {
        return buffer_[index & mask_].load(std::memory_order_relaxed);
    }

References kcenon::thread::lockfree::circular_array< T >::buffer_, and kcenon::thread::lockfree::circular_array< T >::mask_.

Referenced by kcenon::thread::lockfree::circular_array< T >::grow(), kcenon::thread::lockfree::work_stealing_deque< T >::pop(), kcenon::thread::lockfree::work_stealing_deque< T >::steal(), and kcenon::thread::lockfree::work_stealing_deque< T >::steal_batch().

Here is the caller graph for this function:

grow()

template<typename T >

circular_array * kcenon::thread::lockfree::circular_array< T >::grow ( std::int64_t bottom, std::int64_t top ) const

inlinenodiscard

Create a new array with double the capacity, copying elements.

Parameters

bottom	Current bottom index
top	Current top index

Returns

New circular array with doubled capacity

Definition at line 89 of file work_stealing_deque.h.

                                                                                {
        auto* new_array = new circular_array(log_size_ + 1);
        for (std::int64_t i = top; i < bottom; ++i) {
            new_array->put(i, get(i));
        }
        return new_array;
    }

References kcenon::thread::lockfree::circular_array< T >::circular_array(), kcenon::thread::lockfree::circular_array< T >::get(), and kcenon::thread::lockfree::circular_array< T >::log_size_.

Referenced by kcenon::thread::lockfree::work_stealing_deque< T >::push().

Here is the call graph for this function:

Here is the caller graph for this function:

operator=()

template<typename T >

circular_array & kcenon::thread::lockfree::circular_array< T >::operator= ( const circular_array< T > & )

delete

put()

template<typename T >

void kcenon::thread::lockfree::circular_array< T >::put ( std::int64_t index, T value )

inlinenoexcept

Store element at index with relaxed memory ordering.

Parameters

index	Array index (will be masked for circular access)
value	Value to store

Definition at line 79 of file work_stealing_deque.h.

                                                 {
        buffer_[index & mask_].store(value, std::memory_order_relaxed);
    }

References kcenon::thread::lockfree::circular_array< T >::buffer_, and kcenon::thread::lockfree::circular_array< T >::mask_.

Referenced by kcenon::thread::lockfree::work_stealing_deque< T >::push().

Here is the caller graph for this function:

size()

template<typename T >

std::size_t kcenon::thread::lockfree::circular_array< T >::size ( ) const

inlinenodiscardnoexcept

Get the capacity of the array.

Returns

Number of elements the array can hold

Definition at line 61 of file work_stealing_deque.h.

                                                  {
        return size_;
    }

References kcenon::thread::lockfree::circular_array< T >::size_.

Referenced by kcenon::thread::lockfree::work_stealing_deque< T >::push().

Here is the caller graph for this function:

Member Data Documentation

buffer_

template<typename T >

std::atomic<T>* kcenon::thread::lockfree::circular_array< T >::buffer_

private

Definition at line 101 of file work_stealing_deque.h.

Referenced by kcenon::thread::lockfree::circular_array< T >::circular_array(), kcenon::thread::lockfree::circular_array< T >::get(), kcenon::thread::lockfree::circular_array< T >::put(), and kcenon::thread::lockfree::circular_array< T >::~circular_array().

log_size_

template<typename T >

std::size_t kcenon::thread::lockfree::circular_array< T >::log_size_

private

Definition at line 98 of file work_stealing_deque.h.

Referenced by kcenon::thread::lockfree::circular_array< T >::grow().

mask_

template<typename T >

std::size_t kcenon::thread::lockfree::circular_array< T >::mask_

private

Definition at line 100 of file work_stealing_deque.h.

Referenced by kcenon::thread::lockfree::circular_array< T >::get(), and kcenon::thread::lockfree::circular_array< T >::put().

size_

template<typename T >

std::size_t kcenon::thread::lockfree::circular_array< T >::size_

private

Definition at line 99 of file work_stealing_deque.h.

Referenced by kcenon::thread::lockfree::circular_array< T >::circular_array(), and kcenon::thread::lockfree::circular_array< T >::size().

---

The documentation for this class was generated from the following file:

• include/kcenon/thread/lockfree/work_stealing_deque.h