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   /* First index of valid data in fifo. */
  47   u32 head_index;
  48
  49   /* One beyond last index in fifo. */
  50   u32 tail_index;
  51 } clib_fifo_header_t;
  52
  53 always_inline clib_fifo_header_t *
  54 clib_fifo_header (void * f)
  55 { return vec_header (f, sizeof (clib_fifo_header_t)); }
  56
  57 /* Aliases. */
  58 #define clib_fifo_len(v) vec_len(v)
  59 #define _clib_fifo_len(v) _vec_len(v)
  60 #define clib_fifo_end(v) vec_end(v)
  61
  62 always_inline uword
  63 clib_fifo_elts (void * v)
  64 {
  65   word l, r;
  66   clib_fifo_header_t * f = clib_fifo_header (v);
  67
  68   if (! v)
  69     return 0;
  70
  71   l = _clib_fifo_len (v);
  72   r = (word) f->tail_index - (word) f->head_index;
  73   r = r < 0 ? r + l : r;
  74   ASSERT (r >= 0 && r <= l);
  75   return r;
  76 }
  77
  78 always_inline uword
  79 clib_fifo_free_elts (void * v)
  80 { return clib_fifo_len (v) - clib_fifo_elts (v); }
  81
  82 always_inline void
  83 clib_fifo_reset (void * v)
  84 {
  85   clib_fifo_header_t * f = clib_fifo_header (v);
  86   if (v)
  87     {
  88       f->head_index = f->tail_index = 0;
  89       _vec_len (v) = 0;
  90     }
  91 }
  92
  93 /* External resize function. */
  94 void * _clib_fifo_resize (void * v, uword n_elts, uword elt_bytes);
  95
  96 #define clib_fifo_resize(f,n_elts) \
  97   f = _clib_fifo_resize ((f), (n_elts), sizeof ((f)[0]))
  98
  99 always_inline void *
 100 _clib_fifo_validate (void * v, uword n_elts, uword elt_bytes)
 101 {
 102   if (clib_fifo_free_elts (v) < n_elts)
 103     v = _clib_fifo_resize (v, n_elts, elt_bytes);
 104   return v;
 105 }
 106
 107 #define clib_fifo_validate(f,n_elts) \
 108   f = _clib_fifo_validate ((f), (n_elts), sizeof (f[0]))
 109
 110 /* Advance tail pointer by N_ELTS which can be either positive or negative. */
 111 always_inline void *
 112 _clib_fifo_advance_tail (void * v, word n_elts, uword elt_bytes,
 113                          uword * tail_return)
 114 {
 115   word i, l, n_free;
 116   clib_fifo_header_t * f;
 117
 118   n_free = clib_fifo_free_elts (v);
 119   if (n_free < n_elts)
 120     {
 121       v = _clib_fifo_resize (v, n_elts, elt_bytes);
 122       n_free = clib_fifo_free_elts (v);
 123     }
 124
 125   ASSERT (n_free >= n_elts);
 126   n_free -= n_elts;
 127
 128   f = clib_fifo_header (v);
 129   l = _clib_fifo_len (v);
 130   i = f->tail_index;
 131
 132   if (n_free == 0)
 133     {
 134       /* Mark fifo full. */
 135       f->tail_index = f->head_index + l;
 136     }
 137   else
 138     {
 139       word n = f->tail_index + n_elts;
 140       if (n >= l)
 141         n -= l;
 142       else if (n < 0)
 143         n += l;
 144       ASSERT (n >= 0 && n < l);
 145       f->tail_index = n;
 146     }
 147
 148   ASSERT (clib_fifo_free_elts (v) == n_free);
 149
 150   if (tail_return)
 151     *tail_return = n_elts > 0 ? i : f->tail_index;
 152
 153   return v;
 154 }
 155
 156 #define clib_fifo_advance_tail(f,n_elts)                                \
 157 ({                                                                      \
 158   uword _i;                                                             \
 159   (f) = _clib_fifo_advance_tail ((f), (n_elts), sizeof ((f)[0]), &_i);  \
 160   (f) + _i;                                                             \
 161 })
 162
 163 always_inline uword
 164 clib_fifo_advance_head (void * v, uword n_elts)
 165 {
 166   clib_fifo_header_t * f;
 167   uword l, i, n;
 168
 169   ASSERT (clib_fifo_elts (v) >= n_elts);
 170   f = clib_fifo_header (v);
 171   l = _clib_fifo_len (v);
 172
 173   /* If fifo was full, restore tail pointer. */
 174   if (f->tail_index == f->head_index + l)
 175     f->tail_index = f->head_index;
 176
 177   n = i = f->head_index;
 178   n += n_elts;
 179   n = n >= l ? n - l : n;
 180   ASSERT (n < l);
 181   f->head_index = n;
 182
 183   return i;
 184 }
 185
 186 /* Add given element to fifo. */
 187 #define clib_fifo_add1(f,e)                                     \
 188 do {                                                            \
 189   uword _i;                                                     \
 190   (f) = _clib_fifo_advance_tail ((f), 1, sizeof ((f)[0]), &_i); \
 191   (f)[_i] = (e);                                                \
 192 } while (0)
 193
 194 /* Add element to fifo; return pointer to new element. */
 195 #define clib_fifo_add2(f,p)                                     \
 196 do {                                                            \
 197   uword _i;                                                     \
 198   (f) = _clib_fifo_advance_tail ((f), 1, sizeof ((f)[0]), &_i); \
 199   (p) = (f) + _i;                                               \
 200 } while (0)
 201
 202 /* Add several elements to fifo. */
 203 #define clib_fifo_add(f,e,n)                                            \
 204 do {                                                                    \
 205   uword _i, _l; word _n0, _n1;                                          \
 206                                                                         \
 207   _n0 = (n);                                                            \
 208   (f) = _clib_fifo_advance_tail ((f), _n0, sizeof ((f)[0]), &_i);       \
 209   _l = clib_fifo_len (f);                                               \
 210   _n1 = _i + _n0 - _l;                                                  \
 211   _n1 = _n1 < 0 ? 0 : _n1;                                              \
 212   _n0 -= _n1;                                                           \
 213   memcpy ((f) + _i, (e), _n0 * sizeof ((f)[0]));                        \
 214   if (_n1)                                                              \
 215     memcpy ((f) + 0, (e) + _n0, _n1 * sizeof ((f)[0]));                 \
 216 } while (0)
 217
 218 /* Subtract element from fifo. */
 219 #define clib_fifo_sub1(f,e)                     \
 220 do {                                            \
 221   uword _i;                                     \
 222   ASSERT (clib_fifo_elts (f) >= 1);             \
 223   _i = clib_fifo_advance_head ((f), 1);         \
 224   (e) = (f)[_i];                                \
 225 } while (0)
 226
 227 #define clib_fifo_sub2(f,p)                     \
 228 do {                                            \
 229   uword _i;                                     \
 230   ASSERT (clib_fifo_elts (f) >= 1);             \
 231   _i = clib_fifo_advance_head ((f), 1);         \
 232   (p) = (f) + _i;                               \
 233 } while (0)
 234
 235 always_inline uword
 236 clib_fifo_head_index (void * v)
 237 {
 238   clib_fifo_header_t * f = clib_fifo_header (v);
 239   return v ? f->head_index : 0;
 240 }
 241
 242 always_inline uword
 243 clib_fifo_tail_index (void * v)
 244 {
 245   clib_fifo_header_t * f = clib_fifo_header (v);
 246   return v ? f->tail_index : 0;
 247 }
 248
 249 #define clib_fifo_head(v) ((v) + clib_fifo_head_index (v))
 250 #define clib_fifo_tail(v) ((v) + clib_fifo_tail_index (v))
 251
 252 #define clib_fifo_free(f) vec_free_h((f),sizeof(clib_fifo_header_t))
 253
 254 always_inline uword
 255 clib_fifo_elt_index (void * v, uword i)
 256 {
 257   clib_fifo_header_t * f = clib_fifo_header (v);
 258   uword result = 0;
 259
 260   ASSERT (i < clib_fifo_elts (v));
 261
 262   if (v)
 263     {
 264       result = f->head_index + i;
 265       if (result >= _vec_len (v))
 266         result -= _vec_len (v);
 267     }
 268
 269   return result;
 270 }
 271
 272 #define clib_fifo_elt_at_index(v,i) ((v) + clib_fifo_elt_index (v, (i)))
 273
 274 #define clib_fifo_foreach(v,f,body)             \
 275 do {                                            \
 276   uword _i, _l, _n;                             \
 277                                                 \
 278   _i = clib_fifo_head_index (f);                \
 279   _l = clib_fifo_len (f);                       \
 280   _n = clib_fifo_elts (f);                      \
 281   while (_n > 0)                                \
 282     {                                           \
 283       (v) = (f) + _i;                           \
 284       do { body; } while (0);                   \
 285       _n--;                                     \
 286       _i++;                                     \
 287       _i = _i >= _l ? 0 : _i;                   \
 288     }                                           \
 289 } while (0)
 290
 291 #endif /* included_fifo_h */