The pileup Reference Manual

This is the pileup Reference Manual, version 1.0.1, generated automatically by Declt version 4.0 beta 2 "William Riker" on Wed May 15 06:31:37 2024 GMT+0.

Table of Contents


1 Introduction


2 Systems

The main system appears first, followed by any subsystem dependency.


2.1 pileup

A portable, performant, and thread-safe binary heap / priority queue.

Author

Nikodemus Siivola <>

License

MIT

Version

1.0.1

Dependency

alexandria (system).

Source

pileup.asd.

Child Components

3 Files

Files are sorted by type and then listed depth-first from the systems components trees.


3.1 Lisp


3.1.1 pileup/pileup.asd

Source

pileup.asd.

Parent Component

pileup (system).

ASDF Systems

pileup.


3.1.2 pileup/package.lisp

Source

pileup.asd.

Parent Component

pileup (system).

Packages

pileup.


3.1.3 pileup/pileup.lisp

Dependency

package.lisp (file).

Source

pileup.asd.

Parent Component

pileup (system).

Public Interface
Internals

3.2 Static


3.2.1 pileup/README

Dependency

pileup.lisp (file).

Source

pileup.asd.

Parent Component

pileup (system).


3.2.2 pileup/LICENCE

Dependency

readme (file).

Source

pileup.asd.

Parent Component

pileup (system).


4 Packages

Packages are listed by definition order.


4.1 pileup

Pileup provides a thread-safe binary heap implementation.

Source

package.lisp.

Use List
  • alexandria.
  • common-lisp.
Public Interface
Internals

5 Definitions

Definitions are sorted by export status, category, package, and then by lexicographic order.


5.1 Public Interface


5.1.1 Constants

Constant: heap-size-limit

Exclusive upper limit for heap size, based on ARRAY-DIMENSION-LIMIT.
When an insertion is attempted and the heap cannot grow any further, an error is signaled.

Package

pileup.

Source

pileup.lisp.


5.1.2 Macros

Macro: with-locked-heap ((heap) &body body)

Executes BODY with HEAP locked. Heap operations which implicitly lock the heap are: HEAP-INSERT, HEAP-POP, HEAP-DELETE, and MAP-HEAP. Allows grouping multiple heap operations into atomic units.

Package

pileup.

Source

pileup.lisp.


5.1.3 Compiler macros

Compiler Macro: make-heap (predicate &rest initargs)
Package

pileup.

Source

pileup.lisp.


5.1.4 Ordinary functions

Function: heap-count (heap)

Returns the number of objects in the heap.

Package

pileup.

Source

pileup.lisp.

Function: heap-delete (elt heap &key count)

Removes elements of the HEAP EQL to ELT. Returns T if one or more elements were found and removed, NIL otherwise.

If COUNT is NIL (the default), removes all elements EQL to ELT, otherwise at most the indicated number.

Locks the heap during its operation unless the current thread is already holding the heap lock via WITH-LOCKED-HEAP.

Package

pileup.

Source

pileup.lisp.

Function: heap-empty-p (heap)

Returns true if the heap is empty, that is iff HEAP-COUNT is zero.

Package

pileup.

Source

pileup.lisp.

Function: heap-insert (elt heap)

Insert ELT to HEAP. Returns ELT.

Locks the heap during its operation unless the current thread is already holding the heap lock via WITH-LOCKED-HEAP.

Package

pileup.

Source

pileup.lisp.

Function: heap-key (heap)

Returns the heap key, a function one argument used to extract values for use by the heap predicate. Heap key may also be NIL, meaning heap elements are used directly by the heap predicate.

Package

pileup.

Source

pileup.lisp.

Function: heap-name (heap)

Returns the name of the heap. Heap name affects only printed representation of the heap. Can be changed using SETF unlike other heap properties.

Package

pileup.

Source

pileup.lisp.

Function: (setf heap-name) (heap)
Package

pileup.

Source

pileup.lisp.

Function: heap-pop (heap)

Removes and returns the element at the top of the HEAP and a secondary value of T. Should the heap be empty, both the primary and the secondary values are NIL.

Locks the heap during its operation unless the current thread is already holding the heap lock via WITH-LOCKED-HEAP.

Package

pileup.

Source

pileup.lisp.

Function: heap-predicate (heap)

Returns the heap predicate, a function of two arguments, returning true if the first argument should be closer to te top of the heap than the second.

Package

pileup.

Source

pileup.lisp.

Function: heap-size (heap)

Returns the reserved size of the heap. Note, this is not the same as the number of elements in the heap: see HEAP-COUNT for comparison.

Package

pileup.

Source

pileup.lisp.

Function: heap-top (heap)

Returns the element at the top of the HEAP without removing it, and a secondary value of T. Should the heap be empty, both the primary and the secondary values are NIL.

Package

pileup.

Source

pileup.lisp.

Function: make-heap (predicate &key name size key)

Constructs a HEAP.

The PREDICATE determines the ordering of the heap. It must be a function of two arguments, returning true if the first argument should be closer to top of the heap than the second. If a predicate signals an error and causes a non-local exit from a heap operation, it may leave the heap in an inconsistent state and cause a subsequent heap operation to signal an error.

If KEY is not NIL, it must be a function of one argument, and is used to extract values for use by PREDICATE for comparison.

The NAME can be used to optionally specify a name for the heap: it affects only printing of the heap.

The SIZE is the size of the storage initially reserved for the heap. Specifying size is not necessary: the heap will grow as necessary, but a reasonable estimate can improve performance by eliminating unnecessary copying by allocating sufficient storage immediately.

Package

pileup.

Source

pileup.lisp.

Function: map-heap (function heap &key ordered)

Calls FUNCTION for each element in heap. Returns the heap.

If ORDERED is true (the default), processes the elements in heap order from top down.

If ORDERED is false, uses unordered traversal. Unordered traversal is faster and also works on heaps that have been corrupted by eg. the heap predicate performing a non-local exit from a heap operation.

Attempts to insert or delete elements to the heap from FUNCTION will cause an error to be signalled.

Locks the heap during its operation unless the current thread is already holding the heap lock via WITH-LOCKED-HEAP.

Package

pileup.

Source

pileup.lisp.


5.1.5 Standalone methods

Method: print-object ((heap heap) stream)
Source

pileup.lisp.


5.1.6 Structures

Structure: heap

A thread-safe binary heap.

Heap operations which need the heap to remain consistent heap lock it. Users can also group multiple heap operations into atomic units using WITH-LOCKED-HEAP.

Thread-safety is implemented using a single lock per heap. While Pileup heaps are fine for threaded use, a more specialized solution is recommended when the heap is highly contested between multiple threads.

Important: Pileup heaps are not asynch-unwind safe: asynchronous interrupts causing non-local exits may leave the heap in an inconsistent state or lose data. Do not use INTERRUPT-THREAD or asychronous timeouts with Pileup.

All slot names in HEAP are internal to the PILEUP package, so it is safe to subclass using eg. DEFSTRUCT :INCLUDE, as long as only the exported operations are used to accessor or modify heap state.

Package

pileup.

Source

pileup.lisp.

Direct superclasses

structure-object.

Direct methods

print-object.

Direct slots
Slot: %name
Readers

heap-%name.

Writers

(setf heap-%name).

Slot: %vector
Type

simple-vector

Initform

(alexandria:required-argument :vector)

Readers

heap-%vector.

Writers

(setf heap-%vector).

Slot: %count
Type

alexandria:array-index

Initform

0

Readers

heap-%count.

Writers

(setf heap-%count).

Slot: %size
Type

alexandria:array-index

Initform

(alexandria:required-argument :%size)

Readers

heap-%size.

Writers

(setf heap-%size).

Slot: %predicate
Type

function

Initform

(alexandria:required-argument :predicate)

Readers

heap-%predicate.

Writers

This slot is read-only.

Slot: %key
Type

(or null function)

Readers

heap-%key.

Writers

This slot is read-only.

Slot: fast-pred
Type

function

Initform

(alexandria:required-argument :fast-pred)

Readers

heap-fast-pred.

Writers

This slot is read-only.

Slot: lock
Initform

(sb-thread:make-mutex :name "heap lock")

Readers

heap-lock.

Writers

This slot is read-only.

Slot: state
Type

(member :clean :dirty :traverse)

Initform

:clean

Readers

heap-state.

Writers

(setf heap-state).


5.2 Internals


5.2.1 Constants

Constant: +empty+
Package

pileup.

Source

pileup.lisp.

Constant: max-heap-size
Package

pileup.

Source

pileup.lisp.


5.2.2 Special variables

Special Variable: *two-arg-predicates*
Package

pileup.

Source

pileup.lisp.


5.2.3 Ordinary functions

Function: %heap-delete (index heap)
Package

pileup.

Source

pileup.lisp.

Function: check-heap-clean (heap what &optional allow-traverse)
Package

pileup.

Source

pileup.lisp.

Reader: heap-%count (instance)
Writer: (setf heap-%count) (instance)
Package

pileup.

Source

pileup.lisp.

Target Slot

%count.

Reader: heap-%key (instance)
Package

pileup.

Source

pileup.lisp.

Target Slot

%key.

Reader: heap-%name (instance)
Writer: (setf heap-%name) (instance)
Package

pileup.

Source

pileup.lisp.

Target Slot

%name.

Reader: heap-%predicate (instance)
Package

pileup.

Source

pileup.lisp.

Target Slot

%predicate.

Reader: heap-%size (instance)
Writer: (setf heap-%size) (instance)
Package

pileup.

Source

pileup.lisp.

Target Slot

%size.

Reader: heap-%vector (instance)
Writer: (setf heap-%vector) (instance)
Package

pileup.

Source

pileup.lisp.

Target Slot

%vector.

Reader: heap-fast-pred (instance)
Package

pileup.

Source

pileup.lisp.

Target Slot

fast-pred.

Reader: heap-lock (instance)
Package

pileup.

Source

pileup.lisp.

Target Slot

lock.

Reader: heap-state (instance)
Writer: (setf heap-state) (instance)
Package

pileup.

Source

pileup.lisp.

Target Slot

state.

Function: make-heap-using-fast-pred (%predicate fast-pred &key name size)
Package

pileup.

Source

pileup.lisp.

Function: make-heap-vector (size)
Package

pileup.

Source

pileup.lisp.

Function: two-arg-< (x y)
Package

pileup.

Source

pileup.lisp.

Function: two-arg-<= (x y)
Package

pileup.

Source

pileup.lisp.

Function: two-arg-> (x y)
Package

pileup.

Source

pileup.lisp.

Function: two-arg->= (x y)
Package

pileup.

Source

pileup.lisp.


Appendix A Indexes


A.1 Concepts


A.2 Functions

Jump to:   %   (  
C   F   H   M   P   T   W  
Index Entry  Section

%
%heap-delete: Private ordinary functions

(
(setf heap-%count): Private ordinary functions
(setf heap-%name): Private ordinary functions
(setf heap-%size): Private ordinary functions
(setf heap-%vector): Private ordinary functions
(setf heap-name): Public ordinary functions
(setf heap-state): Private ordinary functions

C
check-heap-clean: Private ordinary functions
Compiler Macro, make-heap: Public compiler macros

F
Function, %heap-delete: Private ordinary functions
Function, (setf heap-%count): Private ordinary functions
Function, (setf heap-%name): Private ordinary functions
Function, (setf heap-%size): Private ordinary functions
Function, (setf heap-%vector): Private ordinary functions
Function, (setf heap-name): Public ordinary functions
Function, (setf heap-state): Private ordinary functions
Function, check-heap-clean: Private ordinary functions
Function, heap-%count: Private ordinary functions
Function, heap-%key: Private ordinary functions
Function, heap-%name: Private ordinary functions
Function, heap-%predicate: Private ordinary functions
Function, heap-%size: Private ordinary functions
Function, heap-%vector: Private ordinary functions
Function, heap-count: Public ordinary functions
Function, heap-delete: Public ordinary functions
Function, heap-empty-p: Public ordinary functions
Function, heap-fast-pred: Private ordinary functions
Function, heap-insert: Public ordinary functions
Function, heap-key: Public ordinary functions
Function, heap-lock: Private ordinary functions
Function, heap-name: Public ordinary functions
Function, heap-pop: Public ordinary functions
Function, heap-predicate: Public ordinary functions
Function, heap-size: Public ordinary functions
Function, heap-state: Private ordinary functions
Function, heap-top: Public ordinary functions
Function, make-heap: Public ordinary functions
Function, make-heap-using-fast-pred: Private ordinary functions
Function, make-heap-vector: Private ordinary functions
Function, map-heap: Public ordinary functions
Function, two-arg-<: Private ordinary functions
Function, two-arg-<=: Private ordinary functions
Function, two-arg->: Private ordinary functions
Function, two-arg->=: Private ordinary functions

H
heap-%count: Private ordinary functions
heap-%key: Private ordinary functions
heap-%name: Private ordinary functions
heap-%predicate: Private ordinary functions
heap-%size: Private ordinary functions
heap-%vector: Private ordinary functions
heap-count: Public ordinary functions
heap-delete: Public ordinary functions
heap-empty-p: Public ordinary functions
heap-fast-pred: Private ordinary functions
heap-insert: Public ordinary functions
heap-key: Public ordinary functions
heap-lock: Private ordinary functions
heap-name: Public ordinary functions
heap-pop: Public ordinary functions
heap-predicate: Public ordinary functions
heap-size: Public ordinary functions
heap-state: Private ordinary functions
heap-top: Public ordinary functions

M
Macro, with-locked-heap: Public macros
make-heap: Public compiler macros
make-heap: Public ordinary functions
make-heap-using-fast-pred: Private ordinary functions
make-heap-vector: Private ordinary functions
map-heap: Public ordinary functions
Method, print-object: Public standalone methods

P
print-object: Public standalone methods

T
two-arg-<: Private ordinary functions
two-arg-<=: Private ordinary functions
two-arg->: Private ordinary functions
two-arg->=: Private ordinary functions

W
with-locked-heap: Public macros