The pileup Reference Manual

Table of Contents

Next: , Previous: , Up: (dir)   [Contents][Index]

The pileup Reference Manual

This is the pileup Reference Manual, version 1.0.1, generated automatically by Declt version 2.4 "Will Decker" on Wed Jun 20 12:23:53 2018 GMT+0.


Next: , Previous: , Up: Top   [Contents][Index]

1 Introduction

For full documentation, see: http://nikodemus.github.com/pileup/

Pileup is a portable, performant, and thread-safe binary heap for
Common Lisp, under an MIT-style licence.

It depends on Alexandria, and outside SBCL additionally on
Bordeaux-Threads.

Pileup is maintained in Git:

  git clone git://github.com/nikodemus/pileup.git

will get you a local copy.

  http://github.com/nikodemus/pileup

is the GitHub project page.


Next: , Previous: , Up: Top   [Contents][Index]

2 Systems

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


Previous: , Up: Systems   [Contents][Index]

2.1 pileup

Author

Nikodemus Siivola <nikodemus@random-state.net>

License

MIT

Description

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

Version

1.0.1

Dependency

alexandria

Source

pileup.asd (file)

Components

Next: , Previous: , Up: Top   [Contents][Index]

3 Files

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


Next: , Previous: , Up: Files   [Contents][Index]

3.1 Lisp


Next: , Previous: , Up: Lisp files   [Contents][Index]

3.1.1 pileup.asd

Location

pileup.asd

Systems

pileup (system)


Next: , Previous: , Up: Lisp files   [Contents][Index]

3.1.2 pileup/package.lisp

Parent

pileup (system)

Location

package.lisp

Packages

pileup


Previous: , Up: Lisp files   [Contents][Index]

3.1.3 pileup/pileup.lisp

Dependency

package.lisp (file)

Parent

pileup (system)

Location

pileup.lisp

Exported Definitions
Internal Definitions

Previous: , Up: Files   [Contents][Index]

3.2 Other


Next: , Previous: , Up: Other files   [Contents][Index]

3.2.1 pileup/README

Dependency

pileup.lisp (file)

Parent

pileup (system)

Location

README


Previous: , Up: Other files   [Contents][Index]

3.2.2 pileup/LICENCE

Dependency

readme (file)

Parent

pileup (system)

Location

LICENCE


Next: , Previous: , Up: Top   [Contents][Index]

4 Packages

Packages are listed by definition order.


Previous: , Up: Packages   [Contents][Index]

4.1 pileup

Pileup provides a thread-safe binary heap implementation.

Source

package.lisp (file)

Use List
Exported Definitions
Internal Definitions

Next: , Previous: , Up: Top   [Contents][Index]

5 Definitions

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


Next: , Previous: , Up: Definitions   [Contents][Index]

5.1 Exported definitions


Next: , Previous: , Up: Exported definitions   [Contents][Index]

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 (file)


Next: , Previous: , Up: Exported definitions   [Contents][Index]

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 (file)


Next: , Previous: , Up: Exported definitions   [Contents][Index]

5.1.3 Compiler macros

Compiler Macro: make-heap PREDICATE &rest INITARGS
Package

pileup

Source

pileup.lisp (file)


Next: , Previous: , Up: Exported definitions   [Contents][Index]

5.1.4 Functions

Function: heap-count HEAP

Returns the number of objects in the heap.

Package

pileup

Source

pileup.lisp (file)

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 (file)

Function: heap-empty-p HEAP

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

Package

pileup

Source

pileup.lisp (file)

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 (file)

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 (file)

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 (file)

Writer

(setf heap-name) (function)

Function: (setf heap-name) NAME HEAP
Package

pileup

Source

pileup.lisp (file)

Reader

heap-name (function)

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 (file)

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 (file)

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 (file)

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 (file)

Function: make-heap PREDICATE &key (NAME %NAME) (SIZE %SIZE) (KEY %KEY) &aux %VECTOR %PREDICATE FAST-PRED

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 (file)

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 (file)


Previous: , Up: Exported definitions   [Contents][Index]

5.1.5 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 (file)

Direct superclasses

structure-object (structure)

Direct methods

print-object (method)

Direct slots
Slot: %name
Readers

heap-%name (function)

Writers

(setf heap-%name) (function)

Slot: %vector
Type

simple-vector

Initform

(alexandria.0.dev:required-argument :vector)

Readers

heap-%vector (function)

Writers

(setf heap-%vector) (function)

Slot: %count
Type

alexandria.0.dev:array-index

Initform

0

Readers

heap-%count (function)

Writers

(setf heap-%count) (function)

Slot: %size
Type

alexandria.0.dev:array-index

Initform

(alexandria.0.dev:required-argument :%size)

Readers

heap-%size (function)

Writers

(setf heap-%size) (function)

Slot: %predicate
Type

function

Initform

(alexandria.0.dev:required-argument :predicate)

Readers

heap-%predicate (function)

Writers

(setf heap-%predicate) (function)

Slot: %key
Type

(or null function)

Readers

heap-%key (function)

Writers

(setf heap-%key) (function)

Slot: fast-pred
Type

function

Initform

(alexandria.0.dev:required-argument :fast-pred)

Readers

heap-fast-pred (function)

Writers

(setf heap-fast-pred) (function)

Slot: lock
Initform

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

Readers

heap-lock (function)

Writers

(setf heap-lock) (function)

Slot: state
Type

(member :clean :dirty :traverse)

Initform

:clean

Readers

heap-state (function)

Writers

(setf heap-state) (function)


Previous: , Up: Definitions   [Contents][Index]

5.2 Internal definitions


Next: , Previous: , Up: Internal definitions   [Contents][Index]

5.2.1 Constants

Constant: +empty+
Package

pileup

Source

pileup.lisp (file)

Constant: max-heap-size
Package

pileup

Source

pileup.lisp (file)


Next: , Previous: , Up: Internal definitions   [Contents][Index]

5.2.2 Special variables

Special Variable: *two-arg-predicates*
Package

pileup

Source

pileup.lisp (file)


Previous: , Up: Internal definitions   [Contents][Index]

5.2.3 Functions

Function: %heap-delete INDEX HEAP
Package

pileup

Source

pileup.lisp (file)

Function: check-heap-clean HEAP WHAT &optional ALLOW-TRAVERSE
Package

pileup

Source

pileup.lisp (file)

Function: heap-%count INSTANCE
Function: (setf heap-%count) VALUE INSTANCE
Package

pileup

Source

pileup.lisp (file)

Function: heap-%key INSTANCE
Package

pileup

Source

pileup.lisp (file)

Function: heap-%name INSTANCE
Function: (setf heap-%name) VALUE INSTANCE
Package

pileup

Source

pileup.lisp (file)

Function: heap-%predicate INSTANCE
Package

pileup

Source

pileup.lisp (file)

Function: heap-%size INSTANCE
Function: (setf heap-%size) VALUE INSTANCE
Package

pileup

Source

pileup.lisp (file)

Function: heap-%vector INSTANCE
Function: (setf heap-%vector) VALUE INSTANCE
Package

pileup

Source

pileup.lisp (file)

Function: heap-fast-pred INSTANCE
Package

pileup

Source

pileup.lisp (file)

Function: heap-lock INSTANCE
Package

pileup

Source

pileup.lisp (file)

Function: heap-state INSTANCE
Function: (setf heap-state) VALUE INSTANCE
Package

pileup

Source

pileup.lisp (file)

Function: make-heap-using-fast-pred %PREDICATE FAST-PRED &key (NAME %NAME) (SIZE %SIZE) &aux %VECTOR
Package

pileup

Source

pileup.lisp (file)

Function: make-heap-vector SIZE
Package

pileup

Source

pileup.lisp (file)

Function: two-arg-< ()
Package

pileup

Source

pileup.lisp (file)

Function: two-arg-<= ()
Package

pileup

Source

pileup.lisp (file)

Function: two-arg-> ()
Package

pileup

Source

pileup.lisp (file)

Function: two-arg->= ()
Package

pileup

Source

pileup.lisp (file)


Previous: , Up: Top   [Contents][Index]

Appendix A Indexes


Next: , Previous: , Up: Indexes   [Contents][Index]

A.1 Concepts

Jump to:   F   L   O   P  
Index Entry  Section

F
File, Lisp, pileup.asd: The pileup<dot>asd file
File, Lisp, pileup/package.lisp: The pileup/package<dot>lisp file
File, Lisp, pileup/pileup.lisp: The pileup/pileup<dot>lisp file
File, other, pileup/LICENCE: The pileup/licence file
File, other, pileup/README: The pileup/readme file

L
Lisp File, pileup.asd: The pileup<dot>asd file
Lisp File, pileup/package.lisp: The pileup/package<dot>lisp file
Lisp File, pileup/pileup.lisp: The pileup/pileup<dot>lisp file

O
Other File, pileup/LICENCE: The pileup/licence file
Other File, pileup/README: The pileup/readme file

P
pileup.asd: The pileup<dot>asd file
pileup/LICENCE: The pileup/licence file
pileup/package.lisp: The pileup/package<dot>lisp file
pileup/pileup.lisp: The pileup/pileup<dot>lisp file
pileup/README: The pileup/readme file

Jump to:   F   L   O   P  

Next: , Previous: , Up: Indexes   [Contents][Index]

A.2 Functions

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

%
%heap-delete: Internal functions

(
(setf heap-%count): Internal functions
(setf heap-%name): Internal functions
(setf heap-%size): Internal functions
(setf heap-%vector): Internal functions
(setf heap-name): Exported functions
(setf heap-state): Internal functions

C
check-heap-clean: Internal functions
Compiler Macro, make-heap: Exported compiler macros

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

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

M
Macro, with-locked-heap: Exported macros
make-heap: Exported compiler macros
make-heap: Exported functions
make-heap-using-fast-pred: Internal functions
make-heap-vector: Internal functions
map-heap: Exported functions

T
two-arg-<: Internal functions
two-arg-<=: Internal functions
two-arg->: Internal functions
two-arg->=: Internal functions

W
with-locked-heap: Exported macros

Jump to:   %   (  
C   F   H   M   T   W  

Next: , Previous: , Up: Indexes   [Contents][Index]

A.3 Variables

Jump to:   %   *   +  
C   F   H   L   M   S  
Index Entry  Section

%
%count: Exported structures
%key: Exported structures
%name: Exported structures
%predicate: Exported structures
%size: Exported structures
%vector: Exported structures

*
*two-arg-predicates*: Internal special variables

+
+empty+: Internal constants

C
Constant, +empty+: Internal constants
Constant, heap-size-limit: Exported constants
Constant, max-heap-size: Internal constants

F
fast-pred: Exported structures

H
heap-size-limit: Exported constants

L
lock: Exported structures

M
max-heap-size: Internal constants

S
Slot, %count: Exported structures
Slot, %key: Exported structures
Slot, %name: Exported structures
Slot, %predicate: Exported structures
Slot, %size: Exported structures
Slot, %vector: Exported structures
Slot, fast-pred: Exported structures
Slot, lock: Exported structures
Slot, state: Exported structures
Special Variable, *two-arg-predicates*: Internal special variables
state: Exported structures

Jump to:   %   *   +  
C   F   H   L   M   S  

Previous: , Up: Indexes   [Contents][Index]

A.4 Data types

Jump to:   H   P   S  
Index Entry  Section

H
heap: Exported structures

P
Package, pileup: The pileup package
pileup: The pileup system
pileup: The pileup package

S
Structure, heap: Exported structures
System, pileup: The pileup system

Jump to:   H   P   S