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 ask for 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; feeding values large enough that a range sum 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 of 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 rule dictated by the math: 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 been built with 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: version 0.02 widened the node to carry the assign tag and the gcd/product aggregates, so a segment-tree file written by 0.01 cannot be opened by 0.02 (it 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 argument is ignored. 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>. Note that range_add/add gate off the gcd/product monoids (see below), while 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 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.
SHARING ACROSS PROCESSES
The tree lives in a shared mapping, shared 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). 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 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.
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.
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.