remove ceph code

[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
deleted file mode 100644 (file)
index 291e579..0000000
--- a/src/ceph/src/dmclock/support/src/intrusive_heap.h
+++ /dev/null
@@ -1,214 +0,0 @@
-// -*- 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