data.queue - Queue ¶Provides a queue (FIFO). You can create a simple queue, which is lightweight but not thread-safe, or an MTqueue, a thread-safe queue. Basic queue operations work on both type of queues. When an mtqueue is passed to the procedures listed in this section, each operation is done in atomic way, unless otherwise noted.
There are also a set of procedures for mtqueues that can be used for thread synchronization; for example, you can let the consumer thread block if an mtqueue is empty, and/or the producer thread block if the number of items in the mtqueue reaches a specified limit. Using these procedures allows the program to use an mtqueue as a channel.
The simple queue API is a superset of SLIB’s queue implementation,
which supports not only enqueue! (add item to the end of the sequence)
and dequeue! (take item from the front of the sequence), but also
queue-push! (add item to the front of the sequence), so that
it can be used as a stack as well.
If you also want to take item from the end of the sequence in O(1),
you need a deque (double-ended queue).
See data.ring-buffer - Ring buffer, which works as an efficient (both speed and space)
dequeue on top of vectors. Or you can use immutable deques
provided by data.ideque (see data.ideque - Immutable deques).
See also scheme.list-queue (scheme.list-queue - R7RS list queues), which defines a
portable API for list-based queue.
| • Queue classes and constructors: | ||
| • Queue predicates: | ||
| • Queue basic operations: | ||
| • Queue other accessors: | ||
| • Queue as channel: |
{data.queue}
A class of simple queue.
<queue>: length ¶A read-only slot that returns the number of items in the queue.
{data.queue}
A class of mtqueue. Inherits <queue>.
<mtqueue>: max-length ¶The upper bound of the number of items in the queue.
If this slot is zero, the queue cannot hold any items, but works as a synchronization device. A writer will block until a reader appears to take the item; a reader will block until a writer appears to give the item.
<mtqueue>: closed ¶A boolean flag, set to #f initially.
If this is true, the queue no longer accepts a new
data by enqueue! etc. This slot is read-only and can only
be changed atomically by enqueue/wait!, queue-push/wait!,
dequeue/wait! and queue-pop/wait!.
This is useful when an mtqueue used as a channel is being shutdown.
{data.queue}
Creates and returns an empty simple queue.
{data.queue}
Creates and returns an empty mtqueue. When an integer is given
to the keyword argument max-length, it is used to
initialize the max-length slot.
{data.queue}
Returns a copy of the queue. If queue is an mtqueue,
a fresh mtqueue with the same content and max length is returned.
{data.queue}
Returns #t if obj is a queue (either a simple queue
or an mtqueue).
{data.queue}
Returns #t if obj is an mtqueue.
{data.queue}
Returns #t if obj is an empty queue.
{data.queue}
Add obj to the end of queue. You may give more than
one object, and each of them are enqueued in order.
If queue is an mtqueue, all the objects are enqueued
atomically; no other objects from other threads can be inserted
between the objects given to a single enqueue! call.
Besides, if the value of its max-length slot
has a positive finite value, and adding objs makes the number of
elements in queue exceeds max-length,
an error is signaled and queue won’t be modified.
(If max-length is zero, this procedure always fail.
Use enqueue/wait!. See Queue as channel, for the details.)
If queue is an mtqueue and it is closed, no change is made to it and an error is thrown.
{data.queue}
Add obj in front of queue. You may give more than
one object, and each of them are pushed in order.
Like enqueue!, when queue is an mtqueue,
all objects are added atomically, and the value of
max-length slot is checked. See enqueue! above
for the details.
{data.queue}
Like enqueue! and queue-push!, respectively, except that these
don’t modify queue if it already contains obj
(elements are compared by two-argument procedure eq-proc).
When queue is an mtqueue, all objects are added atomically,
and the value of
max-length slot is checked. See enqueue! above
for the details.
{data.queue}
Take one object from the front of the queue queue and returns it.
Both function works the same, but queue-pop! may be used to
emphasize it works with queue-push!.
If queue is empty, fallback is returned if given, otherwise an error is signaled.
If queue is an mtqueue and its max-length is zero,
the queue is always empty. Use dequeue/wait! to use
such a queue as an synchronization device.
{data.queue}
Returns the whole content of the queue by a list, with emptying
queue. If queue is already empty, returns an empty list.
See also queue->list (see Other queue accessors).
{data.queue}
Removes all items in the queue that satisfies pred.
Returns #t if any item is removed. Otherwise returns #f.
The order of arguments follows
remove in scheme.list
(see scheme.list - R7RS lists).
Note on portability:
Scheme48 has delete-from-queue!, which takes object to remove
rather than predicate, and also takes arguments in reversed order
(i.e. queue comes first). Avoid conflicting with that I intentionally
left out delete-from-queue!; it’s easy to write one in either
Scheme48 compatible way or consistent to SRFI-1 argument order.
{data.queue}
Returns the number of the items in the queue.
{data.queue}
Returns the maximum number of items the mtqueue can hold.
If the queue doesn’t have a limit, #f is returned.
{data.queue}
Returns the number of elements the mtqueue can accept at this moment
before it hits its maximum length. For example, if the queue
already has the maximum number of elements, 0 is returned.
If the queue doesn’t have the limit, +inf.0 is returned.
Note that even if this returns a non-zero finite value, subsequent
enqueue! may throw an error because of the queue being full.
It’s because another thread may put an item to the queue
between this procedure call and enqueue!. To avoid
this situation, use enqueue/wait! to insert item
to mtqueue with finite max-length.
{data.queue}
Returns the number of threads waiting on the mtqueue to read
at this moment.
The return value is always a nonnegative exact integer.
Note that the value might change between this procedure’s returning the value and your checking it, if some other thread inserts an element into the queue. To use the value reliably, you need another mutex to restrict putting items in the queue.
(define q (make-mtqueue)) (thread-start! (make-thread (^[] (dequeue/wait! q)))) (mtqueue-num-waiting-readers q) ⇒ 1 (enqueue! q 'a) (mtqueue-num-waiting-readers q) ⇒ 0
{data.queue}
Peek the head or the tail of the queue and returns the object, respectively.
The queue itself is not modified.
If queue is empty, fallback is returned if it is given,
otherwise an error is signaled.
{data.queue}
Returns a new queue whose content is the elements in list,
in the given order.
By default the created queue is a simple queue, but you
can create mtqueue or instances of other subclasses of <queue>
by giving the class to the optional class arguments.
The optional initargs arguments are passed to the constructor
of class.
{data.queue}
Returns a list whose content is the items in the queue in order.
Unlike dequeue-all!, the content of queue remains intact.
In Gauche, queue->list copies the content of the queue to a
freshly allocated list, while dequeue-all! doesn’t copy but
directly returns the queue’s internal list. There are some Scheme
systems that has queue->list but doesn’t guarantee the content
is copied, so if you’re planning to share the code among these
implementations, it’s better not to rely on the fact that
queue->list copies the content.
{data.queue}
Returns the first item in queue that satisfies a
predicate pred. The order of arguments follows
find (see Other list procedures).
{data.queue}
Like any in SRFI-1, apply pred on each item
in queue until it evaluates true, and returns that
true value (doesn’t necessarily be #t). If no
items in the queue satisfies pred, #f is returned.
{data.queue}
Like every in SRFI-1, apply pred on each item
in queue. If pred returns #f, stops
iteration and returns #f immediately.
Otherwise, returns the result of the application of
pred on the last item of the queue. If the queue
is empty, #t is returned.
Mtqueues can be used as a communication channel between threads
to implement producer-consumer pattern. Using enqueue/wait!,
the producer is suspended when the queue is full, until
the consumer reads the items to make room. Using dequeue/wait!,
the consumer is suspended when the queue is empty, until
the producer make items available.
You can specify timeouts for those procedures as well, in case some threads got stuck.
{data.queue}
Insert obj to mtqueue. Like enqueue! and
queue-push!, euqueue/wait! inserts obj at the
end of the queue (so that it will be retrieved after existing
items are dequeued), while queue-push/wait! inserts obj
at the beginning of the queue (so that it will be retrieved
next call of dequeue).
If the queue is full, the caller is blocked. The caller is unblocked when items are taken, or the timeout reaches.
The optional timeout argument specifies the timeout condition.
If it is #f, those procedures wait indefinitely.
If it is a real number, they wait at least the given number of
seconds. If it is a <time> object (see Time),
they wait until the absolute point of time the argument specifies.
In case the call is blocked then timed out, the value of
timeout-val is returned, which defaults to #f.
When enqueue/wait! and queue-push/wait! succeeds
without hitting timeout, they return #t.
The last optinoal argument, close, closes the queue if it is given
and true. The close operation is done atomically, and if you’re calling
enqueue/wait! or queue-push/wait!, obj is guaranteed
to be the last item put in the queue. It effectively “shut down”
the channel.
If mtqueue is already closed, an error is raised without modifying the queue. The check and queue insertion is done atomically, to eliminate the possibility that other thread tries to enqueue between the check and insetion.
{data.queue}
Remove one item from the head of the queue and returns it.
Both procedures works exactly the same. You can use dequeue/wait!
to pair with enqueue/wait!, and queue-pop/wait!
with queue-push/wait!, for clarity.
The caller thread would block if the queue is empty. The blocked caller thread is unblockedeither when the blocking condition is resolved, or the timeout condition is met.
See the enqueue/wait! entry above for the meaning of
timeout, timeout-val, and close arguments.
{data.queue}
Closes the mtqueue without inserting or retrieving objects.
If the mtqueue is closed, it does nothing.