The jpl-queues Reference Manual

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 4.0 beta 2 "William Riker" on Mon Aug 15 04:54:57 2022 GMT+0.

Table of Contents


1 Systems

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


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

1.1 jpl-queues

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

Maintainer

J.P. Larocque

Author

J.P. Larocque

License

ISC-style permissive

Version

0.1

Dependencies
  • bordeaux-threads (system).
  • jpl-util (system)., at least version "0.2"
Source

jpl-queues.asd.

Child Components

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   [Contents][Index]

2.1.1 jpl-queues/jpl-queues.asd

Source

jpl-queues.asd.

Parent Component

jpl-queues (system).

ASDF Systems

jpl-queues.


2.1.2 jpl-queues/interface.lisp

Dependency

package.lisp (file).

Source

jpl-queues.asd.

Parent Component

jpl-queues (system).

Public Interface

2.1.3 jpl-queues/bounded-fifo.lisp

Dependencies
Source

jpl-queues.asd.

Parent Component

jpl-queues (system).

Public Interface
Internals

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


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

Dependencies
Source

jpl-queues.asd.

Parent Component

jpl-queues (system).

Public Interface

2.1.5 jpl-queues/unbounded-fifo.lisp

Dependencies
Source

jpl-queues.asd.

Parent Component

jpl-queues (system).

Public Interface
Internals

buffer (reader method).


2.1.6 jpl-queues/unbounded-random.lisp

Dependencies
Source

jpl-queues.asd.

Parent Component

jpl-queues (system).

Public Interface

2.1.7 jpl-queues/synchronized.lisp

Dependencies
Source

jpl-queues.asd.

Parent Component

jpl-queues (system).

Public Interface

2.1.8 jpl-queues/package.lisp

Source

jpl-queues.asd.

Parent Component

jpl-queues (system).

Packages

jpl-queues.


3 Packages

Packages are listed by definition order.


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

3.1 jpl-queues

Source

package.lisp.

Use List

common-lisp.

Public Interface
Internals

4 Definitions

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


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

4.1 Public Interface


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.

Methods
Method: capacity ((queue synchronized-queue))
Source

synchronized.lisp.

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

unbounded-random.lisp.

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

unbounded-fifo.lisp.

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

bounded-fifo.lisp.

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.

Methods
Method: dequeue ((queue synchronized-queue))
Source

synchronized.lisp.

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

unbounded-random.lisp.

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

unbounded-fifo.lisp.

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

bounded-fifo.lisp.

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.

Methods
Method: dequeue-object (object (queue synchronized-queue) &key test key)
Source

synchronized.lisp.

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.

Methods
Method: dequeue-object-if (predicate (queue synchronized-queue) &key key)
Source

synchronized.lisp.

Method: dequeue-object-if (predicate (queue unbounded-random-queue) &key key)
Source

unbounded-random.lisp.

Method: dequeue-object-if (predicate (queue unbounded-fifo-queue) &key key)
Source

unbounded-fifo.lisp.

Method: dequeue-object-if (predicate (queue bounded-fifo-queue) &key key)
Source

bounded-fifo.lisp.

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.

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

synchronized.lisp.

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.

Methods
Method: enqueue (object (queue synchronized-queue))
Source

synchronized.lisp.

Method: enqueue (object (queue unbounded-random-queue))
Source

unbounded-random.lisp.

Method: enqueue (object (queue unbounded-fifo-queue))
Source

unbounded-fifo.lisp.

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

lossy-bounded-fifo.lisp.

Method: enqueue (object (queue bounded-fifo-queue))
Source

bounded-fifo.lisp.

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.

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

synchronized.lisp.

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

lossy-bounded-fifo.lisp.

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.

Methods
Method: size ((queue synchronized-queue))
Source

synchronized.lisp.

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

unbounded-random.lisp.

Reader Method: size ((unbounded-fifo-queue unbounded-fifo-queue))

The number of elements in BUFFER.

Source

unbounded-fifo.lisp.

Target Slot

size.

Reader Method: size ((bounded-fifo-queue bounded-fifo-queue))

The number of elements queued in BUFFER.

Source

bounded-fifo.lisp.

Target Slot

size.


4.1.2 Standalone methods

Method: initialize-instance :after ((queue bounded-fifo-queue) &key capacity &allow-other-keys)
Source

bounded-fifo.lisp.

Method: initialize-instance :after ((queue unbounded-random-queue) &key capacity &allow-other-keys)
Source

unbounded-random.lisp.

Method: print-object ((queue bounded-fifo-queue) stream)
Source

bounded-fifo.lisp.

Method: print-object ((queue synchronized-queue) stream)
Source

synchronized.lisp.


4.1.3 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.

Direct superclasses

queue.

Direct subclasses

lossy-bounded-fifo-queue.

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.

Writers

This slot is read-only.

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.

Direct superclasses

bounded-fifo-queue.

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.

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.

Direct superclasses

queue.

Direct methods
Direct slots
Slot: queue

The wrapped QUEUE for which operations are synchronized.

Type

jpl-queues:queue

Initform

(error "must specify :queue.")

Initargs

: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.

Direct superclasses

queue.

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.

Writers

This slot is read-only.

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.

Writers

This slot is read-only.

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.

Direct superclasses

queue.

Direct methods
Direct slots
Slot: buffer

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

Type

vector


4.2 Internals


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

4.2.1 Ordinary functions

Function: test-bounded-fifo-queue-dequeue-object-if (list-length)
Package

jpl-queues.

Source

bounded-fifo.lisp.


4.2.2 Generic functions

Generic Reader: buffer (object)
Package

jpl-queues.

Methods
Reader 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.

Target Slot

buffer.


Appendix A Indexes


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

A.1 Concepts


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

A.2 Functions

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

B
buffer: Private generic functions
buffer: Private generic functions

C
capacity: Public generic functions
capacity: Public generic functions
capacity: Public generic functions
capacity: Public generic functions
capacity: Public generic functions

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

E
empty?: Public generic functions
empty?: Public generic functions
empty?: Public generic functions
enqueue: Public generic functions
enqueue: Public generic functions
enqueue: Public generic functions
enqueue: Public generic functions
enqueue: Public generic functions
enqueue: Public generic functions

F
full?: Public generic functions
full?: Public generic functions
full?: Public generic functions
full?: Public generic functions
Function, test-bounded-fifo-queue-dequeue-object-if: Private ordinary functions

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

I
initialize-instance: Public standalone methods
initialize-instance: Public standalone methods

M
Method, buffer: Private generic functions
Method, capacity: Public generic functions
Method, capacity: Public generic functions
Method, capacity: Public generic functions
Method, capacity: Public generic functions
Method, dequeue: Public generic functions
Method, dequeue: Public generic functions
Method, dequeue: Public generic functions
Method, dequeue: Public generic functions
Method, dequeue-object: Public generic functions
Method, dequeue-object: Public generic functions
Method, dequeue-object-if: Public generic functions
Method, dequeue-object-if: Public generic functions
Method, dequeue-object-if: Public generic functions
Method, dequeue-object-if: Public generic functions
Method, empty?: Public generic functions
Method, empty?: Public generic functions
Method, enqueue: Public generic functions
Method, enqueue: Public generic functions
Method, enqueue: Public generic functions
Method, enqueue: Public generic functions
Method, enqueue: Public generic functions
Method, full?: Public generic functions
Method, full?: Public generic functions
Method, full?: Public generic functions
Method, initialize-instance: Public standalone methods
Method, initialize-instance: Public standalone methods
Method, print-object: Public standalone methods
Method, print-object: Public standalone methods
Method, size: Public generic functions
Method, size: Public generic functions
Method, size: Public generic functions
Method, size: Public generic functions

P
print-object: Public standalone methods
print-object: Public standalone methods

S
size: Public generic functions
size: Public generic functions
size: Public generic functions
size: Public generic functions
size: Public generic functions

T
test-bounded-fifo-queue-dequeue-object-if: Private ordinary functions

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

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

A.4 Data types

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

B
bounded-fifo-queue: Public classes
bounded-fifo.lisp: The jpl-queues/bounded-fifo․lisp file

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

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

I
interface.lisp: The jpl-queues/interface․lisp file

J
jpl-queues: The jpl-queues system
jpl-queues: The jpl-queues package
jpl-queues.asd: The jpl-queues/jpl-queues․asd file

L
lossy-bounded-fifo-queue: Public classes
lossy-bounded-fifo.lisp: The jpl-queues/lossy-bounded-fifo․lisp file

P
Package, jpl-queues: The jpl-queues package
package.lisp: The jpl-queues/package․lisp file

Q
queue: Public classes

S
synchronized-queue: Public classes
synchronized.lisp: The jpl-queues/synchronized․lisp file
System, jpl-queues: The jpl-queues system

U
unbounded-fifo-queue: Public classes
unbounded-fifo.lisp: The jpl-queues/unbounded-fifo․lisp file
unbounded-random-queue: Public classes
unbounded-random.lisp: The jpl-queues/unbounded-random․lisp file

Jump to:   B   C   F   I   J   L   P   Q   S   U