循環バッファ

コンピュータサイエンスにおいて、循環バッファ、循環キュー、巡回バッファ、またはリングバッファは、単一の固定サイズのバッファをエンドツーエンドで接続されているかのように使用するデータ構造です。この構造は、データストリームのバッファリングに適しています。^[1]初期の循環バッファはハードウェアで実装されていました。^{[2] [3]}

循環バッファは最初は空で、長さが設定されています。下の図は 7 要素のバッファです。

1 が円形バッファの中央に書き込まれていると仮定します (円形バッファでは正確な開始位置は重要ではありません)。

次に、循環バッファにさらに 2 つの要素 (2 と 3) が追加され、1 の後に置かれると仮定します。

2 つの要素が削除されると、循環バッファ内の最も古い 2 つの値が削除されます。循環バッファは FIFO (先入れ先出し) ロジックを使用します。例では、1 と 2 が最初に循環バッファに入ったため、最初に削除され、バッファ内に 3 が残ります。

バッファに 7 つの要素がある場合、バッファは完全にいっぱいになります。

循環バッファの特性として、バッファがいっぱいになったときに次の書き込みが実行されると、最も古いデータが上書きされます。現在の例では、さらに 2 つの要素 (A と B) が追加され、3 と 4 が上書きされます。

あるいは、バッファを管理するルーチンは、データの上書きを防止し、エラーを返すか、例外を発生させることもできます。データが上書きされるかどうかは、バッファ ルーチンまたは循環バッファを使用するアプリケーションのセマンティクスに依存します。

最後に、2 つの要素が削除された場合、削除されるのは3 と 4 (または A と B)ではなく、5 と 6 です。これは、5 と 6 が最も古い要素であるためです。その結果、バッファーは次のようになります。

循環バッファの便利な特性は、1 つのバッファが消費されるときにその要素をシャッフルする必要がないことです。(非循環バッファを使用した場合、1 つのバッファが消費されるときにすべての要素をシフトする必要があります。) 言い換えると、循環バッファはFIFO (先入れ先出し) バッファとして適しており、標準の非循環バッファはLIFO (後入れ先出し) バッファとして適しています。

循環バッファリングは、最大サイズが固定されているキューに適した実装戦略です。キューに最大サイズを採用する場合、循環バッファは完全に理想的な実装です。キューのすべての操作は一定時間で実行されます。ただし、循環バッファを拡張するにはメモリをシフトする必要があり、これは比較的コストがかかります。キューを任意に拡張する場合は、代わりにリンク リストアプローチが適している場合があります。

状況によっては、例えばマルチメディアなどで、上書き循環バッファを使用できます。バッファがプロデューサー-コンシューマ問題で境界バッファとして使用される場合、コンシューマ (サウンド カードなど)が一時的に追いつけない場合、プロデューサー (オーディオ ジェネレータなど) が古いデータを上書きすることが望まれる可能性があります。また、ロスレス データ圧縮アルゴリズムのLZ77ファミリは、データ ストリーム内で最近出現した文字列は、ストリーム内ですぐに出現する可能性が高いという仮定に基づいて動作します。実装では、最新のデータを循環バッファに格納します。

循環バッファはポインタと3つの整数を使って実装できる: ^[4]

• メモリ内のバッファ開始
• バッファ容量（長さ）
• バッファインデックスに書き込む（終了）
• バッファインデックスから読み取る（開始）

この画像は、長さ = 7 の部分的にいっぱいになったバッファを示しています。

この画像は、4 つの要素 (1 から 4 までの番号) が上書きされた完全なバッファーを示しています。

最初は、インデックスの終了と開始は 0 に設定されます。循環バッファ書き込み操作では、終了インデックス位置に要素が書き込まれ、終了インデックスは次のバッファ位置に増分されます。循環バッファ読み取り操作では、開始インデックス位置から要素が読み取られ、開始インデックスは次のバッファ位置に増分されます。

開始インデックスと終了インデックスだけでは、すべてのバッファスロットを活用しながらバッファがいっぱいか空かの区別をするには不十分ですが、^[5]バッファの最大使用サイズが長さ - 1 しかない場合は十分です。^[6]この場合、開始インデックスと終了インデックスが等しく、使用サイズが長さ - 1 のときにいっぱいになると、バッファは空になります。別の解決策は、書き込み操作で増加し、読み取り操作で減少する別の整数カウントを用意することです。すると、空かどうかをチェックすることはカウントが 0 に等しいことを意味し、いっぱいかどうかをチェックすることはカウントが長さに等しいことを意味します。^[7]

次のソース コードは、最小限のテストを伴った C 実装です。関数 put() はバッファにアイテムを配置し、関数 get() はバッファからアイテムを取得します。どちらの関数もバッファの容量を考慮します。

#include <stdio.h> 

enum { N = 10 }; // 循環バッファのサイズ       

int buffer [ N ]; // 注意: 一度に格納できるのは (N - 1) 個の要素のみですint writeIndx = 0 ; int readIndx = 0 ;   
   
    

int put ( int item ) { if (( writeIndx + 1 ) % N == readIndx ) { // バッファがいっぱいなので、オーバーフローを回避しますreturn 0 ; } buffer [ writeIndx ] = item ; writeIndx = ( writeIndx + 1 ) % N ; return 1 ; }    

         
  
     
      
  
    
        
   


int get ( int * value ) { if ( readIndx == writeIndx ) { // バッファは空ですreturn 0 ; }     

     
  
     
      
  

  *値= buffer [ readIndx ]; readIndx = ( readIndx + 1 ) % N ; 1を返す; }  
        
   


int main () { // 循環バッファをテストint value = 1001 ; while ( put ( value ++ )); while ( get ( & value )) printf ( "read %d \n " , value ); return 0 ; }  

  
     
     
     
       
   

循環バッファの実装は、基になるバッファを仮想メモリの 2 つの連続した領域にマッピングすることで最適化できます。^{[8] [議論中–議論] (当然、基になるバッファの長さはシステムの}ページ サイズの倍数に等しくなければなりません。) 循環バッファからの読み取りと書き込みは、直接メモリ アクセスによってより効率的に実行できます。最初の仮想メモリ領域の末尾を超えるアクセスは、自動的に基になるバッファの先頭に折り返されます。読み取りオフセットが 2 番目の仮想メモリ領域に進むと、読み取りと書き込みの両方のオフセットが基になるバッファの長さだけ減算されます。

おそらく、循環バッファの最も一般的なバージョンでは、8 ビット バイトを要素として使用します。

循環バッファの実装の中には、8 ビット バイトより大きい固定長要素 (オーディオ バッファの場合は 16 ビット整数、テレコム バッファの場合は 53 バイトのATMセルなど) を使用するものもあります。各項目は連続しており、正しいデータ アラインメントが確保されているため、これらの値を読み書きするソフトウェアは、連続していない値やアラインメントされていない値を処理するソフトウェアよりも高速です。

ピンポン バッファリングは、正確に 2 つの大きな固定長要素を持つ非常に特殊な循環バッファと考えることができます。

bipバッファ（二部バッファ）は、可変長の連続ブロックを常に返す点を除けば、循環バッファと非常によく似ています。これにより、連続ブロックのみを受け入れるAPIでバッファを使用できる機能を維持しながら、循環バッファの効率上の利点をほぼすべて提供します。^[9]

固定サイズの圧縮循環バッファは、基本的な数論に基づく代替インデックス戦略を使用して、データシーケンス全体の固定サイズの圧縮表現を維持します。^[10]

• ポートランドパターンリポジトリの CircularBuffer
• ブースト:

  テンプレート化された循環バッファコンテナ:circular_buffer/base.hpp

  同期された境界キュー: sync_bounded_queue.hpp

• LinuxカーネルのCB
• DSPのCB
• C 言語の循環キュー 2018-10-29 にWayback Machineでアーカイブ