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) ((H) == clib_llist_next((LP),name,(H)))
 106 /**
 107  * Insert entry between previous and next
 108  *
 109  * Internal use.
 110  *
 111  * @param LP    linked list pool
 112  * @param name  list anchor name
 113  * @param E     new entry
 114  * @param P     previous in list
 115  * @param N     next in list
 116  */
 117 #define _llist_insert(LP,name,E,P,N)                                    \
 118 do {                                                                    \
 119   _lprev (E,name) = _lprev(N,name);                                     \
 120   _lnext (E,name) = _lnext(P,name);                                     \
 121   _lprev ((N),name) = clib_llist_entry_index ((LP),(E));                \
 122   _lnext ((P),name) = clib_llist_entry_index ((LP),(E));                \
 123 } while (0)
 124 /**
 125  * Insert entry after previous
 126  *
 127  * @param LP    linked list pool
 128  * @param name  list anchor name
 129  * @param E     new entry
 130  * @param P     previous in list
 131  */
 132 #define clib_llist_insert(LP,name,E,P)                                  \
 133 do {                                                                    \
 134   typeof (LP) _ll_var (N) = clib_llist_next (LP,name,P);                \
 135   _llist_insert ((LP),name,(E),(P), _ll_var (N));                       \
 136 } while (0)
 137
 138 /**
 139  * Add entry after head
 140  *
 141  * @param LP    linked list pool
 142  * @param name  list anchor name
 143  * @param E     new entry
 144  * @param H     list head
 145  */
 146 #define clib_llist_add(LP,name,E,H) clib_llist_insert ((LP),name,(E),(H))
 147 /**
 148  * Add entry after tail
 149  *
 150  * @param LP    linked list pool
 151  * @param name  list anchor name
 152  * @param E     new entry
 153  * @param H     list head
 154  */
 155 #define clib_llist_add_tail(LP,name,E,H)                                \
 156 do {                                                                    \
 157   typeof (LP) _ll_var (P) = clib_llist_prev ((LP),name,(H));            \
 158   _llist_insert ((LP),name,(E),_ll_var (P),(H));                        \
 159 } while (0)
 160 /**
 161  * Remove entry from list
 162  *
 163  * @param LP    linked list pool
 164  * @param name  list anchor name
 165  * @param E     entry to be removed
 166  */
 167 #define clib_llist_remove(LP,name,E)                                    \
 168 do {                                                                    \
 169   ASSERT ((E) != clib_llist_next (LP,name,E));/* don't remove sentinel */\
 170   ASSERT (_lnext (E,name) != CLIB_LLIST_INVALID_INDEX);                 \
 171   ASSERT (_lprev (E,name) != CLIB_LLIST_INVALID_INDEX);                 \
 172   typeof (LP) _ll_var (P) = clib_llist_prev ((LP),name,E);              \
 173   typeof (LP) _ll_var (N) = clib_llist_next ((LP),name,E);              \
 174   _lnext (_ll_var (P),name) = _lnext (E,name);                          \
 175   _lprev (_ll_var (N),name) = _lprev (E,name);                          \
 176   _lnext (E,name) = _lprev (E,name) = CLIB_LLIST_INVALID_INDEX;         \
 177 }while (0)
 178
 179 /**
 180  * Splice two lists at a given position
 181  *
 182  * List spliced into destination list is left with 0 entries, i.e., head
 183  * is made to point to itself.
 184  *
 185  * @param LP    linked list pool
 186  * @param name  list anchor name
 187  * @param P     position in destination where source list is spliced
 188  * @param H     head of source list that will be spliced into destination
 189  */
 190 #define clib_llist_splice(LP,name,P,H)                                  \
 191 do {                                                                    \
 192   typeof (LP) _ll_var (fe) = clib_llist_next (LP,name,H);               \
 193   if (_ll_var (fe) != (H))                                              \
 194     {                                                                   \
 195       typeof (LP) _ll_var (le) = clib_llist_prev (LP,name,H);           \
 196       typeof (LP) _ll_var (ne) = clib_llist_next (LP,name,P);           \
 197       _lprev (_ll_var (fe),name) = clib_llist_entry_index(LP,P);        \
 198       _lnext (_ll_var (le),name) = clib_llist_entry_index(LP,_ll_var (ne));\
 199       _lnext (P,name) = clib_llist_entry_index (LP,_ll_var (fe));       \
 200       _lprev (_ll_var (ne),name) = clib_llist_entry_index(LP,_ll_var (le));\
 201       _lnext (H,name) = clib_llist_entry_index(LP,H);                   \
 202       _lprev (H,name) = _lnext (H,name);                                \
 203     }                                                                   \
 204 } while (0)
 205 /**
 206  * Walk list starting at head
 207  *
 208  * @param LP    linked list pool
 209  * @param name  list anchor name
 210  * @param H     head entry
 211  * @param E     entry iterator
 212  * @param body  code to be executed
 213  */
 214 #define clib_llist_foreach(LP,name,H,E,body)                            \
 215 do {                                                                    \
 216   typeof (LP) _ll_var (n);                                              \
 217   (E) = clib_llist_next (LP,name,H);                                    \
 218   while (E != H)                                                        \
 219     {                                                                   \
 220       _ll_var (n) = clib_llist_next (LP,name,E);                        \
 221       do { body; } while (0);                                           \
 222       (E) = _ll_var (n);                                                \
 223     }                                                                   \
 224 } while (0)
 225 /**
 226  * Walk list starting at head in reverse order
 227  *
 228  * @param LP    linked list pool
 229  * @param name  list anchor name
 230  * @param H     head entry
 231  * @param E     entry iterator
 232  * @param body  code to be executed
 233  */
 234 #define clib_llist_foreach_reverse(LP,name,H,E,body)                    \
 235 do {                                                                    \
 236   typeof (LP) _ll_var (p);                                              \
 237   (E) = clib_llist_prev (LP,name,H);                                    \
 238   while (E != H)                                                        \
 239     {                                                                   \
 240       _ll_var (p) = clib_llist_prev (LP,name,E);                        \
 241       do { body; } while (0);                                           \
 242       (E) = _ll_var (p);                                                \
 243     }                                                                   \
 244 } while (0)
 245
 246 #endif /* SRC_VPPINFRA_CLIB_LLIST_H_ */
 247
 248 /*
 249  * fd.io coding-style-patch-verification: ON
 250  *
 251  * Local Variables:
 252  * eval: (c-set-style "gnu")
 253  * End:
 254  */