src/vppinfra/llist.h

   1 /*
   2  * Copyright (c) 2019 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  * @file
  16  * @brief Circular doubly linked list with head sentinel.
  17  * List entries are allocated out of a "supporting" pool and all pool entries
  18  * must contain a list anchor struct for each list they pertain to.
  19  */
  20
  21 #ifndef SRC_VPPINFRA_CLIB_LLIST_H_
  22 #define SRC_VPPINFRA_CLIB_LLIST_H_
  23
  24 #include <vppinfra/types.h>
  25 #include <vppinfra/pool.h>
  26
  27 typedef u32 clib_llist_index_t;
  28
  29 typedef struct clib_llist_anchor
  30 {
  31   clib_llist_index_t prev;
  32   clib_llist_index_t next;
  33 } clib_llist_anchor_t;
  34
  35 #define CLIB_LLIST_INVALID_INDEX ((u32)~0)
  36
  37 /**
  38  * Local variable naming macro.
  39  */
  40 #define _ll_var(v) _llist_##v
  41 /**
  42  * Local macros to grab llist anchor next and prev from pool entry
  43  */
  44 #define _lnext(E,name) ((E)->name).next
  45 #define _lprev(E,name) ((E)->name).prev
  46 /**
  47  * Get list entry index
  48  *
  49  * @param LP    linked list pool
  50  * @param E     pool entry
  51  * @return      pool entry index
  52  */
  53 #define clib_llist_entry_index(LP,E) ((E) - (LP))
  54 /**
  55  * Alloc new element
  56  *
  57  * @param LP    linked list pool
  58  * @param E     element to be returned
  59  */
  60 #define clib_llist_get(LP, E) pool_get (LP, E)
  61 /**
  62  * Free element
  63  *
  64  * @param LP    linked list pool
  65  * @param E     element to be freed
  66  */
  67 #define clib_llist_put(LP, E) pool_put (LP, E)
  68 /**
  69  * Free list supporting container
  70  *
  71  * @param LP    linked list pool
  72  */
  73 #define clib_llist_free(LP) pool_free (LP)
  74 /**
  75  * Get list elt at index
  76  *
  77  * @param LP    linked list pool
  78  * @param EI    element index
  79  * @return      element
  80  */
  81 #define clib_llist_elt(LP, EI) pool_elt_at_index (LP, EI)
  82 /**
  83  * Get number of elements in supporting container
  84  *
  85  * This is NOT the elements linked in the list but the number of
  86  * elements consumed out of the supporting pool
  87  *
  88  * @param LP    linked list pool
  89  * @return      number of elements
  90  */
  91 #define clib_llist_elts(LP) pool_elts (LP)
  92 /**
  93  * Get prev list entry index
  94  *
  95  * @param E     pool entry
  96  * @name        list anchor name
  97  * @return      previous index
  98  */
  99 #define clib_llist_prev_index(E,name) _lprev(E,name)
 100 /**
 101  * Get next list entry index
 102  *
 103  * @param E     pool entry
 104  * @name        list anchor name
 105  * @return      next index
 106  */
 107 #define clib_llist_next_index(E,name) _lnext(E,name)
 108 /**
 109  * Get next pool entry
 110  *
 111  * @param LP    linked list pool
 112  * @param name  list anchor name
 113  * @param E     pool entry
 114  * @return      next pool entry
 115  */
 116 #define clib_llist_next(LP,name,E) pool_elt_at_index((LP),_lnext((E),name))
 117 /**
 118  * Get previous pool entry
 119  *
 120  * @param LP    linked list pool
 121  * @param name  list anchor name
 122  * @param E     pool entry
 123  * @return      previous pool entry
 124  */
 125 #define clib_llist_prev(LP,name,E) pool_elt_at_index((LP),_lprev((E),name))
 126 /**
 127  * Initialize element in llist for entry
 128  *
 129  * @param LP    linked list pool
 130  * @param name  list anchor name
 131  * @param E     entry whose ll anchor is to be initialized
 132  */
 133 #define clib_llist_anchor_init(LP,name,E)                               \
 134 do {                                                                    \
 135   _lprev ((E),name) = clib_llist_entry_index ((LP), (E));               \
 136   _lnext ((E),name) = _lprev ((E),name);                                \
 137 } while (0)
 138 /**
 139  * Initialize llist head
 140  *
 141  * @param LP    linked list pool
 142  * @param name  list anchor name
 143  */
 144 #define clib_llist_make_head(LP,name)                                   \
 145 ({                                                                      \
 146   typeof (LP) _ll_var (head);                                           \
 147   pool_get_zero ((LP), _ll_var (head));                                 \
 148   clib_llist_anchor_init ((LP),name,_ll_var (head));                    \
 149   clib_llist_entry_index ((LP), _ll_var (head));                        \
 150 })
 151 /**
 152  * Check is list is empty
 153  *
 154  * @param LP    linked list pool
 155  * @param name  list anchor name
 156  * @param H     list head
 157  * @return      1 if sentinel is the only node part of the list, 0 otherwise
 158  */
 159 #define clib_llist_is_empty(LP,name,H)                                  \
 160   (clib_llist_entry_index (LP,H) == (H)->name.next)
 161 /**
 162  * Check if element is linked in a list
 163  *
 164  * @param E     list element
 165  * @param name  list anchor name
 166  */
 167 #define clib_llist_elt_is_linked(E,name)                                \
 168   ((E)->name.next != CLIB_LLIST_INVALID_INDEX                           \
 169    && (E)->name.prev != CLIB_LLIST_INVALID_INDEX)
 170 /**
 171  * Insert entry between previous and next
 172  *
 173  * Internal use.
 174  *
 175  * @param LP    linked list pool
 176  * @param name  list anchor name
 177  * @param E     new entry
 178  * @param P     previous in list
 179  * @param N     next in list
 180  */
 181 #define _llist_insert(LP,name,E,P,N)                                    \
 182 do {                                                                    \
 183   _lprev (E,name) = _lprev(N,name);                                     \
 184   _lnext (E,name) = _lnext(P,name);                                     \
 185   _lprev ((N),name) = clib_llist_entry_index ((LP),(E));                \
 186   _lnext ((P),name) = clib_llist_entry_index ((LP),(E));                \
 187 } while (0)
 188 /**
 189  * Insert entry after previous
 190  *
 191  * @param LP    linked list pool
 192  * @param name  list anchor name
 193  * @param E     new entry
 194  * @param P     previous in list
 195  */
 196 #define clib_llist_insert(LP,name,E,P)                                  \
 197 do {                                                                    \
 198   typeof (LP) _ll_var (N) = clib_llist_next (LP,name,P);                \
 199   _llist_insert ((LP),name,(E),(P), _ll_var (N));                       \
 200 } while (0)
 201
 202 /**
 203  * Add entry after head
 204  *
 205  * @param LP    linked list pool
 206  * @param name  list anchor name
 207  * @param E     new entry
 208  * @param H     list head
 209  */
 210 #define clib_llist_add(LP,name,E,H) clib_llist_insert ((LP),name,(E),(H))
 211 /**
 212  * Add entry after tail
 213  *
 214  * @param LP    linked list pool
 215  * @param name  list anchor name
 216  * @param E     new entry
 217  * @param H     list head
 218  */
 219 #define clib_llist_add_tail(LP,name,E,H)                                \
 220 do {                                                                    \
 221   typeof (LP) _ll_var (P) = clib_llist_prev ((LP),name,(H));            \
 222   _llist_insert ((LP),name,(E),_ll_var (P),(H));                        \
 223 } while (0)
 224 /**
 225  * Remove entry from list
 226  *
 227  * @param LP    linked list pool
 228  * @param name  list anchor name
 229  * @param E     entry to be removed
 230  */
 231 #define clib_llist_remove(LP,name,E)                                    \
 232 do {                                                                    \
 233   ASSERT ((E) != clib_llist_next (LP,name,E));/* don't remove sentinel */\
 234   ASSERT (_lnext (E,name) != CLIB_LLIST_INVALID_INDEX);                 \
 235   ASSERT (_lprev (E,name) != CLIB_LLIST_INVALID_INDEX);                 \
 236   typeof (LP) _ll_var (P) = clib_llist_prev ((LP),name,E);              \
 237   typeof (LP) _ll_var (N) = clib_llist_next ((LP),name,E);              \
 238   _lnext (_ll_var (P),name) = _lnext (E,name);                          \
 239   _lprev (_ll_var (N),name) = _lprev (E,name);                          \
 240   _lnext (E,name) = _lprev (E,name) = CLIB_LLIST_INVALID_INDEX;         \
 241 }while (0)
 242 /**
 243  * Removes and returns the first element in the list.
 244  *
 245  * The element is not freed. It's the responsability of the caller to
 246  * free it.
 247  *
 248  * @param LP    linked list pool
 249  * @param name  list anchor name
 250  * @param E     storage the first entry
 251  * @param H     list head entry
 252  */
 253 #define clib_llist_pop_first(LP,name,E,H)                               \
 254 do {                                                                    \
 255   E = clib_llist_next (LP,name,H);                                      \
 256   clib_llist_remove (LP,name,E);                                        \
 257 } while (0)
 258 /**
 259  * Splice two lists at a given position
 260  *
 261  * List spliced into destination list is left with 0 entries, i.e., head
 262  * is made to point to itself.
 263  *
 264  * @param LP    linked list pool
 265  * @param name  list anchor name
 266  * @param P     position in destination where source list is spliced
 267  * @param H     head of source list that will be spliced into destination
 268  */
 269 #define clib_llist_splice(LP,name,P,H)                                  \
 270 do {                                                                    \
 271   typeof (LP) _ll_var (fe) = clib_llist_next (LP,name,H);               \
 272   if (_ll_var (fe) != (H))                                              \
 273     {                                                                   \
 274       typeof (LP) _ll_var (le) = clib_llist_prev (LP,name,H);           \
 275       typeof (LP) _ll_var (ne) = clib_llist_next (LP,name,P);           \
 276       _lprev (_ll_var (fe),name) = clib_llist_entry_index(LP,P);        \
 277       _lnext (_ll_var (le),name) = clib_llist_entry_index(LP,_ll_var (ne));\
 278       _lnext (P,name) = clib_llist_entry_index (LP,_ll_var (fe));       \
 279       _lprev (_ll_var (ne),name) = clib_llist_entry_index(LP,_ll_var (le));\
 280       _lnext (H,name) = clib_llist_entry_index(LP,H);                   \
 281       _lprev (H,name) = _lnext (H,name);                                \
 282     }                                                                   \
 283 } while (0)
 284 /**
 285  * Walk list starting at head
 286  *
 287  * @param LP    linked list pool
 288  * @param name  list anchor name
 289  * @param H     head entry
 290  * @param E     entry iterator
 291  * @param body  code to be executed
 292  */
 293 #define clib_llist_foreach(LP,name,H,E,body)                            \
 294 do {                                                                    \
 295   typeof (LP) _ll_var (n);                                              \
 296   (E) = clib_llist_next (LP,name,H);                                    \
 297   while (E != H)                                                        \
 298     {                                                                   \
 299       _ll_var (n) = clib_llist_next (LP,name,E);                        \
 300       do { body; } while (0);                                           \
 301       (E) = _ll_var (n);                                                \
 302     }                                                                   \
 303 } while (0)
 304 /**
 305  * Walk list starting at head safe
 306  *
 307  * @param LP    linked list pool
 308  * @param name  list anchor name
 309  * @param HI    head index
 310  * @param EI    entry index iterator
 311  * @param body  code to be executed
 312  */
 313 #define clib_llist_foreach_safe(LP,name,H,E,body)                       \
 314 do {                                                                    \
 315   clib_llist_index_t _ll_var (HI) = clib_llist_entry_index (LP, H);     \
 316   clib_llist_index_t _ll_var (EI), _ll_var (NI);                        \
 317   _ll_var (EI) = _lnext ((H),name);                                     \
 318   while (_ll_var (EI) != _ll_var (HI))                                  \
 319     {                                                                   \
 320       (E) = pool_elt_at_index (LP, _ll_var (EI));                       \
 321       _ll_var (NI) = _lnext ((E),name);                                 \
 322       do { body; } while (0);                                           \
 323       _ll_var (EI) = _ll_var (NI);                                      \
 324     }                                                                   \
 325 } while (0)
 326 /**
 327  * Walk list starting at head in reverse order
 328  *
 329  * @param LP    linked list pool
 330  * @param name  list anchor name
 331  * @param H     head entry
 332  * @param E     entry iterator
 333  * @param body  code to be executed
 334  */
 335 #define clib_llist_foreach_reverse(LP,name,H,E,body)                    \
 336 do {                                                                    \
 337   typeof (LP) _ll_var (p);                                              \
 338   (E) = clib_llist_prev (LP,name,H);                                    \
 339   while (E != H)                                                        \
 340     {                                                                   \
 341       _ll_var (p) = clib_llist_prev (LP,name,E);                        \
 342       do { body; } while (0);                                           \
 343       (E) = _ll_var (p);                                                \
 344     }                                                                   \
 345 } while (0)
 346
 347 #endif /* SRC_VPPINFRA_CLIB_LLIST_H_ */
 348
 349 /*
 350  * fd.io coding-style-patch-verification: ON
 351  *
 352  * Local Variables:
 353  * eval: (c-set-style "gnu")
 354  * End:
 355  */