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  * Get prev list entry index
  56  *
  57  * @param E     pool entry
  58  * @name        list anchor name
  59  * @return      previous index
  60  */
  61 #define clib_llist_prev_index(E,name) _lprev(E,name)
  62 /**
  63  * Get next list entry index
  64  *
  65  * @param E     pool entry
  66  * @name        list anchor name
  67  * @return      next index
  68  */
  69 #define clib_llist_next_index(E,name) _lnext(E,name)
  70 /**
  71  * Get next pool entry
  72  *
  73  * @param LP    linked list pool
  74  * @param name  list anchor name
  75  * @param E     pool entry
  76  * @return      next pool entry
  77  */
  78 #define clib_llist_next(LP,name,E) pool_elt_at_index((LP),_lnext((E),name))
  79 /**
  80  * Get previous pool entry
  81  *
  82  * @param LP    linked list pool
  83  * @param name  list anchor name
  84  * @param E     pool entry
  85  * @return      previous pool entry
  86  */
  87 #define clib_llist_prev(LP,name,E) pool_elt_at_index((LP),_lprev((E),name))
  88 /**
  89  * Initialize element in llist for entry
  90  *
  91  * @param LP    linked list pool
  92  * @param name  list anchor name
  93  * @param E     entry whose ll anchor is to be initialized
  94  */
  95 #define clib_llist_anchor_init(LP,name,E)                               \
  96 do {                                                                    \
  97   _lprev ((E),name) = clib_llist_entry_index ((LP), (E));               \
  98   _lnext ((E),name) = _lprev ((E),name);                                \
  99 } while (0)
 100 /**
 101  * Initialize llist head
 102  *
 103  * @param LP    linked list pool
 104  * @param name  list anchor name
 105  */
 106 #define clib_llist_make_head(LP,name)                                   \
 107 ({                                                                      \
 108   typeof (LP) _ll_var (head);                                           \
 109   pool_get_zero ((LP), _ll_var (head));                                 \
 110   clib_llist_anchor_init ((LP),name,_ll_var (head));                    \
 111   clib_llist_entry_index ((LP), _ll_var (head));                        \
 112 })
 113 /**
 114  * Check is list is empty
 115  *
 116  * @param LP    linked list pool
 117  * @param name  list anchor name
 118  * @param H     list head
 119  * @return      1 if sentinel is the only node part of the list, 0 otherwise
 120  */
 121 #define clib_llist_is_empty(LP,name,H)                                  \
 122   (clib_llist_entry_index (LP,H) == (H)->name.next)
 123 /**
 124  * Check if element is linked in a list
 125  *
 126  * @param E     list element
 127  * @param name  list anchor name
 128  */
 129 #define clib_llist_elt_is_linked(E,name)                                \
 130   ((E)->name.next != CLIB_LLIST_INVALID_INDEX                           \
 131    && (E)->name.prev != CLIB_LLIST_INVALID_INDEX)
 132 /**
 133  * Insert entry between previous and next
 134  *
 135  * Internal use.
 136  *
 137  * @param LP    linked list pool
 138  * @param name  list anchor name
 139  * @param E     new entry
 140  * @param P     previous in list
 141  * @param N     next in list
 142  */
 143 #define _llist_insert(LP,name,E,P,N)                                    \
 144 do {                                                                    \
 145   _lprev (E,name) = _lprev(N,name);                                     \
 146   _lnext (E,name) = _lnext(P,name);                                     \
 147   _lprev ((N),name) = clib_llist_entry_index ((LP),(E));                \
 148   _lnext ((P),name) = clib_llist_entry_index ((LP),(E));                \
 149 } while (0)
 150 /**
 151  * Insert entry after previous
 152  *
 153  * @param LP    linked list pool
 154  * @param name  list anchor name
 155  * @param E     new entry
 156  * @param P     previous in list
 157  */
 158 #define clib_llist_insert(LP,name,E,P)                                  \
 159 do {                                                                    \
 160   typeof (LP) _ll_var (N) = clib_llist_next (LP,name,P);                \
 161   _llist_insert ((LP),name,(E),(P), _ll_var (N));                       \
 162 } while (0)
 163
 164 /**
 165  * Add entry after head
 166  *
 167  * @param LP    linked list pool
 168  * @param name  list anchor name
 169  * @param E     new entry
 170  * @param H     list head
 171  */
 172 #define clib_llist_add(LP,name,E,H) clib_llist_insert ((LP),name,(E),(H))
 173 /**
 174  * Add entry after tail
 175  *
 176  * @param LP    linked list pool
 177  * @param name  list anchor name
 178  * @param E     new entry
 179  * @param H     list head
 180  */
 181 #define clib_llist_add_tail(LP,name,E,H)                                \
 182 do {                                                                    \
 183   typeof (LP) _ll_var (P) = clib_llist_prev ((LP),name,(H));            \
 184   _llist_insert ((LP),name,(E),_ll_var (P),(H));                        \
 185 } while (0)
 186 /**
 187  * Remove entry from list
 188  *
 189  * @param LP    linked list pool
 190  * @param name  list anchor name
 191  * @param E     entry to be removed
 192  */
 193 #define clib_llist_remove(LP,name,E)                                    \
 194 do {                                                                    \
 195   ASSERT ((E) != clib_llist_next (LP,name,E));/* don't remove sentinel */\
 196   ASSERT (_lnext (E,name) != CLIB_LLIST_INVALID_INDEX);                 \
 197   ASSERT (_lprev (E,name) != CLIB_LLIST_INVALID_INDEX);                 \
 198   typeof (LP) _ll_var (P) = clib_llist_prev ((LP),name,E);              \
 199   typeof (LP) _ll_var (N) = clib_llist_next ((LP),name,E);              \
 200   _lnext (_ll_var (P),name) = _lnext (E,name);                          \
 201   _lprev (_ll_var (N),name) = _lprev (E,name);                          \
 202   _lnext (E,name) = _lprev (E,name) = CLIB_LLIST_INVALID_INDEX;         \
 203 }while (0)
 204 /**
 205  * Removes and returns the first element in the list.
 206  *
 207  * The element is not freed. It's the responsability of the caller to
 208  * free it.
 209  *
 210  * @param LP    linked list pool
 211  * @param name  list anchor name
 212  * @param E     storage the first entry
 213  * @param H     list head entry
 214  */
 215 #define clib_llist_pop_first(LP,name,E,H)                               \
 216 do {                                                                    \
 217   E = clib_llist_next (LP,name,H);                                      \
 218   clib_llist_remove (LP,name,E);                                        \
 219 } while (0)
 220 /**
 221  * Splice two lists at a given position
 222  *
 223  * List spliced into destination list is left with 0 entries, i.e., head
 224  * is made to point to itself.
 225  *
 226  * @param LP    linked list pool
 227  * @param name  list anchor name
 228  * @param P     position in destination where source list is spliced
 229  * @param H     head of source list that will be spliced into destination
 230  */
 231 #define clib_llist_splice(LP,name,P,H)                                  \
 232 do {                                                                    \
 233   typeof (LP) _ll_var (fe) = clib_llist_next (LP,name,H);               \
 234   if (_ll_var (fe) != (H))                                              \
 235     {                                                                   \
 236       typeof (LP) _ll_var (le) = clib_llist_prev (LP,name,H);           \
 237       typeof (LP) _ll_var (ne) = clib_llist_next (LP,name,P);           \
 238       _lprev (_ll_var (fe),name) = clib_llist_entry_index(LP,P);        \
 239       _lnext (_ll_var (le),name) = clib_llist_entry_index(LP,_ll_var (ne));\
 240       _lnext (P,name) = clib_llist_entry_index (LP,_ll_var (fe));       \
 241       _lprev (_ll_var (ne),name) = clib_llist_entry_index(LP,_ll_var (le));\
 242       _lnext (H,name) = clib_llist_entry_index(LP,H);                   \
 243       _lprev (H,name) = _lnext (H,name);                                \
 244     }                                                                   \
 245 } while (0)
 246 /**
 247  * Walk list starting at head
 248  *
 249  * @param LP    linked list pool
 250  * @param name  list anchor name
 251  * @param H     head entry
 252  * @param E     entry iterator
 253  * @param body  code to be executed
 254  */
 255 #define clib_llist_foreach(LP,name,H,E,body)                            \
 256 do {                                                                    \
 257   typeof (LP) _ll_var (n);                                              \
 258   (E) = clib_llist_next (LP,name,H);                                    \
 259   while (E != H)                                                        \
 260     {                                                                   \
 261       _ll_var (n) = clib_llist_next (LP,name,E);                        \
 262       do { body; } while (0);                                           \
 263       (E) = _ll_var (n);                                                \
 264     }                                                                   \
 265 } while (0)
 266 /**
 267  * Walk list starting at head safe
 268  *
 269  * @param LP    linked list pool
 270  * @param name  list anchor name
 271  * @param HI    head index
 272  * @param EI    entry index iterator
 273  * @param body  code to be executed
 274  */
 275 #define clib_llist_foreach_safe(LP,name,H,E,body)                       \
 276 do {                                                                    \
 277   clib_llist_index_t _ll_var (HI) = clib_llist_entry_index (LP, H);     \
 278   clib_llist_index_t _ll_var (EI), _ll_var (NI);                        \
 279   _ll_var (EI) = _lnext ((H),name);                                     \
 280   while (_ll_var (EI) != _ll_var (HI))                                  \
 281     {                                                                   \
 282       (E) = pool_elt_at_index (LP, _ll_var (EI));                       \
 283       _ll_var (NI) = _lnext ((E),name);                                 \
 284       do { body; } while (0);                                           \
 285       _ll_var (EI) = _ll_var (NI);                                      \
 286     }                                                                   \
 287 } while (0)
 288 /**
 289  * Walk list starting at head in reverse order
 290  *
 291  * @param LP    linked list pool
 292  * @param name  list anchor name
 293  * @param H     head entry
 294  * @param E     entry iterator
 295  * @param body  code to be executed
 296  */
 297 #define clib_llist_foreach_reverse(LP,name,H,E,body)                    \
 298 do {                                                                    \
 299   typeof (LP) _ll_var (p);                                              \
 300   (E) = clib_llist_prev (LP,name,H);                                    \
 301   while (E != H)                                                        \
 302     {                                                                   \
 303       _ll_var (p) = clib_llist_prev (LP,name,E);                        \
 304       do { body; } while (0);                                           \
 305       (E) = _ll_var (p);                                                \
 306     }                                                                   \
 307 } while (0)
 308
 309 #endif /* SRC_VPPINFRA_CLIB_LLIST_H_ */
 310
 311 /*
 312  * fd.io coding-style-patch-verification: ON
 313  *
 314  * Local Variables:
 315  * eval: (c-set-style "gnu")
 316  * End:
 317  */