* Created on: Apr 14, 2010
* Author: jmakuch
*/
#ifndef FIXEDQUEUE_H_
#define FIXEDQUEUE_H_
#include <stdint.h>
template <int I> struct FixedInt {
enum { value = I };
};
/** confirms whether I is an exponent of two - explodes if not. */
template<unsigned I> struct Exp2 {
enum { value = ((I - 1) & I)?0:I,
error_I_not_exp_of_two = sizeof(char[value])};
};
template <int I> struct Sub {
enum { value = I - 1 };
};
template <int S> struct B_Size {};
template <> struct B_Size <4> { typedef uint32_t Type; };
template <> struct B_Size<2> { typedef uint16_t Type; };
template <> struct B_Size<1> { typedef uint8_t Type; };
/** counter is currently only good up to 2^32... not good fer filesystems, I guess.*/
template <unsigned long Max> struct UnsignedCounter {
public:
enum { s = (Max <= 0x10000)?((Max <= 0x100)?1:2):4 };
};
/** queue what attempts to use a minimal representation, and simple fast
* operations. Since we can't return an error on embedded platforms, I am
* sceptical whether it is warranted to check over/underflows.
* Without error checking, adding to a full queue should either overwrite
* the oldest element, or be dropped. Removing from an empty queue will have
* to return garbage, or a bogus value if possible, but should not affect
* the state of the queue.
* This impl drops inserts when full, and returns the last value returned
* when eating from empty.
* The non-checking versions are for when the user is already checking - not
* to shave ticks otherwise. */
template <unsigned long Size, class T> class FixedQueue {
protected:
T buffer[Exp2<Size>::value];
typedef typename B_Size<UnsignedCounter<Size>::s>::Type UC_T;
static const UC_T mask = Size - 1;
UC_T count;
UC_T first;
public:
FixedQueue() : count(0), first(0) {}
/** non-checking version, for when user is checking properly themselves. */
void unsafe_insert(T element) {
buffer[(first+count) & mask] = element;
count++;
}
.
.
.