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)
21 return i != ~0 ? vec_elt_at_index (f->nodes, i) : 0;
24 always_inline fheap_node_t *
25 fheap_get_root (fheap_t * f)
27 return fheap_get_node (f, f->min_root);
31 fheap_validate (fheap_t * f)
36 if (!CLIB_DEBUG || !f->enable_validate)
39 vec_foreach_index (ni, f->nodes)
41 n = vec_elt_at_index (f->nodes, ni);
46 /* Min root must have minimal key. */
47 m = vec_elt_at_index (f->nodes, f->min_root);
48 ASSERT (n->key >= m->key);
50 /* Min root must have no parent. */
51 if (ni == f->min_root)
52 ASSERT (n->parent == ~0);
54 /* Check sibling linkages. */
55 if (n->next_sibling == ~0)
56 ASSERT (n->prev_sibling == ~0);
57 else if (n->prev_sibling == ~0)
58 ASSERT (n->next_sibling == ~0);
61 fheap_node_t *prev, *next;
62 u32 si = n->next_sibling, si_start = si;
65 m = vec_elt_at_index (f->nodes, si);
66 prev = vec_elt_at_index (f->nodes, m->prev_sibling);
67 next = vec_elt_at_index (f->nodes, m->next_sibling);
68 ASSERT (prev->next_sibling == si);
69 ASSERT (next->prev_sibling == si);
72 while (si != si_start);
75 /* Loop through all siblings. */
79 foreach_fheap_node_sibling (f, si, n->next_sibling, (
84 /* All siblings must have same parent. */
92 /* Either parent is non-empty or there are siblings present. */
93 if (n->parent == ~0 && ni != f->min_root)
94 ASSERT (n_siblings > 0);
97 /* Loop through all children. */
99 u32 found_first_child = n->first_child == ~0;
102 foreach_fheap_node_sibling (f, si, n->first_child, (
107 /* Children must have larger keys than their parent. */
118 /* Check that first child is present on list. */
119 ASSERT (found_first_child);
121 /* Make sure rank is correct. */
122 ASSERT (n->rank == n_children);
126 /* Increment serial number for each successful validate.
127 Failure can be used as condition for gdb breakpoints. */
128 f->validate_serial++;
132 fheap_node_add_sibling (fheap_t * f, u32 ni, u32 ni_to_add)
134 fheap_node_t *n = vec_elt_at_index (f->nodes, ni);
135 fheap_node_t *n_to_add = vec_elt_at_index (f->nodes, ni_to_add);
136 fheap_node_t *n_next = fheap_get_node (f, n->next_sibling);
137 fheap_node_t *parent;
140 if (n->next_sibling == ~0)
142 ASSERT (n->prev_sibling == ~0);
143 n->next_sibling = n->prev_sibling = ni_to_add;
144 n_to_add->next_sibling = n_to_add->prev_sibling = ni;
148 /* Add node after existing node. */
149 n_to_add->prev_sibling = ni;
150 n_to_add->next_sibling = n->next_sibling;
152 n->next_sibling = ni_to_add;
153 n_next->prev_sibling = ni_to_add;
156 n_to_add->parent = n->parent;
157 parent = fheap_get_node (f, n->parent);
163 fheap_add (fheap_t * f, u32 ni, u32 key)
168 n = vec_elt_at_index (f->nodes, ni);
170 memset (n, 0, sizeof (n[0]));
171 n->parent = n->first_child = n->next_sibling = n->prev_sibling = ~0;
174 r = fheap_get_root (f);
178 /* No root? Add node as new root. */
183 /* Add node as sibling of current root. */
184 fheap_node_add_sibling (f, ri, ni);
186 /* New node may become new root. */
195 fheap_node_remove_internal (fheap_t * f, u32 ni, u32 invalidate)
197 fheap_node_t *n = vec_elt_at_index (f->nodes, ni);
198 u32 prev_ni = n->prev_sibling;
199 u32 next_ni = n->next_sibling;
200 u32 list_has_single_element = prev_ni == ni;
201 fheap_node_t *prev = fheap_get_node (f, prev_ni);
202 fheap_node_t *next = fheap_get_node (f, next_ni);
203 fheap_node_t *p = fheap_get_node (f, n->parent);
207 ASSERT (p->rank > 0);
209 p->first_child = list_has_single_element ? ~0 : next_ni;
214 ASSERT (prev->next_sibling == ni);
215 prev->next_sibling = next_ni;
219 ASSERT (next->prev_sibling == ni);
220 next->prev_sibling = prev_ni;
223 n->prev_sibling = n->next_sibling = ni;
225 n->is_valid = invalidate == 0;
227 return list_has_single_element ? ~0 : next_ni;
231 fheap_node_remove (fheap_t * f, u32 ni)
233 return fheap_node_remove_internal (f, ni, /* invalidate */ 0);
237 fheap_node_remove_and_invalidate (fheap_t * f, u32 ni)
239 return fheap_node_remove_internal (f, ni, /* invalidate */ 1);
243 fheap_link_root (fheap_t * f, u32 ni)
245 fheap_node_t *n = vec_elt_at_index (f->nodes, ni);
246 fheap_node_t *r, *lo, *hi;
247 u32 ri, lo_i, hi_i, k;
252 vec_validate_init_empty (f->root_list_by_rank, k, ~0);
253 ri = f->root_list_by_rank[k];
254 r = fheap_get_node (f, ri);
257 f->root_list_by_rank[k] = ni;
261 f->root_list_by_rank[k] = ~0;
263 /* Sort n/r into lo/hi by their keys. */
266 if (hi->key < lo->key)
271 lo = hi, lo_i = hi_i;
275 /* Remove larger key. */
276 fheap_node_remove (f, hi_i);
278 /* Add larger key as child of smaller one. */
279 if (lo->first_child == ~0)
282 lo->first_child = hi_i;
286 fheap_node_add_sibling (f, lo->first_child, hi_i);
288 /* Following Fredman & Trajan: "When making a root node X a child of another node in a linking step,
298 fheap_del_min (fheap_t * f, u32 * min_key)
300 fheap_node_t *r = fheap_get_root (f);
301 u32 to_delete_min_ri = f->min_root;
308 /* Root's children become siblings. Call this step a; see below. */
309 if (r->first_child != ~0)
312 fheap_node_t *c, *cn, *rn;
314 /* Splice child & root circular lists together. */
316 c = vec_elt_at_index (f->nodes, ci);
318 cni = c->next_sibling;
319 rni = r->next_sibling;
320 cn = vec_elt_at_index (f->nodes, cni);
321 rn = vec_elt_at_index (f->nodes, rni);
323 r->next_sibling = cni;
324 c->next_sibling = rni;
325 cn->prev_sibling = to_delete_min_ri;
326 rn->prev_sibling = ci;
329 /* Remove min root. */
330 ri = fheap_node_remove_and_invalidate (f, to_delete_min_ri);
332 /* Find new min root from among siblings including the ones we've just added. */
336 u32 ri_last, ri_next, i, min_ds;
338 r = fheap_get_node (f, ri);
339 ri_last = r->prev_sibling;
342 /* Step a above can put children (with r->parent != ~0) on root list. */
345 ri_next = r->next_sibling;
346 fheap_link_root (f, ri);
350 r = fheap_get_node (f, ri);
354 vec_foreach_index (i, f->root_list_by_rank)
356 ni = f->root_list_by_rank[i];
359 f->root_list_by_rank[i] = ~0;
360 r = fheap_get_node (f, ni);
365 ASSERT (r->parent == ~0);
370 /* Return deleted min root. */
371 r = vec_elt_at_index (f->nodes, to_delete_min_ri);
377 return to_delete_min_ri;
381 fheap_mark_parent (fheap_t * f, u32 pi)
383 fheap_node_t *p = vec_elt_at_index (f->nodes, pi);
385 /* Parent is a root: do nothing. */
389 /* If not marked, mark it. */
396 /* Its a previously marked, non-root parent.
397 Cut edge to its parent and add to root list. */
398 fheap_node_remove (f, pi);
399 fheap_node_add_sibling (f, f->min_root, pi);
401 /* Unmark it since its now a root node. */
404 /* "Cascading cuts": check parent. */
406 fheap_mark_parent (f, p->parent);
409 /* Set key to new smaller value. */
411 fheap_decrease_key (fheap_t * f, u32 ni, u32 new_key)
413 fheap_node_t *n = vec_elt_at_index (f->nodes, ni);
414 fheap_node_t *r = fheap_get_root (f);
420 fheap_mark_parent (f, n->parent);
422 /* Remove node and add to root list. */
423 fheap_node_remove (f, ni);
424 fheap_node_add_sibling (f, f->min_root, ni);
434 fheap_del (fheap_t * f, u32 ni)
438 n = vec_elt_at_index (f->nodes, ni);
442 ASSERT (ni == f->min_root);
443 fheap_del_min (f, 0);
449 fheap_mark_parent (f, n->parent);
451 /* Add children to root list. */
452 foreach_fheap_node_sibling (f, ci, n->first_child, (
456 fheap_node_add_sibling
461 fheap_node_remove_and_invalidate (f, ni);
468 * fd.io coding-style-patch-verification: ON
471 * eval: (c-set-style "gnu")