folly/folly/container/IntrusiveHeap.h

/*
 * Copyright (c) Meta Platforms, Inc. and affiliates.
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

/**
 * Skew heap [1] implementation using top-down meld.
 *
 * [1] D.D. Sleator, R.E. Tarjan, Self-Adjusting Heaps,
 * SIAM Journal of Computing, 15(1): 52-69, 1986.
 * http://www.cs.cmu.edu/~sleator/papers/adjusting-heaps.pdf
 */

#pragma once

#include <functional>

#include <boost/intrusive/parent_from_member.hpp>
#include <boost/noncopyable.hpp>
#include <glog/logging.h>
#include <folly/Portability.h>

namespace folly {

/**
 * Base class for items to be inserted into IntrusiveHeap<..., Tag> storing
 * pointers for internal use.
 */
template <class Tag = void>
class IntrusiveHeapNode : private boost::noncopyable { … };

template <class Tag>
IntrusiveHeapNode<Tag>* const IntrusiveHeapNode<Tag>::kUnlinked = …;

template <class T, class Tag>
struct DerivedNodeTraits { … };

template <class T, class Tag, IntrusiveHeapNode<Tag> T::*PtrToMember>
struct MemberNodeTraits { … };

/**
 * IntrusiveHeap implements a skew heap with intrusive pointers to provide
 * O(log(n)) operations on any node in the heap with no separately allocated
 * node type.
 *
 * - To be inserted into an IntrusiveHeap<T, Compare, Tag>, T must inherit from
 *   IntrusiveHeapNode<Tag>, or have a member of type IntrusiveHeapNode<Tag> and
 *   use MemberNodeTraits.
 *
 * - An instance of T may only be included in one IntrusiveHeap for each Tag
 *   type. It may be included in more than one IntrusiveHeap by inheriting from
 *   IntrusiveHeapNode again with a different tag type, or by using composition
 *   with different members.
 */
template <
    class T,
    class Compare = std::less<>,
    class Tag = void,
    class NodeTraitsType = DerivedNodeTraits<T, Tag>>
class IntrusiveHeap {
 public:
  using Node = IntrusiveHeapNode<Tag>;
  using NodeTraits = NodeTraitsType;
  using Value = T;

  IntrusiveHeap() { … }

  IntrusiveHeap(const IntrusiveHeap&) = delete;
  IntrusiveHeap& operator=(const IntrusiveHeap&) = delete;

  IntrusiveHeap(IntrusiveHeap&& other) noexcept
      : … { … }
  IntrusiveHeap& operator=(IntrusiveHeap&&) = delete;

  /**
   * Returns a pointer to the maximum value in the heap, or nullptr if the heap
   * is empty.
   */
  T* top() const { … }

  bool empty() const { … }

  /**
   * Removes the maximum value from the heap and returns it, or nullptr if the
   * heap is empty.
   */
  T* pop() { … }

  /**
   * Visits all items in the heap.
   */
  template <class Visitor>
  void visit(const Visitor& visitor) const { … }

  /**
   * Updates the heap to reflect a change in a given value.
   */
  void update(T* x) { … }

  void push(T* x) { … }

  void erase(T* x) { … }

  /**
   * Check whether this node is included in this heap. Primarily meant for
   * assertions, as containment should be externally tracked.
   */
  bool contains(const T* x) const { … }

  /**
   * Moves the contents of other into *this.
   */
  void merge(IntrusiveHeap other) { … }

 private:
  friend class IntrusiveHeapTest;

  template <class Visitor>
  static void visit(const Visitor& visitor, Node* x) { … }

  /**
   * Merges two subtrees, assigns a parent, populates *out with new subtree.
   */
  FOLLY_ALWAYS_INLINE static void merge(
      Node* a, Node* b, Node* parent, Node** out) { … }

  static Node* asNode(T* x) { … }

  static const Node* asNode(const T* x) { … }

  static T* asT(Node* n) { … }

  static const T* asT(const Node* n) { … }

  static bool compare(const Node* a, const Node* b) { … }

  Node* root_ = nullptr;
};

} // namespace folly