Data-SpatialHash-Shared
view release on metacpan or search on metacpan
t/version_check.t
xt/asan.t
xt/cloexec_exec.t
xt/concurrent_open.t
xt/crash_recovery.t
xt/dead_reader_recovery.t
xt/eg_runs.t
xt/fd_leak.t
xt/fd_validation.t
xt/fork_live.t
xt/fork_locked.t
xt/invalid_args.t
xt/kwalitee.t
xt/manifest_vs_git.t
xt/memfd_seal.t
xt/memfd_xproc.t
xt/mmap_leak.t
xt/mpmc_fuzz.t
xt/perf.t
xt/pod.t
xt/pool_exhaustion.t
uint32_t idx;
CODE:
/* (x,y,value)=4 2D ; (x,y,z,value)=5 3D ; (x,y,z,value,radius)=6 3D+radius */
z = 0; radius = 0;
if (items == 4) { val = (int64_t)SvIV(ST(3)); }
else if (items == 5) { z = (double)SvNV(ST(3)); val = (int64_t)SvIV(ST(4)); }
else if (items == 6) { z = (double)SvNV(ST(3)); val = (int64_t)SvIV(ST(4)); radius = (double)SvNV(ST(5)); }
else croak("insert: expected (x,y,value), (x,y,z,value), or (x,y,z,value,radius)");
if (radius < 0 || !isfinite(radius)) croak("insert: radius must be a finite number >= 0");
sph_rwlock_wrlock(h);
idx = sph_insert_locked(h, x, y, z, val, radius);
__atomic_fetch_add(&h->hdr->stat_ops, 1, __ATOMIC_RELAXED);
sph_rwlock_wrunlock(h);
RETVAL = (idx == SPH_NONE) ? &PL_sv_undef : newSVuv(idx);
OUTPUT:
RETVAL
bool
move(self, handle, x, y, ...)
SV *self
UV handle
NV x
NV y
PREINIT:
EXTRACT(self);
double z;
CODE:
z = 0;
if (items == 5) z = (double)SvNV(ST(4));
else if (items != 4) croak("move: expected (handle,x,y) or (handle,x,y,z)");
sph_rwlock_wrlock(h);
RETVAL = sph_move_locked(h, (uint32_t)handle, x, y, z);
__atomic_fetch_add(&h->hdr->stat_ops, 1, __ATOMIC_RELAXED);
sph_rwlock_wrunlock(h);
OUTPUT:
RETVAL
bool
remove(self, handle)
SV *self
UV handle
PREINIT:
EXTRACT(self);
CODE:
sph_rwlock_wrlock(h);
RETVAL = sph_remove_locked(h, (uint32_t)handle);
__atomic_fetch_add(&h->hdr->stat_ops, 1, __ATOMIC_RELAXED);
sph_rwlock_wrunlock(h);
OUTPUT:
RETVAL
bool
has(self, handle)
SV *self
UV handle
PREINIT:
sph_rwlock_wrlock(h);
for (SSize_t i = 0; i < nr; i++) {
SV **rv = av_fetch(av, i, 0);
if (!rv || !SvROK(*rv) || SvTYPE(SvRV(*rv)) != SVt_PVAV) continue;
AV *row = (AV *)SvRV(*rv);
SSize_t rl = av_len(row) + 1;
if (rl != 3 && rl != 4) continue;
SV **hp = av_fetch(row, 0, 0), **xp = av_fetch(row, 1, 0), **yp = av_fetch(row, 2, 0);
SV **zp = (rl == 4) ? av_fetch(row, 3, 0) : NULL;
if (!hp || !xp || !yp) continue;
if (sph_move_locked(h, (uint32_t)SvUV(*hp), SvNV(*xp), SvNV(*yp), zp ? SvNV(*zp) : 0.0)) moved++;
}
if (nr > 0) __atomic_fetch_add(&h->hdr->stat_ops, (uint64_t)nr, __ATOMIC_RELAXED);
sph_rwlock_wrunlock(h);
}
RETVAL = moved;
OUTPUT:
RETVAL
void
insert_many(self, rows)
AV *row = (AV *)SvRV(*rv);
SSize_t rl = av_len(row) + 1;
if (rl == 3 || rl == 4) {
SV **xp = av_fetch(row, 0, 0), **yp = av_fetch(row, 1, 0), **vp = av_fetch(row, 2, 0);
SV **rp = (rl == 4) ? av_fetch(row, 3, 0) : NULL;
if (xp && yp && vp) {
double rad = rp ? SvNV(*rp) : 0.0;
/* skip a row with a bad radius (-> undef handle), like other
malformed rows; can't croak here -- we hold the write lock */
if (rad >= 0 && isfinite(rad))
idx = sph_insert_locked(h, SvNV(*xp), SvNV(*yp), 0.0,
(int64_t)SvIV(*vp), rad);
}
}
}
PUSHs(idx == SPH_NONE ? &PL_sv_undef : sv_2mortal(newSVuv(idx)));
}
if (nr > 0) __atomic_fetch_add(&h->hdr->stat_ops, (uint64_t)nr, __ATOMIC_RELAXED);
sph_rwlock_wrunlock(h);
}
NV alt
IV value
PREINIT:
EXTRACT(self);
double xyz[3];
uint32_t idx;
CODE:
if (!(h->hdr->sphere_radius > 0.0)) croak("insert_geo: map was not created with sphere => R");
sph_geo_to_xyz(h->hdr->sphere_radius, lat, lon, alt, xyz);
sph_rwlock_wrlock(h);
idx = sph_insert_locked(h, xyz[0], xyz[1], xyz[2], (int64_t)value, 0.0);
__atomic_fetch_add(&h->hdr->stat_ops, 1, __ATOMIC_RELAXED);
sph_rwlock_wrunlock(h);
RETVAL = (idx == SPH_NONE) ? &PL_sv_undef : newSVuv(idx);
OUTPUT:
RETVAL
bool
move_geo(self, handle, lat, lon, alt)
SV *self
UV handle
NV lat
NV lon
NV alt
PREINIT:
EXTRACT(self);
double xyz[3];
CODE:
if (!(h->hdr->sphere_radius > 0.0)) croak("move_geo: map was not created with sphere => R");
sph_geo_to_xyz(h->hdr->sphere_radius, lat, lon, alt, xyz);
sph_rwlock_wrlock(h);
RETVAL = sph_move_locked(h, (uint32_t)handle, xyz[0], xyz[1], xyz[2]);
__atomic_fetch_add(&h->hdr->stat_ops, 1, __ATOMIC_RELAXED);
sph_rwlock_wrunlock(h);
OUTPUT:
RETVAL
void
position_geo(self, handle)
SV *self
UV handle
PREINIT:
PPCODE:
if (!SvROK(cb) || SvTYPE(SvRV(cb)) != SVt_PVCV) croak("each_colliding_pair: arg must be a coderef");
EMIT_PAIRS(sph_pairs(h, -1.0, sph_pair_to_collect, &col));
void clear(self)
SV *self
PREINIT:
EXTRACT(self);
CODE:
sph_rwlock_wrlock(h);
sph_clear_locked(h);
__atomic_fetch_add(&h->hdr->stat_ops, 1, __ATOMIC_RELAXED);
sph_rwlock_wrunlock(h);
SV *stats(self)
SV *self
PREINIT:
EXTRACT(self);
CODE:
sph_rwlock_rdlock(h);
uint32_t occ, mx, mxcell; sph_chain_stats(h, &occ, &mx, &mxcell);
static inline void sph_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 SPH_RWLOCK_WRITER_BIT 0x80000000U
#define SPH_RWLOCK_PID_MASK 0x7FFFFFFFU
#define SPH_RWLOCK_WR(pid) (SPH_RWLOCK_WRITER_BIT | ((uint32_t)(pid) & SPH_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 < SPH_RWLOCK_SPIN_LIMIT, 1)) {
sph_rwlock_spin_pause();
continue;
}
sph_park_reader(h);
cur = __atomic_load_n(lock, __ATOMIC_RELAXED);
/* Sleep when write-locked OR when yielding to waiting writers */
if (cur >= SPH_RWLOCK_WRITER_BIT || cur == 0) {
long rc = syscall(SYS_futex, lock, FUTEX_WAIT, cur,
&sph_lock_timeout, NULL, 0);
if (rc == -1 && errno == ETIMEDOUT) {
sph_unpark_reader(h);
sph_recover_after_timeout(h);
spin = 0;
continue;
}
}
uint32_t b = sph_bucket_of_cell(h, cell);
uint32_t p = h->entries[idx].prev, n = h->entries[idx].next;
if (p != SPH_NONE) h->entries[p].next = n; else h->buckets[b] = n;
if (n != SPH_NONE) h->entries[n].prev = p;
}
/* ================================================================
* Mutation ops (callers hold write lock)
* ================================================================ */
static inline uint32_t sph_insert_locked(SpatialHandle *h, double x, double y, double z,
int64_t value, double radius) {
uint32_t idx = sph_alloc_slot(h);
if (idx == SPH_NONE) return SPH_NONE;
h->entries[idx].pos[0] = x; h->entries[idx].pos[1] = y; h->entries[idx].pos[2] = z;
h->entries[idx].value = value;
h->entries[idx].radius = radius;
sph_bucket_link(h, idx);
h->hdr->count++;
return idx;
}
static inline int sph_remove_locked(SpatialHandle *h, uint32_t idx) {
if (!sph_is_live(h, idx)) return 0;
sph_bucket_unlink(h, idx);
sph_free_slot(h, idx);
h->hdr->count--;
return 1;
}
static inline int sph_move_locked(SpatialHandle *h, uint32_t idx, double x, double y, double z) {
if (!sph_is_live(h, idx)) return 0;
int64_t oc[3], nc[3];
sph_cell_of(h, h->entries[idx].pos, oc);
double np[3] = { x, y, z }; sph_cell_of(h, np, nc);
if (sph_cell_eq(oc, nc)) { /* same cell: just rewrite pos */
h->entries[idx].pos[0] = x; h->entries[idx].pos[1] = y; h->entries[idx].pos[2] = z;
return 1;
}
sph_bucket_unlink(h, idx); /* unlink uses OLD pos */
h->entries[idx].pos[0] = x; h->entries[idx].pos[1] = y; h->entries[idx].pos[2] = z;
}
}
}
return SPH_Q_OK;
}
/* ================================================================
* Lifecycle helpers: clear, chain stats
* ================================================================ */
static void sph_clear_locked(SpatialHandle *h) {
uint32_t me = h->hdr->max_entries, nb = h->hdr->num_buckets;
for (uint32_t b = 0; b < nb; b++) h->buckets[b] = SPH_NONE;
memset(h->bitmap, 0, (size_t)h->bitmap_words * sizeof(uint64_t));
for (uint32_t i = 0; i < me; i++) h->entries[i].next = (i+1 < me) ? i+1 : SPH_NONE;
h->hdr->free_head = 0; /* max_entries >= 1 (validated at create) */
h->hdr->count = 0;
}
static void sph_chain_stats(SpatialHandle *h, uint32_t *occupied, uint32_t *max_chain,
uint32_t *max_cell) {
uint32_t occ = 0, mx = 0, mxc = 0, nb = h->hdr->num_buckets;
( run in 0.657 second using v1.01-cache-2.11-cpan-bbe5e583499 )