[c/c++]いまさらリングバッファ

Firefoxで、githubのサイトの「あれ」が表示されなくて困っている。
Chromeでは表示されているし、以前は表示されていたから、Windows10にしてインストールしたときなどに何か忘れているのか・・・。
Flash Playerかもしれないと思ってインストールしたけど、変わらん。
アドオンも無効にしたのだが、変わらん。。。

URL名じゃないけど、git://とかhttps://とかの、あれが出てこないのだ。
ちっ。

---

さて、今回はリングバッファだ。
作業が空いてしまったので何か作ろうと思ったのだが、その「何か」がリングバッファだった。
私は「リングバッファ(ring)」で覚えたけど、「循環バッファ(circular)」のような呼び名もあるようだ。

教科書にも出てきそうな内容ではあるが、私が初めて見たのはネットワークのドライバか何かだったと思う。
こういうのもあるんだ、と感心した記憶があります。

それから早数年…十数年…数十年…、ソースが公開されることも増え、フレームワークなんかにはデータ構造に関するライブラリも付いていることが多く、こういうのは実装することがなかったので、やってみました。

というよりも、見たソースがけっこう高機能なものが多く、さらっと動きが速いものが作りたかったのです。
構造体をリングにするとかではなく、単に1バイトずつのバッファがリングになっているだけというものでよいのです。

 

基本に忠実に、

• バッファの前後がつながっている
• 位置として、書込みポインタと読込みポインタを持つ
• 読込みポインタは、書込みポインタを追い越さない

くらいの内容で考えました。

あとは、構造体みたいなデータは考慮外で、単にバイトデータだけを管理します。
ドライバ付近で使うイメージですかね。

また、ポインタがぐるっと回る動作を剰余(%, modulo)で実現するものが多いのですが、あれって時間かかるよなぁ、と思い、目に見える実装部分での剰余やループはなくすことにしました。

---

まだテスト中だが、現状を置いておこう。
https://github.com/hirokuma/ringbuf

いやぁ、かかったよ！
こんなにかかるなんて考えてなかったですわ。
頭が回ってないのだろうか。。。

 

最初は、malloc()ではなくstatic変数でべたべたに作っていた。
ここは以前の反省で、データ構造で分離できるものは構造体にして引数にした方がよい、ということで、外に出した。

この構造体だが、メンバが

• 読込みポインタ
• 書込みポインタ
• バッファサイズ
• 空きかどうか
• バッファ

となった。
この「空きかどうか」を採用するかは、けっこう悩んだ。

---

初期状態は、こう。
Wは書込みポインタ、Rは読込みポインタだ。

データ(A, B, C, D)を詰めると、こう。
書込みポインタは「次に書込む位置」を、読込みポインタは「次に読込む位置」を表している。

 

では、次に1バイト書込むとどうなるか？

RとWが並ぶのだ。
「空きがあるかどうか」を判断するのに、RとWの位置を使うとすると、この状態はまずい。
全部空いている状態との区別が付かないのだ。

 

RAMよりもROMに余裕があるだろうから、RとWが揃わない実装にしようと思い、あれこれやっていた。
が、まあ、予想が付くかもしれないが、かなり面倒だった。。。
ちょっと処理するたびに、RとWが並ぶかどうかをチェックしないといけないのだ。

疲れて、空きがあるかどうかのフラグを別に分けることにした。
フラグが立つのは、初期化時と、読込んでRとWが一致したときだけだ。

---

あとは、ループ処理を実装で書かないという制約が大きかったか。

剰余の代わりは、このくらいの処理であればif文で書いてしまえば済む。
三項演算子でもよいだろう。

ただ、データの読み書きでループ処理を実装で書かないので、memcpy()を使うしか無い。
いや、そうじゃないな。
データの読み書きをmemcpy()でやりたかったからループ処理が不要になったのだ。

 

memcpy()で処理するには、データが連続するように扱うしかない。
たとえば、RとWがこういう配置だった場合。

読込み可能なのは青い部分、書き込み可能なのは茶色の部分だ。
RとWの位置が逆になると、もちろんこうなる。

つまり、パターンとしては、

• 領域が1つしかない
• 領域が2つに分かれている

があることになる。
剰余とループを使うと、このパターン分けが不要になるのだ。

でもまあ、パターンが2つしかないならいいか、というのがmemcpy()でやろうとした理由だ。
そこまでは考えていたのだが、この図だとポインタが[0]とか[4]にあるとか、バッファが空いていないとか、途中までしか読込まないとか、そういうのをやっていくとゴチャゴチャしてきたのだ。

---

WriteとReadは似たような構造をしているのだけど、気にせず分けた。
こういうのを格好良くまとめようとすると、だいたい私の場合はろくなことにならないのを経験上わかっているのだ(私という人間が)。

 

ただ、けっこうテストパターンを通したつもりだったのだが、カバレッジを見ると通っていないルートが残っていた。
通し切れていないのか、通るはずがないルートなのかはわかっていない。

 

malloc()/free()にしてるけど、そこは書き換えできるだろう。
配列にできれば、sizeも不要になって、sizeを使っているところはsizeofで置き換えられるんじゃなかろうか。

 

あとはねぇ、たぶんまだまだ格好良くできると思うから、そこですかね。
汎用性は他の人がいいのを作っているので、速度とサイズ重視で行きたいところだ。