src/vppinfra/fifo.h

   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 clib_fifo_header (void *f)
  56 {
  57   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 clib_fifo_elts (void *v)
  67 {
  68   word l, r;
  69   clib_fifo_header_t *f = clib_fifo_header (v);
  70
  71   if (!v)
  72     return 0;
  73
  74   l = _clib_fifo_len (v);
  75   r = (word) f->tail_index - (word) f->head_index;
  76   r = r < 0 ? r + l : r;
  77   ASSERT (r >= 0 && r <= l);
  78   return r;
  79 }
  80
  81 always_inline uword
  82 clib_fifo_free_elts (void *v)
  83 {
  84   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 _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   n_free = clib_fifo_free_elts (v);
 124   if (n_free < n_elts)
 125     {
 126       v = _clib_fifo_resize (v, n_elts, align, elt_bytes);
 127       n_free = clib_fifo_free_elts (v);
 128     }
 129
 130   ASSERT (n_free >= n_elts);
 131   n_free -= n_elts;
 132
 133   f = clib_fifo_header (v);
 134   l = _clib_fifo_len (v);
 135   i = f->tail_index;
 136
 137   if (n_free == 0)
 138     {
 139       /* Mark fifo full. */
 140       f->tail_index = f->head_index + l;
 141     }
 142   else
 143     {
 144       word n = f->tail_index + n_elts;
 145       if (n >= l)
 146         n -= l;
 147       else if (n < 0)
 148         n += l;
 149       ASSERT (n >= 0 && n < l);
 150       f->tail_index = n;
 151     }
 152
 153   ASSERT (clib_fifo_free_elts (v) == n_free);
 154
 155   if (tail_return)
 156     *tail_return = n_elts > 0 ? i : f->tail_index;
 157
 158   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 clib_fifo_advance_head (void *v, uword n_elts)
 171 {
 172   clib_fifo_header_t *f;
 173   uword l, i, n;
 174
 175   ASSERT (clib_fifo_elts (v) >= n_elts);
 176   f = clib_fifo_header (v);
 177   l = _clib_fifo_len (v);
 178
 179   /* If fifo was full, restore tail pointer. */
 180   if (f->tail_index == f->head_index + l)
 181     f->tail_index = f->head_index;
 182
 183   n = i = f->head_index;
 184   n += n_elts;
 185   n = n >= l ? n - l : n;
 186   ASSERT (n < l);
 187   f->head_index = n;
 188
 189   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 clib_fifo_head_index (void *v)
 253 {
 254   clib_fifo_header_t *f = clib_fifo_header (v);
 255   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  */