While developing a streaming audio application, I found the need for a fast and reliable buffering mechanism. I developed a Queue Class and used it as a buffer, stuffing blocks of data in on one thread and pulling them out on another. The quality of the audio was greatly improved by this buffering mechanism. But I wanted something better, something that would perform as few **conditional **and **allocation **operations as possible. So I developed this circular queue class.

The number of elements in the queue is restricted to powers of two. Keeping track of front, back, overflow, and underflow requires only two internal member variables, one of which is incremented on every enqueue operation, the other is incremented on every dequeue operation (wrapping around to zero is expected and supported behavior). Applying a bitmask to one of these variables reduces the actual number to an “index” of the front or back of the queue, respectively. The bitmask value is calculated from the “size” (number of elements) specified during initialization. Allocation of the array of elements is also performed during initialization.

The only condition checked during an enqueue operation is an overflow test. The only condition checked during a dequeue operation is an underflow test. There is no “is initialized” test in these functions, so be sure to initialize an instance before using it!

Cross-platform permutations of the source (GitHub):

https://github.com/UniversalProgrammingOrganization/upo-lib/blob/master/upo-lib/CircularQueue.h

https://github.com/UniversalProgrammingOrganization/upo-lib/blob/master/upo-lib/CircularQueue.cpp

#define O void // for Object pointers (O*) #define Z NULL // shorthand for NULL class CQ // a circular queue class { public: DWORD m_dwNQs; // total number of enqueue operations DWORD m_dwDQs; // total number of dequeue operations DWORD m_dwIM; // Index Mask - a bitmask O** m_ppE; // pointer to array of elements CQ() { m_ppE = Z; }; ~CQ() { Reset(); }; void Reset() { // free array of elements: if (m_ppE) delete [] m_ppE; m_dwNQs = 0; m_dwDQs = 0; m_dwIM = 0; m_ppE = Z; } bool Init( DWORD dwSize) { // allow object re-use: Reset(); // verify size is not zero: if (dwSize == 0) return false; // calculate the bit mask: m_dwIM = dwSize - 1; // verify size is a power of 2: if (dwSize & (m_dwIM)) return false; // allocate the queue elements: m_ppE = new O*[dwSize]; // will return true only if all of the above succeeded: return (m_ppE != Z); }; // enqueue function: O* NQ(O* pO) { // check for overflow: if (Size() > m_dwIM) return Z; // calculate the enqueue index: DWORD dwEi = (m_dwNQs & m_dwIM); // set the element value: *(m_ppE + dwEi) = pO; // increment enqueue count: m_dwNQs++; return pO; }; // dequeue function: O* DQ() { // get the element value: O* pO = Peek(); // increment dequeue count (if no peek error): if (pO != Z) m_dwDQs++; return pO; }; O* Peek() { // check for underflow: if (Size() == 0) return Z; // calculate the dequeue index: DWORD dwDi = (m_dwDQs & m_dwIM); // return the element value: return *(m_ppE + dwDi); }; // returns the distance between m_dwDQs and m_dwNQs // (the size of the actual queue contents): DWORD Size() { if (m_dwDQs < m_dwNQs) return (m_dwNQs - m_dwDQs); else return (m_dwDQs - m_dwNQs); }; };

The above “Size()” function would look shorter if it was constructed like this:

DWORD Size() { return abs(m_dwDQs - m_dwNQs); };

But the “abs()” function is typically implemented like this:

int abs(int n) { if (n >= 0) return n; else return -n; };