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

diff --git a/src/ceph/src/dmclock/support/src/indirect_intrusive_heap.h b/src/ceph/src/dmclock/support/src/indirect_intrusive_heap.h
deleted file mode 100644
index 6342e29..0000000
--- a/src/ceph/src/dmclock/support/src/indirect_intrusive_heap.h
+++ /dev/null
@@ -1,549 +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 <memory>
-#include <vector>
-#include <string>
-#include <iostream>
-#include <functional>
-#include <algorithm>
-
-#include "assert.h"
-
-
-namespace crimson {
-  using IndIntruHeapData = size_t;
-
-  /* T is the ultimate data that's being stored in the heap, although
-   *   through indirection.
-   *
-   * I is the indirect type that will actually be stored in the heap
-   *   and that must allow dereferencing (via operator*) to yield a
-   *   T&.
-   *
-   * C is a functor when given two T&'s will return true if the first
-   *   must precede the second.
-   *
-   * heap_info is a data member pointer as to where the heap data in T
-   * is stored.
-   *
-   * K is the branching factor of the heap, default is 2 (binary heap).
-   */
-  template<typename I,
-	   typename T,
-	   IndIntruHeapData T::*heap_info,
-	   typename C,
-	   uint K = 2>
-  class IndIntruHeap {
-
-    // shorthand
-    using HeapIndex = IndIntruHeapData;
-
-    static_assert(
-      std::is_same<T,typename std::pointer_traits<I>::element_type>::value,
-      "class I must resolve to class T by indirection (pointer dereference)");
-
-    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");
-
-    static_assert(K >= 2, "K (degree of branching) must be at least 2");
-
-    class Iterator {
-      friend IndIntruHeap<I, T, heap_info, C, K>;
-
-      IndIntruHeap<I, T, heap_info, C, K>& heap;
-      HeapIndex                            index;
-
-      Iterator(IndIntruHeap<I, T, heap_info, C, K>& _heap, HeapIndex _index) :
-	heap(_heap),
-	index(_index)
-      {
-	// empty
-      }
-
-    public:
-
-      Iterator(Iterator&& other) :
-	heap(other.heap),
-	index(other.index)
-      {
-	// empty
-      }
-
-      Iterator(const Iterator& other) :
-	heap(other.heap),
-	index(other.index)
-      {
-	// empty
-      }
-
-      Iterator& operator=(Iterator&& other) {
-	std::swap(heap, other.heap);
-	std::swap(index, other.index);
-	return *this;
-      }
-
-      Iterator& operator=(const Iterator& other) {
-	heap = other.heap;
-	index = other.index;
-      }
-
-      Iterator& operator++() {
-	if (index <= heap.count) {
-	  ++index;
-	}
-	return *this;
-      }
-
-      bool operator==(const Iterator& other) const {
-	return &heap == &other.heap && index == other.index;
-      }
-
-      bool operator!=(const Iterator& other) const {
-	return !(*this == other);
-      }
-
-      T& operator*() {
-	return *heap.data[index];
-      }
-
-      T* operator->() {
-	return &(*heap.data[index]);
-      }
-
-#if 0
-      // the item this iterator refers to
-      void increase() {
-	heap.sift_up(index);
-      }
-#endif
-    }; // class Iterator
-
-
-    class ConstIterator {
-      friend IndIntruHeap<I, T, heap_info, C, K>;
-
-      const IndIntruHeap<I, T, heap_info, C, K>& heap;
-      HeapIndex                                  index;
-
-      ConstIterator(const IndIntruHeap<I, T, heap_info, C, K>& _heap,
-		    HeapIndex _index) :
-	heap(_heap),
-	index(_index)
-      {
-	// empty
-      }
-
-    public:
-
-      ConstIterator(ConstIterator&& other) :
-	heap(other.heap),
-	index(other.index)
-      {
-	// empty
-      }
-
-      ConstIterator(const ConstIterator& other) :
-	heap(other.heap),
-	index(other.index)
-      {
-	// empty
-      }
-
-      ConstIterator& operator=(ConstIterator&& other) {
-	std::swap(heap, other.heap);
-	std::swap(index, other.index);
-	return *this;
-      }
-
-      ConstIterator& operator=(const ConstIterator& other) {
-	heap = other.heap;
-	index = other.index;
-      }
-
-      ConstIterator& operator++() {
-	if (index <= heap.count) {
-	  ++index;
-	}
-	return *this;
-      }
-
-      bool operator==(const ConstIterator& other) const {
-	return &heap == &other.heap && index == other.index;
-      }
-
-      bool operator!=(const ConstIterator& other) const {
-	return !(*this == other);
-      }
-
-      const T& operator*() {
-	return *heap.data[index];
-      }
-
-      const T* operator->() {
-	return &(*heap.data[index]);
-      }
-    }; // class ConstIterator
-
-
-  protected:
-
-    std::vector<I> data;
-    HeapIndex      count;
-    C              comparator;
-
-  public:
-
-    IndIntruHeap() :
-      count(0)
-    {
-      // empty
-    }
-
-    IndIntruHeap(const IndIntruHeap<I,T,heap_info,C,K>& other) :
-      count(other.count)
-    {
-      for (HeapIndex i = 0; i < other.count; ++i) {
-	data.push_back(other.data[i]);
-      }
-    }
-
-    bool empty() const { return 0 == count; }
-
-    size_t size() const { return (size_t) count; }
-
-    T& top() { return *data[0]; }
-
-    const T& top() const { return *data[0]; }
-
-    I& top_ind() { return data[0]; }
-
-    const I& top_ind() const { return data[0]; }
-
-    void push(I&& item) {
-      HeapIndex i = count++;
-      intru_data_of(item) = i;
-      data.emplace_back(std::move(item));
-      sift_up(i);
-    }
-
-    void push(const I& item) {
-      I copy(item);
-      push(std::move(copy));
-    }
-
-    void pop() {
-      remove(HeapIndex(0));
-    }
-
-    void remove(Iterator& i) {
-      remove(i.index);
-      i = end();
-    }
-
-    Iterator find(const I& ind_item) {
-      for (HeapIndex i = 0; i < count; ++i) {
-	if (data[i] == ind_item) {
-	  return Iterator(*this, i);
-	}
-      }
-      return end();
-    }
-
-    // when passing in value we do a comparison via operator==
-    Iterator find(const T& item) {
-      for (HeapIndex i = 0; i < count; ++i) {
-	if (*data[i] == item) {
-	  return Iterator(*this, i);
-	}
-      }
-      return end();
-    }
-
-    // reverse find -- start looking from bottom of heap
-    Iterator rfind(const I& ind_item) {
-      // HeapIndex is unsigned, so we can't allow to go negative; so
-      // we'll keep it one more than actual index
-      for (HeapIndex i = count; i > 0; --i) {
-	if (data[i-1] == ind_item) {
-	  return Iterator(*this, i-1);
-	}
-      }
-      return end();
-    }
-
-    // reverse find -- start looking from bottom of heap
-    Iterator rfind(const T& item) {
-      // HeapIndex is unsigned, so we can't allow to go negative; so
-      // we'll keep it one more than actual index
-      for (HeapIndex i = count; i > 0; --i) {
-	if (*data[i-1] == item) {
-	  return Iterator(*this, i-1);
-	}
-      }
-      return end();
-    }
-
-    ConstIterator find(const I& ind_item) const {
-      for (HeapIndex i = 0; i < count; ++i) {
-	if (data[i] == ind_item) {
-	  return ConstIterator(*this, i);
-	}
-      }
-      return cend();
-    }
-
-    // when passing in value we do a comparison via operator==
-    ConstIterator find(const T& item) const {
-      for (HeapIndex i = 0; i < count; ++i) {
-	if (*data[i] == item) {
-	  return ConstIterator(*this, i);
-	}
-      }
-      return cend();
-    }
-
-    // reverse find -- start looking from bottom of heap
-    ConstIterator rfind(const I& ind_item) const {
-      // HeapIndex is unsigned, so we can't allow to go negative; so
-      // we'll keep it one more than actual index
-      for (HeapIndex i = count; i > 0; --i) {
-	if (data[i-1] == ind_item) {
-	  return ConstIterator(*this, i-1);
-	}
-      }
-      return cend();
-    }
-
-    // reverse find -- start looking from bottom of heap
-    ConstIterator rfind(const T& item) const {
-      // HeapIndex is unsigned, so we can't allow to go negative; so
-      // we'll keep it one more than actual index
-      for (HeapIndex i = count; i > 0; --i) {
-	if (*data[i-1] == item) {
-	  return ConstIterator(*this, i-1);
-	}
-      }
-      return cend();
-    }
-
-    void promote(T& item) {
-      sift_up(item.*heap_info);
-    }
-
-    void demote(T& item) {
-      sift_down(item.*heap_info);
-    }
-
-    void adjust(T& item) {
-      sift(item.*heap_info);
-    }
-
-    Iterator begin() {
-      return Iterator(*this, 0);
-    }
-
-    Iterator end() {
-      return Iterator(*this, count);
-    }
-
-    ConstIterator cbegin() const {
-      return ConstIterator(*this, 0);
-    }
-
-    ConstIterator cend() const {
-      return ConstIterator(*this, count);
-    }
-
-    friend std::ostream& operator<<(std::ostream& out, const IndIntruHeap& h) {
-      auto i = h.data.cbegin();
-      if (i != h.data.cend()) {
-	out << **i;
-	++i;
-	while (i != h.data.cend()) {
-	  out << ", " << **i;
-	}
-      }
-      return out;
-    }
-
-    // can only be called if I is copyable; copies heap into a vector
-    // and sorts it before displaying it
-    std::ostream&
-    display_sorted(std::ostream& out,
-		   std::function<bool(const T&)> filter = all_filter) const {
-      static_assert(std::is_copy_constructible<I>::value,
-		    "cannot call display_sorted when class I is not copy"
-		    " constructible");
-      auto compare = [this] (const I first, const I second) -> bool {
-	return this->comparator(*first, *second);
-      };
-      std::vector<I> copy(data);
-      std::sort(copy.begin(), copy.end(), compare);
-
-      bool first = true;
-      for (auto c = copy.begin(); c != copy.end(); ++c) {
-	if (filter(**c)) {
-	  if (!first) {
-	    out << ", ";
-	  } else {
-	    first = false;
-	  }
-	  out << **c;
-	}
-      }
-
-      return out;
-    }
-
-
-  protected:
-
-    static IndIntruHeapData& intru_data_of(I& item) {
-      return (*item).*heap_info;
-    }
-
-    void remove(HeapIndex i) {
-      std::swap(data[i], data[--count]);
-      intru_data_of(data[i]) = i;
-      data.pop_back();
-
-      // the following needs to be sift (and not sift_down) as it can
-      // go up or down the heap; imagine the heap vector contains 0,
-      // 10, 100, 20, 30, 200, 300, 40; then 200 is removed, and 40
-      // would have to be sifted upwards
-      // sift(i);
-      sift(i);
-    }
-
-    // default value of filter parameter to display_sorted
-    static bool all_filter(const T& data) { return true; }
-
-    // when i is negative?
-    static inline HeapIndex parent(HeapIndex i) {
-      assert(0 != i);
-      return (i - 1) / K;
-    }
-
-    // index of left child when K==2, index of left-most child when K>2
-    static inline HeapIndex lhs(HeapIndex i) { return K*i + 1; }
-
-    // index of right child when K==2, index of right-most child when K>2
-    static inline HeapIndex rhs(HeapIndex i) { return K*i + K; }
-
-    void sift_up(HeapIndex i) {
-      while (i > 0) {
-	HeapIndex 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
-
-    // use this sift_down definition when K>2; it's more general and
-    // uses a loop; EnableBool insures template uses a template
-    // parameter
-    template<bool EnableBool=true>
-    typename std::enable_if<(K>2)&&EnableBool,void>::type sift_down(HeapIndex i) {
-      if (i >= count) return;
-      while (true) {
-	HeapIndex li = lhs(i);
-
-	if (li < count) {
-	  HeapIndex ri = std::min(rhs(i), count - 1);
-
-	  // find the index of min. child
-	  HeapIndex min_i = li;
-	  for (HeapIndex k = li + 1; k <= ri; ++k) {
-	    if (comparator(*data[k], *data[min_i])) {
-	      min_i = k;
-	    }
-	  }
-
-	  if (comparator(*data[min_i], *data[i])) {
-	    std::swap(data[i], data[min_i]);
-	    intru_data_of(data[i]) = i;
-	    intru_data_of(data[min_i]) = min_i;
-	    i = min_i;
-	  } else {
-	    // no child is smaller
-	    break;
-	  }
-	} else {
-	  // no children
-	  break;
-	}
-      }
-    } // sift_down
-
-    // use this sift_down definition when K==2; EnableBool insures
-    // template uses a template parameter
-    template<bool EnableBool=true>
-    typename std::enable_if<K==2&&EnableBool,void>::type sift_down(HeapIndex i) {
-      if (i >= count) return;
-      while (true) {
-	const HeapIndex li = lhs(i);
-	const HeapIndex ri = 1 + li;
-
-        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 {
-	    // no child is smaller
-            break;
-          }
-        } else {
-	  // no children
-          break;
-        }
-      } // while
-    } // sift_down
-
-    void sift(HeapIndex i) {
-      if (i == 0) {
-	// if we're at top, can only go down
-	sift_down(i);
-      } else {
-	HeapIndex 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 IndIntruHeap
-
-} // namespace crimson