Circular Queue Class

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;
    };

415 Replies to “Circular Queue Class”

  1. Pingback: continued here
  2. Pingback: notehub.org
  3. Pingback: more info
  4. Pingback: page address
  5. Pingback: notehub.org
  6. Pingback: notehub.org
  7. Pingback: notehub.org
  8. Pingback: notehub.org
  9. Pingback: go here
  10. Pingback: notehub.org
  11. Pingback: more info
  12. Pingback: follow the link
  13. Pingback: notehub.org link
  14. Pingback: Cialis prices
  15. Pingback: link to the page
  16. Pingback: find out more
  17. Pingback: pronvipse.mobi
  18. Pingback: visit web page
  19. Pingback: link
  20. Pingback: topsexportal.mobi
  21. Pingback: topdatingse.mobi
  22. Pingback: follow the link
  23. Pingback: solars.biz
  24. Pingback: Cheap cialis
  25. Pingback: ABrand
  26. Pingback: buy cialis
  27. Pingback: cialis
  28. Pingback: sildenafil 100mg
  29. Pingback: cialis generic
  30. Pingback: cialis coupon
  31. Pingback: cialis 20mg
  32. Pingback: levitra
  33. Pingback: generic cialis
  34. Pingback: tadalafil 5mg
  35. Pingback: tadalafil 20mg
  36. Pingback: viagra tablets
  37. Pingback: sildenafil
  38. Pingback: tadalafil
  39. Pingback: cialis dosage
  40. Pingback: cialis prices
  41. Pingback: viagra connect
  42. Pingback: tadalafil 20 mg
  43. Pingback: tadalafil generic
  44. Pingback: cialis online
  45. Pingback: cialis tablets
  46. Pingback: cialis 5 mg
  47. Pingback: cheap cialis
  48. Pingback: cialis coupons
  49. Pingback: cialis canada
  50. Pingback: generic viagra
  51. Pingback: sildenafil citrate
  52. Pingback: viagra pills
  53. Pingback: viagra online
  54. Pingback: viagra prices
  55. Pingback: viagra generic
  56. Pingback: cheap viagra
  57. Pingback: buy viagra online
  58. Pingback: sildenafil 100
  59. Pingback: buy biaxin
  60. Pingback: buy ceftin
  61. Pingback: buy chloromycetin
  62. Pingback: buy biaxin online
  63. Pingback: buy ceftin online
  64. Pingback: buy viagra
  65. Pingback: free bitcoin cash
  66. Pingback: Viagra pills
  67. Pingback: Cialis prices
  68. Pingback: buy cialis online
  69. Pingback: cialis cost
  70. Pingback: cialis cooupons
  71. Pingback: cialis free trial
  72. Pingback: atorvastatin
  73. Pingback: cymbalta
  74. Pingback: levitra generic
  75. Pingback: atorvastatin 10 mg
  76. Pingback: cymbalta dosage
  77. Pingback: atorvastatin 10mg
  78. Pingback: cymbalta for pain
  79. Pingback: levitra 20 mg
  80. Pingback: cialis pills
  81. Pingback: cymbalta generic
  82. Pingback: levitra coupon
  83. Pingback: levitra dosage
  84. Pingback: cymbalta reviews
  85. Pingback: cialis vs viagra
  86. Pingback: levitra vs viagra
  87. Pingback: vardenafil
  88. Pingback: duloxetine
  89. Pingback: vardenafil 20 mg
  90. Pingback: viagra vs cialis
  91. Pingback: duloxetine 20 mg
  92. Pingback: vardenafil 20mg
  93. Pingback: duloxetine hcl
  94. Pingback: duloxetine 60 mg
  95. Pingback: Cheap
  96. Pingback: augmentin
  97. Pingback: levaquin
  98. Pingback: augmentin 875
  99. Pingback: buy levitra
  100. Pingback: levaquin 500 mg
  101. Pingback: augmentin 875 mg
  102. Pingback: levaquin 750 mg
  103. Pingback: cheap levitra
  104. Pingback: buy levitra online
  105. Pingback: generic levitra
  106. Pingback: sildenafil coupons
  107. Pingback: cialis 20 mg
  108. Pingback: levaquin dosage
  109. Pingback: augmentin dosage
  110. Pingback: sildenafil tablets
  111. Pingback: levaquin for uti
  112. Pingback: augmentin dose
  113. Pingback: levaquin lawsuit
  114. Pingback: augmentin for dogs
  115. Pingback: viagra
  116. Pingback: levitra 20mg
  117. Pingback: viagra 100mg
  118. Pingback: augmentin for uti
  119. Pingback: levitra cost
  120. Pingback: viagra coupons
  121. Pingback: levaquin uses
  122. Pingback: augmentin uses
  123. Pingback: what is levaquin
  124. Pingback: levitra online
  125. Pingback: what is augmentin
  126. Pingback: levitra prices
  127. Pingback: viagra tablet
  128. Pingback: cialis pharmacy
  129. Pingback: cialis generico
  130. Pingback: levitra recviews
  131. Pingback: cialis generika
  132. Pingback: levitra vs cialis
  133. Pingback: vardenafil generic
  134. Pingback: what is levitra
  135. Pingback: tadalafila
  136. Pingback: free cialis
  137. Pingback: 5mg cialis
  138. Pingback: free cialis coupon
  139. Pingback: cialis copay card
  140. Pingback: canadian cialis
  141. Pingback: cialis price
  142. Pingback: cialis daily
  143. Pingback: cialis reviews
  144. Pingback: generic for cialis
  145. Pingback: cialis samples
  146. Pingback: cialis saving card
  147. Pingback: liquid cialis
  148. Pingback: cialis for sale
  149. Pingback: cialis for women
  150. Pingback: cialis soft
  151. Pingback: natural cialis
  152. Pingback: cialis 5mg
  153. Pingback: cialis 5mg coupon
  154. Pingback: cialis from canada
  155. Pingback: cialis walmart
  156. Pingback: cialis wikipedia
  157. Pingback: online cialis
  158. Pingback: otc cialis
  159. Pingback: cialis and alcohol
  160. Pingback: cialis medication
  161. Pingback: cost of cialis
  162. Pingback: cialis black
  163. Pingback: cialis on line
  164. Pingback: discount cialis
  165. Pingback: Viagra levitra
  166. Pingback: dutch women viagra
  167. Pingback: female viagra
  168. Pingback: natural viagra
  169. Pingback: sophia viagra
  170. Pingback: viagra for men
  171. Pingback: viagra for sale
  172. Pingback: viagra for women
  173. Pingback: viagra sex
  174. Pingback: cialis prices 10mg
  175. Pingback: cialis prices 20mg
  176. Pingback: cialis prices 5mg
  177. Pingback: sildenafil 20 mg
  178. Pingback: sildenafil dosage
  179. Pingback: sildenafil generic
  180. Pingback: canadian viagra
  181. Pingback: cost of viagra
  182. Pingback: herbal viagra
  183. Pingback: online viagra
  184. Pingback: real viagra
  185. Pingback: viagra alternative
  186. Pingback: viagra cost
  187. Pingback: cialis vs levitra
  188. Pingback: viagra in action
  189. Pingback: viagra on line
  190. Pingback: viagra pill
  191. Pingback: viagra price
  192. Pingback: viagra on line
  193. Pingback: pharmacie
  194. Pingback: pharmacy online
  195. Pingback: tadalafil 20mg
  196. Pingback: cialis prices
  197. Pingback: canadian pharmacy
  198. Pingback: buy viagra
  199. Pingback: buy generic cialis
  200. Pingback: we-b-tv.com
  201. Pingback: hs;br
  202. Pingback: tureckie_serialy
  203. Pingback: 00-tv.com
  204. Pingback: +1+
  205. Pingback: watch
  206. Pingback: ++++++
  207. Pingback: HD-720
  208. Pingback: 2020
  209. Pingback: Video
  210. Pingback: wwin-tv.com

Comments are closed.