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 #include <vppinfra/fheap.h>
17 /* Fibonacci heaps. */
18 always_inline fheap_node_t *
19 fheap_get_node (fheap_t * f, u32 i)
20 { return i != ~0 ? vec_elt_at_index (f->nodes, i) : 0; }
22 always_inline fheap_node_t *
23 fheap_get_root (fheap_t * f)
24 { return fheap_get_node (f, f->min_root); }
26 static void fheap_validate (fheap_t * f)
28 fheap_node_t * n, * m;
31 if (! CLIB_DEBUG || ! f->enable_validate)
34 vec_foreach_index (ni, f->nodes)
36 n = vec_elt_at_index (f->nodes, ni);
41 /* Min root must have minimal key. */
42 m = vec_elt_at_index (f->nodes, f->min_root);
43 ASSERT (n->key >= m->key);
45 /* Min root must have no parent. */
46 if (ni == f->min_root)
47 ASSERT (n->parent == ~0);
49 /* Check sibling linkages. */
50 if (n->next_sibling == ~0)
51 ASSERT (n->prev_sibling == ~0);
52 else if (n->prev_sibling == ~0)
53 ASSERT (n->next_sibling == ~0);
56 fheap_node_t * prev, * next;
57 u32 si = n->next_sibling, si_start = si;
59 m = vec_elt_at_index (f->nodes, si);
60 prev = vec_elt_at_index (f->nodes, m->prev_sibling);
61 next = vec_elt_at_index (f->nodes, m->next_sibling);
62 ASSERT (prev->next_sibling == si);
63 ASSERT (next->prev_sibling == si);
65 } while (si != si_start);
68 /* Loop through all siblings. */
72 foreach_fheap_node_sibling (f, si, n->next_sibling, ({
73 m = vec_elt_at_index (f->nodes, si);
75 /* All siblings must have same parent. */
76 ASSERT (m->parent == n->parent);
81 /* Either parent is non-empty or there are siblings present. */
82 if (n->parent == ~0 && ni != f->min_root)
83 ASSERT (n_siblings > 0);
86 /* Loop through all children. */
88 u32 found_first_child = n->first_child == ~0;
91 foreach_fheap_node_sibling (f, si, n->first_child, ({
92 m = vec_elt_at_index (f->nodes, si);
94 /* Children must have larger keys than their parent. */
95 ASSERT (m->key >= n->key);
97 if (! found_first_child)
98 found_first_child = si == n->first_child;
103 /* Check that first child is present on list. */
104 ASSERT (found_first_child);
106 /* Make sure rank is correct. */
107 ASSERT (n->rank == n_children);
111 /* Increment serial number for each successful validate.
112 Failure can be used as condition for gdb breakpoints. */
113 f->validate_serial++;
117 fheap_node_add_sibling (fheap_t * f, u32 ni, u32 ni_to_add)
119 fheap_node_t * n = vec_elt_at_index (f->nodes, ni);
120 fheap_node_t * n_to_add = vec_elt_at_index (f->nodes, ni_to_add);
121 fheap_node_t * n_next = fheap_get_node (f, n->next_sibling);
122 fheap_node_t * parent;
125 if (n->next_sibling == ~0)
127 ASSERT (n->prev_sibling == ~0);
128 n->next_sibling = n->prev_sibling = ni_to_add;
129 n_to_add->next_sibling = n_to_add->prev_sibling = ni;
133 /* Add node after existing node. */
134 n_to_add->prev_sibling = ni;
135 n_to_add->next_sibling = n->next_sibling;
137 n->next_sibling = ni_to_add;
138 n_next->prev_sibling = ni_to_add;
141 n_to_add->parent = n->parent;
142 parent = fheap_get_node (f, n->parent);
147 void fheap_add (fheap_t * f, u32 ni, u32 key)
149 fheap_node_t * r, * n;
152 n = vec_elt_at_index (f->nodes, ni);
154 memset (n, 0, sizeof (n[0]));
155 n->parent = n->first_child = n->next_sibling = n->prev_sibling = ~0;
158 r = fheap_get_root (f);
162 /* No root? Add node as new root. */
167 /* Add node as sibling of current root. */
168 fheap_node_add_sibling (f, ri, ni);
170 /* New node may become new root. */
179 fheap_node_remove_internal (fheap_t * f, u32 ni, u32 invalidate)
181 fheap_node_t * n = vec_elt_at_index (f->nodes, ni);
182 u32 prev_ni = n->prev_sibling;
183 u32 next_ni = n->next_sibling;
184 u32 list_has_single_element = prev_ni == ni;
185 fheap_node_t * prev = fheap_get_node (f, prev_ni);
186 fheap_node_t * next = fheap_get_node (f, next_ni);
187 fheap_node_t * p = fheap_get_node (f, n->parent);
191 ASSERT (p->rank > 0);
193 p->first_child = list_has_single_element ? ~0 : next_ni;
198 ASSERT (prev->next_sibling == ni);
199 prev->next_sibling = next_ni;
203 ASSERT (next->prev_sibling == ni);
204 next->prev_sibling = prev_ni;
207 n->prev_sibling = n->next_sibling = ni;
209 n->is_valid = invalidate == 0;
211 return list_has_single_element ? ~0 : next_ni;
214 always_inline u32 fheap_node_remove (fheap_t * f, u32 ni)
215 { return fheap_node_remove_internal (f, ni, /* invalidate */ 0); }
217 always_inline u32 fheap_node_remove_and_invalidate (fheap_t * f, u32 ni)
218 { return fheap_node_remove_internal (f, ni, /* invalidate */ 1); }
220 static void fheap_link_root (fheap_t * f, u32 ni)
222 fheap_node_t * n = vec_elt_at_index (f->nodes, ni);
223 fheap_node_t * r, * lo, * hi;
224 u32 ri, lo_i, hi_i, k;
229 vec_validate_init_empty (f->root_list_by_rank, k, ~0);
230 ri = f->root_list_by_rank[k];
231 r = fheap_get_node (f, ri);
234 f->root_list_by_rank[k] = ni;
238 f->root_list_by_rank[k] = ~0;
240 /* Sort n/r into lo/hi by their keys. */
243 if (hi->key < lo->key)
248 lo = hi, lo_i = hi_i;
252 /* Remove larger key. */
253 fheap_node_remove (f, hi_i);
255 /* Add larger key as child of smaller one. */
256 if (lo->first_child == ~0)
259 lo->first_child = hi_i;
263 fheap_node_add_sibling (f, lo->first_child, hi_i);
265 /* Following Fredman & Trajan: "When making a root node X a child of another node in a linking step,
274 u32 fheap_del_min (fheap_t * f, u32 * min_key)
276 fheap_node_t * r = fheap_get_root (f);
277 u32 to_delete_min_ri = f->min_root;
284 /* Root's children become siblings. Call this step a; see below. */
285 if (r->first_child != ~0)
288 fheap_node_t * c, * cn, * rn;
290 /* Splice child & root circular lists together. */
292 c = vec_elt_at_index (f->nodes, ci);
294 cni = c->next_sibling;
295 rni = r->next_sibling;
296 cn = vec_elt_at_index (f->nodes, cni);
297 rn = vec_elt_at_index (f->nodes, rni);
299 r->next_sibling = cni;
300 c->next_sibling = rni;
301 cn->prev_sibling = to_delete_min_ri;
302 rn->prev_sibling = ci;
305 /* Remove min root. */
306 ri = fheap_node_remove_and_invalidate (f, to_delete_min_ri);
308 /* Find new min root from among siblings including the ones we've just added. */
312 u32 ri_last, ri_next, i, min_ds;
314 r = fheap_get_node (f, ri);
315 ri_last = r->prev_sibling;
318 /* Step a above can put children (with r->parent != ~0) on root list. */
321 ri_next = r->next_sibling;
322 fheap_link_root (f, ri);
326 r = fheap_get_node (f, ri);
330 vec_foreach_index (i, f->root_list_by_rank)
332 ni = f->root_list_by_rank[i];
335 f->root_list_by_rank[i] = ~0;
336 r = fheap_get_node (f, ni);
341 ASSERT (r->parent == ~0);
346 /* Return deleted min root. */
347 r = vec_elt_at_index (f->nodes, to_delete_min_ri);
353 return to_delete_min_ri;
356 static void fheap_mark_parent (fheap_t * f, u32 pi)
358 fheap_node_t * p = vec_elt_at_index (f->nodes, pi);
360 /* Parent is a root: do nothing. */
364 /* If not marked, mark it. */
371 /* Its a previously marked, non-root parent.
372 Cut edge to its parent and add to root list. */
373 fheap_node_remove (f, pi);
374 fheap_node_add_sibling (f, f->min_root, pi);
376 /* Unmark it since its now a root node. */
379 /* "Cascading cuts": check parent. */
381 fheap_mark_parent (f, p->parent);
384 /* Set key to new smaller value. */
385 void fheap_decrease_key (fheap_t * f, u32 ni, u32 new_key)
387 fheap_node_t * n = vec_elt_at_index (f->nodes, ni);
388 fheap_node_t * r = fheap_get_root (f);
394 fheap_mark_parent (f, n->parent);
396 /* Remove node and add to root list. */
397 fheap_node_remove (f, ni);
398 fheap_node_add_sibling (f, f->min_root, ni);
407 void fheap_del (fheap_t * f, u32 ni)
411 n = vec_elt_at_index (f->nodes, ni);
415 ASSERT (ni == f->min_root);
416 fheap_del_min (f, 0);
422 fheap_mark_parent (f, n->parent);
424 /* Add children to root list. */
425 foreach_fheap_node_sibling (f, ci, n->first_child, ({
426 fheap_node_remove (f, ci);
427 fheap_node_add_sibling (f, f->min_root, ci);
430 fheap_node_remove_and_invalidate (f, ni);