src/ceph/src/dmclock/support/src/indirect_intrusive_heap.h

   1 // -*- mode:C++; tab-width:8; c-basic-offset:2; indent-tabs-mode:t -*-
   2 // vim: ts=8 sw=2 smarttab
   3
   4 /*
   5  * Copyright (C) 2016 Red Hat Inc.
   6  */
   7
   8
   9 #pragma once
  10
  11
  12 #include <memory>
  13 #include <vector>
  14 #include <string>
  15 #include <iostream>
  16 #include <functional>
  17 #include <algorithm>
  18
  19 #include "assert.h"
  20
  21
  22 namespace crimson {
  23   using IndIntruHeapData = size_t;
  24
  25   /* T is the ultimate data that's being stored in the heap, although
  26    *   through indirection.
  27    *
  28    * I is the indirect type that will actually be stored in the heap
  29    *   and that must allow dereferencing (via operator*) to yield a
  30    *   T&.
  31    *
  32    * C is a functor when given two T&'s will return true if the first
  33    *   must precede the second.
  34    *
  35    * heap_info is a data member pointer as to where the heap data in T
  36    * is stored.
  37    *
  38    * K is the branching factor of the heap, default is 2 (binary heap).
  39    */
  40   template<typename I,
  41            typename T,
  42            IndIntruHeapData T::*heap_info,
  43            typename C,
  44            uint K = 2>
  45   class IndIntruHeap {
  46
  47     // shorthand
  48     using HeapIndex = IndIntruHeapData;
  49
  50     static_assert(
  51       std::is_same<T,typename std::pointer_traits<I>::element_type>::value,
  52       "class I must resolve to class T by indirection (pointer dereference)");
  53
  54     static_assert(
  55       std::is_same<bool,
  56       typename std::result_of<C(const T&,const T&)>::type>::value,
  57       "class C must define operator() to take two const T& and return a bool");
  58
  59     static_assert(K >= 2, "K (degree of branching) must be at least 2");
  60
  61     class Iterator {
  62       friend IndIntruHeap<I, T, heap_info, C, K>;
  63
  64       IndIntruHeap<I, T, heap_info, C, K>& heap;
  65       HeapIndex                            index;
  66
  67       Iterator(IndIntruHeap<I, T, heap_info, C, K>& _heap, HeapIndex _index) :
  68         heap(_heap),
  69         index(_index)
  70       {
  71         // empty
  72       }
  73
  74     public:
  75
  76       Iterator(Iterator&& other) :
  77         heap(other.heap),
  78         index(other.index)
  79       {
  80         // empty
  81       }
  82
  83       Iterator(const Iterator& other) :
  84         heap(other.heap),
  85         index(other.index)
  86       {
  87         // empty
  88       }
  89
  90       Iterator& operator=(Iterator&& other) {
  91         std::swap(heap, other.heap);
  92         std::swap(index, other.index);
  93         return *this;
  94       }
  95
  96       Iterator& operator=(const Iterator& other) {
  97         heap = other.heap;
  98         index = other.index;
  99       }
 100
 101       Iterator& operator++() {
 102         if (index <= heap.count) {
 103           ++index;
 104         }
 105         return *this;
 106       }
 107
 108       bool operator==(const Iterator& other) const {
 109         return &heap == &other.heap && index == other.index;
 110       }
 111
 112       bool operator!=(const Iterator& other) const {
 113         return !(*this == other);
 114       }
 115
 116       T& operator*() {
 117         return *heap.data[index];
 118       }
 119
 120       T* operator->() {
 121         return &(*heap.data[index]);
 122       }
 123
 124 #if 0
 125       // the item this iterator refers to
 126       void increase() {
 127         heap.sift_up(index);
 128       }
 129 #endif
 130     }; // class Iterator
 131
 132
 133     class ConstIterator {
 134       friend IndIntruHeap<I, T, heap_info, C, K>;
 135
 136       const IndIntruHeap<I, T, heap_info, C, K>& heap;
 137       HeapIndex                                  index;
 138
 139       ConstIterator(const IndIntruHeap<I, T, heap_info, C, K>& _heap,
 140                     HeapIndex _index) :
 141         heap(_heap),
 142         index(_index)
 143       {
 144         // empty
 145       }
 146
 147     public:
 148
 149       ConstIterator(ConstIterator&& other) :
 150         heap(other.heap),
 151         index(other.index)
 152       {
 153         // empty
 154       }
 155
 156       ConstIterator(const ConstIterator& other) :
 157         heap(other.heap),
 158         index(other.index)
 159       {
 160         // empty
 161       }
 162
 163       ConstIterator& operator=(ConstIterator&& other) {
 164         std::swap(heap, other.heap);
 165         std::swap(index, other.index);
 166         return *this;
 167       }
 168
 169       ConstIterator& operator=(const ConstIterator& other) {
 170         heap = other.heap;
 171         index = other.index;
 172       }
 173
 174       ConstIterator& operator++() {
 175         if (index <= heap.count) {
 176           ++index;
 177         }
 178         return *this;
 179       }
 180
 181       bool operator==(const ConstIterator& other) const {
 182         return &heap == &other.heap && index == other.index;
 183       }
 184
 185       bool operator!=(const ConstIterator& other) const {
 186         return !(*this == other);
 187       }
 188
 189       const T& operator*() {
 190         return *heap.data[index];
 191       }
 192
 193       const T* operator->() {
 194         return &(*heap.data[index]);
 195       }
 196     }; // class ConstIterator
 197
 198
 199   protected:
 200
 201     std::vector<I> data;
 202     HeapIndex      count;
 203     C              comparator;
 204
 205   public:
 206
 207     IndIntruHeap() :
 208       count(0)
 209     {
 210       // empty
 211     }
 212
 213     IndIntruHeap(const IndIntruHeap<I,T,heap_info,C,K>& other) :
 214       count(other.count)
 215     {
 216       for (HeapIndex i = 0; i < other.count; ++i) {
 217         data.push_back(other.data[i]);
 218       }
 219     }
 220
 221     bool empty() const { return 0 == count; }
 222
 223     size_t size() const { return (size_t) count; }
 224
 225     T& top() { return *data[0]; }
 226
 227     const T& top() const { return *data[0]; }
 228
 229     I& top_ind() { return data[0]; }
 230
 231     const I& top_ind() const { return data[0]; }
 232
 233     void push(I&& item) {
 234       HeapIndex i = count++;
 235       intru_data_of(item) = i;
 236       data.emplace_back(std::move(item));
 237       sift_up(i);
 238     }
 239
 240     void push(const I& item) {
 241       I copy(item);
 242       push(std::move(copy));
 243     }
 244
 245     void pop() {
 246       remove(HeapIndex(0));
 247     }
 248
 249     void remove(Iterator& i) {
 250       remove(i.index);
 251       i = end();
 252     }
 253
 254     Iterator find(const I& ind_item) {
 255       for (HeapIndex i = 0; i < count; ++i) {
 256         if (data[i] == ind_item) {
 257           return Iterator(*this, i);
 258         }
 259       }
 260       return end();
 261     }
 262
 263     // when passing in value we do a comparison via operator==
 264     Iterator find(const T& item) {
 265       for (HeapIndex i = 0; i < count; ++i) {
 266         if (*data[i] == item) {
 267           return Iterator(*this, i);
 268         }
 269       }
 270       return end();
 271     }
 272
 273     // reverse find -- start looking from bottom of heap
 274     Iterator rfind(const I& ind_item) {
 275       // HeapIndex is unsigned, so we can't allow to go negative; so
 276       // we'll keep it one more than actual index
 277       for (HeapIndex i = count; i > 0; --i) {
 278         if (data[i-1] == ind_item) {
 279           return Iterator(*this, i-1);
 280         }
 281       }
 282       return end();
 283     }
 284
 285     // reverse find -- start looking from bottom of heap
 286     Iterator rfind(const T& item) {
 287       // HeapIndex is unsigned, so we can't allow to go negative; so
 288       // we'll keep it one more than actual index
 289       for (HeapIndex i = count; i > 0; --i) {
 290         if (*data[i-1] == item) {
 291           return Iterator(*this, i-1);
 292         }
 293       }
 294       return end();
 295     }
 296
 297     ConstIterator find(const I& ind_item) const {
 298       for (HeapIndex i = 0; i < count; ++i) {
 299         if (data[i] == ind_item) {
 300           return ConstIterator(*this, i);
 301         }
 302       }
 303       return cend();
 304     }
 305
 306     // when passing in value we do a comparison via operator==
 307     ConstIterator find(const T& item) const {
 308       for (HeapIndex i = 0; i < count; ++i) {
 309         if (*data[i] == item) {
 310           return ConstIterator(*this, i);
 311         }
 312       }
 313       return cend();
 314     }
 315
 316     // reverse find -- start looking from bottom of heap
 317     ConstIterator rfind(const I& ind_item) const {
 318       // HeapIndex is unsigned, so we can't allow to go negative; so
 319       // we'll keep it one more than actual index
 320       for (HeapIndex i = count; i > 0; --i) {
 321         if (data[i-1] == ind_item) {
 322           return ConstIterator(*this, i-1);
 323         }
 324       }
 325       return cend();
 326     }
 327
 328     // reverse find -- start looking from bottom of heap
 329     ConstIterator rfind(const T& item) const {
 330       // HeapIndex is unsigned, so we can't allow to go negative; so
 331       // we'll keep it one more than actual index
 332       for (HeapIndex i = count; i > 0; --i) {
 333         if (*data[i-1] == item) {
 334           return ConstIterator(*this, i-1);
 335         }
 336       }
 337       return cend();
 338     }
 339
 340     void promote(T& item) {
 341       sift_up(item.*heap_info);
 342     }
 343
 344     void demote(T& item) {
 345       sift_down(item.*heap_info);
 346     }
 347
 348     void adjust(T& item) {
 349       sift(item.*heap_info);
 350     }
 351
 352     Iterator begin() {
 353       return Iterator(*this, 0);
 354     }
 355
 356     Iterator end() {
 357       return Iterator(*this, count);
 358     }
 359
 360     ConstIterator cbegin() const {
 361       return ConstIterator(*this, 0);
 362     }
 363
 364     ConstIterator cend() const {
 365       return ConstIterator(*this, count);
 366     }
 367
 368     friend std::ostream& operator<<(std::ostream& out, const IndIntruHeap& h) {
 369       auto i = h.data.cbegin();
 370       if (i != h.data.cend()) {
 371         out << **i;
 372         ++i;
 373         while (i != h.data.cend()) {
 374           out << ", " << **i;
 375         }
 376       }
 377       return out;
 378     }
 379
 380     // can only be called if I is copyable; copies heap into a vector
 381     // and sorts it before displaying it
 382     std::ostream&
 383     display_sorted(std::ostream& out,
 384                    std::function<bool(const T&)> filter = all_filter) const {
 385       static_assert(std::is_copy_constructible<I>::value,
 386                     "cannot call display_sorted when class I is not copy"
 387                     " constructible");
 388       auto compare = [this] (const I first, const I second) -> bool {
 389         return this->comparator(*first, *second);
 390       };
 391       std::vector<I> copy(data);
 392       std::sort(copy.begin(), copy.end(), compare);
 393
 394       bool first = true;
 395       for (auto c = copy.begin(); c != copy.end(); ++c) {
 396         if (filter(**c)) {
 397           if (!first) {
 398             out << ", ";
 399           } else {
 400             first = false;
 401           }
 402           out << **c;
 403         }
 404       }
 405
 406       return out;
 407     }
 408
 409
 410   protected:
 411
 412     static IndIntruHeapData& intru_data_of(I& item) {
 413       return (*item).*heap_info;
 414     }
 415
 416     void remove(HeapIndex i) {
 417       std::swap(data[i], data[--count]);
 418       intru_data_of(data[i]) = i;
 419       data.pop_back();
 420
 421       // the following needs to be sift (and not sift_down) as it can
 422       // go up or down the heap; imagine the heap vector contains 0,
 423       // 10, 100, 20, 30, 200, 300, 40; then 200 is removed, and 40
 424       // would have to be sifted upwards
 425       // sift(i);
 426       sift(i);
 427     }
 428
 429     // default value of filter parameter to display_sorted
 430     static bool all_filter(const T& data) { return true; }
 431
 432     // when i is negative?
 433     static inline HeapIndex parent(HeapIndex i) {
 434       assert(0 != i);
 435       return (i - 1) / K;
 436     }
 437
 438     // index of left child when K==2, index of left-most child when K>2
 439     static inline HeapIndex lhs(HeapIndex i) { return K*i + 1; }
 440
 441     // index of right child when K==2, index of right-most child when K>2
 442     static inline HeapIndex rhs(HeapIndex i) { return K*i + K; }
 443
 444     void sift_up(HeapIndex i) {
 445       while (i > 0) {
 446         HeapIndex pi = parent(i);
 447         if (!comparator(*data[i], *data[pi])) {
 448           break;
 449         }
 450
 451         std::swap(data[i], data[pi]);
 452         intru_data_of(data[i]) = i;
 453         intru_data_of(data[pi]) = pi;
 454         i = pi;
 455       }
 456     } // sift_up
 457
 458     // use this sift_down definition when K>2; it's more general and
 459     // uses a loop; EnableBool insures template uses a template
 460     // parameter
 461     template<bool EnableBool=true>
 462     typename std::enable_if<(K>2)&&EnableBool,void>::type sift_down(HeapIndex i) {
 463       if (i >= count) return;
 464       while (true) {
 465         HeapIndex li = lhs(i);
 466
 467         if (li < count) {
 468           HeapIndex ri = std::min(rhs(i), count - 1);
 469
 470           // find the index of min. child
 471           HeapIndex min_i = li;
 472           for (HeapIndex k = li + 1; k <= ri; ++k) {
 473             if (comparator(*data[k], *data[min_i])) {
 474               min_i = k;
 475             }
 476           }
 477
 478           if (comparator(*data[min_i], *data[i])) {
 479             std::swap(data[i], data[min_i]);
 480             intru_data_of(data[i]) = i;
 481             intru_data_of(data[min_i]) = min_i;
 482             i = min_i;
 483           } else {
 484             // no child is smaller
 485             break;
 486           }
 487         } else {
 488           // no children
 489           break;
 490         }
 491       }
 492     } // sift_down
 493
 494     // use this sift_down definition when K==2; EnableBool insures
 495     // template uses a template parameter
 496     template<bool EnableBool=true>
 497     typename std::enable_if<K==2&&EnableBool,void>::type sift_down(HeapIndex i) {
 498       if (i >= count) return;
 499       while (true) {
 500         const HeapIndex li = lhs(i);
 501         const HeapIndex ri = 1 + li;
 502
 503         if (li < count) {
 504           if (comparator(*data[li], *data[i])) {
 505             if (ri < count && comparator(*data[ri], *data[li])) {
 506               std::swap(data[i], data[ri]);
 507               intru_data_of(data[i]) = i;
 508               intru_data_of(data[ri]) = ri;
 509               i = ri;
 510             } else {
 511               std::swap(data[i], data[li]);
 512               intru_data_of(data[i]) = i;
 513               intru_data_of(data[li]) = li;
 514               i = li;
 515             }
 516           } else if (ri < count && comparator(*data[ri], *data[i])) {
 517             std::swap(data[i], data[ri]);
 518             intru_data_of(data[i]) = i;
 519             intru_data_of(data[ri]) = ri;
 520             i = ri;
 521           } else {
 522             // no child is smaller
 523             break;
 524           }
 525         } else {
 526           // no children
 527           break;
 528         }
 529       } // while
 530     } // sift_down
 531
 532     void sift(HeapIndex i) {
 533       if (i == 0) {
 534         // if we're at top, can only go down
 535         sift_down(i);
 536       } else {
 537         HeapIndex pi = parent(i);
 538         if (comparator(*data[i], *data[pi])) {
 539           // if we can go up, we will
 540           sift_up(i);
 541         } else {
 542           // otherwise we'll try to go down
 543           sift_down(i);
 544         }
 545       }
 546     } // sift
 547   }; // class IndIntruHeap
 548
 549 } // namespace crimson