Line data Source code
1 : /*
2 : * Copyright (c) 2015 Cisco and/or its affiliates.
3 : * Licensed under the Apache License, Version 2.0 (the "License");
4 : * you may not use this file except in compliance with the License.
5 : * You may obtain a copy of the License at:
6 : *
7 : * http://www.apache.org/licenses/LICENSE-2.0
8 : *
9 : * Unless required by applicable law or agreed to in writing, software
10 : * distributed under the License is distributed on an "AS IS" BASIS,
11 : * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 : * See the License for the specific language governing permissions and
13 : * limitations under the License.
14 : */
15 : /*
16 : Copyright (c) 2005 Eliot Dresselhaus
17 :
18 : Permission is hereby granted, free of charge, to any person obtaining
19 : a copy of this software and associated documentation files (the
20 : "Software"), to deal in the Software without restriction, including
21 : without limitation the rights to use, copy, modify, merge, publish,
22 : distribute, sublicense, and/or sell copies of the Software, and to
23 : permit persons to whom the Software is furnished to do so, subject to
24 : the following conditions:
25 :
26 : The above copyright notice and this permission notice shall be
27 : included in all copies or substantial portions of the Software.
28 :
29 : THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
30 : EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
31 : MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
32 : NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
33 : LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
34 : OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
35 : WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
36 : */
37 :
38 : #ifndef included_fifo_h
39 : #define included_fifo_h
40 :
41 : #include <vppinfra/cache.h>
42 : #include <vppinfra/error.h> /* for ASSERT */
43 : #include <vppinfra/vec.h>
44 :
45 : typedef struct
46 : {
47 : /* First index of valid data in fifo. */
48 : u32 head_index;
49 :
50 : /* One beyond last index in fifo. */
51 : u32 tail_index;
52 : } clib_fifo_header_t;
53 :
54 : always_inline clib_fifo_header_t *
55 166761229 : clib_fifo_header (void *f)
56 : {
57 166761229 : return vec_header (f);
58 : }
59 :
60 : /* Aliases. */
61 : #define clib_fifo_len(v) vec_len(v)
62 : #define _clib_fifo_len(v) _vec_len(v)
63 : #define clib_fifo_end(v) vec_end(v)
64 :
65 : always_inline uword
66 163624825 : clib_fifo_elts (void *v)
67 : {
68 : word l, r;
69 163624825 : clib_fifo_header_t *f = clib_fifo_header (v);
70 :
71 163597915 : if (!v)
72 132421655 : return 0;
73 :
74 31176456 : l = _clib_fifo_len (v);
75 31176906 : r = (word) f->tail_index - (word) f->head_index;
76 31176906 : r = r < 0 ? r + l : r;
77 31176906 : ASSERT (r >= 0 && r <= l);
78 31176906 : return r;
79 : }
80 :
81 : always_inline uword
82 1691879 : clib_fifo_free_elts (void *v)
83 : {
84 1691879 : return clib_fifo_len (v) - clib_fifo_elts (v);
85 : }
86 :
87 : always_inline void
88 : clib_fifo_reset (void *v)
89 : {
90 : clib_fifo_header_t *f = clib_fifo_header (v);
91 : if (v)
92 : {
93 : f->head_index = f->tail_index = 0;
94 : vec_set_len (v, 0);
95 : }
96 : }
97 :
98 : /* External resize function. */
99 : void *_clib_fifo_resize (void *v, uword n_elts, uword align, uword elt_bytes);
100 :
101 : #define clib_fifo_resize(f, n_elts) \
102 : f = _clib_fifo_resize ((f), (n_elts), _vec_align (f, 0), _vec_elt_sz (f))
103 :
104 : always_inline void *
105 : _clib_fifo_validate (void *v, uword n_elts, uword align, uword elt_bytes)
106 : {
107 : if (clib_fifo_free_elts (v) < n_elts)
108 : v = _clib_fifo_resize (v, n_elts, align, elt_bytes);
109 : return v;
110 : }
111 :
112 : #define clib_fifo_validate(f, n_elts) \
113 : f = _clib_fifo_validate ((f), (n_elts), _vec_align (f, 0), _vec_elt_sz (f))
114 :
115 : /* Advance tail pointer by N_ELTS which can be either positive or negative. */
116 : always_inline void *
117 832945 : _clib_fifo_advance_tail (void *v, word n_elts, uword align, uword elt_bytes,
118 : uword *tail_return)
119 : {
120 : word i, l, n_free;
121 : clib_fifo_header_t *f;
122 :
123 832945 : n_free = clib_fifo_free_elts (v);
124 832793 : if (n_free < n_elts)
125 : {
126 26425 : v = _clib_fifo_resize (v, n_elts, align, elt_bytes);
127 26425 : n_free = clib_fifo_free_elts (v);
128 : }
129 :
130 832793 : ASSERT (n_free >= n_elts);
131 832793 : n_free -= n_elts;
132 :
133 832793 : f = clib_fifo_header (v);
134 832721 : l = _clib_fifo_len (v);
135 832746 : i = f->tail_index;
136 :
137 832746 : if (n_free == 0)
138 : {
139 : /* Mark fifo full. */
140 11308 : f->tail_index = f->head_index + l;
141 : }
142 : else
143 : {
144 821438 : word n = f->tail_index + n_elts;
145 821438 : if (n >= l)
146 8026 : n -= l;
147 813412 : else if (n < 0)
148 0 : n += l;
149 821438 : ASSERT (n >= 0 && n < l);
150 821440 : f->tail_index = n;
151 : }
152 :
153 832748 : ASSERT (clib_fifo_free_elts (v) == n_free);
154 :
155 832791 : if (tail_return)
156 832790 : *tail_return = n_elts > 0 ? i : f->tail_index;
157 :
158 832791 : return v;
159 : }
160 :
161 : #define clib_fifo_advance_tail(f, n_elts) \
162 : ({ \
163 : uword _i; \
164 : (f) = _clib_fifo_advance_tail ((f), (n_elts), _vec_align (f, 0), \
165 : _vec_elt_sz (f), &_i); \
166 : (f) + _i; \
167 : })
168 :
169 : always_inline uword
170 290667 : clib_fifo_advance_head (void *v, uword n_elts)
171 : {
172 : clib_fifo_header_t *f;
173 : uword l, i, n;
174 :
175 290667 : ASSERT (clib_fifo_elts (v) >= n_elts);
176 290667 : f = clib_fifo_header (v);
177 290667 : l = _clib_fifo_len (v);
178 :
179 : /* If fifo was full, restore tail pointer. */
180 290667 : if (f->tail_index == f->head_index + l)
181 683 : f->tail_index = f->head_index;
182 :
183 290667 : n = i = f->head_index;
184 290667 : n += n_elts;
185 290667 : n = n >= l ? n - l : n;
186 290667 : ASSERT (n < l);
187 290667 : f->head_index = n;
188 :
189 290667 : return i;
190 : }
191 :
192 : /* Add given element to fifo. */
193 : #define clib_fifo_add1(f, e) \
194 : do \
195 : { \
196 : uword _i; \
197 : (f) = _clib_fifo_advance_tail ((f), 1, _vec_align (f, 0), \
198 : _vec_elt_sz (f), &_i); \
199 : (f)[_i] = (e); \
200 : } \
201 : while (0)
202 :
203 : /* Add element to fifo; return pointer to new element. */
204 : #define clib_fifo_add2(f, p) \
205 : do \
206 : { \
207 : uword _i; \
208 : (f) = _clib_fifo_advance_tail ((f), 1, _vec_align (f, 0), \
209 : _vec_elt_sz (f), &_i); \
210 : (p) = (f) + _i; \
211 : } \
212 : while (0)
213 :
214 : /* Add several elements to fifo. */
215 : #define clib_fifo_add(f, e, n) \
216 : do \
217 : { \
218 : uword _i, _l; \
219 : word _n0, _n1; \
220 : \
221 : _n0 = (n); \
222 : (f) = _clib_fifo_advance_tail ((f), _n0, _vec_align (f, 0), \
223 : _vec_elt_sz (f), &_i); \
224 : _l = clib_fifo_len (f); \
225 : _n1 = _i + _n0 - _l; \
226 : _n1 = _n1 < 0 ? 0 : _n1; \
227 : _n0 -= _n1; \
228 : clib_memcpy_fast ((f) + _i, (e), _n0 * sizeof ((f)[0])); \
229 : if (_n1) \
230 : clib_memcpy_fast ((f) + 0, (e) + _n0, _n1 * sizeof ((f)[0])); \
231 : } \
232 : while (0)
233 :
234 : /* Subtract element from fifo. */
235 : #define clib_fifo_sub1(f,e) \
236 : do { \
237 : uword _i; \
238 : ASSERT (clib_fifo_elts (f) >= 1); \
239 : _i = clib_fifo_advance_head ((f), 1); \
240 : (e) = (f)[_i]; \
241 : } while (0)
242 :
243 : #define clib_fifo_sub2(f,p) \
244 : do { \
245 : uword _i; \
246 : ASSERT (clib_fifo_elts (f) >= 1); \
247 : _i = clib_fifo_advance_head ((f), 1); \
248 : (p) = (f) + _i; \
249 : } while (0)
250 :
251 : always_inline uword
252 1982161 : clib_fifo_head_index (void *v)
253 : {
254 1982161 : clib_fifo_header_t *f = clib_fifo_header (v);
255 1982161 : return v ? f->head_index : 0;
256 : }
257 :
258 : always_inline uword
259 : clib_fifo_tail_index (void *v)
260 : {
261 : clib_fifo_header_t *f = clib_fifo_header (v);
262 : return v ? f->tail_index : 0;
263 : }
264 :
265 : #define clib_fifo_head(v) ((v) + clib_fifo_head_index (v))
266 : #define clib_fifo_tail(v) ((v) + clib_fifo_tail_index (v))
267 :
268 : #define clib_fifo_free(f) vec_free ((f))
269 :
270 : always_inline uword
271 : clib_fifo_elt_index (void *v, uword i)
272 : {
273 : clib_fifo_header_t *f = clib_fifo_header (v);
274 : uword result = 0;
275 :
276 : ASSERT (i < clib_fifo_elts (v));
277 :
278 : if (v)
279 : {
280 : result = f->head_index + i;
281 : if (result >= _vec_len (v))
282 : result -= _vec_len (v);
283 : }
284 :
285 : return result;
286 : }
287 :
288 : #define clib_fifo_elt_at_index(v, i) ((v) + (i))
289 :
290 : #define clib_fifo_foreach(v,f,body) \
291 : do { \
292 : uword _i, _l, _n; \
293 : \
294 : _i = clib_fifo_head_index (f); \
295 : _l = clib_fifo_len (f); \
296 : _n = clib_fifo_elts (f); \
297 : while (_n > 0) \
298 : { \
299 : (v) = (f) + _i; \
300 : do { body; } while (0); \
301 : _n--; \
302 : _i++; \
303 : _i = _i >= _l ? 0 : _i; \
304 : } \
305 : } while (0)
306 :
307 : #endif /* included_fifo_h */
308 :
309 : /*
310 : * fd.io coding-style-patch-verification: ON
311 : *
312 : * Local Variables:
313 : * eval: (c-set-style "gnu")
314 : * End:
315 : */
|
