NAME
Data::Fenwick2D::Shared - shared-memory 2-D Fenwick tree (binary indexed tree) for Linux
SYNOPSIS
use Data::Fenwick2D::Shared;
# a rows x cols grid of signed 64-bit integers, all 0
my $grid = Data::Fenwick2D::Shared->new(undef, 24, 7);
$grid->update(9, 1, 12); # add 12 at cell (row 9, col 1)
$grid->update(22, 5, 30); # add 30 at cell (22, 5)
$grid->point(22, 5); # 30 (value at a single cell)
$grid->prefix(12, 5); # sum over the rectangle [1..12] x [1..5]
$grid->rect(8, 1, 12, 5); # sum over [8..12] x [1..5]
$grid->total; # sum over the whole grid
$grid->set(9, 1, 100); # set cell (9,1) to 100 (returns the old value)
# share the grid across processes via a backing file
my $shared = Data::Fenwick2D::Shared->new("/tmp/heatmap.f2d", 24, 7);DESCRIPTION
A 2-D Fenwick tree (binary indexed tree) in shared memory: a fixed rows x cols grid of signed 64-bit integers that supports point update and rectangle-sum query in O(log rows * log cols) each. It is the compact, update-friendly structure behind 2-D cumulative-frequency tables, running heatmaps, and image / grid area-sum queries -- the two-dimensional companion to Data::Fenwick::Shared.
Cells are addressed by a 1-based (row, col) pair, 1..rows by 1..cols. update($x, $y, $delta) adds a (possibly negative) delta at a cell; prefix($x, $y) returns the sum of the rectangle from the origin, [1..$x] x [1..$y]; rect($x1, $y1, $x2, $y2) the sum of any axis-aligned rectangle (via inclusion-exclusion of four prefix queries); point($x, $y) a single cell's value; and total the sum of the whole grid. set overwrites a cell with an absolute value.
The grid lives in a shared mapping, so several processes update and query one grid: any process that opens the same backing file, inherits the anonymous mapping across fork, or reopens a passed memfd sees the others' updates and contributes its own. A write-preferring futex rwlock with dead-process recovery guards mutation, so many processes may update and query concurrently; queries take only the read lock.
Values and rectangle sums are signed 64-bit integers; sums that overflow 64 bits wrap, as with any native integer accumulator. Memory is (rows+1) * (cols+1) * 8 bytes for the grid plus a fixed header. Linux-only. Requires 64-bit Perl.
METHODS
Constructors
my $grid = Data::Fenwick2D::Shared->new($path, $rows, $cols);
my $grid = Data::Fenwick2D::Shared->new(undef, $rows, $cols); # anonymous
my $grid = Data::Fenwick2D::Shared->new_memfd($name, $rows, $cols);
my $grid = Data::Fenwick2D::Shared->new_from_fd($fd);$rows and $cols are the grid dimensions (each at least 1, up to 2^24); cells are then addressed as (1..$rows, 1..$cols). Every cell starts at 0. new and new_memfd croak if a dimension is below 1 or above the cap. When reopening an existing file or memfd the stored dimensions win and the caller's arguments are ignored. An optional file mode may be passed as the last argument to new (e.g. 0660) to opt a newly-created backing file into cross-user sharing; it defaults to 0600 (owner-only).
Updating
$grid->update($x, $y, $delta); # add $delta at cell ($x, $y)
my $old = $grid->set($x, $y, $value); # set cell ($x, $y) to $value; returns the old value
$grid->clear; # reset every cell to 0update adds a signed delta at a single cell. set overwrites a cell with an absolute value and returns its previous value (it is update($x, $y, $value - point($x, $y)) done atomically under one lock). Both croak if ($x, $y) is outside (1..rows, 1..cols). clear zeroes the grid.
Querying
my $v = $grid->point($x, $y); # value at a single cell
my $s = $grid->prefix($x, $y); # sum over [1..$x] x [1..$y] (origin rectangle)
my $s = $grid->rect($x1, $y1, $x2, $y2); # sum over [$x1..$x2] x [$y1..$y2]
my $t = $grid->total; # sum over the whole gridprefix returns the cumulative sum of the rectangle anchored at the origin; either coordinate may be 0 (an empty rectangle, sum 0). rect returns the sum of any inclusive axis-aligned rectangle, computed from four prefix queries by inclusion-exclusion; it croaks unless 1 <= $x1 <= $x2 <= rows and 1 <= $y1 <= $y2 <= cols. point is the 1x1 rectangle at a cell. total is prefix(rows, cols). Every query takes only the read lock, so many run concurrently.
Introspection and lifecycle
$grid->rows; $grid->cols; # the grid dimensions
$grid->stats; # { rows, cols, total, ops, mmap_size }
$grid->path; $grid->memfd; $grid->sync; $grid->unlink;stats returns a hash reference with the dimensions, the current grand total, the running count of write-path operations, and the mapping size. sync flushes the mapping to its backing store (a no-op for anonymous and memfd grids); unlink removes the backing file (also callable as Class->unlink($path)); path returns the backing path (undef for anonymous, memfd, or fd-reopened grids) and memfd the backing descriptor.
SHARING ACROSS PROCESSES
The grid 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 grid, 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. Each update is a short bounded O(log rows * log cols) walk, so a crash leaves the grid consistent up to the last completed operation. 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 (the 1-D Fenwick tree: prefix sums, point/range update, weighted lookup), 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.