initial code repo

[stor4nfv.git] / src / ceph / src / dmclock / support / src / intrusive_heap.h

diff --git a/src/ceph/src/dmclock/support/src/intrusive_heap.h b/src/ceph/src/dmclock/support/src/intrusive_heap.h
new file mode 100644 (file)
index 0000000..291e579
--- /dev/null
+++ b/src/ceph/src/dmclock/support/src/intrusive_heap.h
@@ -0,0 +1,214 @@
+// -*- mode:C++; tab-width:8; c-basic-offset:2; indent-tabs-mode:t -*-
+// vim: ts=8 sw=2 smarttab
+
+/*
+ * Copyright (C) 2016 Red Hat Inc.
+ */
+
+
+#pragma once
+
+
+#include <vector>
+#include <string>
+#include <iostream>
+#include <functional>
+
+#include "assert.h"
+
+
+namespace crimson {
+  using IntruHeapData = size_t;
+
+  // T = type of data in heap; I = functor that returns a non-const
+  // reference to IntruHeapData; C = functor that compares two const
+  // refs and return true if the first precedes the second
+  template<typename T, typename I, typename C>
+  class IntruHeap {
+
+    static_assert(
+      std::is_same<IntruHeapData&,typename std::result_of<I(T&)>::type>::value,
+      "class I must define operator() to take T& and return a IntruHeapData&.");
+
+    static_assert(
+      std::is_same<bool,typename std::result_of<C(const T&,const T&)>::type>::value,
+      "class C must define operator() to take two const T& and return a bool.");
+
+
+  protected:
+    using index_t = IntruHeapData;
+
+    std::vector<T> data;
+    index_t count;
+    I intru_data_of;
+    C comparator;
+
+  public:
+
+    IntruHeap() :
+      count(0)
+    {
+      // empty
+    }
+
+    IntruHeap(const IntruHeap<T,I,C>& other) :
+      count(other.count)
+    {
+      for (uint i = 0; i < other.count; ++i) {
+       data.push_back(other.data[i]);
+      }
+    }
+
+    bool empty() const { return 0 == count; }
+
+    T& top() { return data[0]; }
+
+    void push(T&& item) {
+      index_t i = count++;
+      intru_data_of(item) = i;
+      data.emplace_back(item);
+      sift_up(i);
+    }
+
+    void push(const T& item) {
+      T copy(item);
+      push(std::move(copy));
+    }
+
+    void pop() {
+      std::swap(data[0], data[--count]);
+      intru_data_of(data[0]) = 0;
+      data.pop_back();
+      sift_down(0);
+    }
+
+    void adjust_up(T& item) {
+      sift_up(intru_data_of(item));
+    }
+
+    void adjust_down(T& item) {
+      sift_down(intru_data_of(item));
+    }
+
+    void adjust(T& item) {
+      sift(intru_data_of(item));
+    }
+
+    friend std::ostream& operator<<(std::ostream& out, const IntruHeap& h) {
+      for (uint i = 0; i < h.count; ++i) {
+       out << h.data[i] << ", ";
+      }
+      return out;
+    }
+
+    std::ostream&
+    display_sorted(std::ostream& out,
+                  bool insert_line_breaks = true,
+                  std::function<bool(const T&)> filter = all_filter) const {
+      IntruHeap<T,I,C> copy = *this;
+
+      bool first = true;
+      out << "[ ";
+
+      while(!copy.empty()) {
+       const T& top = copy.top();
+       if (filter(top)) {
+         if (!first) {
+           out << ", ";
+         }
+         if (insert_line_breaks) {
+           out << std::endl << "    ";
+         }
+         out << copy.top();
+         first = false;
+       }
+       copy.pop();
+      }
+
+      out << " ]";
+      if (insert_line_breaks) {
+       out << std::endl;
+      }
+
+      return out;
+    }
+
+
+  protected:
+
+    // default value of filter parameter to display_sorted
+    static bool all_filter(const T& data) { return true; }
+
+    // when i is negative?
+    static inline index_t parent(index_t i) {
+      assert(0 != i);
+      return (i - 1) / 2;
+    }
+
+    static inline index_t lhs(index_t i) { return 2*i + 1; }
+
+    static inline index_t rhs(index_t i) { return 2*i + 2; }
+
+    void sift_up(index_t i) {
+      while (i > 0) {
+       index_t pi = parent(i);
+       if (!comparator(data[i], data[pi])) {
+         break;
+       }
+
+       std::swap(data[i], data[pi]);
+       intru_data_of(data[i]) = i;
+       intru_data_of(data[pi]) = pi;
+       i = pi;
+      }
+    } // sift_up
+
+    void sift_down(index_t i) {
+      while (i < count) {
+       index_t li = lhs(i);
+       index_t ri = rhs(i);
+
+       if (li < count) {
+         if (comparator(data[li], data[i])) {
+           if (ri < count && comparator(data[ri], data[li])) {
+             std::swap(data[i], data[ri]);
+             intru_data_of(data[i]) = i;
+             intru_data_of(data[ri]) = ri;
+             i = ri;
+           } else {
+             std::swap(data[i], data[li]);
+             intru_data_of(data[i]) = i;
+             intru_data_of(data[li]) = li;
+             i = li;
+           }
+         } else if (ri < count && comparator(data[ri], data[i])) {
+           std::swap(data[i], data[ri]);
+           intru_data_of(data[i]) = i;
+           intru_data_of(data[ri]) = ri;
+           i = ri;
+         } else {
+           break;
+         }
+       } else {
+         break;
+       }
+      }
+    } // sift_down
+
+    void sift(index_t i) {
+      if (i == 0) {
+       // if we're at top, can only go down
+       sift_down(i);
+      } else {
+       index_t pi = parent(i);
+       if (comparator(data[i], data[pi])) {
+         // if we can go up, we will
+         sift_up(i);
+       } else {
+         // otherwise we'll try to go down
+         sift_down(i);
+       }
+      }
+    } // sift
+  }; // class IntruHeap
+} // namespace crimson