ring buffer の管理変数
上書きタイプのting buffer
tailに追加し、headから読み出す、sizeサイズのring buffer。古いものを書き潰すタイプ。
- size 最大登録数。0の場合は、一つも登録できない。
- length 登録済みの数。0はなにも登録されていない。
- head lengthが1以上なら存在する先頭のエントリ。先頭は最も古いものを示す。
- tail 次に登録する空きエントリを示す。
登録処理
tailに登録し、tailをラウンドカウントアップする。書き潰すタイプである為、sizeがゼロでない限り、登録可能。 条件に応じて、length, headを更新する。
フルでない場合、lengthをカウントアップ。
フルの場合は、lengthをカウントアップしないが、書き潰した為、headをラウンドカウントアップ。
フル判断は、length=size
ダンプ
全データを見る。取り出さない。 headから、length個を読み出す。
取り出し
空でない場合、headから取り出し、headをラウンドカウントアップし、lengthをデクリメント。
空の場合、空を返し、管理変数を変更しない。
length=0の場合、空。
判断
記載済みだが参考までに。
- フル判断。length = size
- 空判断。length = 0
補足
head=tailの場合、二つの状態がある。一つは空。もう一つはフル。
空の場合、headが空、tailは次に書き込む空の位置を示すため、先頭のheadを示す。つまり、head=tail。lengthで空を判断する。
フルの場合、最も古いデータをhead が指し、その同じデータは次に書き潰されるtailの位置でもある。やはり、head=tail。判断はlength=size。
lengthを持ちたくない場合
lengthを持つ理由は、head=tailの場合に、フルと空の二つの状態が存在する為、よって、この場合に、どちらか一つの状態に確定すれば、headとtailだけでlengthが不要になる。
空の状態は無くせない場合が多い為、フルの状態でhead=tailでなければ良い。つまり、tailを一つ前で止める。そのため、保持可能な要素がバッファより一つ少ないsize-1個になる。headとtailから算出される要素数がsize-1個の状態で登録する場合、headを一つ進ませ、データを破棄する。最大登録数が1減るデメリットがあるが、管理変数lengthが不要になる。
lengthを持ちたくない場合その二
もう一つは、空を許さない方法。常時一つ以上のデータを保持する制約とする。この条件下では、データが一個の場合は、データを取り出せない。データがあるのに取り出せない事を許容できるか。
lengthではなくfullフラグを持つ場合
head=tailの時に、fullかどうかを判断する別の方法。専用のfullフラグで管理。管理変数の数は同じだか、使い方が異なる。
fullフラグの初期値はfalse。登録後、head=tailになる場合にtrueにセット。取り出し時にfalseにセット。
登録数は、fullならsize。 そうでなければ、tail-head から算出。
lengthと比べると
fullフラグの場合
フル判断: fullフラグ 空判断: not full and head=tail
lengthの場合
フル判断: length=size 空判断: length=0
上記から、フル判断はfullフラグが簡単、空判断はlengthが簡単。
フル判断は書き込み時に必要であり、書き込みが多い場合はfullフラグ。
読み出しが多い場合は、空判断が簡単なlengthにメリットがある。
ただし、リングバッファは読み書きが同じ頻度を想定しており、どちらかが多い場合は少ない。なお、fullフラグの場合、空判断の為に3個の変数を見る必要があり、判断という点ではlengthを使う方法が優れていると言える。
一方、flagはオンオフのみの操作で、lengthは加減算が必要。swではなく、hwで論理を組む場合は、加減算機が不要なflagにメリットがあるかもしれない。swでは、セットも加減算もほぼ同等。即値が不要な加減算の方がもしかしたら早いかもしれない。
