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