src/vppinfra/fheap.c - fdio/vpp - Gitiles

 /*
  * Copyright (c) 2015 Cisco and/or its affiliates.
  * Licensed under the Apache License, Version 2.0 (the "License");
  * you may not use this file except in compliance with the License.
  * You may obtain a copy of the License at:
  *
  *     http://www.apache.org/licenses/LICENSE-2.0
  *
  * Unless required by applicable law or agreed to in writing, software
  * distributed under the License is distributed on an "AS IS" BASIS,
  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  * See the License for the specific language governing permissions and
  * limitations under the License.
  */
 #include <vppinfra/fheap.h>

 /* 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;
 }

 always_inline fheap_node_t *
 fheap_get_root (fheap_t * f)
 {
   return fheap_get_node (f, f->min_root);
 }

 static void
 fheap_validate (fheap_t * f)
 {
   fheap_node_t *n, *m;
   uword ni, si;

   if (!CLIB_DEBUG || !f->enable_validate)
     return;

   vec_foreach_index (ni, f->nodes)
   {
     n = vec_elt_at_index (f->nodes, ni);

     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 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
 	  {
 	    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);
     }

     /* 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. */
   f->validate_serial++;
 }

 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;

   /* Empty list? */
   if (n->next_sibling == ~0)
     {
       ASSERT (n->prev_sibling == ~0);
       n->next_sibling = n->prev_sibling = ni_to_add;
       n_to_add->next_sibling = n_to_add->prev_sibling = ni;
     }
   else
     {
       /* Add node after existing node. */
       n_to_add->prev_sibling = ni;
       n_to_add->next_sibling = n->next_sibling;

       n->next_sibling = ni_to_add;
       n_next->prev_sibling = ni_to_add;
     }

   n_to_add->parent = n->parent;
   parent = fheap_get_node (f, n->parent);
   if (parent)
     parent->rank += 1;
 }

 void
 fheap_add (fheap_t * f, u32 ni, u32 key)
 {
   fheap_node_t *r, *n;
   u32 ri;

   n = vec_elt_at_index (f->nodes, ni);

   clib_memset (n, 0, sizeof (n[0]));
   n->parent = n->first_child = n->next_sibling = n->prev_sibling = ~0;
   n->key = key;

   r = fheap_get_root (f);
   ri = f->min_root;
   if (!r)
     {
       /* No root?  Add node as new root. */
       f->min_root = ni;
     }
   else
     {
       /* Add node as sibling of current root. */
       fheap_node_add_sibling (f, ri, ni);

       /* New node may become new root. */
       if (r->key > n->key)
 	f->min_root = ni;
     }

   fheap_validate (f);
 }

 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);
   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);

   if (p)
     {
       ASSERT (p->rank > 0);
       p->rank -= 1;
       p->first_child = list_has_single_element ? ~0 : next_ni;
     }

   if (prev)
     {
       ASSERT (prev->next_sibling == ni);
       prev->next_sibling = next_ni;
     }
   if (next)
     {
       ASSERT (next->prev_sibling == ni);
       next->prev_sibling = prev_ni;
     }

   n->prev_sibling = n->next_sibling = ni;
   n->parent = ~0;
   n->is_valid = invalidate == 0;

   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_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)
 {
   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)
     {
       k = n->rank;
       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)
 	{
 	  f->root_list_by_rank[k] = ni;
 	  return;
 	}

       f->root_list_by_rank[k] = ~0;

       /* Sort n/r into lo/hi by their keys. */
       lo = r, lo_i = ri;
       hi = n, hi_i = ni;
       if (hi->key < lo->key)
 	{
 	  u32 ti;
 	  fheap_node_t *tn;
 	  ti = lo_i, tn = lo;
 	  lo = hi, lo_i = hi_i;
 	  hi = tn, hi_i = ti;
 	}

       /* Remove larger key. */
       fheap_node_remove (f, hi_i);

       /* Add larger key as child of smaller one. */
       if (lo->first_child == ~0)
 	{
 	  hi->parent = lo_i;
 	  lo->first_child = hi_i;
 	  lo->rank = 1;
 	}
       else
 	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". */
       hi->is_marked = 0;

       ni = lo_i;
       n = lo;
     }
 }

 u32
 fheap_del_min (fheap_t * f, u32 * min_key)
 {
   fheap_node_t *r = fheap_get_root (f);
   u32 to_delete_min_ri = f->min_root;
   u32 ri, ni;

   /* Empty heap? */
   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;

       /* Splice child & root circular lists together. */
       ci = r->first_child;
       c = vec_elt_at_index (f->nodes, ci);

       cni = c->next_sibling;
       rni = r->next_sibling;
       cn = vec_elt_at_index (f->nodes, cni);
       rn = vec_elt_at_index (f->nodes, rni);

       r->next_sibling = cni;
       c->next_sibling = rni;
       cn->prev_sibling = to_delete_min_ri;
       rn->prev_sibling = ci;
     }

   /* Remove min root. */
   ri = fheap_node_remove_and_invalidate (f, to_delete_min_ri);

   /* Find new min root from among siblings including the ones we've just added. */
   f->min_root = ~0;
   if (ri != ~0)
     {
       u32 ri_last, ri_next, i, min_ds;

       r = fheap_get_node (f, ri);
       ri_last = r->prev_sibling;
       while (1)
 	{
 	  /* Step a above can put children (with r->parent != ~0) on root list. */
 	  r->parent = ~0;

 	  ri_next = r->next_sibling;
 	  fheap_link_root (f, ri);
 	  if (ri == ri_last)
 	    break;
 	  ri = ri_next;
 	  r = fheap_get_node (f, ri);
 	}

       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);
 	  }
       }
     }

   /* Return deleted min root. */
   r = vec_elt_at_index (f->nodes, to_delete_min_ri);
   if (min_key)
     *min_key = r->key;

   fheap_validate (f);

   return to_delete_min_ri;
 }

 static void
 fheap_mark_parent (fheap_t * f, u32 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)
     {
       p->is_marked = 1;
       return;
     }

   /* Its a previously marked, non-root parent.
      Cut edge to its parent and add to root list. */
   fheap_node_remove (f, pi);
   fheap_node_add_sibling (f, f->min_root, pi);

   /* Unmark it since its now a root node. */
   p->is_marked = 0;

   /* "Cascading cuts": check parent. */
   if (p->parent != ~0)
     fheap_mark_parent (f, p->parent);
 }

 /* Set key to new smaller value. */
 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);

   n->key = new_key;

   if (n->parent != ~0)
     {
       fheap_mark_parent (f, n->parent);

       /* Remove node and add to root list. */
       fheap_node_remove (f, ni);
       fheap_node_add_sibling (f, f->min_root, ni);
     }

   if (n->key < r->key)
     f->min_root = ni;

   fheap_validate (f);
 }

 void
 fheap_del (fheap_t * f, u32 ni)
 {
   fheap_node_t *n;

   n = vec_elt_at_index (f->nodes, ni);

   if (n->parent == ~0)
     {
       ASSERT (ni == f->min_root);
       fheap_del_min (f, 0);
     }
   else
     {
       u32 ci;

       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);}
 				  ));

       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:
  */
	/*
	* Copyright (c) 2015 Cisco and/or its affiliates.
	* Licensed under the Apache License, Version 2.0 (the "License");
	* you may not use this file except in compliance with the License.
	* You may obtain a copy of the License at:
	*
	* http://www.apache.org/licenses/LICENSE-2.0
	*
	* Unless required by applicable law or agreed to in writing, software
	* distributed under the License is distributed on an "AS IS" BASIS,
	* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
	* See the License for the specific language governing permissions and
	* limitations under the License.
	*/
	#include <vppinfra/fheap.h>

	/* 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;
	}

	always_inline fheap_node_t *
	fheap_get_root (fheap_t * f)
	{
	return fheap_get_node (f, f->min_root);
	}

	static void
	fheap_validate (fheap_t * f)
	{
	fheap_node_t n, m;
	uword ni, si;

	if (!CLIB_DEBUG \|\| !f->enable_validate)
	return;

	vec_foreach_index (ni, f->nodes)
	{
	n = vec_elt_at_index (f->nodes, ni);

	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 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
	{
	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);
	}

	/* 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. */
	f->validate_serial++;
	}

	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;

	/* Empty list? */
	if (n->next_sibling == ~0)
	{
	ASSERT (n->prev_sibling == ~0);
	n->next_sibling = n->prev_sibling = ni_to_add;
	n_to_add->next_sibling = n_to_add->prev_sibling = ni;
	}
	else
	{
	/* Add node after existing node. */
	n_to_add->prev_sibling = ni;
	n_to_add->next_sibling = n->next_sibling;

	n->next_sibling = ni_to_add;
	n_next->prev_sibling = ni_to_add;
	}

	n_to_add->parent = n->parent;
	parent = fheap_get_node (f, n->parent);
	if (parent)
	parent->rank += 1;
	}

	void
	fheap_add (fheap_t * f, u32 ni, u32 key)
	{
	fheap_node_t r, n;
	u32 ri;

	n = vec_elt_at_index (f->nodes, ni);

	clib_memset (n, 0, sizeof (n[0]));
	n->parent = n->first_child = n->next_sibling = n->prev_sibling = ~0;
	n->key = key;

	r = fheap_get_root (f);
	ri = f->min_root;
	if (!r)
	{
	/* No root? Add node as new root. */
	f->min_root = ni;
	}
	else
	{
	/* Add node as sibling of current root. */
	fheap_node_add_sibling (f, ri, ni);

	/* New node may become new root. */
	if (r->key > n->key)
	f->min_root = ni;
	}

	fheap_validate (f);
	}

	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);
	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);

	if (p)
	{
	ASSERT (p->rank > 0);
	p->rank -= 1;
	p->first_child = list_has_single_element ? ~0 : next_ni;
	}

	if (prev)
	{
	ASSERT (prev->next_sibling == ni);
	prev->next_sibling = next_ni;
	}
	if (next)
	{
	ASSERT (next->prev_sibling == ni);
	next->prev_sibling = prev_ni;
	}

	n->prev_sibling = n->next_sibling = ni;
	n->parent = ~0;
	n->is_valid = invalidate == 0;

	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_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)
	{
	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)
	{
	k = n->rank;
	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)
	{
	f->root_list_by_rank[k] = ni;
	return;
	}

	f->root_list_by_rank[k] = ~0;

	/* Sort n/r into lo/hi by their keys. */
	lo = r, lo_i = ri;
	hi = n, hi_i = ni;
	if (hi->key < lo->key)
	{
	u32 ti;
	fheap_node_t *tn;
	ti = lo_i, tn = lo;
	lo = hi, lo_i = hi_i;
	hi = tn, hi_i = ti;
	}

	/* Remove larger key. */
	fheap_node_remove (f, hi_i);

	/* Add larger key as child of smaller one. */
	if (lo->first_child == ~0)
	{
	hi->parent = lo_i;
	lo->first_child = hi_i;
	lo->rank = 1;
	}
	else
	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". */
	hi->is_marked = 0;

	ni = lo_i;
	n = lo;
	}
	}

	u32
	fheap_del_min (fheap_t * f, u32 * min_key)
	{
	fheap_node_t *r = fheap_get_root (f);
	u32 to_delete_min_ri = f->min_root;
	u32 ri, ni;

	/* Empty heap? */
	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;

	/* Splice child & root circular lists together. */
	ci = r->first_child;
	c = vec_elt_at_index (f->nodes, ci);

	cni = c->next_sibling;
	rni = r->next_sibling;
	cn = vec_elt_at_index (f->nodes, cni);
	rn = vec_elt_at_index (f->nodes, rni);

	r->next_sibling = cni;
	c->next_sibling = rni;
	cn->prev_sibling = to_delete_min_ri;
	rn->prev_sibling = ci;
	}

	/* Remove min root. */
	ri = fheap_node_remove_and_invalidate (f, to_delete_min_ri);

	/* Find new min root from among siblings including the ones we've just added. */
	f->min_root = ~0;
	if (ri != ~0)
	{
	u32 ri_last, ri_next, i, min_ds;

	r = fheap_get_node (f, ri);
	ri_last = r->prev_sibling;
	while (1)
	{
	/* Step a above can put children (with r->parent != ~0) on root list. */
	r->parent = ~0;

	ri_next = r->next_sibling;
	fheap_link_root (f, ri);
	if (ri == ri_last)
	break;
	ri = ri_next;
	r = fheap_get_node (f, ri);
	}

	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);
	}
	}
	}

	/* Return deleted min root. */
	r = vec_elt_at_index (f->nodes, to_delete_min_ri);
	if (min_key)
	*min_key = r->key;

	fheap_validate (f);

	return to_delete_min_ri;
	}

	static void
	fheap_mark_parent (fheap_t * f, u32 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)
	{
	p->is_marked = 1;
	return;
	}

	/* Its a previously marked, non-root parent.
	Cut edge to its parent and add to root list. */
	fheap_node_remove (f, pi);
	fheap_node_add_sibling (f, f->min_root, pi);

	/* Unmark it since its now a root node. */
	p->is_marked = 0;

	/* "Cascading cuts": check parent. */
	if (p->parent != ~0)
	fheap_mark_parent (f, p->parent);
	}

	/* Set key to new smaller value. */
	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);

	n->key = new_key;

	if (n->parent != ~0)
	{
	fheap_mark_parent (f, n->parent);

	/* Remove node and add to root list. */
	fheap_node_remove (f, ni);
	fheap_node_add_sibling (f, f->min_root, ni);
	}

	if (n->key < r->key)
	f->min_root = ni;

	fheap_validate (f);
	}

	void
	fheap_del (fheap_t * f, u32 ni)
	{
	fheap_node_t *n;

	n = vec_elt_at_index (f->nodes, ni);

	if (n->parent == ~0)
	{
	ASSERT (ni == f->min_root);
	fheap_del_min (f, 0);
	}
	else
	{
	u32 ci;

	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);}
	));

	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:
	*/