配列を輪として使う
循環バッファは、有限の配列の末尾へ達した位置を先頭へ戻し、領域を繰り返し使う構造です。ここではheadを次の書込み位置、tailを次の読取り位置とする規則で説明します。別の実装では呼び名の意味が逆の場合もあるため、変数名だけでコードを読まないことが重要です。追加ではhead、取出しではtailを進めます。古い要素を物理的にすべて前へずらさなくても、先頭の論理的な位置を変えられます。配列の格納順と、利用者に返すFIFOの論理順を区別することが、折返し後の動作を理解する鍵になります。
空と満杯に同じ位置を使わない
headとtailが等しい状態を空と決めるなら、同じ組合せを満杯にも使うと判定が曖昧になります。一つの方法は一枠を常に空け、headの次がtailなら満杯とすることです。この方式では配列がN枠あっても利用可能な要素数はN−1です。別の方法として、使用数や世代の情報を持って全枠を使う実装もあります。容量の説明では配列の枠数と受け入れられる要素数をそろえます。ある実装のN−1という式を、すべてのリングバッファの必須条件へ一般化しないようにします。まず採用した空と満杯の表現を確認します。
四枠の折返しを追う
四枠で一枠を空ける方式を使い、最初はhead=0、tail=0とします。A、B、Cを順に追加するとhead=3、tail=0で満杯です。Aを一つ取り出すとtail=1へ進み、Dを追加するとheadは3から0へ折り返します。残る論理順はB、C、Dであり、配列を添字0から表示した順とは一致しません。ここでhead=0でも空ではありません。tail=1と組にして読む必要があります。説明の各操作は一つずつ完了しており、並行アクセスの観測が自動的に同じ原子的な状態を見せると主張しているわけではありません。
剰余とビットマスクの条件を守る
一般的には次の位置を(index+1) mod Nで求めます。Nが2の冪なら、適切な非負整数の扱いの下で(index+1) & (N−1)を使える場合があります。ただしNが6のような任意の数なら同じ置換はできません。省いた条件を忘れると、添字が配列の一部へ偏ったり、期待する折返しにならなかったりします。また、複数要素をまとめて扱う場合は、必要な領域が配列の末尾と先頭の二つに分かれることがあります。使用可能な総量と、一回で連続して読める・書ける量も別です。添字の計算を最適化する前に境界の規則を検証します。
データの公開と添字の更新をそろえる
生産者が要素を書き終える前にheadだけを公開すると、消費者がまだ完成していない内容を読む危険があります。消費者が読み終える前に空きを返しても、書き手が使用中の場所を上書きする場合があります。単一生産者・単一消費者を前提にした方式と、複数が同じ端を操作する方式では同期の条件が違います。Linuxカーネルの公開手順を、普通の整数を使うユーザー空間のC++へそのまま写すこともできません。言語と実行環境の適切なatomicやロックを使い、データの寿命も含めて、どの観測が安全な使用の根拠になるかを設計します。
満杯と空の扱いまで試す
満杯で追加を拒否する、古い要素を上書きする、空きまで待つ、という選択は用途で変わります。ログの直近履歴と未処理の仕事では同じ破棄方針にできません。試験では空での取出し、満杯での追加、一周以上の折返し、一要素ずつの交互操作を含めます。順序と受け入れた個数を参照用のキューと比較すると、添字が一つずれる問題を見つけやすくなります。四枠の例は状態の手計算であり、性能差の測定ではありません。有限の領域を再利用する利点と、容量・待機・同期の条件を一緒に理解して利用します。