This library provides deque (double-ended queue) data structure and its operations.
You can create a simple deque, which is not thread-safe, or an MT deque, a thread-safe deque. Basic deque operations work on both type of deques. When a mtdeque 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 mtdeques that can be used for thread synchronisation; for example, you can let the consumer thread block if an mtdeque is empty, and/or the producer thread block if the number of items in the mtdeque reaches a specified limit. Using these procedures allows the program to use an mtdeque as a channel.
NOTE: (util queue) is implemented using this library.
A class of simple deque.
A class of mtdeque. Inherits <deque>.
Creates and return an empty simple deque.
Creates and return an empty mtdeque.
The keyword argument max-length specifies the maximum entry count of the deque. Negative number indicates unlimited number of entry. If the given number is zero then the deque cannot hold any item.
Returns #t if obj is a deque (either a simple deque or an mtdeque).
Returns #t if obj is an mtdeque.
Returns #t if deque is an empty deque.
Returns the number of the items in the deque.
Returns the maximum number of items mtdeque can hold. #f indicates unlimited.
Returns the number of elements mtdeque can accept at this moment
before it hits its maximum length. If the deque has unlimited capacity then
the procedure returns +inf.0.
Returns a copy of deque.
Adds obj to the end of deque. You may give more than one object, and each of them are pushed in order.
If deque is an mtdeque, all the objects are pushed atomically; no
other objects from other threads can be inserted between the objects given
to a single deque-push! call. Besides, if the value of the result of
mtdeque-max-length is positive, and adding objs makes the
number of element in deque exceeds it, an error is raised and
deque won't be modified. (If the maximum length is zero, this procedure
always fail. Use deque-push/wait! below.)
Adds obj to in front of deque. You may give more than one object, and each of them are pushed in order.
Like deque-push!, when deque is an mtdeque, all objects are added
atomically, and the value of max length is checked. See deque-push! above
for more detail.
The name unshift is taken from Perl.
Like deque-push! and deque-unshift!, respectively, except
that these don't modify deque if it already contains objs (elements
are compared by two-argument procedure eq-proc).
When deque is an mtdeque, all objects are added atomically, and the max
length is checked. See deque-push! above for the detail.
Take one object from the end or the front of deque, respectively, and return it.
If deque is empty, fallback is returned if give, otherwise an error is raised.
If deque is mtdeque and its max length is zero, then the deque is
always empty. Use deque-pop/wait! or deque-shift/wait! to use
such a deque as a synchronisation device.
The name shift is take from Perl.
Returns the whole content of deque by a list, with emptying deque. If deque is empty, returns an empty list.
The the returning list of deque-pop-all! is constructed from the end
of queue and deque-shift-all!'s one is constructed from the front
of queue.
See also deque->list below.
Peek the head or the tail of deque and return the object, respectively.
If deque is empty, fallback is returned if give, otherwise an error is raised.
Returns a new deque which content is the elements in list, in the given order.
By default the created deque is a simple deque, but you can create mtdeque
or instance of other subclass <deque> by giving the class to the
optional class arguments. The optional initargs arguments are
passed to the constructor of class.
Returns a list whose content is the items in deque in order.
Unlike deque-shift-all!, the content of deque remains intact.
The returning list is a copy of the content. So modifying the list won't
affect deque.
Returns the first item in deque that satisfies a predicate pred.
Apply pred on each item in deque until it evaluates true, and returns that true value. If no item satisfies pred, #f is returned.
Apply pred on each item in deque. If pred returns #f, stops iteration and returns #f immediately. Otherwise, returns the result of pred on the last item of deque. If the deque is empty, #t is returned.
Removes all items in deque that satisfies pred. Returns #t if any item is removed. Otherwise #f.
These synchronising variants work on an mtdeque and make the caller
thread block when the mtdeque has reached its maximum length (for
deque-unshift/wait! and deque-push/wait!), or the mtdeque is empty
(for deque-shift/wait! and deque-pop/wait!). The blocked caller
thread is unblocked either the blocking condition is resolved, or the
timeout condition is met.
The optional timeout argument specifies the timeout condition. If it is #f, those procedure wait indefinitely. If it is a real number, they wait at least the given number of seconds.
In case the call is blocked then timed out, the value of timeout-val is returned, which default value is #t.
When deque-unshift/wait! and deque-push/wait! succeeds without
hitting timeout, they return #t.