update sources to v12.1.0

[ceph.git] / ceph / src / dmclock / support / src / indirect_intrusive_heap.h

// -*- 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