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

Module: data.ring-buffer ¶

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

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

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

Function: make-ring-buffer :optional initial-storage :key overflow-handler initial-head-index initial-tail-index ¶

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

デフォルトでは、initial-storageに渡されたストレージは空のバッファとみなされます。 しかし、あらかじめ一部に有効なデータを入れて渡すこともできます。その場合は、 initial-head-indexとinitial-tail-index引数で有効なデータの インデックスの範囲を指定してください(これらの引数のデフォルトは0です)。 例えば次のコードは、初期容量8のリングバッファのうち、最初の4要素が既に埋められているような リングバッファを作って返します。

(make-ring-buffer (vector 'a 'b 'c 'd #f #f #f #f)
                  :initial-tail-index 4)

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

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

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

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

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

{data.ring-buffer} make-ring-bufferのoverflow-handlerキーワード引数に 渡せる手続きを作って返します。

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

• 現在のバッキングストレージの大きさがmax-capacity以上であれば、 errorを返す。
• そうではなく、現在のバッキングストレージの大きさがmax-increase以上で あれば、(+ max-increase 現在の大きさ)の大きさを持つ ベクタもしくはユニフォームベクタをアロケートして返す。
• そうでない場合は、(* 2 現在の大きさ) の大きさを持つ ベクタもしくはユニフォームベクタをアロケートして返す。

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

Function: ring-buffer-empty? rb ¶

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

Function: ring-buffer-full? rb ¶

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

Function: ring-buffer-num-entries rb ¶

{data.ring-buffer} リングバッファrbが格納している要素数を返します。

Function: ring-buffer-capacity rb ¶

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

Function: ring-buffer-front rb ¶

Function: ring-buffer-back rb ¶

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

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

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

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

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

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

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

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

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

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

Function: ring-buffer-set! rb index value ¶

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

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

Function: ring-buffer->flat-vector rb :optional start end ¶

{data.ring-buffer} リングバッファrbの現在の有効な範囲の内容を、新たにアロケートされる rbのストレージと同じ型のベクタとして返します。 start/endインデックスを指定した場合はそのインデックスの範囲内の 内容だけが取り出されます。

(define rb (make-ring-buffer (make-vector 4)))

(ring-buffer->flat-vector rb) ⇒ #()

(ring-buffer-add-back! rb 'a)
(ring-buffer-add-back! rb 'b)
(ring-buffer-add-front! rb 'z)
(ring-buffer-add-front! rb 'y)

(ring-buffer->flat-vector rb) ⇒ #(y z a b)
(ring-buffer->flat-vector rb 1 3) ⇒ #(z a)