RingBuffer Code

RingBuf.h

#ifndef RINGBUFH

#define RINGBUFH

// Ring Buffer manager
class RingBuf
{
   public:
       RingBuf(int size);

       void Loop1();
       bool Loop2();
       void Loop3();
       int  LoopIdx();
#define RBFOR(x) for((x)->Loop1();(x)->Loop2();(x)->Loop3())
       // example:
       // RingBuf rb(1024);
       // RBFOR(&rb)
       // {
       //     int i= rb.LoopIdx();
       // }
       int NextStep();
       int NewEntry();

   private:
       int Size;
       int Head;
       int Tail;
       int Tail2;
       int Idx;
};
#endif

RingBuf.cc

#include "RingBuf.h"
#include <stdio.h>
#include <stdlib.h>

/////// Init ////////////////
RingBuf::RingBuf(int size)
{
    Size = size;
    Head = Tail = 0;
    Tail2 = Tail;
}

//////////// Loop ////////////
void RingBuf::Loop1()
{
    Idx = Head;
}

bool RingBuf::Loop2()
{
    return (Idx != Tail);
}

void RingBuf::Loop3()
{
    Idx++;
    if(Idx==Size) Idx=0;
}
int RingBuf:: LoopIdx()
{
    return Idx;
}

int RingBuf::NewEntry()
{
    int res = Tail2;
    Tail2++;
    if(Tail2==Size) Tail2=0;
    if(Tail2 == Head)
    {
	fprintf(stderr, "#RingBuf Size=%d not enough\n", Size);
	exit(1);
    }
    return res;
}

// return size of next buffer
int RingBuf::NextStep()
{
    Head = Tail;
    Tail = Tail2;
    int res = Tail - Head;
    if (res < 0) res += Size;
    return res;
}

#if 1
// test routine
#define L 60
char flag[L*L];
#define xy2i(x,y) ((x)+(y)*L)
#define i2xy(i,x,y) { x=(i)%L;y=(i)/L;}
int main()
{
    int i;
    for(i=0;i<L*L;i++)
    {
	flag[i]=0;
	if (rand()<(int)(RAND_MAX*0.4)) flag[i]=2;
    }

    int x,y;
    x=y=L/2;

    int pbuf[L*3];
    RingBuf rb(L*3);

    int j= rb.NewEntry();
    int pos= xy2i(x,y);
    pbuf[j]=pos;
    flag[pos]=1;
    rb.NextStep();

    while(1)
    {
	// loop over stack
	RBFOR(&rb)
	{
	    //Get Index in the ring buffer
	    int j=rb.LoopIdx();
	    // Get actual value
	    int pos = pbuf[j];

	    //Calculate neighbor
	    i2xy(pos,x,y);
	    int xL=(x-1+L)%L;
	    int xR=(x+1+L)%L;
	    int yU=(y-1+L)%L;
	    int yD=(y+1+L)%L;
	    int pos2[4];
	    pos2[0]=xy2i(xL,y);
	    pos2[1]=xy2i(xR,y);
	    pos2[2]=xy2i(x,yU);
	    pos2[3]=xy2i(x,yD);
	    int k;
	    for(k=0;k<4;k++)
	    {
	        if (flag[pos2[k]]==0)
	        {
		    // Put neighbor into ring buffer
		    // j=index in RingBuffer for new value
		    j= rb.NewEntry();
		    // actually store the value
		    pbuf[j] = pos2[k];
		    flag[pos2[k]]=1;
		}
	    }
	}//Loop

	// move to the next segment in the ring buffer
	int nsiz=rb.NextStep();
	// if next segment is null, end
	if(nsiz==0) break;
    }//while(1)

    // Print result
    for(y=0;y<L;y++){
    for(x=0;x<L;x++){
	printf("%1d",flag[xy2i(x,y)]);
    }
    printf("\n");
    }
}
#endif