vnet/vnet/fib/fib_node_list.c

   1 /*
   2  * Copyright (c) 2016 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  * @brief a hetrogeneous w.r.t. FIB node type, of FIB nodes.
  17  * Since we cannot use C pointers, due to memeory reallocs, the next/prev
  18  * are described as key:{type,index}.
  19  */
  20
  21 #include <vnet/fib/fib_node_list.h>
  22
  23 /**
  24  * @brief An element in the list
  25  */
  26 typedef struct fib_node_list_elt_t_
  27 {
  28     /**
  29      * An opaque indentifier set by the FIB node owning this element
  30      * that will allow the owner to identify which element it is.
  31      */
  32     int fnle_owner_id;
  33
  34     /**
  35      * The index of the list this element is in
  36      */
  37     fib_node_list_t fnle_list;
  38
  39     /**
  40      * The owner of this element
  41      */
  42     fib_node_ptr_t fnle_owner;
  43
  44     /**
  45      * The next element in the list
  46      */
  47     u32 fnle_next;
  48
  49     /**
  50      * The previous element in the list
  51      */
  52     u32 fnle_prev;
  53 } fib_node_list_elt_t;
  54
  55 /**
  56  * @brief A list of FIB nodes
  57  */
  58 typedef struct fib_node_list_head_t_
  59 {
  60     /**
  61      * The head element
  62      */
  63     u32 fnlh_head;
  64
  65     /**
  66      * Number of elements in the list
  67      */
  68     u32 fnlh_n_elts;
  69 } fib_node_list_head_t;
  70
  71 /**
  72  * Pools of list elements and heads
  73  */
  74 static fib_node_list_elt_t *fib_node_list_elt_pool;
  75 static fib_node_list_head_t *fib_node_list_head_pool;
  76
  77 static index_t
  78 fib_node_list_elt_get_index (fib_node_list_elt_t *elt)
  79 {
  80     return (elt - fib_node_list_elt_pool);
  81 }
  82
  83 static fib_node_list_elt_t *
  84 fib_node_list_elt_get (index_t fi)
  85 {
  86     return (pool_elt_at_index(fib_node_list_elt_pool, fi));
  87 }
  88
  89 static index_t
  90 fib_node_list_head_get_index (fib_node_list_head_t *head)
  91 {
  92     return (head - fib_node_list_head_pool);
  93 }
  94 static fib_node_list_head_t *
  95 fib_node_list_head_get (fib_node_list_t fi)
  96 {
  97     return (pool_elt_at_index(fib_node_list_head_pool, fi));
  98 }
  99
 100 static fib_node_list_elt_t *
 101 fib_node_list_elt_create (fib_node_list_head_t *head,
 102                           int id,
 103                           fib_node_type_t type,
 104                           fib_node_index_t index)
 105 {
 106     fib_node_list_elt_t *elt;
 107
 108     pool_get(fib_node_list_elt_pool, elt);
 109
 110     elt->fnle_list = fib_node_list_head_get_index(head);
 111     elt->fnle_owner_id = id;
 112     elt->fnle_owner.fnp_type  = type;
 113     elt->fnle_owner.fnp_index = index;
 114
 115     elt->fnle_next = FIB_NODE_INDEX_INVALID;
 116     elt->fnle_prev = FIB_NODE_INDEX_INVALID;
 117
 118     return (elt);
 119 }
 120
 121 static void
 122 fib_node_list_head_init (fib_node_list_head_t *head)
 123 {
 124     head->fnlh_n_elts = 0;
 125     head->fnlh_head = FIB_NODE_INDEX_INVALID;
 126 }
 127
 128 /**
 129  * @brief Create a new node list. The expectation is that these are few in number
 130  * so straight from the memory subsystem
 131  */
 132 fib_node_list_t
 133 fib_node_list_create (void)
 134 {
 135     fib_node_list_head_t *head;
 136
 137     pool_get(fib_node_list_head_pool, head);
 138
 139     fib_node_list_head_init(head);
 140
 141     return (fib_node_list_head_get_index(head));
 142 }
 143
 144 void
 145 fib_node_list_destroy (fib_node_list_t *list)
 146 {
 147     fib_node_list_head_t *head;
 148
 149     if (FIB_NODE_INDEX_INVALID == *list)
 150         return;
 151
 152     head = fib_node_list_head_get(*list);
 153     ASSERT(0 == head->fnlh_n_elts);
 154
 155     pool_put(fib_node_list_head_pool, head);
 156     *list = FIB_NODE_INDEX_INVALID;
 157 }
 158
 159
 160 /**
 161  * @brief Insert an element at the from of the list.
 162  */
 163 u32
 164 fib_node_list_push_front (fib_node_list_t list,
 165                           int owner_id,
 166                           fib_node_type_t type,
 167                           fib_node_index_t index)
 168 {
 169     fib_node_list_elt_t *elt, *next;
 170     fib_node_list_head_t *head;
 171
 172     head = fib_node_list_head_get(list);
 173     elt = fib_node_list_elt_create(head, owner_id, type, index);
 174
 175     elt->fnle_prev = FIB_NODE_INDEX_INVALID;
 176     elt->fnle_next = head->fnlh_head;
 177
 178     if (FIB_NODE_INDEX_INVALID != head->fnlh_head)
 179     {
 180         next = fib_node_list_elt_get(head->fnlh_head);
 181         next->fnle_prev = fib_node_list_elt_get_index(elt);
 182     }
 183     head->fnlh_head = fib_node_list_elt_get_index(elt);
 184
 185     head->fnlh_n_elts++;
 186
 187     return (fib_node_list_elt_get_index(elt));
 188 }
 189
 190 u32
 191 fib_node_list_push_back (fib_node_list_t list,
 192                         int owner_id,
 193                         fib_node_type_t type,
 194                         fib_node_index_t index)
 195 {
 196     ASSERT(0);
 197     return (FIB_NODE_INDEX_INVALID);
 198 }
 199
 200 static void
 201 fib_node_list_extract (fib_node_list_head_t *head,
 202                        fib_node_list_elt_t *elt)
 203 {
 204     fib_node_list_elt_t *next, *prev;
 205
 206     if (FIB_NODE_INDEX_INVALID != elt->fnle_next)
 207     {
 208         next = fib_node_list_elt_get(elt->fnle_next);
 209         next->fnle_prev = elt->fnle_prev;
 210     }
 211
 212     if (FIB_NODE_INDEX_INVALID != elt->fnle_prev)
 213     {
 214         prev = fib_node_list_elt_get(elt->fnle_prev);
 215         prev->fnle_next = elt->fnle_next;
 216     }
 217     else
 218     {
 219         ASSERT (fib_node_list_elt_get_index(elt) == head->fnlh_head);
 220         head->fnlh_head = elt->fnle_next;
 221     }
 222 }
 223
 224 static void
 225 fib_node_list_insert_after (fib_node_list_head_t *head,
 226                             fib_node_list_elt_t *prev,
 227                             fib_node_list_elt_t *elt)
 228 {
 229     fib_node_list_elt_t *next;
 230
 231     elt->fnle_next = prev->fnle_next;
 232     if (FIB_NODE_INDEX_INVALID != prev->fnle_next)
 233     {
 234         next = fib_node_list_elt_get(prev->fnle_next);
 235         next->fnle_prev = fib_node_list_elt_get_index(elt);
 236     }
 237     prev->fnle_next = fib_node_list_elt_get_index(elt);
 238     elt->fnle_prev = fib_node_list_elt_get_index(prev);
 239 }
 240
 241 void
 242 fib_node_list_remove (fib_node_list_t list,
 243                       u32 sibling)
 244 {
 245     fib_node_list_head_t *head;
 246     fib_node_list_elt_t *elt;
 247
 248     head = fib_node_list_head_get(list);
 249     elt  = fib_node_list_elt_get(sibling);
 250
 251     fib_node_list_extract(head, elt);
 252
 253     head->fnlh_n_elts--;
 254     pool_put(fib_node_list_elt_pool, elt);
 255 }
 256
 257 void
 258 fib_node_list_elt_remove (u32 sibling)
 259 {
 260     fib_node_list_elt_t *elt;
 261
 262     elt = fib_node_list_elt_get(sibling);
 263
 264     fib_node_list_remove(elt->fnle_list, sibling);
 265 }
 266
 267 /**
 268  * @brief Advance the sibling one step (toward the tail) in the list.
 269  * return 0 if at the end of the list, 1 otherwise.
 270  */
 271 int
 272 fib_node_list_advance (u32 sibling)
 273 {
 274     fib_node_list_elt_t *elt, *next;
 275     fib_node_list_head_t *head;
 276
 277     elt = fib_node_list_elt_get(sibling);
 278     head = fib_node_list_head_get(elt->fnle_list);
 279
 280     if (FIB_NODE_INDEX_INVALID != elt->fnle_next)
 281     {
 282         /*
 283          * not at the end of the list
 284          */
 285         next = fib_node_list_elt_get(elt->fnle_next);
 286
 287         fib_node_list_extract(head, elt);
 288         fib_node_list_insert_after(head, next, elt);
 289
 290         return (1);
 291     }
 292     else
 293     {
 294         return (0);
 295     }
 296 }
 297
 298 int
 299 fib_node_list_elt_get_next (u32 sibling,
 300                             fib_node_ptr_t *ptr)
 301 {
 302     fib_node_list_elt_t *elt, *next;
 303
 304     elt = fib_node_list_elt_get(sibling);
 305
 306     if (FIB_NODE_INDEX_INVALID != elt->fnle_next)
 307     {
 308         next = fib_node_list_elt_get(elt->fnle_next);
 309
 310         *ptr = next->fnle_owner;
 311         return (1);
 312     }
 313     else
 314     {
 315         ptr->fnp_index = FIB_NODE_INDEX_INVALID;
 316         return (0);
 317     }
 318 }
 319
 320 u32
 321 fib_node_list_get_size (fib_node_list_t list)
 322 {
 323     fib_node_list_head_t *head;
 324
 325     if (FIB_NODE_INDEX_INVALID == list)
 326     {
 327         return (0);
 328     }
 329
 330     head = fib_node_list_head_get(list);
 331
 332     return (head->fnlh_n_elts);
 333 }
 334
 335 int
 336 fib_node_list_get_front (fib_node_list_t list,
 337                          fib_node_ptr_t *ptr)
 338 {
 339     fib_node_list_head_t *head;
 340     fib_node_list_elt_t *elt;
 341
 342
 343     if (0 == fib_node_list_get_size(list))
 344     {
 345         ptr->fnp_index = FIB_NODE_INDEX_INVALID;
 346         return (0);
 347     }
 348
 349     head = fib_node_list_head_get(list);
 350     elt = fib_node_list_elt_get(head->fnlh_head);
 351
 352     *ptr = elt->fnle_owner;
 353
 354     return (1);
 355 }
 356
 357 /**
 358  * @brief Walk the list of node. This must be safe w.r.t. the removal
 359  * of nodes during the walk.
 360  */
 361 void
 362 fib_node_list_walk (fib_node_list_t list,
 363                     fib_node_list_walk_cb_t fn,
 364                     void *args)
 365 {
 366     fib_node_list_elt_t *elt;
 367     fib_node_list_head_t *head;
 368     u32 sibling;
 369
 370     if (FIB_NODE_INDEX_INVALID == list)
 371     {
 372         return;
 373     }
 374
 375     head = fib_node_list_head_get(list);
 376     sibling = head->fnlh_head;
 377
 378     while (FIB_NODE_INDEX_INVALID != sibling)
 379     {
 380         elt = fib_node_list_elt_get(sibling);
 381         sibling = elt->fnle_next;
 382
 383         fn(&elt->fnle_owner, args);
 384     }
 385 }