vppinfra/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, sizeof (clib_fifo_header_t));
  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_len (v) = 0;
  95     }
  96 }
  97
  98 /* External resize function. */
  99 void *_clib_fifo_resize (void *v, uword n_elts, uword elt_bytes);
 100
 101 #define clib_fifo_resize(f,n_elts) \
 102   f = _clib_fifo_resize ((f), (n_elts), sizeof ((f)[0]))
 103
 104 always_inline void *
 105 _clib_fifo_validate (void *v, uword n_elts, uword elt_bytes)
 106 {
 107   if (clib_fifo_free_elts (v) < n_elts)
 108     v = _clib_fifo_resize (v, n_elts, elt_bytes);
 109   return v;
 110 }
 111
 112 #define clib_fifo_validate(f,n_elts) \
 113   f = _clib_fifo_validate ((f), (n_elts), sizeof (f[0]))
 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 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, 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), sizeof ((f)[0]), &_i);  \
 165   (f) + _i;                                                             \
 166 })
 167
 168 always_inline uword
 169 clib_fifo_advance_head (void *v, uword n_elts)
 170 {
 171   clib_fifo_header_t *f;
 172   uword l, i, n;
 173
 174   ASSERT (clib_fifo_elts (v) >= n_elts);
 175   f = clib_fifo_header (v);
 176   l = _clib_fifo_len (v);
 177
 178   /* If fifo was full, restore tail pointer. */
 179   if (f->tail_index == f->head_index + l)
 180     f->tail_index = f->head_index;
 181
 182   n = i = f->head_index;
 183   n += n_elts;
 184   n = n >= l ? n - l : n;
 185   ASSERT (n < l);
 186   f->head_index = n;
 187
 188   return i;
 189 }
 190
 191 /* Add given element to fifo. */
 192 #define clib_fifo_add1(f,e)                                     \
 193 do {                                                            \
 194   uword _i;                                                     \
 195   (f) = _clib_fifo_advance_tail ((f), 1, sizeof ((f)[0]), &_i); \
 196   (f)[_i] = (e);                                                \
 197 } while (0)
 198
 199 /* Add element to fifo; return pointer to new element. */
 200 #define clib_fifo_add2(f,p)                                     \
 201 do {                                                            \
 202   uword _i;                                                     \
 203   (f) = _clib_fifo_advance_tail ((f), 1, sizeof ((f)[0]), &_i); \
 204   (p) = (f) + _i;                                               \
 205 } while (0)
 206
 207 /* Add several elements to fifo. */
 208 #define clib_fifo_add(f,e,n)                                            \
 209 do {                                                                    \
 210   uword _i, _l; word _n0, _n1;                                          \
 211                                                                         \
 212   _n0 = (n);                                                            \
 213   (f) = _clib_fifo_advance_tail ((f), _n0, sizeof ((f)[0]), &_i);       \
 214   _l = clib_fifo_len (f);                                               \
 215   _n1 = _i + _n0 - _l;                                                  \
 216   _n1 = _n1 < 0 ? 0 : _n1;                                              \
 217   _n0 -= _n1;                                                           \
 218   clib_memcpy ((f) + _i, (e), _n0 * sizeof ((f)[0]));                   \
 219   if (_n1)                                                              \
 220     clib_memcpy ((f) + 0, (e) + _n0, _n1 * sizeof ((f)[0]));            \
 221 } while (0)
 222
 223 /* Subtract element from fifo. */
 224 #define clib_fifo_sub1(f,e)                     \
 225 do {                                            \
 226   uword _i;                                     \
 227   ASSERT (clib_fifo_elts (f) >= 1);             \
 228   _i = clib_fifo_advance_head ((f), 1);         \
 229   (e) = (f)[_i];                                \
 230 } while (0)
 231
 232 #define clib_fifo_sub2(f,p)                     \
 233 do {                                            \
 234   uword _i;                                     \
 235   ASSERT (clib_fifo_elts (f) >= 1);             \
 236   _i = clib_fifo_advance_head ((f), 1);         \
 237   (p) = (f) + _i;                               \
 238 } while (0)
 239
 240 always_inline uword
 241 clib_fifo_head_index (void *v)
 242 {
 243   clib_fifo_header_t *f = clib_fifo_header (v);
 244   return v ? f->head_index : 0;
 245 }
 246
 247 always_inline uword
 248 clib_fifo_tail_index (void *v)
 249 {
 250   clib_fifo_header_t *f = clib_fifo_header (v);
 251   return v ? f->tail_index : 0;
 252 }
 253
 254 #define clib_fifo_head(v) ((v) + clib_fifo_head_index (v))
 255 #define clib_fifo_tail(v) ((v) + clib_fifo_tail_index (v))
 256
 257 #define clib_fifo_free(f) vec_free_h((f),sizeof(clib_fifo_header_t))
 258
 259 always_inline uword
 260 clib_fifo_elt_index (void *v, uword i)
 261 {
 262   clib_fifo_header_t *f = clib_fifo_header (v);
 263   uword result = 0;
 264
 265   ASSERT (i < clib_fifo_elts (v));
 266
 267   if (v)
 268     {
 269       result = f->head_index + i;
 270       if (result >= _vec_len (v))
 271         result -= _vec_len (v);
 272     }
 273
 274   return result;
 275 }
 276
 277 #define clib_fifo_elt_at_index(v,i) ((v) + clib_fifo_elt_index (v, (i)))
 278
 279 #define clib_fifo_foreach(v,f,body)             \
 280 do {                                            \
 281   uword _i, _l, _n;                             \
 282                                                 \
 283   _i = clib_fifo_head_index (f);                \
 284   _l = clib_fifo_len (f);                       \
 285   _n = clib_fifo_elts (f);                      \
 286   while (_n > 0)                                \
 287     {                                           \
 288       (v) = (f) + _i;                           \
 289       do { body; } while (0);                   \
 290       _n--;                                     \
 291       _i++;                                     \
 292       _i = _i >= _l ? 0 : _i;                   \
 293     }                                           \
 294 } while (0)
 295
 296 #endif /* included_fifo_h */
 297
 298 /*
 299  * fd.io coding-style-patch-verification: ON
 300  *
 301  * Local Variables:
 302  * eval: (c-set-style "gnu")
 303  * End:
 304  */