ceph/src/dmclock/support/src/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 <vector>
  13 #include <string>
  14 #include <iostream>
  15 #include <functional>
  16
  17 #include "assert.h"
  18
  19
  20 namespace crimson {
  21   using IntruHeapData = size_t;
  22
  23   // T = type of data in heap; I = functor that returns a non-const
  24   // reference to IntruHeapData; C = functor that compares two const
  25   // refs and return true if the first precedes the second
  26   template<typename T, typename I, typename C>
  27   class IntruHeap {
  28
  29     static_assert(
  30       std::is_same<IntruHeapData&,typename std::result_of<I(T&)>::type>::value,
  31       "class I must define operator() to take T& and return a IntruHeapData&.");
  32
  33     static_assert(
  34       std::is_same<bool,typename std::result_of<C(const T&,const T&)>::type>::value,
  35       "class C must define operator() to take two const T& and return a bool.");
  36
  37
  38   protected:
  39     using index_t = IntruHeapData;
  40
  41     std::vector<T> data;
  42     index_t count;
  43     I intru_data_of;
  44     C comparator;
  45
  46   public:
  47
  48     IntruHeap() :
  49       count(0)
  50     {
  51       // empty
  52     }
  53
  54     IntruHeap(const IntruHeap<T,I,C>& other) :
  55       count(other.count)
  56     {
  57       for (uint i = 0; i < other.count; ++i) {
  58         data.push_back(other.data[i]);
  59       }
  60     }
  61
  62     bool empty() const { return 0 == count; }
  63
  64     T& top() { return data[0]; }
  65
  66     void push(T&& item) {
  67       index_t i = count++;
  68       intru_data_of(item) = i;
  69       data.emplace_back(item);
  70       sift_up(i);
  71     }
  72
  73     void push(const T& item) {
  74       T copy(item);
  75       push(std::move(copy));
  76     }
  77
  78     void pop() {
  79       std::swap(data[0], data[--count]);
  80       intru_data_of(data[0]) = 0;
  81       data.pop_back();
  82       sift_down(0);
  83     }
  84
  85     void adjust_up(T& item) {
  86       sift_up(intru_data_of(item));
  87     }
  88
  89     void adjust_down(T& item) {
  90       sift_down(intru_data_of(item));
  91     }
  92
  93     void adjust(T& item) {
  94       sift(intru_data_of(item));
  95     }
  96
  97     friend std::ostream& operator<<(std::ostream& out, const IntruHeap& h) {
  98       for (uint i = 0; i < h.count; ++i) {
  99         out << h.data[i] << ", ";
 100       }
 101       return out;
 102     }
 103
 104     std::ostream&
 105     display_sorted(std::ostream& out,
 106                    bool insert_line_breaks = true,
 107                    std::function<bool(const T&)> filter = all_filter) const {
 108       IntruHeap<T,I,C> copy = *this;
 109
 110       bool first = true;
 111       out << "[ ";
 112
 113       while(!copy.empty()) {
 114         const T& top = copy.top();
 115         if (filter(top)) {
 116           if (!first) {
 117             out << ", ";
 118           }
 119           if (insert_line_breaks) {
 120             out << std::endl << "    ";
 121           }
 122           out << copy.top();
 123           first = false;
 124         }
 125         copy.pop();
 126       }
 127
 128       out << " ]";
 129       if (insert_line_breaks) {
 130         out << std::endl;
 131       }
 132
 133       return out;
 134     }
 135
 136
 137   protected:
 138
 139     // default value of filter parameter to display_sorted
 140     static bool all_filter(const T& data) { return true; }
 141
 142     // when i is negative?
 143     static inline index_t parent(index_t i) {
 144       assert(0 != i);
 145       return (i - 1) / 2;
 146     }
 147
 148     static inline index_t lhs(index_t i) { return 2*i + 1; }
 149
 150     static inline index_t rhs(index_t i) { return 2*i + 2; }
 151
 152     void sift_up(index_t i) {
 153       while (i > 0) {
 154         index_t pi = parent(i);
 155         if (!comparator(data[i], data[pi])) {
 156           break;
 157         }
 158
 159         std::swap(data[i], data[pi]);
 160         intru_data_of(data[i]) = i;
 161         intru_data_of(data[pi]) = pi;
 162         i = pi;
 163       }
 164     } // sift_up
 165
 166     void sift_down(index_t i) {
 167       while (i < count) {
 168         index_t li = lhs(i);
 169         index_t ri = rhs(i);
 170
 171         if (li < count) {
 172           if (comparator(data[li], data[i])) {
 173             if (ri < count && comparator(data[ri], data[li])) {
 174               std::swap(data[i], data[ri]);
 175               intru_data_of(data[i]) = i;
 176               intru_data_of(data[ri]) = ri;
 177               i = ri;
 178             } else {
 179               std::swap(data[i], data[li]);
 180               intru_data_of(data[i]) = i;
 181               intru_data_of(data[li]) = li;
 182               i = li;
 183             }
 184           } else if (ri < count && comparator(data[ri], data[i])) {
 185             std::swap(data[i], data[ri]);
 186             intru_data_of(data[i]) = i;
 187             intru_data_of(data[ri]) = ri;
 188             i = ri;
 189           } else {
 190             break;
 191           }
 192         } else {
 193           break;
 194         }
 195       }
 196     } // sift_down
 197
 198     void sift(index_t i) {
 199       if (i == 0) {
 200         // if we're at top, can only go down
 201         sift_down(i);
 202       } else {
 203         index_t pi = parent(i);
 204         if (comparator(data[i], data[pi])) {
 205           // if we can go up, we will
 206           sift_up(i);
 207         } else {
 208           // otherwise we'll try to go down
 209           sift_down(i);
 210         }
 211       }
 212     } // sift
 213   }; // class IntruHeap
 214 } // namespace crimson