view release on metacpan or  search on metacpan

lib/Data/IntervalTree/Shared.pm  view on Meta::CPAN

package Data::IntervalTree::Shared;
use strict;
use warnings;
our $VERSION = '0.02';
require XSLoader;
XSLoader::load('Data::IntervalTree::Shared', $VERSION);

sub CLONE_SKIP { 1 }  # blessed C-pointer handle: never clone into ithreads (double-free)
1;
__END__

=encoding utf-8

=head1 NAME

Data::IntervalTree::Shared - shared-memory interval tree (overlap / stabbing queries)

=head1 SYNOPSIS

    use Data::IntervalTree::Shared;

    # up to 100_000 intervals
    my $it = Data::IntervalTree::Shared->new(undef, 100_000);

    $it->add($start, $end, $booking_id) for @bookings;   # each interval carries an id

    # which intervals contain a point?
    my @at = $it->stab($t);              # e.g. "what's booked at time $t"

    # which intervals overlap a range?
    my @ov = $it->overlaps($lo, $hi);    # e.g. "any booking touching [$lo,$hi]"
    printf "id %d: [%d, %d]\n", $_->{id}, $_->{lo}, $_->{hi} for @ov;

    # share the index across processes via a backing file
    my $shared = Data::IntervalTree::Shared->new("/tmp/bookings.it", 100_000);

=head1 DESCRIPTION

An B<interval tree> in shared memory: a set of integer intervals C<[lo, hi]> that
answers B<overlap> and B<stabbing> queries far faster than scanning every
interval -- "which stored intervals contain point C<p>?" and "which overlap the
range C<[lo, hi]>?". It complements L<Data::SegmentTree::Shared> (range-aggregate
over indexed positions) and L<Data::KDTree::Shared> (multi-dimensional points):
this one indexes a B<set of intervals> for containment/overlap. Classic uses:
scheduling and calendar conflict detection, IP-range to owner lookup, genomic
feature overlap, and "what is active at time C<t>".

Endpoints are B<signed 64-bit integers> (timestamps, IP addresses, genomic
coordinates -- exact, with no floating-point edge cases). Each interval carries a
user-supplied 64-bit B<id> (defaulting to its insertion index), returned with
every match. Internally it is an B<augmented balanced binary search tree> keyed
by the low endpoint, each node caching the maximum high endpoint of its subtree
so a query prunes whole subtrees that end before it.

Intervals are B<appended in O(1)> and the balanced tree is B<bulk-built on the
first query> after any insert, so query recursion is O(log n + k) deep (k =
matches) regardless of insertion order -- no risk of a degenerate, deep tree.
Because the intervals live in a shared mapping, B<several processes build and
query one index>: any process that opens the same backing file, inherits the
anonymous mapping across C<fork>, or reopens a passed memfd sees the same
intervals. A write-preferring futex rwlock with dead-process recovery guards
mutation; once the tree is built, queries take only the read lock. B<Linux-only>.
Requires 64-bit Perl.

The index has a fixed B<capacity>; adding beyond it croaks. Memory is
C<capacity * 40> bytes for the intervals plus a build scratch of C<capacity * 4>
bytes and a fixed header.

=head1 METHODS

=head2 Constructors

    my $it = Data::IntervalTree::Shared->new($path, $capacity, $mode);
    my $it = Data::IntervalTree::Shared->new(undef, $capacity);
    my $it = Data::IntervalTree::Shared->new_memfd($name, $capacity);
    my $it = Data::IntervalTree::Shared->new_from_fd($fd);
    my $ro = Data::IntervalTree::Shared->new_readonly($path);   # frozen file, read-only

C<$capacity> is the maximum number of intervals (1..2^24). C<new> and
C<new_memfd> croak on an out-of-range C<$capacity>. When reopening an existing
file or memfd the stored geometry wins and the caller's argument does not
resize it, though it is still range-checked and an out-of-range value croaks;
reopening a B<sealed> (frozen) file read-write is refused -- use
C<new_readonly> instead (see L</"FROZEN (READ-ONLY) MODE">). An optional file
B<mode> may be passed as the last argument to C<new> (e.g. C<0660>)
for cross-user sharing; it defaults to C<0600> (owner-only).

=head2 Adding intervals

    my $i = $it->add($lo, $hi);          # id defaults to the insertion index
    my $i = $it->add($lo, $hi, $id);     # attach an explicit 64-bit id
    $it->build;                          # (optional) force a rebuild now

C<add> appends one interval with integer endpoints C<$lo E<lt>= $hi> (croaks
otherwise) and an optional integer C<$id>, returning its insertion index; it
croaks if the tree is full. Intervals are treated as B<closed> (both endpoints
inclusive). C<build> forces the balanced tree to be (re)built immediately; you
rarely need it, since queries build automatically after inserts.

=head2 Queries

    my @at = $it->stab($point);          # intervals containing $point (lo <= p <= hi)
    my @ov = $it->overlaps($lo, $hi);    # intervals overlapping [$lo, $hi]

C<stab> returns every stored interval that B<contains> the point C<$point>.