fheap.c

Go to the documentation of this file.

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