Next: Introduction, Previous: (dir), Up: (dir) [Contents][Index]
This is the pileup Reference Manual, version 1.0.1, generated automatically by Declt version 3.0 "Montgomery Scott" on Tue Dec 22 14:40:18 2020 GMT+0.
• Introduction | What pileup is all about | |
• Systems | The systems documentation | |
• Files | The files documentation | |
• Packages | The packages documentation | |
• Definitions | The symbols documentation | |
• Indexes | Concepts, functions, variables and data types |
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: Files, Previous: Introduction, Up: Top [Contents][Index]
The main system appears first, followed by any subsystem dependency.
• The pileup system |
Nikodemus Siivola <nikodemus@random-state.net>
MIT
A portable, performant, and thread-safe binary heap / priority queue.
1.0.1
alexandria
pileup.asd (file)
Files are sorted by type and then listed depth-first from the systems components trees.
• Lisp files | ||
• Static files |
Next: Static files, Previous: Files, Up: Files [Contents][Index]
• The pileup.asd file | ||
• The pileup/package.lisp file | ||
• The pileup/pileup.lisp file |
Next: The pileup/package․lisp file, Previous: Lisp files, Up: Lisp files [Contents][Index]
pileup.asd
pileup (system)
Next: The pileup/pileup․lisp file, Previous: The pileup․asd file, Up: Lisp files [Contents][Index]
Previous: The pileup/package․lisp file, Up: Lisp files [Contents][Index]
package.lisp (file)
pileup (system)
pileup.lisp
Previous: Lisp files, Up: Files [Contents][Index]
• The pileup/readme file | ||
• The pileup/licence file |
Next: The pileup/licence file, Previous: Static files, Up: Static files [Contents][Index]
pileup.lisp (file)
pileup (system)
README
Previous: The pileup/readme file, Up: Static files [Contents][Index]
Next: Definitions, Previous: Files, Up: Top [Contents][Index]
Packages are listed by definition order.
• The pileup package |
Pileup provides a thread-safe binary heap implementation.
package.lisp (file)
Definitions are sorted by export status, category, package, and then by lexicographic order.
• Exported definitions | ||
• Internal definitions |
Next: Internal definitions, Previous: Definitions, Up: Definitions [Contents][Index]
• Exported constants | ||
• Exported macros | ||
• Exported compiler macros | ||
• Exported functions | ||
• Exported structures |
Next: Exported macros, Previous: Exported definitions, Up: Exported definitions [Contents][Index]
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.
pileup.lisp (file)
Next: Exported compiler macros, Previous: Exported constants, Up: Exported definitions [Contents][Index]
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.
pileup.lisp (file)
Next: Exported functions, Previous: Exported macros, Up: Exported definitions [Contents][Index]
pileup.lisp (file)
Next: Exported structures, Previous: Exported compiler macros, Up: Exported definitions [Contents][Index]
Returns the number of objects in the heap.
pileup.lisp (file)
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.
pileup.lisp (file)
Returns true if the heap is empty, that is iff HEAP-COUNT is zero.
pileup.lisp (file)
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.
pileup.lisp (file)
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.
pileup.lisp (file)
Returns the name of the heap. Heap name affects only printed representation of the heap. Can be changed using SETF unlike other heap properties.
pileup.lisp (file)
(setf heap-name) (function)
pileup.lisp (file)
heap-name (function)
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.
pileup.lisp (file)
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.
pileup.lisp (file)
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.
pileup.lisp (file)
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.
pileup.lisp (file)
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.
pileup.lisp (file)
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.
pileup.lisp (file)
Previous: Exported functions, Up: Exported definitions [Contents][Index]
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.
pileup.lisp (file)
structure-object (structure)
print-object (method)
heap-%name (function)
(setf heap-%name) (function)
simple-vector
(alexandria:required-argument :vector)
heap-%vector (function)
(setf heap-%vector) (function)
alexandria:array-index
0
heap-%count (function)
(setf heap-%count) (function)
alexandria:array-index
(alexandria:required-argument :%size)
heap-%size (function)
(setf heap-%size) (function)
function
(alexandria:required-argument :predicate)
heap-%predicate (function)
(setf heap-%predicate) (function)
(or null function)
heap-%key (function)
(setf heap-%key) (function)
function
(alexandria:required-argument :fast-pred)
heap-fast-pred (function)
(setf heap-fast-pred) (function)
(sb-thread:make-mutex :name "heap lock")
heap-lock (function)
(setf heap-lock) (function)
(member :clean :dirty :traverse)
:clean
heap-state (function)
(setf heap-state) (function)
Previous: Exported definitions, Up: Definitions [Contents][Index]
• Internal constants | ||
• Internal special variables | ||
• Internal functions |
Next: Internal special variables, Previous: Internal definitions, Up: Internal definitions [Contents][Index]
pileup.lisp (file)
pileup.lisp (file)
Next: Internal functions, Previous: Internal constants, Up: Internal definitions [Contents][Index]
pileup.lisp (file)
Previous: Internal special variables, Up: Internal definitions [Contents][Index]
pileup.lisp (file)
pileup.lisp (file)
pileup.lisp (file)
pileup.lisp (file)
pileup.lisp (file)
pileup.lisp (file)
pileup.lisp (file)
pileup.lisp (file)
pileup.lisp (file)
pileup.lisp (file)
pileup.lisp (file)
pileup.lisp (file)
pileup.lisp (file)
pileup.lisp (file)
pileup.lisp (file)
pileup.lisp (file)
pileup.lisp (file)
Previous: Definitions, Up: Top [Contents][Index]
• Concept index | ||
• Function index | ||
• Variable index | ||
• Data type index |
Next: Function index, Previous: Indexes, Up: Indexes [Contents][Index]
Jump to: | F L P S |
---|
Jump to: | F L P S |
---|
Next: Variable index, Previous: Concept index, Up: Indexes [Contents][Index]
Jump to: | %
(
C F H M T W |
---|
Jump to: | %
(
C F H M T W |
---|
Next: Data type index, Previous: Function index, Up: Indexes [Contents][Index]
Jump to: | %
*
+
C F H L M S |
---|
Jump to: | %
*
+
C F H L M S |
---|
Previous: Variable index, Up: Indexes [Contents][Index]
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 |
---|