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:
7 * http://www.apache.org/licenses/LICENSE-2.0
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.
15 #ifndef included_clib_fheap_h
16 #define included_clib_fheap_h
18 /* Fibonacci Heaps Fredman, M. L.; Tarjan (1987).
19 "Fibonacci heaps and their uses in improved network optimization algorithms" */
21 #include <vppinfra/vec.h>
25 /* Node index of parent. */
28 /* Node index of first child. */
31 /* Next and previous nodes in doubly linked list of siblings. */
32 u32 next_sibling, prev_sibling;
34 /* Key (distance) for this node. Parent always has key
35 <= than keys of children. */
38 /* Number of children (as opposed to descendents). */
43 /* Set to one when node is inserted; zero when deleted. */
47 #define foreach_fheap_node_sibling(f,ni,first_ni,body) \
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) \
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; \
62 /* End of circular list? */ \
63 if (__fheap_foreach_next_ni == __fheap_foreach_first_ni) \
66 __fheap_foreach_ni = __fheap_foreach_next_ni; \
75 /* Vector of nodes. */
78 u32 *root_list_by_rank;
85 /* Initialize empty heap. */
87 fheap_init (fheap_t * f, u32 n_nodes)
89 fheap_node_t *save_nodes = f->nodes;
90 u32 *save_root_list = f->root_list_by_rank;
92 memset (f, 0, sizeof (f[0]));
94 f->nodes = save_nodes;
95 f->root_list_by_rank = save_root_list;
97 vec_validate (f->nodes, n_nodes - 1);
98 vec_reset_length (f->root_list_by_rank);
104 fheap_free (fheap_t * f)
107 vec_free (f->root_list_by_rank);
111 fheap_find_min (fheap_t * f)
117 fheap_is_empty (fheap_t * f)
119 return f->min_root == ~0;
122 /* Add/delete nodes. */
123 void fheap_add (fheap_t * f, u32 ni, u32 key);
124 void fheap_del (fheap_t * f, u32 ni);
126 /* Delete and return minimum. */
127 u32 fheap_del_min (fheap_t * f, u32 * min_key);
129 /* Change key value. */
130 void fheap_decrease_key (fheap_t * f, u32 ni, u32 new_key);
132 #endif /* included_clib_fheap_h */
135 * fd.io coding-style-patch-verification: ON
138 * eval: (c-set-style "gnu")