Michele Moccia wrote:
How can I implement a "time critical" fifo in c++ ?
I just have to manage sequences of raw bytes, no user defined types.
An std::queue<unsigned char> or std::deque<unsigned char> seems to be
slow. I've compared that to a platform depended solution (i tried to use a
MS Window pipe in the same process to create a fifo and it's very faster).
I don't know if this is fast (I am not even sure whether it is correct),
but if you want to try, feel free. If you get some benchmarks, please post
them:
#include <list>
#include <memory>
template < typename T, std::size_t N=1024,
typename Alloc=std::allocator<T> >
class fifo {
public:
typedef T value_type;
typedef std::size_t size_type;
typedef value_type & reference;
typedef value_type const & const_reference;
typedef value_type * pointer;
typedef value_type const * const_pointer;
private:
struct Block : public Alloc {
pointer const b;
Block ( void )
: b( Alloc::allocate(N) )
{}
void clear ( void ) {
Alloc::deallocate( b, N );
}
pointer begin ( void ) const {
return ( b );
}
pointer end ( void ) const {
return ( b+N );
}
};
std::list< Block > blocks;
size_type the_size;
pointer out_pointer;
pointer out_end;
pointer in_pointer;
pointer in_end;
public:
fifo ( void )
: blocks ( 1, Block() )
, the_size ( 0 )
, out_pointer ( blocks.front().begin() )
, out_end ( blocks.front().end() )
, in_pointer ( blocks.front().begin() )
, in_end ( blocks.front().end() )
{
assert( ! blocks.empty() );
}
bool empty ( void ) const {
return ( the_size == 0 );
}
size_type size ( void ) const {
return ( the_size );
}
reference front ( void ) {
return ( *out_pointer );
}
const_reference front ( void ) const {
return ( *out_pointer );
}
reference back ( void ) {
return ( *(in_pointer-1) );
}
const_reference back ( void ) const {
return ( *(in_pointer-1) );
}
void push ( const_reference x ) {
if ( in_pointer == in_end ) {
blocks.push_back( Block() );
in_pointer = blocks.back().begin();
in_end = blocks.back().end();
}
blocks.back().construct( in_pointer, x );
++ in_pointer;
++ the_size;
}
void pop ( void ) {
blocks.front().destroy( out_pointer );
++ out_pointer;
if ( out_pointer == out_end ) {
blocks.front().clear();
blocks.pop_front();
if ( blocks.empty() ) {
blocks.push_back( Block() );
in_pointer = blocks.back().begin();
in_end = blocks.back().end();
}
out_pointer = blocks.front().begin();
out_end = blocks.front().end();
}
-- the_size;
}
void clear ( void ) {
// FIXME: [this might be slow]
while ( the_size > 0 ) {
pop();
}
}
}; // fifo<>
Best
Kai-Uwe Bux