ceph/src/boost/boost/pending/relaxed_heap.hpp

   1 // Copyright 2004 The Trustees of Indiana University.
   2
   3 // Use, modification and distribution is subject to the Boost Software
   4 // License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
   5 // http://www.boost.org/LICENSE_1_0.txt)
   6
   7 //  Authors: Douglas Gregor
   8 //           Andrew Lumsdaine
   9 #ifndef BOOST_RELAXED_HEAP_HEADER
  10 #define BOOST_RELAXED_HEAP_HEADER
  11
  12 #include <functional>
  13 #include <boost/property_map/property_map.hpp>
  14 #include <boost/optional.hpp>
  15 #include <vector>
  16 #include <climits> // for CHAR_BIT
  17 #include <boost/none.hpp>
  18
  19 #ifdef BOOST_RELAXED_HEAP_DEBUG
  20 #  include <iostream>
  21 #endif // BOOST_RELAXED_HEAP_DEBUG
  22
  23 #if defined(BOOST_MSVC)
  24 #  pragma warning(push)
  25 #  pragma warning(disable:4355) // complaint about using 'this' to
  26 #endif                          // initialize a member
  27
  28 namespace boost {
  29
  30 template<typename IndexedType,
  31          typename Compare = std::less<IndexedType>,
  32          typename ID = identity_property_map>
  33 class relaxed_heap
  34 {
  35   struct group;
  36
  37   typedef relaxed_heap self_type;
  38   typedef std::size_t  rank_type;
  39
  40 public:
  41   typedef IndexedType  value_type;
  42   typedef rank_type    size_type;
  43
  44 private:
  45   /**
  46    * The kind of key that a group has. The actual values are discussed
  47    * in-depth in the documentation of the @c kind field of the @c group
  48    * structure. Note that the order of the enumerators *IS* important
  49    * and must not be changed.
  50    */
  51   enum group_key_kind { smallest_key, stored_key, largest_key };
  52
  53   struct group {
  54     explicit group(group_key_kind kind = largest_key)
  55       : kind(kind), parent(this), rank(0) { }
  56
  57     /** The value associated with this group. This value is only valid
  58      *  when @c kind!=largest_key (which indicates a deleted
  59      *  element). Note that the use of boost::optional increases the
  60      *  memory requirements slightly but does not result in extraneous
  61      *  memory allocations or deallocations. The optional could be
  62      *  eliminated when @c value_type is a model of
  63      *  DefaultConstructible.
  64      */
  65     ::boost::optional<value_type> value;
  66
  67     /**
  68      * The kind of key stored at this group. This may be @c
  69      * smallest_key, which indicates that the key is infinitely small;
  70      * @c largest_key, which indicates that the key is infinitely
  71      * large; or @c stored_key, which means that the key is unknown,
  72      * but its relationship to other keys can be determined via the
  73      * comparison function object.
  74      */
  75     group_key_kind        kind;
  76
  77     /// The parent of this group. Will only be NULL for the dummy root group
  78     group*                parent;
  79
  80     /// The rank of this group. Equivalent to the number of children in
  81     /// the group.
  82     rank_type            rank;
  83
  84     /** The children of this group. For the dummy root group, these are
  85      * the roots. This is an array of length log n containing pointers
  86      * to the child groups.
  87      */
  88     group**               children;
  89   };
  90
  91   size_type log_base_2(size_type n) // log2 is a macro on some platforms
  92   {
  93     size_type leading_zeroes = 0;
  94     do {
  95       size_type next = n << 1;
  96       if (n == (next >> 1)) {
  97         ++leading_zeroes;
  98         n = next;
  99       } else {
 100         break;
 101       }
 102     } while (true);
 103     return sizeof(size_type) * CHAR_BIT - leading_zeroes - 1;
 104   }
 105
 106 public:
 107   relaxed_heap(size_type n, const Compare& compare = Compare(),
 108                const ID& id = ID())
 109     : compare(compare), id(id), root(smallest_key), groups(n),
 110       smallest_value(0)
 111   {
 112     if (n == 0) {
 113       root.children = new group*[1];
 114       return;
 115     }
 116
 117     log_n = log_base_2(n);
 118     if (log_n == 0) log_n = 1;
 119     size_type g = n / log_n;
 120     if (n % log_n > 0) ++g;
 121     size_type log_g = log_base_2(g);
 122     size_type r = log_g;
 123
 124     // Reserve an appropriate amount of space for data structures, so
 125     // that we do not need to expand them.
 126     index_to_group.resize(g);
 127     A.resize(r + 1, 0);
 128     root.rank = r + 1;
 129     root.children = new group*[(log_g + 1) * (g + 1)];
 130     for (rank_type i = 0; i < r+1; ++i) root.children[i] = 0;
 131
 132     // Build initial heap
 133     size_type idx = 0;
 134     while (idx < g) {
 135       root.children[r] = &index_to_group[idx];
 136       idx = build_tree(root, idx, r, log_g + 1);
 137       if (idx != g)
 138         r = static_cast<size_type>(log_base_2(g-idx));
 139     }
 140   }
 141
 142   ~relaxed_heap() { delete [] root.children; }
 143
 144   void push(const value_type& x)
 145   {
 146     groups[get(id, x)] = x;
 147     update(x);
 148   }
 149
 150   void update(const value_type& x)
 151   {
 152     group* a = &index_to_group[get(id, x) / log_n];
 153     if (!a->value
 154         || *a->value == x
 155         || compare(x, *a->value)) {
 156       if (a != smallest_value) smallest_value = 0;
 157       a->kind = stored_key;
 158       a->value = x;
 159       promote(a);
 160     }
 161   }
 162
 163   void remove(const value_type& x)
 164   {
 165     group* a = &index_to_group[get(id, x) / log_n];
 166     assert(groups[get(id, x)]);
 167     a->value = x;
 168     a->kind = smallest_key;
 169     promote(a);
 170     smallest_value = a;
 171     pop();
 172   }
 173
 174   value_type& top()
 175   {
 176     find_smallest();
 177     assert(smallest_value->value != none);
 178     return *smallest_value->value;
 179   }
 180
 181   const value_type& top() const
 182   {
 183     find_smallest();
 184     assert(smallest_value->value != none);
 185     return *smallest_value->value;
 186   }
 187
 188   bool empty() const
 189   {
 190     find_smallest();
 191     return !smallest_value || (smallest_value->kind == largest_key);
 192   }
 193
 194   bool contains(const value_type& x) const {
 195     return static_cast<bool>(groups[get(id, x)]);
 196   }
 197
 198
 199   void pop()
 200   {
 201     // Fill in smallest_value. This is the group x.
 202     find_smallest();
 203     group* x = smallest_value;
 204     smallest_value = 0;
 205
 206     // Make x a leaf, giving it the smallest value within its group
 207     rank_type r = x->rank;
 208     group* p = x->parent;
 209     {
 210       assert(x->value != none);
 211
 212       // Find x's group
 213       size_type start = get(id, *x->value) - get(id, *x->value) % log_n;
 214       size_type end = start + log_n;
 215       if (end > groups.size()) end = groups.size();
 216
 217       // Remove the smallest value from the group, and find the new
 218       // smallest value.
 219       groups[get(id, *x->value)].reset();
 220       x->value.reset();
 221       x->kind = largest_key;
 222       for (size_type i = start; i < end; ++i) {
 223         if (groups[i] && (!x->value || compare(*groups[i], *x->value))) {
 224           x->kind = stored_key;
 225           x->value = groups[i];
 226         }
 227       }
 228     }
 229     x->rank = 0;
 230
 231     // Combine prior children of x with x
 232     group* y = x;
 233     for (size_type c = 0; c < r; ++c) {
 234       group* child = x->children[c];
 235       if (A[c] == child) A[c] = 0;
 236       y = combine(y, child);
 237     }
 238
 239     // If we got back something other than x, let y take x's place
 240     if (y != x) {
 241       y->parent = p;
 242       p->children[r] = y;
 243
 244       assert(r == y->rank);
 245       if (A[y->rank] == x)
 246         A[y->rank] = do_compare(y, p)? y : 0;
 247     }
 248   }
 249
 250 #ifdef BOOST_RELAXED_HEAP_DEBUG
 251   /*************************************************************************
 252    * Debugging support                                                     *
 253    *************************************************************************/
 254   void dump_tree() { dump_tree(std::cout); }
 255   void dump_tree(std::ostream& out) { dump_tree(out, &root); }
 256
 257   void dump_tree(std::ostream& out, group* p, bool in_progress = false)
 258   {
 259     if (!in_progress) {
 260       out << "digraph heap {\n"
 261           << "  edge[dir=\"back\"];\n";
 262     }
 263
 264     size_type p_index = 0;
 265     if (p != &root) while (&index_to_group[p_index] != p) ++p_index;
 266
 267     for (size_type i = 0; i < p->rank; ++i) {
 268       group* c = p->children[i];
 269       if (c) {
 270         size_type c_index = 0;
 271         if (c != &root) while (&index_to_group[c_index] != c) ++c_index;
 272
 273         out << "  ";
 274         if (p == &root) out << 'p'; else out << p_index;
 275         out << " -> ";
 276         if (c == &root) out << 'p'; else out << c_index;
 277         if (A[c->rank] == c) out << " [style=\"dotted\"]";
 278         out << ";\n";
 279         dump_tree(out, c, true);
 280
 281         // Emit node information
 282         out << "  ";
 283         if (c == &root) out << 'p'; else out << c_index;
 284         out << " [label=\"";
 285         if (c == &root) out << 'p'; else out << c_index;
 286         out << ":";
 287         size_type start = c_index * log_n;
 288         size_type end = start + log_n;
 289         if (end > groups.size()) end = groups.size();
 290         while (start != end) {
 291           if (groups[start]) {
 292             out << " " << get(id, *groups[start]);
 293             if (*groups[start] == *c->value) out << "(*)";
 294           }
 295           ++start;
 296         }
 297         out << '"';
 298
 299         if (do_compare(c, p)) {
 300           out << "  ";
 301           if (c == &root) out << 'p'; else out << c_index;
 302           out << ", style=\"filled\", fillcolor=\"gray\"";
 303         }
 304         out << "];\n";
 305       } else {
 306         assert(p->parent == p);
 307       }
 308     }
 309     if (!in_progress) out << "}\n";
 310   }
 311
 312   bool valid()
 313   {
 314     // Check that the ranks in the A array match the ranks of the
 315     // groups stored there. Also, the active groups must be the last
 316     // child of their parent.
 317     for (size_type r = 0; r < A.size(); ++r) {
 318       if (A[r] && A[r]->rank != r) return false;
 319
 320       if (A[r] && A[r]->parent->children[A[r]->parent->rank-1] != A[r])
 321         return false;
 322     }
 323
 324     // The root must have no value and a key of -Infinity
 325     if (root.kind != smallest_key) return false;
 326
 327     return valid(&root);
 328   }
 329
 330   bool valid(group* p)
 331   {
 332     for (size_type i = 0; i < p->rank; ++i) {
 333       group* c = p->children[i];
 334       if (c) {
 335         // Check link structure
 336         if (c->parent != p) return false;
 337         if (c->rank != i) return false;
 338
 339         // A bad group must be active
 340         if (do_compare(c, p) && A[i] != c) return false;
 341
 342         // Check recursively
 343         if (!valid(c)) return false;
 344       } else {
 345         // Only the root may
 346         if (p != &root) return false;
 347       }
 348     }
 349     return true;
 350   }
 351
 352 #endif // BOOST_RELAXED_HEAP_DEBUG
 353
 354 private:
 355   size_type
 356   build_tree(group& parent, size_type idx, size_type r, size_type max_rank)
 357   {
 358     group& this_group = index_to_group[idx];
 359     this_group.parent = &parent;
 360     ++idx;
 361
 362     this_group.children = root.children + (idx * max_rank);
 363     this_group.rank = r;
 364     for (size_type i = 0; i < r; ++i) {
 365       this_group.children[i] = &index_to_group[idx];
 366       idx = build_tree(this_group, idx, i, max_rank);
 367     }
 368     return idx;
 369   }
 370
 371   void find_smallest() const
 372   {
 373     group** roots = root.children;
 374
 375     if (!smallest_value) {
 376       std::size_t i;
 377       for (i = 0; i < root.rank; ++i) {
 378         if (roots[i] &&
 379             (!smallest_value || do_compare(roots[i], smallest_value))) {
 380           smallest_value = roots[i];
 381         }
 382       }
 383       for (i = 0; i < A.size(); ++i) {
 384         if (A[i] && (!smallest_value || do_compare(A[i], smallest_value)))
 385           smallest_value = A[i];
 386       }
 387     }
 388   }
 389
 390   bool do_compare(group* x, group* y) const
 391   {
 392     return (x->kind < y->kind
 393             || (x->kind == y->kind
 394                 && x->kind == stored_key
 395                 && compare(*x->value, *y->value)));
 396   }
 397
 398   void promote(group* a)
 399   {
 400     assert(a != 0);
 401     rank_type r = a->rank;
 402     group* p = a->parent;
 403     assert(p != 0);
 404     if (do_compare(a, p)) {
 405       // s is the rank + 1 sibling
 406       group* s = p->rank > r + 1? p->children[r + 1] : 0;
 407
 408       // If a is the last child of p
 409       if (r == p->rank - 1) {
 410         if (!A[r]) A[r] = a;
 411         else if (A[r] != a) pair_transform(a);
 412       } else {
 413         assert(s != 0);
 414         if (A[r + 1] == s) active_sibling_transform(a, s);
 415         else good_sibling_transform(a, s);
 416       }
 417     }
 418   }
 419
 420   group* combine(group* a1, group* a2)
 421   {
 422     assert(a1->rank == a2->rank);
 423     if (do_compare(a2, a1)) do_swap(a1, a2);
 424     a1->children[a1->rank++] = a2;
 425     a2->parent = a1;
 426     clean(a1);
 427     return a1;
 428   }
 429
 430   void clean(group* q)
 431   {
 432     if (2 > q->rank) return;
 433     group* qp = q->children[q->rank-1];
 434     rank_type s = q->rank - 2;
 435     group* x = q->children[s];
 436     group* xp = qp->children[s];
 437     assert(s == x->rank);
 438
 439     // If x is active, swap x and xp
 440     if (A[s] == x) {
 441       q->children[s] = xp;
 442       xp->parent = q;
 443       qp->children[s] = x;
 444       x->parent = qp;
 445     }
 446   }
 447
 448   void pair_transform(group* a)
 449   {
 450 #if defined(BOOST_RELAXED_HEAP_DEBUG) && BOOST_RELAXED_HEAP_DEBUG > 1
 451     std::cerr << "- pair transform\n";
 452 #endif
 453     rank_type r = a->rank;
 454
 455     // p is a's parent
 456     group* p = a->parent;
 457     assert(p != 0);
 458
 459     // g is p's parent (a's grandparent)
 460     group* g = p->parent;
 461     assert(g != 0);
 462
 463     // a' <- A(r)
 464     assert(A[r] != 0);
 465     group* ap = A[r];
 466     assert(ap != 0);
 467
 468     // A(r) <- nil
 469     A[r] = 0;
 470
 471     // let a' have parent p'
 472     group* pp = ap->parent;
 473     assert(pp != 0);
 474
 475     // let a' have grandparent g'
 476     group* gp = pp->parent;
 477     assert(gp != 0);
 478
 479     // Remove a and a' from their parents
 480     assert(ap == pp->children[pp->rank-1]); // Guaranteed because ap is active
 481     --pp->rank;
 482
 483     // Guaranteed by caller
 484     assert(a == p->children[p->rank-1]);
 485     --p->rank;
 486
 487     // Note: a, ap, p, pp all have rank r
 488     if (do_compare(pp, p)) {
 489       do_swap(a, ap);
 490       do_swap(p, pp);
 491       do_swap(g, gp);
 492     }
 493
 494     // Assuming k(p) <= k(p')
 495     // make p' the rank r child of p
 496     assert(r == p->rank);
 497     p->children[p->rank++] = pp;
 498     pp->parent = p;
 499
 500     // Combine a, ap into a rank r+1 group c
 501     group* c = combine(a, ap);
 502
 503     // make c the rank r+1 child of g'
 504     assert(gp->rank > r+1);
 505     gp->children[r+1] = c;
 506     c->parent = gp;
 507
 508 #if defined(BOOST_RELAXED_HEAP_DEBUG) && BOOST_RELAXED_HEAP_DEBUG > 1
 509     std::cerr << "After pair transform...\n";
 510     dump_tree();
 511 #endif
 512
 513     if (A[r+1] == pp) A[r+1] = c;
 514     else promote(c);
 515   }
 516
 517   void active_sibling_transform(group* a, group* s)
 518   {
 519 #if defined(BOOST_RELAXED_HEAP_DEBUG) && BOOST_RELAXED_HEAP_DEBUG > 1
 520     std::cerr << "- active sibling transform\n";
 521 #endif
 522     group* p = a->parent;
 523     group* g = p->parent;
 524
 525     // remove a, s from their parents
 526     assert(s->parent == p);
 527     assert(p->children[p->rank-1] == s);
 528     --p->rank;
 529     assert(p->children[p->rank-1] == a);
 530     --p->rank;
 531
 532     rank_type r = a->rank;
 533     A[r+1] = 0;
 534     a = combine(p, a);
 535     group* c = combine(a, s);
 536
 537     // make c the rank r+2 child of g
 538     assert(g->children[r+2] == p);
 539     g->children[r+2] = c;
 540     c->parent = g;
 541     if (A[r+2] == p) A[r+2] = c;
 542     else promote(c);
 543   }
 544
 545   void good_sibling_transform(group* a, group* s)
 546   {
 547 #if defined(BOOST_RELAXED_HEAP_DEBUG) && BOOST_RELAXED_HEAP_DEBUG > 1
 548     std::cerr << "- good sibling transform\n";
 549 #endif
 550     rank_type r = a->rank;
 551     group* c = s->children[s->rank-1];
 552     assert(c->rank == r);
 553     if (A[r] == c) {
 554 #if defined(BOOST_RELAXED_HEAP_DEBUG) && BOOST_RELAXED_HEAP_DEBUG > 1
 555       std::cerr << "- good sibling pair transform\n";
 556 #endif
 557       A[r] = 0;
 558       group* p = a->parent;
 559
 560       // Remove c from its parent
 561       --s->rank;
 562
 563       // Make s the rank r child of p
 564       s->parent = p;
 565       p->children[r] = s;
 566
 567       // combine a, c and let the result by the rank r+1 child of p
 568       assert(p->rank > r+1);
 569       group* x = combine(a, c);
 570       x->parent = p;
 571       p->children[r+1] = x;
 572
 573       if (A[r+1] == s) A[r+1] = x;
 574       else promote(x);
 575
 576 #if defined(BOOST_RELAXED_HEAP_DEBUG) && BOOST_RELAXED_HEAP_DEBUG > 1
 577       dump_tree(std::cerr);
 578 #endif
 579       //      pair_transform(a);
 580     } else {
 581       // Clean operation
 582       group* p = a->parent;
 583       s->children[r] = a;
 584       a->parent = s;
 585       p->children[r] = c;
 586       c->parent = p;
 587
 588       promote(a);
 589     }
 590   }
 591
 592   static void do_swap(group*& x, group*& y)
 593   {
 594     group* tmp = x;
 595     x = y;
 596     y = tmp;
 597   }
 598
 599   /// Function object that compares two values in the heap
 600   Compare compare;
 601
 602   /// Mapping from values to indices in the range [0, n).
 603   ID id;
 604
 605   /** The root group of the queue. This group is special because it will
 606    *  never store a value, but it acts as a parent to all of the
 607    *  roots. Thus, its list of children is the list of roots.
 608    */
 609   group root;
 610
 611   /** Mapping from the group index of a value to the group associated
 612    *  with that value. If a value is not in the queue, then the "value"
 613    *  field will be empty.
 614    */
 615   std::vector<group> index_to_group;
 616
 617   /** Flat data structure containing the values in each of the
 618    *  groups. It will be indexed via the id of the values. The groups
 619    *  are each log_n long, with the last group potentially being
 620    *  smaller.
 621    */
 622   std::vector< ::boost::optional<value_type> > groups;
 623
 624   /** The list of active groups, indexed by rank. When A[r] is null,
 625    *  there is no active group of rank r. Otherwise, A[r] is the active
 626    *  group of rank r.
 627    */
 628   std::vector<group*> A;
 629
 630   /** The group containing the smallest value in the queue, which must
 631    *  be either a root or an active group. If this group is null, then we
 632    *  will need to search for this group when it is needed.
 633    */
 634   mutable group* smallest_value;
 635
 636   /// Cached value log_base_2(n)
 637   size_type log_n;
 638 };
 639
 640
 641 } // end namespace boost
 642
 643 #if defined(BOOST_MSVC)
 644 #  pragma warning(pop)
 645 #endif
 646
 647 #endif // BOOST_RELAXED_HEAP_HEADER