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>
37 : class RingPtr
38 : {
39 : public:
40 0 : inline T value() const { return ptrVal; };
41 : inline T ptr(T num) const { return ((ptrVal % num) + ptrAdjust) % num; };
42 0 : inline T ptr(T num, T off) const
43 : {
44 0 : return ((ptrVal % num) + ptrAdjust + off) % num;
45 : };
46 :
47 0 : void incr(T num, T amount)
48 : {
49 0 : T optrVal = ptrVal;
50 0 : ptrVal += amount;
51 : /* Since the length of the ring is not a power of two we need to
52 : correct when there is a wrap around. This scheme puts the bulk of
53 : the cost of that calculation at incr time, not at access time.*/
54 0 : if (ptrVal < optrVal)
55 0 : ptrAdjust = (ptrAdjust + ((T)(-1) % num) + 1) % num;
56 0 : }
57 0 : inline void clear()
58 : {
59 0 : ptrVal = 0;
60 0 : ptrAdjust = 0;
61 0 : };
62 :
63 0 : inline RingPtr()
64 : : ptrVal(0)
65 0 : , ptrAdjust(0){};
66 :
67 : private:
68 : T ptrVal;
69 : T ptrAdjust;
70 : };
71 :
72 : template <typename T, unsigned int NUM>
73 : class Ring
74 : {
75 : public:
76 : enum
77 : {
78 : HEAD = 0,
79 : MIDDLE = NUM / 2,
80 : TAIL = NUM - 1
81 : };
82 :
83 0 : inline T size() const { return num; };
84 0 : inline bool isEmpty(unsigned int ID1, unsigned int ID2) const
85 : {
86 0 : return ptrs[ID1].value() == ptrs[ID2].value();
87 : };
88 0 : inline bool isFull(unsigned int ID1, unsigned int ID2) const
89 : {
90 0 : return available(ID1, ID2) == num;
91 : };
92 0 : inline T available(unsigned int ID1, unsigned int ID2) const
93 : {
94 0 : return ptrs[ID1].value() - ptrs[ID2].value();
95 : };
96 0 : inline T negAvailable(unsigned int ID1, unsigned int ID2) const
97 : {
98 0 : return num - available(ID1, ID2);
99 : };
100 : inline bool isEqual(unsigned int ID1, unsigned int ID2) const
101 : {
102 : return ptrs[ID1].value() == ptrs[ID2].value();
103 : };
104 :
105 0 : inline void incr(unsigned int ID, T amount = 1)
106 : {
107 0 : ptrs[ID].incr(num, amount);
108 0 : };
109 0 : inline T ptr(unsigned int ID, T off = 0) const
110 : {
111 0 : return ptrs[ID].ptr(num, off);
112 : };
113 : inline T value(unsigned int ID) const { return ptrs[ID].value(); };
114 : /* This moves the pointer to a new value. The new pointer is thought of as
115 : ahead of the old one, and buffer indicies are adjusted
116 : appropriately. */
117 : inline void moveValue(unsigned int ID, T val) { incr(ID, val - value(ID)); }
118 : // Simple accessors for the head/tail
119 0 : inline bool isEmpty() const { return isEmpty(HEAD, TAIL); };
120 0 : inline bool isFull() const { return isFull(HEAD, TAIL); };
121 0 : inline T available() const { return available(HEAD, TAIL); };
122 0 : inline T negAvailable() const { return negAvailable(HEAD, TAIL); };
123 : inline T head(T off = 0) const { return ptr(HEAD, off); };
124 0 : inline void incrHead(T amount = 1) { incr(HEAD, amount); };
125 0 : inline T tail(T off = 0) const { return ptr(TAIL, off); };
126 0 : inline void incrTail(T amount = 1) { incr(TAIL, amount); };
127 : /* Return the number of consecutive entries between ID1 and ID2, such that
128 : bptr(ID2) + linearSize() does not pass ID1 or the end of the buffer. */
129 : T linearSize(unsigned int ID1, unsigned int ID2) const
130 : {
131 : T avail = available(ID1, ID2);
132 : T id2 = ptr(ID2);
133 : T left = size() - id2;
134 : if (avail < left)
135 : return avail;
136 : return left;
137 : }
138 :
139 : /* linearSize is the entries between the pointers (to get from ID2 to ID1)
140 : while negLinearSize is the entries outside the pointers (to get from ID1
141 : to ID2). linearSize is for reading, negLinearSize is for writing. */
142 : T negLinearSize(unsigned int ID1, unsigned int ID2) const
143 : {
144 : T avail = size() - available(ID1, ID2);
145 : T id1 = ptr(ID1);
146 : T left = size() - id1;
147 : if (avail < left)
148 : return avail;
149 : return left;
150 : }
151 :
152 : // Makes ptr(ID) % a == 0
153 : inline void align(unsigned int ID, T a)
154 : {
155 : incr(ID, (a - (ptr(ID) % a)) % a);
156 : }
157 :
158 : /* One usage model is to have the tail pointer be set to the lowest
159 : of several tail pointers. This is usefull if the progress of the
160 : other tails is unrelated. */
161 : void updateTail()
162 : {
163 : T avail = 0;
164 : for (unsigned int I = 1; I < TAIL; I++)
165 : {
166 : T tmp = available(HEAD, I);
167 : if (tmp > avail)
168 : avail = tmp;
169 : }
170 : incrTail(available() - avail);
171 : }
172 :
173 0 : void clear(T newNum)
174 : {
175 0 : for (unsigned int I = 0; I != NUM; I++)
176 0 : ptrs[I].clear();
177 0 : num = newNum;
178 0 : }
179 :
180 0 : inline Ring(T num_)
181 0 : : num(num_){};
182 :
183 : private:
184 : T num;
185 : RingPtr<T> ptrs[NUM];
186 : };
187 :
188 : template <typename BT, typename RT = size_t, unsigned int NUM = 2>
189 : class BufferQ : public Ring<RT, NUM>
190 : {
191 : typedef RT T;
192 : typedef BT buffer_t;
193 : typedef Ring<RT, NUM> RING;
194 :
195 : protected:
196 : buffer_t *buffer;
197 :
198 : inline BufferQ(buffer_t *buffer_, T num_)
199 : : Ring<RT, NUM>(num_)
200 : , buffer(buffer_){};
201 :
202 : public:
203 : enum
204 : {
205 : HEAD = 0,
206 : MIDDLE = NUM / 2,
207 : TAIL = NUM - 1
208 : };
209 :
210 : inline const buffer_t *bptr(unsigned int ID, T off = 0) const
211 : {
212 : return buffer + ptr(ID, off);
213 : }
214 : inline const buffer_t *bhead(T off = 0) const { return bptr(HEAD, off); }
215 : inline const buffer_t *btail(T off = 0) const { return bptr(TAIL, off); }
216 0 : inline buffer_t *bptr(unsigned int ID, T off = 0)
217 : {
218 0 : return buffer + this->ptr(ID, off);
219 : }
220 0 : inline buffer_t *bhead(T off = 0) { return bptr(HEAD, off); }
221 0 : inline buffer_t *btail(T off = 0) { return bptr(TAIL, off); }
222 0 : inline buffer_t &get()
223 : {
224 0 : buffer_t *res = bhead();
225 0 : RING::incrHead();
226 0 : return *res;
227 : };
228 0 : inline void put(const buffer_t &val)
229 : {
230 0 : *btail() = val;
231 0 : RING::incrTail();
232 0 : };
233 :
234 : inline buffer_t *bufferPtr() const { return buffer; };
235 0 : void clear(T newNum = RING::size())
236 : {
237 0 : if (newNum != RING::size())
238 : {
239 0 : delete[] buffer;
240 0 : buffer = new buffer_t[newNum];
241 : }
242 0 : return RING::clear(newNum);
243 : }
244 :
245 0 : inline BufferQ(T num_)
246 0 : : Ring<RT, NUM>(num_)
247 : {
248 0 : buffer = new buffer_t[num_];
249 0 : }
250 0 : inline ~BufferQ() { delete[] buffer; }
251 : };
252 :
253 : /* The track version of BufferQ extends an existing BufferQ with an additional
254 : set of pointers, but they still share the same memory region. */
255 : template <typename BT, typename RT = size_t, unsigned int NUM = 2>
256 : class BufferQTrack : public BufferQ<BT, RT, NUM>
257 : {
258 : typedef RT T;
259 : typedef BT buffer_t;
260 : typedef Ring<RT, NUM> RING;
261 : typedef BufferQ<BT, RT, NUM> BUFFERQ;
262 :
263 : void clear(T newNum);
264 :
265 : public:
266 : template <unsigned int T>
267 : inline void clear(const BufferQ<BT, RT, T> &parent)
268 : {
269 : BUFFERQ::buffer = parent.bufferPtr();
270 : RING::clear(parent.size());
271 : }
272 :
273 : template <unsigned int T>
274 : inline BufferQTrack(const BufferQ<BT, RT, T> &parent)
275 : : BufferQ<BT, RT, NUM>(parent.bufferPtr(), parent.size())
276 : {
277 : }
278 : inline ~BufferQTrack() { BUFFERQ::buffer = 0; }
279 : };
280 :
281 : #endif // CO_RING_H
|
