view release on metacpan or  search on metacpan

README  view on Meta::CPAN

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

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);

DESCRIPTION
    An interval tree in shared memory: a set of integer intervals "[lo, hi]"
    that answers overlap and stabbing queries far faster than scanning every
    interval -- "which stored intervals contain point "p"?" and "which overlap
    the range "[lo, hi]"?". It complements Data::SegmentTree::Shared
    (range-aggregate over indexed positions) and Data::KDTree::Shared
    (multi-dimensional points): this one indexes a 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 "t"".

    Endpoints are signed 64-bit integers (timestamps, IP addresses, genomic
    coordinates -- exact, with no floating-point edge cases). Each interval
    carries a user-supplied 64-bit id (defaulting to its insertion index),
    returned with every match. Internally it is an 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 appended in O(1) and the balanced tree is 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, several processes
    build and query one index: any process that opens the same backing file,
    inherits the anonymous mapping across "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. Linux-only. Requires 64-bit Perl.

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

METHODS
  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

    $capacity is the maximum number of intervals (1..2^24). "new" and
    "new_memfd" croak on an out-of-range $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 sealed (frozen) file read-write is refused -- use
    "new_readonly" instead (see "FROZEN (READ-ONLY) MODE"). 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).

    "new" and "new_memfd" create a new segment sparse: pages are allocated as
    they are first written, and once the filesystem is full, an "add" or query
    that touches a page not yet allocated dies with "SIGBUS". Set
    "DATA_INTERVALTREE_SHARED_SPARSE=0" to reserve the whole segment at
    creation, so a full filesystem makes them croak instead; on tmpfs and
    memfd that commits the segment's memory at once, and a memory cgroup too
    small for it gets an OOM kill rather than a croak.

  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

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

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

    "stab" returns every stored interval that contains the point $point.
    "overlaps" returns every stored interval that intersects the closed range
    "[$lo, $hi]" (i.e. "interval.lo <= $hi" and "interval.hi >= $lo"); "$lo >
    $hi" croaks. Both return a list of hash references "{ id => ..., lo =>
    ..., hi => ... }", sorted by "lo" ascending. A point stab is exactly
    "overlaps($p, $p)".

  Introspection and lifecycle
        $it->count;         # number of intervals added
        $it->capacity;      # maximum number of intervals
        $it->clear;         # remove all intervals
        $it->stats;         # { count, capacity, dirty, ops, mmap_size, frozen, readonly }
        $it->frozen;        # 1 if sealed by freeze, else 0
        $it->readonly;      # 1 if this handle is a read-only view, else 0
        $it->path; $it->memfd; $it->sync; $it->unlink;

    "clear" empties the index. "sync" flushes the mapping to its backing store
    (a no-op for anonymous and memfd trees, and for any read-only view);
    "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. "frozen" and "readonly" report whether the tree has been
    sealed and whether this handle is a read-only view, respectively (see
    "FROZEN (READ-ONLY) MODE").

SHARING ACROSS PROCESSES
    The index 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). The descriptor you pass is duplicated
    ("F_DUPFD_CLOEXEC"), so it stays yours to close and closing it does not
    disturb the handle. Any process can add intervals; the first query after
    an add rebuilds the shared tree once (under the write lock), and
    subsequent queries run concurrently under the read lock.

FROZEN (READ-ONLY) MODE
    A file-backed tree can be frozen and then shipped to other machines, where
    consumers open it read-only and query it with no locking at all.

        # producer: build, freeze, ship the file
        my $it = Data::IntervalTree::Shared->new("/tmp/bookings.it", 100_000);
        $it->add($_->[0], $_->[1], $_->[2]) for @known;
        $it->freeze;                 # seal: now immutable, and $it itself is read-only
        # ... copy /tmp/bookings.it to another host ...

        # consumer (any process, same architecture): read-only, lock-free
        my $ro = Data::IntervalTree::Shared->new_readonly("/tmp/bookings.it");
        $ro->stab($t);                # or $ro->overlaps($lo, $hi)

    "freeze" takes the write lock, force-completes any balanced-tree build
    still pending (so a frozen tree is never left "dirty"), marks the tree
    permanently immutable (there is no unfreeze -- rebuild the file to change
    it), and flushes the seal to disk. A frozen tree rejects every mutator