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 $value "set" 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.