Data-IntervalTree-Shared
view release on metacpan or search on metacpan
(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
"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 >
intervaltree.h view on Meta::CPAN
/*
* intervaltree.h -- Shared-memory interval tree for Linux
*
* A set of integer intervals [lo, hi] with fast overlap queries: which stored
* intervals contain a point (stabbing), or overlap a query range. Backed by an
* augmented balanced BST -- keyed by the low endpoint, each node carrying the
* maximum high endpoint of its subtree so a query prunes 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 stays O(log n) deep
* regardless of insertion order). The intervals and tree live in a shared
* mapping so several processes build and query one index; a write-preferring
* futex rwlock with reader-slot dead-process recovery guards mutation, and
* queries take only the read lock once the tree is built.
*
* Layout: Header -> reader_slots[1024] -> nodes[capacity] -> build_idx[capacity]
*/
intervaltree.h view on Meta::CPAN
uint32_t slotless_rdepth; /* readers holding with no reader-slot (documented residual) */
uint64_t stat_ops; /* 80 */
uint8_t sealed; /* 88 0 = mutable, 1 = frozen (read-only; lock-free reads) */
uint8_t _pad[167]; /* 89..255 */
};
typedef struct ItHeader ItHeader;
_Static_assert(sizeof(ItHeader) == 256, "ItHeader must be 256 bytes");
/* One interval node: [lo, hi] with a user payload id, plus max_hi = the maximum
* hi endpoint over this node's whole subtree (the augmentation that lets a query
* prune subtrees that cannot reach the query point/range). A balanced BST keyed
* by lo; left/right are child indices (IT_NIL for none). */
typedef struct {
int64_t lo, hi;
int64_t max_hi;
uint64_t payload;
uint32_t left, right;
} ItNode;
_Static_assert(sizeof(ItNode) == 40, "ItNode must be 40 bytes");
intervaltree.h view on Meta::CPAN
h->hdr->sealed = 1;
it_rwlock_wrunlock(h);
if (h->path || h->backing_fd >= 0) return it_msync(h);
return 0; /* anonymous: the seal lives in shared memory (visible to forks); nothing to flush */
}
/* ================================================================
* Interval-tree operations (callers hold the lock)
*
* Intervals are appended O(1) and marked dirty; a balanced BST keyed by the low
* endpoint is bulk-built on the first query after any insert (sorted once by lo,
* then median-split), so query recursion is O(log n) deep whatever the insertion
* order. Each node carries max_hi = the maximum hi endpoint over its whole
* subtree, so a query can prune a subtree whose intervals all end before it.
* Every child index read from shared memory is bounds-checked.
* ================================================================ */
/* one snapshotted matching interval, for a query result */
typedef struct { uint64_t id; int64_t lo, hi; } ItRes;
/* append an interval [lo,hi] with a payload id; returns its slot, or -1 if the
* tree is full. Marks the tree dirty so the next query rebuilds. (caller holds wrlock) */
static int64_t it_add_locked(ItHandle *h, int64_t lo, int64_t hi, uint64_t payload) {
lib/Data/IntervalTree/Shared.pm view on Meta::CPAN
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>.
lib/Data/IntervalTree/Shared.pm view on Meta::CPAN
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.
=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>.
C<overlaps> returns every stored interval that B<intersects> the closed range
t/01-basic.t view on Meta::CPAN
is $it->add(15, 25, 999), 1, 'second add returns index 1';
is $it->count, 2, 'count after adds';
# default id == insertion index
my ($first) = $it->stab(10);
is $first->{id}, 0, 'default id is the insertion index';
is $first->{lo}, 10, 'result carries lo';
is $first->{hi}, 20, 'result carries hi';
# explicit id
my %ids = map { $_->{id} => 1 } $it->stab(18); # both [10,20] and [15,25] contain 18
ok $ids{0} && $ids{999}, 'explicit id is returned';
# closed intervals: endpoints are inclusive
is scalar(my @s20 = $it->stab(20)), 2, 'hi endpoint inclusive: stab at 20 hits [10,20] and [15,25]';
is scalar(my @s15 = $it->stab(15)), 2, 'lo endpoint inclusive: stab at 15 hits [15,25] and [10,20]';
is scalar(my @s26 = $it->stab(26)), 0, 'just past every hi: no hit';
is scalar(my @s22 = $it->stab(22)), 1, 'stab at 22 hits only [15,25]';
}
# stab / overlaps vs a brute-force reference
{
my $N = 1500;
my $it = Data::IntervalTree::Shared->new(undef, $N);
srand(20260710);
my @iv; # [lo, hi, id]
t/01-basic.t view on Meta::CPAN
my $ql = int(rand 10000);
my $qh = $ql + int(rand 600);
my @g = $it->overlaps($ql, $qh);
my %got = map { $_->{id} => 1 } @g;
my @true = grep { $_->[0] <= $qh && $_->[1] >= $ql } @iv;
$obad++ if keys(%got) != @true;
$obad++ if grep { !$got{$_->[2]} } @true;
$obad++ if grep { $g[$_]{lo} < $g[$_ - 1]{lo} } 1 .. $#g; # sorted by lo?
$obad++ if grep { $_->{lo} != $iv[$_->{id}][0] || $_->{hi} != $iv[$_->{id}][1] } @g;
}
is $obad, 0, 'overlaps matches brute force, sorted by lo, correct endpoints';
# a point stab is exactly overlaps(p, p)
my $p = 5000;
my @a = sort { $a <=> $b } map { $_->{id} } $it->stab($p);
my @b = sort { $a <=> $b } map { $_->{id} } $it->overlaps($p, $p);
is_deeply \@a, \@b, 'stab($p) == overlaps($p, $p)';
}
# negative and large endpoints (signed 64-bit)
{
my $it = Data::IntervalTree::Shared->new(undef, 10);
$it->add(-1000, -500, 1);
$it->add(-600, -100, 2);
$it->add(-3_000_000_000, 3_000_000_000, 3); # spans 0, exceeds 32-bit
is_deeply [sort map { $_->{id} } $it->stab(-550)], [1, 2, 3], 'negative-point stab';
is_deeply [sort map { $_->{id} } $it->stab(0)], [3], 'stab at 0 hits the wide interval';
is_deeply [sort map { $_->{id} } $it->overlaps(-700, -550)], [1, 2, 3], 'overlaps over negatives';
my ($wide) = $it->stab(2_000_000_000);
is $wide->{lo}, -3_000_000_000, 'large negative endpoint preserved';
is $wide->{hi}, 3_000_000_000, 'large positive endpoint preserved';
}
# adding after a query rebuilds (dirty handling)
{
my $it = Data::IntervalTree::Shared->new(undef, 100);
$it->add(0, 10, 100);
is +($it->stab(5))[0]{id}, 100, 'query builds the tree';
$it->add(3, 7, 200); # marks dirty again
my %got = map { $_->{id} => 1 } $it->stab(5); # must rebuild and see both
ok $got{100} && $got{200}, 'an interval added after a query is found by the next query';
xt/fork_it.t view on Meta::CPAN
waitpid $_, 0 for @pids;
is $it->count, $cap, "count == grand total ($cap): no lost appends across children";
# exactly the $kids probe-spanning intervals contain $PROBE
my @at = $it->stab($PROBE);
is scalar(@at), $kids, "stab(probe) finds exactly one interval per child ($kids)";
my %ids = map { $_->{id} => 1 } @at;
is scalar(keys %ids), $kids, 'the probe hits are distinct (no duplicate/corrupt ids)';
ok !(grep { $_->{lo} != $PROBE - 10 || $_->{hi} != $PROBE + 10 } @at),
'each probe hit carries the correct endpoints';
done_testing;
( run in 0.726 second using v1.01-cache-2.11-cpan-16aabcbfbcb )