リングバッファ

説明

循環バッファ、サイクリックバッファ、リングバッファは、単一の固定サイズのバッファを、端と端がつながっているかのように使うデータ構造です。

循環バッファは最初は空で、あらかじめ決められた長さを持ちます。 たとえば、これは7要素のバッファです：

[ ][ ][ ][ ][ ][ ][ ]

バッファの真ん中に1が書き込まれたとします（循環バッファでは、正確な開始位置は問題になりません）：

[ ][ ][ ][1][ ][ ][ ]

次に、さらに2つの要素、2と3が追加され、1の後に続けて入るとします：

[ ][ ][ ][1][2][3][ ]

そのあとでバッファから2つの要素を取り除くと、バッファの中で最も古い値が取り除かれます。 この場合に取り除かれる2つの要素は1と2で、バッファには3だけが残ります：

[ ][ ][ ][ ][ ][3][ ]

バッファに7つの要素が入ると、完全にいっぱいになります：

[5][6][7][8][9][3][4]

バッファがいっぱいになるとエラーが発生し、スロットが空くまでこれ以上書き込めないことをクライアントに知らせます。

バッファがいっぱいのとき、クライアントは強制書き込みで最も古いデータを上書きすることを選べます。 この場合、さらに2つの要素AとBが追加され、3と4を上書きします：

[5][6][7][8][9][A][B]

3と4はAとBに置き換えられ、バッファの中で最も古いデータは5になりました。 最後に、2つの要素を取り除くと、返されるのは5と6で、バッファはこうなります：

[ ][ ][7][8][9][A][B]

空きがあるので、ここでクライアントが再び上書きを使ってCとDを保存すると、使われるのは前に5と6が入っていた場所で、7と8の場所ではありません。 7は依然として最も古い要素で、バッファは再びいっぱいになります。

[C][D][7][8][9][A][B]

この演習では、これまでに見たことのないかもしれない概念をいくつか紹介します。

ユーザー定義の名前空間

8thでは、ワードはすべて名前空間に属します。たとえば、a:newはa名前空間のnewワードを指します。 独自の名前空間を定義することもでき、circular-buffer.8thファイルの先頭ではまさにそれを行っています。

ns: cb

つまり、そのファイル内のワードはすべてcb:<word>でアクセスできるようになります。関連する機能をまとめるのに最適な方法です。

詳しくは、名前空間のドキュメントを参照してください。

例外

readとwriteのワードは、どちらも不正な状態の循環バッファーに対して呼び出されたときに、例外を投げることが求められます。 詳しくは、例外とエラー処理のドキュメントを参照してください。

オブジェクト

循環バッファーの実装方法は自由ですが、8thのオブジェクトのサポートを使うことも検討してみてください。

---

出典

Wikipedia