NAME
    Data::KDTree::Shared - shared-memory k-d tree (nearest-neighbour + range
    search)

SYNOPSIS
        use Data::KDTree::Shared;

        # up to 100_000 points in 2 dimensions
        my $kd = Data::KDTree::Shared->new(undef, 2, 100_000);

        $kd->add([$lon, $lat], $city_id) for @cities;   # each point carries an id

        my $near = $kd->nearest([$x, $y]);          # { id => ..., dist => ... }
        my @k5   = $kd->knn([$x, $y], 5);           # 5 nearest, closest first
        my @box  = $kd->range([$x0, $y0], [$x1, $y1]); # ids inside a bounding box
        my @ball = $kd->radius([$x, $y], 3.0);      # points within distance 3

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

DESCRIPTION
    A k-d tree in shared memory: a spatial index over points in up to 16
    dimensions that answers nearest-neighbour, k-nearest, bounding-box, and
    radius queries far faster than scanning every point. It complements
    Data::SpatialHash::Shared (a uniform grid, ideal for fixed-radius
    proximity): a k-d tree adapts to the point density and answers exact
    k-NN and arbitrary-box queries.

    Points are appended in O(1) and each carries a user-supplied 64-bit id
    (defaulting to its insertion index). To keep queries fast regardless of
    insertion order, the tree is bulk-built balanced (median split on a
    cycling axis) the first time it is queried after any insert, so query
    recursion is O(log n) deep -- there is no risk of a degenerate, deep
    tree from sorted inserts.

    Because the points 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 points. A write-preferring futex rwlock with dead-process recovery
    guards mutation; once the tree is built, queries take only the read
    lock, so many run concurrently. Coordinates are "double"; a non-finite
    coordinate croaks. Linux-only. Requires 64-bit Perl.

    The index has a fixed capacity; adding beyond it croaks. Memory is
    "capacity * (dims * 8 + 16)" bytes for the points plus a build scratch
    of "capacity * 4" bytes and a fixed header.

METHODS
  Constructors
        my $kd = Data::KDTree::Shared->new($path, $dims, $capacity, $mode);
        my $kd = Data::KDTree::Shared->new(undef, $dims, $capacity);
        my $kd = Data::KDTree::Shared->new_memfd($name, $dims, $capacity);
        my $kd = Data::KDTree::Shared->new_from_fd($fd);

    $dims is the number of dimensions (1..16) and $capacity the maximum
    number of points (1..2^24). "new" and "new_memfd" croak on an
    out-of-range $dims or $capacity. When reopening an existing file or
    memfd the stored geometry wins and the caller's arguments are 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).

  Adding points
        my $i = $kd->add(\@coords);          # id defaults to the insertion index
        my $i = $kd->add(\@coords, $id);     # attach an explicit 64-bit id
        $kd->build;                          # (optional) force a rebuild now

    "add" appends one point (an array reference of exactly $dims finite
    coordinates) with an optional integer $id and returns its insertion
    index; it croaks if the tree is full or a coordinate is missing or
    non-finite. "build" forces the balanced tree to be (re)built
    immediately; you rarely need it, since queries build automatically after
    inserts.

  Queries
        my $near  = $kd->nearest(\@point);       # { id, dist } or undef if empty
        my @knn   = $kd->knn(\@point, $m);       # up to $m nearest, closest first
        my @ids   = $kd->range(\@lo, \@hi);      # ids whose coords lie in [lo, hi] per axis
        my @ball  = $kd->radius(\@point, $r);    # { id, dist } within Euclidean distance $r

    "nearest" returns the single closest point as "{ id => ..., dist => ...
    }" (Euclidean distance), or "undef" if the index is empty. "knn" returns
    up to $m such hash references sorted by increasing distance. "range"
    returns a plain list of the ids of every point inside the axis-aligned
    box with corners "\@lo" and "\@hi" (order unspecified). "radius" returns
    "{ id, dist }" hash references for every point within Euclidean distance
    $r, closest first. All query points and box corners are array references
    of exactly $dims finite coordinates.

  Introspection and lifecycle
        $kd->count;         # number of points added
        $kd->capacity;      # maximum number of points
        $kd->dims;          # number of dimensions
        $kd->clear;         # remove all points
        $kd->stats;         # { count, dims, capacity, dirty, ops, mmap_size }
        $kd->path; $kd->memfd; $kd->sync; $kd->unlink;

    "clear" empties the index. "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 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). Any process can add points; the first query after
    an add rebuilds the shared tree once (under the write lock), and
    subsequent queries run concurrently under the read lock.

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. Adds are short bounded
    appends and the bulk build runs entirely under the write lock, so a
    crash leaves the index consistent up to the last completed operation (a
    crash mid-build simply leaves it marked for rebuild). 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::SpatialHash::Shared (uniform-grid proximity), 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.

