« こいつは、良いかも。更新無料セキュリティソフト | トップページ | 初めて見たよ『コレジャナイロボ』! »

2006年6月 1日 (木)

リングバッファーについて♪

たまには、プログラマーぽい事でも書こう…。

でないと、プログラマーだと言う事を忘れそうだ…。
(笑)

良く見かけるリングバッファの処理。
でも、これには、落とし穴が…。

/* -------------------------------------
リングバッファーの処理
------------------------------------- */
#include<stdio.h>
/* ---------------------------------- */
#define RING_MAX 10
int ring_buffer[RING_MAX];
int ring_wrt=0;/* これから書き込む場所 */
int ring_rnd=0;/* これから読み出す場所 */
/* -------------------------------------
古い要素を上書きしない追加処理
------------------------------------- */
int ring_push(int element){
    int n;
    n=(ring_wrt+1)%RING_MAX;
    if(ring_rnd==n)
        return -1;/* 要素が一杯なのでエラー */
    ring_buffer[ring_wrt]=element;
    ring_wrt=n;
    return 0;
}
/* -------------------------------------
古い要素を順次呼び出す処理
------------------------------------- */
int ring_pop(void){
    int n;
    if(ring_wrt==ring_rnd)
        return -1;/* 要素が無いのでエラー */
    n=ring_rnd;
    ring_rnd=(ring_rnd+1)%RING_MAX;
    return ring_buffer[n];
}
/* -------------------------------------
バッファー内を表示する処理
------------------------------------- */
void ring_print(void){
    int now,cnt,i;
    if(ring_wrt==ring_rnd){
    /* 要素がありません */
        printf("c - p : empty\n");
        return;
    }
    cnt=(RING_MAX+ring_wrt-ring_rnd)%RING_MAX;
    now=(RING_MAX+ring_wrt-1)%RING_MAX;
    printf("%d - %d : ",cnt,ring_wrt);
    for(i=0;i<cnt;i=i++,now=(RING_MAX+now-1)%RING_MAX)
        printf("%2d-",ring_buffer[now]);
    printf("\n");
}
/* ---------------------------------- */
void ring_push_print(int i){
    printf("%2d -> ",i);
    if(ring_push(i)<0){
        printf("9 - 9 : over flow\n");
    }else{
        ring_print();
    }
}
/* ---------------------------------- */
void ring_pop_print(void){
    int i;
    if((i=ring_pop())<0){
        printf("--          : pop empty\n",i);
    }else{
        printf("%2d <- ",i);
        ring_print();
    }
}
/* ---------------------------------- */
void main(void)
{
    int i;
    printf("el <> ");
    ring_print();/* 要素が無い時の表示テスト */
    /* オーバーした時のチェックとして一回余計に回しています。 */
    for(i=0;i<RING_MAX;i++)
        ring_push_print(i);
    /* オーバーした時のチェックとして一回余計に回しています。 */
    for(i=0;i<RING_MAX;i++)
        ring_pop_print();
    /* 二歩進んで一歩引く形でバッファー境の処理の確認 */
    for(i=0;i<RING_MAX*3;i++){
        ring_push_print(i);
        if(i&1)
            ring_pop_print();
    }
}

実に直線的な考えで分かり易い反面、無駄がある。

それは、書き込み場所と読み出し場所に
データの有る無しの意味を持たせたため
要素が無い時にデータ1個分消費する。
つまりバッファー数-1個しか利用できない。

書き込み場所と書き込み個数の形にしたら
感じの
良い処理になった。

/* -------------------------------------
リングバッファーの処理
------------------------------------- */
#include<stdio.h>
/* ---------------------------------- */
#define RING_MAX 10
int ring_buffer[RING_MAX];
int ring_wrt=0;/* これから書き込む場所 */
int ring_cnt=0;/* 書き込まれた要素数 */
/* -------------------------------------
古い要素を上書きする追加処理
------------------------------------- */
void ring_add(int element){
    ring_buffer[ring_wrt]=element;
    ring_wrt=(ring_wrt+1)%RING_MAX;
    if(ring_cnt<RING_MAX)
        ring_cnt++;
}
/* -------------------------------------
古い要素を上書きしない追加処理
------------------------------------- */
int ring_push(int element){
    if(ring_cnt==RING_MAX)
        return -1;/* 要素が一杯なのでエラー */
    ring_add(element);
    return 0;
}
/* -------------------------------------
古い要素を順次呼び出す処理
------------------------------------- */
int ring_pop(void){
    if(ring_cnt==0)
        return -1;/* 要素が無いのでエラー */
    ring_cnt--;
    ring_wrt=(RING_MAX+ring_wrt-1)%RING_MAX;
    return ring_buffer[ring_wrt];
}
/* -------------------------------------
バッファー内を表示する処理
------------------------------------- */
void ring_print(void){
    int now,i;
    if(ring_cnt==0){
    /* 要素がありません */
        printf("c - p : empty\n");
        return;
    }
    now=(RING_MAX+ring_wrt-1)%RING_MAX;
    printf("%2d - %d : ",ring_cnt,ring_wrt);
    for(i=0;i<ring_cnt;i=i++,now=(RING_MAX+now-1)%RING_MAX)
        printf("%2d-",ring_buffer[now]);
    printf("\n");
}
/* ---------------------------------- */
void ring_push_print(int i){
    printf("%2d -> ",i);
    if(ring_push(i)<0){
        printf("9 - 9 : over flow\n");
    }else{
        ring_print();
    }
}
/* ---------------------------------- */
void ring_pop_print(void){
    int i;
    if((i=ring_pop())<0){
        printf("--          : pop empty\n",i);
    }else{
        printf("%2d <- ",i);
        ring_print();
    }
}
/* ---------------------------------- */
void main(void)
{
    int i;
    printf("el <> ");
    ring_print();/* 要素が無い時の表示テスト */
    /* オーバーした時のチェックとして一回余計に回しています。 */
    for(i=0;i<=RING_MAX;i++)
        ring_push_print(i);
    /* オーバーした時のチェックとして一回余計に回しています。 */
    for(i=0;i<=RING_MAX;i++)
        ring_pop_print();
    /* 二歩進んで一歩引く形でバッファー境の処理の確認 */
    for(i=0;i<=RING_MAX*3;i++){
        ring_push_print(i);
        if(i&1)
            ring_pop_print();
    }
    /* オーバーライト時のテスト */
    ring_cnt=ring_wrt=0;
    for(i=0;i<=RING_MAX*3;i++)
    {
        printf("%2d -> ",i);
        ring_add(i);
        ring_print();
    }
}

実は…
これらは、キューの処理を目的にしていないのですね。
普通は、キュー処理を目的なんですが…。

『古い要素を上書きする追加処理』で
分かったら凄い。

これは、アドベンチャーの
会話のバックログ用の処理なんですね。

でも、キューとしても当然使えるし
他にも色々と使いでが有りますぜ!
如何?

|

« こいつは、良いかも。更新無料セキュリティソフト | トップページ | 初めて見たよ『コレジャナイロボ』! »

コメント

コメントを書く



(ウェブ上には掲載しません)




トラックバック

この記事のトラックバックURL:
http://app.cocolog-nifty.com/t/trackback/108365/10339175

この記事へのトラックバック一覧です: リングバッファーについて♪:

« こいつは、良いかも。更新無料セキュリティソフト | トップページ | 初めて見たよ『コレジャナイロボ』! »