12.19 data.queue - キュー

Module: data.queue ¶

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

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

シンプルキューのAPIはSLIBのキュー実装の上位互換になっています。 要素を並びの末尾に追加するenqueue!と、要素を並びの先頭から取り除く dequeue!だけでなく、要素を並びの先頭に追加するqueue-push!も 提供されているので、スタックとしても使えます。

要素を並びの末尾からO(1)で取り除くAPIも欲しい場合は、 deque (double-ended queue)が必要です。data.ring-bufferモジュール は、ベクタの上に実装された(空間的にも時間的にも)効率の良いdequeを提供しています (data.ring-buffer - リングバッファ参照)。また、変更不可な両端キューdata.ideque もあります(data.ideque - 変更不可な両端キュー参照)。

また、scheme.list-queueはポータブルなリストベースのキューのAPIを提供しています (scheme.list-queue - R7RSリストキュー)。

Class: <queue> ¶

{data.queue} シンプルなキューのクラスです。

Instance Variable of <queue>: length ¶

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

Class: <mtqueue> ¶

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

Instance Variable of <mtqueue>: max-length ¶

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

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

Instance Variable of <mtqueue>: closed ¶

論理値のフラグ。初期値は#fです。 これが真になると、enqueue!などによる新たなデータの挿入ができなくなります。 このスロットは読み出し専用で、enqueue/wait!、queue-push/wait!、 dequeue/wait!、queue-pop/wait!によってアトミックにセットすることが できます。 これは、mtqueueをチャネルとして使っていて、シャットダウンする場合に有用です。

Function: make-queue ¶

{data.queue} 空のシンプルなキューを作って返します。

Function: make-mtqueue :key max-length ¶

{data.queue} 空のmtqueueを作って返します。整数がmax-lengthに与えられた場合は、 それがmax-lengthスロットの値となります。

Function: queue? obj ¶

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

Function: mtqueue? obj ¶

{data.queue} objがmtqueueであれば#tを返します。

Function: queue-empty? queue ¶

{data.queue} objが空のキューであれば#tを返します。

Function: queue-length queue ¶

{data.queue} キューの中にある要素の数を返します。

Function: mtqueue-max-length mtqueue ¶

{data.queue} キューが保持できる要素の最大数を返します。限度がない場合は#fが返ります。

Function: mtqueue-room mtqueue ¶

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

この手続きが0以外有限値を返した場合でも、続くenqueue!の呼び出し時点で キューがいっぱいになっている可能性があることに注意してください。 この手続きの呼び出しとenqueue!の 呼び出しの間に、他のスレッドがキューに要素を入れるかもしれないからです。 有限長のmtqueueに確実に要素を挿入したい場合はenqueue/wait!を使ってください。

Function: mtqueue-num-waiting-readers mtqueue ¶

{data.queue} mtqueueからの読み出しで待っているスレッドの数を返します。 返り値は常に非負の正確な整数です。

この手続きが値を返してからその値を使うまでの間に、別のスレッドが キューに要素を挿入したら、待っているスレッドの数は変わってしまうことに 注意してください。この手続きの返り値を安全に使うには、 キューに値を挿入する部分を別に排他制御する必要があります。

(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 ¶

{data.queue} キューqueueのコピーを返します。

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

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

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

queueがmtqueueで既にクローズされていた場合は、キューは変更されず エラーが投げられます。

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

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

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

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

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

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

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

Function: dequeue! queue :optional fallback ¶

Function: queue-pop! queue :optional fallback ¶

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

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

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

Function: dequeue-all! queue ¶

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

Function: queue-front queue :optional fallback ¶

Function: queue-rear queue :optional fallback ¶

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

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

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

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

Function: queue->list queue ¶

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

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

Function: queue-internal-list queue ¶

{data.queue} queue->listと同じように、queueの内容をリストとして返しますが、 そのリストはqueueの内部構造と共有されているかもしれません。 つまり、返されたリストは続くqueueへの操作によって変更される可能性があり、 また返されたリストを変更するとqueueの一貫性は失われるでしょう。

この危険性のため、<mtqueue>をこの手続きに渡すことは禁じられています。 もしそうしたらエラーとなります。

queueに蓄積されたデータをコピーせずに取り出したいというだけなら、 dequeue-all!を使ってください。それは取り出すのとキューを空にする 操作をアトミックに行うので安全です。この手続きは、キューの中身を取り出すこと無く 内部にアクセスしたいという場合にだけ使って下さい。

Function: find-in-queue pred queue ¶

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

Function: any-in-queue pred queue ¶

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

Function: every-in-queue pred queue ¶

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

Function: remove-from-queue! pred queue ¶

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

移植性に関する註：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 close ¶

Function: queue-push/wait! mtqueue obj :optional timeout timeout-val close ¶

Function: dequeue/wait! mtqueue :optional timeout timeout-val close ¶

Function: queue-pop/wait! mtqueue :optional timeout timeout-val close ¶

{data.queue} これらの同期的手続きで、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を返します。

もしmtqueueが既にクローズされていたら、enqueue/wait! and queue-push/wait!はキューを変更せずにエラーを投げます。 フラグのチェックとキューへの挿入はアトミックに行われるので、 チェックと挿入の間に他のスレッドがenqueueしてしまうことはありません。 dequeue/wait!とqueue-push/wait!はクローズ済みのmtqueueに 対しても使えます。

最後の省略可能引数closeは、もし真の値が与えられれば、キューをクローズします。 クローズはアトミックに行われるので、 enqueue/wait!やqueue-push/wait!を呼び出したのであれば、 objが最後にキューに追加されるデータであることが保証されます。 これはチャネルの「シャットダウン」操作と考えることができます。