11.53 util.queue - キュー

Module: util.queue

キュー(FIFO)機能を提供します。 極めて軽量ですがスレッドセーフでないシンプルなキューと、 スレッドセーフなmtqueueがあります。基本的なキュー操作手続きは どちらのキューに対しても使うことができます。本節で説明されている 手続きをmtqueueに適用した場合、特に断りが無い限り、操作は アトミックに行われます。

また、スレッド間同期に使えるmtqueue用の手続きも用意されています。 例えばキューが空の時に読み出しスレッドをブロックさせたり キューの長さが指定値に達した場合に書き込みスレッドをブロックさせることができ、 いわゆる「チャネル」としてキューを使うことができます。

シンプルキューのAPIはSLIBのキュー実装の上位互換になっています。

Class: <queue>

シンプルなキューのクラスです。

Instance Variable of <queue>: length

キュー中の要素の数を返す、読み取り専用のスロットです。

Class: <mtqueue>

mtqueueのクラスです。<queue>を継承しています。

Instance Variable of <mtqueue>: max-length

キュー中の要素数の上限を示します。

このスロットが0の場合、キューは要素を中に持つことはできませんが、同期デバイスとして動作します。 書き込みスレッドは、その要素を受け取る読み出しスレッドが現れるまでブロックし、 読み出しスレッドは、要素を渡してくれる書き込みスレッドが現れるまでブロックします。

Function: make-queue

空のシンプルなキューを作って返します。

Function: make-mtqueue &key max-length

空のmtqueueを作って返します。整数がmax-lengthに与えられた場合は、 それがmax-lengthスロットの値となります (ゼロは無制限を意味します)。

Function: queue? obj

objがキューであれば(シンプルなキューでもmtqueueでも)#tを返します。

Function: mtqueue? obj

objがmtqueueであれば#tを返します。

Function: queue-empty? queue

objが空のキューであれば#tを返します。

Function: queue-length queue

キューの中にある要素の数を返します。

Function: mtqueue-max-length mtqueue

キューが保持できる要素の最大数を返します。限度がない場合はゼロが返ります。

Function: mtqueue-room mtqueue

保持できる最大容量に達するまであといくつ要素を受け入れることができるかを 示す整数を返します。例えば、既にキューがいっぱいであれば0が返ります。 キューに最大容量が設定されていなければ+inf.0が返ります。

Function: copy-queue queue

キューqueueのコピーを返します。

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

objをキューqueueの末尾に追加します。 一つ以上のobjを与えることができ、その場合はそれらが順にenqueueされます。

queueがmtqueueの場合、渡されたオブジェクト全ての追加は アトミックに行われます。すなわち、途中に別スレッドが要素を挿入する ことはありません。さらに、max-lengthスロットが正の値を 持っており、このenqueue!の実行によってキューの要素数が max-lengthを越えることになる場合は、queueは 変更されずエラーとなります。 (max-lengthがゼロの場合、この手続きは常にエラーとなります。 下に説明するenqueue/wait!を使ってください。)

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

objをキューqueueの先頭に追加します。 一つ以上のobjを与えることができ、その場合はそれらが順にpushされます。

enqueue!と同様に、queueがmtqueueの場合は 全てのオブジェクトはアトミックに追加され、またmax-lengthの値も チェックされます。詳しくは上のenqueue!の説明を参照してください。

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

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

objが既にqueueの中に含まれている場合にはqueueを 変更しないことを以外には、enqueue!およびqueue-push!と同じ 動作をします。objが含まれているかどうかの検査は 2引数の関数eq-procで行います。

queueがmtqueueの場合は 全てのオブジェクトはアトミックに追加され、またmax-lengthの値も チェックされます。詳しくは上のenqueue!の説明を参照してください。

Function: dequeue! queue :optional fallback

Function: queue-pop! queue :optional fallback

キューqueueの先頭からひとつ要素を取って返します。 二つの手続きは全く同じ動作をします。queue-pop!はqueue-push!と ペアで使われていることを強調したいときに使うと良いでしょう。

キューが空の場合は、fallbackが与えられていればそれが返され、 そうでなければエラーが報告されます。

キューがmtqueueでそのmax-lengthがゼロの場合、 キューは常に空であるとみなされます。ゼロ長のキューを同期デバイスとして 使う場合はdequeue/wait!を使ってください。

Function: dequeue-all! queue

キューの全ての内容をリストにして返します。キューそのものは空になります。 キューが既に空の場合は空リストが返されます。 下のqueue->listも参照してください。

Function: queue-front queue :optional fallback

Function: queue-rear queue :optional fallback

キューqueueの先頭もしくは末尾の要素を返します。キューそのものは変更されません。 キューが空の場合、fallbackが与えられていればその値を返し、 そうでなければエラーを報告します。

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

与えられたリストlistの各要素をその順で持つようなキューを作成して返します。

デフォルトではシンプルキューが作られますが、classに<class>の サブクラスを渡すことで他のキュークラスのインスタンスを作ることができます。 initargsはclassのコンストラクタに渡されます。

Function: queue->list queue

キューqueueの内容をリストにして返します。 dequeue-all!と異なり、キューそのものの内容は変化しません。

Gaucheではqueue->listは新しいリストをアロケートしてキューの 内容をコピーします (dequeue-all!はコピーをせずにキューの内部の リストをそのまま返します)。組込みでqueue->listを持っているScheme 実装がいくつかありますが、その中にはqueue->listがキューの 内容をコピーすることを保証していないものがあるので、それらの処理系と 共有するコードではqueue->listがリストをコピーすることを あてにしない方が良いでしょう。

Function: find-in-queue pred queue

キュー内の要素のうち述語predを満たす最初の要素を返します。 引数の順序はfindに揃えました (他のリスト手続き参照)。

Function: any-in-queue pred queue

SRFI-1のanyのように、queue中の各要素に 順にpredを適用し、それが真の値 (#tである必要はありません) に 評価されたらその値を返します。predを満たす要素が無ければ#fが 返ります。

Function: every-in-queue pred queue

SRFI-1のeveryのように、queue中の各要素に 順にpredを適用し、それが#fを返したらすぐ#fを返します。 predに対し#fを返す要素が無ければ、最後の要素にpredを 適用した結果が返ります。キューが空なら#fが返ります。

Function: remove-from-queue! pred queue

キューから、述語predを満たす要素を全て取り除きます。 要素が削除された場合は#tが、そうでなければ#fが返されます。 引数の順序はSRFI-1のremoveに揃えました (SRFI-1 リスト操作関数参照)。

移植性に関する註：Scheme48には、述語ではなく削除するオブジェクトそのものを取る delete-from-queue!がありますが、引数の順序が逆(キューが先)になっています。 まぎらわしい衝突を避けるため、敢えてdelete-from-queue!は 提供しませんでした。remove-from-queue!を使えば、Scheme48互換の方法でも、 あるいはSRFI-1と一貫性のある方法でもdelete-from-queue!を簡単に書けるでしょう。

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

これらの手続きはmtqueueに対して使うことができ、 スレッド間同期を実現できます。 enqueue/wait!とqueue-push/wait!は、 キューの要素数がmax-lengthを越える場合に、キューに空きができるまで、 dequeue/wait!とqueue-pop/wait!は、 キューが空の場合に、キューに要素が追加されるまで、 呼び出しスレッドをブロックします。

timeout引数で、ブロックされたスレッドのタイムアウトを指定することができます。 #fは指定しなかった場合と同じで、キューの状態が変化するまで 無期限に待ちます。実数が渡された場合はそれが秒数と解釈され、最低限 その時間経過するまでは待ちます。渡されたのが<time>オブジェクト (時間参照)である場合は、そのオブジェクトが指定する絶対時刻を 経過するまで待ちます。

タイムアウトによりブロックが解かれた場合は、timeout-valで 指定した値が返されます。timeout-valの省略時値は#fです。

enqueue/wait!とqueue-push/wait!は、 タイムアウトせずに操作が成功した場合は#tを返します。

This document was generated by Shiro Kawai on May 28, 2012 using texi2html 1.82.