dicrg.hpp

namespace rg

Functions

bool is_valid_point(const int ss_x, const int ss_y, const subset::Grid &ss_grid)
Parameters:

  • x –

  • y –

  • px_hori –

  • px_vert –

  • ss_size –

Returns:

true

Returns:

false

bool check_convergence(const int x, const int y, const OptResult &res, std::string &msg, bool direct_neigh = false)
struct Point

Public Functions

inline Point(int _idx, double _val)
inline bool operator<(const Point &other) const

Public Members

int idx
double val
struct QueueGlobal : public rg::QueuePolicy

Public Functions

inline explicit QueueGlobal(const int num_threads)
virtual bool pop(const int tid, rg::Point &out)

Retrieves the next point from a global priority queue.

Coordinates multiple threads to pop the highest-priority point. If the queue is empty, threads will wait as long as other threads are still active (processing points that might add new neighbours to the queue).

Parameters:

  • tid – Thread ID.

  • out – Populated with the next point if found.

Returns:

True if a point was retrieved, false if the queue is empty and all threads are idle.

virtual void push(const int tid, const std::vector<rg::Point> &points)

Pushes multiple points to the global priority queue in a thread-safe manner.

Parameters:

  • tid – Thread ID.

  • points – Vector of points to add.

Public Members

std::priority_queue<rg::Point> q
std::mutex m
std::atomic<int> active_threads
struct QueueLocal : public rg::QueuePolicy

Public Functions

inline explicit QueueLocal(const int num_threads)
virtual bool pop(const int tid, rg::Point &current)

Retrieves the next point for a thread to process, blocking briefly if queues are empty.

First tries the calling thread’s own queue via try_pop_own_q(). If empty, repeatedly attempts to steal from other threads via try_steal_from_other_q() up to a fixed number of idle iterations, sleeping 1ms between attempts.

Parameters:

  • tid – Thread ID.

  • current – Populated with the next point to process if one is found.

Returns:

True if a point was retrieved, false if all queues remained empty after exhausting idle iterations.

virtual void push(const int tid, const std::vector<rg::Point> &points)

Pushes multiple points to a local threads priority queue in a thread-safe manner.

Parameters:

  • tid – Thread ID.

  • points – neighbours to add.

Public Members

std::vector<std::priority_queue<rg::Point>> qs
std::vector<std::mutex> locks
std::mutex steal_lock

Private Functions

bool try_steal_from_other_q(const int tid, rg::Point &out)

Attempts to steal the highest-priority point from any other thread’s queue.

Iterates over all queues and pops from the first non-empty one found. The global steal_mtx is held for the duration to prevent two threads from stealing simultaneously.

Parameters:

  • tid – Thread ID.

  • out – Populated with the stolen point if successful.

Returns:

True if a point was stolen, false if all queues were empty.

bool try_pop_own_q(const int tid, rg::Point &out)

Attempts to pop the highest-priority point from a thread’s own queue.

Parameters:

  • tid – Thread ID.

  • out – Populated with the popped point if successful.

Returns:

True if a point was popped, false if the queue was empty.

struct QueuePolicy

Subclassed by rg::QueueGlobal, rg::QueueLocal

Public Functions

virtual bool pop(const int tid, rg::Point &out) = 0
virtual void push(const int tid, const std::vector<rg::Point> &points) = 0
virtual ~QueuePolicy() = default