/ 
Data-Heap-Shared-0.07
/ Data::Heap::Shared

NAME

Data::Heap::Shared - Shared-memory binary min-heap (priority queue) for Linux

SYNOPSIS

use Data::Heap::Shared;

my $heap = Data::Heap::Shared->new(undef, 1000);
$heap->push(3, 300);   # priority=3, value=300
$heap->push(1, 100);
$heap->push(2, 200);

my ($pri, $val) = $heap->pop;   # (1, 100) -- lowest priority first
my ($pri, $val) = $heap->peek;  # (2, 200) -- without removing

# blocking pop
my ($pri, $val) = $heap->pop_wait(5.0);

DESCRIPTION

Binary min-heap in shared memory. Elements are (priority, value) integer pairs. Lowest priority pops first.

Mutex-protected push/pop with sift-up/sift-down. PID-based stale mutex recovery. Futex blocking when empty.

Crash safety: if a process dies while holding the heap mutex (mid-push or mid-pop), the mutex is recovered via PID detection, but the heap data may be in an inconsistent state (partially sifted). Callers should clear and rebuild if crash recovery is triggered in a critical application.

Linux-only. Requires 64-bit Perl.

CONSTRUCTORS

new

my $heap = Data::Heap::Shared->new($path, $capacity);
my $heap = Data::Heap::Shared->new($path, $capacity, $mode);
my $heap = Data::Heap::Shared->new(undef, $capacity);

Create or attach a heap. $capacity is the maximum number of elements. If $path is a defined filename, the heap is backed by that file (created if absent, attached if present). If $path is undef, an anonymous mapping is used -- it has no backing file but is MAP_SHARED, so it is inherited across fork and shared with child processes (an unrelated process simply cannot attach it).

The optional $mode is an octal permission mask applied only when the backing file is created; it defaults to 0600 (owner-only). See "SECURITY".

Croaks on error (bad capacity, permission denied, header mismatch, etc.).

new_memfd

my $heap = Data::Heap::Shared->new_memfd($name, $capacity);

Create an anonymous heap backed by a Linux memfd. $name is a label for debugging (as shown in /proc). The underlying file descriptor can be retrieved with "memfd" and passed to another process (e.g. over a unix socket or by inheritance) which attaches with "new_from_fd". Croaks on error.

new_from_fd

my $heap = Data::Heap::Shared->new_from_fd($fd);

Attach to an existing heap given an open file descriptor for its backing store (typically obtained from "memfd" in another process). The header is validated on attach. Croaks on error.

METHODS

push

my $ok = $heap->push($priority, $value);

Insert a ($priority, $value) integer pair. Returns true on success, or false if the heap is full (see "is_full"). Wakes one blocked "pop_wait" waiter.

pop

my ($pri, $val) = $heap->pop;

Remove and return the lowest-priority element as a ($priority, $value) pair. Returns the empty list if the heap is empty.

pop_wait

my ($pri, $val) = $heap->pop_wait;         # block forever
my ($pri, $val) = $heap->pop_wait($secs);  # block up to $secs
my ($pri, $val) = $heap->pop_wait(0);      # non-blocking

Like "pop", but blocks (via futex) until an element is available. With no argument (or a negative timeout) it blocks indefinitely. A timeout of 0 polls without blocking. A positive fractional $secs bounds the wait; on timeout the empty list is returned.

peek

my ($pri, $val) = $heap->peek;

Return the lowest-priority element without removing it. Returns the empty list if the heap is empty.

size

my $n = $heap->size;

Current number of elements.

capacity

my $cap = $heap->capacity;

Maximum number of elements (fixed at creation).

is_empty

my $bool = $heap->is_empty;

True if size == 0.

is_full

my $bool = $heap->is_full;

True if size >= capacity.

clear

$heap->clear;

Remove all elements (resets size to zero).

path

my $p = $heap->path;

The backing file path, or undef for anonymous / memfd heaps.

memfd

my $fd = $heap->memfd;

The backing file descriptor: the memfd of a "new_memfd" heap, or the dup'd fd of a "new_from_fd" heap. Such an fd can be shared with another process which attaches via "new_from_fd". Returns -1 for file-backed and anonymous heaps, which keep no shareable descriptor.

sync

$heap->sync;

Flush the mapping to the backing file with msync. Croaks on error. No effect for anonymous heaps.

$heap->unlink;
Data::Heap::Shared->unlink($path);

Remove the backing file from the filesystem. Called as an instance method it unlinks the heap's own path; called as a class method it unlinks the given $path. Croaks for anonymous / memfd heaps (no path) or on unlink failure. The mapping stays valid until all handles are destroyed.

stats

my $stats = $heap->stats;

Return a hashref with the keys size, capacity, pushes, pops, waits, timeouts, recoveries, and mmap_size. The counters are cumulative across all processes sharing the heap.

EVENTFD NOTIFICATION

An optional eventfd lets an event loop (e.g. EV, AnyEvent, IO::Async) wake when the heap is written, instead of blocking in "pop_wait".

eventfd

my $fd = $heap->eventfd;

Create (or return) an eventfd associated with this handle and return its file descriptor. Watch it for readability; readiness means "notify" was called. Croaks on error.

eventfd_set

$heap->eventfd_set($fd);

Use a caller-supplied file descriptor for notification instead of one created by "eventfd". Any previously-owned eventfd is closed. The heap takes ownership of $fd: it is closed on the next eventfd_set and when the heap is destroyed, so pass a dup(2) of the descriptor if you need to keep using your own copy.

fileno

my $fd = $heap->fileno;

The current notification file descriptor, or -1 if none is set.

notify

$heap->notify;

Signal the notification fd (write to the eventfd), making it readable. Returns true if a notification was delivered.

eventfd_consume

my $count = $heap->eventfd_consume;

Read and clear the eventfd counter, returning the accumulated count, or undef if there was nothing to read.

BENCHMARKS

Single-process (500K ops, x86_64 Linux, Perl 5.40):

push (sequential)       5.3M/s
pop (drain)             2.5M/s
push+pop (interleaved)  2.5M/s
peek                    4.9M/s

Multi-process (4 workers, 100K ops each, cap=64):

push+pop                3.1M/s aggregate

SECURITY

Backing files are created with mode 0600 (owner-only) by default, so only the creating user can open and attach them. To share a backing file across users, pass an explicit octal file mode such as 0660 as the last argument to new; the mode is applied only when the file is created (an existing file keeps its own permissions). The file is opened with O_NOFOLLOW, so a symlink planted at the path is refused, and created with O_EXCL; the on-disk header is validated when the file is attached. Any process you grant write access to a shared mapping is trusted not to corrupt its contents while other processes are using it.

SEE ALSO

Data::Stack::Shared - LIFO stack

Data::Deque::Shared - double-ended queue

Data::Queue::Shared - FIFO queue

Data::ReqRep::Shared - request-reply

Data::Pool::Shared - fixed-size object pool

Data::Log::Shared - append-only log (WAL)

Data::Buffer::Shared - typed shared array

Data::Sync::Shared - synchronization primitives

Data::HashMap::Shared - concurrent hash table

Data::PubSub::Shared - publish-subscribe ring

Data::Graph::Shared - directed weighted graph

Data::BitSet::Shared - shared bitset (lock-free per-bit ops)

Data::RingBuffer::Shared - fixed-size overwriting ring buffer

AUTHOR

vividsnow

LICENSE

This is free software; you can redistribute it and/or modify it under the same terms as Perl itself.