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=6342e29b16370dc1a5508a360b9fa1c31581428c;hb=812ff6ca9fcd3e629e49d4328905f33eee8ca3f5;hp=0000000000000000000000000000000000000000;hpb=15280273faafb77777eab341909a3f495cf248d9;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
new file mode 100644
index 0000000..6342e29
--- /dev/null
+++ b/src/ceph/src/dmclock/support/src/indirect_intrusive_heap.h
@@ -0,0 +1,549 @@
+// -*- 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