source: nanovis/trunk/CircularQueue.h @ 4822

Last change on this file since 4822 was 3613, checked in by ldelgass, 11 years ago

Include namespace in header guard defines

  • Property svn:eol-style set to native
File size: 4.7 KB
Line 
1/* -*- mode: c++; c-basic-offset: 4; indent-tabs-mode: nil -*- */
2/* CircularFifo.h
3* Not any company's property but Public-Domain
4* Do with source-code as you will. No requirement to keep this
5* header if need to use it/change it/ or do whatever with it
6*
7* Note that there is No guarantee that this code will work
8* and I take no responsibility for this code and any problems you
9* might get if using it. The code is highly platform dependent!
10*
11* Code & platform dependent issues with it was originally
12* published at http://www.kjellkod.cc/threadsafecircularqueue
13* 2009-11-02
14* @author Kjell Hedström, hedstrom@kjellkod.cc */
15
16#ifndef CIRCULARFIFO_H
17#define CIRCULARFIFO_H
18
19/** Circular Fifo (a.k.a. Circular Buffer)
20* Thread safe for one reader, and one writer */
21template<typename Element, unsigned int Size>
22class CircularFifo {
23public:
24   enum {Capacity = Size+1};
25
26   CircularFifo() : tail(0), head(0){}
27   virtual ~CircularFifo() {}
28
29   bool push(Element& item_);
30   bool pop(Element& item_);
31   bool isEmpty() const;
32   bool isFull() const;
33   
34   // INSOO
35   bool push();
36   int tailIndex();
37   bool pop();
38   bool top(Element&);
39   
40public:
41   volatile unsigned int tail; // input index
42   Element array[Capacity];
43   volatile unsigned int head; // output index
44
45   unsigned int increment(unsigned int idx_) const;
46};
47
48
49
50
51/** Producer only: Adds item to the circular queue.
52* If queue is full at 'push' operation no update/overwrite
53* will happen, it is up to the caller to handle this case
54*
55* \param item_ copy by reference the input item
56* \return whether operation was successful or not */
57template<typename Element, unsigned int Size>
58bool CircularFifo<Element, Size>::push(Element& item_)
59{
60   int nextTail = increment(tail);
61   if(((unsigned int) nextTail) != head)
62   {
63      array[tail] = item_;
64      tail = nextTail;
65      return true;
66   }
67
68   // queue was full
69   return false;
70}
71
72template<typename Element, unsigned int Size>
73bool CircularFifo<Element, Size>::top(Element& data)
74{
75   if(head == tail)
76      return false;  // empty queue
77
78   data = array[head];
79   head = increment(head);
80   return true;
81}
82
83
84/** Consumer only: Removes and returns item from the queue
85* If queue is empty at 'pop' operation no retrieve will happen
86* It is up to the caller to handle this case
87*
88* \param item_ return by reference the wanted item
89* \return whether operation was successful or not */
90template<typename Element, unsigned int Size>
91bool CircularFifo<Element, Size>::pop(Element& item_)
92{
93   if(head == tail)
94      return false;  // empty queue
95
96   item_ = array[head];
97   head = increment(head);
98   return true;
99}
100
101/** Consumer only: Removes and returns item from the queue
102* If queue is empty at 'pop' operation no retrieve will happen
103* It is up to the caller to handle this case
104*
105* \return whether operation was successful or not */
106template<typename Element, unsigned int Size>
107bool CircularFifo<Element, Size>::pop()
108{
109   if(head == tail)
110      return false;  // empty queue
111   head = increment(head);
112   return true;
113}
114
115/** Useful for testinng and Consumer check of status
116  * Remember that the 'empty' status can change quickly
117  * as the Procuder adds more items.
118  *
119  * \return true if circular buffer is empty */
120template<typename Element, unsigned int Size>
121bool CircularFifo<Element, Size>::isEmpty() const
122{
123   return (head == tail);
124}
125
126/** Useful for testing and Producer check of status
127  * Remember that the 'full' status can change quickly
128  * as the Consumer catches up.
129  *
130  * \return true if circular buffer is full.  */
131template<typename Element, unsigned int Size>
132bool CircularFifo<Element, Size>::isFull() const
133{
134   int tailCheck = (tail+1) % Capacity;
135   return (((unsigned int) tailCheck) == head);
136}
137
138/** Increment helper function for index of the circular queue
139* index is inremented or wrapped
140*
141*  \param idx_ the index to the incremented/wrapped
142*  \return new value for the index */
143template<typename Element, unsigned int Size>
144unsigned int CircularFifo<Element, Size>::increment(unsigned int idx_) const
145{
146   // increment or wrap
147   // =================
148   //    index++;
149   //    if(index == array.lenght) -> index = 0;
150   //
151   //or as written below:   
152   //    index = (index+1) % array.length
153   idx_ = (idx_+1) % Capacity;
154   return idx_;
155}
156
157template<typename Element, unsigned int Size>
158int CircularFifo<Element, Size>::tailIndex()
159{
160   int nextTail = increment(tail);
161   if(((unsigned int)nextTail) != head)
162   {
163      return tail;
164   }
165
166   return -1;
167}
168
169
170template<typename Element, unsigned int Size>
171bool CircularFifo<Element, Size>::push()
172{
173   int nextTail = increment(tail);
174   if(((unsigned int)nextTail) != head)
175   {
176      tail = nextTail;
177      return true;
178   }
179
180   return false;
181}
182
183#endif
Note: See TracBrowser for help on using the repository browser.