Line data Source code
1 : // -*- mode: c++ -*-
2 : /* $Header$
3 :
4 : This is a fixed size ring buffer structure. The Ring class maintains ring
5 : pointers, and the BufferQ class provides a deque-like fixed size buffer.
6 :
7 : The buffer pointers operate on two rings, the first is formed from ring_t
8 : (aka the integer group Z_(2^sizeof(ring_t)*8) which is the primary ring,
9 : and the secondary is formed on Z_num. Converting from the primary to
10 : secondary ring is done in a way that supports arbitary values of num, not
11 : just powers of two.
12 :
13 : The net result is particularly useful for many application that might
14 : otherwise use a linked list, so long as the number of entries has an upper
15 : bound. This is particularly well suited as the underlying storage for
16 : several IB constructs - for instance the entire storage can be registered
17 : with no fear of DMAs destroying link pointers.
18 :
19 : Since the BufferQ does not do object construct/object destroy as the list
20 : circulates it is also very useful for avoiding certain kinds of memory
21 : allocation overheads (ie for std::string)
22 :
23 : When used with multiple ring pointers some very useful and efficient
24 : queuing constructs can be easially described, including multiple cascading
25 : lists, and independent progress of parallel actions on the same data.
26 :
27 : This source is placed in the Public Domain, do with it what you will
28 : It was originally written by Jason Gunthorpe.
29 : */
30 :
31 : #ifndef CO_RING_H
32 : #define CO_RING_H
33 :
34 : #include <sys/types.h>
35 :
36 : template< typename T > class RingPtr
37 : {
38 : public:
39 6241828 : inline T value() const {return ptrVal;};
40 : inline T ptr(T num) const {return ((ptrVal % num) + ptrAdjust) % num;};
41 4079369 : inline T ptr(T num,T off) const {return ((ptrVal % num) + ptrAdjust + off) % num;};
42 :
43 4220897 : void incr(T num,T amount)
44 : {
45 4220897 : T optrVal = ptrVal;
46 4220897 : ptrVal += amount;
47 : /* Since the length of the ring is not a power of two we need to
48 : correct when there is a wrap around. This scheme puts the bulk of
49 : the cost of that calculation at incr time, not at access time.*/
50 4220897 : if (ptrVal < optrVal)
51 7 : ptrAdjust = (ptrAdjust + ((T)(-1) % num) + 1) % num;
52 4220897 : }
53 76 : inline void clear() {ptrVal = 0; ptrAdjust = 0;};
54 :
55 74 : inline RingPtr() : ptrVal(0), ptrAdjust(0) {};
56 :
57 : private:
58 : T ptrVal;
59 : T ptrAdjust;
60 : };
61 :
62 : template< typename T, unsigned int NUM > class Ring
63 : {
64 : public:
65 :
66 : enum {HEAD = 0, MIDDLE = NUM/2, TAIL = NUM-1};
67 :
68 24 : inline T size() const {return num;};
69 2 : inline bool isEmpty(unsigned int ID1,unsigned int ID2) const
70 2 : {return ptrs[ID1].value() == ptrs[ID2].value();};
71 644922 : inline bool isFull(unsigned int ID1,unsigned int ID2) const
72 644922 : {return available(ID1,ID2) == num;};
73 3124057 : inline T available(unsigned int ID1,unsigned int ID2) const
74 3124057 : {return ptrs[ID1].value() - ptrs[ID2].value();};
75 1574198 : inline T negAvailable(unsigned int ID1,unsigned int ID2) const
76 1574198 : {return num - available(ID1,ID2);};
77 : inline bool isEqual(unsigned int ID1,unsigned int ID2) const
78 : {return ptrs[ID1].value() == ptrs[ID2].value();};
79 :
80 4260886 : inline void incr(unsigned int ID,T amount = 1) {ptrs[ID].incr(num,amount);};
81 4084306 : inline T ptr(unsigned int ID,T off = 0) const {return ptrs[ID].ptr(num,off);};
82 : inline T value(unsigned int ID) const {return ptrs[ID].value();};
83 :
84 : /* This moves the pointer to a new value. The new pointer is thought of as
85 : ahead of the old one, and buffer indicies are adjusted
86 : appropriately. */
87 : inline void moveValue(unsigned int ID,T val) {incr(ID,val - value(ID));}
88 :
89 : // Simple accessors for the head/tail
90 2 : inline bool isEmpty() const {return isEmpty(HEAD,TAIL);};
91 644922 : inline bool isFull() const {return isFull(HEAD,TAIL);};
92 442791 : inline T available() const {return available(HEAD,TAIL);};
93 1574198 : inline T negAvailable() const {return negAvailable(HEAD,TAIL);};
94 :
95 : inline T head(T off = 0) const {return ptr(HEAD,off);};
96 2268445 : inline void incrHead(T amount = 1) {incr(HEAD,amount);};
97 442791 : inline T tail(T off = 0) const {return ptr(TAIL,off);};
98 1528893 : inline void incrTail(T amount = 1) {incr(TAIL,amount);};
99 :
100 : /* Return the number of consecutive entries between ID1 and ID2, such that
101 : bptr(ID2) + linearSize() does not pass ID1 or the end of the buffer. */
102 : T linearSize(unsigned int ID1,unsigned int ID2) const
103 : {
104 : T avail = available(ID1,ID2);
105 : T id2 = ptr(ID2);
106 : T left = size() - id2;
107 : if (avail < left)
108 : return avail;
109 : return left;
110 : }
111 :
112 : /* linearSize is the entries between the pointers (to get from ID2 to ID1)
113 : while negLinearSize is the entries outside the pointers (to get from ID1
114 : to ID2). linearSize is for reading, negLinearSize is for writing. */
115 : T negLinearSize(unsigned int ID1,unsigned int ID2) const
116 : {
117 : T avail = size() - available(ID1,ID2);
118 : T id1 = ptr(ID1);
119 : T left = size() - id1;
120 : if (avail < left)
121 : return avail;
122 : return left;
123 : }
124 :
125 : // Makes ptr(ID) % a == 0
126 : inline void align(unsigned int ID,T a)
127 : {
128 : incr(ID,(a - (ptr(ID) % a)) % a);
129 : }
130 :
131 : /* One usage model is to have the tail pointer be set to the lowest
132 : of several tail pointers. This is usefull if the progress of the
133 : other tails is unrelated. */
134 : void updateTail()
135 : {
136 : T avail = 0;
137 : for (unsigned int I = 1; I < TAIL; I++)
138 : {
139 : T tmp = available(HEAD,I);
140 : if (tmp > avail)
141 : avail = tmp;
142 : }
143 : incrTail(available() - avail);
144 : }
145 :
146 36 : void clear(T newNum )
147 : {
148 112 : for (unsigned int I = 0; I != NUM; I++)
149 76 : ptrs[I].clear();
150 36 : num = newNum;
151 36 : }
152 :
153 34 : inline Ring(T num_) : num(num_) {};
154 :
155 : private:
156 : T num;
157 : RingPtr<T> ptrs[NUM];
158 : };
159 :
160 : template <typename BT,typename RT = size_t,unsigned int NUM = 2>
161 : class BufferQ : public Ring<RT,NUM>
162 : {
163 : typedef RT T;
164 : typedef BT buffer_t;
165 : typedef Ring<RT,NUM> RING;
166 :
167 : protected:
168 :
169 : buffer_t *buffer;
170 :
171 : inline BufferQ(buffer_t *buffer_,T num_) : Ring<RT,NUM>(num_), buffer(buffer_) {};
172 :
173 : public:
174 :
175 : enum {HEAD = 0, MIDDLE = NUM/2, TAIL = NUM-1};
176 :
177 : inline const buffer_t *bptr(unsigned int ID,T off = 0) const {return buffer + ptr(ID,off);}
178 : inline const buffer_t *bhead(T off = 0) const {return bptr(HEAD,off);}
179 : inline const buffer_t *btail(T off = 0) const {return bptr(TAIL,off);}
180 :
181 1139141 : inline buffer_t *bptr(unsigned int ID,T off = 0) {return buffer + this->ptr(ID,off);}
182 568611 : inline buffer_t *bhead(T off = 0) {return bptr(HEAD,off);}
183 570660 : inline buffer_t *btail(T off = 0) {return bptr(TAIL,off);}
184 :
185 568611 : inline buffer_t &get()
186 : {
187 568611 : buffer_t *res = bhead();
188 568611 : RING::incrHead();
189 568612 : return *res;
190 : };
191 570660 : inline void put(const buffer_t &val)
192 : {
193 570660 : *btail() = val;
194 570660 : RING::incrTail();
195 570659 : };
196 :
197 : inline buffer_t *bufferPtr() const {return buffer;};
198 :
199 24 : void clear(T newNum = RING::size())
200 : {
201 24 : if (newNum != RING::size())
202 : {
203 8 : delete [] buffer;
204 8 : buffer = new buffer_t[newNum];
205 : }
206 24 : return RING::clear(newNum);
207 : }
208 :
209 6 : inline BufferQ(T num_) : Ring<RT,NUM>(num_)
210 : {
211 6 : buffer = new buffer_t[num_];
212 6 : }
213 6 : inline ~BufferQ()
214 : {
215 6 : delete [] buffer;
216 6 : }
217 : };
218 :
219 : /* The track version of BufferQ extends an existing BufferQ with an additional
220 : set of pointers, but they still share the same memory region. */
221 : template <typename BT,typename RT = size_t,unsigned int NUM = 2>
222 : class BufferQTrack : public BufferQ<BT,RT,NUM>
223 : {
224 : typedef RT T;
225 : typedef BT buffer_t;
226 : typedef Ring<RT,NUM> RING;
227 : typedef BufferQ<BT,RT,NUM> BUFFERQ;
228 :
229 : void clear(T newNum);
230 :
231 : public:
232 :
233 : template <unsigned int T>
234 : inline void clear(const BufferQ<BT,RT,T> &parent)
235 : {
236 : BUFFERQ::buffer = parent.bufferPtr();
237 : RING::clear(parent.size());
238 : }
239 :
240 : template <unsigned int T>
241 : inline BufferQTrack(const BufferQ<BT,RT,T> &parent) :
242 : BufferQ<BT,RT,NUM>(parent.bufferPtr(),parent.size())
243 : {
244 : }
245 : inline ~BufferQTrack()
246 : {
247 : BUFFERQ::buffer = 0;
248 : }
249 : };
250 :
251 : #endif // CO_RING_H
|
