リングバッファ
リングバッファ (英: ring buffer)、またはサーキュラーバッファ (英: circular buffer)、環状バッファ（かんじょうバッファ）は、図のようなリング状に配置されたバッファである。
仕組み[編集]
バッファを物理的にリング状に配置することはできないので、インデックス（添え数）をバッファサイズで割って剰余を取る正規化をし、一定の範囲に限定することで、直線状のバッファの両端を論理的に繋げる。正規化により、インデックスがバッファの最後を超えると最初に戻り、また負数が適切に処理されていれば、バッファの最初より前になると最後に進む。
正規化の内容は剰余演算だが、実際には、バッファサイズを2の冪に切り上げ、「バッファサイズ－1」とのビットごとの論理積を求めることが多い（ソースコードでは剰余のままであっても、現在のコンパイラの多くは、2の冪での剰余を自動的にビットごとの論理積に最適化する）。ただしバッファサイズを切り上げると余分なメモリが必要になるため、メモリ使用量の制約が強いときはバッファサイズを半端なままにしておき、一般的な方法で剰余を求めたり、バッファの端に達したかどうかで条件分岐したりする。
ただしこれらは、インデックスが0オリジンの場合の話である。1オリジンなどオリジンが0ではない場合は、0オリジンのインデックスに換算して正規化する必要がある。
リングバッファのインデックスは、数論的には剰余類をなす。
類似の機構[編集]
エンドレステープは、アナログ記録ではあるが、物理的にリングを実現したリングバッファと考えることもできる。
用途[編集]
現在では、動画や音楽再生のバッファリングとしてよく使用される。この場合、書き込みを行う位置と、読み込みを行う位置の衝突が発生する場合がある。 ストリーミング等でバッファの蓄積が再生より遅くなった場合、再生のバッファ待ちが発生する。
