/* Fibonacci heaps. */
always_inline fheap_node_t *
fheap_get_node (fheap_t * f, u32 i)
-{ return i != ~0 ? vec_elt_at_index (f->nodes, i) : 0; }
+{
+ return i != ~0 ? vec_elt_at_index (f->nodes, i) : 0;
+}
always_inline fheap_node_t *
fheap_get_root (fheap_t * f)
-{ return fheap_get_node (f, f->min_root); }
+{
+ return fheap_get_node (f, f->min_root);
+}
-static void fheap_validate (fheap_t * f)
+static void
+fheap_validate (fheap_t * f)
{
- fheap_node_t * n, * m;
+ fheap_node_t *n, *m;
uword ni, si;
- if (! CLIB_DEBUG || ! f->enable_validate)
+ if (!CLIB_DEBUG || !f->enable_validate)
return;
vec_foreach_index (ni, f->nodes)
- {
- n = vec_elt_at_index (f->nodes, ni);
+ {
+ n = vec_elt_at_index (f->nodes, ni);
- if (! n->is_valid)
- continue;
+ if (!n->is_valid)
+ continue;
- /* Min root must have minimal key. */
- m = vec_elt_at_index (f->nodes, f->min_root);
- ASSERT (n->key >= m->key);
+ /* Min root must have minimal key. */
+ m = vec_elt_at_index (f->nodes, f->min_root);
+ ASSERT (n->key >= m->key);
- /* Min root must have no parent. */
- if (ni == f->min_root)
- ASSERT (n->parent == ~0);
+ /* Min root must have no parent. */
+ if (ni == f->min_root)
+ ASSERT (n->parent == ~0);
- /* Check sibling linkages. */
- if (n->next_sibling == ~0)
- ASSERT (n->prev_sibling == ~0);
- else if (n->prev_sibling == ~0)
- ASSERT (n->next_sibling == ~0);
- else
- {
- fheap_node_t * prev, * next;
- u32 si = n->next_sibling, si_start = si;
- do {
+ /* Check sibling linkages. */
+ if (n->next_sibling == ~0)
+ ASSERT (n->prev_sibling == ~0);
+ else if (n->prev_sibling == ~0)
+ ASSERT (n->next_sibling == ~0);
+ else
+ {
+ fheap_node_t *prev, *next;
+ u32 si = n->next_sibling, si_start = si;
+ do
+ {
m = vec_elt_at_index (f->nodes, si);
prev = vec_elt_at_index (f->nodes, m->prev_sibling);
next = vec_elt_at_index (f->nodes, m->next_sibling);
ASSERT (prev->next_sibling == si);
ASSERT (next->prev_sibling == si);
si = m->next_sibling;
- } while (si != si_start);
- }
-
- /* Loop through all siblings. */
- {
- u32 n_siblings = 0;
-
- foreach_fheap_node_sibling (f, si, n->next_sibling, ({
- m = vec_elt_at_index (f->nodes, si);
-
- /* All siblings must have same parent. */
- ASSERT (m->parent == n->parent);
-
- n_siblings += 1;
- }));
-
- /* Either parent is non-empty or there are siblings present. */
- if (n->parent == ~0 && ni != f->min_root)
- ASSERT (n_siblings > 0);
+ }
+ while (si != si_start);
}
- /* Loop through all children. */
- {
- u32 found_first_child = n->first_child == ~0;
- u32 n_children = 0;
-
- foreach_fheap_node_sibling (f, si, n->first_child, ({
- m = vec_elt_at_index (f->nodes, si);
-
- /* Children must have larger keys than their parent. */
- ASSERT (m->key >= n->key);
-
- if (! found_first_child)
- found_first_child = si == n->first_child;
-
- n_children += 1;
- }));
-
- /* Check that first child is present on list. */
- ASSERT (found_first_child);
+ /* Loop through all siblings. */
+ {
+ u32 n_siblings = 0;
+
+ foreach_fheap_node_sibling (f, si, n->next_sibling, (
+ {
+ m =
+ vec_elt_at_index
+ (f->nodes, si);
+ /* All siblings must have same parent. */
+ ASSERT (m->parent
+ ==
+ n->
+ parent);
+ n_siblings += 1;}
+ ));
+
+ /* Either parent is non-empty or there are siblings present. */
+ if (n->parent == ~0 && ni != f->min_root)
+ ASSERT (n_siblings > 0);
+ }
- /* Make sure rank is correct. */
- ASSERT (n->rank == n_children);
- }
+ /* Loop through all children. */
+ {
+ u32 found_first_child = n->first_child == ~0;
+ u32 n_children = 0;
+
+ foreach_fheap_node_sibling (f, si, n->first_child, (
+ {
+ m =
+ vec_elt_at_index
+ (f->nodes, si);
+ /* Children must have larger keys than their parent. */
+ ASSERT (m->key >=
+ n->key);
+ if
+ (!found_first_child)
+ found_first_child =
+ si ==
+ n->first_child;
+ n_children += 1;}
+ ));
+
+ /* Check that first child is present on list. */
+ ASSERT (found_first_child);
+
+ /* Make sure rank is correct. */
+ ASSERT (n->rank == n_children);
}
+ }
/* Increment serial number for each successful validate.
Failure can be used as condition for gdb breakpoints. */
always_inline void
fheap_node_add_sibling (fheap_t * f, u32 ni, u32 ni_to_add)
{
- fheap_node_t * n = vec_elt_at_index (f->nodes, ni);
- fheap_node_t * n_to_add = vec_elt_at_index (f->nodes, ni_to_add);
- fheap_node_t * n_next = fheap_get_node (f, n->next_sibling);
- fheap_node_t * parent;
+ fheap_node_t *n = vec_elt_at_index (f->nodes, ni);
+ fheap_node_t *n_to_add = vec_elt_at_index (f->nodes, ni_to_add);
+ fheap_node_t *n_next = fheap_get_node (f, n->next_sibling);
+ fheap_node_t *parent;
/* Empty list? */
if (n->next_sibling == ~0)
parent->rank += 1;
}
-void fheap_add (fheap_t * f, u32 ni, u32 key)
+void
+fheap_add (fheap_t * f, u32 ni, u32 key)
{
- fheap_node_t * r, * n;
+ fheap_node_t *r, *n;
u32 ri;
n = vec_elt_at_index (f->nodes, ni);
r = fheap_get_root (f);
ri = f->min_root;
- if (! r)
+ if (!r)
{
/* No root? Add node as new root. */
f->min_root = ni;
always_inline u32
fheap_node_remove_internal (fheap_t * f, u32 ni, u32 invalidate)
{
- fheap_node_t * n = vec_elt_at_index (f->nodes, ni);
+ fheap_node_t *n = vec_elt_at_index (f->nodes, ni);
u32 prev_ni = n->prev_sibling;
u32 next_ni = n->next_sibling;
u32 list_has_single_element = prev_ni == ni;
- fheap_node_t * prev = fheap_get_node (f, prev_ni);
- fheap_node_t * next = fheap_get_node (f, next_ni);
- fheap_node_t * p = fheap_get_node (f, n->parent);
+ fheap_node_t *prev = fheap_get_node (f, prev_ni);
+ fheap_node_t *next = fheap_get_node (f, next_ni);
+ fheap_node_t *p = fheap_get_node (f, n->parent);
if (p)
{
return list_has_single_element ? ~0 : next_ni;
}
-always_inline u32 fheap_node_remove (fheap_t * f, u32 ni)
-{ return fheap_node_remove_internal (f, ni, /* invalidate */ 0); }
+always_inline u32
+fheap_node_remove (fheap_t * f, u32 ni)
+{
+ return fheap_node_remove_internal (f, ni, /* invalidate */ 0);
+}
-always_inline u32 fheap_node_remove_and_invalidate (fheap_t * f, u32 ni)
-{ return fheap_node_remove_internal (f, ni, /* invalidate */ 1); }
+always_inline u32
+fheap_node_remove_and_invalidate (fheap_t * f, u32 ni)
+{
+ return fheap_node_remove_internal (f, ni, /* invalidate */ 1);
+}
-static void fheap_link_root (fheap_t * f, u32 ni)
+static void
+fheap_link_root (fheap_t * f, u32 ni)
{
- fheap_node_t * n = vec_elt_at_index (f->nodes, ni);
- fheap_node_t * r, * lo, * hi;
+ fheap_node_t *n = vec_elt_at_index (f->nodes, ni);
+ fheap_node_t *r, *lo, *hi;
u32 ri, lo_i, hi_i, k;
while (1)
vec_validate_init_empty (f->root_list_by_rank, k, ~0);
ri = f->root_list_by_rank[k];
r = fheap_get_node (f, ri);
- if (! r)
+ if (!r)
{
f->root_list_by_rank[k] = ni;
return;
if (hi->key < lo->key)
{
u32 ti;
- fheap_node_t * tn;
+ fheap_node_t *tn;
ti = lo_i, tn = lo;
lo = hi, lo_i = hi_i;
hi = tn, hi_i = ti;
fheap_node_add_sibling (f, lo->first_child, hi_i);
/* Following Fredman & Trajan: "When making a root node X a child of another node in a linking step,
- we unmark X". */
+ we unmark X". */
hi->is_marked = 0;
ni = lo_i;
}
}
-u32 fheap_del_min (fheap_t * f, u32 * min_key)
+u32
+fheap_del_min (fheap_t * f, u32 * min_key)
{
- fheap_node_t * r = fheap_get_root (f);
+ fheap_node_t *r = fheap_get_root (f);
u32 to_delete_min_ri = f->min_root;
u32 ri, ni;
/* Empty heap? */
- if (! r)
+ if (!r)
return ~0;
/* Root's children become siblings. Call this step a; see below. */
if (r->first_child != ~0)
{
u32 ci, cni, rni;
- fheap_node_t * c, * cn, * rn;
+ fheap_node_t *c, *cn, *rn;
/* Splice child & root circular lists together. */
ci = r->first_child;
min_ds = ~0;
vec_foreach_index (i, f->root_list_by_rank)
- {
- ni = f->root_list_by_rank[i];
- if (ni == ~0)
- continue;
- f->root_list_by_rank[i] = ~0;
- r = fheap_get_node (f, ni);
- if (r->key < min_ds)
- {
- f->min_root = ni;
- min_ds = r->key;
- ASSERT (r->parent == ~0);
- }
- }
+ {
+ ni = f->root_list_by_rank[i];
+ if (ni == ~0)
+ continue;
+ f->root_list_by_rank[i] = ~0;
+ r = fheap_get_node (f, ni);
+ if (r->key < min_ds)
+ {
+ f->min_root = ni;
+ min_ds = r->key;
+ ASSERT (r->parent == ~0);
+ }
+ }
}
/* Return deleted min root. */
return to_delete_min_ri;
}
-static void fheap_mark_parent (fheap_t * f, u32 pi)
+static void
+fheap_mark_parent (fheap_t * f, u32 pi)
{
- fheap_node_t * p = vec_elt_at_index (f->nodes, pi);
+ fheap_node_t *p = vec_elt_at_index (f->nodes, pi);
/* Parent is a root: do nothing. */
if (p->parent == ~0)
return;
/* If not marked, mark it. */
- if (! p->is_marked)
+ if (!p->is_marked)
{
p->is_marked = 1;
return;
}
/* Set key to new smaller value. */
-void fheap_decrease_key (fheap_t * f, u32 ni, u32 new_key)
+void
+fheap_decrease_key (fheap_t * f, u32 ni, u32 new_key)
{
- fheap_node_t * n = vec_elt_at_index (f->nodes, ni);
- fheap_node_t * r = fheap_get_root (f);
+ fheap_node_t *n = vec_elt_at_index (f->nodes, ni);
+ fheap_node_t *r = fheap_get_root (f);
n->key = new_key;
fheap_validate (f);
}
-void fheap_del (fheap_t * f, u32 ni)
+void
+fheap_del (fheap_t * f, u32 ni)
{
- fheap_node_t * n;
+ fheap_node_t *n;
n = vec_elt_at_index (f->nodes, ni);
fheap_mark_parent (f, n->parent);
/* Add children to root list. */
- foreach_fheap_node_sibling (f, ci, n->first_child, ({
- fheap_node_remove (f, ci);
- fheap_node_add_sibling (f, f->min_root, ci);
- }));
+ foreach_fheap_node_sibling (f, ci, n->first_child, (
+ {
+ fheap_node_remove
+ (f, ci);
+ fheap_node_add_sibling
+ (f, f->min_root,
+ ci);}
+ ));
fheap_node_remove_and_invalidate (f, ni);
}
fheap_validate (f);
}
+
+/*
+ * fd.io coding-style-patch-verification: ON
+ *
+ * Local Variables:
+ * eval: (c-set-style "gnu")
+ * End:
+ */
Code Review / vpp.git / blobdiff