 |
|
 |
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 .
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<<g;
}
unsigned char buffer[1024];
void FlatenCircular(
char *buffer,
int hd, //the index of head
int sz, //size of buffer
int lt //number of used elements of buffer
)
{
long l_gcd = gcd(sz, hd); //gcd, number of external for cycles
int stp = sz / l_gcd; //number of internal for cycles
int sum = sz - hd; //
int rd, swp; // read, swap
for (int j=0; j < l_gcd; j++)
{
int y = (hd + j) % sz;
char rd = buffer[y];
for (int i=0; i < stp;i++)
{
y = (y + sum) % sz;
swp = buffer[y];
buffer[y] = rd;
rd = swp;
}
}
}
void main(){
long cd = 1171;
long l1 = 1103*1109*cd;
long l2 = 1129*1151*cd;
printf("%d\n",gcd( l1,l2));
unsigned char d=0;
for(int i=500; i<1524; i++ )
buffer[i%1024] = d++;
FlatenCircular( (char*)&buffer[0], 500,1024, 1024);
d=0;
for(i=0; i<1024; i++ )
if( buffer[i] != d++ )
printf("Error At index %d\n",i );
}
|
|
|
|
 |
|
 |
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 );
}
|
|
|
|
 |
 | bugs  |  | fred huang | 11:54 6 Sep '00 |
|
 |
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;
}
|
|
|
|
 |
|