EntropyEngine::Core::Concurrency::SignalTree

EntropyEngine::Core::Concurrency::SignalTree

A lock-free binary tree for signal selection and management. More…

#include <SignalTree.h>

Inherits from EntropyEngine::Core::Concurrency::SignalTreeBase

Public Types

	Name
enum class	TreePath { Right = 2, Left = 1}

Public Functions

	Name
void	signal(size_t leafIndex) Alias for set() - signals a contract is ready for execution.
virtual void	set(size_t leafIndex) override Sets a signal as active in the tree.
virtual std::pair< size_t, bool >	select(uint64_t & biasFlags) override Selects and clears an active signal from the tree.
SignalTree &	operator=(const SignalTree & ) =delete
SignalTree &	operator=(SignalTree && ) =delete
virtual bool	isEmpty() const override Checks if the tree has no active signals.
size_t	getTotalNodes() const Gets total number of nodes in the tree (internal + leaf).
std::atomic< uint64_t > &	getRoot() Gets direct access to the root node.
size_t	getParentIndex(size_t child) const Calculates parent node index for tree traversal.
std::atomic< uint64_t > &	getNode(size_t index) Direct access to any node by index.
size_t	getLeafCapacity() const Gets the number of leaf nodes in the tree.
size_t	getChildIndex(size_t parent, TreePath path) const Calculates child node index without accessing the node.
std::atomic< uint64_t > &	getChild(size_t parent, TreePath path) Gets a child node given parent index and direction.
virtual size_t	getCapacity() const override Gets the total capacity of this SignalTree.
virtual void	clear(size_t leafIndex) override Clears a signal from the tree without selecting it.
	SignalTree(size_t leafCapacity) Constructs a SignalTree with specified leaf capacity.
	SignalTree(const SignalTree & ) =delete
	SignalTree(SignalTree && ) =delete

Public Attributes

	Name
size_t	S_INVALID_SIGNAL_INDEX Returned when no signal is available.
size_t	INVALID_SIGNAL Constant for invalid signal (alias for compatibility).

Additional inherited members

Public Functions inherited from EntropyEngine::Core::Concurrency::SignalTreeBase

	Name
virtual	~SignalTreeBase() =default

Detailed Description

class EntropyEngine::Core::Concurrency::SignalTree;

A lock-free binary tree for signal selection and management.

Template Parameters:

• LeafCapacity Number of leaf nodes (must be power of 2). Total signal capacity is LeafCapacity * 64.

A signal dispatcher that can handle large numbers of signals without locks. Suitable for work-stealing schedulers, event systems, or any scenario requiring atomic signal selection and processing from multiple threads.

The key innovation is the tree structure - internal nodes track active signal counts in their subtrees, while leaf nodes pack 64 signals each into bit fields. This provides O(log n) signal selection with excellent cache coherence.

Key features:

• Lock-free: Multiple threads can set/select signals concurrently
• Cache-friendly: Entire tree lives in a contiguous array
• Scalable: Supports LeafCapacity * 64 total signals
• Fair: The bias system prevents signal starvation

// Complete multi-threaded workflow
SignalTree tree(4);  // 256 signals capacity
std::atomic<bool> running{true};

// Producer threads: submit work signals
std::thread producer([&tree]() {
    for (int i = 0; i < 100; ++i) {
        tree.set(i % 256);  // Set signal
        std::this_thread::sleep_for(1ms);
    }
});

// Consumer threads: process signals with fairness
std::thread consumer([&tree, &running]() {
    uint64_t bias = 0;
    while (running) {
        auto [index, found] = tree.select(bias);
        if (found) {
            processSignal(index);
            // Rotate bias for fairness
            bias = (bias << 1) | (bias >> 63);
        } else {
            std::this_thread::yield();
        }
    }
});

producer.join();
running = false;
consumer.join();

Public Types Documentation

enum TreePath

Enumerator	Value	Description
Right	2
Left	1

Public Functions Documentation

function signal

inline void signal(
    size_t leafIndex
)

Alias for set() - signals a contract is ready for execution.

Parameters:

• leafIndex Signal index to signal (0 to LeafCapacity*64-1)

function set

inline virtual void set(
    size_t leafIndex
) override

Sets a signal as active in the tree.

Parameters:

• leafIndex Signal index to set (0 to LeafCapacity*64-1)

Reimplements: EntropyEngine::Core::Concurrency::SignalTreeBase::set

Thread-safe and lock-free. Updates internal counters up to root.

// Worker thread marks task 42 as ready
signals.set(42);

// Multiple threads can set signals concurrently
std::thread t1([&]() { signals.set(10); });
std::thread t2([&]() { signals.set(20); });

function select

inline virtual std::pair< size_t, bool > select(
    uint64_t & biasFlags
) override

Selects and clears an active signal from the tree.

Parameters:

• biasFlags Bit pattern controlling traversal (LSB at root, shifts left)

Return: Pair of {signal_index, tree_is_empty}. signal_index is S_INVALID_SIGNAL_INDEX if none available

Reimplements: EntropyEngine::Core::Concurrency::SignalTreeBase::select

Atomically finds, clears and returns signal index. Lock-free. Bias controls fairness by guiding traversal (each bit chooses left/right at each level).

// Basic work-stealing loop with empty detection
uint64_t bias = 0;
while (running) {
    auto [signal, isEmpty] = signals.select(bias);
    if (signal != SignalTree<4>::S_INVALID_SIGNAL_INDEX) {
        processWork(signal);
        if (isEmpty) {
            // Tree is now empty, might want to steal work
        }
    } else {
        // No work available, steal from another queue
    }
    bias = rotateBias(bias);  // Ensure fairness
}

function operator=

SignalTree & operator=(
    const SignalTree &
) =delete

function operator=

SignalTree & operator=(
    SignalTree &&
) =delete

function isEmpty

inline virtual bool isEmpty() const override

Checks if the tree has no active signals.

Return: true if no signals are set

Reimplements: EntropyEngine::Core::Concurrency::SignalTreeBase::isEmpty

function getTotalNodes

inline size_t getTotalNodes() const

Gets total number of nodes in the tree (internal + leaf).

Return: Total node count (always 2*LeafCapacity - 1)

function getRoot

inline std::atomic< uint64_t > & getRoot()

Gets direct access to the root node.

Return: Reference to the atomic root node counter

Advanced use only. Root value = total active signals.

function getParentIndex

inline size_t getParentIndex(
    size_t child
) const

Calculates parent node index for tree traversal.

Parameters:

• child Index of the child node (must not be root)

Return: Index of the parent node

Formula: parent = (child - 1) / 2

function getNode

inline std::atomic< uint64_t > & getNode(
    size_t index
)

Direct access to any node by index.

Parameters:

• index Node index in the internal array

Return: Reference to the atomic node

Low-level access. Internal nodes: 0 to LeafCapacity-2, leaf nodes: rest.

function getLeafCapacity

inline size_t getLeafCapacity() const

Gets the number of leaf nodes in the tree.

Return: LeafCapacity template parameter value

function getChildIndex

inline size_t getChildIndex(
    size_t parent,
    TreePath path
) const

Calculates child node index without accessing the node.

Parameters:

• parent Index of the parent node
• path Which child (Left or Right)

Return: Index of the child node in the internal array

function getChild

inline std::atomic< uint64_t > & getChild(
    size_t parent,
    TreePath path
)

Gets a child node given parent index and direction.

Parameters:

• parent Index of the parent node
• path Which child to get (Left or Right)

Return: Reference to the child node

Internal navigation helper for tree traversal.

function getCapacity

inline virtual size_t getCapacity() const override

Gets the total capacity of this SignalTree.

Return: Maximum number of signals (LeafCapacity * 64)

Reimplements: EntropyEngine::Core::Concurrency::SignalTreeBase::getCapacity

function clear

inline virtual void clear(
    size_t leafIndex
) override

Clears a signal from the tree without selecting it.

Parameters:

• leafIndex Signal index to clear (0 to LeafCapacity*64-1)

Reimplements: EntropyEngine::Core::Concurrency::SignalTreeBase::clear

function SignalTree

inline explicit SignalTree(
    size_t leafCapacity
)

Constructs a SignalTree with specified leaf capacity.

Parameters:

• leafCapacity Number of leaf nodes (must be power of 2)

Exceptions:

• std::invalid_argument if leafCapacity is not a power of 2

function SignalTree

SignalTree(
    const SignalTree &
) =delete

function SignalTree

SignalTree(
    SignalTree &&
) =delete

Public Attributes Documentation

variable S_INVALID_SIGNAL_INDEX

static size_t S_INVALID_SIGNAL_INDEX = ~0ULL;

Returned when no signal is available.

variable INVALID_SIGNAL

static size_t INVALID_SIGNAL = S_INVALID_SIGNAL_INDEX;

Constant for invalid signal (alias for compatibility).

---

Updated on 2026-01-26 at 17:14:35 -0500