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>
24 /* Node index of parent. */
27 /* Node index of first child. */
30 /* Next and previous nodes in doubly linked list of siblings. */
31 u32 next_sibling, prev_sibling;
33 /* Key (distance) for this node. Parent always has key
34 <= than keys of children. */
37 /* Number of children (as opposed to descendents). */
42 /* Set to one when node is inserted; zero when deleted. */
46 #define foreach_fheap_node_sibling(f,ni,first_ni,body) \
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) \
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; \
61 /* End of circular list? */ \
62 if (__fheap_foreach_next_ni == __fheap_foreach_first_ni) \
65 __fheap_foreach_ni = __fheap_foreach_next_ni; \
73 /* Vector of nodes. */
76 u32 * root_list_by_rank;
83 /* Initialize empty heap. */
85 fheap_init (fheap_t * f, u32 n_nodes)
87 fheap_node_t * save_nodes = f->nodes;
88 u32 * save_root_list = f->root_list_by_rank;
90 memset (f, 0, sizeof (f[0]));
92 f->nodes = save_nodes;
93 f->root_list_by_rank = save_root_list;
95 vec_validate (f->nodes, n_nodes - 1);
96 vec_reset_length (f->root_list_by_rank);
102 fheap_free (fheap_t * f)
105 vec_free (f->root_list_by_rank);
109 fheap_find_min (fheap_t * f)
110 { return f->min_root; }
113 fheap_is_empty (fheap_t * f)
114 { return f->min_root == ~0; }
116 /* Add/delete nodes. */
117 void fheap_add (fheap_t * f, u32 ni, u32 key);
118 void fheap_del (fheap_t * f, u32 ni);
120 /* Delete and return minimum. */
121 u32 fheap_del_min (fheap_t * f, u32 * min_key);
123 /* Change key value. */
124 void fheap_decrease_key (fheap_t * f, u32 ni, u32 new_key);
126 #endif /* included_clib_fheap_h */