The jpl-queues Reference Manual

Table of Contents

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

The jpl-queues Reference Manual

This is the jpl-queues Reference Manual, version 0.1, generated automatically by Declt version 2.3 "Robert April" on Wed Mar 14 04:05:44 2018 GMT+0.


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

1 Systems

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


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

1.1 jpl-queues

Maintainer

J.P. Larocque

Author

J.P. Larocque

License

ISC-style permissive

Description

A few different kinds of queues, with optional multithreading synchronization.

Version

0.1

Dependencies
Source

jpl-queues.asd (file)

Components

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

2 Files

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


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

2.1 Lisp


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

2.1.1 jpl-queues.asd

Location

jpl-queues.asd

Systems

jpl-queues (system)


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

2.1.2 jpl-queues/interface.lisp

Dependency

package.lisp (file)

Parent

jpl-queues (system)

Location

interface.lisp

Exported Definitions

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

2.1.3 jpl-queues/bounded-fifo.lisp

Dependencies
Parent

jpl-queues (system)

Location

bounded-fifo.lisp

Exported Definitions
Internal Definitions

test-bounded-fifo-queue-dequeue-object-if (function)


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

2.1.4 jpl-queues/lossy-bounded-fifo.lisp

Dependencies
Parent

jpl-queues (system)

Location

lossy-bounded-fifo.lisp

Exported Definitions

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

2.1.5 jpl-queues/unbounded-fifo.lisp

Dependencies
Parent

jpl-queues (system)

Location

unbounded-fifo.lisp

Exported Definitions
Internal Definitions

buffer (method)


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

2.1.6 jpl-queues/unbounded-random.lisp

Dependencies
Parent

jpl-queues (system)

Location

unbounded-random.lisp

Exported Definitions

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

2.1.7 jpl-queues/synchronized.lisp

Dependencies
Parent

jpl-queues (system)

Location

synchronized.lisp

Exported Definitions

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

2.1.8 jpl-queues/package.lisp

Parent

jpl-queues (system)

Location

package.lisp

Packages

jpl-queues


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

3 Packages

Packages are listed by definition order.


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

3.1 jpl-queues

Source

package.lisp (file)

Use List

common-lisp

Exported Definitions
Internal Definitions

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

4 Definitions

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


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

4.1 Exported definitions


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

4.1.1 Generic functions

Generic Function: capacity QUEUE

Returns the number of elements that can be stored
at once in the given QUEUE, or NIL if there is no limit.

Most implementations will take constant time.

Package

jpl-queues

Source

interface.lisp (file)

Methods
Method: capacity (QUEUE synchronized-queue)
Source

synchronized.lisp (file)

Method: capacity (QUEUE unbounded-random-queue)
Source

unbounded-random.lisp (file)

Method: capacity (QUEUE unbounded-fifo-queue)
Source

unbounded-fifo.lisp (file)

Method: capacity (QUEUE bounded-fifo-queue)
Source

bounded-fifo.lisp (file)

Generic Function: dequeue QUEUE

Removes an element from QUEUE, returning the
element.

After this function returns, FULL? must return false.

It is the caller’s responsibility to determine whether QUEUE has an element available for reading. The consequences are undefined if it doesn’t.

Most implementations will take constant time.

Package

jpl-queues

Source

interface.lisp (file)

Methods
Method: dequeue (QUEUE synchronized-queue)
Source

synchronized.lisp (file)

Method: dequeue (QUEUE unbounded-random-queue)
Source

unbounded-random.lisp (file)

Method: dequeue (QUEUE unbounded-fifo-queue)
Source

unbounded-fifo.lisp (file)

Method: dequeue (QUEUE bounded-fifo-queue)
Source

bounded-fifo.lisp (file)

Generic Function: dequeue-object OBJECT QUEUE &key TEST KEY

Prematurely dequeues OBJECT from QUEUE.

TEST is a function of two arguments that is used to compare OBJECT with the result of KEY applied to each enqueued element. When TEST returns true, the element is deleted. Zero or more elements may be matched and removed.

If anything was actually removed, FULL? must return false.

Most implementations will have the same time complexity as DELETE-OBJECT-IF.

Package

jpl-queues

Source

interface.lisp (file)

Methods
Method: dequeue-object OBJECT (QUEUE synchronized-queue) &key TEST KEY
Source

synchronized.lisp (file)

Method: dequeue-object OBJECT (QUEUE queue) &key TEST KEY
Generic Function: dequeue-object-if PREDICATE QUEUE &key KEY

Prematurely dequeues elements from QUEUE that
PREDICATE returns true for.

PREDICATE is called with the result of KEY applied to each enqueued element. When PREDICATE returns true, the element is deleted. Zero or more elements may be matched and removed.

If anything was actually removed, FULL? must return false.

Most implementations will take time in linear proportion to the number of enqueued elements.

Package

jpl-queues

Source

interface.lisp (file)

Methods
Method: dequeue-object-if PREDICATE (QUEUE synchronized-queue) &key KEY
Source

synchronized.lisp (file)

Method: dequeue-object-if PREDICATE (QUEUE unbounded-random-queue) &key KEY
Source

unbounded-random.lisp (file)

Method: dequeue-object-if PREDICATE (QUEUE unbounded-fifo-queue) &key KEY
Source

unbounded-fifo.lisp (file)

Method: dequeue-object-if PREDICATE (QUEUE bounded-fifo-queue) &key KEY
Source

bounded-fifo.lisp (file)

Generic Function: empty? QUEUE

Returns a boolean indicating whether the given
QUEUE cannot have any more elements dequeued from it. When this function returns false, it is safe to call DEQUEUE.

Most implementations will take constant time.

Package

jpl-queues

Source

interface.lisp (file)

Methods
Method: empty? (QUEUE synchronized-queue)
Source

synchronized.lisp (file)

Method: empty? (QUEUE queue)
Generic Function: enqueue OBJECT QUEUE

Writes OBJECT to QUEUE.

After this function returns, EMPTY? must return false.

It is the caller’s responsibility to determine whether QUEUE has room for another element. The consequences are undefined if it doesn’t.

Most implementations will take constant time.

Package

jpl-queues

Source

interface.lisp (file)

Methods
Method: enqueue OBJECT (QUEUE synchronized-queue)
Source

synchronized.lisp (file)

Method: enqueue OBJECT (QUEUE unbounded-random-queue)
Source

unbounded-random.lisp (file)

Method: enqueue OBJECT (QUEUE unbounded-fifo-queue)
Source

unbounded-fifo.lisp (file)

Method: enqueue OBJECT (QUEUE lossy-bounded-fifo-queue) before
Source

lossy-bounded-fifo.lisp (file)

Method: enqueue OBJECT (QUEUE bounded-fifo-queue)
Source

bounded-fifo.lisp (file)

Generic Function: full? QUEUE

Returns a boolean indicating whether the given
QUEUE cannot have any more elements enqueued to it. When this function returns false, it is safe to call ENQUEUE.

This is subtly different than saying its SIZE is equal to its CAPACITY: a lossy queue may have a capacity, and it may be "full" in that sense, but it will still accept new elements to be enqueued.

Most implementations will take constant time.

Package

jpl-queues

Source

interface.lisp (file)

Methods
Method: full? (QUEUE synchronized-queue)
Source

synchronized.lisp (file)

Method: full? (QUEUE lossy-bounded-fifo-queue)
Source

lossy-bounded-fifo.lisp (file)

Method: full? (QUEUE queue)
Generic Function: size QUEUE

Returns the number of elements stored in QUEUE.

Most implementations will take constant time.

Package

jpl-queues

Source

interface.lisp (file)

Methods
Method: size (QUEUE synchronized-queue)
Source

synchronized.lisp (file)

Method: size (QUEUE unbounded-random-queue)
Source

unbounded-random.lisp (file)

Method: size (UNBOUNDED-FIFO-QUEUE unbounded-fifo-queue)

The number of elements in BUFFER.

Source

unbounded-fifo.lisp (file)

Method: size (BOUNDED-FIFO-QUEUE bounded-fifo-queue)

The number of elements queued in BUFFER.

Source

bounded-fifo.lisp (file)


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

4.1.2 Classes

Class: bounded-fifo-queue ()

A bounded FIFO queue. The queue capacity (a
positive integer less than ARRAY-DIMENSION-LIMIT) must be specified with the :CAPACITY keyword parameter.

Space usage is constant after instantiation, in proportion to the capacity. Conses little, if at all, for any operation.

Package

jpl-queues

Source

bounded-fifo.lisp (file)

Direct superclasses

queue (class)

Direct subclasses

lossy-bounded-fifo-queue (class)

Direct methods
Direct slots
Slot: buffer

A ring buffer of elements, oldest first, that have yet to be read.

Type

vector

Slot: size

The number of elements queued in BUFFER.

Type

jpl-util:array-dimension

Initform

0

Readers

size (generic function)

Slot: start

The index into BUFFER of its oldest element.

Type

jpl-util:array-index

Initform

0

Class: lossy-bounded-fifo-queue ()

A bounded FIFO queue that throws away old entries
when ENQUEUE is called and the queue is full. A queue capacity (a positive integer less than ARRAY-DIMENSION-LIMIT) must be specified with the :CAPACITY keyword parameter.

Space usage is constant after instantiation, in proportion to the capacity. Conses little, if at all, for any operation.

Package

jpl-queues

Source

lossy-bounded-fifo.lisp (file)

Direct superclasses

bounded-fifo-queue (class)

Direct methods
Class: queue ()

Abstract class for queues.

Unless noted otherwise, subclasses do no synchronization. It is the client’s responsibility to ensure no two operations occur simultaneously.

The usual time complexity for each operation is documented in the generic function for the operation. Per-method exceptions should be documented.

Package

jpl-queues

Source

interface.lisp (file)

Direct superclasses

standard-object (class)

Direct subclasses
Direct methods
Class: synchronized-queue ()

Wraps another QUEUE (given by the :QUEUE keyword
parameter), synchronizing operations for safe multithreaded access. After instantiating this queue, the wrapped QUEUE must not be directly used for the duration of this queue.

When ENQUEUE is called on this QUEUE and the wrapped QUEUE is full, blocks until it is no longer full. When DEQUEUE is called on this QUEUE and the wrapped QUEUE is empty, blocks until it is no longer empty. This blocking also ensures that the internal state of the wrapped QUEUE won’t become corrupt by calling DEQUEUE when empty or ENQUEUE when full.

Operations that should return no useful value will return no values.

The time and space complexity for this queue and all its operations are equal to those of the wrapped QUEUE, plus any locking overhead imposed by the system, except that ENQUEUE and DEQUEUE may block indefinitely.

Package

jpl-queues

Source

synchronized.lisp (file)

Direct superclasses

queue (class)

Direct methods
Direct slots
Slot: queue

The wrapped QUEUE for which operations are synchronized.

Type

jpl-queues:queue

Initargs

:queue

Initform

(error "must specify :queue.")

Slot: lock

The LOCK which must be held during each operation.

Initform

(bordeaux-threads:make-lock)

Slot: enqueued

Condition variable that is notified each time an element has been enqueued.

Initform

(bordeaux-threads:make-condition-variable)

Slot: dequeued

Condition variable that is notified each time an element has been dequeued.

Initform

(bordeaux-threads:make-condition-variable)

Class: unbounded-fifo-queue ()

An unbounded FIFO queue.

Space usage is proportional to the number of queued elements at any given point in time. Conses for each enqueued element.

Package

jpl-queues

Source

unbounded-fifo.lisp (file)

Direct superclasses

queue (class)

Direct methods
Direct slots
Slot: buffer

A list of elements, oldest first, that have
yet to be read.

The cells of the list do not share structure with anything outside the queue.

Type

list

Initform

(quote nil)

Readers

buffer (generic function)

Slot: last-cell

The last cons cell of BUFFER, or NIL if BUFFER is empty.

Type

(or cons null)

Slot: size

The number of elements in BUFFER.

Type

(integer 0)

Initform

0

Readers

size (generic function)

Class: unbounded-random-queue ()

A virtually unbounded, random-order
queue. (Strictly speaking, the queue size is limited by ARRAY-DIMENSION-LIMIT.)

Space usage is proportional to the peak number of queued elements over the lifetime of the queue. An initial queue capacity (a positive integer less than ARRAY-DIMENSION-LIMIT) may optionally be specified with the :CAPACITY keyword parameter; the capacity will be grown as required. Conses for an enqueued element only when the current queue capacity is reached and needs to be extended.

Package

jpl-queues

Source

unbounded-random.lisp (file)

Direct superclasses

queue (class)

Direct methods
Direct slots
Slot: buffer

A buffer of elements, in unspecified order, that have yet to be read.

Type

vector


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

4.2 Internal definitions


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

4.2.1 Functions

Function: test-bounded-fifo-queue-dequeue-object-if LIST-LENGTH
Package

jpl-queues

Source

bounded-fifo.lisp (file)


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

4.2.2 Generic functions

Generic Function: buffer OBJECT
Package

jpl-queues

Methods
Method: buffer (UNBOUNDED-FIFO-QUEUE unbounded-fifo-queue)

A list of elements, oldest first, that have
yet to be read.

The cells of the list do not share structure with anything outside the queue.

Source

unbounded-fifo.lisp (file)


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

Appendix A Indexes


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

A.1 Concepts

Jump to:   F   J   L  
Index Entry  Section

F
File, Lisp, jpl-queues.asd: The jpl-queues<dot>asd file
File, Lisp, jpl-queues/bounded-fifo.lisp: The jpl-queues/bounded-fifo<dot>lisp file
File, Lisp, jpl-queues/interface.lisp: The jpl-queues/interface<dot>lisp file
File, Lisp, jpl-queues/lossy-bounded-fifo.lisp: The jpl-queues/lossy-bounded-fifo<dot>lisp file
File, Lisp, jpl-queues/package.lisp: The jpl-queues/package<dot>lisp file
File, Lisp, jpl-queues/synchronized.lisp: The jpl-queues/synchronized<dot>lisp file
File, Lisp, jpl-queues/unbounded-fifo.lisp: The jpl-queues/unbounded-fifo<dot>lisp file
File, Lisp, jpl-queues/unbounded-random.lisp: The jpl-queues/unbounded-random<dot>lisp file

J
jpl-queues.asd: The jpl-queues<dot>asd file
jpl-queues/bounded-fifo.lisp: The jpl-queues/bounded-fifo<dot>lisp file
jpl-queues/interface.lisp: The jpl-queues/interface<dot>lisp file
jpl-queues/lossy-bounded-fifo.lisp: The jpl-queues/lossy-bounded-fifo<dot>lisp file
jpl-queues/package.lisp: The jpl-queues/package<dot>lisp file
jpl-queues/synchronized.lisp: The jpl-queues/synchronized<dot>lisp file
jpl-queues/unbounded-fifo.lisp: The jpl-queues/unbounded-fifo<dot>lisp file
jpl-queues/unbounded-random.lisp: The jpl-queues/unbounded-random<dot>lisp file

L
Lisp File, jpl-queues.asd: The jpl-queues<dot>asd file
Lisp File, jpl-queues/bounded-fifo.lisp: The jpl-queues/bounded-fifo<dot>lisp file
Lisp File, jpl-queues/interface.lisp: The jpl-queues/interface<dot>lisp file
Lisp File, jpl-queues/lossy-bounded-fifo.lisp: The jpl-queues/lossy-bounded-fifo<dot>lisp file
Lisp File, jpl-queues/package.lisp: The jpl-queues/package<dot>lisp file
Lisp File, jpl-queues/synchronized.lisp: The jpl-queues/synchronized<dot>lisp file
Lisp File, jpl-queues/unbounded-fifo.lisp: The jpl-queues/unbounded-fifo<dot>lisp file
Lisp File, jpl-queues/unbounded-random.lisp: The jpl-queues/unbounded-random<dot>lisp file

Jump to:   F   J   L  

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

A.2 Functions

Jump to:   B   C   D   E   F   G   M   S   T  
Index Entry  Section

B
buffer: Internal generic functions
buffer: Internal generic functions

C
capacity: Exported generic functions
capacity: Exported generic functions
capacity: Exported generic functions
capacity: Exported generic functions
capacity: Exported generic functions

D
dequeue: Exported generic functions
dequeue: Exported generic functions
dequeue: Exported generic functions
dequeue: Exported generic functions
dequeue: Exported generic functions
dequeue-object: Exported generic functions
dequeue-object: Exported generic functions
dequeue-object: Exported generic functions
dequeue-object-if: Exported generic functions
dequeue-object-if: Exported generic functions
dequeue-object-if: Exported generic functions
dequeue-object-if: Exported generic functions
dequeue-object-if: Exported generic functions

E
empty?: Exported generic functions
empty?: Exported generic functions
empty?: Exported generic functions
enqueue: Exported generic functions
enqueue: Exported generic functions
enqueue: Exported generic functions
enqueue: Exported generic functions
enqueue: Exported generic functions
enqueue: Exported generic functions

F
full?: Exported generic functions
full?: Exported generic functions
full?: Exported generic functions
full?: Exported generic functions
Function, test-bounded-fifo-queue-dequeue-object-if: Internal functions

G
Generic Function, buffer: Internal generic functions
Generic Function, capacity: Exported generic functions
Generic Function, dequeue: Exported generic functions
Generic Function, dequeue-object: Exported generic functions
Generic Function, dequeue-object-if: Exported generic functions
Generic Function, empty?: Exported generic functions
Generic Function, enqueue: Exported generic functions
Generic Function, full?: Exported generic functions
Generic Function, size: Exported generic functions

M
Method, buffer: Internal generic functions
Method, capacity: Exported generic functions
Method, capacity: Exported generic functions
Method, capacity: Exported generic functions
Method, capacity: Exported generic functions
Method, dequeue: Exported generic functions
Method, dequeue: Exported generic functions
Method, dequeue: Exported generic functions
Method, dequeue: Exported generic functions
Method, dequeue-object: Exported generic functions
Method, dequeue-object: Exported generic functions
Method, dequeue-object-if: Exported generic functions
Method, dequeue-object-if: Exported generic functions
Method, dequeue-object-if: Exported generic functions
Method, dequeue-object-if: Exported generic functions
Method, empty?: Exported generic functions
Method, empty?: Exported generic functions
Method, enqueue: Exported generic functions
Method, enqueue: Exported generic functions
Method, enqueue: Exported generic functions
Method, enqueue: Exported generic functions
Method, enqueue: Exported generic functions
Method, full?: Exported generic functions
Method, full?: Exported generic functions
Method, full?: Exported generic functions
Method, size: Exported generic functions
Method, size: Exported generic functions
Method, size: Exported generic functions
Method, size: Exported generic functions

S
size: Exported generic functions
size: Exported generic functions
size: Exported generic functions
size: Exported generic functions
size: Exported generic functions

T
test-bounded-fifo-queue-dequeue-object-if: Internal functions

Jump to:   B   C   D   E   F   G   M   S   T  

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

A.3 Variables

Jump to:   B   D   E   L   Q   S  
Index Entry  Section

B
buffer: Exported classes
buffer: Exported classes
buffer: Exported classes

D
dequeued: Exported classes

E
enqueued: Exported classes

L
last-cell: Exported classes
lock: Exported classes

Q
queue: Exported classes

S
size: Exported classes
size: Exported classes
Slot, buffer: Exported classes
Slot, buffer: Exported classes
Slot, buffer: Exported classes
Slot, dequeued: Exported classes
Slot, enqueued: Exported classes
Slot, last-cell: Exported classes
Slot, lock: Exported classes
Slot, queue: Exported classes
Slot, size: Exported classes
Slot, size: Exported classes
Slot, start: Exported classes
start: Exported classes

Jump to:   B   D   E   L   Q   S  

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

A.4 Data types

Jump to:   B   C   J   L   P   Q   S   U  
Index Entry  Section

B
bounded-fifo-queue: Exported classes

C
Class, bounded-fifo-queue: Exported classes
Class, lossy-bounded-fifo-queue: Exported classes
Class, queue: Exported classes
Class, synchronized-queue: Exported classes
Class, unbounded-fifo-queue: Exported classes
Class, unbounded-random-queue: Exported classes

J
jpl-queues: The jpl-queues system
jpl-queues: The jpl-queues package

L
lossy-bounded-fifo-queue: Exported classes

P
Package, jpl-queues: The jpl-queues package

Q
queue: Exported classes

S
synchronized-queue: Exported classes
System, jpl-queues: The jpl-queues system

U
unbounded-fifo-queue: Exported classes
unbounded-random-queue: Exported classes

Jump to:   B   C   J   L   P   Q   S   U