diff options
Diffstat (limited to 'vppinfra/vppinfra/fheap.c')
-rw-r--r-- | vppinfra/vppinfra/fheap.c | 271 |
1 files changed, 155 insertions, 116 deletions
diff --git a/vppinfra/vppinfra/fheap.c b/vppinfra/vppinfra/fheap.c index 2e8b977a54a..1369245615a 100644 --- a/vppinfra/vppinfra/fheap.c +++ b/vppinfra/vppinfra/fheap.c @@ -17,96 +17,111 @@ /* 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. */ @@ -116,10 +131,10 @@ static void fheap_validate (fheap_t * f) 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) @@ -144,9 +159,10 @@ fheap_node_add_sibling (fheap_t * f, u32 ni, u32 ni_to_add) 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); @@ -157,7 +173,7 @@ void fheap_add (fheap_t * f, u32 ni, u32 key) r = fheap_get_root (f); ri = f->min_root; - if (! r) + if (!r) { /* No root? Add node as new root. */ f->min_root = ni; @@ -178,13 +194,13 @@ void fheap_add (fheap_t * f, u32 ni, u32 key) 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) { @@ -211,16 +227,23 @@ fheap_node_remove_internal (fheap_t * f, u32 ni, u32 invalidate) 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) @@ -229,7 +252,7 @@ static void fheap_link_root (fheap_t * f, u32 ni) 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; @@ -243,7 +266,7 @@ static void fheap_link_root (fheap_t * f, u32 ni) 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; @@ -263,7 +286,7 @@ static void fheap_link_root (fheap_t * f, u32 ni) 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; @@ -271,21 +294,22 @@ static void fheap_link_root (fheap_t * f, u32 ni) } } -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; @@ -328,19 +352,19 @@ u32 fheap_del_min (fheap_t * f, u32 * min_key) 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. */ @@ -353,16 +377,17 @@ u32 fheap_del_min (fheap_t * f, u32 * min_key) 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; @@ -382,10 +407,11 @@ static void fheap_mark_parent (fheap_t * f, u32 pi) } /* 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; @@ -404,9 +430,10 @@ void fheap_decrease_key (fheap_t * f, u32 ni, u32 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); @@ -422,13 +449,25 @@ void fheap_del (fheap_t * f, u32 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: + */ |