NAME
Data::SegmentTree::Shared - shared-memory segment tree (range add/assign, range sum/min/max/gcd/product)
SYNOPSIS
use Data::SegmentTree::Shared;
# an array of 1000 signed-integer positions, all 0
my $st = Data::SegmentTree::Shared->new(undef, 1000);
$st->set(10, 42); # position 10 := 42
$st->add(10, 5); # position 10 += 5 (now 47)
$st->range_add(0, 99, 3); # add 3 to every position in [0, 99]
$st->range_assign(0, 99, 7); # set every position in [0, 99] to 7
my $s = $st->sum(0, 99); # sum over a range
my $lo = $st->min(0, 99); # minimum over a range
my $hi = $st->max(0, 99); # maximum over a range
my $q = $st->query(0, 99); # { sum, min, max, count } in one call
my $g = $st->gcd(0, 99); # gcd over a range (assign/set-only trees)
my $p = $st->product(0, 99); # product over a range (assign/set-only trees)
# share the array across processes via a backing file
my $shared = Data::SegmentTree::Shared->new("/tmp/array.st", 1000);DESCRIPTION
A segment tree in shared memory: a fixed array of n signed 64-bit integer positions that supports range updates and range queries in O(log n) each -- add a delta to every element of a range, and query the sum, minimum, or maximum of any range. It complements Data::Fenwick::Shared (which does prefix sums and point updates): a segment tree adds range minimum and maximum queries and range add (via lazy propagation), neither of which a Fenwick tree can do.
The tree is a perfect binary tree over next_pow2(n) leaves; each node caches its subtree's sum, min, and max, plus a pending "range add" delta that is pushed down lazily. Range updates and queries therefore touch only O(log n) nodes. Positions start at 0 and are addressed by a 0-based index; out-of-range indices croak.
Because the tree lives in a shared mapping, several processes update and query one array: any process that opens the same backing file, inherits the anonymous mapping across fork, or reopens a passed memfd sees the same array. A write-preferring futex rwlock with dead-process recovery guards mutation; queries never mutate the tree, so they take only the read lock and many can run at once. Linux-only. Requires 64-bit Perl.
Values and range sums are signed 64-bit integers; a range sum that exceeds the 64-bit range overflows (wraps), as with any native integer accumulator.
Range assign and the gcd/product monoids
Alongside range_add, the tree supports range_assign -- set every position in a range to a constant in O(log n) (a second lazy tag, composed correctly with range_add). It also offers two extra range monoids, gcd and product.
These monoids come with a hard mathematical restriction: gcd and product cannot be maintained under range_add (there is no way to recover the gcd or product of {a+d, b+d, ...} from the gcd/product of {a, b, ...}). So gcd and product are exact only while the tree has seen assign/set updates only; the first range_add or add permanently gates them off (gcd/ product then croak until clear). Use $st->monoids_valid to check. Point updates via set use assign internally, so they keep the monoids valid. product additionally croaks if the product of the queried range overflows a signed 64-bit integer.
On-disk format: the on-disk layout changes between releases (0.02 widened the node to carry the assign tag and the gcd/product aggregates; 0.03 added the reader-slots lock's occupancy bitmap), so a file written by an older release is rejected on attach -- rebuild it. These trees are normally ephemeral compute structures, so this only matters if you persisted one.
METHODS
Constructors
my $st = Data::SegmentTree::Shared->new($path, $n, $mode);
my $st = Data::SegmentTree::Shared->new(undef, $n); # anonymous
my $st = Data::SegmentTree::Shared->new_memfd($name, $n);
my $st = Data::SegmentTree::Shared->new_from_fd($fd);$n is the number of positions (at least 1, up to 2^24); every position starts at 0. Memory is 2 * next_pow2(n) * 64 bytes plus a fixed header. new and new_memfd croak on a $n below 1 or above 2^24. When reopening an existing file or memfd the stored $n wins and the caller's arguments do not resize it -- but they are still range-checked, so an out-of-range value croaks. An optional file mode may be passed as the last argument to new (e.g. 0660) for cross-user sharing; it defaults to 0600 (owner-only).
Updates
$st->set($i, $value); # position $i := $value
my $new = $st->add($i, $delta); # position $i += $delta; returns the new value
$st->range_add($l, $r, $delta); # add $delta to every position in [$l, $r]
$st->range_assign($l, $r, $value); # set every position in [$l, $r] to $valueset assigns a single position; add adds a delta to a single position and returns its new value; range_add adds a delta to every position in the inclusive range [$l, $r], and range_assign sets every position in the range to a constant -- each in O(log n) via lazy propagation. All indices are 0-based and croak if out of range; the range forms croak if $l $r>. range_add/add gate off the gcd/product monoids (see below); set/ range_assign do not.
Queries
my $v = $st->get($i); # value at position $i
my $s = $st->sum($l, $r); # sum over [$l, $r]
my $lo = $st->min($l, $r); # minimum over [$l, $r]
my $hi = $st->max($l, $r); # maximum over [$l, $r]
my $q = $st->query($l, $r); # { sum, min, max, count } in one locked call
my $g = $st->gcd($l, $r); # gcd over [$l, $r] (assign/set-only trees)
my $p = $st->product($l, $r); # product over [$l, $r] (assign/set-only trees)get returns a single position's value. sum, min, and max return one aggregate over the inclusive range [$l, $r]. query returns all of them at once as a hash reference { sum, min, max, count } (count is $r - $l + 1), computed under a single read lock so the four values are mutually consistent. gcd returns the greatest common divisor of |values| over the range (0 for an all-zero range), and product returns their product; both require an assign/set-only tree and croak once any range_add/add has run (see "Range assign and the gcd/product monoids"), and product also croaks on 64-bit overflow. Ranges croak if an index is out of range or $l $r>.
Introspection and lifecycle
$st->size; # n, the number of positions
$st->monoids_valid; # true if gcd/product are still usable (no range_add yet)
$st->clear; # reset every position to 0
$st->stats; # { n, size, tree_size, ops, mmap_size }
$st->path; $st->memfd; $st->sync; $st->unlink;monoids_valid reports whether gcd/product are currently usable (false once a range_add/add has gated them off). clear resets every position to 0 and re-enables the monoids. sync flushes the mapping to its backing store (a no-op for anonymous and memfd trees); unlink removes the backing file (also callable as Class->unlink($path)); path returns the backing path (undef for anonymous, memfd, or fd-reopened trees) and memfd the backing descriptor. The descriptor memfd returns is owned by the object and closed when the object is destroyed; do not close it yourself. Pass it to another process (or new_from_fd) while the object is still alive.
SHARING ACROSS PROCESSES
The tree lives in a shared mapping, exposed the same three ways as the rest of the family: a backing file, an anonymous mapping inherited across fork, or a memfd passed to an unrelated process and reopened with new_from_fd($fd). The descriptor you pass is duplicated (F_DUPFD_CLOEXEC), so it stays yours to close and closing it does not disturb the handle. Every process's updates land in the one shared array, and queries take only the read lock so many readers proceed concurrently.
SECURITY
Backing files are created with mode 0600 (owner-only) by default; pass an explicit octal mode (e.g. 0660) as the last argument to new for cross-user sharing (the mode is masked to the permission bits 0777). The file is opened with O_NOFOLLOW and O_EXCL, and the header is validated on attach. Any process granted write access is trusted not to corrupt the mapping.
A descriptor passed to new_from_fd must be resize-sealed (a memfd sealed against F_SEAL_SHRINK|F_SEAL_GROW, as new_memfd produces) or come from a trusted owner: a hostile donor that truncates the fd after it is mapped can fault the reader with SIGBUS on a later access. new_from_fd rejects a sealable fd that lacks both resize seals; a non-sealable fd (e.g. a regular file) cannot carry seals and is accepted on the caller's trust.
CRASH SAFETY
Mutation is guarded by a futex-based write-preferring rwlock with PID-encoded ownership and dead-owner recovery. Dead-owner recovery restores lock availability only. Each mutation is a multi-store O(log n) tree walk with no commit protocol, so a writer killed mid-update leaves that update partially applied: the tree can be left internally inconsistent (a later query may disagree with the individual get values), and recovery neither detects nor repairs the torn update. Treat a crash during a mutation as leaving the tree in an undefined state, and rebuild from a trusted source if you need consistency across crashes. Limitation: PID reuse is not detected (very unlikely in practice).
Reader-slot exhaustion (slotless readers): dead-process recovery attributes a crashed lock holder's contribution through its reader-slot. The slot table holds 1024 entries (one per concurrent reader process). If more than that many reader processes share one mapping at once, a reader that cannot claim a slot proceeds "slotless" -- it still takes the read lock but leaves no per-process record. If such a slotless reader is then killed while holding the read lock, its share of the lock cannot be attributed to a dead process, so writer recovery cannot reclaim it and writers may block until the mapping is recreated. Reaching this needs more than 1024 concurrent reader processes on one mapping plus a crash in the brief read-lock window; the dead-process slot reclaim keeps the table from filling with stale entries, so in practice it is very unlikely.
An interrupted create is recovered too. A creator killed after the backing file is sized but before its header is committed leaves a full-size, all-zero file. new re-initializes such a file automatically, but only when it is exactly the size the requested geometry needs, is owned by your effective uid, and is still entirely zero -- a file holding data is never re-initialized. If the creator got as far as writing part of the header, the file cannot be told apart from a corrupt one and new croaks with incomplete segment-tree file left by an interrupted create; remove it and retry. A file left behind by an interrupted create never held data, so removing it is safe -- but a file whose header was corrupted after the fact reaches the same croak, so confirm it is an abandoned create before deleting anything you care about.
SEE ALSO
Data::Fenwick::Shared (prefix sums / point updates), and the rest of the Data::*::Shared family.
AUTHOR
vividsnow
LICENSE
This is free software; you can redistribute it and/or modify it under the same terms as Perl itself.