A circular character buffer

If an application requires occasionally a big buffer, but normally uses only a small portion, we could use more efficiently the memory by using dinamic allocation.

The problem is that if a string starts at bottom and terminate at top, a realloc will fragment our block.

I propose this algorithm to avoid this, thus we could use dinamic reallocation.

The complexity is O(n), we can optimize it to obtain O(n/sizeof(int)), aligning strings in buffer, and the buffer too, to sizeof(int).

Variables:
hd; //the index of head
sz; //size of buffer
lt; //number of used elements of buffer
gcd = gcd(sz, hd); //gcd, number of external for cycles
stp = sz / mcd; //number of internal for cycles
sum = sz - hd; //
i, j; //counters
rd, swp// readed, swap

for (j=0; j < mcd; j++)
{
y = (hd + j) % sz;
rd = buffer[y];
for (i=0; i < stp;i++)
{
y = (y + sum) % sz;
swp = buffer[y];
buffer[y] = rd;
rd = swp;
}
}
//if we use pointers to head and tail we must move them
pHead = buffer;
pTail = buffer[lt];

Because of my low mathematical skill, I can't give a demonstration, but I tried it and it works Big Grin | :-D

.

Andrea Simonassi

here it is for c & C++ programmers
UDria, it is a magnificent algorithm. 10x

long gcd (long x, long y)
{
long temp;
long g;

if (x < y) { temp = x; x = y; y = temp; }

g = 0;
while ((0 == (x & 1)) && (0 == (y & 1))) { /* While both even */
x >>= 1; y >>= 1; g++;
}
while (x != 0) {
while (0 == (x & 1)) { x >>= 1; }
while (0 == (y & 1)) { y >>= 1; }
temp = (x-y)/2; if (temp<0) { temp = -temp; }
if (x >= y) {
x = temp;
} else {
y = temp;
}
}
return y<

Hi,

I think there might be another little mistake in the circular buffer class code. In function
CircularBuffer::read(BYTE* data, long length),

the following line of code:
if ( lenToEnd > 0 )
{
memcpy( data, &que[read], lenToEnd );
}

should be in fact:
if ( lenToEnd > 0 )
{
memcpy( data, &que[read], length );
}

This error was trying to copy too much read data into the target string, unless the target string was as big as the
buffer of the CircularBuffer...

Cheers

In fact, the proper part of code should be:

// copy buffer from read position. Check for end position as well.
if ( lenToEnd > length )
{
memcpy( data, &que[read], length );
}
else
{
memcpy( data, &que[read], lenToEnd );
}

:

A better usage should be that single line of code :

long lenToEnd = (length > (lenToEnd = lengthToEnd(idWrite))) ? lenToEnd : length;

Instead of :

In fact, the proper part of code should be:

// copy buffer from read position. Check for end position as well.
if ( lenToEnd > length )
{
memcpy( data, &que[read], length );
}
else
{
memcpy( data, &que[read], lenToEnd );
}

The CircularBuffer::incPos has an error,

*pos += lenToEnd should be *pos += inc

Also, the program does not take into account in read and write procedures when data to be read or written is less than length to end of queue.

Submitted By: Fred Huang (2000/09/06)

Fred,

Hopefully better source code.

Greetings Jan Marco

// inc read/write pos based
// on operation
bool CircularBuffer::incPos ( long inc, long op )
{
long * pos = NULL;
long lenToEnd = 0;
// if inc > que size stop
if ( inc < 0 || inc > m_queSz )
{
return false;
}
// get pos to modify
pos = &m_write;
if ( op == idRead )
{
pos = &m_read;
}
// get len to que end
lenToEnd = lengthToEnd(op);

// if inc not beyond que end
if ( inc <= lenToEnd )
{
*pos += inc;
}
else
{
// set pos to length from start
// because of wrap
*pos = inc - lenToEnd;

// could set wrap event here
}

// if either pos has wrapped to other
if ( m_read == m_write )
{
m_wrapType = idWriteWrap;
if ( op == idRead )
{
m_wrapType = idReadWrap;
}
}
else
{
m_wrapType = idNoWrap;
}

if (m_read == m_queSz)
{
if (m_write == m_queSz)
{
m_read = 0;
m_write = 0;
}
else
{
m_read = 0;
}
}

return true;
}

bool CircularBuffer::read ( BYTE * data, long length )
{
long lenRemaining = 0;
long lenToEnd = 0;

// show data block to long
if ( length < 0 || length > m_queSz )
{
memset(data, 0, length);
return false;
}
// set read lock
if ( !m_lock.lock() )
{
memset(data, 0, length);
return false;
}

// read length to que end
lenToEnd = lengthToEnd(idRead);

if (lenToEnd >= length)
{
if ((m_read+length) <= m_write)
{
if (length > 0 )
{
memcpy(data, &m_que[m_read], length);
// inc read pos
incPos( length, idRead );
}
}
else
{
if ((m_write < m_read))
{
if (length > 0 )
{
memcpy(data, &m_que[m_read], length);
incPos( length, idRead );
}
}
else
{
//buffer is empty
memset(data, 0, length);
m_lock.unlock();
return false;
}
}
}
else
{
lenRemaining = length - lenToEnd;
if ((m_write < m_read) && (m_write >=lenRemaining))
{
if (lenToEnd > 0 )
{
memcpy(data, &m_que[m_read], lenToEnd );
}

if (lenRemaining > 0 )
{
memcpy(&data[lenToEnd], &m_que[0], lenRemaining );
}
incPos( length, idRead );
}
else
{
//buffer is empty
memset(data, 0, length);
m_lock.unlock();
return false;
}
}

m_lock.unlock();
return true;
}

bool CircularBuffer::write ( BYTE * data, long length )
{
long lenRemaining = 0;
long lenToEnd = 0;

// show data block to long
if ( length < 0 || length > m_queSz )
{
return false;
}
// wait for write lock
if ( !m_lock.lock() )
{
return false;
}
// read length to que end

lenToEnd = lengthToEnd(idWrite);

if (lenToEnd >= length)
{
if ((m_read <= m_write) || ( (m_write+length) <= m_read))
{
memcpy( &m_que[m_write], data, length);
incPos( length, idWrite );
}
else
{ //buffer is full
}
}
else
{
lenRemaining = length - lenToEnd;
if ((m_read <= m_write) && (m_read >=lenRemaining))
{
if (lenToEnd > 0 )
{
memcpy(&m_que[m_write], data, lenToEnd );
}

if (lenRemaining > 0 )
{
memcpy(&m_que[0], &data[lenToEnd], lenRemaining );
}
incPos( length, idWrite );
}
else
{
//buffer is full
}
}

m_lock.unlock();

// set recieve event
m_rxEvent.set();

return true;
}

A circular character buffer

License

Comments and Discussions