For Gauche 0.9.5


Next: , Previous: , Up: Library modules - Utilities   [Contents][Index]

12.11 data.queue - Queue

Module: data.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 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 Immutable deques).

See also SRFI-117 (Queues based on lists), which defines a portable API for list-based queue.

Class: <queue>

A class of simple queue.

Instance Variable of <queue>: length

A read-only slot that returns the number of items in the queue.

Class: <mtqueue>

A class of mtqueue. Inherits <queue>.

Instance Variable of <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.

Function: make-queue

Creates and returns an empty simple queue.

Function: make-mtqueue :key max-length

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.

Function: queue? obj

Returns #t if obj is a queue (either a simple queue or an mtqueue).

Function: mtqueue? obj

Returns #t if obj is an mtqueue.

Function: queue-empty? queue

Returns #t if obj is an empty queue.

Function: queue-length queue

Returns the number of the items in the queue.

Function: mtqueue-max-length mtqueue

Returns the maximum number of items the mtqueue can hold. If the queue doesn’t have a limit, #f is returned.

Function: mtqueue-room mtqueue

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.

Function: mtqueue-num-waiting-readers mtqueue

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
Function: copy-queue queue

Returns a copy of the queue.

Function: enqueue! queue obj :optional more-objs …

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! below.)

Function: queue-push! queue obj :optional more-objs …

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.

Function: enqueue-unique! queue eq-proc obj :optional more-objs …
Function: queue-push-unique! queue eq-proc obj :optional more-objs …

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.

Function: dequeue! queue :optional fallback
Function: queue-pop! queue :optional fallback

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.

Function: dequeue-all! 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 below.

Function: queue-front queue :optional fallback
Function: queue-rear queue :optional fallback

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.

Function: list->queue list :optional class :rest initargs

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.

Function: queue->list 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.

Function: queue-internal-list queue

Like queue->list, returns a list whose content is the items in the queue in order, but the returned list may share the internal storage of queue. The returned list can be modified by subsequent operations of queue, and any modification on the list can make queue inconsistent.

Because of this danger, we don’t allow <mtqueue> to be passed to this procedure; it would signal an error if you do so.

If you just want to extract the accumulated result in queue without copying, consinder dequeue-all!, which is safe because it atomically resets the queue. Use this procedure only when you absolutely need to access the contents of the queue without taking them out.

Function: find-in-queue pred queue

Returns the first item in queue that satisfies a predicate pred. The order of arguments follows find (see Other list procedures).

Function: any-in-queue pred 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.

Function: every-in-queue pred 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.

Function: remove-from-queue! pred 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 SRFI-1 (see SRFI-1 List utilities).

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.

Function: enqueue/wait! mtqueue obj :optional timeout timeout-val
Function: queue-push/wait! mtqueue obj :optional timeout timeout-val
Function: dequeue/wait! mtqueue :optional timeout timeout-val
Function: queue-pop/wait! mtqueue :optional timeout timeout-val

These synchronizing variants work on an mtqueue and make the caller thread block when the mtqueue has reached its maximum length (for enqueue/wait! and queue-push/wait!), or the mtqueue is empty (for dequeue/wait! and queue-pop/wait!). The blocked caller thread is unblocked either when the blocking condition is resolved, or the timeout condition is met.

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.


Next: , Previous: , Up: Library modules - Utilities   [Contents][Index]