FD.io VPP  v17.07.01-10-g3be13f0
Vector Packet Processing
fheap.h
Go to the documentation of this file.
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 {
25  /* Node index of parent. */
27 
28  /* Node index of first child. */
30 
31  /* Next and previous nodes in doubly linked list of siblings. */
32  u32 next_sibling, prev_sibling;
33 
34  /* Key (distance) for this node. Parent always has key
35  <= than keys of children. */
37 
38  /* Number of children (as opposed to descendents). */
40 
42 
43  /* Set to one when node is inserted; zero when deleted. */
45 } fheap_node_t;
46 
47 #define foreach_fheap_node_sibling(f,ni,first_ni,body) \
48 do { \
49  u32 __fheap_foreach_first_ni = (first_ni); \
50  u32 __fheap_foreach_ni = __fheap_foreach_first_ni; \
51  u32 __fheap_foreach_next_ni; \
52  fheap_node_t * __fheap_foreach_n; \
53  if (__fheap_foreach_ni != ~0) \
54  while (1) \
55  { \
56  __fheap_foreach_n = fheap_get_node ((f), __fheap_foreach_ni); \
57  __fheap_foreach_next_ni = __fheap_foreach_n -> next_sibling; \
58  (ni) = __fheap_foreach_ni; \
59  \
60  body; \
61  \
62  /* End of circular list? */ \
63  if (__fheap_foreach_next_ni == __fheap_foreach_first_ni) \
64  break; \
65  \
66  __fheap_foreach_ni = __fheap_foreach_next_ni; \
67  \
68  } \
69 } while (0)
70 
71 typedef struct
72 {
74 
75  /* Vector of nodes. */
77 
79 
81 
83 } fheap_t;
84 
85 /* Initialize empty heap. */
86 always_inline void
87 fheap_init (fheap_t * f, u32 n_nodes)
88 {
89  fheap_node_t *save_nodes = f->nodes;
90  u32 *save_root_list = f->root_list_by_rank;
91 
92  memset (f, 0, sizeof (f[0]));
93 
94  f->nodes = save_nodes;
95  f->root_list_by_rank = save_root_list;
96 
97  vec_validate (f->nodes, n_nodes - 1);
99 
100  f->min_root = ~0;
101 }
102 
103 always_inline void
105 {
106  vec_free (f->nodes);
108 }
109 
112 {
113  return f->min_root;
114 }
115 
118 {
119  return f->min_root == ~0;
120 }
121 
122 /* Add/delete nodes. */
123 void fheap_add (fheap_t * f, u32 ni, u32 key);
124 void fheap_del (fheap_t * f, u32 ni);
125 
126 /* Delete and return minimum. */
127 u32 fheap_del_min (fheap_t * f, u32 * min_key);
128 
129 /* Change key value. */
130 void fheap_decrease_key (fheap_t * f, u32 ni, u32 new_key);
131 
132 #endif /* included_clib_fheap_h */
133 
134 /*
135  * fd.io coding-style-patch-verification: ON
136  *
137  * Local Variables:
138  * eval: (c-set-style "gnu")
139  * End:
140  */
#define vec_validate(V, I)
Make sure vector is long enough for given index (no header, unspecified alignment) ...
Definition: vec.h:436
u32 parent
Definition: fheap.h:26
static u32 fheap_find_min(fheap_t *f)
Definition: fheap.h:111
void fheap_del(fheap_t *f, u32 ni)
Definition: fheap.c:434
static u32 fheap_is_empty(fheap_t *f)
Definition: fheap.h:117
#define vec_reset_length(v)
Reset vector length to zero NULL-pointer tolerant.
fheap_node_t * nodes
Definition: fheap.h:76
#define always_inline
Definition: clib.h:84
static void fheap_init(fheap_t *f, u32 n_nodes)
Definition: fheap.h:87
u32 prev_sibling
Definition: fheap.h:32
u32 * root_list_by_rank
Definition: fheap.h:78
u32 validate_serial
Definition: fheap.h:82
u32 is_valid
Definition: fheap.h:44
void fheap_decrease_key(fheap_t *f, u32 ni, u32 new_key)
Definition: fheap.c:411
#define vec_free(V)
Free vector&#39;s memory (no header).
Definition: vec.h:340
static void fheap_free(fheap_t *f)
Definition: fheap.h:104
unsigned int u32
Definition: types.h:88
u32 fheap_del_min(fheap_t *f, u32 *min_key)
Definition: fheap.c:298
u32 rank
Definition: fheap.h:39
u32 enable_validate
Definition: fheap.h:80
Definition: fheap.h:71
u32 first_child
Definition: fheap.h:29
void fheap_add(fheap_t *f, u32 ni, u32 key)
Definition: fheap.c:163
u32 is_marked
Definition: fheap.h:41
u32 min_root
Definition: fheap.h:73
CLIB vectors are ubiquitous dynamically resized arrays with by user defined "headers".
u32 key
Definition: fheap.h:36