vppinfra/vppinfra/fheap.c

   1 /*
   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:
   6  *
   7  *     http://www.apache.org/licenses/LICENSE-2.0
   8  *
   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.
  14  */
  15 #include <vppinfra/fheap.h>
  16
  17 /* Fibonacci heaps. */
  18 always_inline fheap_node_t *
  19 fheap_get_node (fheap_t * f, u32 i)
  20 { return i != ~0 ? vec_elt_at_index (f->nodes, i) : 0; }
  21
  22 always_inline fheap_node_t *
  23 fheap_get_root (fheap_t * f)
  24 { return fheap_get_node (f, f->min_root); }
  25
  26 static void fheap_validate (fheap_t * f)
  27 {
  28   fheap_node_t * n, * m;
  29   uword ni, si;
  30
  31   if (! CLIB_DEBUG || ! f->enable_validate)
  32     return;
  33
  34   vec_foreach_index (ni, f->nodes)
  35     {
  36       n = vec_elt_at_index (f->nodes, ni);
  37
  38       if (! n->is_valid)
  39         continue;
  40
  41       /* Min root must have minimal key. */
  42       m = vec_elt_at_index (f->nodes, f->min_root);
  43       ASSERT (n->key >= m->key);
  44
  45       /* Min root must have no parent. */
  46       if (ni == f->min_root)
  47         ASSERT (n->parent == ~0);
  48
  49       /* Check sibling linkages. */
  50       if (n->next_sibling == ~0)
  51         ASSERT (n->prev_sibling == ~0);
  52       else if (n->prev_sibling == ~0)
  53         ASSERT (n->next_sibling == ~0);
  54       else
  55         {
  56           fheap_node_t * prev, * next;
  57           u32 si = n->next_sibling, si_start = si;
  58           do {
  59             m = vec_elt_at_index (f->nodes, si);
  60             prev = vec_elt_at_index (f->nodes, m->prev_sibling);
  61             next = vec_elt_at_index (f->nodes, m->next_sibling);
  62             ASSERT (prev->next_sibling == si);
  63             ASSERT (next->prev_sibling == si);
  64             si = m->next_sibling;
  65           } while (si != si_start);
  66         }
  67
  68       /* Loop through all siblings. */
  69       {
  70         u32 n_siblings = 0;
  71
  72         foreach_fheap_node_sibling (f, si, n->next_sibling, ({
  73           m = vec_elt_at_index (f->nodes, si);
  74
  75           /* All siblings must have same parent. */
  76           ASSERT (m->parent == n->parent);
  77
  78           n_siblings += 1;
  79         }));
  80
  81         /* Either parent is non-empty or there are siblings present. */
  82         if (n->parent == ~0 && ni != f->min_root)
  83           ASSERT (n_siblings > 0);
  84       }
  85
  86       /* Loop through all children. */
  87       {
  88         u32 found_first_child = n->first_child == ~0;
  89         u32 n_children = 0;
  90
  91         foreach_fheap_node_sibling (f, si, n->first_child, ({
  92           m = vec_elt_at_index (f->nodes, si);
  93
  94           /* Children must have larger keys than their parent. */
  95           ASSERT (m->key >= n->key);
  96
  97           if (! found_first_child)
  98             found_first_child = si == n->first_child;
  99
 100           n_children += 1;
 101         }));
 102
 103         /* Check that first child is present on list. */
 104         ASSERT (found_first_child);
 105
 106         /* Make sure rank is correct. */
 107         ASSERT (n->rank == n_children);
 108       }
 109     }
 110
 111   /* Increment serial number for each successful validate.
 112      Failure can be used as condition for gdb breakpoints. */
 113   f->validate_serial++;
 114 }
 115
 116 always_inline void
 117 fheap_node_add_sibling (fheap_t * f, u32 ni, u32 ni_to_add)
 118 {
 119   fheap_node_t * n = vec_elt_at_index (f->nodes, ni);
 120   fheap_node_t * n_to_add = vec_elt_at_index (f->nodes, ni_to_add);
 121   fheap_node_t * n_next = fheap_get_node (f, n->next_sibling);
 122   fheap_node_t * parent;
 123
 124   /* Empty list? */
 125   if (n->next_sibling == ~0)
 126     {
 127       ASSERT (n->prev_sibling == ~0);
 128       n->next_sibling = n->prev_sibling = ni_to_add;
 129       n_to_add->next_sibling = n_to_add->prev_sibling = ni;
 130     }
 131   else
 132     {
 133       /* Add node after existing node. */
 134       n_to_add->prev_sibling = ni;
 135       n_to_add->next_sibling = n->next_sibling;
 136
 137       n->next_sibling = ni_to_add;
 138       n_next->prev_sibling = ni_to_add;
 139     }
 140
 141   n_to_add->parent = n->parent;
 142   parent = fheap_get_node (f, n->parent);
 143   if (parent)
 144     parent->rank += 1;
 145 }
 146
 147 void fheap_add (fheap_t * f, u32 ni, u32 key)
 148 {
 149   fheap_node_t * r, * n;
 150   u32 ri;
 151
 152   n = vec_elt_at_index (f->nodes, ni);
 153
 154   memset (n, 0, sizeof (n[0]));
 155   n->parent = n->first_child = n->next_sibling = n->prev_sibling = ~0;
 156   n->key = key;
 157
 158   r = fheap_get_root (f);
 159   ri = f->min_root;
 160   if (! r)
 161     {
 162       /* No root?  Add node as new root. */
 163       f->min_root = ni;
 164     }
 165   else
 166     {
 167       /* Add node as sibling of current root. */
 168       fheap_node_add_sibling (f, ri, ni);
 169
 170       /* New node may become new root. */
 171       if (r->key > n->key)
 172         f->min_root = ni;
 173     }
 174
 175   fheap_validate (f);
 176 }
 177
 178 always_inline u32
 179 fheap_node_remove_internal (fheap_t * f, u32 ni, u32 invalidate)
 180 {
 181   fheap_node_t * n = vec_elt_at_index (f->nodes, ni);
 182   u32 prev_ni = n->prev_sibling;
 183   u32 next_ni = n->next_sibling;
 184   u32 list_has_single_element = prev_ni == ni;
 185   fheap_node_t * prev = fheap_get_node (f, prev_ni);
 186   fheap_node_t * next = fheap_get_node (f, next_ni);
 187   fheap_node_t * p = fheap_get_node (f, n->parent);
 188
 189   if (p)
 190     {
 191       ASSERT (p->rank > 0);
 192       p->rank -= 1;
 193       p->first_child = list_has_single_element ? ~0 : next_ni;
 194     }
 195
 196   if (prev)
 197     {
 198       ASSERT (prev->next_sibling == ni);
 199       prev->next_sibling = next_ni;
 200     }
 201   if (next)
 202     {
 203       ASSERT (next->prev_sibling == ni);
 204       next->prev_sibling = prev_ni;
 205     }
 206
 207   n->prev_sibling = n->next_sibling = ni;
 208   n->parent = ~0;
 209   n->is_valid = invalidate == 0;
 210
 211   return list_has_single_element ? ~0 : next_ni;
 212 }
 213
 214 always_inline u32 fheap_node_remove (fheap_t * f, u32 ni)
 215 { return fheap_node_remove_internal (f, ni, /* invalidate */ 0); }
 216
 217 always_inline u32 fheap_node_remove_and_invalidate (fheap_t * f, u32 ni)
 218 { return fheap_node_remove_internal (f, ni, /* invalidate */ 1); }
 219
 220 static void fheap_link_root (fheap_t * f, u32 ni)
 221 {
 222   fheap_node_t * n = vec_elt_at_index (f->nodes, ni);
 223   fheap_node_t * r, * lo, * hi;
 224   u32 ri, lo_i, hi_i, k;
 225
 226   while (1)
 227     {
 228       k = n->rank;
 229       vec_validate_init_empty (f->root_list_by_rank, k, ~0);
 230       ri = f->root_list_by_rank[k];
 231       r = fheap_get_node (f, ri);
 232       if (! r)
 233         {
 234           f->root_list_by_rank[k] = ni;
 235           return;
 236         }
 237
 238       f->root_list_by_rank[k] = ~0;
 239
 240       /* Sort n/r into lo/hi by their keys. */
 241       lo = r, lo_i = ri;
 242       hi = n, hi_i = ni;
 243       if (hi->key < lo->key)
 244         {
 245           u32 ti;
 246           fheap_node_t * tn;
 247           ti = lo_i, tn = lo;
 248           lo = hi, lo_i = hi_i;
 249           hi = tn, hi_i = ti;
 250         }
 251
 252       /* Remove larger key. */
 253       fheap_node_remove (f, hi_i);
 254
 255       /* Add larger key as child of smaller one. */
 256       if (lo->first_child == ~0)
 257         {
 258           hi->parent = lo_i;
 259           lo->first_child = hi_i;
 260           lo->rank = 1;
 261         }
 262       else
 263         fheap_node_add_sibling (f, lo->first_child, hi_i);
 264
 265       /* Following Fredman & Trajan: "When making a root node X a child of another node in a linking step,
 266          we unmark X". */
 267       hi->is_marked = 0;
 268
 269       ni = lo_i;
 270       n = lo;
 271     }
 272 }
 273
 274 u32 fheap_del_min (fheap_t * f, u32 * min_key)
 275 {
 276   fheap_node_t * r = fheap_get_root (f);
 277   u32 to_delete_min_ri = f->min_root;
 278   u32 ri, ni;
 279
 280   /* Empty heap? */
 281   if (! r)
 282     return ~0;
 283
 284   /* Root's children become siblings.  Call this step a; see below. */
 285   if (r->first_child != ~0)
 286     {
 287       u32 ci, cni, rni;
 288       fheap_node_t * c, * cn, * rn;
 289
 290       /* Splice child & root circular lists together. */
 291       ci = r->first_child;
 292       c = vec_elt_at_index (f->nodes, ci);
 293
 294       cni = c->next_sibling;
 295       rni = r->next_sibling;
 296       cn = vec_elt_at_index (f->nodes, cni);
 297       rn = vec_elt_at_index (f->nodes, rni);
 298
 299       r->next_sibling = cni;
 300       c->next_sibling = rni;
 301       cn->prev_sibling = to_delete_min_ri;
 302       rn->prev_sibling = ci;
 303     }
 304
 305   /* Remove min root. */
 306   ri = fheap_node_remove_and_invalidate (f, to_delete_min_ri);
 307
 308   /* Find new min root from among siblings including the ones we've just added. */
 309   f->min_root = ~0;
 310   if (ri != ~0)
 311     {
 312       u32 ri_last, ri_next, i, min_ds;
 313
 314       r = fheap_get_node (f, ri);
 315       ri_last = r->prev_sibling;
 316       while (1)
 317         {
 318           /* Step a above can put children (with r->parent != ~0) on root list. */
 319           r->parent = ~0;
 320
 321           ri_next = r->next_sibling;
 322           fheap_link_root (f, ri);
 323           if (ri == ri_last)
 324             break;
 325           ri = ri_next;
 326           r = fheap_get_node (f, ri);
 327         }
 328
 329       min_ds = ~0;
 330       vec_foreach_index (i, f->root_list_by_rank)
 331         {
 332           ni = f->root_list_by_rank[i];
 333           if (ni == ~0)
 334             continue;
 335           f->root_list_by_rank[i] = ~0;
 336           r = fheap_get_node (f, ni);
 337           if (r->key < min_ds)
 338             {
 339               f->min_root = ni;
 340               min_ds = r->key;
 341               ASSERT (r->parent == ~0);
 342             }
 343         }
 344     }
 345
 346   /* Return deleted min root. */
 347   r = vec_elt_at_index (f->nodes, to_delete_min_ri);
 348   if (min_key)
 349     *min_key = r->key;
 350
 351   fheap_validate (f);
 352
 353   return to_delete_min_ri;
 354 }
 355
 356 static void fheap_mark_parent (fheap_t * f, u32 pi)
 357 {
 358   fheap_node_t * p = vec_elt_at_index (f->nodes, pi);
 359
 360   /* Parent is a root: do nothing. */
 361   if (p->parent == ~0)
 362     return;
 363
 364   /* If not marked, mark it. */
 365   if (! p->is_marked)
 366     {
 367       p->is_marked = 1;
 368       return;
 369     }
 370
 371   /* Its a previously marked, non-root parent.
 372      Cut edge to its parent and add to root list. */
 373   fheap_node_remove (f, pi);
 374   fheap_node_add_sibling (f, f->min_root, pi);
 375
 376   /* Unmark it since its now a root node. */
 377   p->is_marked = 0;
 378
 379   /* "Cascading cuts": check parent. */
 380   if (p->parent != ~0)
 381     fheap_mark_parent (f, p->parent);
 382 }
 383
 384 /* Set key to new smaller value. */
 385 void fheap_decrease_key (fheap_t * f, u32 ni, u32 new_key)
 386 {
 387   fheap_node_t * n = vec_elt_at_index (f->nodes, ni);
 388   fheap_node_t * r = fheap_get_root (f);
 389
 390   n->key = new_key;
 391
 392   if (n->parent != ~0)
 393     {
 394       fheap_mark_parent (f, n->parent);
 395
 396       /* Remove node and add to root list. */
 397       fheap_node_remove (f, ni);
 398       fheap_node_add_sibling (f, f->min_root, ni);
 399     }
 400
 401   if (n->key < r->key)
 402     f->min_root = ni;
 403
 404   fheap_validate (f);
 405 }
 406
 407 void fheap_del (fheap_t * f, u32 ni)
 408 {
 409   fheap_node_t * n;
 410
 411   n = vec_elt_at_index (f->nodes, ni);
 412
 413   if (n->parent == ~0)
 414     {
 415       ASSERT (ni == f->min_root);
 416       fheap_del_min (f, 0);
 417     }
 418   else
 419     {
 420       u32 ci;
 421
 422       fheap_mark_parent (f, n->parent);
 423
 424       /* Add children to root list. */
 425       foreach_fheap_node_sibling (f, ci, n->first_child, ({
 426         fheap_node_remove (f, ci);
 427         fheap_node_add_sibling (f, f->min_root, ci);
 428       }));
 429
 430       fheap_node_remove_and_invalidate (f, ni);
 431     }
 432
 433   fheap_validate (f);
 434 }