X-Git-Url: https://gerrit.opnfv.org/gerrit/gitweb?a=blobdiff_plain;f=src%2Fceph%2Fsrc%2Fdmclock%2Fsupport%2Fsrc%2Fheap.h;fp=src%2Fceph%2Fsrc%2Fdmclock%2Fsupport%2Fsrc%2Fheap.h;h=0000000000000000000000000000000000000000;hb=7da45d65be36d36b880cc55c5036e96c24b53f00;hp=0f4d24f7c2dc0e02f9986c2890ca3ab636426425;hpb=691462d09d0987b47e112d6ee8740375df3c51b2;p=stor4nfv.git

diff --git a/src/ceph/src/dmclock/support/src/heap.h b/src/ceph/src/dmclock/support/src/heap.h
deleted file mode 100644
index 0f4d24f..0000000
--- a/src/ceph/src/dmclock/support/src/heap.h
+++ /dev/null
@@ -1,240 +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 <ostream>
-
-#include "assert.h"
-
-
-namespace crimson {
-
-  /*
-   * T : type of data held in the heap.
-   *
-   * C : class that implements operator() with two arguments and
-   * returns a boolean when the first argument is greater than (higher
-   * in priority than) the second.
-   */
-  template<typename T, typename C>
-  class Heap {
-
-  public:
-
-    class iterator {
-
-      friend Heap<T,C>;
-
-      Heap<T,C>& heap;
-      int        index;
-
-      iterator(Heap<T,C>& _heap, int _index) :
-	heap(_heap),
-	index(_index)
-      {
-	// empty
-      }
-
-    public:
-
-      iterator(iterator&& other) :
-	heap(other.heap),
-	index(other.index)
-      {
-	// empty
-      }
-
-      iterator& operator++() {
-	++index;
-	return *this;
-      }
-
-      bool operator==(const iterator& other) const {
-	return index == other.index;
-      }
-
-      bool operator!=(const iterator& other) const {
-	return !(*this == other);
-      }
-
-      T& operator*() {
-	return heap.data[index];
-      }
-
-      // the item this iterator refers to
-      void increase() {
-	heap.siftUp(index);
-      }
-    }; // class iterator
-
-    friend iterator;
-
-  protected:
-
-    std::vector<T> data;
-    int count;
-    C comparator;
-
-    // parent(0) should be a negative value, which it is due to
-    // truncating towards negative infinity
-    static inline int parent(int i) { return (i - 1) / 2; }
-
-    static inline int lhs(int i) { return 2*i + 1; }
-
-    static inline int rhs(int i) { return 2*i + 2; }
-
-    void siftUp(int i) {
-      assert(i < count);
-
-      while (i > 0) {
-	int pi = parent(i);
-	if (!comparator(data[i], data[pi])) {
-	  break;
-	}
-
-	std::swap(data[i], data[pi]);
-	i = pi;
-      }
-    }
-
-    void siftDown(int i) {
-      while (i < count) {
-	int li = lhs(i);
-	int 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]);
-	      i = ri;
-	    } else {
-	      std::swap(data[i], data[li]);
-	      i = li;
-	    }
-	  } else if (ri < count && comparator(data[ri], data[i])) {
-	    std::swap(data[i], data[ri]);
-	    i = ri;
-	  } else {
-	    break;
-	  }
-	} else {
-	  break;
-	}
-      }
-    }
-
-
-  public:
-
-    Heap() :
-      count(0)
-    {
-      // empty
-    }
-
-    Heap(const Heap<T,C>& other) {
-      data.resize(other.data.size());
-      for (int i = 0; i < other.count; ++i) {
-	data[i] = other.data[i];
-      }
-      count = other.count;
-    }
-
-    const Heap<T,C>& operator=(const Heap<T,C>& other) {
-      data.resize(other.data.size());
-      for (int i = 0; i < other.count; ++i) {
-	data[i] = other.data[i];
-      }
-      count = other.count;
-      return *this;
-    }
-
-    bool empty() const { return 0 == count; }
-
-    T& top() { return data[0]; }
-
-    void push(T item) {
-      int i = count++;
-      data.push_back(item);
-      siftUp(i);
-    }
-
-    void pop() {
-      data[0] = data[--count];
-      data.resize(count);
-      siftDown(0);
-    }
-
-    void updateTop() {
-      siftDown(0);
-    }
-
-    void clear() {
-      count = 0;
-      data.resize(0);
-    }
-
-    iterator begin() {
-      return iterator(*this, 0);
-    }
-
-    iterator end() {
-      return iterator(*this, count);
-    }
-
-    std::ostream& displaySorted(std::ostream& out,
-				std::function<bool(const T&)> filter,
-				bool insert_line_breaks = true) const {
-      Heap<T,C> temp = *this;
-
-      bool first = true;
-      out << "[ ";
-
-      while(!temp.empty()) {
-	const T& top = temp.top();
-	if (filter(top)) {
-	  if (!first) {
-	    out << ", ";
-	  }
-	  if (insert_line_breaks) {
-	    out << std::endl << "    ";
-	  }
-	  out << temp.top();
-	  first = false;
-	}
-	temp.pop();
-      }
-
-      out << " ]";
-      if (insert_line_breaks) {
-	out << std::endl;
-      }
-      return out;
-    }
-
-    template<typename T1, typename T2>
-    friend std::ostream& operator<<(std::ostream&, const Heap<T1,T2>&);
-  }; // class Heap
-
-
-  template<typename T1, typename T2>
-  std::ostream& operator<<(std::ostream& out, const Heap<T1,T2>& h) {
-    out << "[ ";
-    if (h.count) {
-      out << h.data[0];
-    }
-    for (int i = 1; i < h.count; i++) {
-      out << ", " << h.data[i];
-    }
-    out << " ]";
-    return out;
-  }
-} // namespace