Data-DisjointSet-Shared
view release on metacpan or search on metacpan
PREINIT:
EXTRACT(self);
CODE:
if (a >= h->hdr->n)
croak("Data::DisjointSet::Shared->union: index %" UVuf " out of range (n=%u)",
a, h->hdr->n);
if (b >= h->hdr->n)
croak("Data::DisjointSet::Shared->union: index %" UVuf " out of range (n=%u)",
b, h->hdr->n);
dsu_rwlock_wrlock(h);
RETVAL = (IV)dsu_union_locked(h, (uint32_t)a, (uint32_t)b); /* 1 = newly merged, 0 = already together */
__atomic_fetch_add(&h->hdr->stat_ops, 1, __ATOMIC_RELAXED);
dsu_rwlock_wrunlock(h);
OUTPUT:
RETVAL
bool
connected(self, a, b)
SV *self
UV a
UV b
EXTRACT(self);
CODE:
if (a >= h->hdr->n)
croak("Data::DisjointSet::Shared->connected: index %" UVuf " out of range (n=%u)",
a, h->hdr->n);
if (b >= h->hdr->n)
croak("Data::DisjointSet::Shared->connected: index %" UVuf " out of range (n=%u)",
b, h->hdr->n);
/* connected compresses paths via dsu_find -> it MUTATES -> write lock. */
dsu_rwlock_wrlock(h);
RETVAL = dsu_connected_locked(h, (uint32_t)a, (uint32_t)b);
__atomic_fetch_add(&h->hdr->stat_ops, 1, __ATOMIC_RELAXED);
dsu_rwlock_wrunlock(h);
OUTPUT:
RETVAL
UV
union_many(self, pairs)
SV *self
SV *pairs
PREINIT:
Newx(vals, cnt, uint32_t); SAVEFREEPV(vals); /* freed on return OR unwind */
for (i = 0; i < cnt; i++) { /* a croak here holds NO lock; SAVEFREEPV cleans up */
SV **el = av_fetch(av, (SSize_t)i, 0);
UV v = (el && *el) ? SvUV(*el) : 0;
if (v >= n)
croak("Data::DisjointSet::Shared->union_many: index %" UVuf " out of range (n=%u)",
v, n);
vals[i] = (uint32_t)v;
}
}
dsu_rwlock_wrlock(h); /* locked region: NO croak-capable calls */
for (i = 0; i < npairs; i++)
merged += (UV)dsu_union_locked(h, vals[2*i], vals[2*i + 1]);
__atomic_fetch_add(&h->hdr->stat_ops, 1, __ATOMIC_RELAXED); /* a call always counts, even an empty batch */
dsu_rwlock_wrunlock(h);
RETVAL = merged;
}
OUTPUT:
RETVAL
UV
set_size(self, x)
SV *self
UV x
PREINIT:
EXTRACT(self);
CODE:
if (x >= h->hdr->n)
croak("Data::DisjointSet::Shared->set_size: index %" UVuf " out of range (n=%u)",
x, h->hdr->n);
/* set_size compresses paths via dsu_find -> it MUTATES -> write lock. */
dsu_rwlock_wrlock(h);
RETVAL = (UV)dsu_set_size_locked(h, (uint32_t)x);
__atomic_fetch_add(&h->hdr->stat_ops, 1, __ATOMIC_RELAXED);
dsu_rwlock_wrunlock(h);
OUTPUT:
RETVAL
UV
num_sets(self)
SV *self
PREINIT:
EXTRACT(self);
OUTPUT:
RETVAL
void
reset(self)
SV *self
PREINIT:
EXTRACT(self);
CODE:
dsu_rwlock_wrlock(h);
dsu_reset_locked(h);
__atomic_fetch_add(&h->hdr->stat_ops, 1, __ATOMIC_RELAXED);
dsu_rwlock_wrunlock(h);
SV *
stats(self)
SV *self
PREINIT:
EXTRACT(self);
CODE:
{
static inline void dsu_rwlock_spin_pause(void) {
#if defined(__x86_64__) || defined(__i386__)
__asm__ volatile("pause" ::: "memory");
#elif defined(__aarch64__)
__asm__ volatile("yield" ::: "memory");
#else
__asm__ volatile("" ::: "memory");
#endif
}
/* Extract writer PID from rwlock value (lower 31 bits when write-locked). */
#define DSU_RWLOCK_WRITER_BIT 0x80000000U
#define DSU_RWLOCK_PID_MASK 0x7FFFFFFFU
#define DSU_RWLOCK_WR(pid) (DSU_RWLOCK_WRITER_BIT | ((uint32_t)(pid) & DSU_RWLOCK_PID_MASK))
/* Check if a PID is alive. Returns 1 if alive or unknown, 0 if definitely dead. */
/* Liveness via kill(pid,0). NOTE: cannot detect PID reuse -- if a dead
* lock-holder's PID is recycled to an unrelated live process before recovery
* runs, this reports "alive" and that slot's orphaned contribution is not
* reclaimed until the recycled process exits. Robust detection would require
* a per-slot process-start-time epoch (a header-layout/version change).
if (__atomic_compare_exchange_n(lock, &cur, 1,
1, __ATOMIC_ACQUIRE, __ATOMIC_RELAXED))
return;
}
if (__builtin_expect(spin < DSU_RWLOCK_SPIN_LIMIT, 1)) {
dsu_rwlock_spin_pause();
continue;
}
dsu_park_reader(h);
cur = __atomic_load_n(lock, __ATOMIC_RELAXED);
/* Sleep when write-locked OR when yielding to waiting writers */
if (cur >= DSU_RWLOCK_WRITER_BIT || cur == 0) {
long rc = syscall(SYS_futex, lock, FUTEX_WAIT, cur,
&dsu_lock_timeout, NULL, 0);
if (rc == -1 && errno == ETIMEDOUT) {
dsu_unpark_reader(h);
dsu_recover_after_timeout(h);
spin = 0;
continue;
}
}
p[x] = p[p[x]]; /* path halving */
x = p[x];
}
return x;
}
/* Union the sets containing a and b by size (the larger-sized root wins, so
* the tree stays shallow). Returns 1 if the two were in different sets and
* are now merged, 0 if they were already in the same set. Caller holds the
* write lock; a and b are range-checked. */
static inline int dsu_union_locked(DsuHandle *h, uint32_t a, uint32_t b) {
uint32_t ra = dsu_find(h, a), rb = dsu_find(h, b);
if (ra == rb) return 0;
uint32_t *p = dsu_parent(h);
uint32_t *sz = dsu_size(h);
if (sz[ra] < sz[rb]) { uint32_t t = ra; ra = rb; rb = t; }
p[rb] = ra;
sz[ra] += sz[rb];
h->hdr->num_sets--;
return 1;
}
/* Whether a and b are in the same set (mutates via path compression). */
static inline int dsu_connected_locked(DsuHandle *h, uint32_t a, uint32_t b) {
return dsu_find(h, a) == dsu_find(h, b);
}
/* Size of the set containing x (mutates via path compression). */
static inline uint32_t dsu_set_size_locked(DsuHandle *h, uint32_t x) {
return dsu_size(h)[dsu_find(h, x)];
}
/* Reset to all singletons: parent[i]=i, size[i]=1, num_sets=n.
* Caller holds the write lock. */
static inline void dsu_reset_locked(DsuHandle *h) {
uint32_t *p = dsu_parent(h);
uint32_t *sz = dsu_size(h);
uint32_t n = h->hdr->n;
for (uint32_t i = 0; i < n; i++) { p[i] = i; sz[i] = 1; }
h->hdr->num_sets = n;
}
/* ================================================================
* Validate args + header init / setup / open / destroy
* ================================================================ */
( run in 0.330 second using v1.01-cache-2.11-cpan-bbe5e583499 )