Data-RadixTree-Shared
view release on metacpan or search on metacpan
CODE:
/* Resolve key bytes BEFORE locking: SvPVbyte croaks on wide chars, and a
croak must never happen while holding the lock. */
kp = SvPVbyte(key, klen);
rdx_rwlock_wrlock(h);
if (!rdx_insert_has_room(h, (uint32_t)klen)) {
rdx_rwlock_wrunlock(h); /* release BEFORE croak */
croak("Data::RadixTree::Shared->insert: capacity exhausted "
"(node pool or label arena full; grow node/arena capacity)");
}
isnew = rdx_insert_locked(h, (const uint8_t *)kp, (uint32_t)klen, (uint64_t)value);
__atomic_fetch_add(&h->hdr->stat_ops, 1, __ATOMIC_RELAXED);
rdx_rwlock_wrunlock(h);
RETVAL = (IV)isnew;
OUTPUT:
RETVAL
SV *
lookup(self, key)
SV *self
SV *key
PREINIT:
EXTRACT(self);
STRLEN klen;
const char *kp;
uint64_t val;
int found;
CODE:
kp = SvPVbyte(key, klen); /* before the lock */
rdx_rwlock_rdlock(h);
found = rdx_lookup_locked(h, (const uint8_t *)kp, (uint32_t)klen, &val);
rdx_rwlock_rdunlock(h);
RETVAL = found ? newSVuv((UV)val) : &PL_sv_undef;
OUTPUT:
RETVAL
bool
exists(self, key)
SV *self
SV *key
PREINIT:
EXTRACT(self);
STRLEN klen;
const char *kp;
CODE:
kp = SvPVbyte(key, klen); /* before the lock */
rdx_rwlock_rdlock(h);
RETVAL = rdx_lookup_locked(h, (const uint8_t *)kp, (uint32_t)klen, NULL) ? 1 : 0;
rdx_rwlock_rdunlock(h);
OUTPUT:
RETVAL
SV *
longest_prefix(self, key)
SV *self
SV *key
PREINIT:
EXTRACT(self);
STRLEN klen;
const char *kp;
uint64_t val;
int found;
CODE:
kp = SvPVbyte(key, klen); /* before the lock */
rdx_rwlock_rdlock(h);
found = rdx_longest_prefix_locked(h, (const uint8_t *)kp, (uint32_t)klen, &val);
rdx_rwlock_rdunlock(h);
RETVAL = found ? newSVuv((UV)val) : &PL_sv_undef;
OUTPUT:
RETVAL
IV
delete(self, key)
SV *self
SV *key
PREINIT:
EXTRACT(self);
STRLEN klen;
const char *kp;
int removed;
CODE:
kp = SvPVbyte(key, klen); /* before the lock */
rdx_rwlock_wrlock(h);
removed = rdx_delete_locked(h, (const uint8_t *)kp, (uint32_t)klen);
__atomic_fetch_add(&h->hdr->stat_ops, 1, __ATOMIC_RELAXED);
rdx_rwlock_wrunlock(h);
RETVAL = (IV)removed;
OUTPUT:
RETVAL
void
clear(self)
SV *self
PREINIT:
EXTRACT(self);
CODE:
rdx_rwlock_wrlock(h);
rdx_clear_locked(h);
__atomic_fetch_add(&h->hdr->stat_ops, 1, __ATOMIC_RELAXED);
rdx_rwlock_wrunlock(h);
UV
count(self)
SV *self
PREINIT:
EXTRACT(self);
CODE:
rdx_rwlock_rdlock(h);
static inline void rdx_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 RDX_RWLOCK_WRITER_BIT 0x80000000U
#define RDX_RWLOCK_PID_MASK 0x7FFFFFFFU
#define RDX_RWLOCK_WR(pid) (RDX_RWLOCK_WRITER_BIT | ((uint32_t)(pid) & RDX_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 < RDX_RWLOCK_SPIN_LIMIT, 1)) {
rdx_rwlock_spin_pause();
continue;
}
rdx_park_reader(h);
cur = __atomic_load_n(lock, __ATOMIC_RELAXED);
/* Sleep when write-locked OR when yielding to waiting writers */
if (cur >= RDX_RWLOCK_WRITER_BIT || cur == 0) {
long rc = syscall(SYS_futex, lock, FUTEX_WAIT, cur,
&rdx_lock_timeout, NULL, 0);
if (rc == -1 && errno == ETIMEDOUT) {
rdx_unpark_reader(h);
rdx_recover_after_timeout(h);
spin = 0;
continue;
}
}
static inline uint32_t rdx_cpl(const uint8_t *a, const uint8_t *b, uint32_t max) {
uint32_t i = 0;
while (i < max && a[i] == b[i]) i++;
return i;
}
/* Insert key -> value. Returns 1 if a new key was added, 0 if an existing key
* was updated. Caller holds the write lock AND has verified rdx_insert_has_room
* (so every rdx_alloc_node / rdx_arena_append below is guaranteed to succeed,
* keeping the tree consistent -- no partial-split-on-OOM possibility). */
static inline int rdx_insert_locked(RdxHandle *h, const uint8_t *key, uint32_t klen, uint64_t value) {
RdxHeader *hdr = h->hdr;
RdxNode *nodes = rdx_nodes(h);
uint8_t *arena = rdx_arena(h);
uint32_t cur = hdr->root, kpos = 0;
for (;;) {
if (kpos == klen) { /* key ends here -> mark this node */
int isnew = !nodes[cur].has_value;
nodes[cur].has_value = 1;
nodes[cur].value = value;
if (isnew) hdr->keys++;
nodes[mid].children[key[kpos + m]] = leaf;
hdr->keys++;
return 1;
}
}
/* Navigate `key` to its terminal node. Returns the node index once the full
* key is consumed, or 0 (the NIL sentinel) if any step diverges. Read-only, so
* the caller may hold the READ or write lock. root is always >= 1, so a 0
* return is an unambiguous "not found". */
static inline uint32_t rdx_find_locked(RdxHandle *h, const uint8_t *key, uint32_t klen) {
RdxNode *nodes = rdx_nodes(h);
uint8_t *arena = rdx_arena(h);
uint32_t cur = h->hdr->root, kpos = 0;
for (;;) {
if (kpos == klen) return cur;
uint32_t ch = nodes[cur].children[key[kpos]];
if (!ch) return 0;
uint32_t llen = nodes[ch].label_len;
if (klen - kpos < llen) return 0;
if (memcmp(arena + nodes[ch].label_off, key + kpos, llen) != 0) return 0;
cur = ch;
kpos += llen;
}
}
/* Exact lookup. Returns 1 and sets *out if found, else 0. Read-only (no path
* compression) so the caller may hold the READ lock. */
static inline int rdx_lookup_locked(RdxHandle *h, const uint8_t *key, uint32_t klen, uint64_t *out) {
uint32_t n = rdx_find_locked(h, key, klen);
if (!n) return 0;
RdxNode *nodes = rdx_nodes(h);
if (nodes[n].has_value) { if (out) *out = nodes[n].value; return 1; }
return 0;
}
/* Longest-prefix match: is some stored key a prefix of `key`? Returns 1 and
* sets *out to the value of the LONGEST such stored key, else 0. Read-only. */
static inline int rdx_longest_prefix_locked(RdxHandle *h, const uint8_t *key, uint32_t klen, uint64_t *out) {
RdxNode *nodes = rdx_nodes(h);
uint8_t *arena = rdx_arena(h);
uint32_t cur = h->hdr->root, kpos = 0;
int found = 0;
if (nodes[cur].has_value) { if (out) *out = nodes[cur].value; found = 1; } /* empty key stored */
for (;;) {
if (kpos == klen) break;
uint32_t ch = nodes[cur].children[key[kpos]];
if (!ch) break;
uint32_t llen = nodes[ch].label_len;
cur = ch;
kpos += llen;
if (nodes[cur].has_value) { if (out) *out = nodes[cur].value; found = 1; }
}
return found;
}
/* Lazy delete: walk to the node; if found and has_value, clear it. Returns
* 1 if a key was removed, 0 if absent. Does NOT free nodes or compact the
* arena in v1. Caller holds the write lock. */
static inline int rdx_delete_locked(RdxHandle *h, const uint8_t *key, uint32_t klen) {
uint32_t n = rdx_find_locked(h, key, klen);
if (!n) return 0;
RdxNode *nodes = rdx_nodes(h);
if (!nodes[n].has_value) return 0;
nodes[n].has_value = 0;
nodes[n].value = 0;
h->hdr->keys--;
return 1;
}
/* Reset to a single empty root: node_used=2, arena_used=0, keys=0, and a fresh
* zeroed root. Caller holds the write lock. */
static inline void rdx_clear_locked(RdxHandle *h) {
RdxHeader *hdr = h->hdr;
RdxNode *nodes = rdx_nodes(h);
hdr->node_used = 2;
hdr->arena_used = 0;
hdr->keys = 0;
memset(&nodes[hdr->root], 0, sizeof(RdxNode)); /* zero children + has_value + label */
}
/* ================================================================
* Validate args + header init / setup / open / destroy
( run in 0.357 second using v1.01-cache-2.11-cpan-bbe5e583499 )