ページ 1 / 1
リングバッファについて
Posted: 2008年8月01日(金) 08:11
by デンマーク
リングバッファを作成しています。上書きの部分とかいろいろ考えてようやく正常に動くところまで、できました。自分としては大丈夫だと考えていますが、何かここが変だぞという箇所があったら指摘をいただきたいです。
ご存知だと思いますが
リングバッファとは配列にデータを格納していき、
最大格納数に達したら古いデータから上書きしていくというものです。
data_set[SIZE]; // 大きさが SIZE の配列を宣
言
long data_head; // データ先頭位置を表す変数
long data_number; // 総データ数
long data_new; // 最新のデータ位置を表す変数
}DATA; // データ型の宣言
DATA data_data;//変数を使うために宣言 DATAは型でdata_data
は変数
void data_set( long data )
{
2
data_data.data_set[data_new] = data; //データを保存
していく
5 2
if( data_number <= SIZE - 1 ) //データ個数がSIZE以下の
時
{ 3
data_number ++; //データ個数が増えていくが「head」は動
かない
3 3
data_new = data_number ; //最新のデータ位置がずれて
いく
3 2
if(data_new > SIZE - 1) //最新データ位置が配列数をこえ
たら
{ 0
data_new = 0; //最新データ位置を配列の最初に戻す
}
}
else //データ個数がSIZEより大きい時
{
0 5 3
data_new = (data_number + 1) % SIZE;
3
data_head++; //古い位置をインクリメント
6
data_number++; //データ総数は増えていく…
3 2
if( data_head > SIZE - 1 ) //古いデータ位置が配列より
大きくなったら
{
0
data_head = 0; // 0に戻す
}
}
Re:リングバッファについて
Posted: 2008年8月01日(金) 08:51
by box
DATAの定義の先頭部分にあるはずのstructが抜けていたり、
インクルードしているはずのヘッダーファイルがなかったり、
コンパイルするにはmain関数などの定義が抜けていたり、
コードの途中に意味のわからない数字が紛れ込んでいたり、
preタグと/preタグによる字下げを行なっていなかったりしていますので、
お書きになったコード全体を正確に載せていただけますか?
Re:リングバッファについて
Posted: 2008年8月01日(金) 09:25
by バグ
リスト構造にしてしまえばいいのではないでしょうか?
とはいうものの、私自身この辺のことはSTL任せでほとんど勉強していなかったので、試しに書いてみました。
あ、main関数は省いてあり、リングバッファに関する部分のみ載せています。
本来は利便性を考えれば、双方向リストにすべきなんでしょうが、今回はスレ主さんの仕様に沿ってみました。
ツッコミよろしくお願いします(^_^;)
#define SIZE 10
/* リスト構造体 */
struct list
{
int data;
struct list* next;
};
/* リングバッファ構造体 */
struct ring
{
struct list buffer[SIZE];
struct list* set_pos;
};
/* リングバッファの初期化 */
void initialize(struct ring* r)
{
for (int i = 0; i < SIZE; i++)
{
r->buffer.data = 0;
if (i + 1 >= SIZE)
{
r->buffer.next = &r->buffer[0];
}
else
{
r->buffer.next = &r->buffer[i + 1];
}
}
r->set_pos = &r->buffer[0];
}
/* リングバッファへ新しいデータをセットする */
void set(struct ring* r, int data)
{
r->set_pos->data = data;
r->set_pos = r->set_pos->next;
}
Re:リングバッファについて
Posted: 2008年8月01日(金) 11:03
by box
>デンマークさん
リングバッファーを実装するには、少なくとも
・データの先頭位置(次にそこから取り出す)
・データの末尾位置(次にそこに挿入する)
・バッファーが空っぽかどうかの判定(空っぽならば、取り出そうとしてもできない)
・バッファーが満杯かどうかの判定(満杯ならば、挿入しようとしてもできない)
といったようなことを管理できる必要があります。
Re:リングバッファについて
Posted: 2008年8月02日(土) 13:39
by たかぎ
古いものを上書きするということなので...
> ・バッファーが空っぽかどうかの判定(空っぽならば、取り出そうとしてもできない)
> ・バッファーが満杯かどうかの判定(満杯ならば、挿入しようとしてもできない)
すくなくとも、上の二つは不要です。
ちょっと私も作ってみましたが、至って簡単です(テスト用のmainは手抜きです)。
#include <stdio.h>
#include <errno.h>
#define N 4
long data[N];
size_t size = 0;
void data_set(long value)
{
data[size++ % N] = value;
}
int main(void)
{
long value;
size_t start;
size_t n;
size_t i;
while (scanf(" %ld", &value) == 1)
{
data_set(value);
}
if (size < N)
{
start = 0;
n = size;
}
else
{
start = size % N;
n = N;
}
for (i = 0; i < n; i++)
{
printf("%ld\n", data[(start + i) % N]);
}
return 0;
}
データの取り出し部分は専用の関数にしてもよい気がしますが、まあこれでも十分でしょう。
途中でデータを取り出すのであれば、取り出し位置の管理が別途必要になります。
Re:リングバッファについて
Posted: 2008年8月02日(土) 14:31
by デンマーク
みなさま、ご意見ありがとうございます。
main関数仕様にして、取り出し関数も追加したものを
添付しましたがコンパイルするとエラーがでてしまいます。
「未定義のシンボルがそうたら」とでています。
その原因を教えて頂けたらと思います。
あと取り出し関数で errorを返す時に
値は何を返したらいいでしょうか?
型が long なので値がかぶらないものを考えています。
説明が雑で申し訳ありませんが宜しくお願いします。
Re:リングバッファについて
Posted: 2008年8月02日(土) 21:59
by バグ
>>あと取り出し関数で errorを返す時に
>>値は何を返したらいいでしょうか?
>>型がlong なので値がかぶらないものを考えています。
絶対にかぶらない値というのは無いのではないでしょうか?
ですので、関数の戻り値で成否を判定し、データの格納は変数のアドレスを渡してあげることで解決してみてはいかがでしょうか?
それから、デンマークさんのソースで気になったのは構造体のメンバ変数にアクセスするのにドットではなくカンマを使用している点ですね。これではコンパイルすら通らなかったのではないでしょうか?
下記のソースは、できるだけデンマークさんのやりたかったであろう流れを推測して残しつつ、0から書き直してみました。グローバル変数は使わずにポインタを利用しています。
総データ数や、データ取り出し回数などのオーバーフロウを起こしそうな箇所も対策をしておきました(とはいえ、SIZEの値がintで表現できる値を超えてしまうとこのソースでもオーバフロウをおこしてしまう可能性はあります)ので、参考になればよいのですが…
#include <stdio.h>
#define SIZE 10
struct DATA
{
long data[SIZE]; // データ格納用の配列
int new_pos; // 最新データのインデックス
int first_pos; // 最も古いデータのインデックス
int last_pos; // 最後に取得したデータのインデックス
int count_check; // データ数がSIZEを超えたら1、そうでない場合は0
int get_check; // 一度でもデータの取得を行ったら1、そうでない場合は0
};
// プロトタイプ宣言
void init(struct DATA* data);
void set(struct DATA* data, long value);
int first(struct DATA* data, long* buffer);
int next(struct DATA* data, long* buffer);
int main(void)
{
int i, j;
long buf = 0;
DATA data;
// 初期化
init(&data);
// エラーテスト
if (first(&data, &buf) == 0)
{
printf("first関数が実行されましたが、データがありません\n");
}
if (next(&data, &buf) == 0)
{
printf("next関数が実行されましたが、データがありません\n");
}
// リングバッファに代入されるデータの動きを見るテスト
for (i = 0; i < 33; i++)
{
// データをセットする
set(&data, i);
// メンバ変数であるdata配列の値を全て表示する
for (j = 0; j < SIZE; j++)
{
printf("%02d ", data.data[j]);
}
// 最も古いデータのインデックスを表示する
printf("first index = %d\n", data.first_pos);
}
// データ取得テスト
if (first(&data, &buf) == 0)
{
printf("first関数が実行されましたが、データがありません\n");
}
else
{
printf("first value = %d\n", buf);
}
if (next(&data, &buf) == 0)
{
printf("next関数が実行されましたが、データがありません\n");
}
else
{
printf("next value = %d\n", buf);
}
return 0;
}
void init(struct DATA* data)
{
int i;
for (i = 0; i < SIZE; i++)
{
data->data = 0;
}
data->new_pos = 0;
data->first_pos = 0;
data->last_pos = 0;
data->count_check = 0;
data->get_check = 0;
}
void set(struct DATA* data, long value)
{
// 最新データのインデックスが指し示す場所へ値を代入する
data->data[data->new_pos] = value;
// チェックが1の場合は最も古いデータのインデックスを更新する
if (data->count_check == 1)
{
data->first_pos++;
// 更新された値が配列の要素数を超えた場合は0にする
if (data->first_pos >= SIZE)
{
data->first_pos = 0;
}
}
// 最新データのインデックスを更新する
data->new_pos++;
// 更新された値が配列の要素数を超えた場合は0にする
if (data->new_pos >= SIZE)
{
data->new_pos = 0;
// ここを通るということはデータ総数がSIZEを超えたという事なので、checkを1にする
data->count_check = 1;
}
}
int first(struct DATA* data, long* buffer)
{
// 最新データのインデックスが0で、なおかつチェックが0の場合はデータ無しとみなす
if (data->new_pos == 0 && data->count_check == 0)
{
// エラー値を返す
return 0;
}
// 最後に取得したデータのインデックスを更新する
data->last_pos = data->first_pos;
// データ取得フラグをたてる
data->get_check = 1;
// バッファにデータを代入する
*buffer = data->data[data->first_pos];
// 正常終了
return 1;
}
int next(struct DATA* data, long* buffer)
{
// 最新データのインデックスが0で、なおかつチェックが0の場合はデータ無しとみなす
if (data->new_pos == 0 && data->count_check == 0)
{
// エラー値を返す
return 0;
}
// 一度もデータ取得が行われていない場合はエラー値を返す
if (data->get_check == 0)
{
return 0;
}
// 最後に取得したデータのインデックスを更新する
data->last_pos++;
// 更新された値が配列の要素数を超えた場合は0にする
if (data->last_pos >= SIZE)
{
data->last_pos = 0;
}
// データ取得フラグをたてる
data->get_check = 1;
// バッファにデータを代入する
*buffer = data->data[data->last_pos];
// 正常終了
return 1;
}
Re:リングバッファについて
Posted: 2008年8月03日(日) 22:57
by デンマーク
>バグ ..神 さん
ソースありがとうございます。
大変参考になります。
なんと言っていいかわかりませんが、人のソースを
見てこんなに自分の考えが見透かされる(笑)?感じは
初めてです。。
今のソースに改良を加えていますので、
終わったら見て下さい。