jpl-queues is a Common Lisp library implementing a few different kinds of queues.
These kinds of queues are provided:
Additionally, a synchronization wrapper is provided to make any queue conforming to the jpl-queues API thread-safe for lightweight multithreading applications. (See Calispel for a more sophisticated CL multithreaded message-passing library with timeouts and alternation among several blockable channels.)
jpl-queues is used by Calispel.
The latest version of jpl-queues, with accompanying documentation, can be found at: http://www.thoughtcrime.us/software/jpl-queues/
The most recent release is 0.1, released 2009-10-19. It depends on: cl-jpl-util 0.2, Bordeaux Threads
I sign all my software with OpenPGP, key ID 0xE979FFBEA002D20F, fingerprint A87B 1C5A 28C4 03BD 54BA CE8E E979 FFBE A002 D20F. (Releases were previously signed with 0x80555CED7394F948, which has been revoked, but not compromised. See my OpenPGP transition statement.)
The software and this document are licensed under permissive, BSD-like terms, copied from the ISC license:
Copyright © 2009, Jean-Paul Guy Larocque
Permission to use, copy, modify, and/or distribute this software for any purpose with or without fee is hereby granted, provided that the above copyright notice and this permission notice appear in all copies.
THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
Create a queue that can hold an unlimited number of elements in FIFO order, which is not permitted to drop elements:
(defparameter *queue* (make-instance 'jpl-queues:unbounded-fifo-queue))
Enqueue some elements:
(loop for i below 10
until (jpl-queues:full? *queue*)
doing (jpl-queues:enqueue i *queue*))(Note that because our queue is unbounded, the
FULL?
check is, strictly speaking, unnecessary. However, it's good
habit to check the queue first. Enqueuing to a full queue or
dequeuing from an empty queue may corrupt the queue's
state.)
Dequeue those elements:
(loop until (jpl-queues:empty? *queue*)
collecting (jpl-queues:dequeue *queue*))
=> (0 1 2 3 4 5 6 7 8 9)Several classes are available, each offering different queuing policies.
Queues can be classified in a few different dimensions:
Queues are created by
calling MAKE-INSTANCE
with the name of one of the concrete queue classes. The queue
classes are described below.
A queue stores values which are enqueued, to be dequeued at a later time.
The QUEUE abstract class cannot be directly
instantiated and used by itself. Clients must instantiate a
subclass that provides specific queuing policies, or
subclass QUEUE to implement their own queue
according to the jpl-queues API: see
Section 3.2, “The jpl-queues API”
Syntax.
(MAKE-INSTANCE'BOUNDED-FIFO-QUEUE&keyCAPACITY) => (ABOUNDED-FIFO-QUEUEinstance.)
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.
Syntax.
(MAKE-INSTANCE'UNBOUNDED-FIFO-QUEUE) => (AnUNBOUNDED-FIFO-QUEUEinstance.)
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.
Syntax.
(MAKE-INSTANCE'LOSSY-BOUNDED-FIFO-QUEUE&keyCAPACITY) => (ALOSSY-BOUNDED-FIFO-QUEUEinstance.)
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.
Syntax.
(MAKE-INSTANCE'UNBOUNDED-RANDOM-QUEUE&keyCAPACITY) => (AnUNBOUNDED-RANDOM-QUEUEinstance.)
A virtually unbounded, random-order queue. (Strictly
speaking, the queue size must be less than
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.
Syntax.
(MAKE-INSTANCE'SYNCHRONIZED-QUEUE&keyQUEUE) => (ASYNCHRONIZED-QUEUEinstance.)
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 be corrupted
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.
This section defines several generic functions that apply
to any instance of a concrete subclass
of QUEUE.
Unless operating on an instance of a subclass that is designed to support thread-safe access, no two operations may occur at the same time in a multithreaded scenario, or else either an incorrect or inconsistent answer may be returned, or the internal state of the queue may be corrupted.
Implementers of QUEUE subclasses are expected
to define methods for most of these functions. Some functions
have default methods which, for most QUEUE
subclasses, infer correct answers from other functions. Refer
to interface.lisp to find which functions
have default methods and what their semantics are.
Syntax.
(EMPTY?QUEUE) => boolean
EMPTY? 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.
Syntax.
(FULL?QUEUE) => boolean
FULL? 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.
Syntax.
(SIZEQUEUE) => (A non-negative integer.)
Returns the number of elements stored
in QUEUE.
Most implementations will take constant time.
Syntax.
(CAPACITYQUEUE) => (a non-negative integer, orNIL)
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.
Syntax.
(ENQUEUEOBJECTQUEUE) => (unspecified)
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.
Syntax.
(DEQUEUEQUEUE) =>OBJECT
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.
Syntax.
(DEQUEUE-OBJECTOBJECTQUEUE&keyTESTKEY) => (unspecified)
(DEQUEUE-OBJECT-IFPREDICATEQUEUE&keyKEY) => (unspecified)
Prematurely dequeues elements
from QUEUE.
DEQUEUE-OBJECT dequeues each
instance
of OBJECT. 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.
DEQUEUE-OBJECT-IF dequeues each
element 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
of DELETE-OBJECT will have the same
time complexity
as DELETE-OBJECT-IF.
Most implementations
of DELETE-OBJECT-IF will take time in
linear proportion to the number of enqueued elements.