vppinfra/vppinfra/fheap.h

   1 /*
   2  * Copyright (c) 2015 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 #ifndef included_clib_fheap_h
  16 #define included_clib_fheap_h
  17
  18 /* Fibonacci Heaps Fredman, M. L.; Tarjan (1987).
  19    "Fibonacci heaps and their uses in improved network optimization algorithms" */
  20
  21 #include <vppinfra/vec.h>
  22
  23 typedef struct {
  24   /* Node index of parent. */
  25   u32 parent;
  26
  27   /* Node index of first child. */
  28   u32 first_child;
  29
  30   /* Next and previous nodes in doubly linked list of siblings. */
  31   u32 next_sibling, prev_sibling;
  32
  33   /* Key (distance) for this node.  Parent always has key
  34      <= than keys of children. */
  35   u32 key;
  36
  37   /* Number of children (as opposed to descendents). */
  38   u32 rank;
  39
  40   u32 is_marked;
  41
  42   /* Set to one when node is inserted; zero when deleted. */
  43   u32 is_valid;
  44 } fheap_node_t;
  45
  46 #define foreach_fheap_node_sibling(f,ni,first_ni,body)                  \
  47 do {                                                                    \
  48   u32 __fheap_foreach_first_ni = (first_ni);                            \
  49   u32 __fheap_foreach_ni = __fheap_foreach_first_ni;                    \
  50   u32 __fheap_foreach_next_ni;                                          \
  51   fheap_node_t * __fheap_foreach_n;                                     \
  52   if (__fheap_foreach_ni != ~0)                                         \
  53     while (1)                                                           \
  54       {                                                                 \
  55         __fheap_foreach_n = fheap_get_node ((f), __fheap_foreach_ni);   \
  56         __fheap_foreach_next_ni = __fheap_foreach_n -> next_sibling;    \
  57         (ni) = __fheap_foreach_ni;                                      \
  58                                                                         \
  59         body;                                                           \
  60                                                                         \
  61         /* End of circular list? */                                     \
  62         if (__fheap_foreach_next_ni == __fheap_foreach_first_ni)        \
  63           break;                                                        \
  64                                                                         \
  65         __fheap_foreach_ni = __fheap_foreach_next_ni;                   \
  66                                                                         \
  67       }                                                                 \
  68 } while (0)
  69
  70 typedef struct {
  71   u32 min_root;
  72
  73   /* Vector of nodes. */
  74   fheap_node_t * nodes;
  75
  76   u32 * root_list_by_rank;
  77
  78   u32 enable_validate;
  79
  80   u32 validate_serial;
  81 } fheap_t;
  82
  83 /* Initialize empty heap. */
  84 always_inline void
  85 fheap_init (fheap_t * f, u32 n_nodes)
  86 {
  87   fheap_node_t * save_nodes = f->nodes;
  88   u32 * save_root_list = f->root_list_by_rank;
  89
  90   memset (f, 0, sizeof (f[0]));
  91
  92   f->nodes = save_nodes;
  93   f->root_list_by_rank = save_root_list;
  94
  95   vec_validate (f->nodes, n_nodes - 1);
  96   vec_reset_length (f->root_list_by_rank);
  97
  98   f->min_root = ~0;
  99 }
 100
 101 always_inline void
 102 fheap_free (fheap_t * f)
 103 {
 104   vec_free (f->nodes);
 105   vec_free (f->root_list_by_rank);
 106 }
 107
 108 always_inline u32
 109 fheap_find_min (fheap_t * f)
 110 { return f->min_root; }
 111
 112 always_inline u32
 113 fheap_is_empty (fheap_t * f)
 114 { return f->min_root == ~0; }
 115
 116 /* Add/delete nodes. */
 117 void fheap_add (fheap_t * f, u32 ni, u32 key);
 118 void fheap_del (fheap_t * f, u32 ni);
 119
 120 /* Delete and return minimum. */
 121 u32 fheap_del_min (fheap_t * f, u32 * min_key);
 122
 123 /* Change key value. */
 124 void fheap_decrease_key (fheap_t * f, u32 ni, u32 new_key);
 125
 126 #endif /* included_clib_fheap_h */