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