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