kcenon::thread::policies::lockfree_sync_policy Class Reference

Lock-free synchronization policy using Michael-Scott algorithm. More...

#include <sync_policies.h>

Collaboration diagram for kcenon::thread::policies::lockfree_sync_policy:

Classes
struct	node

Public Types
using	policy_tag = sync_policy_tag

Public Member Functions
	lockfree_sync_policy ()
	Construct lock-free sync policy.
	~lockfree_sync_policy ()
	Destructor.
	lockfree_sync_policy (const lockfree_sync_policy &)=delete
lockfree_sync_policy &	operator= (const lockfree_sync_policy &)=delete
	lockfree_sync_policy (lockfree_sync_policy &&)=delete
lockfree_sync_policy &	operator= (lockfree_sync_policy &&)=delete
auto	enqueue (std::unique_ptr< job > &&value) -> common::VoidResult
	Enqueue a job (wait-free)
auto	dequeue () -> common::Result< std::unique_ptr< job > >
	Dequeue a job (lock-free)
auto	try_dequeue () -> common::Result< std::unique_ptr< job > >
	Try to dequeue a job (non-blocking, same as dequeue for lock-free)
auto	empty () const -> bool
	Check if queue appears empty (approximate)
auto	size () const -> std::size_t
	Get approximate queue size.
auto	clear () -> void
	Clear queue (best effort for lock-free)
auto	stop () -> void
	Stop the queue (sets shutdown flag)
auto	is_stopped () const -> bool
	Check if queue is stopped.
auto	set_notify (bool) -> void
	Set notify flag (no-op for lock-free)

Static Public Member Functions
static constexpr auto	get_capabilities () -> queue_capabilities
	Queue capabilities for lock-free sync policy.

Private Attributes
std::atomic< node * >	head_
std::atomic< node * >	tail_
std::atomic< bool >	shutdown_
std::atomic< std::size_t >	approximate_size_

Detailed Description

Lock-free synchronization policy using Michael-Scott algorithm.

Provides high-throughput operations without locking. Size and empty checks are approximate.

Thread Safety

• All operations are thread-safe using atomic operations
• No blocking - uses spin-wait pattern

Performance Characteristics

• Enqueue: O(1), wait-free
• Dequeue: O(1), lock-free

Definition at line 211 of file sync_policies.h.

Member Typedef Documentation

policy_tag

using kcenon::thread::policies::lockfree_sync_policy::policy_tag = sync_policy_tag

Definition at line 213 of file sync_policies.h.

Constructor & Destructor Documentation

lockfree_sync_policy() [1/3]

kcenon::thread::policies::lockfree_sync_policy::lockfree_sync_policy ( )

inline

Construct lock-free sync policy.

Definition at line 233 of file sync_policies.h.

                           : shutdown_(false), approximate_size_(0) {
        auto dummy = new node(nullptr);
        head_.store(dummy, std::memory_order_relaxed);
        tail_.store(dummy, std::memory_order_relaxed);
    }

References head_, and tail_.

~lockfree_sync_policy()

kcenon::thread::policies::lockfree_sync_policy::~lockfree_sync_policy ( )

inline

Destructor.

Definition at line 242 of file sync_policies.h.

                            {
        shutdown_.store(true, std::memory_order_release);
 
        // Drain remaining nodes
        node* current = head_.load(std::memory_order_acquire);
        while (current != nullptr) {
            node* next = current->next.load(std::memory_order_acquire);
            delete current;
            current = next;
        }
    }

References head_, kcenon::thread::policies::lockfree_sync_policy::node::next, and shutdown_.

lockfree_sync_policy() [2/3]

kcenon::thread::policies::lockfree_sync_policy::lockfree_sync_policy ( const lockfree_sync_policy & )

delete

lockfree_sync_policy() [3/3]

kcenon::thread::policies::lockfree_sync_policy::lockfree_sync_policy ( lockfree_sync_policy && )

delete

Member Function Documentation

clear()

auto kcenon::thread::policies::lockfree_sync_policy::clear ( ) -> void

inline

Clear queue (best effort for lock-free)

Definition at line 363 of file sync_policies.h.

                         {
        while (true) {
            auto result = dequeue();
            if (result.is_err()) {
                break;
            }
        }
    }

References dequeue().

Here is the call graph for this function:

dequeue()

auto kcenon::thread::policies::lockfree_sync_policy::dequeue ( ) -> common::Result<std::unique_ptr<job>>

inlinenodiscard

Dequeue a job (lock-free)

Returns

Result containing the job or error

Definition at line 304 of file sync_policies.h.

                                                                     {
        while (true) {
            node* head = head_.load(std::memory_order_acquire);
            node* tail = tail_.load(std::memory_order_acquire);
            node* next = head->next.load(std::memory_order_acquire);
 
            if (head == head_.load(std::memory_order_acquire)) {
                if (head == tail) {
                    if (next == nullptr) {
                        return common::error_info{-121, "queue is empty", "thread_system"};
                    }
                    tail_.compare_exchange_weak(tail, next,
                        std::memory_order_release,
                        std::memory_order_relaxed);
                } else {
                    if (next != nullptr) {
                        auto value = std::move(next->data);
                        if (head_.compare_exchange_weak(head, next,
                                std::memory_order_release,
                                std::memory_order_relaxed)) {
                            approximate_size_.fetch_sub(1, std::memory_order_relaxed);
                            delete head;
                            return value;
                        }
                    }
                }
            }
        }
    }

References approximate_size_, kcenon::thread::policies::lockfree_sync_policy::node::data, head_, kcenon::thread::policies::lockfree_sync_policy::node::next, and tail_.

Referenced by clear(), and try_dequeue().

Here is the caller graph for this function:

empty()

auto kcenon::thread::policies::lockfree_sync_policy::empty ( ) const -> bool

inlinenodiscard

Check if queue appears empty (approximate)

Returns

true if queue appears empty

Definition at line 346 of file sync_policies.h.

                                             {
        node* head = head_.load(std::memory_order_acquire);
        node* next = head->next.load(std::memory_order_acquire);
        return next == nullptr;
    }

References head_, and kcenon::thread::policies::lockfree_sync_policy::node::next.

enqueue()

auto kcenon::thread::policies::lockfree_sync_policy::enqueue ( std::unique_ptr< job > && value ) -> common::VoidResult

inlinenodiscard

Enqueue a job (wait-free)

Parameters

value

Job to enqueue

Returns

VoidResult indicating success or error

Definition at line 265 of file sync_policies.h.

                                                                               {
        if (!value) {
            return common::error_info{-105, "cannot enqueue null job", "thread_system"};
        }
 
        if (shutdown_.load(std::memory_order_acquire)) {
            return common::error_info{-122, "queue is shutting down", "thread_system"};
        }
 
        auto new_node = new node(std::move(value));
 
        while (true) {
            node* tail = tail_.load(std::memory_order_acquire);
            node* next = tail->next.load(std::memory_order_acquire);
 
            if (tail == tail_.load(std::memory_order_acquire)) {
                if (next == nullptr) {
                    if (tail->next.compare_exchange_weak(next, new_node,
                            std::memory_order_release,
                            std::memory_order_relaxed)) {
                        tail_.compare_exchange_strong(tail, new_node,
                            std::memory_order_release,
                            std::memory_order_relaxed);
                        approximate_size_.fetch_add(1, std::memory_order_relaxed);
                        return common::ok();
                    }
                } else {
                    tail_.compare_exchange_weak(tail, next,
                        std::memory_order_release,
                        std::memory_order_relaxed);
                }
            }
        }
    }

References approximate_size_, kcenon::thread::policies::lockfree_sync_policy::node::next, shutdown_, and tail_.

get_capabilities()

static constexpr auto kcenon::thread::policies::lockfree_sync_policy::get_capabilities ( ) -> queue_capabilities

inlinestaticnodiscardconstexpr

Queue capabilities for lock-free sync policy.

Definition at line 218 of file sync_policies.h.

                                                                                 {
        return queue_capabilities{
            .exact_size = false,
            .atomic_empty_check = false,
            .lock_free = true,
            .wait_free = false,
            .supports_batch = false,
            .supports_blocking_wait = false,
            .supports_stop = false
        };
    }

Referenced by kcenon::thread::policies::adaptive_sync_policy::get_capabilities().

Here is the caller graph for this function:

is_stopped()

auto kcenon::thread::policies::lockfree_sync_policy::is_stopped ( ) const -> bool

inlinenodiscard

Check if queue is stopped.

Returns

true if stopped

Definition at line 383 of file sync_policies.h.

                                                  {
        return shutdown_.load(std::memory_order_acquire);
    }

References shutdown_.

operator=() [1/2]

lockfree_sync_policy & kcenon::thread::policies::lockfree_sync_policy::operator= ( const lockfree_sync_policy & )

delete

operator=() [2/2]

lockfree_sync_policy & kcenon::thread::policies::lockfree_sync_policy::operator= ( lockfree_sync_policy && )

delete

set_notify()

auto kcenon::thread::policies::lockfree_sync_policy::set_notify ( bool ) -> void

inline

Set notify flag (no-op for lock-free)

Parameters

notify

Ignored

Definition at line 391 of file sync_policies.h.

                                    {
        // No-op: lock-free queue doesn't use condition variables
    }

size()

auto kcenon::thread::policies::lockfree_sync_policy::size ( ) const -> std::size_t

inlinenodiscard

Get approximate queue size.

Returns

Approximate number of jobs

Definition at line 356 of file sync_policies.h.

                                                 {
        return approximate_size_.load(std::memory_order_relaxed);
    }

References approximate_size_.

stop()

auto kcenon::thread::policies::lockfree_sync_policy::stop ( ) -> void

inline

Stop the queue (sets shutdown flag)

Definition at line 375 of file sync_policies.h.

                        {
        shutdown_.store(true, std::memory_order_release);
    }

References shutdown_.

try_dequeue()

auto kcenon::thread::policies::lockfree_sync_policy::try_dequeue ( ) -> common::Result<std::unique_ptr<job>>

inlinenodiscard

Try to dequeue a job (non-blocking, same as dequeue for lock-free)

Returns

Result containing the job or error

Definition at line 338 of file sync_policies.h.

                                                                         {
        return dequeue();
    }

References dequeue().

Here is the call graph for this function:

Member Data Documentation

approximate_size_

std::atomic<std::size_t> kcenon::thread::policies::lockfree_sync_policy::approximate_size_

mutableprivate

Definition at line 407 of file sync_policies.h.

Referenced by dequeue(), enqueue(), and size().

head_

std::atomic<node*> kcenon::thread::policies::lockfree_sync_policy::head_

private

Definition at line 404 of file sync_policies.h.

Referenced by dequeue(), empty(), lockfree_sync_policy(), and ~lockfree_sync_policy().

shutdown_

std::atomic<bool> kcenon::thread::policies::lockfree_sync_policy::shutdown_

private

Definition at line 406 of file sync_policies.h.

Referenced by enqueue(), is_stopped(), stop(), and ~lockfree_sync_policy().

tail_

std::atomic<node*> kcenon::thread::policies::lockfree_sync_policy::tail_

private

Definition at line 405 of file sync_policies.h.

Referenced by dequeue(), enqueue(), and lockfree_sync_policy().

---

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

• include/kcenon/thread/policies/sync_policies.h