The damn-fast-priority-queue Reference Manual

Table of Contents

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

The damn-fast-priority-queue Reference Manual

This is the damn-fast-priority-queue Reference Manual, version 0.0.2, generated automatically by Declt version 3.0 "Montgomery Scott" on Mon Apr 19 15:49:15 2021 GMT+0.


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

1 Introduction

Damn Fast Priority Queue

A heap-based priority queue whose first and foremost priority is speed. Optionally comes in a stable flavor.

Blame @mfiano for the existence of this library. He's the one who wanted a priority queue that's going to run as fast as possible in one of the hottest loops of his game engine ~~and then figured out that hey, he actually doesn't need a prio queue there~~.

License

MIT.

Systems

Description

Implementation details

Optimization settings

Exports

All exported functions are proclaimed inline by default.

Tests

Performance tests

See the Priority Queue Benchmark README.


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 damn-fast-priority-queue

Author

Michał "phoe" Herda <phoe@disroot.org>

License

MIT

Description

A heap-based priority queue whose first and foremost priority is speed.

Version

0.0.2

Dependency

alexandria

Source

damn-fast-priority-queue.asd (file)

Component

src.lisp (file)


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

3 Files

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


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

3.1 Lisp


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

3.1.1 damn-fast-priority-queue.asd

Location

damn-fast-priority-queue.asd

Systems

damn-fast-priority-queue (system)


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

3.1.2 damn-fast-priority-queue/src.lisp

Parent

damn-fast-priority-queue (system)

Location

src.lisp

Packages

damn-fast-priority-queue

Exported Definitions
Internal Definitions

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

4 Packages

Packages are listed by definition order.


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

4.1 damn-fast-priority-queue

Source

src.lisp (file)

Use List

common-lisp

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 Macros

Macro: do-queue (OBJECT QUEUE &optional RESULT) &body BODY
Package

damn-fast-priority-queue

Source

src.lisp (file)


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

5.1.2 Functions

Function: copy-queue QUEUE
Package

damn-fast-priority-queue

Source

src.lisp (file)

Function: dequeue QUEUE
Package

damn-fast-priority-queue

Source

src.lisp (file)

Function: enqueue QUEUE OBJECT PRIORITY
Package

damn-fast-priority-queue

Source

src.lisp (file)

Function: make-queue &optional INITIAL-STORAGE-SIZE EXTENSION-FACTOR EXTEND-QUEUE-P
Package

damn-fast-priority-queue

Source

src.lisp (file)

Function: map QUEUE FUNCTION
Package

damn-fast-priority-queue

Source

src.lisp (file)

Function: peek QUEUE
Package

damn-fast-priority-queue

Source

src.lisp (file)

Function: size QUEUE
Package

damn-fast-priority-queue

Source

src.lisp (file)

Function: trim QUEUE
Package

damn-fast-priority-queue

Source

src.lisp (file)


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

5.1.3 Generic functions

Generic Function: queue-size-limit-reached-object CONDITION
Package

damn-fast-priority-queue

Methods
Method: queue-size-limit-reached-object (CONDITION queue-size-limit-reached)
Source

src.lisp (file)

Generic Function: queue-size-limit-reached-queue CONDITION
Package

damn-fast-priority-queue

Methods
Method: queue-size-limit-reached-queue (CONDITION queue-size-limit-reached)
Source

src.lisp (file)


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

5.1.4 Conditions

Condition: queue-size-limit-reached ()
Package

damn-fast-priority-queue

Source

src.lisp (file)

Direct superclasses

error (condition)

Direct methods
Direct slots
Slot: %queue
Initargs

:queue

Readers

queue-size-limit-reached-queue (generic function)

Slot: %object
Initargs

:element

Readers

queue-size-limit-reached-object (generic function)

Direct Default Initargs
InitargValue
:object(alexandria:required-argument :object)
:queue(alexandria:required-argument :queue)

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

5.1.5 Structures

Structure: queue ()
Package

damn-fast-priority-queue

Source

src.lisp (file)

Direct superclasses

structure-object (structure)

Direct methods

print-object (method)

Direct slots
Slot: data-vector
Type

damn-fast-priority-queue::data-vector-type

Initform

(make-array 256 :element-type (quote damn-fast-priority-queue::data-type))

Readers

%data-vector (function)

Writers

(setf %data-vector) (function)

Slot: prio-vector
Type

damn-fast-priority-queue::prio-vector-type

Initform

(make-array 256 :element-type (quote damn-fast-priority-queue::prio-type))

Readers

%prio-vector (function)

Writers

(setf %prio-vector) (function)

Slot: size
Type

alexandria:array-length

Initform

0

Readers

%size (function)

Writers

(setf %size) (function)

Slot: extension-factor
Type

damn-fast-priority-queue::extension-factor-type

Initform

2

Readers

%extension-factor (function)

Writers

(setf %extension-factor) (function)

Slot: extend-queue-p
Type

boolean

Initform

t

Readers

%extend-queue-p (function)

Writers

(setf %extend-queue-p) (function)


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

5.2 Internal definitions


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

5.2.1 Special variables

Special Variable: *optimize-qualities*
Package

damn-fast-priority-queue

Source

src.lisp (file)


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

5.2.2 Functions

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

damn-fast-priority-queue

Source

src.lisp (file)

Function: %extend-queue-p INSTANCE
Function: (setf %extend-queue-p) VALUE INSTANCE
Package

damn-fast-priority-queue

Source

src.lisp (file)

Function: %extension-factor INSTANCE
Function: (setf %extension-factor) VALUE INSTANCE
Package

damn-fast-priority-queue

Source

src.lisp (file)

Function: %make &key (DATA-VECTOR DATA-VECTOR) (PRIO-VECTOR PRIO-VECTOR) (SIZE SIZE) (EXTENSION-FACTOR EXTENSION-FACTOR) (EXTEND-QUEUE-P EXTEND-QUEUE-P)
Package

damn-fast-priority-queue

Source

src.lisp (file)

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

damn-fast-priority-queue

Source

src.lisp (file)

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

damn-fast-priority-queue

Source

src.lisp (file)

Function: heapify-downwards DATA-VECTOR PRIO-VECTOR SIZE
Package

damn-fast-priority-queue

Source

src.lisp (file)

Function: heapify-upwards DATA-VECTOR PRIO-VECTOR INDEX
Package

damn-fast-priority-queue

Source

src.lisp (file)

Function: report-queue-size-limit-reached CONDITION STREAM
Package

damn-fast-priority-queue

Source

src.lisp (file)


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

5.2.3 Types

Type: data-type ()
Package

damn-fast-priority-queue

Source

src.lisp (file)

Type: data-vector-type ()
Package

damn-fast-priority-queue

Source

src.lisp (file)

Type: extension-factor-type ()
Package

damn-fast-priority-queue

Source

src.lisp (file)

Type: prio-type ()
Package

damn-fast-priority-queue

Source

src.lisp (file)

Type: prio-vector-type ()
Package

damn-fast-priority-queue

Source

src.lisp (file)


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

Appendix A Indexes


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

A.1 Concepts

Jump to:   D   F   L  
Index Entry  Section

D
damn-fast-priority-queue.asd: The damn-fast-priority-queue․asd file
damn-fast-priority-queue/src.lisp: The damn-fast-priority-queue/src․lisp file

F
File, Lisp, damn-fast-priority-queue.asd: The damn-fast-priority-queue․asd file
File, Lisp, damn-fast-priority-queue/src.lisp: The damn-fast-priority-queue/src․lisp file

L
Lisp File, damn-fast-priority-queue.asd: The damn-fast-priority-queue․asd file
Lisp File, damn-fast-priority-queue/src.lisp: The damn-fast-priority-queue/src․lisp file

Jump to:   D   F   L  

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

A.2 Functions

Jump to:   %   (  
C   D   E   F   G   H   M   P   Q   R   S   T  
Index Entry  Section

%
%data-vector: Internal functions
%extend-queue-p: Internal functions
%extension-factor: Internal functions
%make: Internal functions
%prio-vector: Internal functions
%size: Internal functions

(
(setf %data-vector): Internal functions
(setf %extend-queue-p): Internal functions
(setf %extension-factor): Internal functions
(setf %prio-vector): Internal functions
(setf %size): Internal functions

C
copy-queue: Exported functions

D
dequeue: Exported functions
do-queue: Exported macros

E
enqueue: Exported functions

F
Function, %data-vector: Internal functions
Function, %extend-queue-p: Internal functions
Function, %extension-factor: Internal functions
Function, %make: Internal functions
Function, %prio-vector: Internal functions
Function, %size: Internal functions
Function, (setf %data-vector): Internal functions
Function, (setf %extend-queue-p): Internal functions
Function, (setf %extension-factor): Internal functions
Function, (setf %prio-vector): Internal functions
Function, (setf %size): Internal functions
Function, copy-queue: Exported functions
Function, dequeue: Exported functions
Function, enqueue: Exported functions
Function, heapify-downwards: Internal functions
Function, heapify-upwards: Internal functions
Function, make-queue: Exported functions
Function, map: Exported functions
Function, peek: Exported functions
Function, report-queue-size-limit-reached: Internal functions
Function, size: Exported functions
Function, trim: Exported functions

G
Generic Function, queue-size-limit-reached-object: Exported generic functions
Generic Function, queue-size-limit-reached-queue: Exported generic functions

H
heapify-downwards: Internal functions
heapify-upwards: Internal functions

M
Macro, do-queue: Exported macros
make-queue: Exported functions
map: Exported functions
Method, queue-size-limit-reached-object: Exported generic functions
Method, queue-size-limit-reached-queue: Exported generic functions

P
peek: Exported functions

Q
queue-size-limit-reached-object: Exported generic functions
queue-size-limit-reached-object: Exported generic functions
queue-size-limit-reached-queue: Exported generic functions
queue-size-limit-reached-queue: Exported generic functions

R
report-queue-size-limit-reached: Internal functions

S
size: Exported functions

T
trim: Exported functions

Jump to:   %   (  
C   D   E   F   G   H   M   P   Q   R   S   T  

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

A.3 Variables

Jump to:   %   *  
D   E   P   S  
Index Entry  Section

%
%object: Exported conditions
%queue: Exported conditions

*
*optimize-qualities*: Internal special variables

D
data-vector: Exported structures

E
extend-queue-p: Exported structures
extension-factor: Exported structures

P
prio-vector: Exported structures

S
size: Exported structures
Slot, %object: Exported conditions
Slot, %queue: Exported conditions
Slot, data-vector: Exported structures
Slot, extend-queue-p: Exported structures
Slot, extension-factor: Exported structures
Slot, prio-vector: Exported structures
Slot, size: Exported structures
Special Variable, *optimize-qualities*: Internal special variables

Jump to:   %   *  
D   E   P   S  

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

A.4 Data types

Jump to:   C   D   E   P   Q   S   T  
Index Entry  Section

C
Condition, queue-size-limit-reached: Exported conditions

D
damn-fast-priority-queue: The damn-fast-priority-queue system
damn-fast-priority-queue: The damn-fast-priority-queue package
data-type: Internal types
data-vector-type: Internal types

E
extension-factor-type: Internal types

P
Package, damn-fast-priority-queue: The damn-fast-priority-queue package
prio-type: Internal types
prio-vector-type: Internal types

Q
queue: Exported structures
queue-size-limit-reached: Exported conditions

S
Structure, queue: Exported structures
System, damn-fast-priority-queue: The damn-fast-priority-queue system

T
Type, data-type: Internal types
Type, data-vector-type: Internal types
Type, extension-factor-type: Internal types
Type, prio-type: Internal types
Type, prio-vector-type: Internal types

Jump to:   C   D   E   P   Q   S   T