For Gauche 0.9.5


Next: , Previous: , Up: ライブラリモジュール - ユーティリティ   [Contents][Index]

12.13 data.ring-buffer - リングバッファ

Module: data.ring-buffer

リングバッファは、両端を指す二つのポインタを持つ配列と考えられます。良くある使い方は、 生産者が配列の一方の端にデータを追加してゆき、消費者がもう一方の端から データを取り出してゆくというものです。もし端を示すポインタが配列の 終端に達したら、それはもう一方の端につながっているように振る舞います。 「リング」バッファと呼ばれるのはそのためです。

このモジュールの提供するリングバッファは、どちらの端にもデータを追加し、 どちらの端からもデータを取り出すことができます。したがって機能的には 両端キュー(double-ended queue, deque)の一種とも考えられます。 また、O(1)で要素にアクセス可能で、 さらにバッファが一杯になった時の振る舞いをカスタマイズできます。

リングバッファがデータを格納するバッキングストレージとして、 通常のベクタかユニフォームベクタを使えます。

Function: make-ring-buffer :optional initial-storage :key overflow-handler

リングバッファを作成します。デフォルトでは、データ格納のための領域として 新たなベクタがアロケートされます。かわりに、呼び出し側でベクタかユニフォームベクタ を用意してinitial-storageに渡すこともできます。その場合、 渡すベクタやユニフォームベクタは変更可能でなければなりません。以降、 リングバッファがそのベクタを変更するので、呼び出し側でベクタを変更 したりベクタの内容が保存されることを期待してはいけません。

overflow-handlerキーワード引数は、バッファがフルの状態で 新たな要素が追加されようとした時の振る舞いを指定します。 引数は手続きか、シンボルerroroverwriteのいずれかでなければなりません。

引数が手続きの場合、リングバッファと(一杯になった)バッキングストレージ が引数として渡されます。この手続きは以下の3つのアクションのうちひとつを 実行しなければなりません。(1)渡されたバッキングストレージ(ベクタか ユニフォームベクタ)と同じ型で、より大きなベクタまたはユニフォームベクタをアロケートして 返す。(2)シンボルerrorを返す。(3)シンボルoverwriteを返す。 手続きがベクタもしくはユニフォームベクタを返した場合は、それが 新たなバッキングストレージとして使われます。 返すベクタの内容を設定する必要はありません。リングバッファが適切に内容のコピーや 必要な初期化を行います。手続きがerrorを返した場合は、 “buffer is full”のエラーが投げられます。 手続きがoverwriteを返した場合は、 新たな要素で古い要素を上書きします(つまり、 あたかも別の端から1要素がポップされて捨てられ、その後で新たな要素が 追加されたかのように振る舞います)。

overflow-handler引数にシンボルerroroverwrite を渡した場合は、あたかもそれらのシンボルを無条件に返すoverflow handlerが 指定されたかのように振る舞います。

overflow-handlerが指定されない場合のデフォルトの動作は、 元のバッキングストレージの倍の容量をアロケートして返すことです。 下のmake-overflow-doublerを使うと、カスタマイズした オーバフローハンドラを簡単に作ることができます。

Function: make-overflow-doubler :key max-increase max-capacity

make-ring-bufferoverflow-handlerキーワード引数に 渡せる手続きを作って返します。

返される手続きは、リングバッファとバッキングストレージを引数に取り、 以下のとおり振る舞います。

max-increasemax-capacityのデフォルト値はどちらも +inf.0です。

Function: ring-buffer-empty? rb

リングバッファrbが空なら#tを、そうでなければ#fを返します。

Function: ring-buffer-full? rb

リングバッファrbがフルなら#tを、そうでなければ#fを返します。

Function: ring-buffer-num-elements rb

リングバッファrbが格納している要素数を返します。

Function: ring-buffer-capacity rb

リングバッファの現在のバッキングストレージの容量(格納可能な要素数)を返します。

Function: ring-buffer-front rb
Function: ring-buffer-back rb

リングバッファrbの先頭あるいは末尾の要素をそれぞれ返します。 バッファが空の場合はエラーが投げられます。

Function: ring-buffer-add-front! rb elt
Function: ring-buffer-add-back! rb elt

リングバッファrbの先頭もしくは末尾にそれぞれ要素を追加します。 rbがフルの場合の振る舞いは、バッファのオーバーフローハンドラによって 決定されます。詳しくはmake-ring-bufferのエントリを参照してください。

Function: ring-buffer-remove-front! rb
Function: ring-buffer-remove-back! rb

リングバッファrbの先頭もしくは末尾から要素をひとつ取り、取った要素を 返します。 バッファが空の場合はエラーが投げられます。

Function: ring-buffer-ref rb index :optional fallback

リングバッファrbindex番目の要素を返します。 要素は先頭から数えられます。したがって、新たな要素が先頭に付け加えられた場合、 既存の要素のインデックスはひとつづつずれます。

indexrbの持つ要素の範囲外の場合、fallbackが与えられていれば それを返し、そうでなければエラーが投げられます。

Function: ring-buffer-set! rb index value

リングバッファrbindex番目の要素にvalueをセットします。 要素は先頭から数えられます。したがって、新たな要素が先頭に付け加えられた場合、 既存の要素のインデックスはひとつづつずれます。

indexrbの持つ要素の範囲外の場合はエラーが投げられます。


Next: , Previous: , Up: ライブラリモジュール - ユーティリティ   [Contents][Index]